Warut Suksompong

Search for another author

Author Description

Ask a Question About This Mathematician

Approximate maximin shares for groups of agents

2017-09-22

Warut Suksompong

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

Fairly allocating contiguous blocks of indivisible items

2019-02-22

Warut Suksompong

View PDF Chat

Almost envy-freeness in group resource allocation

2020-07-15

Maria Kyropoulou , Warut Suksompong , Alexandros A. Voudouris

View PDF Chat

Asymptotic existence of fair divisions for groups

2017-07-08

Pasin Manurangsi , Warut Suksompong

View PDF Chat

Democratic fair allocation of indivisible goods

2019-09-03

Erel Segal-Halevi , Warut Suksompong

View PDF Chat

The Price of Fairness for Indivisible Goods

2019-07-28

Xiaohui Bei , Xinhang Lu , Pasin Manurangsi +1 more

We investigate the efficiency of fair allocations of indivisible goods using the well-studied price of fairness concept. Previous work has focused on classical fairness notions such as envy-freeness, proportionality, and … We investigate the efficiency of fair allocations of indivisible goods using the well-studied price of fairness concept. Previous work has focused on classical fairness notions such as envy-freeness, proportionality, and equitability. However, these notions cannot always be satisfied for indivisible goods, leading to certain instances being ignored in the analysis. In this paper, we focus instead on notions with guaranteed existence, including envy-freeness up to one good (EF1), balancedness, maximum Nash welfare (MNW), and leximin. We mostly provide tight or asymptotically tight bounds on the worst-case efficiency loss for allocations satisfying these notions.

View PDF Chat

Scheduling asynchronous round-robin tournaments

2015-12-15

Warut Suksompong

View PDF Chat

Who Can Win a Single-Elimination Tournament?

2017-01-01

Michael P. Kim , Warut Suksompong , Virginia Vassilevska Williams

A single-elimination (SE) tournament is a popular way to select a winner both in sports competitions and in elections. A natural and well-studied question is the tournament fixing problem (TFP): … A single-elimination (SE) tournament is a popular way to select a winner both in sports competitions and in elections. A natural and well-studied question is the tournament fixing problem (TFP): given the set of all pairwise match outcomes, can a tournament organizer rig an SE tournament by adjusting the initial seeding so that the organizer's favorite player wins? We prove new sufficient conditions on the pairwise match outcome information and the favorite player, under which there is guaranteed to be a seeding where the player wins the tournament. Our results greatly generalize previous results. We also investigate the relationship between the set of players that can win an SE tournament under some seeding (so-called SE winners) and other traditional tournament solutions. In addition, we generalize and strengthen prior work on probabilistic models for generating tournaments. For instance, we show that every player in an $n$ player tournament generated by the Condorcet random model will be an SE winner even when the noise is as small as possible, $p=\Theta(\ln n/n)$; prior work only had such results for $p\geq \Omega(\sqrt{\ln n/n})$. We also establish new results for significantly more general generative models.

View PDF Chat

The Price of Fairness for Indivisible Goods

2021-03-29

Xiaohui Bei , Xinhang Lu , Pasin Manurangsi +1 more

View PDF Chat

The Price of Connectivity in Fair Division

2021-05-18

Xiaohui Bei , Ayumi Igarashi , Xinhang Lu +1 more

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

View PDF Chat

Democratic Fair Allocation of Indivisible Goods

2018-07-01

Erel Segal-Halevi , Warut Suksompong

We study the problem of fairly allocating indivisible goods to groups of agents. Agents in the same group share the same set of goods even though they may have different … We study the problem of fairly allocating indivisible goods to groups of agents. Agents in the same group share the same set of goods even though they may have different preferences. Previous work has focused on unanimous fairness, in which all agents in each group must agree that their group's share is fair. Under this strict requirement, fair allocations exist only for small groups. We introduce the concept of democratic fairness, which aims to satisfy a certain fraction of the agents in each group. This concept is better suited to large groups such as cities or countries. We present protocols for democratic fair allocation among two or more arbitrarily large groups of agents with monotonic, additive, or binary valuations. Our protocols approximate both envy-freeness and maximin-share fairness. As an example, for two groups of agents with additive valuations, our protocol yields an allocation that is envy-free up to one good and gives at least half of the maximin share to at least half of the agents in each group.

View PDF Chat

Contiguous Cake Cutting: Hardness Results and Approximation Algorithms

2020-09-22

Paul W. Goldberg , Alexandros Hollender , Warut Suksompong

We study the fair allocation of a cake, which serves as a metaphor for a divisible resource, under the requirement that each agent should receive a contiguous piece of the … We study the fair allocation of a cake, which serves as a metaphor for a divisible resource, under the requirement that each agent should receive a contiguous piece of the cake. While it is known that no finite envy-free algorithm exists in this setting, we exhibit efficient algorithms that produce allocations with low envy among the agents. We then establish NP-hardness results for various decision problems on the existence of envy-free allocations, such as when we fix the ordering of the agents or constrain the positions of certain cuts. In addition, we consider a discretized setting where indivisible items lie on a line and show a number of hardness results extending and strengthening those from prior work. Finally, we investigate connections between approximate and exact envy-freeness, as well as between continuous and discrete cake cutting.

View PDF Chat

Schelling games on graphs

2021-08-12

Aishwarya Agarwal , Edith Elkind , Jiarui Gan +3 more

View PDF Chat

Closing Gaps in Asymptotic Fair Division

2021-01-01

Pasin Manurangsi , Warut Suksompong

We study a resource allocation setting where $m$ discrete items are to be divided among $n$ agents with additive utilities, and the agents' utilities for individual items are drawn at … We study a resource allocation setting where $m$ discrete items are to be divided among $n$ agents with additive utilities, and the agents' utilities for individual items are drawn at random from a probability distribution. Since common fairness notions like envy-freeness and proportionality cannot always be satisfied in this setting, an important question is when allocations satisfying these notions exist. In this paper, we close several gaps in the line of work on asymptotic fair division. First, we prove that the classical round-robin algorithm is likely to produce an envy-free allocation provided that $m=\Omega(n\log n/\log\log n)$, matching the lower bound from prior work. We then show that a proportional allocation exists with high probability as long as $m\geq n$, while an allocation satisfying envy-freeness up to any item (EFX) is likely to be present for any relation between $m$ and $n$. Finally, we consider a related setting where each agent is assigned exactly one item and the remaining items are left unassigned, and show that the transition from non-existence to existence with respect to envy-free assignments occurs at $m=en$.

View PDF Chat

Almost Envy-Freeness in Group Resource Allocation

2019-07-28

Maria Kyropoulou , Warut Suksompong , Alexandros A. Voudouris

We study the problem of fairly allocating indivisible goods between groups of agents using the recently introduced relaxations of envy-freeness. We consider the existence of fair allocations under different assumptions … We study the problem of fairly allocating indivisible goods between groups of agents using the recently introduced relaxations of envy-freeness. We consider the existence of fair allocations under different assumptions on the valuations of the agents. In particular, our results cover cases of arbitrary monotonic, responsive, and additive valuations, while for the case of binary valuations we fully characterize the cardinalities of two groups of agents for which a fair allocation can be guaranteed with respect to both envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX). Moreover, we introduce a new model where the agents are not partitioned into groups in advance, but instead the partition can be chosen in conjunction with the allocation of the goods. In this model, we show that for agents with arbitrary monotonic valuations, there is always a partition of the agents into two groups of any given sizes along with an EF1 allocation of the goods. We also provide an extension of this result to any number of groups.

View PDF Chat

Truthful fair division without free disposal

2020-04-25

Xiaohui Bei , Guangda Huzhang , Warut Suksompong

Abstract We study the problem of fairly dividing a heterogeneous resource, commonly known as cake cutting and chore division, in the presence of strategic agents. While a number of results … Abstract We study the problem of fairly dividing a heterogeneous resource, commonly known as cake cutting and chore division, in the presence of strategic agents. While a number of results in this setting have been established in previous works, they rely crucially on the free disposal assumption, meaning that the mechanism is allowed to throw away part of the resource at no cost. In the present work, we remove this assumption and focus on mechanisms that always allocate the entire resource. We exhibit a truthful and envy-free mechanism for cake cutting and chore division for two agents with piecewise uniform valuations, and we complement our result by showing that such a mechanism does not exist when certain additional constraints are imposed on the mechanisms. Moreover, we provide bounds on the efficiency of mechanisms satisfying various properties, and give truthful mechanisms for multiple agents with restricted classes of valuations.

View PDF Chat

Welfare Guarantees in Schelling Segregation

2021-05-29

Martin Bullinger , Warut Suksompong , Alexandros A. Voudouris

Schelling’s model is an influential model that reveals how individual perceptions and incentives can lead to residential segregation. Inspired by a recent stream of work, we study welfare guarantees and … Schelling’s model is an influential model that reveals how individual perceptions and incentives can lead to residential segregation. Inspired by a recent stream of work, we study welfare guarantees and complexity in this model with respect to several welfare measures. First, we show that while maximizing the social welfare is NP-hard, computing an assignment of agents to the nodes of any topology graph with approximately half of the maximum welfare can be done in polynomial time. We then consider Pareto optimality, introduce two new optimality notions based on it, and establish mostly tight bounds on the worst-case welfare loss for assignments satisfying these notions as well as the complexity of computing such assignments. In addition, we show that for tree topologies, it is possible to decide whether there exists an assignment that gives every agent a positive utility in polynomial time; moreover, when every node in the topology has degree at least 2, such an assignment always exists and can be found efficiently.

View PDF Chat

On maximum weighted Nash welfare for binary valuations

2022-04-07

Warut Suksompong , Nicholas Teh

We consider the problem of fairly allocating indivisible goods to agents with weights representing their entitlements. A natural rule in this setting is the maximum weighted Nash welfare (MWNW) rule, … We consider the problem of fairly allocating indivisible goods to agents with weights representing their entitlements. A natural rule in this setting is the maximum weighted Nash welfare (MWNW) rule, which selects an allocation maximizing the weighted product of the agents' utilities. We show that when agents have binary valuations, a specific version of MWNW is resource- and population-monotone, satisfies group-strategyproofness, and can be implemented in polynomial time.

View PDF Chat

Envy-freeness in house allocation problems

2019-07-30

Jiarui Gan , Warut Suksompong , Alexandros A. Voudouris

View PDF Chat

On the structure of stable tournament solutions

2016-12-23

Felix Brandt , Markus Brill , Hans Georg Seedig +1 more

View PDF Chat

Fairly Allocating Many Goods with Few Queries

2019-07-17

Hoon Oh , Ariel D. Procaccia , Warut Suksompong

We investigate the query complexity of the fair allocation of indivisible goods. For two agents with arbitrary monotonic valuations, we design an algorithm that computes an allocation satisfying envy-freeness up … We investigate the query complexity of the fair allocation of indivisible goods. For two agents with arbitrary monotonic valuations, we design an algorithm that computes an allocation satisfying envy-freeness up to one good (EF1), a relaxation of envy-freeness, using a logarithmic number of queries. We show that the logarithmic query complexity bound also holds for three agents with additive valuations. These results suggest that it is possible to fairly allocate goods in practice even when the number of goods is extremely large. By contrast, we prove that computing an allocation satisfying envyfreeness and another of its relaxations, envy-freeness up to any good (EFX), requires a linear number of queries even when there are only two agents with identical additive valuations.

View PDF Chat

Picking sequences and monotonicity in weighted fair division

2021-08-13

Mithun Chakraborty , Ulrike Schmidt-Kraepelin , Warut Suksompong

View PDF Chat

Funding public projects: A case for the Nash product rule

2021-10-30

Florian Brandl , Felix Brandt , Matthias Greger +3 more

We study a mechanism design problem where a community of agents wishes to fund public projects via voluntary monetary contributions by the community members. This serves as a model for … We study a mechanism design problem where a community of agents wishes to fund public projects via voluntary monetary contributions by the community members. This serves as a model for public expenditure without an exogenously available budget, such as participatory budgeting or voluntary tax programs, as well as donor coordination when interpreting charities as public projects and donations as contributions. Our aim is to identify a mutually beneficial distribution of the individual contributions. In the preference aggregation problem that we study, agents with linear utility functions over projects report the amount of their contribution, and the mechanism determines a socially optimal distribution of the money. We identify a specific mechanism—the Nash product rule—which picks the distribution that maximizes the product of the agents' utilities. This rule is Pareto efficient and incentivizes agents to contribute their entire budget while spending each agent's contribution only on projects the agent finds acceptable.

View PDF Chat

Asymptotic existence of proportionally fair allocations

2016-03-24

Warut Suksompong

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

When Do Envy-Free Allocations Exist?

2020-01-01

Pasin Manurangsi , Warut Suksompong

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

View PDF Chat

The impossibility of extending random dictatorship to weak preferences

2016-02-10

Florian Brandl , Felix Brandt , Warut Suksompong

View PDF Chat

Computing a small agreeable set of indivisible items

2018-12-18

Pasin Manurangsi , Warut Suksompong

View PDF Chat

Mind the gap: Cake cutting with separation

2022-09-09

Edith Elkind , Erel Segal-Halevi , Warut Suksompong

We study the problem of fairly allocating a divisible resource, also known as cake cutting, with an additional requirement that the shares that different agents receive should be sufficiently separated … We study the problem of fairly allocating a divisible resource, also known as cake cutting, with an additional requirement that the shares that different agents receive should be sufficiently separated from one another. This captures, for example, constraints arising from social distancing guidelines. While it is sometimes impossible to allocate a proportional share to every agent under the separation requirement, we show that the well-known criterion of maximin share fairness can always be attained. We then provide algorithmic analysis of maximin share fairness in this setting -- for instance, the maximin share of an agent cannot be computed exactly by any finite algorithm, but can be approximated with an arbitrarily small error. In addition, we consider the division of a pie (i.e., a circular cake) and show that an ordinal relaxation of maximin share fairness can be achieved. We also prove that an envy-free or equitable allocation that allocates the maximum amount of resource exists under separation.

View PDF Chat

Who Can Win a Single-Elimination Tournament?

2016-02-21

Michael P. Kim , Warut Suksompong , Virginia Vassilevska Williams

A single-elimination (SE) tournament is a popular way to select a winner in both sports competitions and in elections. A natural and well-studied question is the tournament fixing problem (TFP): … A single-elimination (SE) tournament is a popular way to select a winner in both sports competitions and in elections. A natural and well-studied question is the tournament fixing problem (TFP): given the set of all pairwise match outcomes, can a tournament organizer rig an SE tournament by adjusting the initial seeding so that their favorite player wins? We prove new sufficient conditions on the pairwise match outcome information and the favorite player, under which there is guaranteed to be a seeding where the player wins the tournament. Our results greatly generalize previous results. We also investigate the relationship between the set of players that can win an SE tournament under some seeding (so called SE winners) and other traditional tournament solutions. In addition, we generalize and strengthen prior work on probabilistic models for generating tournaments. For instance, we show that every player in an n player tournament generated by the Condorcet Random Model will be an SE winner even when the noise is as small as possible, p = Θ(ln n/n); prior work only had such results for p ≥ Ω( ln n/n). We also establish new results for significantly more general generative models.

View PDF Chat

How to Cut a Cake Fairly: A Generalization to Groups

2021-01-02

Erel Segal-Halevi , Warut Suksompong

A fundamental result in cake cutting states that for any number of players with arbitrary preferences over a cake, there exists a division of the cake such that every player … A fundamental result in cake cutting states that for any number of players with arbitrary preferences over a cake, there exists a division of the cake such that every player receives a single contiguous piece and no player is left envious. We generalize this result by showing that it is possible to partition the players into groups of any desired sizes and divide the cake among the groups so that each group receives a single contiguous piece, and no player finds the piece of another group better than that of the player's own group.

View PDF Chat

Graphical Cake Cutting via Maximin Share

2021-08-01

Edith Elkind , Erel Segal-Halevi , Warut Suksompong

We study the recently introduced cake-cutting setting in which the cake is represented by an undirected graph. This generalizes the canonical interval cake and allows for modeling the division of … We study the recently introduced cake-cutting setting in which the cake is represented by an undirected graph. This generalizes the canonical interval cake and allows for modeling the division of road networks. We show that when the graph is a forest, an allocation satisfying the well-known criterion of maximin share fairness always exists. Our result holds even when separation constraints are imposed; however, in the latter case no multiplicative approximation of proportionality can be guaranteed. Furthermore, while maximin share fairness is not always achievable for general graphs, we prove that ordinal relaxations can be attained.

View PDF Chat

Refining Tournament Solutions via Margin of Victory

2020-04-03

Markus Brill , Ulrike Schmidt-Kraepelin , Warut Suksompong

Tournament solutions are frequently used to select winners from a set of alternatives based on pairwise comparisons between alternatives. Prior work has shown that several common tournament solutions tend to … Tournament solutions are frequently used to select winners from a set of alternatives based on pairwise comparisons between alternatives. Prior work has shown that several common tournament solutions tend to select large winner sets and therefore have low discriminative power. In this paper, we propose a general framework for refining tournament solutions. In order to distinguish between winning alternatives, and also between non-winning ones, we introduce the notion of margin of victory (MoV) for tournament solutions. MoV is a robustness measure for individual alternatives: For winners, the MoV captures the distance from dropping out of the winner set, and for non-winners, the distance from entering the set. In each case, distance is measured in terms of which pairwise comparisons would have to be reversed in order to achieve the desired outcome. For common tournament solutions, including the top cycle, the uncovered set, and the Banks set, we determine the complexity of computing the MoV and provide worst-case bounds on the MoV for both winners and non-winners. Our results can also be viewed from the perspective of bribery and manipulation.

View PDF Chat

Fairly Allocating Contiguous Blocks of Indivisible Items

2017-01-01

Warut Suksompong

View PDF Chat

When Do Envy-Free Allocations Exist?

2019-07-17

Pasin Manurangsi , Warut Suksompong

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

View PDF Chat

On the number of almost envy-free allocations

2020-04-07

Warut Suksompong

View PDF Chat

Weighted Envy-Freeness in Indivisible Item Allocation

2020-05-05

Mithun Chakraborty , Ayumi Igarashi , Warut Suksompong +1 more

In this paper, 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 … In this paper, 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 the envy can be eliminated by removing an item from the envied agent's bundle) and weak (where the 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 envious agent's bundle). We prove that for additive valuations, an allocation that is both Pareto optimal and strongly WEF1 always exists; however, 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 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 classic adjusted winner algorithm. We also explore the connections of WEF1 with approximations to the weighted versions of two other fairness concepts: proportionality and the maximin share guarantee.

Consensus Halving for Sets of Items

2022-02-10

Paul W. Goldberg , Alexandros Hollender , Ayumi Igarashi +2 more

Consensus halving refers to the problem of dividing a resource into two parts so that every agent values both parts equally. Prior work shows that, when the resource is represented … Consensus halving refers to the problem of dividing a resource into two parts so that every agent values both parts equally. Prior work shows that, when the resource is represented by an interval, a consensus halving with at most n cuts always exists but is hard to compute even for agents with simple valuation functions. In this paper, we study consensus halving in a natural setting in which the resource consists of a set of items without a linear ordering. For agents with linear and additively separable utilities, we present a polynomial-time algorithm that computes a consensus halving with at most n cuts and show that n cuts are almost surely necessary when the agents’ utilities are randomly generated. On the other hand, we show that, for a simple class of monotonic utilities, the problem already becomes polynomial parity argument, directed version–hard. Furthermore, we compare and contrast consensus halving with the more general problem of consensus k-splitting, with which we wish to divide the resource into k parts in possibly unequal ratios and provide some consequences of our results on the problem of computing small agreeable sets.

View PDF Chat

Truthful Fair Division without Free Disposal

2018-07-01

Xiaohui Bei , Guangda Huzhang , Warut Suksompong

We study the problem of fairly dividing a heterogeneous resource, commonly known as cake cutting and chore division, in the presence of strategic agents. While a number of results in … We study the problem of fairly dividing a heterogeneous resource, commonly known as cake cutting and chore division, in the presence of strategic agents. While a number of results in this setting have been established in previous works, they rely crucially on the free disposal assumption, meaning that the mechanism is allowed to throw away part of the resource at no cost. In the present work, we remove this assumption and focus on mechanisms that always allocate the entire resource. We exhibit a truthful envy-free mechanism for cake cutting and chore division for two agents with piecewise uniform valuations, and we complement our result by showing that such a mechanism does not exist when certain additional assumptions are made. Moreover, we give truthful mechanisms for multiple agents with restricted classes of valuations.

View PDF Chat

Contiguous Cake Cutting: Hardness Results and Approximation Algorithms

2020-04-03

Paul W. Goldberg , Alexandros Hollender , Warut Suksompong

View PDF Chat

Funding Public Projects: A Case for the Nash Product Rule

2020-05-16

Florian Brandl , Felix Brandt , Dominik Peters +2 more

We study a mechanism design problem where a community of agents wishes to fund public projects via voluntary monetary contributions by the community members. This serves as a model for … We study a mechanism design problem where a community of agents wishes to fund public projects via voluntary monetary contributions by the community members. This serves as a model for participatory budgeting without an exogenously available budget, as well as donor coordination when interpreting charities as public projects and donations as contributions. Our aim is to identify a mutually beneficial distribution of the individual contributions. In the preference aggregation problem that we study, agents report linear utility functions over projects together with the amount of their contributions, and the mechanism determines a socially optimal distribution of the money. We identify a specific mechanism---the Nash product rule---which picks the distribution that maximizes the product of the agents' utilities. This rule is Pareto efficient, and we prove that it satisfies attractive incentive properties: the Nash rule spends an agent's contribution only on projects the agent finds acceptable, and it provides strong participation incentives. We also discuss issues of strategyproofness and monotonicity.

Weighted Fairness Notions for Indivisible Items Revisited

2022-06-28

Mithun Chakraborty , Erel Segal-Halevi , Warut Suksompong

We revisit the setting of fairly allocating indivisible items when agents have different weights representing their entitlements. First, we propose a parameterized family of relaxations for weighted envy-freeness and the … We revisit the setting of fairly allocating indivisible items when agents have different weights representing their entitlements. First, we propose a parameterized family of relaxations for weighted envy-freeness and the same for weighted proportionality; the parameters indicate whether smaller-weight or larger-weight agents should be given a higher priority. We show that each notion in these families can always be satisfied, but any two cannot necessarily be fulfilled simultaneously. We then introduce an intuitive weighted generalization of maximin share fairness and establish the optimal approximation of it that can be guaranteed. Furthermore, we characterize the implication relations between the various weighted fairness notions introduced in this and prior work, and relate them to the lower and upper quota axioms from apportionment.

View PDF Chat

Robust bounds on choosing from large tournaments

2019-08-23

Christian Saile , Warut Suksompong

Tournament solutions provide methods for selecting the "best" alternatives from a tournament and have found applications in a wide range of areas. Previous work has shown that several well-known tournament … Tournament solutions provide methods for selecting the "best" alternatives from a tournament and have found applications in a wide range of areas. Previous work has shown that several well-known tournament solutions almost never rule out any alternative in large random tournaments. Nevertheless, all analytical results thus far have assumed a rigid probabilistic model, in which either a tournament is chosen uniformly at random, or there is a linear order of alternatives and the orientation of all edges in the tournament is chosen with the same probabilities according to the linear order. In this work, we consider a significantly more general model where the orientation of different edges can be chosen with different probabilities. We show that a number of common tournament solutions, including the top cycle and the uncovered set, are still unlikely to rule out any alternative under this model. This corresponds to natural graph-theoretic conditions such as irreducibility of the tournament. In addition, we provide tight asymptotic bounds on the boundary of the probability range for which the tournament solutions select all alternatives with high probability.

View PDF Chat

Computing an Approximately Optimal Agreeable Set of Items

2017-07-28

Pasin Manurangsi , Warut Suksompong

We study the problem of finding a small subset of items that is agreeable to all agents, meaning that all agents value the subset at least as much as its … We study the problem of finding a small subset of items that is agreeable to all agents, meaning that all agents value the subset at least as much as its complement. Previous work has shown worst-case bounds, over all instances with a given number of agents and items, on the number of items that may need to be included in such a subset. Our goal in this paper is to efficiently compute an agreeable subset whose size approximates the size of the smallest agreeable subset for a given instance. We consider three well-known models for representing the preferences of the agents: ordinal preferences on single items, the value oracle model, and additive utilities. In each of these models, we establish virtually tight bounds on the approximation ratio that can be obtained by algorithms running in polynomial time.

View PDF Chat

Margin of Victory in Tournaments: Structural and Experimental Results

2021-05-18

Markus Brill , Ulrike Schmidt-Kraepelin , Warut Suksompong

Tournament solutions are standard tools for identifying winners based on pairwise comparisons between competing alternatives. The recently studied notion of margin of victory (MoV) offers a general method for refining … Tournament solutions are standard tools for identifying winners based on pairwise comparisons between competing alternatives. The recently studied notion of margin of victory (MoV) offers a general method for refining the winner set of any given tournament solution, thereby increasing the discriminative power of the solution. In this paper, we reveal a number of structural insights on the MoV by investigating fundamental properties such as monotonicity and consistency with respect to the covering relation. Furthermore, we provide experimental evidence on the extent to which the MoV notion refines winner sets in tournaments generated according to various stochastic models.

View PDF Chat

Keep Your Distance: Land Division With Separation

2021-08-01

Edith Elkind , Erel Segal-Halevi , Warut Suksompong

This paper is part of an ongoing endeavor to bring the theory of fair division closer to practice by handling requirements from real-life applications. We focus on two requirements originating … This paper is part of an ongoing endeavor to bring the theory of fair division closer to practice by handling requirements from real-life applications. We focus on two requirements originating from the division of land estates: (1) each agent should receive a plot of a usable geometric shape, and (2) plots of different agents must be physically separated. With these requirements, the classic fairness notion of proportionality is impractical, since it may be impossible to attain any multiplicative approximation of it. In contrast, the ordinal maximin share approximation, introduced by Budish in 2011, provides meaningful fairness guarantees. We prove upper and lower bounds on achievable maximin share guarantees when the usable shapes are squares, fat rectangles, or arbitrary axes-aligned rectangles, and explore the algorithmic and query complexity of finding fair partitions in this setting.

View PDF Chat

The Price of Justified Representation

2022-06-28

Edith Elkind , Piotr Faliszewski , Ayumi Igarashi +3 more

In multiwinner approval voting, the goal is to select k-member committees based on voters' approval ballots. A well-studied concept of proportionality in this context is the justified representation (JR) axiom, … In multiwinner approval voting, the goal is to select k-member committees based on voters' approval ballots. A well-studied concept of proportionality in this context is the justified representation (JR) axiom, which demands that no large cohesive group of voters remains unrepresented. However, the JR axiom may conflict with other desiderata, such as coverage (maximizing the number of voters who approve at least one committee member) or social welfare (maximizing the number of approvals obtained by committee members). In this work, we investigate the impact of imposing the JR axiom (as well as the more demanding EJR axiom) on social welfare and coverage. Our approach is threefold: we derive worst-case bounds on the loss of welfare/coverage that is caused by imposing JR, study the computational complexity of finding 'good' committees that provide JR (obtaining a hardness result, an approximation algorithm, and an exact algorithm for one-dimensional preferences), and examine this setting empirically on several synthetic datasets.

View PDF Chat

Fair Division with Two-Sided Preferences

2023-08-01

Ayumi Igarashi , Yasushi Kawase , Warut Suksompong +1 more

We study a fair division setting in which a number of players are to be fairly distributed among a set of teams. In our model, not only do the teams … We study a fair division setting in which a number of players are to be fairly distributed among a set of teams. In our model, not only do the teams have preferences over the players as in the canonical fair division setting, but the players also have preferences over the teams. We focus on guaranteeing envy-freeness up to one player (EF1) for the teams together with a stability condition for both sides. We show that an allocation satisfying EF1, swap stability, and individual stability always exists and can be computed in polynomial time, even when teams may have positive or negative values for players. Similarly, a balanced and swap stable allocation that satisfies a relaxation of EF1 can be computed efficiently. When teams have nonnegative values for players, we prove that an EF1 and Pareto optimal allocation exists and, if the valuations are binary, can be found in polynomial time. We also examine the compatibility between EF1 and justified envy-freeness.

View PDF Chat

Individual and group stability in neutral restrictions of hedonic games

2015-08-17

Warut Suksompong

View PDF Chat

Ordinal Maximin Guarantees for Group Fair Division

2025-03-03

Pasin Manurangsi , Warut Suksompong

View PDF Chat

Reforming an Unfair Allocation by Exchanging Goods

2024-12-26

Sheung Man Yuen , Ayumi Igarashi , Naoyuki Kamiyama +1 more

Fairly allocating indivisible goods is a frequently occurring task in everyday life. Given an initial allocation of the goods, we consider the problem of reforming it via a sequence of … Fairly allocating indivisible goods is a frequently occurring task in everyday life. Given an initial allocation of the goods, we consider the problem of reforming it via a sequence of exchanges to attain fairness in the form of envy-freeness up to one good (EF1). We present a vast array of results on the complexity of determining whether it is possible to reach an EF1 allocation from the initial allocation and, if so, the minimum number of exchanges required. In particular, we uncover several distinctions based on the number of agents involved and their utility functions. Furthermore, we derive essentially tight bounds on the worst-case number of exchanges needed to achieve EF1.

View PDF Chat

On the Fairness of Additive Welfarist Rules

2024-12-19

Karen Frilya Celine , Warut Suksompong , Sheung Man Yuen

Allocating indivisible goods is a ubiquitous task in fair division. We study additive welfarist rules, an important class of rules which choose an allocation that maximizes the sum of some … Allocating indivisible goods is a ubiquitous task in fair division. We study additive welfarist rules, an important class of rules which choose an allocation that maximizes the sum of some function of the agents' utilities. Prior work has shown that the maximum Nash welfare (MNW) rule is the unique additive welfarist rule that guarantees envy-freeness up to one good (EF1). We strengthen this result by showing that MNW remains the only additive welfarist rule that ensures EF1 for identical-good instances, two-value instances, as well as normalized instances with three or more agents. On the other hand, if the agents' utilities are integers, we demonstrate that several other rules offer the EF1 guarantee, and provide characterizations of these rules for various classes of instances.

View PDF Chat

Fair Division with Two-Sided Preferences

2024-08-22

Ayumi Igarashi , Yasushi Kawase , Warut Suksompong +1 more

We study a fair division setting in which participants are to be fairly distributed among teams, where not only do the teams have preferences over the participants as in the … We study a fair division setting in which participants are to be fairly distributed among teams, where not only do the teams have preferences over the participants as in the canonical fair division setting, but the participants also have preferences over the teams. We focus on guaranteeing envy-freeness up to one participant (EF1) for the teams together with a stability condition for both sides. We show that an allocation satisfying EF1, swap stability, and individual stability always exists and can be computed in polynomial time, even when teams may have positive or negative values for participants. When teams have nonnegative values for participants, we prove that an EF1 and Pareto optimal allocation exists and, if the valuations are binary, can be found in polynomial time. We also show that an EF1 and justified envy-free allocation does not necessarily exist, and deciding whether such an allocation exists is computationally difficult.

View PDF Chat

The Price of Justified Representation

2024-08-06

Edith Elkind , Piotr Faliszewski , Ayumi Igarashi +3 more

In multiwinner approval voting, the goal is to select a k -member committee based on voters’ approval ballots. A well-studied concept of proportionality in this context is the justified representation … In multiwinner approval voting, the goal is to select a k -member committee based on voters’ approval ballots. A well-studied concept of proportionality in this context is the justified representation (JR) axiom, which demands that no large cohesive group of voters remains unrepresented. However, the JR axiom may conflict with other desiderata, such as social welfare (the number of approvals obtained by committee members) or coverage (the number of voters who approve at least one committee member). In this article, we investigate the price of imposing the JR axiom (as well as the more demanding extended justified representation axiom) on social welfare and coverage. Our approach is twofold: We derive worst-case bounds on the loss of welfare/coverage caused by imposing JR and study the computational complexity of finding committees with high welfare that provide JR (obtaining hardness results, approximation algorithms, and an exact algorithm for one-dimensional preferences).

View PDF Chat

Ordinal Maximin Guarantees for Group Fair Division

2024-07-26

Pasin Manurangsi , Warut Suksompong

We investigate fairness in the allocation of indivisible items among groups of agents using the notion of maximin share (MMS). While previous work has shown that no nontrivial multiplicative MMS … We investigate fairness in the allocation of indivisible items among groups of agents using the notion of maximin share (MMS). While previous work has shown that no nontrivial multiplicative MMS approximation can be guaranteed in this setting for general group sizes, we demonstrate that ordinal relaxations are much more useful. For example, we show that if n agents are distributed equally across g groups, there exists a 1-out-of-k MMS allocation for k = O(g log(n/g)), while if all but a constant number of agents are in the same group, we obtain k = O(log n / log log n). We also establish the tightness of these bounds and provide non-asymptotic results for the case of two groups.

View PDF Chat

Welfare Loss in Connected Resource Allocation

2024-07-26

Xiaohui Bei , Alexander Lam , Xinhang Lu +1 more

We study the allocation of indivisible goods that form an undirected graph and investigate the worst-case welfare loss when requiring that each agent must receive a connected subgraph. Our focus … We study the allocation of indivisible goods that form an undirected graph and investigate the worst-case welfare loss when requiring that each agent must receive a connected subgraph. Our focus is on both egalitarian and utilitarian welfare. Specifically, we introduce the concept of egalitarian (resp., utilitarian) price of connectivity, which captures the worst-case ratio between the optimal egalitarian (resp., utilitarian) welfare among all allocations and that among the connected allocations. We provide tight or asymptotically tight bounds on the price of connectivity for various large classes of graphs when there are two agents, and for paths, stars and cycles in the general case. Many of our results are supplemented with algorithms which find connected allocations with a welfare guarantee corresponding to the price of connectivity.

View PDF Chat

Approximate envy-freeness in graphical cake cutting

2024-06-15

Sheung Man Yuen , Warut Suksompong

We study the problem of fairly allocating a divisible resource in the form of a graph, also known as graphical cake cutting.Unlike for the canonical interval cake, a connected envy-free … We study the problem of fairly allocating a divisible resource in the form of a graph, also known as graphical cake cutting.Unlike for the canonical interval cake, a connected envy-free allocation is not guaranteed to exist for a graphical cake.We focus on the existence and computation of connected allocations with low envy.For general graphs, we show that there is always a 1/2-additive-envy-free allocation and, if the agents' valuations are identical, a (2 + ǫ)-multiplicative-envy-free allocation for any ǫ > 0. In the case of star graphs, we obtain a multiplicative factor of 3 + ǫ for arbitrary valuations and 2 for identical valuations.We also derive guarantees when each agent can receive more than one connected piece.All of our results come with efficient algorithms for computing the respective allocations.1 Without this assumption, one cannot obtain nontrivial envy-free guarantees-see the caption of Figure 1 (right) for a brief discussion. 2 Star graphs (and path graphs) are also often studied in the context of indivisible items (see Section 1.2).In graphical cake cutting, all path graphs are equivalent to the classic interval cake, which is why the role of star graphs is further highlighted. 3We discuss further motivation for investigating this case at the beginning of Section 4.

View PDF Chat

Welfare Loss in Connected Resource Allocation

2024-05-06

Xiaohui Bei , Alexander Lam , Xinhang Lu +1 more

We study the allocation of indivisible goods that form an undirected graph and investigate the worst-case welfare loss when requiring that each agent must receive a connected subgraph. Our focus … We study the allocation of indivisible goods that form an undirected graph and investigate the worst-case welfare loss when requiring that each agent must receive a connected subgraph. Our focus is on both egalitarian and utilitarian welfare. Specifically, we introduce the concept of egalitarian (resp., utilitarian) price of connectivity, which captures the worst-case ratio between the optimal egalitarian (resp., utilitarian) welfare among all allocations and that among the connected allocations. We provide tight or asymptotically tight bounds on the price of connectivity for various large classes of graphs when there are two agents as well as for paths, stars and cycles in the general case. Many of our results are supplemented with algorithms which find connected allocations with a welfare guarantee corresponding to the price of connectivity.

View PDF Chat

Complexity of Round-Robin Allocation with Potentially Noisy Queries

2024-04-30

Zihan Li , Pasin Manurangsi , Jonathan Scarlett +1 more

We study the complexity of a fundamental algorithm for fairly allocating indivisible items, the round-robin algorithm. For $n$ agents and $m$ items, we show that the algorithm can be implemented … We study the complexity of a fundamental algorithm for fairly allocating indivisible items, the round-robin algorithm. For $n$ agents and $m$ items, we show that the algorithm can be implemented in time $O(nm\log(m/n))$ in the worst case. If the agents' preferences are uniformly random, we establish an improved (expected) running time of $O(nm + m\log m)$. On the other hand, assuming comparison queries between items, we prove that $\Omega(nm + m\log m)$ queries are necessary to implement the algorithm, even when randomization is allowed. We also derive bounds in noise models where the answers to queries are incorrect with some probability. Our proofs involve novel applications of tools from multi-armed bandit, information theory, as well as posets and linear extensions.

View PDF Chat

Ordinal Maximin Guarantees for Group Fair Division

2024-04-17

Pasin Manurangsi , Warut Suksompong

We investigate fairness in the allocation of indivisible items among groups of agents using the notion of maximin share (MMS). While previous work has shown that no nontrivial multiplicative MMS … We investigate fairness in the allocation of indivisible items among groups of agents using the notion of maximin share (MMS). While previous work has shown that no nontrivial multiplicative MMS approximation can be guaranteed in this setting for general group sizes, we demonstrate that ordinal relaxations are much more useful. For example, we show that if $n$ agents are distributed equally across $g$ groups, there exists a $1$-out-of-$k$ MMS allocation for $k = O(g\log(n/g))$, while if all but a constant number of agents are in the same group, we obtain $k = O(\log n/\log \log n)$. We also establish the tightness of these bounds and provide non-asymptotic results for the case of two groups.

View PDF Chat

Weighted Envy-Freeness for Submodular Valuations

2024-03-24

Luisa Montanari , Ulrike Schmidt-Kraepelin , Warut Suksompong +1 more

We investigate the fair allocation of indivisible goods to agents with possibly different entitlements represented by weights. Previous work has shown that guarantees for additive valuations with existing envy-based notions … We investigate the fair allocation of indivisible goods to agents with possibly different entitlements represented by weights. Previous work has shown that guarantees for additive valuations with existing envy-based notions cannot be extended to the case where agents have matroid-rank (i.e., binary submodular) valuations. We propose two families of envy-based notions for matroid-rank and general submodular valuations, one based on the idea of transferability and the other on marginal values. We show that our notions can be satisfied via generalizations of rules such as picking sequences and maximum weighted Nash welfare. In addition, we introduce welfare measures based on harmonic numbers, and show that variants of maximum weighted harmonic welfare offer stronger fairness guarantees than maximum weighted Nash welfare under matroid-rank valuations.

View PDF Chat

Reachability of Fair Allocations via Sequential Exchanges

2024-03-24

Ayumi Igarashi , Naoyuki Kamiyama , Warut Suksompong +1 more

In the allocation of indivisible goods, a prominent fairness notion is envy-freeness up to one good (EF1). We initiate the study of reachability problems in fair division by investigating the … In the allocation of indivisible goods, a prominent fairness notion is envy-freeness up to one good (EF1). We initiate the study of reachability problems in fair division by investigating the problem of whether one EF1 allocation can be reached from another EF1 allocation via a sequence of exchanges such that every intermediate allocation is also EF1. We show that two EF1 allocations may not be reachable from each other even in the case of two agents, and deciding their reachability is PSPACE-complete in general. On the other hand, we prove that reachability is guaranteed for two agents with identical or binary utilities as well as for any number of agents with identical binary utilities. We also examine the complexity of deciding whether there is an EF1 exchange sequence that is optimal in the number of exchanges required.

View PDF Chat

Envy-free house allocation with minimum subsidy

2024-03-02

Davin Choo , Yan Hao Ling , Warut Suksompong +2 more

House allocation refers to the problem where $m$ houses are to be allocated to $n$ agents so that each agent receives one house. Since an envy-free house allocation does not … House allocation refers to the problem where $m$ houses are to be allocated to $n$ agents so that each agent receives one house. Since an envy-free house allocation does not always exist, we consider finding such an allocation in the presence of subsidy. We show that computing an envy-free allocation with minimum subsidy is NP-hard in general, but can be done efficiently if $m$ differs from $n$ by an additive constant or if the agents have identical utilities.

View PDF Chat

Optimal Budget Aggregation with Single-Peaked Preferences

2024-02-24

Felix Brandt , Matthias Greger , Erel Segal-Halevi +1 more

We study the problem of aggregating distributions, such as budget proposals, into a collective distribution. An ideal aggregation mechanism would be Pareto efficient, strategyproof, and fair. Most previous work assumes … We study the problem of aggregating distributions, such as budget proposals, into a collective distribution. An ideal aggregation mechanism would be Pareto efficient, strategyproof, and fair. Most previous work assumes that agents evaluate budgets according to the $\ell_1$ distance to their ideal budget. We investigate and compare different models from the larger class of star-shaped utility functions - a multi-dimensional generalization of single-peaked preferences. For the case of two alternatives, we extend existing results by proving that under very general assumptions, the uniform phantom mechanism is the only strategyproof mechanism that satisfies proportionality - a minimal notion of fairness introduced by Freeman et al. (2021). Moving to the case of more than two alternatives, we establish sweeping impossibilities for $\ell_1$ and $\ell_\infty$ disutilities: no mechanism satisfies efficiency, strategyproofness, and proportionality. We then propose a new kind of star-shaped utilities based on evaluating budgets by the ratios of shares between a given budget and an ideal budget. For these utilities, efficiency, strategyproofness, and fairness become compatible. In particular, we prove that the mechanism that maximizes the Nash product of individual utilities is characterized by group-strategyproofness and a core-based fairness condition.

View PDF Chat

Topological distance games

2023-10-10

Martin Bullinger , Warut Suksompong

We introduce a class of strategic games in which agents are assigned to nodes of a topology graph and the utility of an agent depends on both the agent's inherent … We introduce a class of strategic games in which agents are assigned to nodes of a topology graph and the utility of an agent depends on both the agent's inherent utilities for other agents as well as her distance from these agents on the topology graph. This model of topological distance games (TDGs) offers an appealing combination of important aspects of several prominent settings in coalition formation, including (additively separable) hedonic games, social distance games, and Schelling games. We study the existence and complexity of stable outcomes in TDGs—for instance, while a jump stable assignment may not exist in general, we show that the existence is guaranteed in several special cases. We also investigate the dynamics induced by performing beneficial jumps.

View PDF Chat

Settling the Score: Portioning with Cardinal Preferences

2023-09-28

Edith Elkind , Warut Suksompong , Nicholas Teh

We study a portioning setting in which a public resource such as time or money is to be divided among a given set of candidates, and each agent proposes a … We study a portioning setting in which a public resource such as time or money is to be divided among a given set of candidates, and each agent proposes a division of the resource. We consider two families of aggregation rules for this setting—those based on coordinate-wise aggregation and those that optimize some notion of welfare—as well as the recently proposed Independent Markets mechanism. We provide a detailed analysis of these rules from an axiomatic perspective, both for classic axioms, such as strategyproofness and Pareto optimality, and for novel axioms, which aim to capture proportionality in this setting. Our results indicate that a simple rule that computes the average of all proposals satisfies many of our axioms, including some that are violated by more sophisticated rules.

View PDF Chat

Incentives in social decision schemes with pairwise comparison preferences

2023-08-18

Felix Brandt , Patrick Lederer , Warut Suksompong

Social decision schemes (SDSs) map the ordinal preferences of voters over multiple alternatives to a probability distribution over the alternatives. To study the axiomatic properties of SDSs, we lift preferences … Social decision schemes (SDSs) map the ordinal preferences of voters over multiple alternatives to a probability distribution over the alternatives. To study the axiomatic properties of SDSs, we lift preferences over alternatives to preferences over lotteries using the natural—but little understood—pairwise comparison (PC) preference extension. This extension postulates that one lottery is preferred to another if the former is more likely to return a preferred outcome. We settle three open questions raised by Brandt (2017) and show that (i) no Condorcet-consistent SDS satisfies PC-strategyproofness; (ii) no anonymous and neutral SDS satisfies both PC-efficiency and PC-strategyproofness; and (iii) no anonymous and neutral SDS satisfies both PC-efficiency and strict PC-participation. We furthermore settle an open problem raised by Aziz et al. (2015) by showing that no path of PC-improvements originating from an inefficient lottery may lead to a PC-efficient lottery.

View PDF Chat

Fair Division with Two-Sided Preferences

2023-08-01

Ayumi Igarashi , Yasushi Kawase , Warut Suksompong +1 more

View PDF Chat

Approximate Envy-Freeness in Graphical Cake Cutting

2023-08-01

Sheung Man Yuen , Warut Suksompong

We study the problem of fairly allocating a divisible resource in the form of a graph, also known as graphical cake cutting. Unlike for the canonical interval cake, a connected … We study the problem of fairly allocating a divisible resource in the form of a graph, also known as graphical cake cutting. Unlike for the canonical interval cake, a connected envy-free allocation is not guaranteed to exist for a graphical cake. We focus on the existence and computation of connected allocations with low envy. For general graphs, we show that there is always a 1/2-additive-envy-free allocation and, if the agents' valuations are identical, a (2+\epsilon)-multiplicative-envy-free allocation for any \epsilon > 0. In the case of star graphs, we obtain a multiplicative factor of 3+\epsilon for arbitrary valuations and 2 for identical valuations. We also derive guarantees when each agent can receive more than one connected piece. All of our results come with efficient algorithms for computing the respective allocations.

View PDF Chat

Balanced Donor Coordination

2023-07-07

Felix Brandt , Matthias Greger , Erel Segal-Halevi +1 more

View PDF Chat

Fairness Concepts for Indivisible Items with Externalities

2023-06-26

Haris Aziz , Warut Suksompong , Zhaohong Sun +1 more

We study a fair allocation problem of indivisible items under additive externalities in which each agent also receives utility from items that are assigned to other agents. This allows us … We study a fair allocation problem of indivisible items under additive externalities in which each agent also receives utility from items that are assigned to other agents. This allows us to capture scenarios in which agents benefit from or compete against one another. We extend the well-studied properties of envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) to this setting, and we propose a new fairness concept called general fair share (GFS), which applies to a more general public decision making model. We undertake a detailed study and present algorithms for finding fair allocations.

View PDF Chat

Approval-Based Voting with Mixed Goods

2023-06-26

Xinhang Lu , Jannik Peters , Haris Aziz +2 more

We consider a voting scenario in which the resource to be voted upon may consist of both indivisible and divisible goods. This generalizes both the well-studied model of multiwinner voting … We consider a voting scenario in which the resource to be voted upon may consist of both indivisible and divisible goods. This generalizes both the well-studied model of multiwinner voting and the recently introduced model of cake sharing. Under approval votes, we propose two variants of the extended justified representation (EJR) notion from multiwinner voting, a stronger one called EJR for mixed goods (EJR-M) and a weaker one called EJR up to 1 (EJR-1). We extend three multiwinner voting rules to our setting—GreedyEJR, the method of equal shares (MES), and proportional approval voting (PAV)—and show that while all three generalizations satisfy EJR-1, only the first one provides EJR-M. In addition, we derive tight bounds on the proportionality degree implied by EJR-M and EJR-1, and investigate the proportionality degree of our proposed rules.

View PDF Chat

Topological Distance Games

2023-06-26

Martin Bullinger , Warut Suksompong

View PDF Chat

Differentially Private Fair Division

2023-06-26

Pasin Manurangsi , Warut Suksompong

Fairness and privacy are two important concerns in social decision-making processes such as resource allocation. We study privacy in the fair allocation of indivisible resources using the well-established framework of … Fairness and privacy are two important concerns in social decision-making processes such as resource allocation. We study privacy in the fair allocation of indivisible resources using the well-established framework of differential privacy. We present algorithms for approximate envy-freeness and proportionality when two instances are considered to be adjacent if they differ only on the utility of a single agent for a single item. On the other hand, we provide strong negative results for both fairness criteria when the adjacency notion allows the entire utility function of a single agent to change.

View PDF Chat

Fixing knockout tournaments with seeds

2023-06-24

Pasin Manurangsi , Warut Suksompong

Knockout tournaments constitute a popular format for organizing sports competitions. While prior results have shown that it is often possible to manipulate a knockout tournament by fixing the bracket, these … Knockout tournaments constitute a popular format for organizing sports competitions. While prior results have shown that it is often possible to manipulate a knockout tournament by fixing the bracket, these results ignore the prevalent aspect of player seeds, which can significantly constrain the chosen bracket. We show that certain structural conditions that guarantee that a player can win a knockout tournament without seeds are no longer sufficient in light of seed constraints. On the other hand, we prove that when the pairwise match outcomes are generated randomly, all players are still likely to be knockout winners under the same probability threshold with seeds as without seeds. In addition, we investigate the complexity of deciding whether a manipulation is possible when seeds are present.

View PDF Chat

Justifying groups in multiwinner approval voting

2023-06-20

Edith Elkind , Piotr Faliszewski , Ayumi Igarashi +3 more

Justified representation (JR) is a standard notion of representation in multiwinner approval voting. Not only does a JR committee always exist, but previous work has also shown through experiments that … Justified representation (JR) is a standard notion of representation in multiwinner approval voting. Not only does a JR committee always exist, but previous work has also shown through experiments that the JR condition can typically be fulfilled by groups of fewer than $k$ candidates. In this paper, we study such groups -- known as $n/k$-justifying groups -- both theoretically and empirically. First, we show that under the impartial culture model, $n/k$-justifying groups of size less than $k/2$ are likely to exist, which implies that the number of JR committees is usually large. We then present efficient approximation algorithms that compute a small $n/k$-justifying group for any given instance, and a polynomial-time exact algorithm when the instance admits a tree representation. In addition, we demonstrate that small $n/k$-justifying groups can often be useful for obtaining a gender-balanced JR committee even though the problem is NP-hard.

View PDF Chat

Keep your distance: Land division with separation

2023-03-14

Edith Elkind , Erel Segal-Halevi , Warut Suksompong

This paper is part of an ongoing endeavor to bring the theory of fair division closer to practice by handling requirements from real-life applications. We focus on two requirements originating … This paper is part of an ongoing endeavor to bring the theory of fair division closer to practice by handling requirements from real-life applications. We focus on two requirements originating from the division of land estates: (1) each agent should receive a plot of a usable geometric shape, and (2) plots of different agents must be physically separated. With these requirements, the classic fairness notion of \emph{proportionality} is impractical, since it may be impossible to attain any multiplicative approximation of it. In contrast, the \emph{ordinal maximin share approximation}, introduced by Budish in 2011, provides meaningful fairness guarantees. We prove upper and lower bounds on achievable maximin share guarantees when the usable shapes are squares, fat rectangles, or arbitrary axis-aligned rectangles, and explore the algorithmic and query complexity of finding fair partitions in this setting. Our work makes use of tools and concepts from computational geometry such as independent sets of rectangles and guillotine partitions.

View PDF Chat

On maximum bipartite matching with separation

2023-03-08

Pasin Manurangsi , Erel Segal-Halevi , Warut Suksompong

Maximum bipartite matching is a fundamental algorithmic problem which can be solved in polynomial time. We consider a natural variant in which there is a separation constraint: the vertices on … Maximum bipartite matching is a fundamental algorithmic problem which can be solved in polynomial time. We consider a natural variant in which there is a separation constraint: the vertices on one side lie on a path or a grid, and two vertices that are close to each other are not allowed to be matched simultaneously. We show that the problem is hard to approximate even for paths, and provide constant-factor approximation algorithms for both paths and grids.

View PDF Chat

Extending the characterization of maximum Nash welfare

2023-02-10

Sheung Man Yuen , Warut Suksompong

In the allocation of indivisible goods, the maximum Nash welfare rule has recently been characterized as the only rule within the class of additive welfarist rules that satisfies envy-freeness up … In the allocation of indivisible goods, the maximum Nash welfare rule has recently been characterized as the only rule within the class of additive welfarist rules that satisfies envy-freeness up to one good. We extend this characterization to the class of all welfarist rules.

View PDF Chat

Cutting a Cake Fairly for Groups Revisited

2023-01-13

Erel Segal-Halevi , Warut Suksompong

Cake cutting is a classic fair division problem, with the cake serving as a metaphor for a heterogeneous divisible resource. Recently, it was shown that for any number of players … Cake cutting is a classic fair division problem, with the cake serving as a metaphor for a heterogeneous divisible resource. Recently, it was shown that for any number of players with arbitrary preferences over a cake, it is possible to partition the players into groups of any desired size and divide the cake among the groups so that each group receives a single contiguous piece and every player is envy-free. For two groups, we characterize the group sizes for which such an assignment can be computed by a finite algorithm, showing that the task is possible exactly when one of the groups is a singleton. We also establish an analogous existence result for chore division, and show that the result does not hold for a mixed cake.

View PDF Chat

Extending the Characterization of Maximum Nash Welfare

2023-01-01

Sheung Man Yuen , Warut Suksompong

View PDF Chat

On Maximum Bipartite Matching with Separation

2023-01-01

Pasin Manurangsi , Erel Segal-Halevi , Warut Suksompong

Weighted Fair Division with Matroid-Rank Valuations: Monotonicity and Strategyproofness

2023-01-01

Warut Suksompong , Nicholas Teh

We study the problem of fairly allocating indivisible goods to agents with weights corresponding to their entitlements. Previous work has shown that, when agents have binary additive valuations, the maximum … We study the problem of fairly allocating indivisible goods to agents with weights corresponding to their entitlements. Previous work has shown that, when agents have binary additive valuations, the maximum weighted Nash welfare rule is resource-, population-, and weight-monotone, satisfies group-strategyproofness, and can be implemented in polynomial time. We generalize these results to the class of weighted additive welfarist rules with concave functions and agents with matroid-rank (also known as binary submodular) valuations.

Approximate Envy-Freeness in Graphical Cake Cutting

2023-01-01

Sheung Man Yuen , Warut Suksompong

We study the problem of fairly allocating a divisible resource in the form of a graph, also known as graphical cake cutting. Unlike for the canonical interval cake, a connected … We study the problem of fairly allocating a divisible resource in the form of a graph, also known as graphical cake cutting. Unlike for the canonical interval cake, a connected envy-free allocation is not guaranteed to exist for a graphical cake. We focus on the existence and computation of connected allocations with low envy. For general graphs, we show that there is always a $1/2$-additive-envy-free allocation and, if the agents' valuations are identical, a $(2+\epsilon)$-multiplicative-envy-free allocation for any $\epsilon > 0$. In the case of star graphs, we obtain a multiplicative factor of $3+\epsilon$ for arbitrary valuations and $2$ for identical valuations. We also derive guarantees when each agent can receive more than one connected piece. All of our results come with efficient algorithms for computing the respective allocations.

View PDF Chat

Balanced Donor Coordination

2023-01-01

Felix Brandt , Matthias Greger , Erel Segal-Halevi +1 more

Charity is typically done either by individual donors, who donate money to the charities that they support, or by centralized organizations such as governments or municipalities, which collect the individual … Charity is typically done either by individual donors, who donate money to the charities that they support, or by centralized organizations such as governments or municipalities, which collect the individual contributions and distribute them among a set of charities. On the one hand, individual charity respects the will of the donors but may be inefficient due to a lack of coordination. On the other hand, centralized charity is potentially more efficient but may ignore the will of individual donors. We present a mechanism that combines the advantages of both methods by distributing the contribution of each donor in an efficient way such that no subset of donors has an incentive to redistribute their donations. Assuming Leontief utilities (i.e., each donor is interested in maximizing an individually weighted minimum of all contributions across the charities), our mechanism is group-strategyproof, preference-monotonic, contribution-monotonic, maximizes Nash welfare, and can be computed using convex programming.

View PDF Chat

Settling the Score: Portioning with Cardinal Preferences

2023-01-01

Edith Elkind , Warut Suksompong , Nicholas Teh

We study a portioning setting in which a public resource such as time or money is to be divided among a given set of candidates, and each agent proposes a … We study a portioning setting in which a public resource such as time or money is to be divided among a given set of candidates, and each agent proposes a division of the resource. We consider two families of aggregation rules for this setting - those based on coordinate-wise aggregation and those that optimize some notion of welfare - as well as the recently proposed Independent Markets mechanism. We provide a detailed analysis of these rules from an axiomatic perspective, both for classic axioms, such as strategyproofness and Pareto optimality, and for novel axioms, which aim to capture proportionality in this setting. Our results indicate that a simple rule that computes the average of all proposals satisfies many of our axioms, including some that are violated by more sophisticated rules.

View PDF Chat

Reachability of Fair Allocations via Sequential Exchanges

2023-01-01

Ayumi Igarashi , Naoyuki Kamiyama , Warut Suksompong +1 more

View PDF Chat

A characterization of maximum Nash welfare for indivisible goods

2022-12-08

Warut Suksompong

In the allocation of indivisible goods, the maximum Nash welfare (MNW) rule, which chooses an allocation maximizing the product of the agents' utilities, has received substantial attention for its fairness. … In the allocation of indivisible goods, the maximum Nash welfare (MNW) rule, which chooses an allocation maximizing the product of the agents' utilities, has received substantial attention for its fairness. We characterize MNW as the only additive welfarist rule that satisfies envy-freeness up to one good. Our characterization holds even in the simplest setting of two agents.

View PDF Chat

Mind the gap: Cake cutting with separation

2022-09-09

Edith Elkind , Erel Segal-Halevi , Warut Suksompong

View PDF Chat

Almost envy-freeness for groups: Improved bounds via discrepancy theory

2022-08-04

Pasin Manurangsi , Warut Suksompong

We study the allocation of indivisible goods among groups of agents using well-known fairness notions such as envy-freeness and proportionality. While these notions cannot always be satisfied, we provide several … We study the allocation of indivisible goods among groups of agents using well-known fairness notions such as envy-freeness and proportionality. While these notions cannot always be satisfied, we provide several bounds on the optimal relaxations that can be guaranteed. For instance, our bounds imply that when the number of groups is constant and the n agents are divided into groups arbitrarily, there exists an allocation that is envy-free up to Θ(n) goods, and this bound is tight. Moreover, we show that while such an allocation can be found efficiently, it is NP-hard to compute an allocation that is envy-free up to o(n) goods even when a fully envy-free allocation exists. Our proofs make extensive use of tools from discrepancy theory.

View PDF Chat

Incentives in Social Decision Schemes with Pairwise Comparison Preferences

2022-07-01

Felix Brandt , Patrick Lederer , Warut Suksompong

Social decision schemes (SDSs) map the preferences of individual voters over multiple alternatives to a probability distribution over the alternatives. In order to study properties such as efficiency, strategyproofness, and … Social decision schemes (SDSs) map the preferences of individual voters over multiple alternatives to a probability distribution over the alternatives. In order to study properties such as efficiency, strategyproofness, and participation for SDSs, preferences over alternatives are typically lifted to preferences over lotteries using the notion of stochastic dominance (SD). However, requiring strategyproofness or strict participation with respect to this preference extension only leaves room for rather undesirable SDSs such as random dictatorships. Hence, we focus on the natural but little understood pairwise comparison (PC) preference extension, which postulates that one lottery is preferred to another if the former is more likely to return a preferred outcome. In particular, we settle three open questions raised by Brandt in Rolling the dice: Recent results in probabilistic social choice (2017): (i) there is no Condorcet-consistent SDS that satisfies PC-strategyproofness; (ii) there is no anonymous and neutral SDS that satisfies PC-efficiency and PC-strategyproofness; and (iii) there is no anonymous and neutral SDS that satisfies PC-efficiency and strict PC-participation. All three impossibilities require m>=4 alternatives and turn into possibilities when m<=3.

View PDF Chat

Fixing Knockout Tournaments With Seeds

2022-07-01

Pasin Manurangsi , Warut Suksompong

View PDF Chat

Weighted Fairness Notions for Indivisible Items Revisited

2022-06-28

Mithun Chakraborty , Erel Segal-Halevi , Warut Suksompong

View PDF Chat

The Price of Justified Representation

2022-06-28

Edith Elkind , Piotr Faliszewski , Ayumi Igarashi +3 more

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

Generalized kings and single-elimination winners in random tournaments

2022-04-27

Pasin Manurangsi , Warut Suksompong

Abstract Tournaments can be used to model a variety of practical scenarios including sports competitions and elections. A natural notion of strength of alternatives in a tournament is a generalized … Abstract Tournaments can be used to model a variety of practical scenarios including sports competitions and elections. A natural notion of strength of alternatives in a tournament is a generalized king: an alternative is said to be a k - king if it can reach every other alternative in the tournament via a directed path of length at most k . In this paper, we provide an almost complete characterization of the probability threshold such that all, a large number, or a small number of alternatives are k -kings with high probability in two random models. We show that, perhaps surprisingly, all changes in the threshold occur in the range of constant k , with the biggest change being between $$k=2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>=</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> and $$k=3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>=</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> . In addition, we establish an asymptotically tight bound on the probability threshold for which all alternatives are likely able to win a single-elimination tournament under some bracket.

View PDF Chat

On maximum weighted Nash welfare for binary valuations

2022-04-07

Warut Suksompong , Nicholas Teh

View PDF Chat

Consensus Halving for Sets of Items

2022-02-10

Paul W. Goldberg , Alexandros Hollender , Ayumi Igarashi +2 more

View PDF Chat

Justifying Groups in Multiwinner Approval Voting

2022-01-01

Edith Elkind , Piotr Faliszewski , Ayumi Igarashi +3 more

View PDF Chat

Coauthor	Papers Together
Pasin Manurangsi	36
Erel Segal-Halevi	22
Edith Elkind	20
Ayumi Igarashi	18
Ulrike Schmidt-Kraepelin	16
Xiaohui Bei	13
Felix Brandt	12
Xinhang Lu	10
Sheung Man Yuen	9
Mithun Chakraborty	8
Markus Brill	7
Piotr Faliszewski	7
Nicholas Teh	7
Alexandros A. Voudouris	7
Ayumi Igarashi	6
Martin Bullinger	5
Paul W. Goldberg	5
Alexandros Hollender	5
Haris Aziz	4
Naoyuki Kamiyama	4
Matthias Greger	4
Patrick Lederer	4
Jiarui Gan	3
Yasushi Kawase	3
Michal Feldman	3
Tim Roughgarden	3
Yair Zick	3
Tomer Ezra	3
Hanna Sumita	3
Florian Brandl	3
Peter Key	3
Ian A. Kash	3
Charles E. Leiserson	2
Hoon Oh	2
Alexander Lam	2
Guangda Huzhang	2
Dominik Peters	2
Tao B. Schardl	2
Christian Stricker	2
Christian Saile	2
Rik Sengupta	2
Michael P. Kim	2
Ariel D. Procaccia	2
Virginia Vassilevska Williams	2
Sebastian A. Csar	2
Zhaohong Sun	2
Toby Walsh	2
Luisa Montanari	2
Jannik Peters	2
Maria Kyropoulou	2

Asymptotic existence of fair divisions for groups

2017-07-08

Pasin Manurangsi , Warut Suksompong

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

Approximate maximin shares for groups of agents

2017-09-22

Warut Suksompong

View PDF Chat

Weighted Envy-freeness in Indivisible Item Allocation

2021-08-16

Mithun Chakraborty , Ayumi Igarashi , Warut Suksompong +1 more

View PDF Chat

Fairly allocating contiguous blocks of indivisible items

2019-02-22

Warut Suksompong

View PDF Chat

Almost envy-freeness in group resource allocation

2020-07-15

Maria Kyropoulou , Warut Suksompong , Alexandros A. Voudouris

View PDF Chat

Democratic fair allocation of indivisible goods

2019-09-03

Erel Segal-Halevi , Warut Suksompong

View PDF Chat

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

Envy-Free Cake Divisions Cannot be Found by Finite Protocols

2008-01-07

Walter Stromquist

We show that no finite protocol (even if unbounded) can guarantee an envy-free division of a cake among three or more players, if each player is to receive a single … We show that no finite protocol (even if unbounded) can guarantee an envy-free division of a cake among three or more players, if each player is to receive a single connected piece.

View PDF Chat

Fair Public Decision Making

2017-06-20

Vincent Conitzer , Rupert Freeman , Nisarg Shah

We generalize the classic problem of fairly allocating indivisible goods to the problem of fair public decision making, in which a decision must be made on several social issues simultaneously, … We generalize the classic problem of fairly allocating indivisible goods to the problem of fair public decision making, in which a decision must be made on several social issues simultaneously, and, unlike the classic setting, a decision can provide positive utility to multiple players. We extend the popular fairness notion of proportionality (which is not guaranteeable) to our more general setting, and introduce three novel relaxations --- proportionality up to one issue, round robin share, and pessimistic proportional share --- that are also interesting in the classic goods allocation setting. We show that the Maximum Nash Welfare solution, which is known to satisfy appealing fairness properties in the classic setting, satisfies or approximates all three relaxations in our framework. We also provide polynomial time algorithms and hardness results for finding allocations satisfying these axioms, with or without insisting on Pareto optimality.

View PDF Chat

Comparing Approximate Relaxations of Envy-Freeness

2018-07-01

Georgios Amanatidis , Georgios Birmpas , Vangelis Markakis

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

View PDF Chat

Fair Division Under Cardinality Constraints

2018-07-01

Arpita Biswas , Siddharth Barman

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

View PDF Chat

Contiguous Cake Cutting: Hardness Results and Approximation Algorithms

2020-09-22

Paul W. Goldberg , Alexandros Hollender , Warut Suksompong

View PDF Chat

Finding Fair and Efficient Allocations

2018-06-11

Siddharth Barman , Sanath Kumar Krishnamurthy , Rohit Vaish

We study the problem of allocating a set of indivisible goods among a set of agents in a fair and efficient manner. An allocation is said to be fair if … We study the problem of allocating a set of indivisible goods among a set of agents in a fair and efficient manner. An allocation is said to be fair if it is envy-free up to one good (EF1), which means that each agent prefers its own bundle over the bundle of any other agent up to the removal of one good. In addition, an allocation is deemed efficient if it satisfies Pareto efficiency. While each of these well-studied properties is easy to achieve separately, achieving them together is far from obvious. Recently, Caragiannis et al. (2016) established the surprising result that when agents have additive valuations for the goods, there always exists an allocation that simultaneously satisfies these two seemingly incompatible properties. Specifically, they showed that an allocation that maximizes the Nash social welfare objective is both EF1 and Pareto efficient. However, the problem of maximizing Nash social welfare is NP-hard. As a result, this approach does not provide an efficient algorithm for finding a fair and efficient allocation. In this paper, we bypass this barrier, and develop a pseudopolynomial time algorithm for finding allocations that are EF1 and Pareto efficient; in particular, when the valuations are bounded, our algorithm finds such an allocation in polynomial time. Furthermore, we establish a stronger existence result compared to Caragiannis et al. (2016): For additive valuations, there always exists an allocation that is EF1 and fractionally Pareto efficient. Another key contribution of our work is to show that our algorithm provides a polynomial-time 1.45-approximation to the Nash social welfare objective. This improves upon the best known approximation ratio for this problem (namely, the 2-approximation algorithm of Cole et al., 2017), and also matches the lower bound on the integrality gap of the convex program of Cole et al. (2017). Unlike many of the existing approaches, our algorithm is completely combinatorial, and relies on constructing integral Fisher markets wherein specific equilibria are not only efficient, but also fair.

View PDF Chat

Mind the gap: Cake cutting with separation

2022-09-09

Edith Elkind , Erel Segal-Halevi , Warut Suksompong

View PDF Chat

The Price of Connectivity in Fair Division

2021-05-18

Xiaohui Bei , Ayumi Igarashi , Xinhang Lu +1 more

View PDF Chat

Fairly Allocating Many Goods with Few Queries

2019-07-17

Hoon Oh , Ariel D. Procaccia , Warut Suksompong

View PDF Chat

How to Cut a Cake Fairly: A Generalization to Groups

2021-01-02

Erel Segal-Halevi , Warut Suksompong

View PDF Chat

The Price of Fairness for Indivisible Goods

2019-07-28

Xiaohui Bei , Xinhang Lu , Pasin Manurangsi +1 more

View PDF Chat

Who Can Win a Single-Elimination Tournament?

2017-01-01

Michael P. Kim , Warut Suksompong , Virginia Vassilevska Williams

View PDF Chat

Competitive Equilibrium with Indivisible Goods and Generic Budgets

2021-01-27

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 1967, Varian 1974). Every agent receives an equal budget … Competitive equilibrium from equal incomes (CEEI) is a classic solution to the problem of fair and efficient allocation of goods (Foley 1967, Varian 1974). 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 equilibrium. We further consider agents with arbitrary nonequal budgets, representing nonequal entitlements for goods. We show that competitive equilibrium guarantees a new notion of fairness among nonequal agents and that it exists in cases of interest (such as 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 nonequals.

View PDF Chat

Consensus-halving via theorems of Borsuk-Ulam and Tucker

2003-02-01

Forest W. Simmons , Francis Edward Su

View PDF Chat

Fair division of graphs and of tangled cakes

2023-04-15

Ayumi Igarashi , William S. Zwicker

Abstract Fair division has been studied in both continuous and discrete contexts. One strand of the continuous literature seeks to award each agent with a single connected piece—a subinterval. The … Abstract Fair division has been studied in both continuous and discrete contexts. One strand of the continuous literature seeks to award each agent with a single connected piece—a subinterval. The analogue for the discrete case corresponds to the fair division of a graph , where allocations must be contiguous so that each bundle of vertices is required to induce a connected subgraph. With envy-freeness up to one item ( EF1 ) as the fairness criterion, however, positive results for three or more agents have mostly been limited to traceable graphs. We introduce tangles as a new context for fair division. A tangle is a more complicated cake—a connected topological space constructed by gluing together several copies of the unit interval [0, 1]—and each single tangle $$\mathcal {T}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>T</mml:mi> </mml:math> corresponds in a natural way to an infinite topological class $$\mathcal {G}(\mathcal {T})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>(</mml:mo> <mml:mi>T</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> of graphs, linking envy-free fair division of tangles to EF k fair division of graphs. In addition to the unit interval itself, we show that only five other stringable tangles guarantee the existence of envy-free and connected allocations for arbitrarily many agents, with the corresponding topological classes containing only traceable graphs. Any other tangle $$\mathcal {T}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>T</mml:mi> </mml:math> has a bound r on the number of agents for which such allocations necessarily exist, and our Negative Transfer Principle then applies to the graphs in $$\mathcal {T}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>T</mml:mi> </mml:math> ’s class; for any integer $$k \ge 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> , almost all graphs in this class are non-traceable and fail to guarantee EF k contiguous allocations for $$r + 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> or more agents, even when very strict requirements are placed on the valuation functions for the agents. With bounds on the number of agents, however, we obtain positive results for some non-stringable classes. An elaboration of Stromquist’s moving knife procedure shows that the non-stringable lips tangle $$\mathcal {L}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>L</mml:mi> </mml:math> guarantees envy-free allocations of connected shares for three agents. We then modify the discrete version of Stromquist’s procedure in Bilò et al. (Games Econ Behav 131:197–221, 2022) to show that all graphs in the topological class $$\mathcal {G}(\mathcal {L})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>(</mml:mo> <mml:mi>L</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> (most of which are non-traceable) guarantee EF1 allocations for three agents.

View PDF Chat

Almost envy-free allocations with connected bundles

2021-11-30

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

View PDF Chat

A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents

2016-10-01

Haris Aziz , Simon Mackenzie

We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation based on queries from n agents. The problem has received attention in computer … We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation based on queries from n agents. The problem has received attention in computer science, mathematics, and economics. It has been a major open problem whether there exists a discrete and bounded envy-free protocol. We resolve the problem by proposing a discrete and bounded envy-free protocol for any number of agents. The maximum number of queries required by the protocol is nnnnnn. Even if we do not run our protocol to completion, it can find in at most n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n+1</sup> queries an envy-free partial allocation of the cake in which each agent gets at least 1/n of the value of the whole cake.

View PDF Chat

A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation

2020-07-09

Haris Aziz , Hervé Moulin , Fedor Sandomirskiy

View PDF Chat

Picking sequences and monotonicity in weighted fair division

2021-08-13

Mithun Chakraborty , Ulrike Schmidt-Kraepelin , Warut Suksompong

View PDF Chat

Pareto-Optimal Allocation of Indivisible Goods with Connectivity Constraints

2019-07-17

Ayumi Igarashi , Dominik Peters

We study the problem of allocating indivisible items to agents with additive valuations, under the additional constraint that bundles must be connected in an underlying item graph. Previous work has … We study the problem of allocating indivisible items to agents with additive valuations, under the additional constraint that bundles must be connected in an underlying item graph. Previous work has considered the existence and complexity of fair allocations. We study the problem of finding an allocation that is Pareto-optimal. While it is easy to find an efficient allocation when the underlying graph is a path or a star, the problem is NP-hard for many other graph topologies, even for trees of bounded pathwidth or of maximum degree 3. We show that on a path, there are instances where no Pareto-optimal allocation satisfies envy-freeness up to one good, and that it is NP-hard to decide whether such an allocation exists, even for binary valuations. We also show that, for a path, it is NP-hard to find a Pareto-optimal allocation that satisfies maximin share, but show that a moving-knife algorithm can find such an allocation when agents have binary valuations that have a non-nested interval structure.

View PDF Chat

On the computability of equitable divisions

2012-08-20

Katarı́na Cechlárová , Eva Pillárová

On the structure of stable tournament solutions

2016-12-23

Felix Brandt , Markus Brill , Hans Georg Seedig +1 more

View PDF Chat

Almost Envy-Freeness in Group Resource Allocation

2019-07-28

Maria Kyropoulou , Warut Suksompong , Alexandros A. Voudouris

View PDF Chat

Fair Division Under Cardinality Constraints

2018-04-25

Siddharth Barman , Arpita Biswas

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

Justified representation in approval-based committee voting

2017-01-09

Haris Aziz , Markus Brill , Vincent Conitzer +3 more

View PDF Chat

Democratic Fair Allocation of Indivisible Goods

2018-07-01

Erel Segal-Halevi , Warut Suksompong

View PDF Chat

Cake-cutting with different entitlements: How many cuts are needed?

2019-08-05

Erel Segal-Halevi

View PDF Chat

Graphical Cake Cutting via Maximin Share

2021-08-01

Edith Elkind , Erel Segal-Halevi , Warut Suksompong

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

Schelling Segregation with Strategic Agents

2018-01-01

Ankit Chauhan , Pascal Lenzner , Louise Molitor

View PDF Chat

Fair and square: Cake-cutting in two dimensions

2017-02-09

Erel Segal-Halevi , Shmuel Nitzan , Avinatan Hassidim +1 more

View PDF Chat

Fair cake-cutting among families

2019-08-12

Erel Segal-Halevi , Shmuel Nitzan

View PDF Chat

Maximin Share Allocations on Cycles

2020-10-29

Mirosław Truszczyński , Zbigniew Lonc

   The problem of fair division of indivisible goods is a fundamental problem of resource allocation in multi-agent systems, also studied extensively in social choice. Recently, the problem …    The problem of fair division of indivisible goods is a fundamental problem of resource allocation in multi-agent systems, also studied extensively in social choice. Recently, the problem was generalized to the case when goods form a graph and the goal is to allocate goods to agents so that each agent’s bundle forms a connected subgraph. For the maximin share fairness criterion, researchers proved that if goods form a tree, an allocation offering each agent a bundle of at least her maximin share value always exists. Moreover, it can be found in polynomial time. In this paper we consider the problem of maximin share allocations of goods on a cycle. Despite the simplicity of the graph, the problem turns out to be significantly harder than its tree version. We present cases when maximin share allocations of goods on cycles exist and provide in this case results on allocations guaranteeing each agent a certain fraction of her maximin share. We also study algorithms for computing maximin share allocations of goods on cycles.  

View PDF Chat

Welfare Guarantees in Schelling Segregation

2021-05-29

Martin Bullinger , Warut Suksompong , Alexandros A. Voudouris

View PDF Chat

The Complexity of Cake Cutting with Unequal Shares

2020-06-06

Ágnes Cseh , Tamás Fleiner

An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among … An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among n players who value pieces according to their own measure function. The goal is to assign each player a not necessarily connected part of the cake that the player evaluates at least as much as her proportional share. In this article, we investigate the problem of proportional division with unequal shares, where each player is entitled to receive a predetermined portion of the cake. Our main contribution is threefold. First we present a protocol for integer demands, which delivers a proportional solution in fewer queries than all known protocols. By giving a matching lower bound, we then show that our protocol is asymptotically the fastest possible. Finally, we turn to irrational demands and solve the proportional cake cutting problem by reducing it to the same problem with integer demands only. All results remain valid in a highly general cake cutting model, which can be of independent interest.

View PDF Chat

Refining Tournament Solutions via Margin of Victory

2020-04-03

Markus Brill , Ulrike Schmidt-Kraepelin , Warut Suksompong

View PDF Chat

Fair and Efficient Cake Division with Connected Pieces

2019-01-01

Eshwar Ram Arunachaleswaran , Siddharth Barman , Rachitesh Kumar +1 more

View PDF Chat

Robust bounds on choosing from large tournaments

2019-08-23

Christian Saile , Warut Suksompong

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

Asymptotic existence of proportionally fair allocations

2016-03-24

Warut Suksompong

View PDF Chat

Consensus halving is PPA-complete

2018-06-20

Aris Filos-Ratsikas , Paul W. Goldberg

We show that the computational problem Consensus Halving is PPA-Complete, the first PPA-Completeness result for a problem whose definition does not involve an explicit circuit. We also show that an … We show that the computational problem Consensus Halving is PPA-Complete, the first PPA-Completeness result for a problem whose definition does not involve an explicit circuit. We also show that an approximate version of this problem is polynomial-time equivalent to Necklace Splitting, which establishes PPAD-hardness for Necklace Splitting and suggests that it is also PPA-Complete.

View PDF Chat

Weighted Envy-Freeness in Indivisible Item Allocation

2020-05-05

Mithun Chakraborty , Ayumi Igarashi , Warut Suksompong +1 more