Algorithmics and Computational Complexity Research GroupTalk 30.01.2020

# High-Multiplicity Fair Allocation Made More Practical

Robert Bredereck (TU Berlin)

The envy-free, Pareto-efficient allocation of indivisible goods leads to computationally hard problems. There is a big variety of modeling issues, such as agent-specific utility functions or (high numbers of) types of goods. In recent work by Bredereck et al. [EC 2019], this has been addressed by showing (theoretical) fixed-parameter tractability results in the context of high-multiplicity fair allocation'', exploiting parameters such as number of agents or maximum absolute utility values or number of item types. To this end, they made delicate use of tools from integer linear programming.

In this work, we engineer'' their work towards practical usefulness, thereby being able to solve all real-world instances from the state-of-art online  platform spliddit.org for provably fair solutions''. Besides providing the foundations for a fast tool for fair allocations, we also offer a flexible framework with the possibility to relax fairness or efficiency demands so to e.g. allow tradeoffs between fairness and social welfare. Moreover, our framework has nice interpretability features which makes it possible to perform
further explorations in cases when no envy-free and efficient allocations exist.


Date
Speaker
Location
Language
30.01.2020
16:15
Robert Bredereck
TEL 512
English

Back to the research colloquium site.

To top