Abstract
Fairly dividing indivisible goods among agents with complex preferences is a fundamental challenge in computational social choice. This paper, presented at AAAI 2022, provides significantly improved fairness guarantees for allocations under subadditive and fractionally subadditive (XOS) valuations. For subadditive preferences, the authors achieve an exponential improvement in the Maximin Share (MMS) guarantee relative to the number of agents. For XOS valuations, they push the state-of-the-art bound from $1/5$ to approximately $1/4.6$.
Introduction
The problem of fair division involves allocating a set of indivisible items among $n$ agents such that each agent perceives the allocation as "fair." A standard benchmark for fairness is the Maximin Share (MMS). The MMS value for an agent is the maximum value they can guarantee themselves if they were to partition the items into $n$ bundles and then receive the least preferred bundle. While an MMS-fair allocation (where everyone gets their MMS value) is guaranteed for divisible goods, it may not exist for indivisible items. Consequently, researchers seek $\alpha$-MMS guarantees, ensuring every agent receives at least a fraction $\alpha$ of their MMS value.
This research focuses on two broad classes of valuation functions:
- Subadditive: A general class where the value of a union of sets is no more than the sum of their individual values ($V(A \cup B) \leq V(A) + V(B)$).
- Fractionally Subadditive (XOS): A subset of subadditive functions typically used to model items that act as substitutes.
Methodological Framework
The authors employ distinct algorithmic strategies to address the complexities of these two valuation classes.
Multiallocation and Random Resolution for Subadditive Valuations
Subadditive functions are notoriously difficult to handle because they lack strong concentration properties; the value of a random subset can vary significantly. To overcome this, the authors propose a two-step approach:
- Configuration Linear Program (LP): The algorithm first constructs a "multiallocation" using a Configuration LP. In this phase, items are assigned to multiple agents (up to $O(\log n)$ agents each), ensuring that each agent's pool of items is sufficiently "rich" to be partitioned into many bundles of high value.
- Random Resolution: The multiallocation is then "thinned" by assigning each item to exactly one of its candidate agents at random. The authors prove that because the initial pools were sufficiently redundant, at least one high-value bundle survives for each agent with high probability.
Refined Bounded Welfare for XOS Valuations
For XOS valuations, the paper refines the "bounded welfare" technique. This involves maximizing a modified social welfare objective where individual agent utilities are capped at a specific threshold. By conducting a granular analysis of "contribution functions"—measuring the marginal value an item adds to a bundle relative to its social welfare cost—the authors formulate an optimization program to derive a tighter fairness guarantee.
Key Results and Improvements
The primary contribution of this work is the substantial improvement of existence guarantees for $\alpha$-MMS allocations.
As shown in the table above, the paper achieves the following:
- Subadditive Valuations: The guarantee is improved from $\Omega(1/(n \log n))$ to $\Omega(1/(\log n \log \log n))$. This represents a significant shift, making the bound polylogarithmic in the number of agents $n$, rather than inversely linear.
- XOS Valuations: The existence guarantee is improved from $0.2$ ($1/5$) to approximately $0.219$ ($1/4.6$). While the numerical change appears small, it represents a significant advancement in the analytical techniques used for XOS functions.
Conclusion and Future Directions
This work narrows the gap in our understanding of fair allocation for complex preferences. However, several open questions remain. For subadditive valuations, a constant-factor guarantee (independent of $n$) is still elusive, with the current upper bound standing at $1/2$. Additionally, while the paper establishes the existence of these allocations, the computational complexity of finding them—especially for subadditive functions that are hard to represent—remains a critical area for future research. Finally, the $1/4.6$ bound for XOS valuations is likely not tight, suggesting further room for improvement toward the $1/2$ theoretical limit.
Summary updated