Approximation Algorithms for Maximin Fair Division

Authors

Siddharth Barman, Sanath Kumar Krishna Murthy

Type: Article

Publication Date: 2017-06-20

Citations: 93

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

Ask PDF

Abstract

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.

Locations

arXiv (Cornell University)
View PDF

Ask a Question About This Paper

Summary

Similar Works

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 .

Chat View PDF

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.

Chat View PDF

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.

Chat View PDF

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.

Chat View PDF

Groupwise Maximin Fair Allocation of Indivisible Goods

2017-01-01

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

Chat View PDF

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.

Chat View PDF

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.

Chat View PDF

Guaranteeing Maximin Shares: Some Agents Left Behind

2021-01-01

Seyed Hossein 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.

Chat View PDF

Approximation Algorithms for Computing Maximin Share Allocations

2017-10-31

Georgios Amanatidis , Evangelos Markakis , Afshin Nikzad +1 more

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

Chat View PDF

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.

Chat View PDF

Achieving Proportionality up to the Maximin Item with Indivisible Goods

2020-01-01

Artem Baklanov , Pranav Garimidi , Vasilis Gkatzelis +1 more

Chat View PDF

Achieving Proportionality up to the Maximin Item with Indivisible Goods

2021-05-18

Artem Baklanov , Pranav Garimidi , Vasilis Gkatzelis +1 more

Chat View PDF

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.

Chat View PDF

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.

Chat View PDF

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.

Chat View PDF

Maximin Share Guarantees for Few Agents with Subadditive Valuations

2025-02-07

George Christodoulou , Vasilis Christoforidis , Symeon Mastrakoulis +1 more

We study the problem of fairly allocating a set of indivisible items among a set of agents. We consider the notion of (approximate) maximin share (MMS) and we provide an … We study the problem of fairly allocating a set of indivisible items among a set of agents. We consider the notion of (approximate) maximin share (MMS) and we provide an improved lower bound of $1/2$ (which is tight) for the case of subadditive valuations when the number of agents is at most four. We also provide a tight lower bound for the case of multiple agents, when they are equipped with one of two possible types of valuations. Moreover, we propose a new model that extends previously studied models in the area of fair division, which will hopefully give rise to further research. We demonstrate the usefulness of this model by employing it as a technical tool to derive our main result, and we provide a thorough analysis for this model for the case of three agents. Finally, we provide an improved impossibility result for the case of three submodular agents.

Chat View PDF

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.

Chat View PDF

Maximin Fairness with Mixed Divisible and Indivisible Goods

2021-05-18

Xiaohui Bei , Shengxin Liu , Xinhang Lu +1 more

We study fair resource allocation when the resources contain a mixture of divisible and indivisible goods, focusing on the well-studied fairness notion of maximin share fairness (MMS). With only indivisible … We study fair resource allocation when the resources contain a mixture of divisible and indivisible goods, focusing on the well-studied fairness notion of maximin share fairness (MMS). With only indivisible goods, a full MMS allocation may not exist, but a constant multiplicative approximate allocation always does. We analyze how the MMS approximation guarantee would be affected when the resources to be allocated also contain divisible goods. In particular, we show that the worst-case MMS approximation guarantee with mixed goods is no worse than that with only indivisible goods. However, there exist problem instances to which adding some divisible resources would strictly decrease the MMS approximation ratios of the instances. On the algorithmic front, we propose a constructive algorithm that will always produce an \alpha-MMS allocation for any number of agents, where \alpha takes values between 1/2 and 1 and is a monotonically increasing function determined by how agents value the divisible goods relative to their MMS values.

Chat View PDF

Maximin-Aware Allocations of Indivisible Goods

2019-07-28

Hau Chan , Jing Chen , Bo Li +1 more

We study envy-free allocations of indivisible goods to agents in settings where each agent is unaware of the goods allocated to other agents. In particular, we propose the maximin aware … We study envy-free allocations of indivisible goods to agents in settings where each agent is unaware of the goods allocated to other agents. In particular, we propose the maximin aware (MMA) fairness measure, which guarantees that every agent, given the bundle allocated to her, is aware that she does not envy at least one other agent, even if she does not know how the other goods are distributed among other agents. We also introduce two of its relaxations, and discuss their egalitarian guarantee and existence. Finally, we present a polynomial-time algorithm, which computes an allocation that approximately satisfies MMA or its relaxations. Interestingly, the returned allocation is also 1/2-approximate EFX when all agents have sub- additive valuations, which improves the algorithm in [Plaut and Roughgarden, 2018].

Chat View PDF

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$.

Chat View PDF

Cited by (40)

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

Chat View PDF

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

2021-11-27

Elad Aigner‐Horev , Erel Segal-Halevi

Chat View PDF

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

2022-01-01

Moshe Babaioff , Tomer Ezra , Uriel Feige

Chat View PDF

Existence of EFX for two additive valuations

2023-07-20

Ryoga Mahara

Chat View PDF

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.

Chat View PDF

The Price of Quota-based Diversity in Assignment Problems

2020-08-31

Nawal Benabbou , Mithun Chakraborty , Xuan-Vinh Ho +2 more

We introduce and analyze an extension to the matching problem on a weighted bipartite graph: Assignment with Type Constraints. The two parts of the graph are partitioned into subsets called … We introduce and analyze an extension to the matching problem on a weighted bipartite graph: Assignment with Type Constraints. The two parts of the graph are partitioned into subsets called types and blocks; we seek a matching with the largest sum of weights under the constraint that there is a pre-specified cap on the number of vertices matched in every type-block pair. Our primary motivation stems from the public housing program of Singapore, accounting for over 70% of its residential real estate. To promote ethnic diversity within its housing projects, Singapore imposes ethnicity quotas: each new housing development comprises blocks of flats and each ethnicity-based group in the population must not own more than a certain percentage of flats in a block. Other domains using similar hard capacity constraints include matching prospective students to schools or medical residents to hospitals. Limiting agents' choices for ensuring diversity in this manner naturally entails some welfare loss. One of our goals is to study the trade-off between diversity and social welfare in such settings. We first show that, while the classic assignment program is polynomial-time computable, adding diversity constraints makes it computationally intractable; however, we identify a $\tfrac{1}{2}$-approximation algorithm, as well as reasonable assumptions on the weights that permit poly-time algorithms. Next, we provide two upper bounds on the price of diversity -- a measure of the loss in welfare incurred by imposing diversity constraints -- as functions of natural problem parameters. We conclude the paper with simulations based on publicly available data from two diversity-constrained allocation problems -- Singapore Public Housing and Chicago School Choice -- which shed light on how the constrained maximization as well as lottery-based variants perform in practice.

Chat View PDF

Approximate and strategyproof maximin share allocation of chores with ordinal preferences

2022-07-05

Haris Aziz , Bo Li , Xiaowei Wu

Chat View PDF

Fair Division Under Cardinality Constraints

2018-07-01

Arpita Biswas , Siddharth Barman

We consider the problem of fairly allocating indivisible goods, among agents, under cardinality constraints and additive valuations. In this setting, we are given a partition of the entire set of … We consider the problem of fairly allocating indivisible goods, among agents, under cardinality constraints and additive valuations. In this setting, we are given a partition of the entire set of goods---i.e., the goods are categorized---and a limit is specified on the number of goods that can be allocated from each category to any agent. The objective here is to find a fair allocation in which the subset of goods assigned to any agent satisfies the given cardinality constraints. This problem naturally captures a number of resource-allocation applications, and is a generalization of the well-studied unconstrained fair division problem. The two central notions of fairness, in the context of fair division of indivisible goods, are envy freeness up to one good (EF1) and the (approximate) maximin share guarantee (MMS). We show that the existence and algorithmic guarantees established for these solution concepts in the unconstrained setting can essentially be achieved under cardinality constraints. Furthermore, focusing on the case wherein all the agents have the same additive valuation, we establish that EF1 allocations exist even under matroid constraints.

Chat View PDF

A Little Charity Guarantees Almost Envy-Freeness

2019-12-23

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

Previous chapter Next chapter Full AccessProceedings Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA)A Little Charity Guarantees Almost Envy-FreenessBhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini SgouritsaBhaskar … Previous chapter Next chapter Full AccessProceedings Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA)A Little Charity Guarantees Almost Envy-FreenessBhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini SgouritsaBhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsapp.2658 - 2672Chapter DOI:https://doi.org/10.1137/1.9781611975994.162PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract 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 general 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 even when n = 3. We show there is always a partition of the set of goods into n + 1 subsets (X1, …, Xn, P) where for i ϵ [n], Xi 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 ≫ n). Our proof is constructive. 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 which 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. Previous chapter Next chapter RelatedDetails Published:2020eISBN:978-1-61197-599-4 https://doi.org/10.1137/1.9781611975994Book Series Name:ProceedingsBook Code:PRDA20Book Pages:xxii + 3011

Chat View PDF

Ordinal Maximin Share Approximation for Goods

2022-05-26

Hadi Hosseini , Andrew Searns , Erel Segal-Halevi

Chat View PDF

Toward Fair Recommendation in Two-sided Platforms

2021-12-21

Arpita Biswas , Gourab K Patro , Niloy Ganguly +2 more

Many online platforms today (such as Amazon, Netflix, Spotify, LinkedIn, and AirBnB) can be thought of as two-sided markets with producers and customers of goods and services. Traditionally, recommendation services … Many online platforms today (such as Amazon, Netflix, Spotify, LinkedIn, and AirBnB) can be thought of as two-sided markets with producers and customers of goods and services. Traditionally, recommendation services in these platforms have focused on maximizing customer satisfaction by tailoring the results according to the personalized preferences of individual customers. However, our investigation reinforces the fact that such customer-centric design of these services may lead to unfair distribution of exposure to the producers, which may adversely impact their well-being. However, a pure producer-centric design might become unfair to the customers. As more and more people are depending on such platforms to earn a living, it is important to ensure fairness to both producers and customers. In this work, by mapping a fair personalized recommendation problem to a constrained version of the problem of fairly allocating indivisible goods, we propose to provide fairness guarantees for both sides. Formally, our proposed FairRec algorithm guarantees Maxi-Min Share of exposure for the producers, and Envy-Free up to One Item fairness for the customers. Extensive evaluations over multiple real-world datasets show the effectiveness of FairRec in ensuring two-sided fairness while incurring a marginal loss in overall recommendation quality. Finally, we present a modification of FairRec (named as FairRecPlus ) that at the cost of additional computation time, improves the recommendation performance for the customers, while maintaining the same fairness guarantees.

Chat View PDF

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.

Chat View PDF

Approximation Algorithms for Computing Maximin Share Allocations

2017-10-31

Georgios Amanatidis , Evangelos Markakis , Afshin Nikzad +1 more

Chat View PDF

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

Chat View PDF

A Little Charity Guarantees Almost Envy-Freeness

2019-07-10

Bhaskar Ray Chaudhury , T. Kavitha , Kurt Mehlhorn +1 more

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 … 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 general 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 up to any (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 even when $n=3$. 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$\colon$ 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. When agents have additive valuations and $\lvert P \rvert$ 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 which 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.

Chat View PDF

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

2022-01-01

Georgios Amanatidis , Georgios Birmpas , Federico Fusco +3 more

Chat View PDF

Approximate maximin shares for groups of agents

2017-09-22

Warut Suksompong

Chat View PDF

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].

Chat View PDF

The Fair Division of Hereditary Set Systems

2018-01-01

Z. Li , Adrian Vetta

Chat View PDF

Maximin Shares Under Cardinality Constraints

2022-01-01

Halvard Hummel , Magnus Lie Hetland

Chat View PDF

Unified Fair Allocation of Goods and Chores via Copies

2023-09-22

Yotam Gafni , Xin Huang , Ron Lavi +1 more

We consider fair allocation of indivisible items in a model with goods, chores, and copies, as a unified framework for studying: (1) the existence of EFX and other solution concepts … We consider fair allocation of indivisible items in a model with goods, chores, and copies, as a unified framework for studying: (1) the existence of EFX and other solution concepts for goods with copies; (2) the existence of EFX and other solution concepts for chores. We establish a tight relation between these issues via two conceptual contributions: First, a refinement of envy-based fairness notions that we term envy without commons (denoted EFX WC when applied to EFX). Second, a formal duality theorem relating the existence of a host of (refined) fair allocation concepts for copies to their existence for chores. We demonstrate the usefulness of our duality result by using it to characterize the existence of EFX for chores through the dual environment, as well as to prove EFX existence in the special case of leveled preferences over the chores. We further study the hierarchy among envy-freeness notions without commons and their α-MMS guarantees, showing, for example, that any EFX WC allocation guarantees at least $\frac{4}{11}$ -MMS for goods with copies.

Chat View PDF

Fair and Efficient Allocations under Subadditive Valuations

2021-05-18

Bhaskar Ray Chaudhury , Jugal Garg , Ruta Mehta

We study the problem of allocating a set of indivisible goods among agents with subadditive valuations in a fair and efficient manner. Envy-Freeness up to any good (EFX) is the … We study the problem of allocating a set of indivisible goods among agents with subadditive valuations in a fair and efficient manner. Envy-Freeness up to any good (EFX) is the most compelling notion of fairness in the context of indivisible goods. Although the existence of EFX is not known beyond the simple case of two agents with subadditive valuations, some good approximations of EFX are known to exist, namely 1/2-EFX allocation and EFX allocations with bounded charity. Nash welfare (the geometric mean of agents' valuations) is one of the most commonly used measures of efficiency. In case of additive valuations, an allocation that maximizes Nash welfare also satisfies fairness properties like Envy-Free up to one good (EF1). Although there is substantial work on approximating Nash welfare when agents have additive valuations, very little is known when agents have subadditive valuations. In this paper, we design a polynomial-time algorithm that outputs an allocation that satisfies either of the two approximations of EFX as well as achieves an O(n) approximation to the Nash welfare. Our result also improves the current best-known approximation of O(n log n) and O(m) to Nash welfare when agents have submodular and subadditive valuations, respectively. Furthermore, our technique also gives an O(n) approximation to a family of welfare measures, p-mean of valuations for p in (-\infty, 1], thereby also matching asymptotically the current best approximation ratio for special cases like p = -\infty while also retaining the remarkable fairness properties.

Chat View PDF

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.

Chat View PDF

The Price of Connectivity in Fair Division

2021-05-18

Xiaohui Bei , Ayumi Igarashi , Xinhang Lu +1 more

We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected … We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. Our focus is on the well-studied fairness notion of maximin share fairness. We introduce the price of connectivity to capture the largest gap between the graph-specific and the unconstrained maximin share, and derive bounds on this quantity which are tight for large classes of graphs in the case of two agents and for paths and stars in the general case. For instance, with two agents we show that for biconnected graphs it is possible to obtain at least 3/4 of the maximin share with connected allocations, while for the remaining graphs the guarantee is at most 1/2. Our work demonstrates several applications of graph-theoretic tools and concepts to fair division problems.

Chat View PDF

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.

Chat View PDF

Almost Envy-freeness, Envy-rank, and Nash Social Welfare Matchings

2021-05-18

Alireza Farhadi , MohammadTaghi Hajiaghayi , Mohamad Latifian +2 more

Envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX) are two well-known extensions of envy-freeness for the case of indivisible items. It is shown that EF1 … Envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX) are two well-known extensions of envy-freeness for the case of indivisible items. It is shown that EF1 can always be guaranteed for agents with subadditive valuations. In sharp contrast, it is unknown whether or not an EFX allocation always exists, even for four agents and additive valuations. In addition, the best approximation guarantee for EFX is (φ − 1) ≃ 0.61 by Amanitidis et al.. In order to find a middle ground to bridge this gap, in this paper we suggest another fairness criterion, namely envy-freeness up to a random good or EFR, which is weaker than EFX, yet stronger than EF1. For this notion, we provide a polynomial-time 0.73-approximation allocation algorithm. For our algorithm we introduce Nash Social Welfare Matching which makes a connection between Nash Social Welfare and envy freeness.

Chat View PDF

Achieving Proportionality up to the Maximin Item with Indivisible Goods

2021-05-18

Artem Baklanov , Pranav Garimidi , Vasilis Gkatzelis +1 more

Chat View PDF

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.

Chat View PDF

Pipeline Interventions

2022-05-16

Eshwar Ram Arunachaleswaran , Sampath Kannan , Aaron Roth +1 more

We introduce the pipeline intervention problem, defined by a layered directed acyclic graph and a set of stochastic matrices governing transitions between successive layers. The graph is a stylized model … We introduce the pipeline intervention problem, defined by a layered directed acyclic graph and a set of stochastic matrices governing transitions between successive layers. The graph is a stylized model for how people from different populations are presented opportunities, eventually leading to some reward. In our model, individuals are born into an initial position (i.e., some node in the first layer of the graph) according to a fixed probability distribution and then stochastically progress through the graph according to the transition matrices until they reach a node in the final layer of the graph; each node in the final layer has a reward associated with it. The pipeline intervention problem asks how to best make costly changes to the transition matrices governing people’s stochastic transitions through the graph subject to a budget constraint. We consider two objectives: social welfare maximization and a fairness-motivated maximin objective that seeks to maximize the value to the population (starting node) with the least expected value. We consider two variants of the maximin objective that turn out to be distinct, depending on whether we demand a deterministic solution or allow randomization. For each objective, we give an efficient approximation algorithm (an additive fully polynomial-time approximation scheme) for constant-width networks. We also tightly characterize the “price of fairness” in our setting: the ratio between the highest achievable social welfare and the social welfare consistent with a maximin optimal solution. Finally, we show that, for polynomial-width networks, even approximating the maximin objective to any constant factor is NP hard even for networks with constant depth. This shows that the restriction on the width in our positive results is essential.

Almost (Weighted) Proportional Allocations for Indivisible Chores✱✱

2022-04-25

Bo Li , Yingkai Li , Xiaowei Wu

In this paper, we study how to fairly allocate a set of indivisible chores to a number of (asymmetric) agents with additive cost functions. We consider the fairness notion of … In this paper, we study how to fairly allocate a set of indivisible chores to a number of (asymmetric) agents with additive cost functions. We consider the fairness notion of (weighted) proportionality up to any item (PROPX), and show that a (weighted) PROPX allocation always exists and can be computed efficiently. We also consider the partial information setting, where the algorithms can only use agents' ordinal preferences. We design algorithms that achieve 2-approximate (weighted) PROPX, and the approximation ratio is optimal. We complement the algorithmic results by investigating the relationship between (weighted) PROPX and other fairness notions such as maximin share and AnyPrice share, and bounding the social welfare loss by enforcing the allocations to be (weighted) PROPX.

Chat View PDF

Maximum Nash Welfare and Other Stories About EFX

2020-07-01

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

We consider the classic problem of fairly allocating indivisible goods among agents with additive valuation functions and explore the connection between two prominent fairness notions: maximum Nash welfare (MNW) and … We consider the classic problem of fairly allocating indivisible goods among agents with additive valuation functions and explore the connection between two prominent fairness notions: maximum Nash welfare (MNW) and envy-freeness up to any good (EFX). We establish that an MNW allocation is always EFX as long as there are at most two possible values for the goods, whereas this implication is no longer true for three or more distinct values. As a notable consequence, this proves the existence of EFX allocations for these restricted valuation functions. While the efficient computation of an MNW allocation for two possible values remains an open problem, we present a novel algorithm for directly constructing EFX allocations in this setting. Finally, we study the question of whether an MNW allocation implies any EFX guarantee for general additive valuation functions under a natural new interpretation of approximate EFX allocations.

Chat View PDF

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”].

Chat View PDF

An Improved Approximation Algorithm for Maximin Shares

2020-07-09

Jugal Garg , Setareh Taki

Chat View PDF

Almost Group Envy-free Allocation of Indivisible Goods and Chores

2020-07-01

Haris Aziz , Simon Rey

We consider a multi-agent resource allocation setting in which an agent's utility may decrease or increase when an item is allocated. We take the group envy-freeness concept that is well-established … We consider a multi-agent resource allocation setting in which an agent's utility may decrease or increase when an item is allocated. We take the group envy-freeness concept that is well-established in the literature and present stronger and relaxed versions that are especially suitable for the allocation of indivisible items. Of particular interest is a concept called group envy-freeness up to one item (GEF1). We then present a clear taxonomy of the fairness concepts. We study which fairness concepts guarantee the existence of a fair allocation under which preference domain. For two natural classes of additive utilities, we design polynomial-time algorithms to compute a GEF1 allocation. We also prove that checking whether a given allocation satisfies GEF1 is coNP-complete when there are either only goods, only chores or both.

Chat View PDF

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.

Chat View PDF

Envy-free Relaxations for Goods, Chores, and Mixed Items

2020-01-01

Kristóf Bérczi , Erika R. Bérczi‐Kovács , Endre Boros +5 more

In fair division problems, we are given a set $S$ of $m$ items and a set $N$ of $n$ agents with individual preferences, and the goal is to find an … In fair division problems, we are given a set $S$ of $m$ items and a set $N$ of $n$ agents with individual preferences, and the goal is to find an allocation of items among agents so that each agent finds the allocation fair. There are several established fairness concepts and envy-freeness is one of the most extensively studied ones. However envy-free allocations do not always exist when items are indivisible and this has motivated relaxations of envy-freeness: envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) are two well-studied relaxations. We consider the problem of finding EF1 and EFX allocations for utility functions that are not necessarily monotone, and propose four possible extensions of different strength to this setting. In particular, we present a polynomial-time algorithm for finding an EF1 allocation for two agents with arbitrary utility functions. An example is given showing that EFX allocations need not exist for two agents with non-monotone, non-additive, identical utility functions. However, when all agents have monotone (not necessarily additive) identical utility functions, we prove that an EFX allocation of chores always exists. As a step toward understanding the general case, we discuss two subclasses of utility functions: Boolean utilities that are $\{0,+1\}$-valued functions, and negative Boolean utilities that are $\{0,-1\}$-valued functions. For the latter, we give a polynomial time algorithm that finds an EFX allocation when the utility functions are identical.

Chat View PDF

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.

Chat View PDF

On Lower Bounds for Maximin Share Guarantees

2023-08-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 ≥ 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 ≥ n_c agents and at most n + c items, where n_c ≤ ⌊0.6597^c · c!⌋ for allocation of goods and n_c ≤ ⌊0.7838^c · c!⌋ for chores. Furthermore, we show that for n ≠ 3 agents, all instances with n + 6 goods have an MMS allocation.

Chat View PDF

Groupwise Maximin Fair Allocation of Indivisible Goods

2018-04-25

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

Chat View PDF

The Price of Fairness for Indivisible Goods

2021-03-29

Xiaohui Bei , Xinhang Lu , Pasin Manurangsi +1 more

Chat View PDF

References (9)

Randomized Pipage Rounding for Matroid Polytopes and Applications

2009-09-24

Chandra Chekuri , Jan Vondrák

Chat View PDF

Symmetry and Approximability of Submodular Maximization Problems

2013-01-01

J. Vondrák

A number of recent results on optimization problems involving submodular functions have made use of the multilinear relaxation of the problem. These results hold typically in the value oracle model, … A number of recent results on optimization problems involving submodular functions have made use of the multilinear relaxation of the problem. These results hold typically in the value oracle model, where the objective function is accessible via a black box returning $f(S)$ for a given $S$. We present a general approach to deriving inapproximability results in the value oracle model, based on the notion of symmetry gap. Our main result is that for any fixed instance that exhibits a certain symmetry gap in its multilinear relaxation, there is a naturally related class of instances for which a better approximation factor than the symmetry gap would require exponentially many oracle queries. This unifies several known hardness results for submodular maximization, e.g., the optimality of $(1-1/e)$-approximation for monotone submodular maximization under a cardinality constraint and the impossibility of $(\frac12+\epsilon)$-approximation for unconstrained (nonmonotone) submodular maximization. As a new application, we consider the problem of maximizing a nonmonotone submodular function over the bases of a matroid. A $(\frac16-o(1))$-approximation has been developed for this problem, assuming that the matroid contains two disjoint bases. We show that the best approximation one can achieve is indeed related to packings of bases in the matroid. Specifically, for any $k \geq 2$, there is a class of matroids of fractional base packing number $\nu = \frac{k}{k-1}$ such that any algorithm achieving a better than $(1-\frac{1}{\nu}) = \frac{1}{k}$-approximation for this class would require exponentially many value queries. In particular, there is no constant factor approximation for maximizing a nonmonotone submodular function over the bases of a general matroid. On the positive side, we present a $\frac12 (1-\frac{1}{\nu}-o(1))$-approximation algorithm assuming fractional base packing number at least $\nu$, where $\nu \in (1,2]$. We also present an improved $0.309$-approximation for maximization of a nonmonotone submodular function subject to a matroid independence constraint, improving the previously known factor of $\frac14-\epsilon$. For this problem, we obtain a hardness of $(\frac12 + \epsilon)$-approximation for any fixed $\epsilon>0$.

Chat View PDF

Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes

2014-01-01

Chandra Chekuri , J. Vondrák , Rico Zenklusen

We consider the problem of maximizing a nonnegative submodular set function $f:2^N \rightarrow {\mathbb R}_+$ over a ground set $N$ subject to a variety of packing-type constraints including (multiple) matroid … We consider the problem of maximizing a nonnegative submodular set function $f:2^N \rightarrow {\mathbb R}_+$ over a ground set $N$ subject to a variety of packing-type constraints including (multiple) matroid constraints, knapsack constraints, and their intersections. In this paper we develop a general framework that allows us to derive a number of new results, in particular, when $f$ may be a nonmonotone function. Our algorithms are based on (approximately) maximizing the multilinear extension $F$ of $f$ over a polytope $P$ that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully, it has been limited in some important ways. We overcome these limitations as follows. First, we give constant factor approximation algorithms to maximize $F$ over a downward-closed polytope $P$ described by an efficient separation oracle. Previously this was known only for monotone functions. For nonmonotone functions, a constant factor was known only when the polytope was either the intersection of a fixed number of knapsack constraints or a matroid polytope. Second, we show that contention resolution schemes are an effective way to round a fractional solution, even when $f$ is nonmonotone. In particular, contention resolution schemes for different polytopes can be combined to handle the intersection of different constraints. Via linear programming duality we show that a contention resolution scheme for a constraint is related to the correlation gap of weighted rank functions of the constraint. This leads to an optimal contention resolution scheme for the matroid polytope. Our results provide a broadly applicable framework for maximizing linear and submodular functions subject to independence constraints. We give several illustrative examples. Contention resolution schemes may find other applications.

Chat View PDF

On Allocating Goods to Maximize Fairness

2009-10-01

Deeparnab Chakrabarty , Julia Chuzhoy , Sanjeev Khanna

We consider the Max-Min Allocation problem: given a set A of m agents and a set I of n items, where agent A ¿ A has utility u <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" … We consider the Max-Min Allocation problem: given a set A of m agents and a set I of n items, where agent A ¿ A has utility u A ,i for item i ¿ I, our goal is to allocate items to agents so as to maximize fairness. Specifically, the utility of an agent is the sum of its utilities for the items it receives, and we seek to maximize the minimum utility of any agent. While this problem has received much attention recently, its approximability has not been well-understood thus far: the best known approximation algorithm achieves an O¿(¿m)-approximation, and in contrast, the best known hardness of approximation stands at 2. Our main result is an algorithm that achieves an O¿(n ¿ )-approximation for any ¿ = ¿((log log n)/(log n)) in time n O(1/¿) . In particular, we obtain poly-logarithmic approximation in quasipolynomial time, and for every constant ¿ > 0, we obtain an O¿(n ¿ )-approximation in polynomial time. An interesting technical aspect of our algorithm is that we use as a building block a linear program whose integrality gap is ¿(¿m). We bypass this obstacle by iteratively using the solutions produced by the LP to construct new instances with significantly smaller integrality gaps, eventually obtaining the desired approximation. As a corollary of our main result, we also show that for any constant ¿ > 0, an O(m ¿ )-approximation can be achieved in quasi-polynomial time. We also investigate the special case of the problem, where every item has non-zero utility for at most two agents. This problem is hard to approximate up to any factor better than 2. We give a factor 2-approximation algorithm.

Chat View PDF

Consistent Estimates Based on Partially Consistent Observations

1948-01-01

Jerzy Neyman , Elizabeth L. Scott

Chat View PDF

Approximation Algorithms for Max-Min Share Allocations of Indivisible Chores and Goods

2016-01-01

Haris Aziz , Gerhard Rauchecker , Guido Schryen +1 more

We consider Max-min Share (MmS) allocations of items both in the case where items are goods (positive utility) and when they are chores (negative utility). We show that fair allocations … We consider Max-min Share (MmS) allocations of items both in the case where items are goods (positive utility) and when they are chores (negative utility). We show that fair allocations of goods and chores have some fundamental connections but differences as well. We prove that like in the case for goods, an MmS allocation does not need to exist for chores and computing an MmS allocation - if it exists - is strongly NP-hard. In view of these non-existence and complexity results, we present a polynomial-time 2-approximation algorithm for MmS fairness for chores. We then introduce a new fairness concept called optimal MmS that represents the best possible allocation in terms of MmS that is guaranteed to exist. For both goods and chores, we use connections to parallel machine scheduling to give (1) an exponential-time exact algorithm and (2) a polynomial-time approximation scheme for computing an optimal MmS allocation when the number of agents is fixed.

Chat View PDF

Approximation Algorithms for Computing Maximin Share Allocations

2015-01-01

Georgios Amanatidis , Evangelos Markakis , Afshin Nikzad +1 more

Chat View PDF

Fair Allocation of Indivisible Goods: Improvement and Generalization

2017-01-01

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

Chat View PDF

Efficiency and Sequenceability in Fair Division of Indivisible Goods with Additive Preferences

2016-01-01

Sylvain Bouveret , Michel Lemaı̂tre

In fair division of indivisible goods, using sequences of sincere choices (or picking sequences) is a natural way to allocate the objects. The idea is the following: at each stage, … In fair division of indivisible goods, using sequences of sincere choices (or picking sequences) is a natural way to allocate the objects. The idea is the following: at each stage, a designated agent picks one object among those that remain. This paper, restricted to the case where the agents have numerical additive preferences over objects, revisits to some extent the seminal paper by Brams and King [9] which was specific to ordinal and linear order preferences over items. We point out similarities and differences with this latter context. In particular, we show that any Pareto-optimal allocation (under additive preferences) is sequenceable, but that the converse is not true anymore. This asymmetry leads naturally to the definition of a "scale of efficiency" having three steps: Pareto-optimality, sequenceability without Pareto-optimality, and non-sequenceability. Finally, we investigate the links between these efficiency properties and the "scale of fairness" we have described in an earlier work [7]: we first show that an allocation can be envy-free and non-sequenceable, but that every competitive equilibrium with equal incomes is sequenceable. Then we experimentally explore the links between the scales of efficiency and fairness.

Chat View PDF