Timezone: »

 
Poster
Optimal Efficiency-Envy Trade-Off via Optimal Transport
Steven Yin · Christian Kroer

Wed Nov 30 09:00 AM -- 11:00 AM (PST) @ Hall J #314
in Poster Session 3 »
We consider the problem of allocating a distribution of items to $n$ recipients where each recipient has to be allocated a fixed, pre-specified fraction of all items, while ensuring that each recipient does not experience too much envy. We show that this problem can be formulated as a variant of the semi-discrete optimal transport (OT) problem, whose solution structure in this case has a concise representation and a simple geometric interpretation. Unlike existing literature that treats envy-freeness as a hard constraint, our formulation allows us to \emph{optimally} trade off efficiency and envy continuously. Additionally, we study the statistical properties of the space of our OT based allocation policies by showing a polynomial bound on the number of samples needed to approximate the optimal solution from samples. Our approach is suitable for large-scale fair allocation problems such as the blood donation matching problem, and we show numerically that it performs well on a prior realistic data simulator.
Keywords: optimal transport · fair division · Resource Allocation

Author Information

Steven Yin (Scriptus.app)
Christian Kroer (Columbia University)

More from the Same Authors