Deciding Morality of Graphs is NP-complete
In order to find a causal explanation for data presented in the form of covariance and concentration matrices it is necessary to decide if the graph formed by such associations is a projection of a directed acyclic graph (dag). We show that the general problem of deciding whether such a dag exists is NP-complete.
Code (1)
Similar Papers 제목 키워드 기반
The Complexity of Morality: Checking Markov Blanket Consistency with DAGs via Morality
A family of Markov blankets in a faithful Bayesian network satisfies the symmetry and consistency properties. In this paper, we draw a bijection between families of consistent Markov blankets and moral graphs. We define …
A Polynomial-Time Algorithm for EFX Orientations of Chores
This paper addresses the problem of finding EFX orientations of graphs of chores, in which each vertex corresponds to an agent, each edge corresponds to a chore, and a chore has zero marginal utility to an agent if its c…
Knowledge Graphs meet Moral Values
Operationalizing morality is crucial for understanding multiple aspects of society that have moral values at their core {--} such as riots, mobilizing movements, public debates, etc. Moral Foundations Theory (MFT) has be…
Knowledge GraphsAligning AI With Shared Human Values
We show how to assess a language model's knowledge of basic concepts of morality. We introduce the ETHICS dataset, a new benchmark that spans concepts in justice, well-being, duties, virtues, and commonsense morality. Mo…
Ethicsreinforcement-learningReinforcement Learning (RL)World KnowledgeDirected Regular and Context-Free Languages
We study the problem of deciding whether a given language is directed. A language $L$ is \emph{directed} if every pair of words in $L$ have a common (scattered) superword in $L$. Deciding directedness is a fundamental pr…