Improving fair share guarantees for complex value settings in item division
Toward Constant-Factor Maximin Share Guarantees for Subadditive Valuations
Computer Science and Game Theory
Summary
Dividing items fairly among many people is hard when everyone's value for groups of items isn't simple to add up. This paper improves how close we can get to a fair share for each person in very complex situations, making it much better than before. The authors break down complex value systems into levels and show constant fair share guarantees for several of these, including some where previous results didn't exist. They also develop new technical tools that make these guarantees stronger and more reliable.
What this means in practice
- •For market designers: Design allocation mechanisms that guarantee fair minimum shares in complex valuation settings among participants.
- •For auction platform developers: Build bidding systems that robustly ensure fairness and budget compliance based on new probabilistic fairness guarantees.
A theory result. No direct application yet.
Authors
Bo Li, Ankang Sun
Abstract
For $n$ agents and $m$ indivisible goods, an agent's maximin share (MMS) is the largest minimum bundle value she can obtain by partitioning the goods into $n$ bundles. Constant MMS approximations are known for additive, submodular, or XOS valuations, but whether such a guarantee exists for general subadditive valuations remains open. We advance this question in two directions. For general subadditive valuations, we exponentially improve the guarantee from $Ω(1/\log\log n)$ to $Ω(1/\log^* n)$, where $\log^* n$ is the iterated logarithm. We then seek constant MMS guarantees under additional structure on subadditive valuations by studying $q$-partitioning valuations: every partition of a bundle into at most $q$ groups admits nonnegative group prices that sum to the bundle's value and whose sum on any collection of groups is at most the value of their union. This hierarchy ranges from subadditivity at $q=2$ to XOS for $q\ge m$. We give the first study of MMS in the intermediate classes and prove constant guarantees whenever $q/n$ has a fixed positive lower bound, including $1/6$ for $q\ge n$ and $1/4$ for $q\ge2n$. For XOS valuations, we further improve the universal guarantee from $4/17\approx 0.2353$ to $5/16=0.3125$. For subadditive valuations, we prove a bidding amplification theorem that gives an exponential bound on each agent's probability of receiving less than half her MMS, while satisfying her budget in every outcome. For $q$-partitioning valuations, we give a scalar criterion that converts bounds on the value lost from disjoint deletions within a bundle into bounds on potential losses, even when an agent contributes zero below the target bundle value. For XOS valuations, we prove a reservation theorem that selects goods for integral assignment together with auxiliary additive valuations and accounts for the loss in rounding.