Complexity of Efficient and Envy-Free Resource Allocation: Few Agents, Resources, or Utility Levels

Bernhard Bliem, Robert Bredereck, Rolf NiedermeierIJCAI 2016

Abstract

Finding resource allocations that are simultaneously fair (envy-free) and efficient (Pareto-optimal) is a fundamental challenge in multi-agent systems. While this problem is generally $\Sigma_2^P$-complete, this paper identifies "islands of tractability" by exploring specific constraints. Through parameterized complexity analysis, the authors demonstrate that the problem becomes computationally manageable when the number of resources is small or when there is a limited variety of utility levels among agents.

Introduction

The core of this research is the EEF-ALLOCATION problem: distributing a set of indivisible items among agents such that the resulting allocation is both Envy-Free (no agent prefers another's bundle) and Pareto-Efficient (no agent can be made better off without harming another).

In fair division, achieving both properties is notoriously difficult. While envy-freeness can be trivial (e.g., giving nothing to everyone) and efficiency can be simple (e.g., giving everything to one agent), their intersection is computationally brutal. Previous work established that this problem is generally harder than standard NP-complete problems. This paper seeks to identify specific scenarios—defined by parameters like the number of agents, resources, or utility values—where efficient algorithms exist.

Methodology

The authors utilize Parameterized Complexity Analysis to dissect the problem's hardness. Rather than focusing solely on total input size, they analyze how complexity scales with specific parameters:

  • $n$: The number of agents.
  • $m$: The number of resources.
  • $z$: The number of distinct utility values (e.g., $z=3$ if agents only use values 0, 1, and 2).

The study covers two primary preference models:

  1. Dichotomous Preferences: Agents evaluate bundles based on logical formulas (liking or disliking a bundle).
  2. Additive Preferences: The utility of a bundle is the sum of the values of its individual items.

To establish tractability (upper bounds), the researchers employ Integer Linear Programming (ILP)—leveraging Lenstra’s theorem for fixed variables—and Dynamic Programming. For hardness (lower bounds), they use reductions to the Boolean Hierarchy, providing more precise complexity bounds than traditional NP-hardness proofs.

Key Results

The paper's findings are summarized in a comprehensive "complexity map" that highlights how different constraints impact computational feasibility.

Table 1: Summary of complexity results for EEF-ALLOCATION under various preference types and parameters.

The Impact of Parameters

  • Resource Constraints ($m$): When the number of resources is small, the problem is Fixed-Parameter Tractable (FPT). The computational explosion depends only on $m$, making it manageable regardless of the number of agents.
  • Agent and Utility Constraints ($n$ and $z$): Having a small number of agents ($n$) is not sufficient for tractability in additive preferences. However, when both the number of agents and the number of distinct utility levels ($z$) are small, the problem becomes tractable via ILP-FPT techniques.
  • Preference Types: For dichotomous preferences, the complexity is tied to the number of agents $n$ within the Boolean Hierarchy ($BH_n$), suggesting the problem requires approximately $n$ calls to an NP-solver. In the case of identical preferences (where all agents value items the same way), the problem is generally easier but remains $W[1]$-complete relative to the number of agents.

Discussion and Future Work

While the identification of FPT results is a significant theoretical step, the authors acknowledge certain limitations. The constants involved in ILP-based algorithms (such as Lenstra's) can be extremely large, which may hinder practical performance even for "small" parameters.

Future research directions include exploring how complexity changes when agents do not have a complete ranking of all possible bundles, and investigating the complexity of relaxed fairness notions, such as "envy-free up to one item" (EF1), which are widely studied in modern fair division literature.

Summary updated

BibTeX
@inproceedings{bliem2016complexity,
  author = {Bernhard Bliem and Robert Bredereck and Rolf Niedermeier},
  title = {{Complexity of Efficient and Envy-Free Resource Allocation: Few Agents, Resources, or Utility Levels}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure