Aarhus University Seal

Computing Envy-Freeable Allocations with Limited Subsidies

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Fair division has emerged as a very hot topic in EconCS research, and envy-freeness is among the most compelling fairness concepts. An allocation of indivisible items to agents is envy-free if no agent prefers the bundle of any other agent to his own in terms of value. As envy-freeness is rarely a feasible goal, there is a recent focus on relaxations of its definition. An approach in this direction is to complement allocations with payments (or subsidies) to the agents. A feasible goal then is to achieve envy-freeness in terms of the total value an agent gets from the allocation and the subsidies. We consider the natural optimization problem of computing allocations that are envy-freeable using the minimum amount of subsidies. As the problem is NP-hard, we focus on the design of approximation algorithms. On the positive side, we present an algorithm which, for a constant number of agents, approximates the minimum amount of subsidies within any required accuracy, at the expense of a graceful increase in the running time. On the negative side, we show that, for a superconstant number of agents, the problem of minimizing subsidies for envy-freeness is not only hard to compute exactly (as a folklore argument shows) but also, more importantly, hard to approximate.

Original languageEnglish
Title of host publicationWeb and Internet Economics : 17th International Conference, WINE 2022
EditorsMichal Feldman, Hu Fu, Inbal Talgam-Cohen
Number of pages18
Place of publicationCham
Publication year2022
ISBN (print)9783030946753
Publication statusPublished - 2022
Event17th International Conference on Web and Internet Economics, WINE 2021 - Virtual, Online
Duration: 14 Dec 202117 Dec 2021


Conference17th International Conference on Web and Internet Economics, WINE 2021
ByVirtual, Online
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13112 LNCS

Bibliographical note

Publisher Copyright:
© 2022, Springer Nature Switzerland AG.

    Research areas

  • Approximation algorithms, Fair division, Indivisible goods, Subsidy minimization

See relations at Aarhus University Citationformats

ID: 271449122