Assigning a Small Agreeable Set of Indivisible Items to Multiple Players

Warut SuksompongIJCAI 2016

Introduction

In traditional fair division problems, such as cutting a cake or splitting assets, the goal is to partition a set of items so that each participant receives their own unique bundle. However, many real-world scenarios involve collective consumption, where a group must select a single subset of items for everyone to use. Examples include a committee choosing a software suite for a department or a group of friends packing a single shared bag for a trip.

This paper introduces and explores the concept of an agreeable set: a single subset of items that every player in a group prefers over the items left behind. The research addresses two primary questions: how small can such a set be while guaranteeing its existence, and can we find these sets efficiently?

The Existence of Agreeable Sets

The author establishes a fundamental bound for the existence of these sets. For $m$ items and $n$ players with monotonic preferences (where more items are always preferred to fewer), there always exists an agreeable set of size $\lceil \frac{m+n-1}{2} \rceil$.

To prove this, the paper employs sophisticated tools from combinatorial topology, specifically Kneser’s conjecture regarding the chromatic number of Kneser graphs. By showing that the absence of a small agreeable set would lead to a mathematical contradiction in how the space of possible subsets is "colored," the author proves that the bound is not only universal but also tight—meaning no smaller size can be guaranteed for all cases.

Key Insights: The "Half-Item" Rule

A striking takeaway from this research is that the size of the required agreeable set does not explode as more players are added. In the formula $\lceil \frac{m+n-1}{2} \rceil$, each additional player effectively "costs" the group only an extra half-item in the chosen set to ensure everyone remains satisfied. This suggests that collective agreement is surprisingly achievable, even when players have wildly divergent tastes.

Preference Modeling and Algorithms

The paper distinguishes between two types of preferences:

  • Monotonic Preferences: Players always prefer more items. This is sufficient to guarantee that a small agreeable set exists.
  • Responsive Preferences: A stricter condition where replacing an item with a more preferred one always improves the set. This condition is generally required to find the set efficiently.

Algorithmic Results

While the existence proof covers any number of players, the paper focuses on constructive algorithms for smaller groups:

  • Two Players: For $n=2$, an agreeable set of size $\lceil \frac{m+1}{2} \rceil$ can be found in polynomial time using only the players' rankings of individual items.
  • Three Players: For $n=3$, the author provides a polynomial-time algorithm to find a set of size $\lceil \frac{m}{2} \rceil + 1$. This algorithm is significantly more complex and requires a "preference oracle" to ask players to compare specific subsets, as individual item rankings are insufficient for three or more players.

Welfare and Approximation

Beyond the binary of "agreeable" or "not," the paper examines how well these sets satisfy players' underlying utilities. If players have subadditive utility functions (where the value of a whole is less than or equal to the sum of its parts), an agreeable set provides a 2-approximation of the maximum possible individual welfare for every player. This bridges the gap between social choice (picking one outcome) and fair division (maximizing individual utility).

Limitations and Future Directions

The primary challenge remains scaling these results to larger groups ($n > 3$). The author notes that the three-player algorithm is already quite involved, suggesting that finding agreeable sets for many players might be computationally "hard" (potentially PPAD-hard). Additionally, the requirement for subset-based preference queries for $n \ge 3$ increases the informational burden on participants. Future research may look into "envy-free" allocations between groups of players or further explore the computational boundaries of collective agreement.

Summary updated

BibTeX
@inproceedings{suksompong2016assigning,
  author = {Warut Suksompong},
  title = {{Assigning a Small Agreeable Set of Indivisible Items to Multiple Players}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure