Theory Seminar: Please join us on February 17th at 11am in Siebel 3401 where Vishnu Narayan will give a talk, “Fair Division via Quantile Shares”. Please see their abstract below:
We consider the problem of fair division, where a set of indivisible goods should be distributed fairly among a set of agents with combinatorial valuations. There are two categories of fairness notions in the literature: envy-based fairness, in which an agent compares its bundle with the bundles of the other agents, and share-based fairness, in which an agent compares the value of its bundle against a threshold interpreted as its fair share. A fairness notion is universally feasible if it admits a fair allocation for every profile of monotone valuations. While some well-studied envy-based notions, such as EF1, are known to be universally feasible, no known non-trivial share-based notion and no constant approximation of any such notion is feasible for all monotone valuations.
We propose a new (parameterized) share notion, the quantile share, in which an agent assesses the fairness of a bundle by comparing its value to the value obtained in a random allocation. Our main result establishes a strong connection between the feasibility of quantile shares and the classical Erdős Matching Conjecture. Specifically, we show that if a version of this conjecture is true, then the 1/2e -quantile share is universally feasible. Furthermore, we provide unconditional (and in some cases tight) feasibility results for additive, unit-demand and matroid-rank valuations for constant values of q. Finally, we discuss the implications of our results for other share notions.
Joint work with Y. Babichenko, M. Feldman and R. Holzman. STOC 2024. arxiv.org/abs/2312.01874 .