Approximating Fair Division on D-Claw-Free Graphs

Zbigniew LoncIJCAI 2023 · DOI

TL;DR

This paper tackles the challenge of fairly dividing indivisible goods that are structured as a graph, where agents must receive connected sets of goods. They introduce new approximation guarantees for fair division criteria (maximin share and proportional share) specifically for a class of graphs called "d-claw-free" graphs, which are common in real-world scenarios.

What Problem Does This Paper Address?

Fairly dividing indivisible goods among agents is a long-standing problem in economics and computer science. Unlike divisible goods (like cake), indivisible items (like houses or land plots) make perfect fairness difficult to achieve. Traditional fairness criteria like "envy-freeness" and "proportionality" often have no solution when goods are indivisible. A more recent criterion, "maximin share fairness," aims to give each agent at least the value of the best bundle they could create for themselves if they were to divide the goods into equal shares.

However, even maximin share fairness can be impossible to satisfy. This paper focuses on a specific, practical constraint: the goods themselves form a graph, and agents must receive connected subgraphs of this "graph of goods." This constraint arises in scenarios like allocating land plots that must be contiguous or assigning rooms in a building where adjacency matters. The challenge is to find allocations that are "fair" (satisfy certain criteria) while respecting this connectivity requirement, and to provide guarantees on how close these allocations are to perfect fairness when perfect fairness is impossible.

Methods

The paper introduces new theoretical results for fair division on graphs, focusing on two key fairness criteria:

  • Proportional Share: Each agent receives a bundle of goods whose value is at least 1/n of the total value of all goods (where n is the number of agents).
  • Maximin Share: Each agent receives a bundle of goods whose value is at least their "maximin share," which is the value of the worst bundle they could guarantee themselves if they were to partition the goods into n bundles.

The core of their contribution lies in proving approximation guarantees for these criteria on a specific class of graphs: d-claw-free graphs. These are graphs that do not contain a "star" graph with d+1 edges as an induced subgraph. This class includes many common graph types, such as graphs with bounded maximum degree.

Key methodological elements include:

  • Proving a Theorem for Proportional Allocations: They establish that for d-claw-free graphs and agents whose individual item valuations are bounded (a-proportionally bounded), a β-proportional allocation always exists. The value of β depends on the graph's properties (d) and the agents' valuation bounds (α).
  • Proving a Theorem for Maximin Share Allocations: They show that for d-claw-free graphs, an allocation exists that guarantees each agent at least a certain fraction (specifically, 1/(d+1)) of their maximin share.
  • A Key Lemma for Reducing Complexity: A crucial lemma is introduced that allows them to reduce the problem of finding approximate maximin share allocations for arbitrary agents to the problem for agents with bounded utility functions. This lemma is applicable to a broader class of "hereditary" graphs.
  • Constructing Algorithms (Implicitly): While the paper focuses on existence proofs, the methods described are constructive and can be translated into algorithms for finding these approximate fair allocations.

Datasets

Not discussed in the paper. The paper focuses on theoretical results and does not involve empirical evaluation on specific datasets.

Key Insights and Ideas

  • Connectivity Matters: The requirement that allocated bundles must be connected subgraphs significantly complicates fair division, often making perfect fairness impossible. This paper provides a way to quantify how "fair" an allocation can be under this constraint.
  • Graph Structure is Key: The "d-claw-free" property of the graph of goods is critical. It allows for stronger fairness guarantees than might be possible for arbitrary graphs. This suggests that understanding the structural properties of the goods' relationships is vital for designing fair allocation mechanisms.
  • Bounded Valuations Enable Better Guarantees: For proportional allocations, having agents with bounded valuations (i.e., no single item is disproportionately valuable compared to their total share) leads to better approximation ratios.
  • Maximin Share is More Robust: The paper shows that even for arbitrary agents (not necessarily with bounded valuations), a guaranteed fraction of the maximin share can be achieved for d-claw-free graphs. This suggests that the maximin share criterion is more resilient to agent behavior in this setting.
  • The "Edge Variant" Connection: The paper highlights a connection to the "edge variant" of fair division, where edges of a graph represent goods. This problem is equivalent to fair division on the line graph of the original graph, and line graphs are known to be 3-claw-free, providing a strong motivation for studying this graph class.

Key Results

  • Proportional Allocation Guarantee: For connected (d+1)-claw-free graphs and agents with a-proportionally bounded valuations, an allocation exists that guarantees each agent a bundle of value at least β times their proportional share, where β is a specific function of d and α (e.g., β = (d-1-α)/(d-1) for d≥3).
  • Maximin Share Guarantee: For any (d+1)-claw-free graph (connected or not) and any set of agents, an allocation exists that guarantees each agent at least 1/(d+1) of their maximin share.
  • Sharpness of Results: The paper provides examples demonstrating that the approximation ratios achieved for proportional allocations are tight, meaning no better general guarantee can be made for the studied graph classes. For maximin share, tightness results are not presented but are suggested as an area for future work.

Limitations and Future Work

  • Maximin Share Tightness: The authors note that they do not have a tightness result for their maximin share approximation guarantee (Theorem 2). They suggest that exploring this would be valuable.
  • Computational Complexity: While the paper provides theoretical guarantees for the existence of fair allocations, the proofs for maximin share allocations do not directly translate into efficient polynomial-time algorithms. This is because computing the "packing maximin share" (a key component) is NP-hard. Finding polynomial-time algorithms for these allocations remains an open problem.
  • General Graphs: The paper focuses on d-claw-free graphs. A significant open question is whether a constant approximation ratio for maximin share allocations exists for any graph, not just this specific class.
  • Specific Graph Classes: While cycles were mentioned as a case where a √5-1 approximation is known, the paper's results for d-claw-free graphs might offer improvements or different perspectives for specific subclasses of cycles or other graph structures.

Summary updated

BibTeX
@inproceedings{lonc2023approximating,
  author = {Zbigniew Lonc},
  title = {{Approximating Fair Division on D-Claw-Free Graphs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/315},
}
Figure