TY - GEN
T1 - EFX Under Budget Constraint
AU - Dai, Sijia
AU - Gao, Guichen
AU - Liu, Shengxin
AU - Lim, Boon Han
AU - Ning, Li
AU - Xu, Yicheng
AU - Zhang, Yong
N1 - Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
N2 - Fair division captures many real-world scenarios and plays an important role in many research fields including computer science, economy, operations research, etc. For the problem of indivisible goods allocation, it is well-known that an allocation satisfying the maximum Nash Social Welfare (Max-NSW) is envy-free up to one good (EF1), which is an important fairness concept. However, EF1 is often considered to be somewhat weak since one may remove the most valuable good. In this paper, we investigate the relationship between the Max-NSW allocation and a stronger fairness concept, envy-free up to any good (EFX), which means the envyness disappears after the removal of the least valuable good. We focus on the budget-feasible variant in which each agent has a budget to cover the total cost of goods she gets. We show that a Max-NSW allocation guarantees 14 -EFX when agents’ value are in the Binary { 0, 1 }. Moreover, we provide an algorithm to find a budget-feasible EFX allocation for the Binary variant.
AB - Fair division captures many real-world scenarios and plays an important role in many research fields including computer science, economy, operations research, etc. For the problem of indivisible goods allocation, it is well-known that an allocation satisfying the maximum Nash Social Welfare (Max-NSW) is envy-free up to one good (EF1), which is an important fairness concept. However, EF1 is often considered to be somewhat weak since one may remove the most valuable good. In this paper, we investigate the relationship between the Max-NSW allocation and a stronger fairness concept, envy-free up to any good (EFX), which means the envyness disappears after the removal of the least valuable good. We focus on the budget-feasible variant in which each agent has a budget to cover the total cost of goods she gets. We show that a Max-NSW allocation guarantees 14 -EFX when agents’ value are in the Binary { 0, 1 }. Moreover, we provide an algorithm to find a budget-feasible EFX allocation for the Binary variant.
KW - Budget constraint
KW - Envy-free up to any good
KW - Fair division
KW - Maximum nash social welfare
UR - https://www.scopus.com/pages/publications/85147844102
U2 - 10.1007/978-3-031-20796-9_1
DO - 10.1007/978-3-031-20796-9_1
M3 - 会议稿件
AN - SCOPUS:85147844102
SN - 9783031207952
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 3
EP - 14
BT - Frontiers of Algorithmic Wisdom - International Joint Conference, IJTCS-FAW 2022, Revised Selected Papers
A2 - Li, Minming
A2 - Sun, Xiaoming
PB - Springer Science and Business Media Deutschland GmbH
T2 - International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom, IJTCS-FAW 2022
Y2 - 15 August 2022 through 19 August 2022
ER -