Fair division of indivisibles: on the computability of maximin share (MMS) allocations

Taki, Setareh

Permalink

https://hdl.handle.net/2142/116235 Copy

Description

Title

Fair division of indivisibles: on the computability of maximin share (MMS) allocations

Author(s)

Taki, Setareh

Issue Date

2022-07-14

Director of Research (if dissertation) or Advisor (if thesis)

Garg, Jugal

Doctoral Committee Chair(s)

Garg, Jugal

Committee Member(s)

• Chekuri, Chandra
• Nagi, Rakesh
• Chandrasekaran, Karthekeyan
• Mehta, Ruta

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

Maximin Share, Fair Division, Algorithmic Game Theory, Approximation Algorithms

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 \emph{fair} manner. This thesis studies the case where $m$ indivisible items need to be divided among $n$ agents with additive valuations using the popular fairness notion of \emph{maximin share} (MMS). The maximin value of an agent is the largest value she can guarantee herself if she is allowed to choose a partition of the items into $n$ bundles (one for each agent), on the condition that she receives her least preferred bundle. 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~\cite{procaccia2014fair,kurokawa2016can}, a series of remarkable works~\cite{procaccia2014fair,KurokawaPW18,amanatidis2017approximation,barman2017approximation, ourpaper} provided approximation algorithms for a $\tfrac{2}{3}$-MMS allocation in which each agent receives a bundle worth at least $\tfrac{2}{3}$ times her maximin share. Later, Ghodsi et al.~\cite{ghodsi2017fair} showed the existence of a $\tf34$-MMS allocation and a PTAS to find a ($\tf34-\epsilon$)-MMS allocation for an $\epsilon > 0$. Most of the previous works utilize intricate algorithms and require agents' approximate MMS values, which are computationally expensive to obtain. The focus of this thesis is the classic setting of the MMS problem where all items are assumed to be goods (positively valued). The first result in this setting is an alternative $\tf23$-MMS allocation that offers a simple algorithm and straightforward analysis. In contrast to other algorithms, the approach allows for a simple and intuitive understanding of why it works. Using the intuition built by the simple $\tf23$-MMS algorithm, we develop a new approach that gives a simple algorithm for showing the existence of a $\tf34$-MMS allocation. Furthermore, the approach is powerful enough to be easily extended in two directions: First, we get a strongly polynomial time algorithm to find a $\tf34$-MMS allocation, where we do not need to approximate the MMS values at all. Second, we show that a $(\tf34+\tfrac{1}{12n})$-MMS allocation always exists. This considerably improves the approximation guarantee, most notably for small $n$. We note that $\tf34$ was the best factor known for $n> 4$. To this day, this is the state of the art approximation factor for the MMS problem. Besides the classic setting of MMS, this thesis also covers results on the generalization of the MMS problem. The first aspect is studying the Groupwise MMS (GMMS) problem, which is a stronger notion than MMS. An allocation is GMMS if every sub-allocation is also an MMS allocation. We show an algorithm that obtains $\tf47$-GMMS allocation after donating at most $n$ items (that were intended to be allocated). Another approach to generalize the MMS problem is to study the MMS problem as mixed manna. In mixed manna, an item can be a good for some agents and a chore (that causes disutility) for others. Specifically, a PTAS to obtain MMS value is investigated. Such PTAS is known for goods (and chores) manna and plays a substantial role in obtaining approximate MMS allocation in several works. In contrast to goods (and chores) manna, for the mixed manna, a recent result by \cite{Kulkarni2020} showed that finding even an approximate MMS value of an agent up to any approximation factor in $(0,1]$ is NP-hard for general instances. In this thesis, the hardness result is complemented by considering two restricted settings and obtaining a PTAS for each setting. The first restricted setting is when the following conditions hold: $(i)$ the number of agents is a constant, and $(ii)$ for every agent, her absolute value for all items is at least a constant factor of her total (absolute) value for all goods {\em or} all chores. The second restricted setting is when the absolute value of MMS is at least $1/\rho$ times either the total value of all goods or the total cost of all chores, for some constant $\rho \ge 1$.

Graduation Semester

2022-08

Type of Resource

Thesis

Copyright and License Information

Copyright 2022 Setareh Taki

Owning Collections