Seminars
View all Seminars | Download ICal for this eventFair Division via Quantile Shares
Series: Bangalore Theory Seminars
Speaker: Vishnu Narayan Tel-Aviv University, Israel
Date/Time: Jan 17 17:00:00
Location: CSA Seminar Hall (Room No. 254, First Floor)
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 its value to the value of 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 the quantile. Finally, we discuss the implications of our results for other share notions.
Joint work with Y. Babichenko, M. Feldman, and R. Holzman.
Microsoft teams link:
Link
We are grateful to the Kirani family for generously supporting the theory seminar series
Hosts: Rameesh Paul, Rahul Madhavan, Rachana Gusain, KVN Sreenivas