Computing Envy-Freeable Allocations with Limited Subsidies

被引:12
作者
Caragiannis, Ioannis [1 ]
Ioannidis, Stavros D. [2 ]
机构
[1] Aarhus Univ, Dept Comp Sci, Aarhus, Denmark
[2] Kings Coll London, Dept Informat, London, England
来源
WEB AND INTERNET ECONOMICS, WINE 2021 | 2022年 / 13112卷
关键词
Fair division; Indivisible goods; Subsidy minimization; Approximation algorithms; INDIVISIBLE GOODS; EQUILIBRIUM; FREENESS;
D O I
10.1007/978-3-030-94676-0_29
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
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.
引用
收藏
页码:522 / 539
页数:18
相关论文
共 30 条
[1]   FAIR ALLOCATION OF INDIVISIBLE GOODS AND CRITERIA OF JUSTICE [J].
ALKAN, A ;
DEMANGE, G ;
GALE, D .
ECONOMETRICA, 1991, 59 (04) :1023-1039
[2]   Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination [J].
Amanatidis, Georgios ;
Markakis, Evangelos ;
Ntokos, Apostolos .
THEORETICAL COMPUTER SCIENCE, 2020, 841 :94-109
[3]  
ARAGONES E, 1995, SOC CHOICE WELFARE, V12, P267
[4]  
Aziz H, 2019, PROCEEDINGS OF THE TWENTY-EIGHTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, P53
[5]  
Aziz H, 2018, AAAI CONF ARTIF INTE, P4638
[6]   Finding Fair and Efficient Allocations [J].
Barman, Siddharth ;
Krishnamurthy, Sanath Kumar ;
Vaish, Rohit .
ACM EC'18: PROCEEDINGS OF THE 2018 ACM CONFERENCE ON ECONOMICS AND COMPUTATION, 2018, :557-574
[7]  
Brustle Johannes, 2020, EC '20: Proceedings of the 21st ACM Conference on Economics and Computation, P23, DOI 10.1145/3391403.3399447
[8]   The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes [J].
Budish, Eric .
JOURNAL OF POLITICAL ECONOMY, 2011, 119 (06) :1061-1103
[9]   The Unreasonable Fairness of Maximum Nash Welfare [J].
Caragiannis, Ioannis ;
Kurokawa, David ;
Moulin, Herve ;
Procaccia, Ariel D. ;
Shah, Nisarg ;
Wang, Junxing .
ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION, 2019, 7 (03)
[10]   Envy-Freeness Up to Any Item with High Nash Welfare: The Virtue of Donating Items [J].
Caragiannis, Ioannis ;
Gravin, Nick ;
Huang, Xin .
ACM EC '19: PROCEEDINGS OF THE 2019 ACM CONFERENCE ON ECONOMICS AND COMPUTATION, 2019, :527-545