Approximation Algorithms for Computing Maximin Share Allocations

Authors

Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, Amin Saberi

Type: Article

Publication Date: 2017-10-31

Citations: 100

DOI: https://doi.org/10.1145/3147173

View Ask PDF

Abstract

We study the problem of computing maximin share guarantees, a recently introduced fairness notion. Given a set of $n$ agents and a set of goods, the maximin share of a single agent is the best that she can guarantee to herself, if she would be allowed to partition the goods in any way she prefers, into $n$ bundles, and then receive her least desirable bundle. The objective then in our problem is to find a partition, so that each agent is guaranteed her maximin share. In settings with indivisible goods, such allocations are not guaranteed to exist, so we resort to approximation algorithms. Our main result is a $2/3$-approximation, that runs in polynomial time for any number of agents. This improves upon the algorithm of Procaccia and Wang, which also produces a $2/3$-approximation but runs in polynomial time only for a constant number of agents. To achieve this, we redesign certain parts of their algorithm. Furthermore, motivated by the apparent difficulty, both theoretically and experimentally, in finding lower bounds on the existence of approximate solutions, we undertake a probabilistic analysis. We prove that in randomly generated instances, with high probability there exists a maximin share allocation. This can be seen as a justification of the experimental evidence reported in relevant works. Finally, we provide further positive results for two special cases that arise from previous works. The first one is the intriguing case of $3$ agents, for which it is already known that exact maximin share allocations do not always exist (contrary to the case of $2$ agents). We provide a $7/8$-approximation algorithm, improving the previously known result of $3/4$. The second case is when all item values belong to $\{0, 1, 2\}$, extending the $\{0, 1\}$ setting studied in Bouveret and Lema\^itre. We obtain an exact algorithm for any number of agents in this case.

Locations

ACM Transactions on Algorithms
View
arXiv (Cornell University)
View PDF
Open Access at Essex (University of Essex)
View PDF
DataCite API
View

Ask a Question About This Paper

Summary

Guaranteeing Maximin Shares: Some Agents Left Behind

2021-05-19

Hadi Hosseini , Andrew Searns

The maximin share (MMS) guarantee is a desirable fairness notion for allocating indivisible goods. While MMS allocations do not always exist, several approximation techniques have been developed to ensure that … The maximin share (MMS) guarantee is a desirable fairness notion for allocating indivisible goods. While MMS allocations do not always exist, several approximation techniques have been developed to ensure that all agents receive a fraction of their maximin share. We focus on an alternative approximation notion, based on the population of agents, that seeks to guarantee MMS for a fraction of agents. We show that no optimal approximation algorithm can satisfy more than a constant number of agents, and discuss the existence and computation of MMS for all but one agent and its relation to approximate MMS guarantees. We then prove the existence of allocations that guarantee MMS for $\frac{2}{3}$ of agents, and devise a polynomial time algorithm that achieves this bound for up to nine agents. A key implication of our result is the existence of allocations that guarantee $\text{MMS}^{\lceil{3n/2}\rceil}$, i.e., the value that agents receive by partitioning the goods into $\lceil{\frac{3}{2}n}\rceil$ bundles, improving the best known guarantee of $\text{MMS}^{2n-2}$. Finally, we provide empirical experiments using synthetic data.

Guaranteeing Maximin Shares: Some Agents Left Behind

2021-01-01

Seyed Hossein Hosseini , Andrew Searns

View PDF Chat

Guaranteeing Maximin Shares: Some Agents Left Behind

2021-08-01

Hadi Hosseini , Andrew Searns

The maximin share (MMS) guarantee is a desirable fairness notion for allocating indivisible goods. While MMS allocations do not always exist, several approximation techniques have been developed to ensure that … The maximin share (MMS) guarantee is a desirable fairness notion for allocating indivisible goods. While MMS allocations do not always exist, several approximation techniques have been developed to ensure that all agents receive a fraction of their maximin share. We focus on an alternative approximation notion, based on the population of agents, that seeks to guarantee MMS for a fraction of agents. We show that no optimal approximation algorithm can satisfy more than a constant number of agents, and discuss the existence and computation of MMS for all but one agent and its relation to approximate MMS guarantees. We then prove the existence of allocations that guarantee MMS for 2/3 of agents, and devise a polynomial time algorithm that achieves this bound for up to nine agents. A key implication of our result is the existence of allocations that guarantee the value that an agent receives by partitioning the goods into 3n/2 bundles, improving the best known guarantee when goods are partitioned into 2n-2 bundles. Finally, we provide empirical experiments using synthetic data.

View PDF Chat

An Improved Approximation Algorithm for Maximin Shares

2019-01-01

Jugal Garg , Setareh Taki

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 … 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, a series of work provided approximation algorithms for a 2/3-MMS allocation in which each agent receives a bundle worth at least 2/3 times her maximin share. More recently, Ghodsi et al. [EC'2018] showed the existence of a 3/4-MMS allocation and a PTAS to find a (3/4-\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. In this paper, we develop a new approach that gives a simple algorithm for showing the existence of a 3/4-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 3/4-MMS allocation, where we do not need to approximate the MMS values at all. Second, we show that there always exists a (3/4 + 1/(12n))-MMS allocation, improving the best previous factor. This improves the approximation guarantee, most notably for small n. We note that 3/4 was the best factor known for n> 4.

An Improved Approximation Algorithm for Maximin Shares

2020-07-09

Jugal Garg , Setareh Taki

We study the problem of fair allocation of m indivisible items among n agents with additive valuations using the popular notion of maximin share (MMS) as our measure of fairness. … We study the problem of fair allocation of m indivisible items among n agents with additive valuations using the popular notion of maximin share (MMS) as our measure of fairness. 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 [5, 7], a series of remarkable work [1-3, 6, 7] provided 2/3 approximation algorithms in which each agent receives a bundle worth at least 2/3 times her maximin share. More recently, [4] showed the existence of 3/4 MMS allocations and a PTAS to find a 3/4 - ε MMS allocation. Most of the previous works utilize intricate algorithms and require agents' approximate MMS values, which are computationally expensive to obtain.

View PDF Chat

Approximation Algorithms for Maximin Fair Division

2017-06-20

Siddharth Barman , Sanath Kumar Krishna Murthy

We consider the problem of dividing indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin … We consider the problem of dividing indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin share, that is defined to be the maximum value that an agent can ensure for herself, if she were to partition the goods into n bundles, and then receive a minimum valued bundle. Since maximin fair allocations (i.e., allocations in which each agent gets at least her maximin share) do not always exist, prior work has focussed on approximation results that aim to find allocations in which the value of the bundle allocated to each agent is (multiplicatively) as close to her maximin share as possible. In particular, Procaccia and Wang (2014) along with Amanatidis et al. (2015) have shown that under additive valuations a 2/3-approximate maximin fair allocation always exists and can be found in polynomial time. We complement these results by developing a simple and efficient algorithm that achieves the same approximation guarantee.

View PDF Chat

Ordinal Maximin Share Approximation for Goods

2022-05-26

Hadi Hosseini , Andrew Searns , Erel Segal-Halevi

In fair division of indivisible goods, $\ell$-out-of-$d$ maximin share (MMS) is the value that an agent can guarantee by partitioning the goods into $d$ bundles and choosing the $\ell$ least … In fair division of indivisible goods, $\ell$-out-of-$d$ maximin share (MMS) is the value that an agent can guarantee by partitioning the goods into $d$ bundles and choosing the $\ell$ 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' \emph{ordinal} rankings of bundles. We prove the existence of $\ell$-out-of-$\lfloor(\ell+\frac{1}{2})n\rfloor$ MMS allocations of goods for any integer $\ell\geq 1$, and present a polynomial-time algorithm that finds a $1$-out-of-$\lceil\frac{3n}{2}\rceil$ MMS allocation when $\ell = 1$. We further develop an algorithm that provides a weaker ordinal approximation to MMS for any $\ell > 1$.

View PDF Chat

On Truthful Mechanisms for Maximin Share Allocations

2016-01-01

Georgios Amanatidis , Georgios Birmpas , Evangelos Markakis

We study a fair division problem with indivisible items, namely the computation of maximin share allocations. Given a set of $n$ players, the maximin share of a single player is … We study a fair division problem with indivisible items, namely the computation of maximin share allocations. Given a set of $n$ players, the maximin share of a single player is the best she can guarantee to herself, if she would partition the items in any way she prefers, into $n$ bundles, and then receive her least desirable bundle. The objective then is to find an allocation, so that each player is guaranteed her maximin share. Previous works have studied this problem mostly algorithmically, providing constant factor approximation algorithms. In this work we embark on a mechanism design approach and investigate the existence of truthful mechanisms. We propose three models regarding the information that the mechanism attempts to elicit from the players, based on the cardinal and ordinal representation of preferences. We establish positive and negative (impossibility) results for each model and highlight the limitations imposed by truthfulness on the approximability of the problem. Finally, we pay particular attention to the case of two players, which already leads to challenging questions.

Approximate and Strategyproof Maximin Share Allocation of Chores with Ordinal Preferences

2020-01-01

Haris Aziz , Bo Li , Xiaowei Wu

We initiate the work on maximin share (MMS) fair allocation of m indivisible chores to n agents using only their ordinal preferences, from both algorithmic and mechanism design perspectives. The … We initiate the work on maximin share (MMS) fair allocation of m indivisible chores to n agents using only their ordinal preferences, from both algorithmic and mechanism design perspectives. The previous best-known approximation is 2-1/n by Aziz et al. [IJCAI 2017]. We improve this result by giving a simple deterministic 5/3-approximation algorithm that determines an allocation sequence of agents, according to which items are allocated one by one. By a tighter analysis, we show that for n=2,3, our algorithm achieves better approximation ratios, and is actually optimal. We also consider the setting with strategic agents, where agents may misreport their preferences to manipulate the outcome. We first provide a O(\log (m/n))-approximation consecutive picking algorithm, and then improve the approximation ratio to O(\sqrt{\log n}) by a randomized algorithm. Our results uncover some interesting contrasts between the approximation ratios achieved for chores versus goods.

View PDF Chat

An Algorithmic Framework for Approximating Maximin Share Allocation of Chores

2021-07-18

Xin Huang , Pinyan Lu

We consider the problem of fairly dividing m indivisible chores among n agents. The fairness measure we consider here is the maximin share. The previous best known result is that … We consider the problem of fairly dividing m indivisible chores among n agents. The fairness measure we consider here is the maximin share. The previous best known result is that there always exists a 4/3-approximation maximin share allocation[3]. With our algorithm, we can always find a 11/9-approximation maximin share allocation for any instance. We also discuss how to improve the efficiency of the algorithm and its connection to the job scheduling problem. The full paper can be found at https://arxiv.org/abs/1907.04505.

View PDF Chat

Breaking the $3/4$ Barrier for Approximate Maximin Share

2023-01-01

Hannaneh Akrami , Jugal Garg

We study the fundamental problem of fairly allocating a set of indivisible goods among $n$ agents with additive valuations using the desirable fairness notion of maximin share (MMS). MMS is … We study the fundamental problem of fairly allocating a set of indivisible goods among $n$ agents with additive valuations using the desirable fairness notion of maximin share (MMS). MMS is the most popular share-based notion, in which an agent finds an allocation fair to her if she receives goods worth at least her MMS value. An allocation is called MMS if all agents receive at least their MMS value. Since MMS allocations need not exist when $n>2$, a series of works showed the existence of approximate MMS allocations with the current best factor of $\frac34 + O(\frac{1}{n})$. However, a simple example in [DFL82, BEF21, AGST23] showed the limitations of existing approaches and proved that they cannot improve this factor to $3/4 + \Omega(1)$. In this paper, we bypass these barriers to show the existence of $(\frac{3}{4} + \frac{3}{3836})$-MMS allocations by developing new reduction rules and analysis techniques.

Breaking the 3/4 Barrier for Approximate Maximin Share

2024-01-01

Hannaneh Akrami , Jugal Garg

We study the fundamental problem of fairly allocating a set of indivisible goods among n agents with additive valuations using the desirable fairness notion of maximin share (MMS). MMS is … We study the fundamental problem of fairly allocating a set of indivisible goods among n agents with additive valuations using the desirable fairness notion of maximin share (MMS). MMS is the most popular share-based notion, in which an agent finds an allocation fair to her if she receives goods worth at least her MMS value. An allocation is called MMS if all agents receive at least their MMS value. However, since MMS allocations need not exist when n > 2, a series of works showed the existence of approximate MMS allocations with the current best factor of . The recent work [3] showed the limitations of existing approaches and proved that they cannot improve this factor to 3/4 + Ω(1). In this paper, we bypass these barriers to show the existence of ()-MMS allocations by developing new reduction rules and analysis techniques.

View PDF Chat

Improving Approximation Guarantees for Maximin Share

2023-01-01

Hannaneh Akrami , Jugal Garg , Setareh Taki

We consider fair division of a set of indivisible goods among $n$ agents with additive valuations using the fairness notion of maximin share (MMS). MMS is the most popular share-based … We consider fair division of a set of indivisible goods among $n$ agents with additive valuations using the fairness notion of maximin share (MMS). MMS is the most popular share-based notion, in which an agent finds an allocation fair to her if she receives goods worth at least her ($1$-out-of-$n$) MMS value. An allocation is called MMS if all agents receive their MMS values. However, since MMS allocations do not always exist, the focus shifted to investigating its ordinal and multiplicative approximations. In the ordinal approximation, the goal is to show the existence of $1$-out-of-$d$ MMS allocations (for the smallest possible $d>n$). A series of works led to the state-of-the-art factor of $d=\lfloor3n/2\rfloor$ [Hosseini et al.'21]. We show that $1$-out-of-$4\lceil n/3\rceil$ MMS allocations always exist, thereby improving the state-of-the-art of ordinal approximation. In the multiplicative approximation, the goal is to show the existence of $\alpha$-MMS allocations (for the largest possible $\alpha < 1$), which guarantees each agent at least $\alpha$ times her MMS value. We introduce a general framework of "approximate MMS with agent priority ranking". An allocation is said to be $T$-MMS, for a non-increasing sequence $T = (\tau_1, \ldots, \tau_n)$ of numbers, if the agent at rank $i$ in the order gets a bundle of value at least $\tau_i$ times her MMS value. This framework captures both ordinal approximation and multiplicative approximation as special cases. We show the existence of $T$-MMS allocations where $\tau_i \ge \max(\frac{3}{4} + \frac{1}{12n}, \frac{2n}{2n+i-1})$ for all $i$. Furthermore, we can get allocations that are $(\frac{3}{4} + \frac{1}{12n})$-MMS ex-post and $(0.8253 + \frac{1}{36n})$-MMS ex-ante. We also prove that our algorithm does not give better than $(0.8631 + \frac{1}{2n})$-MMS ex-ante.

View PDF Chat

Ordinal Maximin Share Approximation for Chores

2022-01-01

Seyed Hossein Hosseini , Andrew Searns , Erel Segal-Halevi

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 … 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 <= n for which 1-out-of-d MMS allocation exists. Our main contribution is a polynomial-time algorithm for 1-out-of-floor(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.

View PDF Chat

Maximin Shares Under Cardinality Constraints

2021-01-01

Halvard Hummel , Magnus Lie Hetland

We study the problem of fair allocation of a set of indivisible items among agents with additive valuations, under cardinality constraints. In this setting, the items are partitioned into categories, … We study the problem of fair allocation of a set of indivisible items among agents with additive valuations, under cardinality constraints. In this setting, the items are partitioned into categories, each with its own limit on the number of items it may contribute to any bundle. We consider the fairness measure known as the maximin share (MMS) guarantee, and propose a novel polynomial-time algorithm for finding $1/2$-approximate MMS allocations for goods -- an improvement from the previously best available guarantee of $11/30$. For single-category instances, we show that a modified variant of our algorithm is guaranteed to produce $2/3$-approximate MMS allocations. Among various other existence and non-existence results, we show that a $(\sqrt{n}/(2\sqrt{n} - 1))$-approximate MMS allocation always exists for goods. For chores, we show similar results as for goods, with a $2$-approximate algorithm in the general case and a $3/2$-approximate algorithm for single-category instances. We extend the notions and algorithms related to ordered and reduced instances to work with cardinality constraints, and combine these with bag filling style procedures to construct our algorithms.

Approximation Algorithms for Maximin Fair Division

2020-02-29

Siddharth Barman , Sanath Kumar Krishnamurthy

We consider the problem of allocating indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin … We consider the problem of allocating indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin share , which is defined to be the maximum value that an agent can ensure for herself, if she were to partition the goods into n bundles, and then receive a minimum valued bundle. Since maximin fair allocations (i.e., allocations in which each agent gets at least her maximin share) do not always exist, prior work has focused on approximation results that aim to find allocations in which the value of the bundle allocated to each agent is (multiplicatively) as close to her maximin share as possible. In particular, Procaccia and Wang (2014) along with Amanatidis et al. (2015) have shown that under additive valuations, a 2/3-approximate maximin fair allocation always exists and can be found in polynomial time. We complement these results by developing a simple and efficient algorithm that achieves the same approximation guarantee. Furthermore, we initiate the study of approximate maximin fair division under submodular valuations . Specifically, we show that when the valuations of the agents are nonnegative , monotone , and submodular, then a 0.21-approximate maximin fair allocation is guaranteed to exist. In fact, we show that such an allocation can be efficiently found by using a simple round-robin algorithm. A technical contribution of the article is to analyze the performance of this combinatorial algorithm by employing the concept of multilinear extensions .

View PDF Chat

Approximation Algorithms for Maximin Fair Division

2017-01-01

Siddharth Barman , Sanath Kumar Krishnamurthy

We consider the problem of allocating indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin … We consider the problem of allocating indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin share, that is defined to be the maximum value that an agent can ensure for herself, if she were to partition the goods into n bundles, and then receive a minimum valued bundle. Since maximin fair allocations (i.e., allocations in which each agent gets at least her maximin share) do not always exist, prior work has focused on approximation results that aim to find allocations in which the value of the bundle allocated to each agent is (multiplicatively) as close to her maximin share as possible. In particular, Procaccia and Wang (2014) along with Amanatidis et al. (2015) have shown that under additive valuations a 2/3-approximate maximin fair allocation always exists and can be found in polynomial time. We complement these results by developing a simple and efficient algorithm that achieves the same approximation guarantee. Furthermore, we initiate the study of approximate maximin fair division under submodular valuations. Specifically, we show that when the valuations of the agents are nonnegative, monotone, and submodular, then a 0.21-approximate maximin fair allocation is guaranteed to exist. In fact, we show that such an allocation can be efficiently found by using a simple round-robin algorithm. A technical contribution of the paper is to analyze the performance of this combinatorial algorithm by employing the concept of multilinear extensions.

View PDF Chat

On Lower Bounds for Maximin Share Guarantees

2023-01-01

Halvard Hummel

We study the problem of fairly allocating a set of indivisible items to a set of agents with additive valuations. Recently, Feige et al. (WINE'21) proved that a maximin share … We study the problem of fairly allocating a set of indivisible items to a set of agents with additive valuations. Recently, Feige et al. (WINE'21) proved that a maximin share (MMS) allocation exists for all instances with $n$ agents and no more than $n + 5$ items. Moreover, they proved that an MMS allocation is not guaranteed to exist for instances with $3$ agents and at least $9$ items, or $n \ge 4$ agents and at least $3n + 3$ items. In this work, we shrink the gap between these upper and lower bounds for guaranteed existence of MMS allocations. We prove that for any integer $c > 0$, there exists a number of agents $n_c$ such that an MMS allocation exists for any instance with $n \ge n_c$ agents and at most $n + c$ items, where $n_c \le \lfloor 0.6597^c \cdot c!\rfloor$ for allocation of goods and $n_c \le \lfloor 0.7838^c \cdot c!\rfloor$ for chores. Furthermore, we show that for $n \neq 3$ agents, all instances with $n + 6$ goods have an MMS allocation.

View PDF Chat

Groupwise Maximin Fair Allocation of Indivisible Goods

2018-04-25

Siddharth Barman , Arpita Biswas , Sanath Kumar Krishnamurthy +1 more

We study the problem of allocating indivisible goods among n agents in a fair manner. For this problem, maximin share (MMS) is a well-studied solution concept which provides a fairness … We study the problem of allocating indivisible goods among n agents in a fair manner. For this problem, maximin share (MMS) is a well-studied solution concept which provides a fairness threshold. Specifically, maximin share is defined as the minimum utility that an agent can guarantee for herself when asked to partition the set of goods into n bundles such that the remaining (n-1) agents pick their bundles adversarially. An allocation is deemed to be fair if every agent gets a bundle whose valuation is at least her maximin share. Even though maximin shares provide a natural benchmark for fairness, it has its own drawbacks and, in particular, it is not sufficient to rule out unsatisfactory allocations. Motivated by these considerations, in this work we define a stronger notion of fairness, called groupwise maximin share guarantee (GMMS). In GMMS, we require that the maximin share guarantee is achieved not just with respect to the grand bundle, but also among all the subgroups of agents. Hence, this solution concept strengthens MMS and provides an ex-post fairness guarantee. We show that in specific settings, GMMS allocations always exist. We also establish the existence of approximate GMMS allocations under additive valuations, and develop a polynomial-time algorithm to find such allocations. Moreover, we establish a scale of fairness wherein we show that GMMS implies approximate envy freeness. Finally, we empirically demonstrate the existence of GMMS allocations in a large set of randomly generated instances. For the same set of instances, we additionally show that our algorithm achieves an approximation factor better than the established, worst-case bound.

View PDF Chat

Groupwise Maximin Fair Allocation of Indivisible Goods

2017-01-01

Siddharth Barman , Arpita Biswas , Sanath Kumar Krishnamurthy +1 more

View PDF Chat

Maximum Nash welfare and other stories about EFX

2021-02-09

Georgios Amanatidis , Georgios Birmpas , Aris Filos-Ratsikas +2 more

View PDF Chat

Almost envy-free allocations with connected bundles

2021-11-30

Vittorio Bilò , Ioannis Caragiannis , Michele Flammini +5 more

View PDF Chat

Fairly Allocating Many Goods with Few Queries

2021-01-01

Hoon Oh , Ariel D. Procaccia , Warut Suksompong

Related DatabasesWeb of Science You must be logged in with an active subscription to view this.Article DataHistorySubmitted: 16 January 2020Accepted: 10 January 2021Published online: 15 April 2021Keywordsenvy-freeness, fair division, algorithms, … Related DatabasesWeb of Science You must be logged in with an active subscription to view this.Article DataHistorySubmitted: 16 January 2020Accepted: 10 January 2021Published online: 15 April 2021Keywordsenvy-freeness, fair division, algorithms, query complexityAMS Subject Headings68Q25, 91B32Publication DataISSN (print): 0895-4801ISSN (online): 1095-7146Publisher: Society for Industrial and Applied MathematicsCODEN: sjdmec

View PDF Chat

Computing a small agreeable set of indivisible items

2018-12-18

Pasin Manurangsi , Warut Suksompong

View PDF Chat

Envy-free matchings in bipartite graphs and their applications to fair division

2021-11-27

Elad Aigner‐Horev , Erel Segal-Halevi

View PDF Chat

On Best-of-Both-Worlds Fair-Share Allocations

2022-01-01

Moshe Babaioff , Tomer Ezra , Uriel Feige

View PDF Chat

Existence of EFX for two additive valuations

2023-07-20

Ryoga Mahara

View PDF Chat

Efficient Fair Division with Minimal Sharing

2022-05-01

Fedor Sandomirskiy , Erel Segal-Halevi

When assets are to be divided among several partners, for example, a partnership split, fair division theory can be used to determine a fair allocation. The applicability of existing approaches … When assets are to be divided among several partners, for example, a partnership split, fair division theory can be used to determine a fair allocation. The applicability of existing approaches is limited as they either treat assets as divisible resources that end up being shared among participants or deal with indivisible objects providing only approximate fairness. In practice, sharing is often possible but undesirable, and approximate fairness is not adequate, particularly for highly valuable assets. In “Efficient Fair Division with Minimal Sharing,” Sandomirskiy and Segal-Halevi introduce a novel approach offering a middle ground: the number of shared objects is minimized while maintaining exact fairness and economic efficiency. This minimization can be conducted in polynomial time for generic instances if the number of agents or objects is fixed. Experiments on real data demonstrate a substantial improvement over current methods.

View PDF Chat

Approximate and strategyproof maximin share allocation of chores with ordinal preferences

2022-07-05

Haris Aziz , Bo Li , Xiaowei Wu

View PDF Chat

Ordinal Maximin Share Approximation for Goods

2022-05-26

Hadi Hosseini , Andrew Searns , Erel Segal-Halevi

View PDF Chat

Fair Allocation of Indivisible Goods: Improvement and Generalization

2017-01-01

Mohammad Ghodsi , Mohammad Taghi Hajiaghayi , Masoud Seddighin +2 more

We study the problem of fair allocation for indivisible goods. We use the the maxmin share paradigm introduced by Budish as a measure for fairness. Procaccia and Wang (EC'14) were … We study the problem of fair allocation for indivisible goods. We use the the maxmin share paradigm introduced by Budish as a measure for fairness. Procaccia and Wang (EC'14) were first to investigate this fundamental problem in the additive setting. In contrast to what real-world experiments suggest, they show that a maxmin guarantee (1-MMS allocation) is not always possible even when the number of agents is limited to 3. While the existence of an approximation solution (e.g. a $1/2$-MMS allocation) is quite straightforward, improving the guarantee becomes subtler for larger constants. Procaccia provide a proof for existence of a $2/3$-MMS allocation and leave the question open for better guarantees. Our main contribution is an answer to the above question. We improve the result of [Procaccia and Wang] to a $3/4$ factor in the additive setting. The main idea for our $3/4$-MMS allocation method is clustering the agents. To this end, we introduce three notions and techniques, namely reducibility, matching allocation, and cycle-envy-freeness, and prove the approximation guarantee of our algorithm via non-trivial applications of these techniques. Our analysis involves coloring and double counting arguments that might be of independent interest. One major shortcoming of the current studies on fair allocation is the additivity assumption on the valuations. We alleviate this by extending our results to the case of submodular, fractionally subadditive, and subadditive settings. More precisely, we give constant approximation guarantees for submodular and XOS agents, and a logarithmic approximation for the case of subadditive agents. Furthermore, we complement our results by providing close upper bounds for each class of valuation functions. Finally, we present algorithms to find such allocations for additive, submodular, and XOS settings in polynomial time.

Comparing Approximate Relaxations of Envy-Freeness

2018-06-08

Georgios Amanatidis , Georgios Birmpas , Evangelos Markakis

In fair division problems with indivisible goods it is well known that one cannot have any guarantees for the classic fairness notions of envy-freeness and proportionality. As a result, several … In fair division problems with indivisible goods it is well known that one cannot have any guarantees for the classic fairness notions of envy-freeness and proportionality. As a result, several relaxations have been introduced, most of which in quite recent works. We focus on four such notions, namely envy-freeness up to one good (EF1), envy-freeness up to any good (EFX), maximin share fairness (MMS), and pairwise maximin share fairness (PMMS). Since obtaining these relaxations also turns out to be problematic in several scenarios, approximate versions of them have been considered. In this work, we investigate further the connections between the four notions mentioned above and their approximate versions. We establish several tight, or almost tight, results concerning the approximation quality that any of these notions guarantees for the others, providing an almost complete picture of this landscape. Some of our findings reveal interesting and surprising consequences regarding the power of these notions, e.g., PMMS and EFX provide the same worst-case guarantee for MMS, despite PMMS being a strictly stronger notion than EFX. We believe such implications provide further insight on the quality of approximately fair solutions.

Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination

2020-07-16

Georgios Amanatidis , Evangelos Markakis , Apostolos Ntokos

View PDF Chat

Fair division of mixed divisible and indivisible goods

2021-01-05

Xiaohui Bei , Zihao Li , Jinyan Liu +2 more

View PDF Chat

Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness

2022-01-01

Georgios Amanatidis , Georgios Birmpas , Federico Fusco +3 more

View PDF Chat

Fair-Share Allocations for Agents with Arbitrary Entitlements

2023-10-26

Moshe Babaioff , Tomer Ezra , Uriel Feige

We consider the problem of fair allocation of indivisible goods to n agents with no transfers. When agents have equal entitlements, the well-established notion of the maximin share (MMS) serves … We consider the problem of fair allocation of indivisible goods to n agents with no transfers. When agents have equal entitlements, the well-established notion of the maximin share (MMS) serves as an attractive fairness criterion for which, to qualify as fair, an allocation needs to give every agent at least a substantial fraction of the agent’s MMS. In this paper, we consider the case of arbitrary (unequal) entitlements. We explain shortcomings in previous attempts that extend the MMS to unequal entitlements. Our conceptual contribution is the introduction of a new notion of a share, the AnyPrice share (APS), that is appropriate for settings with arbitrary entitlements. Even for the equal entitlements case, this notion is new and satisfies [Formula: see text], for which the inequality is sometimes strict. We present two equivalent definitions for the APS (one as a minimization problem, the other as a maximization problem) and provide comparisons between the APS and previous notions of fairness. Our main result concerns additive valuations and arbitrary entitlements, for which we provide a polynomial-time algorithm that gives every agent at least a [Formula: see text] - fraction of the agent’s APS. This algorithm can also be viewed as providing strategies in a certain natural bidding game, and these strategies secure each agent at least a [Formula: see text] - fraction of the agent’s APS. Funding: T. Ezra’s research is partially supported by the European Research Council Advanced [Grant 788893] AMDROMA “Algorithmic and Mechanism Design Research in Online Markets” and MIUR PRIN project ALGADIMAR “Algorithms, Games, and Digital Markets.” U. Feige’s research is supported in part by the Israel Science Foundation [Grant 1122/22].

View PDF Chat

Envy-freeness in house allocation problems

2019-07-30

Jiarui Gan , Warut Suksompong , Alexandros A. Voudouris

View PDF Chat

The Fair Division of Hereditary Set Systems

2018-01-01

Z. Li , Adrian Vetta

View PDF Chat

Maximin Shares Under Cardinality Constraints

2022-01-01

Halvard Hummel , Magnus Lie Hetland

View PDF Chat

Round-Robin Beyond Additive Agents: Existence and Fairness of Approximate Equilibria

2023-07-07

Georgios Amanatidis , Georgios Birmpas , Philip Lazos +2 more

Fair allocation of indivisible goods has attracted extensive attention over the last two decades, yielding numerous elegant algorithmic results and producing challenging open questions. The problem becomes much harder in … Fair allocation of indivisible goods has attracted extensive attention over the last two decades, yielding numerous elegant algorithmic results and producing challenging open questions. The problem becomes much harder in the presence of strategic agents. Ideally, one would want to design truthful mechanisms that produce allocations with fairness guarantees. However, in the standard setting without monetary transfers, it is generally impossible to have truthful mechanisms that provide non-trivial fairness guarantees. Recently, Amanatidis et al. [2021] suggested the study of mechanisms that produce fair allocations in their equilibria. Specifically, when the agents have additive valuation functions, the simple Round-Robin algorithm always has pure Nash equilibria and the corresponding allocations are envy-free up to one good (EF1) with respect to the agents' true valuation functions. Following this agenda, we show that this outstanding property of the Round-Robin mechanism extends much beyond the above default assumption of additivity. In particular, we prove that for agents with cancelable valuation functions (a natural class that contains, e.g., additive and budget-additive functions), this simple mechanism always has equilibria and even its approximate equilibria correspond to approximately EF1 allocations with respect to the agents' true valuation functions. Further, we show that the approximate EF1 fairness of approximate equilibria surprisingly holds for the important class of submodular valuation functions as well, even though exact equilibria fail to exist!

View PDF Chat

Fair Shares: Feasibility, Domination, and Incentives

2024-07-30

Moshe Babaioff , Uriel Feige

We consider fair allocation of indivisible goods to n equally entitled agents. Every agent i has a valuation function v i from some given class of valuation functions. A share … We consider fair allocation of indivisible goods to n equally entitled agents. Every agent i has a valuation function v i from some given class of valuation functions. A share s is a function that maps [Formula: see text] to a nonnegative value. A share is feasible if for every allocation instance, there is an allocation that gives every agent i a bundle that is acceptable with respect to v i , one of value at least her share value [Formula: see text]. We introduce the following concepts. A share is self-maximizing if reporting the true valuation maximizes the minimum true value of a bundle that is acceptable with respect to the report. A share s ρ-dominates another share [Formula: see text] if [Formula: see text] for every valuation function. We initiate a systematic study of feasible and self-maximizing shares and a systematic study of ρ-domination relation between shares, presenting both positive and negative results. Funding: The research of M. Babaioff is supported in part by a Golda Meir Fellowship. The research of U. Feige is supported in part by the Israel Science Foundation [Grant 1122/22].

View PDF Chat

The Maximin Share Dominance Relation

2019-01-01

Erel Segal-Halevi

Given a finite set $X$ and an ordering $\succeq$ over its subsets, the $l$-out-of-$d$ maximin-share of $X$ is the maximal (by $\succeq$) subset of $X$ that can be constructed by … Given a finite set $X$ and an ordering $\succeq$ over its subsets, the $l$-out-of-$d$ maximin-share of $X$ is the maximal (by $\succeq$) subset of $X$ that can be constructed by partitioning $X$ into $d$ parts and picking the worst union of $l$ parts. A pair of integers $(l,d)$ dominates a pair $(l',d')$ if, for any set $X$ and ordering $\succeq$, the $l$-out-of-$d$ maximin-share of $X$ is at least as good (by $\succeq$) as the $l'$-out-of-$d'$ maximin-share of $X$. This note presents a necessary and sufficient condition for deciding whether a given pair of integers dominates another pair, and an algorithm for finding all non-dominated pairs. It compares the $l$-out-of-$d$ maximin-share to some other criteria for fair allocation of indivisible objects among people with different entitlements.

Fair allocation of combinations of indivisible goods and chores

2018-01-01

Haris Aziz , Ioannis Caragiannis , Ayumi Igarashi

We consider the problem of fairly dividing a set of items. Much of the fair division literature assumes that the items are `goods' i.e., they yield positive utility for the … We consider the problem of fairly dividing a set of items. Much of the fair division literature assumes that the items are `goods' i.e., they yield positive utility for the agents. There is also some work where the items are `chores' that yield negative utility for the agents. In this paper, we consider a more general scenario where an agent may have negative or positive utility for each item. This framework captures, e.g., fair task assignment, where agents can have both positive and negative utilities for each task. We show that whereas some of the positive axiomatic and computational results extend to this more general setting, others do not. We present several new and efficient algorithms for finding fair allocations in this general setting. We also point out several gaps in the literature regarding the existence of allocations satisfying certain fairness and efficiency properties and further study the complexity of computing such allocations.

Fairness Criteria for Allocating Indivisible Chores: Connections and Efficiencies

2021-01-01

Ankang Sun , Bo Chen , Xuan Vinh Doan

We study several fairness notions in allocating indivisible chores (i.e., items with non-positive values) to agents who have additive and submodular cost functions. The fairness criteria we are concern with … We study several fairness notions in allocating indivisible chores (i.e., items with non-positive values) to agents who have additive and submodular cost functions. The fairness criteria we are concern with are envy-free up to any item (EFX), envy-free up to one item (EF1), maximin share (MMS), and pairwise maximin share (PMMS), which are proposed as relaxations of envy-freeness in the setting of additive cost functions. For allocations under each fairness criterion, we establish their approximation guarantee for other fairness criteria. Under the additive setting, our results show strong connections between these fairness criteria and, at the same time, reveal intrinsic differences between goods allocation and chores allocation. However, such strong relationships cannot be inherited by the submodular setting, under which PMMS and MMS are no longer relaxations of envy-freeness and, even worse, few non-trivial guarantees exist. We also investigate efficiency loss under these fairness constraints and establish their prices of fairness.

View PDF Chat

Achieving Proportionality up to the Maximin Item with Indivisible Goods

2021-05-18

Artem Baklanov , Pranav Garimidi , Vasilis Gkatzelis +1 more

We study the problem of fairly allocating indivisible goods and focus on the classic fairness notion of proportionality. The indivisibility of the goods is long known to pose highly non-trivial … We study the problem of fairly allocating indivisible goods and focus on the classic fairness notion of proportionality. The indivisibility of the goods is long known to pose highly non-trivial obstacles to achieving fairness, and a very vibrant line of research has aimed to circumvent them using appropriate notions of approximate fairness. Recent work has established that even approximate versions of proportionality (PROPx) may be impossible to achieve even for small instances, while the best known achievable approximations (PROP1) are much weaker. We introduce the notion of proportionality up to the maximin item (PROPm) and show how to reach an allocation satisfying this notion for any instance involving up to five agents with additive valuations. PROPm provides a well-motivated middle-ground between PROP1 and PROPx, while also capturing some elements of the well-studied maximin share (MMS) benchmark: another relaxation of proportionality that has attracted a lot of attention.

View PDF Chat

Fair allocation of conflicting items

2021-12-23

Halvard Hummel , Magnus Lie Hetland

Abstract We study fair allocation of indivisible items, where the items are furnished with a set of conflicts , and agents are not permitted to receive conflicting items. This kind … Abstract We study fair allocation of indivisible items, where the items are furnished with a set of conflicts , and agents are not permitted to receive conflicting items. This kind of constraint captures, for example, participating in events that overlap in time, or taking on roles in the presence of conflicting interests. We demonstrate, both theoretically and experimentally, that fairness characterizations such as EF1, MMS and MNW still are applicable and useful under item conflicts. Among other existence, non-existence and computability results, we show that a $$1/\Delta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mi>Δ</mml:mi></mml:mrow></mml:math> -approximate MMS allocation for n agents may be found in polynomial time when $$n>\Delta >2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>n</mml:mi><mml:mo>></mml:mo><mml:mi>Δ</mml:mi><mml:mo>></mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math> , for any conflict graph with maximum degree $$\Delta$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>Δ</mml:mi></mml:math> , and that, if $$n > \Delta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>n</mml:mi><mml:mo>></mml:mo><mml:mi>Δ</mml:mi></mml:mrow></mml:math> , a 1/3-approximate MMS allocation always exists.

View PDF Chat

The Fair Division of Hereditary Set Systems

2018-01-01

Zhentao Li , Adrian Vetta

We consider the fair division of indivisible items using the maximin shares measure. Recent work on the topic has focused on extending results beyond the class of additive valuation functions. … We consider the fair division of indivisible items using the maximin shares measure. Recent work on the topic has focused on extending results beyond the class of additive valuation functions. In this spirit, we study the case where the items form an hereditary set system. We present a simple algorithm that allocates each agent a bundle of items whose value is at least $0.3636$ times the maximin share of the agent. This improves upon the current best known guarantee of $0.2$ due to Ghodsi et al. The analysis of the algorithm is almost tight; we present an instance where the algorithm provides a guarantee of at most $0.3738$. We also show that the algorithm can be implemented in polynomial time given a valuation oracle for each agent.

Fair Division with a Secretive Agent

2018-11-27

Eshwar Ram Arunachaleswaran , Siddharth Barman , Nidhi Rathi

We study classic fair-division problems in a partial information setting. This paper respectively addresses fair division of rent, cake, and indivisible goods among agents with cardinal preferences. We will show … We study classic fair-division problems in a partial information setting. This paper respectively addresses fair division of rent, cake, and indivisible goods among agents with cardinal preferences. We will show that, for all of these settings and under appropriate valuations, a fair (or an approximately fair) division among n agents can be efficiently computed using only the valuations of n-1 agents. The nth (secretive) agent can make an arbitrary selection after the division has been proposed and, irrespective of her choice, the computed division will admit an overall fair allocation. For the rent-division setting we prove that the (well-behaved) utilities of n-1 agents suffice to find a rent division among n rooms such that, for every possible room selection of the secretive agent, there exists an allocation (of the remaining n-1 rooms among the n-1 agents) which ensures overall envy freeness (fairness). We complement this existential result by developing a polynomial-time algorithm that finds such a fair rent division under quasilinear utilities. In this partial information setting, we also develop efficient algorithms to compute allocations that are envy-free up to one good (EF1) and epsilon-approximate envy free. These two notions of fairness are applicable in the context of indivisible goods and divisible goods (cake cutting), respectively. This work also addresses fairness in terms of proportionality and maximin shares. Our key result here is an efficient algorithm that, even with a secretive agent, finds a 1/19-approximate maximin fair allocation (of indivisible goods) under submodular valuations of the non-secretive agents. One of the main technical contributions of this paper is the development of novel connections between different fair-division paradigms, e.g., we use our existential results for envy-free rent-division to develop an efficient EF1 algorithm.

Fair division of indivisible goods: Recent progress and open questions

2023-06-16

Georgios Amanatidis , Haris Aziz , Georgios Birmpas +5 more

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 … 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 recent 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.

View PDF Chat

An improved approximation algorithm for maximin shares

2021-06-08

Jugal Garg , Setareh Taki

View PDF Chat

Extension of Additive Valuations to General Valuations on the Existence of EFX

2023-08-01

Ryoga Mahara

Envy freeness is one of the most widely studied notions in fair division. Because envy-free allocations do not always exist when items are indivisible, several relaxations have been considered. Among … Envy freeness is one of the most widely studied notions in fair division. Because envy-free allocations do not always exist when items are indivisible, several relaxations have been considered. Among them, possibly the most compelling notion is envy freeness up to any item (EFX). Informally speaking, EFX requires that no agent i envies another agent j after the removal of any item in j’s bundle. The existence of EFX allocations is a major open problem. We study the existence of EFX allocations when agents have general valuations. For general valuations, it is known that an EFX allocation always exists (i) when n = 2 or (ii) when all agents have identical valuations, where n is the number of agents. It is also known that an EFX allocation always exists when one can leave at most n − 1 items unallocated. We develop new techniques and extend some results of additive valuations to general valuations on the existence of EFX allocations. We show that an EFX allocation always exists (i) when all agents have one of two general valuations or (ii) when the number of items is at most n + 3. We also show that an EFX allocation always exists when one can leave at most n − 2 items unallocated. In addition to the positive results, we construct an instance with n = 3, in which an existing approach does not work. Funding: This work was partially supported by Kyoto University and Toyota Motor Corporation [Joint Project “Advanced Mathematical Science for Mobility Society”].

View PDF Chat

An Improved Approximation Algorithm for Maximin Shares

2020-07-09

Jugal Garg , Setareh Taki

View PDF Chat

On Achieving Fairness and Stability in Many-to-One Matchings

2020-09-12

Shivika Narang , Arpita Biswas , Y. Narahari

The past few years have seen a surge of work on fairness in social choice literature. This paper initiates the study of finding a stable many-to-one matching, under cardinal valuations, … The past few years have seen a surge of work on fairness in social choice literature. This paper initiates the study of finding a stable many-to-one matching, under cardinal valuations, while satisfying fairness among the agents on either side. Specifically, motivated by several real-world settings, we focus on leximin optimal fairness and seek leximin optimality over many-to-one stable matchings. We first consider the special case of ranked valuations where all agents on each side have the same preference orders or rankings over the agents on the other side (but not necessarily the same valuations). For this special case, we provide a complete characterisation of the space of stable matchings. This leads to FaSt, a novel and efficient algorithm to compute a leximin optimal stable matching under ranked isometric valuations (where, for each pair of agents, the valuation of one agent for the other is the same). The running time of FaSt is linear in the number of edges. Building upon FaSt, we present an efficient algorithm, FaSt-Gen, that finds the leximin optimal stable matching for ranked but otherwise unconstrained valuations. The running time of FaSt-Gen is quadratic in the number of edges. We next establish that, in the absence of rankings, finding a leximin optimal stable matching is NP-Hard, even under isometric valuations. In fact, when additivity and non-negativity are the only assumptions on the valuations, we show that, unless P=NP, no efficient polynomial factor approximation is possible. When additivity is relaxed to submodularity, we find that not even an exponential approximation is possible.

A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations

2022-02-01

Wenzheng Li , Jan Vondrák

We present a 380-approximation algorithm for the Nash Social Welfare problem with submodular valuations. Our algorithm builds on and extends a recent constant-factor approximation for Rado valuations [15]. We present a 380-approximation algorithm for the Nash Social Welfare problem with submodular valuations. Our algorithm builds on and extends a recent constant-factor approximation for Rado valuations [15].

View PDF Chat

How to Fairly Allocate Easy and Difficult Chores

2021-01-01

Soroush Ebadian , Dominik Peters , Nisarg Shah

A major open question in fair allocation of indivisible items is whether there always exists an allocation of chores that is Pareto optimal (PO) and envy-free up to one item … A major open question in fair allocation of indivisible items is whether there always exists an allocation of chores that is Pareto optimal (PO) and envy-free up to one item (EF1). We answer this question affirmatively for the natural class of bivalued utilities, where each agent partitions the chores into easy and difficult ones, and has cost $p > 1$ for chores that are difficult for her and cost $1$ for chores that are easy for her. Such an allocation can be found in polynomial time using an algorithm based on the Fisher market. We also show that for a slightly broader class of utilities, where each agent $i$ can have a potentially different integer $p_i$, an allocation that is maximin share fair (MMS) always exists and can be computed in polynomial time, provided that each $p_i$ is an integer. Our MMS arguments also hold when allocating goods instead of chores, and extend to another natural class of utilities, namely weakly lexicographic utilities.

View PDF Chat

Indivisible Mixed Manna: On the Computability of MMS + PO Allocations

2020-01-01

Rucha Kulkarni , Ruta Mehta , Setareh Taki

In this paper we initiate the study of finding fair and efficient allocations of an indivisible mixed manna: Divide m indivisible items among n agents under the fairness notion of … In this paper we initiate the study of finding fair and efficient allocations of an indivisible mixed manna: Divide m indivisible items among n agents under the fairness notion of maximin share (MMS) and the efficiency notion of Pareto optimality (PO). A mixed manna allows an item to be a good for some agents and a chore for others. The problem of finding $\alpha$-MMS allocation for the (near) best $\alpha\in(0,1]$ for which it exists, remains unresolved even for a goods manna with constantly many agents, while the problem of finding $\alpha$-MMS+PO allocation is unexplored for any $\alpha\in(0,1]$. We make significant progress on the above questions for a mixed manna. First, we show that for any $\alpha>0$, an $\alpha$-MMS allocation may not always exist, thus ruling out solving the problem for a fixed $\alpha$. Second, towards computing $\alpha$-MMS+PO allocation for the best possible $\alpha$, we obtain a dichotomous result: We derive two conditions and show that the problem is tractable under these two conditions, while dropping either renders the problem intractable. The two conditions are: (i) number of agents is a constant, and (ii) for every agent, her absolute value for all the items is at least a constant factor of her total (absolute) value for all the goods or all the chores. In particular, first, for instances satisfying (i) and (ii) we design a PTAS - an efficient algorithm to find an $(\alpha-\epsilon)$-MMS and $\gamma$-PO allocation when given $\epsilon,\gamma>0$, for the highest possible $\alpha\in(0,1]$. Second, we show that if either condition is not satisfied then finding an $\alpha$-MMS allocation for any $\alpha\in(0,1]$ is NP-hard, even when a solution exists for $\alpha=1$. To the best of our knowledge, ours is the first algorithm that ensures both approximate MMS and PO guarantees.

View PDF Chat

Fair Division of Indivisible Goods: A Survey

2022-07-01

Georgios Amanatidis , Georgios Birmpas , Aris Filos-Ratsikas +1 more

Allocating resources to individuals in a fair manner has been a topic of interest since the ancient times, with most of the early rigorous mathematical work on the problem focusing … Allocating resources to individuals in a fair manner has been a topic of interest since the ancient times, with most of the early rigorous mathematical work on the problem focusing on infinitely divisible resources. Recently, there has been a surge of papers studying computational questions regarding various different notions of fairness for the indivisible case, like maximin share fairness (MMS) and envy-freeness up to any good (EFX). We survey the most important results in the discrete fair division literature, focusing on the case of additive valuation functions and paying particular attention to the progress made in the last 10 years.

View PDF Chat

When Do Envy-Free Allocations Exist?

2020-01-01

Pasin Manurangsi , Warut Suksompong

We consider a fair division setting in which $m$ indivisible items are to be allocated among $n$ agents, where the agents have additive utilities and the agents' utilities for individual … We consider a fair division setting in which $m$ indivisible items are to be allocated among $n$ agents, where the agents have additive utilities and the agents' utilities for individual items are independently sampled from a distribution. Previous work has shown that an envy-free allocation is likely to exist when $m=\Omega(n\log n)$ but not when $m=n+o(n)$, and left open the question of determining where the phase transition from non-existence to existence occurs. We show that, surprisingly, there is in fact no universal point of transition---instead, the transition is governed by the divisibility relation between $m$ and $n$. On the one hand, if $m$ is divisible by $n$, an envy-free allocation exists with high probability as long as $m\geq 2n$. On the other hand, if $m$ is not “almost” divisible by $n$, an envy-free allocation is unlikely to exist even when $m=\Theta(n\log n/\log\log n)$.

View PDF Chat

A Little Charity Guarantees Almost Envy-Freeness

2021-01-01

Bhaskar Ray Chaudhury , Telikepalli Kavitha , Kurt Mehlhorn +1 more

The fair division of indivisible goods is a very well-studied problem. The goal of this problem is to distribute $m$ goods to $n$ agents in a "fair" manner, where every … The fair division of indivisible goods is a very well-studied problem. The goal of this problem is to distribute $m$ goods to $n$ agents in a "fair" manner, where every agent has a valuation for each subset of goods. We assume monotone valuations. Envy-freeness is the most extensively studied notion of fairness. However, envy-free allocations do not always exist when goods are indivisible. The notion of fairness we consider here is "envy-freeness up to any good," EFX, where no agent envies another agent after the removal of any single good from the other agent's bundle. It is not known if such an allocation always exists. We show there is always a partition of the set of goods into $n+1$ subsets $(X_1,\ldots,X_n,P)$, where for $i \in [n]$, $X_i$ is the bundle allocated to agent $i$ and the set $P$ is unallocated (or donated to charity) such that we have (1) envy-freeness up to any good, (2) no agent values $P$ higher than her own bundle, and (3) fewer than $n$ goods go to charity, i.e., $|P| < n$ (typically $m \gg n$). Our proof is constructive and leads to a pseudopolynomial time algorithm to find such an allocation. When agents have additive valuations and $|{P}|$ is large (i.e., when $|P|$ is close to $n$), our allocation also has a good maximin share (MMS) guarantee. Moreover, a minor variant of our algorithm also shows the existence of an allocation that is 4/7 groupwise maximin share (GMMS): this is a notion of fairness stronger than MMS. This improves upon the current best bound of 1/2 known for an approximate GMMS allocation. (Very recently and independently, Amanatidis, Ntokos, and Markakis [Theoret. Comput. Sci., 841 (2020), pp. 94--109], also showed the existence of a 4/7-GMMS allocation.)

View PDF Chat

Comparing Approximate Relaxations of Envy-Freeness

2018-07-01

Georgios Amanatidis , Georgios Birmpas , Vangelis Markakis

In fair division problems with indivisible goods it is well known that one cannot have any guarantees for the classic fairness notions of envy-freeness and proportionality. As a result, several … In fair division problems with indivisible goods it is well known that one cannot have any guarantees for the classic fairness notions of envy-freeness and proportionality. As a result, several relaxations have been introduced, most of which in quite recent works. We focus on four such notions, namely envy-freeness up to one good (EF1), envy-freeness up to any good (EFX), maximin share fairness (MMS), and pairwise maximin share fairness (PMMS). Since obtaining these relaxations also turns out to be problematic in several scenarios, approximate versions of them have also been considered. In this work, we investigate further the connections between the four notions mentioned above and their approximate versions. We establish several tight or almost tight results concerning the approximation quality that any of these notions guarantees for the others, providing an almost complete picture of this landscape. Some of our findings reveal interesting and surprising consequences regarding the power of these notions, e.g., PMMS and EFX provide the same worst-case guarantee for MMS, despite PMMS being a strictly stronger notion than EFX. We believe such implications provide further insight on the quality of approximately fair solutions.

View PDF Chat

Computational Statistics

2009-01-01

James E. Gentle

View PDF Chat

A discrete and bounded envy-free cake cutting protocol for four agents

2016-06-10

Haris Aziz , Simon Mackenzie

We consider the well-studied cake cutting problem in which the goal is to identify an envy-free allocation based on a minimal number of queries from the agents. The problem has … We consider the well-studied cake cutting problem in which the goal is to identify an envy-free allocation based on a minimal number of queries from the agents. The problem has attracted considerable attention within various branches of computer science, mathematics, and economics. Although, the elegant Selfridge-Conway envy-free protocol for three agents has been known since 1960, it has been a major open problem to obtain a bounded envy-free protocol for more than three agents. The problem has been termed the central open problem in cake cutting. We solve this problem by proposing a discrete and bounded envy-free protocol for four agents.

View PDF Chat

On Representatives of Subsets

1935-01-01

P. Hall

On Truthful Mechanisms for Maximin Share Allocations

2016-01-01

Georgios Amanatidis , Georgios Birmpas , Evangelos Markakis

Approximation Algorithms for Maximin Fair Division

2017-06-20

Siddharth Barman , Sanath Kumar Krishna Murthy

View PDF Chat

Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness

2017-06-20

Georgios Amanatidis , Georgios Birmpas , George Christodoulou +1 more

We study the mechanism design problem of allocating a set of indivisible items without monetary transfers. Despite the vast literature on this very standard model, it still remains unclear how … We study the mechanism design problem of allocating a set of indivisible items without monetary transfers. Despite the vast literature on this very standard model, it still remains unclear how do truthful mechanisms look like. We focus on the case of two players with additive valuation functions and our purpose is twofold. First, our main result provides a complete characterization of truthful mechanisms that allocate all the items to the players. Our characterization reveals an interesting structure underlying all truthful mechanisms, showing that they can be decomposed into two components: a selection part where players pick their best subset among prespecified choices determined by the mechanism, and an exchange part where players are offered the chance to exchange certain subsets if it is favorable to do so. In the remaining paper, we apply our main result and derive several consequences on the design of mechanisms with fairness guarantees. We consider various notions of fairness, (indicatively, maximin share guarantees and envy-freeness up to one item) and provide tight bounds for their approximability. Our work settles some of the open problems in this agenda, and we conclude by discussing possible extensions to more players.

View PDF Chat