J. Lang

JAIR Journal 2008 Journal Article

Efficiency and Envy-freeness in Fair Division of Indivisible Goods: Logical Representation and Complexity

• S. Bouveret
• J. Lang

We consider the problem of allocating fairly a set of indivisible goods among agents from the point of view of compact representation and computational complexity. We start by assuming that agents have dichotomous preferences expressed by propositional formulae. We express efficiency and envy-freeness in a logical setting, which reveals unexpected connections to nonmonotonic reasoning. Then we identify the complexity of determining whether there exists an efficient and envy-free allocation, for several notions of efficiency, when preferences are represented in a succinct way (as well as restrictions of this problem). We first study the problem under the assumption that preferences are dichotomous, and then in the general case.

JAIR Journal 2008 Journal Article

The Computational Complexity of Dominance and Consistency in CP-Nets

• J. Goldsmith
• J. Lang
• M. Truszczynski
• N. Wilson

We investigate the computational complexity of testing dominance and consistency in CP-nets. Previously, the complexity of dominance has been determined for restricted classes in which the dependency graph of the CP-net is acyclic. However, there are preferences of interest that define cyclic dependency graphs; these are modeled with general CP-nets. In our main results, we show here that both dominance and consistency for general CP-nets are PSPACE-complete. We then consider the concept of strong dominance, dominance equivalence and dominance incomparability, and several notions of optimality, and identify the complexity of the corresponding decision problems. The reductions used in the proofs are from STRIPS planning, and thus reinforce the earlier established connections between both areas.

JAIR Journal 2003 Journal Article

Propositional Independence - Formula-Variable Independence and Forgetting

• J. Lang
• P. Liberatore
• P. Marquis

Independence -- the study of what is relevant to a given problem of reasoning -- has received an increasing attention from the AI community. In this paper, we consider two basic forms of independence, namely, a syntactic one and a semantic one. We show features and drawbacks of them. In particular, while the syntactic form of independence is computationally easy to check, there are cases in which things that intuitively are not relevant are not recognized as such. We also consider the problem of forgetting, i.e., distilling from a knowledge base only the part that is relevant to the set of queries constructed from a subset of the alphabet. While such process is computationally hard, it allows for a simplification of subsequent reasoning, and can thus be viewed as a form of compilation: once the relevant part of a knowledge base has been extracted, all reasoning tasks to be performed can be simplified.

AAAI Conference 1998 Conference Paper

Reasoning under Inconsistency Based on Implicitly-Specified Partial Qualitative Probability Relations: A Unified Framework

• S. Benferhat
• J. Lang
• A. Saffiotti