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 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.
翻译:自古以来,以公平的方式向个人分配资源一直是一个值得关注的议题,大部分早期数学工作都集中在不可分的资源上,过去十年来,研究关于不可分割案例的计算问题的文件激增,很难满足这种不可分割案例的准确公平概念,如无妒忌和相称性。最近研究议程中的一个主要主题是调查在多大程度上可以实现他们的放松,如最大程度的分享公平(MMS)和无妒忌至任何好处(EFX ) 。在这次调查中,我们通过强调放松公平概念的不同方式、共同的算法设计技巧以及未来研究最有趣的问题,对相关文献取得的进展进行了全面审查。