Name
Abstract | ||
|---|---|---|
Fair division is a fundamental problem in various multi-agent settings, where the goal is to divide a set of resources among agents in a fair manner. We study the case where m indivisible items need to be divided among n agents with additive valuations using the popular fairness notion of maximin share (MMS). An MMS allocation provides each agent a bundle worth at least her maximin share. While it is known that such an allocation need not exist [1], [2], a series of remarkable work [1], [3], [4], [5], [6] provided approximation algorithms for a 23-MMS allocation in which each agent receives a bundle worth at least 23 times her maximin share. More recently, Ghodsi et al. [7] showed the existence of a 34-MMS allocation and a PTAS to find a (34−ϵ)-MMS allocation for an ϵ>0. Most of the previous works utilize intricate algorithms and require agents' approximate MMS values, which are computationally expensive to obtain. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1016/j.artint.2021.103547 | Artificial Intelligence |
Keywords | DocType | Volume |
Fair division,Maximin shares,Strongly polynomial algorithm | Journal | 300 |
Issue | ISSN | Citations |
1 | 0004-3702 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jugal Garg | 1 | 3 | 3.77 |
| Setareh Taki | 2 | 1 | 1.37 |