TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 30.01.2020



zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

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.


Robert Bredereck
TEL 512

Back to the research colloquium site.

Nach oben



Schnellnavigation zur Seite über Nummerneingabe