Warut Suksompong

AAMAS Conference 2026 Conference Paper

Comparing the Fairness of Recursively Balanced Picking Sequences

• Karen Frilya Celine
• Warut Suksompong
• Sheung Man Yuen

Picking sequences are well-established methods for allocating indivisible goods. Among the various picking sequences, recursively balanced picking sequences—whereby each agent picks one good in every round—are notable for guaranteeing allocations that satisfy envy-freeness up to one good. In this paper, we compare the fairness of different recursively balanced picking sequences using two key measures. Firstly, we demonstrate that all such sequences have the same price in terms of egalitarian welfare relative to other picking sequences. Secondly, we characterize the approximate maximin share (MMS) guarantees of these sequences. In particular, we show that compensating the agent who picks last in the first round by letting her pick first in every subsequent round yields the best MMS guarantee.

AAAI Conference 2026 Conference Paper

Fair Allocation of Indivisible Goods with Variable Groups

• Paul Gölz
• Ayumi Igarashi
• Pasin Manurangsi
• Warut Suksompong

We study the fair allocation of indivisible goods with variable groups. In this model, the goal is to partition the agents into groups of given sizes and allocate the goods to the groups in a fair manner. We show that for any number of groups and corresponding sizes, there always exists an envy-free up to one good (EF1) outcome, thereby generalizing an important result from the individual setting. Our result holds for arbitrary monotonic utilities and comes with an efficient algorithm. We also prove that an EF1 outcome is guaranteed to exist even when the goods lie on a path and each group must receive a connected bundle. In addition, we consider a probabilistic model where the utilities are additive and drawn randomly from a distribution. We show that if there are n agents and the number of goods m is divisible by the number of groups k, then an envy-free outcome exists with high probability if m = ω(log n), and this bound is tight. On the other hand, if m is not divisible by k, then an envy-free outcome is unlikely to exist as long as m = o(√n).

AAAI Conference 2026 Conference Paper

Reconfiguring Proportional Committees

• Chris Dong
• Fabian Frank
• Jannik Peters
• Warut Suksompong

An important desideratum in approval-based multiwinner voting is proportionality. We study the problem of reconfiguring proportional committees: given two proportional committees, is there a transition path that consists only of proportional committees, where each transition involves replacing one candidate with another candidate? We show that the set of committees satisfying the proportionality axiom of justified representation (JR) is not always connected, and it is PSPACE-complete to decide whether two such committees are connected. On the other hand, we prove that any two JR committees can be connected by committees satisfying a 2-approximation of JR. We also obtain similar results for the stronger axiom of extended justified representation (EJR). In addition, we demonstrate that the committees produced by several well-known voting rules are connected or at least not isolated, and investigate the reconfiguration problem in restricted preference domains.

AIJ Journal 2026 Journal Article

Settling the score: Portioning with cardinal preferences

• Edith Elkind
• Matthias Greger
• Patrick Lederer
• 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 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 rule. 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, some of which aim to capture proportionality in this setting. Our results indicate that a simple rule that computes the average of the proposals satisfies many of our axioms and fares better than all other considered rules in terms of fairness properties. We complement these results by presenting two characterizations of the average rule.

AAAI Conference 2026 Conference Paper

Voting in Divisible Settings: A Survey

• Warut Suksompong
• Nicholas Teh

Voting is one of the most prominent applications of preference aggregation and computational social choice. While much of the literature focuses on models involving discrete candidates, there has been a growing interest in voting over divisible resources, such as budget, space, and time. In this survey, we review existing work on voting in divisible settings, including fundamental models of budget aggregation, fair mixing, and cake sharing. We also establish connections among these models, highlight unifying themes across different frameworks, and suggest directions for future research.

IJCAI Conference 2025 Conference Paper

Asymptotic Analysis of Weighted Fair Division

• Pasin Manurangsi
• Warut Suksompong
• Tomohiko Yokoyama

Several resource allocation settings involve agents with unequal entitlements represented by weights. We analyze weighted fair division from an asymptotic perspective: if m items are divided among n agents whose utilities are independently sampled from a probability distribution, when is it likely that a fair allocation exist? We show that if the ratio between the weights is bounded, a weighted envy-free allocation exists with high probability provided that m = Omega(n log n / log log n), generalizing a prior unweighted result. For weighted proportionality, we establish a sharp threshold of m = n / (1 - \mu) for the transition from non-existence to existence, where \mu in (0, 1) denotes the mean of the distribution. In addition, we prove that for two agents, a weighted envy-free (and weighted proportional) allocation is likely to exist if m = omega(sqrt{r}), where r denotes the ratio between the two weights.

TCS Journal 2025 Journal Article

Asymptotic analysis of weighted fair division

• Pasin Manurangsi
• Warut Suksompong
• Tomohiko Yokoyama

Several resource allocation settings involve agents with unequal entitlements represented by weights. We analyze weighted fair division from an asymptotic perspective: if m items are divided among n agents whose utilities are independently sampled from a probability distribution, when is it likely that a fair allocation exist? We show that if the ratio between the weights is bounded, a weighted envy-free allocation exists with high probability provided that m = Ω ( n log n / log log n ), generalizing a prior unweighted result. For weighted proportionality, we establish a sharp threshold of m = n / ( 1 − μ ) for the transition from non-existence to existence, where μ ∈ ( 0, 1 ) denotes the mean of the distribution. In addition, we prove that for two agents, a weighted envy-free (and weighted proportional) allocation is likely to exist if m = ω ( r ), where r denotes the ratio between the two weights.

IJCAI Conference 2025 Conference Paper

Asymptotic Fair Division: Chores Are Easier Than Goods

• Pasin Manurangsi
• Warut Suksompong

When dividing items among agents, two of the most widely studied fairness notions are envy-freeness and proportionality. We consider a setting where m chores are allocated to n agents and the disutility of each chore for each agent is drawn from a probability distribution. We show that an envy-free allocation exists with high probability provided that m >= 2n, and moreover, m must be at least n+Theta(n) in order for the existence to hold. On the other hand, we prove that a proportional allocation is likely to exist as long as m = omega(1), and this threshold is asymptotically tight. Our results reveal a clear contrast with the allocation of goods, where a larger number of items is necessary to ensure existence for both notions.

I&C Journal 2025 Journal Article

Complexity of round-robin allocation with potentially noisy queries

• Zihan Li
• Pasin Manurangsi
• Jonathan Scarlett
• Warut Suksompong

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 ( n m log ⁡ ( m / n ) ) in the worst case. If the agents' preferences are uniformly random, we establish an improved (expected) running time of O ( n m + m log ⁡ m ). On the other hand, assuming comparison queries between items, we prove that Ω ( n m + 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 bandits, information theory, as well as posets and linear extensions.

AIJ Journal 2025 Journal Article

Differentially private fair division

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

IJCAI Conference 2025 Conference Paper

Discrete Budget Aggregation: Truthfulness and Proportionality

• Ulrike Schmidt-Kraepelin
• Warut Suksompong
• Markus Utke

We study a budget aggregation setting where voters express their preferred allocation of a fixed budget over a set of alternatives, and a mechanism aggregates these preferences into a single output allocation. Motivated by scenarios in which the budget is not perfectly divisible, we depart from the prevailing literature by restricting the mechanism to output allocations that assign integral amounts. This seemingly minor deviation has significant implications for the existence of truthful mechanisms. Specifically, when voters can propose fractional allocations, we demonstrate that the Gibbard-Satterthwaite theorem can be extended to our setting. In contrast, when voters are restricted to integral ballots, we identify a class of truthful mechanisms by adapting moving-phantom mechanisms to our context. Finally, we show that while a weak form of proportionality can be achieved alongside truthfulness, stronger proportionality notions derived from approval-based committee voting are incompatible with truthfulness.

AAMAS Conference 2025 Conference Paper

On the Fairness of Additive Welfarist Rules

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

TCS Journal 2025 Journal Article

Ordinal maximin guarantees for group fair division

• 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 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. Our proofs leverage connections to combinatorial covering designs.

IJCAI Conference 2025 Conference Paper

The Proportional Veto Principle for Approval Ballots

• Daniel Halpern
• Ariel D. Procaccia
• Warut Suksompong

The proportional veto principle, which captures the idea that a candidate vetoed by a large group of voters should not be chosen, has been studied for ranked ballots in single-winner voting. We introduce a version of this principle for approval ballots, which we call flexible-voter representation (FVR). We show that while the approval voting rule and other natural scoring rules provide the optimal FVR guarantee only for some flexibility threshold, there exists a scoring rule that is FVR-optimal for all thresholds simultaneously. We also extend our results to multi-winner voting.

IJCAI Conference 2024 Conference Paper

Expanding the Reach of Social Choice Theory

• Warut Suksompong

The field of social choice theory investigates how individual preferences are aggregated to reach collective decisions. While traditional social choice addresses problems such as choosing a winning candidate based on voter rankings or fairly allocating resources among individuals with the same entitlement, the wide range of decision-making scenarios in real-world applications calls for an extension beyond these basic frameworks. In this paper, I present an overview of my efforts to expand the reach of social choice theory in the domains of fair division, voting, and tournaments. Furthermore, I discuss avenues and challenges of bringing the developed theory closer to practice.

AAAI Conference 2024 System Paper

Fast & Fair: A Collaborative Platform for Fair Division Applications

• Jiatong Han
• Warut Suksompong

Fair division, the study of how to fairly allocate resources among agents, has received substantial interest in the areas of artificial intelligence and multiagent systems. While there is an extensive theoretical literature on fair division by now, the developed algorithms are still mostly confined to research papers and inaccessible to the public. We attempt to bridge this gap by developing Fast & Fair, an open-source web application that hosts a number of fair allocation algorithms with user-friendly interfaces and explainable outcomes. In contrast to existing implementations, Fast & Fair is a collaborative platform that is open to community contributions and thereby facilitates the deployment of additional algorithms.

IJCAI Conference 2024 Conference Paper

Ordinal Maximin Guarantees for Group Fair Division

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

AAAI Conference 2024 Conference Paper

Reachability of Fair Allocations via Sequential Exchanges

• Ayumi Igarashi
• Naoyuki Kamiyama
• Warut Suksompong
• Sheung Man Yuen

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.

TCS Journal 2024 Journal Article

Topological distance games

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

AAAI Conference 2024 Conference Paper

Weighted Envy-Freeness for Submodular Valuations

• Luisa Montanari
• Ulrike Schmidt-Kraepelin
• Warut Suksompong
• Nicholas Teh

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.

IJCAI Conference 2024 Conference Paper

Welfare Loss in Connected Resource Allocation

• Xiaohui Bei
• Alexander Lam
• Xinhang Lu
• Warut Suksompong

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.

AAAI Conference 2023 Conference Paper

Approval-Based Voting with Mixed Goods

• Xinhang Lu
• Jannik Peters
• Haris Aziz
• Xiaohui Bei
• Warut Suksompong

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.

IJCAI Conference 2023 Conference Paper

Approximate Envy-Freeness in Graphical Cake Cutting

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

AAAI Conference 2023 Conference Paper

Differentially Private Fair Division

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

IJCAI Conference 2023 Conference Paper

Fair Division with Two-Sided Preferences

• Ayumi Igarashi
• Yasushi Kawase
• Warut Suksompong
• Hanna Sumita

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.

AAAI Conference 2023 Conference Paper

Fairness Concepts for Indivisible Items with Externalities

• Haris Aziz
• Warut Suksompong
• Zhaohong Sun
• Toby Walsh

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.

TCS Journal 2023 Journal Article

Justifying groups in multiwinner approval voting

• Edith Elkind
• Piotr Faliszewski
• Ayumi Igarashi
• Pasin Manurangsi
• Ulrike Schmidt-Kraepelin
• Warut Suksompong

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, where k is the target size of the committee. 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.

ECAI Conference 2023 Conference Paper

Settling the Score: Portioning with Cardinal Preferences

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

AAAI Conference 2023 Conference Paper

Topological Distance Games

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

TCS Journal 2022 Journal Article

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

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

IJCAI Conference 2022 Conference Paper

Fixing Knockout Tournaments With Seeds

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

JAAMAS Journal 2022 Journal Article

Generalized kings and single-elimination winners in random tournaments

• 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 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\) and \(k=3\). 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.

JAAMAS Journal 2022 Journal Article

Guest editorial: special issue on fair division

• Edith Elkind
• Nicolas Maudet
• Warut Suksompong

IJCAI Conference 2022 Conference Paper

Incentives in Social Decision Schemes with Pairwise Comparison Preferences

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

AIJ Journal 2022 Journal Article

Margin of victory for tournament solutions

• 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 them. 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 bounds on the MoV for both winners and non-winners. We then 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. Our results can also be viewed from the perspective of bribery and manipulation.

AIJ Journal 2022 Journal Article

Mind the gap: Cake cutting with separation

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

AAAI Conference 2022 Conference Paper

The Price of Justified Representation

• Edith Elkind
• Piotr Faliszewski
• Ayumi Igarashi
• Pasin Manurangsi
• Ulrike Schmidt-Kraepelin
• Warut Suksompong

In multiwinner approval voting, the goal is to select kmember 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.

AAAI Conference 2022 Conference Paper

Truthful Cake Sharing

• Xiaohui Bei
• Xinhang Lu
• Warut Suksompong

The classic cake cutting problem concerns the fair allocation of a heterogeneous resource among interested agents. In this paper, we study a public goods variant of the problem, where instead of competing with one another for the cake, the agents all share the same subset of the cake which must be chosen subject to a length constraint. We focus on the design of truthful and fair mechanisms in the presence of strategic agents who have piecewise uniform utilities over the cake. On the one hand, we show that the leximin solution is truthful and moreover maximizes an egalitarian welfare measure among all truthful and position oblivious mechanisms. On the other hand, we demonstrate that the maximum Nash welfare solution is truthful for two agents but not in general. Our results assume that mechanisms can block each agent from accessing parts that the agent does not claim to desire; we provide an impossibility result when blocking is not allowed.

AAAI Conference 2022 Conference Paper

Weighted Fairness Notions for Indivisible Items Revisited

• 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 same for weighted proportionality; the parameters indicate whether smallerweight 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.

IJCAI Conference 2021 Conference Paper

Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy Theory

• 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 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 $\Theta(\sqrt{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(\sqrt{n})$ goods even when a fully envy-free allocation exists. Our proofs make extensive use of tools from discrepancy theory.

AAAI Conference 2021 Conference Paper

Dividing a Graphical Cake

• Xiaohui Bei
• Warut Suksompong

We consider the classical cake-cutting problem where we wish to fairly divide a heterogeneous resource, often modeled as a cake, among interested agents. Work on the subject typically assumes that the cake is represented by an interval. In this paper, we introduce a generalized setting where the cake can be in the form of the set of edges of an undirected graph, allowing us to model the division of road networks. Unlike in the canonical setting, common fairness criteria such as proportionality cannot always be satisfied in our setting if each agent must receive a connected subgraph. We determine the optimal approximation of proportionality that can be obtained for any number of agents with arbitrary valuations, and exhibit a tight guarantee for each graph in the case of two agents. In addition, when more than one connected piece per agent is allowed, we establish the best egalitarian welfare guarantee for each total number of connected pieces. We also study a number of variants and extensions, including when approximate equitability is considered, or when the item to be divided is undesirable (also known as chore division).

IJCAI Conference 2021 Conference Paper

Generalized Kings and Single-Elimination Winners in Random Tournaments

• Pasin Manurangsi
• Warut Suksompong

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 regime of constant k, with the biggest change being between k = 2 and k = 3. 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.

IJCAI Conference 2021 Conference Paper

Graphical Cake Cutting via Maximin Share

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

IJCAI Conference 2021 Conference Paper

Keep Your Distance: Land Division With Separation

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

AAAI Conference 2021 Conference Paper

Margin of Victory in Tournaments: Structural and Experimental Results

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

AAAI Conference 2021 Conference Paper

Mind the Gap: Cake Cutting With Separation

• 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 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 establish several computational properties of maximin share fairness—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.

AIJ Journal 2021 Journal Article

Picking sequences and monotonicity in weighted fair division

• Mithun Chakraborty
• Ulrike Schmidt-Kraepelin
• Warut Suksompong

We study the problem of fairly allocating indivisible items to agents with different entitlements, which captures, for example, the distribution of ministries among political parties in a coalition government. Our focus is on picking sequences derived from common apportionment methods, including five traditional divisor methods and the quota method. We paint a complete picture of these methods in relation to known envy-freeness and proportionality relaxations for indivisible items as well as monotonicity properties with respect to the resource, population, and weights. In addition, we provide characterizations of picking sequences satisfying each of the fairness notions, and show that the well-studied maximum Nash welfare solution fails resource- and population-monotonicity even in the unweighted setting. Our results serve as an argument in favor of using picking sequences in weighted fair division problems.

IJCAI Conference 2021 Conference Paper

Picking Sequences and Monotonicity in Weighted Fair Division

• Mithun Chakraborty
• Ulrike Schmidt-Kraepelin
• Warut Suksompong

We study the problem of fairly allocating indivisible items to agents with different entitlements, which captures, for example, the distribution of ministries among political parties in a coalition government. Our focus is on picking sequences derived from common apportionment methods, including five traditional divisor methods and the quota method. We paint a complete picture of these methods in relation to known envy-freeness and proportionality relaxations for indivisible items as well as monotonicity properties with respect to the resource, population, and weights. In addition, we provide characterizations of picking sequences satisfying each of the fairness notions, and show that the well-studied maximum Nash welfare solution fails resource- and population-monotonicity even in the unweighted setting. Our results serve as an argument in favor of using picking sequences in weighted fair division problems.

AIJ Journal 2021 Journal Article

Schelling games on graphs

• Aishwarya Agarwal
• Edith Elkind
• Jiarui Gan
• Ayumi Igarashi
• Warut Suksompong
• Alexandros A. Voudouris

We study strategic games inspired by Schelling's seminal model of residential segregation. These games are played on undirected graphs, with the set of agents partitioned into multiple types; each agent either aims to maximize the fraction of her neighbors who are of her own type, or occupies a node of the graph and never moves away. We consider two natural variants of this model: in jump games agents can jump to empty nodes of the graph to increase their utility, while in swap games they can swap positions with other agents. We investigate the existence, computational complexity, and quality of equilibrium assignments in these games, both from a social welfare perspective and from a diversity perspective. Some of our results extend to a more general setting where the preferences of the agents over their neighbors are defined by a social network rather than a partition into types.

AAAI Conference 2021 Conference Paper

The Price of Connectivity in Fair Division

• Xiaohui Bei
• Ayumi Igarashi
• Xinhang Lu
• Warut Suksompong

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.

IJCAI Conference 2021 Conference Paper

Tournaments in Computational Social Choice: Recent Developments

• Warut Suksompong

Tournaments are commonly used to select winning alternatives in scenarios involving pairwise comparisons such as sports competitions and political elections. This survey discusses recent developments in two major lines of work—tournament solutions and single-elimination tournaments—with a focus on how computational social choice has brought new frameworks and perspectives into these decades-old studies.

JAIR Journal 2021 Journal Article

Welfare Guarantees in Schelling Segregation

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

AAAI Conference 2021 Conference Paper

Welfare Guarantees in Schelling Segregation

• Martin Bullinger
• Warut Suksompong
• Alexandros A. Voudouris

Schelling’s model is an influential model that reveals how individual perceptions and incentives can lead to racial 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 with approximately half of the maximum welfare can be done in polynomial time. We then consider Pareto optimality and introduce two new optimality notions, and establish mostly tight bounds on the worst-case welfare loss for assignments satisfying these notions. In addition, we show that for trees, 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.

TCS Journal 2020 Journal Article

Almost envy-freeness in group resource allocation

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

AAAI Conference 2020 Conference Paper

Contiguous Cake Cutting: Hardness Results and Approximation Algorithms

• 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 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 strengthening those from prior work.

JAIR Journal 2020 Journal Article

Contiguous Cake Cutting: Hardness Results and Approximation Algorithms

• Paul 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 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.

AAAI Conference 2020 Conference Paper

Refining Tournament Solutions via Margin of Victory

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

IJCAI Conference 2019 Conference Paper

Almost Envy-Freeness in Group Resource Allocation

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

AIJ Journal 2019 Journal Article

Computing a small agreeable set of indivisible items

• Pasin Manurangsi
• Warut Suksompong

We study the problem of assigning a small subset of indivisible items to a group of agents so that the subset is agreeable to all agents, meaning that all agents value the subset as least as much as its complement. For an arbitrary number of agents and items, we derive a tight worst-case bound on the number of items that may need to be included in such a set. We then present polynomial-time algorithms that find an agreeable set whose size matches the worst-case bound when there are two or three agents. We also show that finding small agreeable sets is possible even when we only have access to the agents' preferences on single items. Furthermore, we investigate the problem of efficiently computing an agreeable set whose size approximates the size of the smallest agreeable set for any given instance. We consider two well-known models for representing the preferences of the agents—the value oracle model and additive utilities—and establish tight bounds on the approximation ratio that can be obtained by algorithms running in polynomial time in each of these models.

AIJ Journal 2019 Journal Article

Democratic fair allocation of indivisible goods

• 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 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. For two groups with arbitrary monotonic valuations, we give an efficient protocol that guarantees envy-freeness up to one good for at least 1/2 of the agents in each group, and prove that the 1/2 fraction is optimal. We also present other protocols that make weaker fairness guarantees to more agents in each group, or to more groups. Our protocols combine techniques from different fields, including combinatorial game theory, cake cutting, and voting.

AAAI Conference 2019 Conference Paper

Fairly Allocating Many Goods with Few Queries

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

IJCAI Conference 2019 Conference Paper

Schelling Games on Graphs

• Edith Elkind
• Jiarui Gan
• Ayumi Igarashi
• Warut Suksompong
• Alexandros A. Voudouris

We consider strategic games that are inspired by Schelling's model of residential segregation. In our model, the agents are partitioned into k types and need to select locations on an undirected graph. Agents can be either stubborn, in which case they will always choose their preferred location, or strategic, in which case they aim to maximize the fraction of agents of their own type in their neighborhood. We investigate the existence of equilibria in these games, study the complexity of finding an equilibrium outcome or an outcome with high social welfare, and also provide upper and lower bounds on the price of anarchy and stability. Some of our results extend to the setting where the preferences of the agents over their neighbors are defined by a social network rather than a partition into types.

IJCAI Conference 2019 Conference Paper

The Price of Fairness for Indivisible Goods

• Xiaohui Bei
• Xinhang Lu
• Pasin Manurangsi
• Warut Suksompong

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.

AAAI Conference 2019 Conference Paper

When Do Envy-Free Allocations Exist?

• 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 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 n, an envy-free allocation is unlikely to exist even when m = Θ(n log n/ log log n).

IJCAI Conference 2018 Conference Paper

Democratic Fair Allocation of Indivisible Goods

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

IJCAI Conference 2018 Conference Paper

Truthful Fair Division without Free Disposal

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

IJCAI Conference 2017 Conference Paper

Computing an Approximately Optimal Agreeable Set of Items

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

IJCAI Conference 2016 Conference Paper

Assigning a Small Agreeable Set of Indivisible Items to Multiple Players

• Warut Suksompong

We consider an assignment problem that has aspects of fair division as well as social choice. In particular, we investigate the problem of assigning a small subset from a set of indivisible items to multiple players so that the chosen subset is agreeable to all players, i. e. , every player weakly prefers the chosen subset to any subset of its complement. For an arbitrary number of players, we derive tight upper bounds on the size for which a subset of that size that is agreeable to all players always exists when preferences are monotonic. We then present polynomial-time algorithms that find an agreeable subset of approximately half of the items when there are two or three players and preferences are responsive. Our results translate to a 2-approximation on the individual welfare of every player when preferences are subadditive.

AAAI Conference 2016 Conference Paper

Who Can Win a Single-Elimination Tournament?

• Michael Kim
• Warut Suksompong
• Virginia 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): 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.