TY - JOUR
T1 - Fair division of indivisible goods: Recent progress and open questions
AU - Amanatidis, Georgios
AU - Aziz, Haris
AU - Birmpas, Georgios
AU - Filos-Ratsikas, Aris
AU - Li, Bo
AU - Moulin, Hervé
AU - Voudouris, Alexandros A.
AU - Wu, Xiaowei
N1 - Funding Information:
This work is partially supported by the ERC Advanced Grant 788893 AMDROMA “Algorithmic and Mechanism Design Research in Online Markets”, the MIUR PRIN project ALGADIMAR “Algorithms, Games, Digital Markets”, the NWO Veni project No. VI.Veni.192.153 , NSFC No. 62102333 , HKSAR RGC No. PolyU 25211321 , PolyU Start-up No. P0034420 , FDCT (File no. 0014/2022/AFJ , 0085/2022/A , 0143/2020/A3 , SKL-IOTSC-2021-2023 ).
Publisher Copyright:
© 2023 The Author(s)
PY - 2023/9
Y1 - 2023/9
N2 - Allocating resources to individuals in a fair manner has been a topic of interest since ancient times, with most of the early mathematical work on the problem focusing on resources that are infinitely divisible. Over the last decade, there has been a surge of papers studying computational questions regarding the indivisible case, for which exact fairness notions such as envy-freeness and proportionality are hard to satisfy. One main theme in the recent research agenda is to investigate the extent to which their relaxations, like maximin share fairness (MMS) and envy-freeness up to any good (EFX), can be achieved. In this survey, we present a comprehensive review of the recent progress made in the related literature by highlighting different ways to relax fairness notions, common algorithm design techniques, and the most interesting questions for future research.
AB - Allocating resources to individuals in a fair manner has been a topic of interest since ancient times, with most of the early mathematical work on the problem focusing on resources that are infinitely divisible. Over the last decade, there has been a surge of papers studying computational questions regarding the indivisible case, for which exact fairness notions such as envy-freeness and proportionality are hard to satisfy. One main theme in the recent research agenda is to investigate the extent to which their relaxations, like maximin share fairness (MMS) and envy-freeness up to any good (EFX), can be achieved. In this survey, we present a comprehensive review of the recent progress made in the related literature by highlighting different ways to relax fairness notions, common algorithm design techniques, and the most interesting questions for future research.
KW - Discrete fair division
KW - EF1
KW - EFX
KW - Envy-freeness
KW - MMS
KW - Proportionality
UR - http://www.scopus.com/inward/record.url?scp=85162904937&partnerID=8YFLogxK
U2 - 10.1016/j.artint.2023.103965
DO - 10.1016/j.artint.2023.103965
M3 - Review article
AN - SCOPUS:85162904937
SN - 0004-3702
VL - 322
SP - 1
EP - 25
JO - Artificial Intelligence
JF - Artificial Intelligence
M1 - 103965
ER -