Almost envy-freeness with general valuations

Authors

Benjamin Plaut, Tim Roughgarden

Type: Article

Publication Date: 2018-01-07

Citations: 65

View

Abstract

The goal of division is to distribute resources among competing players in a fair way. Envy-freeness is the most extensively studied fairness notion in division. Envy-free allocations do not always exist with indivisible goods, motivating the study of relaxed versions of envy-freeness. We study the envy-freeness up to any good (EFX) property, which states that no player prefers the bundle of another player following the removal of any single good, and prove the first general results about this property. We use the leximin solution to show existence of EFX allocations in several contexts, sometimes in conjunction with Pareto optimality. For two players with valuations obeying a mild assumption, one of these results provides stronger guarantees than the currently deployed algorithm on Spliddit, a popular division website. Unfortunately, finding the leximin solution can require exponential time. We show that this is necessary by proving an exponential lower bound on the number of value queries needed to identify an EFX allocation, even for two players with identical valuations. We consider both additive and more general valuations, and our work suggests that there is a rich landscape of problems to explore in the division of indivisible goods with different classes of player valuations.

Locations

arXiv (Cornell University)
View

Almost Envy-Freeness with General Valuations

2017-07-15

Benjamin Plaut , Tim Roughgarden

The goal of division is to distribute resources among competing players in a fair way. Envy-freeness is the most extensively studied fairness notion in division. Envy-free allocations do not always … The goal of division is to distribute resources among competing players in a fair way. Envy-freeness is the most extensively studied fairness notion in division. Envy-free allocations do not always exist with indivisible goods, motivating the study of relaxed versions of envy-freeness. We study the envy-freeness up to any good (EFX) property, which states that no player prefers the bundle of another player following the removal of any single good, and prove the first general results about this property. We use the leximin solution to show existence of EFX allocations in several contexts, sometimes in conjunction with Pareto optimality. For two players with valuations obeying a mild assumption, one of these results provides stronger guarantees than the currently deployed algorithm on Spliddit, a popular division website. Unfortunately, finding the leximin solution can require exponential time. We show that this is necessary by proving an exponential lower bound on the number of value queries needed to identify an EFX allocation, even for two players with identical valuations. We consider both additive and more general valuations, and our work suggests that there is a rich landscape of problems to explore in the division of indivisible goods with different classes of player valuations.

Almost Envy-Freeness with General Valuations

2020-01-01

Benjamin Plaut , Tim Roughgarden

The goal of fair division is to distribute resources among competing players in a “fair" way. Envy-freeness is the most extensively studied fairness notion in fair division. Envy-free allocations do … The goal of fair division is to distribute resources among competing players in a “fair" way. Envy-freeness is the most extensively studied fairness notion in fair division. Envy-free allocations do not always exist with indivisible goods, motivating the study of relaxed versions of envy-freeness. We study the envy-freeness up to any good (EFX) property, which states that no player prefers the bundle of another player following the removal of any single good, and prove the first general results about this property. We use the leximin solution to show existence of EFX allocations in several contexts, sometimes in conjunction with Pareto optimality. For two players with valuations obeying a mild assumption, one of these results provides stronger guarantees than the currently deployed algorithm on Spliddit, a popular fair division website. Unfortunately, finding the leximin solution can require exponential time. We show that this is necessary by proving an exponential lower bound on the number of value queries needed to identify an EFX allocation, even for two players with identical valuations. We consider both additive and more general valuations, and our work suggests that there is a rich landscape of problems to explore in the fair division of indivisible goods with different classes of player valuations.

View PDF Chat

Almost Envy-Freeness with General Valuations

2018-01-01

Benjamin Plaut , Tim Roughgarde

The goal of fair division is to distribute resources among competing players in a “fair” way. Envy-freeness is the most extensively studied fairness notion in fair division. Envy-free allocations do … The goal of fair division is to distribute resources among competing players in a “fair” way. Envy-freeness is the most extensively studied fairness notion in fair division. Envy-free allocations do not always exist with indivisible goods, motivating the study of relaxed versions of envy-freeness. We study the envy-freeness up to any good (EFX) property, which states that no player prefers the bundle of another player following the removal of any single good, and prove the first general results about this property. We use the leximin solution to show existence of EFX allocations in several contexts, sometimes in conjunction with Pareto optimality. For two players with valuations obeying a mild assumption, one of these results provides stronger guarantees than the currently deployed algorithm on Spliddit, a popular fair division website. Unfortunately, finding the leximin solution can require exponential time. We show that this is necessary by proving an exponential lower bound on the number of value queries needed to identify an EFX allocation, even for two players with identical valuations. We consider both additive and more general valuations, and our work suggests that there is a rich landscape of problems to explore in the fair division of indivisible goods with different classes of player valuations.

View PDF Chat

Almost Envy-Freeness with General Valuations

2017-01-01

Benjamin Plaut , Tim Roughgarden

The goal of fair division is to distribute resources among competing players in a "fair" way. Envy-freeness is the most extensively studied fairness notion in fair division. Envy-free allocations do … The goal of fair division is to distribute resources among competing players in a "fair" way. Envy-freeness is the most extensively studied fairness notion in fair division. Envy-free allocations do not always exist with indivisible goods, motivating the study of relaxed versions of envy-freeness. We study the envy-freeness up to any good (EFX) property, which states that no player prefers the bundle of another player following the removal of any single good, and prove the first general results about this property. We use the leximin solution to show existence of EFX allocations in several contexts, sometimes in conjunction with Pareto optimality. For two players with valuations obeying a mild assumption, one of these results provides stronger guarantees than the currently deployed algorithm on Spliddit, a popular fair division website. Unfortunately, finding the leximin solution can require exponential time. We show that this is necessary by proving an exponential lower bound on the number of value queries needed to identify an EFX allocation, even for two players with identical valuations. We consider both additive and more general valuations, and our work suggests that there is a rich landscape of problems to explore in the fair division of indivisible goods with different classes of player valuations.

View PDF Chat

Envy-freeness up to any item with high Nash welfare: The virtue of donating items

2019-02-12

Ioannis Caragiannis , Nick Gravin , Xin Huang

Several fairness concepts have been proposed recently in attempts to approximate envy-freeness in settings with indivisible goods. Among them, the concept of envy-freeness up to any item (EFX) is arguably … Several fairness concepts have been proposed recently in attempts to approximate envy-freeness in settings with indivisible goods. Among them, the concept of envy-freeness up to any item (EFX) is arguably the closest to envy-freeness. Unfortunately, EFX allocations are not known to exist except in a few special cases. We make significant progress in this direction. We show that for every instance with additive valuations, there is an EFX allocation of a subset of items with a Nash welfare that is at least half of the maximum possible Nash welfare for the original set of items. That is, after donating some items to a charity, one can distribute the remaining items in a fair way with high efficiency. This bound is proved to be best possible. Our proof is constructive and highlights the importance of maximum Nash welfare allocation. Starting with such an allocation, our algorithm decides which items to donate and redistributes the initial bundles to the agents, eventually obtaining an allocation with the claimed efficiency guarantee. The application of our algorithm to large markets, where the valuations of an agent for every item is relatively small, yields EFX with almost optimal Nash welfare. To the best of our knowledge, this is the first use of large market assumptions in the fair division literature. We also show that our algorithm can be modified to compute, in polynomial-time, EFX allocations that approximate optimal Nash welfare within a factor of at most $2\rho$, using a $\rho$-approximate allocation on input instead of the maximum Nash welfare one.

Envy-freeness up to any item with high Nash welfare: The virtue of donating items

2019-01-01

Ioannis Caragiannis , Nick Gravin , Xin Huang

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.

Average Envy-freeness for Indivisible Items

2023-01-01

Qishen Han , Biaoshuai Tao , Lirong Xia

In fair division applications, agents may have unequal entitlements reflecting their different contributions. Moreover, the contributions of agents may depend on the allocation itself. Previous fairness notions designed for agents … In fair division applications, agents may have unequal entitlements reflecting their different contributions. Moreover, the contributions of agents may depend on the allocation itself. Previous fairness notions designed for agents with equal or pre-determined entitlement fail to characterize fairness in these collaborative allocation scenarios. We propose a novel fairness notion of average envy-freeness (AEF), where the envy of agents is defined on the average value of items in the bundles. Average envy-freeness provides a reasonable comparison between agents based on the items they receive and reflects their entitlements. We study the complexity of finding AEF and its relaxation, average envy-freeness up to one item (AEF-1). While deciding if an AEF allocation exists is NP-complete, an AEF-1 allocation is guaranteed to exist and can be computed in polynomial time. We also study allocation with quotas, i.e. restrictions on the sizes of bundles. We prove that finding AEF-1 allocation satisfying a quota is NP-hard. Nevertheless, in the instances with a fixed number of agents, we propose polynomial-time algorithms to find AEF-1 allocation with a quota for binary valuation and approximated AEF-1 allocation with a quota for general valuation.

Fair Division through Information Withholding

2019-01-01

Hadi Hosseini , Sujoy Sikdar , Rohit Vaish +2 more

Envy-freeness up to one good (EF1) is a well-studied fairness notion for indivisible goods that addresses pairwise envy by the removal of at most one good. In the worst case, … Envy-freeness up to one good (EF1) is a well-studied fairness notion for indivisible goods that addresses pairwise envy by the removal of at most one good. In the worst case, each pair of agents might require the (hypothetical) removal of a different good, resulting in a weak aggregate guarantee. We study allocations that are nearly envy-free in aggregate, and define a novel fairness notion based on information withholding. Under this notion, an agent can withhold (or hide) some of the goods in its bundle and reveal the remaining goods to the other agents. We observe that in practice, envy-freeness can be achieved by withholding only a small number of goods overall. We show that finding allocations that withhold an optimal number of goods is computationally hard even for highly restricted classes of valuations. In contrast to the worst-case results, our experiments on synthetic and real-world preference data show that existing algorithms for finding EF1 allocations withhold close-to-optimal number of goods.

View PDF Chat

Fair Division Through Information Withholding

2020-04-03

Hadi Hosseini , Sujoy Sikdar , Rohit Vaish +2 more

View PDF Chat

Fair Division of Mixed Divisible and Indivisible Goods

2020-04-03

Xiaohui Bei , Zihao Li , Jinyan Liu +2 more

We study the problem of fair division when the resources contain both divisible and indivisible goods. Classic fairness notions such as envy-freeness (EF) and envy-freeness up to one good (EF1) … We study the problem of fair division when the resources contain both divisible and indivisible goods. Classic fairness notions such as envy-freeness (EF) and envy-freeness up to one good (EF1) cannot be directly applied to the mixed goods setting. In this work, we propose a new fairness notion envy-freeness for mixed goods (EFM), which is a direct generalization of both EF and EF1 to the mixed goods setting. We prove that an EFM allocation always exists for any number of agents. We also propose efficient algorithms to compute an EFM allocation for two agents and for n agents with piecewise linear valuations over the divisible goods. Finally, we relax the envy-free requirement, instead asking for ϵ-envy-freeness for mixed goods (ϵ-EFM), and present an algorithm that finds an ϵ-EFM allocation in time polynomial in the number of agents, the number of indivisible goods, and 1/ϵ.

View PDF Chat

Computing Efficient Envy-Free Partial Allocations of Indivisible Goods

2025-02-18

Robert Bredereck , Andrzej Kaczmarczyk , Junjie Luo +1 more

Envy-freeness is one of the most prominent fairness concepts in the allocation of indivisible goods. Even though trivial envy-free allocations always exist, rich literature shows this is not true when … Envy-freeness is one of the most prominent fairness concepts in the allocation of indivisible goods. Even though trivial envy-free allocations always exist, rich literature shows this is not true when one additionally requires some efficiency concept (e.g., completeness, Pareto-efficiency, or social welfare maximization). In fact, in such case even deciding the existence of an efficient envy-free allocation is notoriously computationally hard. In this paper, we explore the limits of efficient computability by relaxing standard efficiency concepts and analyzing how this impacts the computational complexity of the respective problems. Specifically, we allow partial allocations (where not all goods are allocated) and impose only very mild efficiency constraints, such as ensuring each agent receives a bundle with positive utility. Surprisingly, even such seemingly weak efficiency requirements lead to a diverse computational complexity landscape. We identify several polynomial-time solvable or fixed-parameter tractable cases for binary utilities, yet we also find NP-hardness in very restricted scenarios involving ternary utilities.

View PDF Chat

Weighted Envy-freeness in Indivisible Item Allocation

2021-08-16

Mithun Chakraborty , Ayumi Igarashi , Warut Suksompong +1 more

We introduce and analyze new envy-based fairness concepts for agents with weights that quantify their entitlements in the allocation of indivisible items. We propose two variants of weighted envy-freeness up … We introduce and analyze new envy-based fairness concepts for agents with weights that quantify their entitlements in the allocation of indivisible items. We propose two variants of weighted envy-freeness up to one item (WEF1): strong , where envy can be eliminated by removing an item from the envied agent’s bundle, and weak , where envy can be eliminated either by removing an item (as in the strong version) or by replicating an item from the envied agent’s bundle in the envying agent’s bundle. We show that for additive valuations, an allocation that is both Pareto optimal and strongly WEF1 always exists and can be computed in pseudo-polynomial time; moreover, an allocation that maximizes the weighted Nash social welfare may not be strongly WEF1, but it always satisfies the weak version of the property. Moreover, we establish that a generalization of the round-robin picking sequence algorithm produces in polynomial time a strongly WEF1 allocation for an arbitrary number of agents; for two agents, we can efficiently achieve both strong WEF1 and Pareto optimality by adapting the adjusted winner procedure. Our work highlights several aspects in which weighted fair division is richer and more challenging than its unweighted counterpart.

View PDF Chat

The Complexity of Fair Division of Indivisible Items with Externalities

2024-03-24

Argyrios Deligkas , Eduard Eiben , Viktoriia Korchemna +1 more

We study the computational complexity of fairly allocating a set of indivisible items under externalities. In this recently-proposed setting, in addition to the utility the agent gets from their bundle, … We study the computational complexity of fairly allocating a set of indivisible items under externalities. In this recently-proposed setting, in addition to the utility the agent gets from their bundle, they also receive utility from items allocated to other agents. We focus on the extended definitions of envy-freeness up to one item (EF1) and of envy-freeness up to any item (EFX), and we provide the landscape of their complexity for several different scenarios. We prove that it is NP-complete to decide whether there exists an EFX allocation, even when there are only three agents, or even when there are only six different values for the items. We complement these negative results by showing that when both the number of agents and the number of different values for items are bounded by a parameter the problem becomes fixed-parameter tractable. Furthermore, we prove that two-valued and binary-valued instances are equivalent and that EFX and EF1 allocations coincide for this class of instances. Finally, motivated from real-life scenarios, we focus on a class of structured valuation functions, which we term agent/item-correlated. We prove their equivalence to the "standard" setting without externalities. Therefore, all previous results for EF1 and EFX apply immediately for these valuations.

View PDF Chat

Weighted Envy-Freeness in Indivisible Item Allocation.

2019-09-23

Mithun Chakraborty , Ayumi Igarashi , Warut Suksompong +1 more

We introduce and analyze new envy-based fairness concepts for agents with weights that quantify their entitlements in the allocation of indivisible items. We propose two variants of weighted envy-freeness up … We introduce and analyze new envy-based fairness concepts for agents with weights that quantify their entitlements in the allocation of indivisible items. We propose two variants of weighted envy-freeness up to one item (WEF1): strong, where envy can be eliminated by removing an item from the envied agent's bundle, and weak, where envy can be eliminated either by removing an item (as in the strong version) or by replicating an item from the envied agent's bundle in the envying agent's bundle. We show that for additive valuations, an allocation that is both Pareto optimal and strongly WEF1 always exists and can be computed in pseudo-polynomial time; moreover, an allocation that maximizes the weighted Nash social welfare may not be strongly WEF1, but always satisfies the weak version of the property. Moreover, we establish that a generalization of the round-robin picking sequence algorithm produces in polynomial time a strongly WEF1 allocation for an arbitrary number of agents; for two agents, we can efficiently achieve both strong WEF1 and Pareto optimality by adapting the adjusted winner procedure. Our work highlights several aspects in which weighted fair division is richer and more challenging than its unweighted counterpart.

Fair Division Beyond Monotone Valuations

2025-01-24

Siddharth Barman , Paritosh Verma

This paper studies the problem of fairly dividing resources -- a cake or indivisible items -- amongst a set of agents with heterogeneous preferences. This problem has been extensively studied … This paper studies the problem of fairly dividing resources -- a cake or indivisible items -- amongst a set of agents with heterogeneous preferences. This problem has been extensively studied in the literature, however, a majority of the existing work has focused on settings wherein the agents' preferenes are monotone, i.e., increasing the quantity of resource doesn't decrease an agent's value for it. Despite this, the study of non-monotone preferences is as motivated as the study of monotone preferences. We focus on fair division beyond monotone valuations. We prove the existence of fair allocations, develop efficient algorithms to compute them, and prove lower bounds on the number of such fair allocations. For the case of indivisible items, we show that EF3 and EQ3 allocations always exist as long as the valuations of all agents are nonnegative. While nonnegativity suffices, we show that it's not required: EF3 allocations exist even if the valuations are (possibly negative) subadditive functions that satisfy a mild condition. In route to obtaining these results, we establish the existence of envy-free cake divisions for burnt cakes when the valuations are subadditive and the entire cake has a nonnegative value. This is in stark contrast to the well-known nonexistence of envy-free allocations for burnt cakes. In addition to the existence results, we develop an FPTAS for computing equitable cake divisions for nonnegative valuations. For indivisible items, we give an efficient algorithm to compute nearly equitable allocations which works when the valuations are nonnegative, or when they are subadditive subject to a mild condition. This result has implications beyond fair division, e.g., in facility, graph partitioning, among others. Finally, we show that such fair allocations are plenty in number, and increase exponentially (polynomially) in the number of agents (items).

View PDF Chat

Best of Both Worlds: Agents with Entitlements

2022-01-01

Martin Hoefer , Marco Schmalhofer , Giovanna Varricchio

Fair division of indivisible goods is a central challenge in artificial intelligence. For many prominent fairness criteria including envy-freeness (EF) or proportionality (PROP), no allocations satisfying these criteria might exist. … Fair division of indivisible goods is a central challenge in artificial intelligence. For many prominent fairness criteria including envy-freeness (EF) or proportionality (PROP), no allocations satisfying these criteria might exist. Two popular remedies to this problem are randomization or relaxation of fairness concepts. A timely research direction is to combine the advantages of both, commonly referred to as Best of Both Worlds (BoBW). We consider fair division with entitlements, which allows to adjust notions of fairness to heterogeneous priorities among agents. This is an important generalization to standard fair division models and is not well-understood in terms of BoBW results. Our main result is a lottery for additive valuations and different entitlements that is ex-ante weighted envy-free (WEF), as well as ex-post weighted proportional up to one good (WPROP1) and weighted transfer envy-free up to one good (WEF(1,1)). It can be computed in strongly polynomial time. We show that this result is tight - ex-ante WEF is incompatible with any stronger ex-post WEF relaxation. In addition, we extend BoBW results on group fairness to entitlements and explore generalizations of our results to instances with more expressive valuation functions.

View PDF Chat

Almost Envy-free Allocation of Indivisible Goods: A Tale of Two Valuations

2024-07-06

Alireza Kaviani , Masoud Seddighin , AmirMohammad Shahrezaei

The existence of $\textsf{EFX}$ allocations stands as one of the main challenges in discrete fair division. In this paper, we present a collection of symmetrical results on the existence of … The existence of $\textsf{EFX}$ allocations stands as one of the main challenges in discrete fair division. In this paper, we present a collection of symmetrical results on the existence of $\textsf{EFX}$ notion and its approximate variations. These results pertain to two seemingly distinct valuation settings: the restricted additive valuations and $(p,q)$-bounded valuations recently introduced by Christodoulou \textit{et al.} \cite{christodoulou2023fair}. In a $(p,q)$-bonuded instance, each good holds relevance (i.e., has a non-zero marginal value) for at most $p$ agents, and any pair of agents share at most $q$ common relevant goods. The only known guarantees on $(p,q)$-bounded valuations is that $(2,1)$-bounded instances always admit $\textsf{EFX}$ allocations (EC'22) \cite{christodoulou2023fair}. Here we show that instances with $(\infty,1)$-bounded valuations always admit $\textsf{EF2X}$ allocations, and $\textsf{EFX}$ allocations with at most $\lfloor {n}/{2} \rfloor - 1$ discarded goods. These results mirror the existing results for the restricted additive setting \cite{akrami2023efx}. Moreover, we present $({\sqrt{2}}/{2})-\textsf{EFX}$ allocation algorithms for both the restricted additive and $(\infty,1)$-bounded settings. The symmetry of these results suggests that these valuations exhibit symmetric structures. Building on this observation, we conjectured that the $(2,\infty)$-bounded and restricted additive setting might admit $\textsf{EFX}$ guarantee. Intriguingly, our investigation confirms this conjecture. We propose a rather complex $\textsf{EFX}$ allocation algorithm for restricted additive valuations when $p=2$ and $q=\infty$.

View PDF Chat

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

Fair division of indivisible goods: Recent progress and open questions

2023-06-16

Georgios Amanatidis , Haris Aziz , Georgios Birmpas +5 more

Allocating resources to individuals in a fair manner has been a topic of interest since ancient times, with most of the early mathematical work on the problem focusing on resources … Allocating resources to individuals in a fair manner has been a topic of interest since ancient times, with most of the early mathematical work on the problem focusing on resources that are infinitely divisible. Over the last decade, there has been a surge of papers studying computational questions regarding the indivisible case, for which exact fairness notions such as envy-freeness and proportionality are hard to satisfy. One main theme in the recent research agenda is to investigate the extent to which their relaxations, like maximin share fairness (MMS) and envy-freeness up to any good (EFX), can be achieved. In this survey, we present a comprehensive review of the recent progress made in the related literature by highlighting different ways to relax fairness notions, common algorithm design techniques, and the most interesting questions for future research.

View PDF Chat

Maximum Nash welfare and other stories about EFX

2021-02-09

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

View PDF Chat

Almost envy-freeness in group resource allocation

2020-07-15

Maria Kyropoulou , Warut Suksompong , Alexandros A. Voudouris

View PDF Chat

Efficient Fair Division with Minimal Sharing

2022-05-01

Fedor Sandomirskiy , Erel Segal-Halevi

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

View PDF Chat

Greedy Algorithms for Maximizing Nash Social Welfare

2018-01-27

Siddharth Barman , Sanath Kumar Krishnamurthy , Rohit Vaish

We study the problem of fairly allocating a set of indivisible goods among agents with additive valuations. The extent of fairness of an allocation is measured by its Nash social … We study the problem of fairly allocating a set of indivisible goods among agents with additive valuations. The extent of fairness of an allocation is measured by its Nash social welfare, which is the geometric mean of the valuations of the agents for their bundles. While the problem of maximizing Nash social welfare is known to be APX-hard in general, we study the effectiveness of simple, greedy algorithms in solving this problem in two interesting special cases. First, we show that a simple, greedy algorithm provides a 1.061-approximation guarantee when agents have identical valuations, even though the problem of maximizing Nash social welfare remains NP-hard for this setting. Second, we show that when agents have binary valuations over the goods, an exact solution (i.e., a Nash optimal allocation) can be found in polynomial time via a greedy algorithm. Our results in the binary setting extend to provide novel, exact algorithms for optimizing Nash social welfare under concave valuations. Notably, for the above mentioned scenarios, our techniques provide a simple alternative to several of the existing, more sophisticated techniques for this problem such as constructing equilibria of Fisher markets or using real stable polynomials.

Algorithms for Competitive Division of Chores

2019-07-03

Simina Brânzei , Fedor Sandomirskiy

We study the problem of allocating divisible bads (chores) among multiple agents with additive utilities, when money transfers are not allowed. The competitive rule is known to be the best … We study the problem of allocating divisible bads (chores) among multiple agents with additive utilities, when money transfers are not allowed. The competitive rule is known to be the best mechanism for goods with additive utilities and was recently extended to chores by Bogomolnaia et al (2017). For both goods and chores, the rule produces Pareto optimal and envy-free allocations. In the case of goods, the outcome of the competitive rule can be easily computed. Competitive allocations solve the Eisenberg-Gale convex program; hence the outcome is unique and can be approximately found by standard gradient methods. An exact algorithm that runs in polynomial time in the number of agents and goods was given by Orlin. In the case of chores, the competitive rule does not solve any convex optimization problem; instead, competitive allocations correspond to local minima, local maxima, and saddle points of the Nash Social Welfare on the Pareto frontier of the set of feasible utilities. The rule becomes multivalued and none of the standard methods can be applied to compute its outcome. In this paper, we show that all the outcomes of the competitive rule for chores can be computed in strongly polynomial time if either the number of agents or the number of chores is fixed. The approach is based on a combination of three ideas: all consumption graphs of Pareto optimal allocations can be listed in polynomial time; for a given consumption graph, a candidate for a competitive allocation can be constructed via explicit formula; and a given allocation can be checked for being competitive using a maximum flow computation as in Devanur et al (2002). Our algorithm immediately gives an approximately-fair allocation of indivisible chores by the rounding technique of Barman and Krishnamurthy (2018).

Comparing Approximate Relaxations of Envy-Freeness

2018-06-08

Georgios Amanatidis , Georgios Birmpas , Evangelos Markakis

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

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

2020-07-16

Georgios Amanatidis , Evangelos Markakis , Apostolos Ntokos

View PDF Chat

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.

Finding Fair and Efficient Allocations When Valuations Don’t Add Up

2020-01-01

Nawal Benabbou , Mithun Chakraborty , Ayumi Igarashi +1 more

View PDF Chat

Equitable Allocations of Indivisible Goods

2019-01-01

Rupert Freeman , Sujoy Sikdar , Rohit Vaish +1 more

In fair division, equitability dictates that each participant receives the same level of utility. In this work, we study equitable allocations of indivisible goods among agents with additive valuations. While … In fair division, equitability dictates that each participant receives the same level of utility. In this work, we study equitable allocations of indivisible goods among agents with additive valuations. While prior work has studied (approximate) equitability in isolation, we consider equitability in conjunction with other well-studied notions of fairness and economic efficiency. We show that the Leximin algorithm produces an allocation that satisfies equitability up to any good and Pareto optimality. We also give a novel algorithm that guarantees Pareto optimality and equitability up to one good in pseudopolynomial time. Our experiments on real-world preference data reveal that approximate envy-freeness, approximate equitability, and Pareto optimality can often be achieved simultaneously.

View PDF Chat

On the number of almost envy-free allocations

2020-04-07

Warut Suksompong

View PDF Chat

Almost Envy Freeness and Welfare Efficiency in Fair Division with Goods or Bads

2018-01-01

Martin Aleksandrov

We consider two models of fair division with indivisible items: one for goods and one for bads. For goods, we study two generalized envy freeness proxies (EF1 and EFX for … We consider two models of fair division with indivisible items: one for goods and one for bads. For goods, we study two generalized envy freeness proxies (EF1 and EFX for goods) and three common welfare (utilitarian, egalitarian and Nash) efficiency notions. For bads, we study two generalized envy freeness proxies (1EF and XEF for goods) and two less common diswelfare (egalitarian and Nash) efficiency notions. Some existing algorithms for goods do not work for bads. We thus propose several new algorithms for the model with bads. Our new algorithms exhibit many nice properties. For example, with additive identical valuations, an allocation that maximizes the egalitarian diswelfare or Nash diswelfare is XEF and PE. Finally, we also give simple and tractable cases when these envy freeness proxies and welfare efficiency are attainable in combination (e.g. binary valuations, house allocations).

Fair allocation of combinations of indivisible goods and chores

2018-01-01

Haris Aziz , Ioannis Caragiannis , Ayumi Igarashi

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

Maximin-Aware Allocations of Indivisible Goods

2019-01-01

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 subadditive valuations, which improves the algorithm in [Plaut and Roughgarden, SODA 2018].

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

Protecting the Protected Group: Circumventing Harmful Fairness

2021-05-18

Omer Ben-Porat , Fedor Sandomirskiy , Moshe Tennenholtz

The recent literature on fair Machine Learning manifests that the choice of fairness constraints must be driven by the utilities of the population. However, virtually all previous work makes the … The recent literature on fair Machine Learning manifests that the choice of fairness constraints must be driven by the utilities of the population. However, virtually all previous work makes the unrealistic assumption that the exact underlying utilities of the population (representing private tastes of individuals) are known to the regulator that imposes the fairness constraint. In this paper we initiate the discussion of the \emph{mismatch}, the unavoidable difference between the underlying utilities of the population and the utilities assumed by the regulator. We demonstrate that the mismatch can make the disadvantaged protected group worse off after imposing the fairness constraint and provide tools to design fairness constraints that help the disadvantaged group despite the mismatch.

View PDF Chat

Monotone and Online Fair Division

2020-06-29

Martin Aleksandrov , Toby Walsh

We study a new but simple model for online fair division in which indivisible items arrive one-by-one and agents have monotone utilities over bundles of the items. We consider axiomatic … We study a new but simple model for online fair division in which indivisible items arrive one-by-one and agents have monotone utilities over bundles of the items. We consider axiomatic properties of mechanisms for this model such as strategy-proofness, envy-freeness, and Pareto efficiency. We prove a number of impossibility results that justify why we consider relaxations of the properties, as well as why we consider restricted preference domains on which good axiomatic properties can be achieved. We propose two mechanisms that have good axiomatic fairness properties on restricted but common preference domains.

Two Algorithms for Additive and Fair Division of Mixed Manna

2020-07-08

Martin Aleksandrov , Toby Walsh

We consider a fair division model in which agents have positive, zero and negative utilities for items. For this model, we analyse one existing fairness property - EFX - and … We consider a fair division model in which agents have positive, zero and negative utilities for items. For this model, we analyse one existing fairness property - EFX - and three new and related properties - EFX$_0$, EFX$^3$ and EF1$^3$ - in combination with Pareto-optimality. With general utilities, we give a modified version of an existing algorithm for computing an EF1$^3$ allocation. With $-\alpha/0/\alpha$ utilities, this algorithm returns an EFX$^3$ and PO allocation. With absolute identical utilities, we give a new algorithm for an EFX and PO allocation. With $-\alpha/0/\beta$ utilities, this algorithm also returns such an allocation. We report some new impossibility results as well.

Greedy Algorithms for Fair Division of Mixed Manna.

2019-11-25

Martin Aleksandrov , Toby Walsh

We consider a multi-agent model for fair division of mixed manna (i.e. items for which agents can have positive, zero or negative utilities), in which agents have additive utilities for … We consider a multi-agent model for fair division of mixed manna (i.e. items for which agents can have positive, zero or negative utilities), in which agents have additive utilities for bundles of items. For this model, we give several general impossibility results and special possibility results for three common fairness concepts (i.e. EF1, EFX, EFX3) and one popular efficiency concept (i.e. PO). We also study how these interact with common welfare objectives such as the Nash, disutility Nash and egalitarian welfares. For example, we show that maximizing the Nash welfare with mixed manna (or minimizing the disutility Nash welfare) does not ensure an EF1 allocation whereas with goods and the Nash welfare it does. We also prove that an EFX3 allocation may not exist even with identical utilities. By comparison, with tertiary utilities, EFX and PO allocations, or EFX3 and PO allocations always exist. Also, with identical utilities, EFX and PO allocations always exist. For these cases, we give polynomial-time algorithms, returning such allocations and approximating further the Nash, disutility Nash and egalitarian welfares in special cases.

Fair and Truthful Mechanisms for Dichotomous Valuations

2020-02-25

Moshe Babaioff , Tomer Ezra , Uriel Feige

We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, … We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, in which the added value of any item to a set is either 0 or 1, and aim to design truthful allocation mechanisms (without money) that maximize welfare and are fair. For the case that players have submodular valuations with dichotomous marginals, we design such a deterministic truthful allocation mechanism. The allocation output by our mechanism is Lorenz dominating, and consequently satisfies many desired fairness properties, such as being envy-free up to any item (EFX), and maximizing the Nash Social Welfare (NSW). We then show that our mechanism with random priorities is envy-free ex-ante, while having all the above properties ex-post. Furthermore, we present several impossibility results precluding similar results for the larger class of XOS valuations. To gauge the robustness of our positive results, we also study $\epsilon$-dichotomous valuations, in which the added value of any item to a set is either non-positive, or in the range $[1, 1 + \epsilon]$. We show several impossibility results in this setting, and also a positive result: for players that have additive $\epsilon$-dichotomous valuations with sufficiently small $\epsilon$, we design a randomized truthful mechanism with strong ex-post guarantees. For $\rho = \frac{1}{1 + \epsilon}$, the allocations that it produces generate at least a $\rho$-fraction of the maximum welfare, and enjoy $\rho$-approximations for various fairness properties, such as being envy-free up to one item (EF1), and giving each player at least her maximin share.

Almost Envy-Free Repeated Matching in Two-Sided Markets

2020-01-01

Sreenivas Gollapudi , Kostas Kollias , Benjamin Plaut

View PDF Chat

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.

View PDF Chat

Two Algorithms for Additive and Fair Division of Mixed Manna

2020-01-01

Martin Aleksandrov , Toby Walsh

View PDF Chat

Envy-freeness up to one item: Shall we add or remove resources?

2020-01-01

Martin Aleksandrov

We consider a fair division model in which agents have general valuations for bundles of indivisible items. We propose two new axiomatic properties for allocations in this model: EF1+- and … We consider a fair division model in which agents have general valuations for bundles of indivisible items. We propose two new axiomatic properties for allocations in this model: EF1+- and EFX+-. We compare these with the existing EF1 and EFX. Although EF1 and EF1+- allocations often exist, our results assert eloquently that EFX+- and PO allocations exist in each case where EFX and PO allocations do not exist. Additionally, we prove several new impossibility and incompatibility results.

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

2020-01-01

Rucha Kulkarni , Ruta Mehta , Setareh Taki

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

View PDF Chat

Fair Division with Binary Valuations: One Rule to Rule Them All

2020-01-01

Daniel Halpern , Ariel D. Procaccia , Alexandros Psomas +1 more

View PDF Chat

High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming

2023-09-28

Robert Bredereck , Andrzej Kaczmarczyk , Dušan Knop +1 more

Using insights from parametric integer linear programming, we improve the work of Bredereck et al. [Proc. ACM EC 2019] on high-multiplicity fair allocation. Answering an open question from their work, … Using insights from parametric integer linear programming, we improve the work of Bredereck et al. [Proc. ACM EC 2019] on high-multiplicity fair allocation. Answering an open question from their work, we proved that the problem of finding envy-free Pareto-efficient allocations of indivisible items is fixed-parameter tractable with respect to the combined parameter “number of agents” plus “number of item types.” Our central improvement, compared to their result, is to break the condition that the corresponding utility and multiplicity values have to be encoded in unary, which is required there. Concretely, we show that, while preserving fixed-parameter tractability, these values can be encoded in binary. Thus, we substantially expand the range of feasible utility and multiplicity values.

View PDF Chat

Almost Envy-free Repeated Matching in Two-sided Markets.

2020-09-20

Sreenivas Gollapudi , Kostas Kollias , Benjamin Plaut

A two-sided market consists of two sets of agents, each of whom have preferences over the other (Airbnb, Upwork, Lyft, Uber, etc.). We propose and analyze a repeated matching problem, … A two-sided market consists of two sets of agents, each of whom have preferences over the other (Airbnb, Upwork, Lyft, Uber, etc.). We propose and analyze a repeated matching problem, where some set of matches occur on each time step, and our goal is to ensure fairness with respect to the cumulative allocations over an infinite time horizon. Our main result is a polynomial-time algorithm for additive, symmetric (v_i(j) = v_j(i)), and binary (v_i(j) \in \{a,1\}) valuations that both (1) guarantees up to a single match (EF1) and (2) selects a maximum weight matching on each time step. Thus for this class of fairness can be achieved without sacrificing economic efficiency. This result holds even for valuations, i.e., valuations that change over time. Although symmetry is a strong assumption, we show that this result cannot be extended to asymmetric binary valuations: (1) and (2) together are impossible even when valuations do not change over time, and for dynamic even (1) alone is impossible. To our knowledge, this is the first analysis of envy-freeness in a repeated matching setting.

Fair Division of Indivisible Goods Among Strategic Agents

2019-01-01

Siddharth Barman , Ganesh Ghalme , Shweta Jain +2 more

We study fair division of indivisible goods in a single-parameter environment. In particular, we develop truthful social welfare maximizing mechanisms for fairly allocating indivisible goods. Our fairness guarantees are in … We study fair division of indivisible goods in a single-parameter environment. In particular, we develop truthful social welfare maximizing mechanisms for fairly allocating indivisible goods. Our fairness guarantees are in terms of solution concepts which are tailored to address allocation of indivisible goods and, hence, provide an appropriate framework for fair division of goods. This work specifically considers fairness in terms of envy freeness up to one good (EF1), maximin share guarantee (MMS), and Nash social welfare (NSW). Our first result shows that (in a single-parameter environment) the problem of maximizing welfare, subject to the constraint that the allocation of the indivisible goods is EF1, admits a polynomial-time, 1/2-approximate, truthful auction. We further prove that this problem is NP-Hard and, hence, an approximation is warranted. This hardness result also complements prior works which show that an arbitrary EF1 allocation can be computed efficiently. We also establish a bi-criteria approximation guarantee for the problem of maximizing social welfare under MMS constraints. In particular, we develop a truthful auction which efficiently finds an allocation wherein each agent gets a bundle of value at least $\left(1/2 - \varepsilon \right)$ times her maximin share and the welfare of the computed allocation is at least the optimal, here $\varepsilon >0$ is a fixed constant. We complement this result by showing that maximizing welfare is computationally hard even if one aims to only satisfy the MMS constraint approximately.

Algorithmic Stability in Fair Allocation of Indivisible Goods Among Two Agents.

2020-07-30

Vijay Menon , Kate Larson

Many allocation problems in multiagent systems rely on agents specifying cardinal preferences. However, allocation mechanisms can be sensitive to small perturbations in cardinal preferences, thus causing agents who make ``small … Many allocation problems in multiagent systems rely on agents specifying cardinal preferences. However, allocation mechanisms can be sensitive to small perturbations in cardinal preferences, thus causing agents who make ``small or ``innocuous mistakes while reporting their preferences to experience a large change in their utility for the final outcome. To address this, we introduce a notion of algorithmic stability and study it in the context of fair and efficient allocations of indivisible goods among two agents. We show that it is impossible to achieve exact stability along with even a weak notion of fairness and even approximate efficiency. As a result, we propose two relaxations to stability, namely, approximate-stability and weak-approximate-stability, and show how existing algorithms in the fair division literature that guarantee fair and efficient outcomes perform poorly with respect to these relaxations. This leads us to explore the possibility of designing new algorithms that are more stable. Towards this end, we present a general characterization result for pairwise maximin share allocations, and in turn use it to design an algorithm that is approximately-stable and guarantees a pairwise maximin share and Pareto optimal allocation for two agents. Finally, we present a simple framework that can be used to modify existing fair and efficient algorithms in order to ensure that they also achieve weak-approximate-stability.

Envy-freeness up to any item with high Nash welfare: The virtue of donating items

2019-02-12

Ioannis Caragiannis , Nick Gravin , Xin Huang

Competitive Equilibrium with Indivisible Goods and Generic Budgets.

2017-03-23

Moshe Babaioff , Noam Nisan , Inbal Talgam-Cohen

Competitive equilibrium from equal incomes (CEEI) is a classic solution to the problem of fair and efficient allocation of goods [Foley'67, Varian'74]. Every agent receives an equal budget of artificial … Competitive equilibrium from equal incomes (CEEI) is a classic solution to the problem of fair and efficient allocation of goods [Foley'67, Varian'74]. Every agent receives an equal budget of artificial currency with which to purchase goods, and prices match demand and supply. However, a CEEI is not guaranteed to exist when the goods are indivisible, even in the simple two-agent, single-item market. Yet, it is easy to see that once the two budgets are slightly perturbed (made generic), a competitive equilibrium does exist. In this paper we aim to extend this approach beyond the single-item case, and study the existence of equilibria in markets with two agents and additive preferences over multiple items. We show that for agents with equal budgets, making the budgets generic -- by adding vanishingly small random perturbations -- ensures the existence of an equilibrium. We further consider agents with arbitrary non-equal budgets, representing non-equal entitlements for goods. We show that competitive equilibrium guarantees a new notion of fairness among non-equal agents, and that it exists in cases of interest (like when the agents have identical preferences) if budgets are perturbed. Our results open opportunities for future research on generic equilibrium existence and fair treatment of non-equals.

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.

An Algorithmic Framework for Approximating Maximin Share Allocation of Chores

2019-01-01

Xin Huang , Pinyan Lu

In this paper, we consider the problem of how to fairly dividing $m$ indivisible chores among $n$ agents. The fairness measure we considered here is the maximin share. The previous … In this paper, we consider the problem of how to fairly dividing $m$ indivisible chores among $n$ agents. The fairness measure we considered here is the maximin share. The previous best known result is that there always exists a $\frac{4}{3}$ approximation maximin share allocation. With a novel algorithm, we can always find a $\frac{11}{9}$ approximation maximin share allocation for any instances. We also discuss how to improve the efficiency of the algorithm and its connection to the job scheduling problem.

View PDF Chat

The Query Complexity of Cake Cutting.

2017-05-08

Simina Brânzei , Noam Nisan

We study the query complexity of cake cutting and give lower and upper bounds for computing approximately envy-free, perfect, and equitable allocations with the minimum number of cuts. The lower … We study the query complexity of cake cutting and give lower and upper bounds for computing approximately envy-free, perfect, and equitable allocations with the minimum number of cuts. The lower bounds are tight for computing connected envy-free allocations among n=3 players and for computing perfect and equitable allocations with minimum number of cuts between n=2 players. We also formalize moving knife procedures and show that a large subclass of this family, which captures all the known moving knife procedures, can be simulated efficiently with arbitrarily small error in the Robertson-Webb query model.

Monotone and Online Fair Division

2019-01-01

Martin Aleksandrov , Toby Walsh

View PDF Chat

Well-behaved Online Load Balancing Against Strategic Jobs

2019-01-01

Bo Li , Minming Li , Xiaowei Wu

In the online load balancing problem on related machines, we have a set of jobs (with different sizes) arriving online, and we need to assign each job to a machine … In the online load balancing problem on related machines, we have a set of jobs (with different sizes) arriving online, and we need to assign each job to a machine immediately upon its arrival, so as to minimize the makespan, i.e., the maximum completion time. In classic mechanism design problems, we assume that the jobs are controlled by selfish agents, with the sizes being their private information. Each job (agent) aims at minimizing its own cost, which is its completion time plus the payment charged by the mechanism. Truthful mechanisms guaranteeing that every job minimizes its cost by reporting its true size have been well-studied [Aspnes et al. JACM 1997, Feldman et al. EC 2017]. In this paper, we study truthful online load balancing mechanisms that are well-behaved [Epstein et al., MOR 2016]. Well-behavior is important as it guarantees fairness between machines, and implies truthfulness in some cases when machines are controlled by selfish agents. Unfortunately, existing truthful online load balancing mechanisms are not well-behaved. We first show that to guarantee producing a well-behaved schedule, any online algorithm (even non-truthful) has a competitive ratio at least $\Omega(\sqrt{m})$, where m is the number of machines. Then we propose a mechanism that guarantees truthfulness of the online jobs, and produces a schedule that is almost well-behaved. We show that our algorithm has a competitive ratio of $O(\log m)$. Moreover, for the case when the sizes of online jobs are bounded, the competitive ratio of our algorithm improves to $O(1)$. Interestingly, we show several cases for which our mechanism is actually truthful against selfish machines.

Fair Allocation of Indivisible Public Goods

2018-06-11

Brandon Fain , Kamesh Munagala , Nisarg Shah

We consider the problem of fairly allocating indivisible public goods. We model the public goods as elements with feasibility constraints on what subsets of elements can be chosen, and assume … We consider the problem of fairly allocating indivisible public goods. We model the public goods as elements with feasibility constraints on what subsets of elements can be chosen, and assume that agents have additive utilities across elements. Our model generalizes existing frameworks such as fair public decision making and participatory budgeting. We study a groupwise fairness notion called the core, which generalizes well-studied notions of proportionality and Pareto efficiency, and requires that each subset of agents must receive an outcome that is fair relative to its size. In contrast to the case of divisible public goods (where fractional allocations are permitted), the core is not guaranteed to exist when allocating indivisible public goods. Our primary contributions are the notion of an additive approximation to the core (with a tiny multiplicative loss), and polynomial time algorithms that achieve a small additive approximation, where the additive factor is relative to the largest utility of an agent for an element. If the feasibility constraints define a matroid, we show an additive approximation of 2. A similar approach yields a constant additive bound when the feasibility constraints define a matching. For feasibility constraints defining an arbitrary packing polytope with mild restrictions, we show an additive guarantee that is logarithmic in the width of the polytope. Our algorithms are based on the convex program for maximizing the Nash social welfare, but differ significantly from previous work in how it is used. As far as we are aware, our work is the first to approximate the core in indivisible settings.

View PDF Chat

The Price of Connectivity in Fair Division

2022-05-19

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 well-studied fairness notions including envy-freeness and maximin share fairness. We introduce the price of connectivity to capture the largest multiplicative 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. In addition, we determine the optimal relaxation of envy-freeness that can be obtained with each graph for two agents and characterize the set of trees and complete bipartite graphs that always admit an allocation satisfying envy-freeness up to one good (EF1) for three agents. Our work demonstrates several applications of graph-theoretic tools and concepts to fair division problems.

View PDF Chat

Fair Allocation of Indivisible Public Goods

2018-05-08

Brandon Fain , Kamesh Munagala , Nisarg Shah

We consider the problem of fairly allocating indivisible public goods. We model the public goods as elements with feasibility constraints on what subsets of elements can be chosen, and assume … We consider the problem of fairly allocating indivisible public goods. We model the public goods as elements with feasibility constraints on what subsets of elements can be chosen, and assume that agents have additive utilities across elements. Our model generalizes existing frameworks such as fair public decision making and participatory budgeting. We study a groupwise fairness notion called the core, which generalizes well-studied notions of proportionality and Pareto efficiency, and requires that each subset of agents must receive an outcome that is fair relative to its size. In contrast to the case of divisible public goods (where fractional allocations are permitted), the core is not guaranteed to exist when allocating indivisible public goods. Our primary contributions are the notion of an additive approximation to the core (with a tiny multiplicative loss), and polynomial time algorithms that achieve a small additive approximation, where the additive factor is relative to the largest utility of an agent for an element. If the feasibility constraints define a matroid, we show an additive approximation of 2. A similar approach yields a constant additive bound when the feasibility constraints define a matching. More generally, if the feasibility constraints define an arbitrary packing polytope with mild restrictions, we show an additive guarantee that is logarithmic in the width of the polytope. Our algorithms are based on variants of the convex program for maximizing the Nash social welfare, but differ significantly from previous work in how it is used. Our guarantees are meaningful even when there are fewer elements than the number of agents. As far as we are aware, our work is the first to approximate the core in indivisible settings.