Fair Division via Quantile Shares

We consider the problem of fair division, where a set of m indivisible goods should be distributed fairly among n agents with combinatorial valuations. We propose a novel fairness notion, where an agent assesses the fairness of a bundle by comparing it to a random bundle, in which she gets each good, independently, with probability 1/n. In this framework, a bundle is considered q-quantile fair, for q ∈ (0,1], if it is at least as good as the random bundle with probability at least q.

We show that if a version of the classical Erdos Matching Conjecture is true, then 1/(2e)-quantile fairness is universally feasible, in the following sense: for every n-tuple of monotone valuations, there exists an allocation giving every agent a bundle which is 1/(2e)-quantile fair. This is tight up to a factor of 2. Furthermore, we provide unconditional feasibility results for additive, unit-demand, and matroid-rank valuations for constant values of q. Finally, we compare our notion to other fair share notions in the literature, such as the maximin and proportional share, none of which is universally feasible.

The paper: https://holzman.technion.ac.il/files/2024/07/quantile_shares_journal.pdf
Roh Holzman's homepage: https://holzman.technion.ac.il