In fair division of indivisible goods, l-out-of-d maximin share (MMS) is the value that an agent can guarantee by partitioning the goods into d bundles and choosing the l least preferred bundles. Most existing works aim to guarantee to all agents a constant fraction of their 1-out-of-n MMS. But this guarantee is sensitive to small perturbation in agents' cardinal valuations. We consider a more robust approximation notion, which depends only on the agents' ordinal rankings of bundles. We prove the existence of l-out-of-floor((l+1/2)n) MMS allocations of goods for any integer l greater than or equal to 1, and present a polynomial-time algorithm that finds a 1-out-of-ceiling(3n/2) MMS allocation when l = 1. We further develop an algorithm that provides a weaker ordinal approximation to MMS for any l > 1.
more »
« less
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
-
In fair division of indivisible goods, ℓ-out-of-d maximin share (MMS) is the value that an agent can guarantee by partitioning the goods into d bundles and choosing the ℓ least preferred bundles. Most existing works aim to guarantee to all agents a constant fraction of their 1-out-of-n MMS. But this guarantee is sensitive to small perturbation in agents' cardinal valuations. We consider a more robust approximation notion, which depends only on the agents' ordinal rankings of bundles. We prove the existence of ℓ-out-of-⌊(ℓ + 1/2)n⌋ MMS allocations of goods for any integer ℓ ≥ 1, and present a polynomial-time algorithm that finds a 1-out-of-⌈3n/2⌉ MMS allocation when ℓ=1. We further develop an algorithm that provides a weaker ordinal approximation to MMS for any ℓ > 1.more » « less
-
We study the problem of fairly allocating a set of m indivisible chores (items with non-positive value) to n agents. We consider the desirable fairness notion of 1-out-of-d maximin share (MMS)---the minimum value that an agent can guarantee by partitioning items into d bundles and receiving the least valued bundle---and focus on ordinal approximation of MMS that aims at finding the largest dłeq n for which 1-out-of-d MMS allocation exists. Our main contribution is a polynomial-time algorithm for 1-out-of-ł 2n/3 MMS allocation, and a proof of existence of 1-out-of-łfloor 3n/4 MMS allocation of chores. Furthermore, we show how to use recently-developed algorithms for bin-packing to approximate the latter bound up to a logarithmic factor in polynomial time.more » « less
-
null (Ed.)Fair division is a subfield of multiagent systems that is concerned with object distribution. When objects are indivisible, the Maximin Share Guarantee (MMS) is a desirable fairness notion; however, it is not guaranteed to exist. While MMS allocations may not always exist, a relaxation of MMS is guaranteed to exist. We show that there exists a family of instances for which this relaxation fails to guarantee the MMS value for all but a small constant number of agents.more » « less
-
null (Ed.)We initiate the study of multi-layered cake cutting with the goal of fairly allocating multiple divisible resources (layers of a cake) among a set of agents. The key requirement is that each agent can only utilize a single resource at each time interval. Several real-life applications exhibit such restrictions on overlapping pieces, for example, assigning time intervals over multiple facilities and resources or assigning shifts to medical professionals. We investigate the existence and computation of envy-free and proportional allocations. We show that envy-free allocations that are both feasible and contiguous are guaranteed to exist for up to three agents with two types of preferences, when the number of layers is two. We further devise an algorithm for computing proportional allocations for any number of agents when the number of layers is factorable to three and/or some power of two.more » « less
Full Text Available