E-resources
-
Garg, Jugal; Taki, Setareh
Artificial intelligence, November 2021, 2021-11-00, 20211101, Volume: 300Journal Article
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–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. In this paper, we develop a new approach that gives a simple algorithm for showing the existence of a 34-MMS allocation. Furthermore, our approach is powerful enough to be easily extended in two directions: First, we get a strongly polynomial time algorithm to find a 34-MMS allocation, where we do not need to approximate the MMS values at all. Second, we show that there always exists a (34+112n)-MMS allocation, improving the best previous factor. This improves the approximation guarantee, most notably for small n. We note that 34 was the best factor known for n>4.
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
If the library membership card is not in the list,
add a new one.
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|
Source: Personal bibliographies
and: SICRIS
The material is available in full text. If you wish to order the material anyway, click the Continue button.