EconCS Seminar

 

Lecturer: 

Prof. Yakov Babichenko (Technion)

Title: 

Fair Division via Quantile Shares

Abstract: 

We consider the problem of fair division, where indivisible goods should be distributed fairly among agents with valuations over bundles of goods. To capture fairness, we adopt the notion of shares, by which every agent has a fair share, according to some definition, and an allocation is considered fair if the value of every agent for her bundle (weakly) exceeds her fair share. We introduce a new notion of shares in which an agent deems a bundle fair or unfair based on how it compares to her value in a uniform allocation of the goods. Specifically, for every 0<q<1, a bundle is q-quantile fair if the probability of getting a (weakly) worse bundle in a uniform allocation is at least q. The question that drives us in this work is the feasibility of q-quantile shares. Namely, for what values of q, every profile of (monotone) valuations admits a q-quantile fair allocation.

Our main result establishes a strong connection between the feasibility of quantile shares and the classical Erdos Matching Conjecture. Specifically, we show that if the rainbow version of the Erdos Matching Conjecture is true, then the (0.5/e)-quantile share is feasible with respect to all monotone valuations, and this result is tight up to a factor of 2; that is, the q-quantile share is infeasible for q > 1/e. In addition, we provide unconditional feasibility results for special cases. Specifically, we show that every profile of additive (respectively, unit-demand or matroid-rank) valuations admits a q-quantile fair allocation for q=0.14/e (respectively, for q=1/e). Finally, we discuss the implications of our results for other share notions.

Location: 

Room 130, Feldman Building, Edmond J. Safra Campus.