SU\G(𝔸)/K·U
Sign Up for free Log In

PROPm Allocations of Indivisible Goods to Multiple Agents

Authors

Artem Baklanov, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin
Type: Preprint
Publication Date: 2021-01-01
Citations: 0
DOI: https://doi.org/10.48550/arxiv.2105.11348

Abstract

We study the classic problem of fairly allocating a set of indivisible goods among a group of agents, and focus on the notion of approximate proportionality known as PROPm. Prior work showed that there exists an allocation that satisfies this notion of fairness for instances involving up to five agents, but fell short of proving that this is true in general. We extend this result to show that a PROPm allocation is guaranteed to exist for all instances, independent of the number of agents or goods. Our proof is constructive, providing an algorithm that computes such an allocation and, unlike prior work, the running time of this algorithm is polynomial in both the number of agents and the number of goods.

Locations

  • arXiv (Cornell University)
    View
  • DataCite API
    View

PROPm Allocations of Indivisible Goods to Multiple Agents

2021-08-01
Artem Baklanov , Pranav Garimidi , Vasilis Gkatzelis +1 more
We study the classic problem of fairly allocating a set of indivisible goods among a group of agents, and focus on the notion of approximate proportionality known as PROPm. Prior … We study the classic problem of fairly allocating a set of indivisible goods among a group of agents, and focus on the notion of approximate proportionality known as PROPm. Prior work showed that there exists an allocation that satisfies this notion of fairness for instances involving up to five agents, but fell short of proving that this is true in general. We extend this result to show that a PROPm allocation is guaranteed to exist for all instances, independent of the number of agents or goods. Our proof is constructive, providing an algorithm that computes such an allocation and, unlike prior work, the running time of this algorithm is polynomial in both the number of agents and the number of goods.
View PDF Chat

PROPm Allocations of Indivisible Goods to Multiple Agents

2021-05-24
Artem Baklanov , Pranav Garimidi , Vasilis Gkatzelis +1 more
We study the classic problem of fairly allocating a set of indivisible goods among a group of agents, and focus on the notion of approximate proportionality known as PROPm. Prior … We study the classic problem of fairly allocating a set of indivisible goods among a group of agents, and focus on the notion of approximate proportionality known as PROPm. Prior work showed that there exists an allocation that satisfies this notion of fairness for instances involving up to five agents, but fell short of proving that this is true in general. We extend this result to show that a PROPm allocation is guaranteed to exist for all instances, independent of the number of agents or goods. Our proof is constructive, providing an algorithm that computes such an allocation and, unlike prior work, the running time of this algorithm is polynomial in both the number of agents and the number of goods.

Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average

2022-01-01
Yusuke Kobayashi , Ryoga Mahara
We study the problem of fairly allocating a set of indivisible goods to multiple agents and focus on the proportionality, which is one of the classical fairness notions. Since proportional … We study the problem of fairly allocating a set of indivisible goods to multiple agents and focus on the proportionality, which is one of the classical fairness notions. Since proportional allocations do not always exist when goods are indivisible, approximate concepts of proportionality have been considered in the previous work. Among them, proportionality up to the maximin good (PROPm) has been the best approximate notion of proportionality that can be achieved for all instances. In this paper, we introduce the notion of proportionality up to the least valued good on average (PROPavg), which is a stronger notion than PROPm, and show that a PROPavg allocation always exists for all instances and can be computed in polynomial time. %% for all instances. Our results establish PROPavg as a notable non-trivial fairness notion that can be achieved for all instances. Our proof is constructive, and based on a new technique that generalizes the cut-and-choose protocol and uses a recursive technique.
View PDF Chat

Achieving Proportionality up to the Maximin Item with Indivisible Goods

2020-01-01
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

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

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.

Algorithmic Fair Allocation of Indivisible Items: A Survey and New Questions

2022-01-01
Haris Aziz , Bo Li , Hervé Moulin +1 more
The theory of algorithmic fair allocation is within the center of multi-agent systems and economics in the last decade due to its industrial and social importance. At a high level, … The theory of algorithmic fair allocation is within the center of multi-agent systems and economics in the last decade due to its industrial and social importance. At a high level, the problem is to assign a set of items that are either goods or chores to a set of agents so that every agent is happy with what she obtains. Particularly, in this survey, we focus on indivisible items, for which absolute fairness such as envy-freeness and proportionality cannot be guaranteed. One main theme in the recent research agenda is about designing algorithms that approximately achieve the fairness criteria. We aim at presenting a comprehensive survey of recent progresses through the prism of algorithms, highlighting the ways to relax fairness notions and common techniques to design algorithms, as well as the most interesting questions for future research.

Fair Allocation of goods and chores -- Tutorial and Survey of Recent Results

2023-01-01
Shaily Mishra , Manisha Padala , Sujit Gujar
Fair resource allocation is an important problem in many real-world scenarios, where resources such as goods and chores must be allocated among agents. In this survey, we delve into the … Fair resource allocation is an important problem in many real-world scenarios, where resources such as goods and chores must be allocated among agents. In this survey, we delve into the intricacies of fair allocation, focusing specifically on the challenges associated with indivisible resources. We define fairness and efficiency within this context and thoroughly survey existential results, algorithms, and approximations that satisfy various fairness criteria, including envyfreeness, proportionality, MMS, and their relaxations. Additionally, we discuss algorithms that achieve fairness and efficiency, such as Pareto Optimality and Utilitarian Welfare. We also study the computational complexity of these algorithms, the likelihood of finding fair allocations, and the price of fairness for each fairness notion. We also cover mixed instances of indivisible and divisible items and investigate different valuation and allocation settings. By summarizing the state-of-the-art research, this survey provides valuable insights into fair resource allocation of indivisible goods and chores, highlighting computational complexities, fairness guarantees, and trade-offs between fairness and efficiency. It serves as a foundation for future advancements in this vital field.
View PDF Chat

Exploring Relations among Fairness Notions in Discrete Fair Division

2025-02-04
Jugal Garg , Eklavya Sharma
Fairly allocating indivisible items among agents is an important and well-studied problem. However, fairness does not have a single universally agreed-upon definition, and so, many different definitions of fairness have … Fairly allocating indivisible items among agents is an important and well-studied problem. However, fairness does not have a single universally agreed-upon definition, and so, many different definitions of fairness have been proposed and studied. Some of these definitions are considered more fair than others, although stronger fairness notions are also more difficult to guarantee. In this work, we study 21 different notions of fairness and arrange them in a hierarchy. Formally, we say that a fairness notion $F_1$ implies another notion $F_2$ if every $F_1$-fair allocation is also an $F_2$-fair allocation. We give a near-complete picture of implications among fairness notions: for almost every pair of notions, we either prove that one notion implies the other, or we give a counterexample, i.e., an allocation that is fair by one notion but not by the other. Although some of these results are well-known, many of them are new. We give results for many different settings: allocating goods, allocating chores, and allocating mixed manna. We believe our work clarifies the relative merits of different fairness notions, and provides a foundation for further research in fair allocation. Moreover, we developed an inference engine to automate part of our work. This inference engine is implemented as a user-friendly web application and is not restricted to fair division scenarios, so it holds potential for broader use.
View PDF Chat

On the Price of Fairness of Allocating Contiguous Blocks

2022-01-01
Ankang Sun , Bo Li
In this work, we revisit the problem of fairly allocating a number of indivisible items that are located on a line to multiple agents. A feasible allocation requires that the … In this work, we revisit the problem of fairly allocating a number of indivisible items that are located on a line to multiple agents. A feasible allocation requires that the allocated items to each agent are connected on the line. The items can be goods on which agents have non-negative utilities, or chores on which the utilities are non-positive. Our objective is to understand the extent to which welfare is inevitably sacrificed by enforcing the allocations to be fair, i.e., price of fairness (PoF). We study both egalitarian and utilitarian welfare. Previous works by Suksompong [Discret. Appl. Math., 2019] and H\"ohne and van Stee [Inf. Comput., 2021] have studied PoF regarding the notions of envy-freeness and proportionality. However, these fair allocations barely exist for indivisible items, and thus in this work, we focus on the relaxations of maximin share fairness and proportionality up to one item, which are guaranteed to be satisfiable. For most settings, we give (almost) tight ratios of PoF and all the upper bounds are proved by designing polynomial time algorithms.

Almost Group Envy-free Allocation of Indivisible Goods and Chores

2019-01-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.
View PDF Chat

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.
View PDF Chat

Allocating Mixed Goods with Customized Fairness and Indivisibility Ratio

2024-07-26
Bo Li , Zihao Li , Shengxin Liu +1 more
We consider the problem of fairly allocating a combination of divisible and indivisible goods. While fairness criteria like envy-freeness (EF) and proportionality (PROP) can always be achieved for divisible goods, … We consider the problem of fairly allocating a combination of divisible and indivisible goods. While fairness criteria like envy-freeness (EF) and proportionality (PROP) can always be achieved for divisible goods, only their relaxed versions, such as the “up to one” relaxations EF1 and PROP1, can be satisfied when the goods are indivisible. The “up to one” relaxations require the fairness conditions to be satisfied provided that one good can be completely eliminated or added in the comparison. In this work, we bridge the gap between the two extremes and propose “up to a fraction” relaxations for the allocation of mixed divisible and indivisible goods. The fraction is determined based on the proportion of indivisible goods, which we call the indivisibility ratio. The new concepts also introduce asymmetric conditions that are customized for individuals with varying indivisibility ratios. We provide both upper and lower bounds on the fractions of the modified item in order to satisfy the fairness criterion. Our results are tight up to a constant for EF and asymptotically tight for PROP.
View PDF Chat

Allocating Mixed Goods with Customized Fairness and Indivisibility Ratio

2024-04-28
Bo Li , Zihao Li , Shengxin Liu +1 more
We consider the problem of fairly allocating a combination of divisible and indivisible goods. While fairness criteria like envy-freeness (EF) and proportionality (PROP) can always be achieved for divisible goods, … We consider the problem of fairly allocating a combination of divisible and indivisible goods. While fairness criteria like envy-freeness (EF) and proportionality (PROP) can always be achieved for divisible goods, only their relaxed versions, such as the ''up to one'' relaxations EF1 and PROP1, can be satisfied when the goods are indivisible. The ''up to one'' relaxations require the fairness conditions to be satisfied provided that one good can be completely eliminated or added in the comparison. In this work, we bridge the gap between the two extremes and propose ''up to a fraction'' relaxations for the allocation of mixed divisible and indivisible goods. The fraction is determined based on the proportion of indivisible goods, which we call the indivisibility ratio. The new concepts also introduce asymmetric conditions that are customized for individuals with varying indivisibility ratios. We provide both upper and lower bounds on the fractions of the modified item in order to satisfy the fairness criterion. Our results are tight up to a constant for EF and asymptotically tight for PROP.
View PDF Chat

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.
View PDF Chat

Equitable Allocations of Indivisible Chores

2020-01-01
Rupert Freeman , Sujoy Sikdar , Rohit Vaish +1 more
We study fair allocation of indivisible chores (i.e., items with non-positive value) among agents with additive valuations. An allocation is deemed fair if it is (approximately) equitable, which means that … We study fair allocation of indivisible chores (i.e., items with non-positive value) among agents with additive valuations. An allocation is deemed fair if it is (approximately) equitable, which means that the disutilities of the agents are (approximately) equal. Our main theoretical contribution is to show that there always exists an allocation that is simultaneously equitable up to one chore (EQ1) and Pareto optimal (PO), and to provide a pseudopolynomial-time algorithm for computing such an allocation. In addition, we observe that the Leximin solution---which is known to satisfy a strong form of approximate equitability in the goods setting---fails to satisfy even EQ1 for chores. It does, however, satisfy a novel fairness notion that we call equitability up to any duplicated chore. Our experiments on synthetic as well as real-world data obtained from the Spliddit website reveal that the algorithms considered in our work satisfy approximate fairness and efficiency properties significantly more often than the algorithm currently deployed on Spliddit.

Fair Division with Allocator's Preference

2023-01-01
Xiaolin Bu , Zihao Li , Shengxin Liu +2 more
We consider the fair allocation problem of indivisible items. Most previous work focuses on fairness and/or efficiency among agents given agents' preferences. However, besides the agents, the allocator as the … We consider the fair allocation problem of indivisible items. Most previous work focuses on fairness and/or efficiency among agents given agents' preferences. However, besides the agents, the allocator as the resource owner may also be involved in many real-world scenarios, e.g., heritage division. The allocator has the inclination to obtain a fair or efficient allocation based on her own preference over the items and to whom each item is allocated. In this paper, we propose a new model and focus on the following two problems: 1) Is it possible to find an allocation that is fair for both the agents and the allocator? 2) What is the complexity of maximizing the allocator's social welfare while satisfying the agents' fairness? We consider the two fundamental fairness criteria: envy-freeness and proportionality. For the first problem, we study the existence of an allocation that is envy-free up to $c$ goods (EF-$c$) or proportional up to $c$ goods (PROP-$c$) from both the agents' and the allocator's perspectives, in which such an allocation is called doubly EF-$c$ or doubly PROP-$c$ respectively. When the allocator's utility depends exclusively on the items (but not to whom an item is allocated), we prove that a doubly EF-$1$ allocation always exists. For the general setting where the allocator has a preference over the items and to whom each item is allocated, we prove that a doubly EF-$1$ allocation always exists for two agents, a doubly PROP-$2$ allocation always exists for binary valuations, and a doubly PROP-$O(\log n)$ allocation always exists in general. For the second problem, we provide various (in)approximability results in which the gaps between approximation and inapproximation ratios are asymptotically closed under most settings. Most results are based on novel technical tools including the chromatic numbers of the Kneser graphs and linear programming-based analysis.

Almost (Weighted) Proportional Allocations for Indivisible Chores

2021-01-01
Bo Li , Yingkai Li , Xiaowei Wu
In this paper, we study how to fairly allocate m indivisible chores to n (asymmetric) agents. We consider (weighted) proportionality up to any item (PROPX) and show that a (weighted) … In this paper, we study how to fairly allocate m indivisible chores to n (asymmetric) agents. We consider (weighted) proportionality up to any item (PROPX) and show that a (weighted) PROPX allocation always exists and can be computed efficiently. For chores, we argue that PROPX might be a more reliable relaxation for proportionality by the facts that any PROPX allocation ensures 2-approximation of maximin share (MMS) fairness [Budish, 2011] for symmetric agents and of anyprice share (APS) fairness [Babaioff et al, 2021] for asymmetric agents. APS allocations for chores have not been studied before the current work, and our result implies a 2-approximation algorithm. Another by-product result is that an EFX and a weighted EF1 allocation for indivisible chores exist if all agents have the same ordinal preference, which might be of independent interest. We then consider the partial information setting and design algorithms that only use agents' ordinal preferences to compute approximately PROPX allocations. Our algorithm achieves a 2-approximation for both symmetric and asymmetric agents, and the approximation ratio is optimal. Finally, we study the price of fairness (PoF), i.e., the loss in social welfare by enforcing allocations to be (weighted) PROPX. We prove that the tight ratio for PoF is Theta(n) for symmetric agents and unbounded for asymmetric agents.
View PDF Chat

Fair Allocation of Indivisible Goods to Asymmetric Agents

2019-01-07
Alireza Farhadi , Mohammad Ghodsi , Mohammad Taghi Hajiaghayi +5 more
We study fair allocation of indivisible goods to agents with unequal entitlements. Fair allocation has been the subject of many studies in both divisible and indivisible settings. Our emphasis is … We study fair allocation of indivisible goods to agents with unequal entitlements. Fair allocation has been the subject of many studies in both divisible and indivisible settings. Our emphasis is on the case where the goods are indivisible and agents have unequal entitlements. This problem is a generalization of the work by Procaccia and Wang (2014) wherein the agents are assumed to be symmetric with respect to their entitlements. Although Procaccia and Wang show an almost fair (constant approximation) allocation exists in their setting, our main result is in sharp contrast to their observation. We show that, in some cases with n agents, no allocation can guarantee better than 1/n approximation of a fair allocation when the entitlements are not necessarily equal. Furthermore, we devise a simple algorithm that ensures a 1/n approximation guarantee.
 Our second result is for a restricted version of the problem where the valuation of every agent for each good is bounded by the total value he wishes to receive in a fair allocation. Although this assumption might seem without loss of generality, we show it enables us to find a 1/2 approximation fair allocation via a greedy algorithm. Finally, we run some experiments on real-world data and show that, in practice, a fair allocation is likely to exist. We also support our experiments by showing positive results for two stochastic variants of the problem, namely stochastic agents and stochastic items.
View PDF Chat

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.
View PDF Chat