| Title | : | Fair Division via Quantile Shares |
| Speaker | : | Vishnu V. Narayan (PostDoctoral Fellow, Tel Aviv University) |
| Details | : | Wed, 27 Dec, 2023 11:00 AM @ SSB-334 |
| Abstract: | : | 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. Broadly, there are two categories of fairness notions in the literature: envy-based fairness and share-based fairness. 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 universally feasible, no known non-trivial share based notion (and no constant approximation of any of them) is feasible for all monotone valuations. We propose a novel share notion (the quantile share) where an agent assesses the fairness of a bundle by comparing it to her valuation 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 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. |
