Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity

Sylvain Bouveret, Jérôme LangIJCAI 2005

Abstract

This paper investigates the computational complexity of finding allocations of indivisible goods that are simultaneously envy-free and Pareto efficient. By utilizing propositional logic to represent agent preferences compactly, the authors establish a formal link between fair division and nonmonotonic reasoning. The study proves that determining the existence of such allocations is $\Sigma^p_2$-complete, revealing that the problem resides at a higher level of complexity than standard NP-complete problems and suggesting a deep connection to skeptical inference in default logic.

Introduction

Fair division is a fundamental problem in social choice theory, focusing on the allocation of resources among agents such that the resulting distribution is perceived as "fair." Two primary criteria define this fairness: Envy-freeness (EF), where no agent prefers another's bundle over their own, and Pareto Efficiency (PE), where no alternative allocation can make an agent better off without making another worse off.

While these concepts are well-understood for divisible goods (e.g., "cake-cutting"), they become significantly more complex when dealing with indivisible goods, such as houses, shifts, or specific assets. In these scenarios, items cannot be split, and the number of possible allocations grows exponentially. This paper addresses the gap in existing literature regarding the computational complexity of finding Efficient and Envy-Free (EEF) allocations when preferences are represented compactly rather than through exhaustive lists.

Logical Representation of Preferences

The authors focus on dichotomous preferences, a model where an agent is either satisfied or unsatisfied with a given bundle. To represent these preferences efficiently, they use propositional logic. Each agent $i$ is associated with a propositional formula $\phi_i$. An agent is satisfied if the bundle they receive satisfies $\phi_i$, and unsatisfied otherwise.

This logical approach allows for a more nuanced analysis of the problem:

  • Mapping to SAT: Finding an envy-free allocation can be reduced to a standard satisfiability (SAT) problem.
  • Nonmonotonic Reasoning: The search for an efficient allocation is shown to be equivalent to finding "maximal consistent subsets" of formulas. This connects fair division to Supernormal Default Logic, a framework in AI used for reasoning with defaults and exceptions.

Complexity Results

The core of the paper is a rigorous analysis of the computational hardness of finding EEF allocations. The results indicate that the problem is significantly more difficult than previously assumed.

The General Case

The problem of deciding whether an EEF allocation exists is $\Sigma^p_2$-complete. This placement in the polynomial hierarchy suggests that the problem is "harder" than NP-complete problems, making it unlikely that a general-purpose efficient algorithm exists for large-scale instances.

Specific Constraints

The authors also explored how various constraints affect this complexity:

  • Identical Preferences: If all agents share the exact same preferences, the complexity drops to NP-complete (for a fixed number of agents).
  • Two-Agent Case: For exactly two agents with monotonic preferences (where more goods are always better), the problem remains NP-complete.
  • Social Welfare: If the goal shifts from Pareto efficiency to maximizing utilitarian or egalitarian social welfare, the complexity is categorized as $\Delta^p_2$-complete.

Insights and Implications

The most striking insight of this research is the "Aha!" connection between fair division and skeptical inference in default logic. This implies that the search for fair and efficient outcomes is essentially a problem of automated reasoning. Consequently, tools developed for belief revision and nonmonotonic reasoning could potentially be adapted to solve fair division problems.

Furthermore, the authors demonstrate that assuming monotonicity does not simplify the problem. Even when agents always prefer more items to fewer, the $\Sigma^p_2$-completeness persists, highlighting the inherent difficulty of balancing envy-freeness with efficiency in discrete settings.

Conclusion and Future Work

The high computational complexity identified in this paper presents a significant challenge for practical applications. However, it also opens several avenues for future research:

  1. Algorithm Design: Researchers can explore the use of Answer Set Programming (ASP) and other nonmonotonic reasoning tools to implement practical solvers for fair division.
  2. Approximation: Given the hardness of finding perfect EEF allocations, future studies should investigate approximate envy-freeness (e.g., minimizing the number of envious agents or items).
  3. Additive Preferences: The complexity of the case where items have specific numerical values (additive preferences) remains a major open question in the field.

By bridging the gap between social choice theory and formal logic, this work provides a robust framework for understanding the limits of automated fair division.

Summary updated

BibTeX
@inproceedings{bouveret2005efficiency,
  author = {Sylvain Bouveret and Jérôme Lang},
  title = {{Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
}
Figure