Expanding the Reach of Social Choice Theory

1 Introduction

Social choice theory is a discipline that examines methods for combining individual preferences into a satisfactory collective decision [Arrow et al., 2002]. Its applications are wide-ranging-for example, a group of students choosing a restaurant for dinner, a university dividing resources among its departments, or a country electing its president. While early social choice theory primarily centered around the axiomatic aspect of aggregation rules, the past two decades have witnessed a significant surge of interest in the computational perspective [Brandt et al., 2016].

Even basic social choice settings can lead to surprisingly challenging theoretical questions. Consider, for instance, the setting of fairly allocating indivisible items among agents with additive valuations. A fundamental notion of fairness is envy-freeness, which means that no agent should envy another agent based on the allocated bundles. With discrete items, envy-freeness cannot always be satisfied, as is clear when two agents vie for a single valuable item. A natural relaxation is envy-freeness up to any item (EFX), which requires any envy that an agent has toward another agent to disappear as soon as any item in the latter agent's bundle is removed. EFX has received substantial attention within the fair division community since its introduction by Caragiannis et al. [2016]. However, except for a few special cases, it remains unknown whether an EFX allocation is guaranteed to exist. This stands in contrast with the weaker notion of envyfreeness up to one item (EF1)-this notion only requires the envy to disappear upon the removal of some item, and can always be fulfilled. A similarly intriguing question concerns another fairness notion called maximin share (MMS), which is defined as the highest value that each agent can guarantee for herself by partitioning the items into n parts and receiving the worst part, where n denotes the number of agents [Budish, 2011]. Although it is known that an allocation that gives every agent at least her MMS does not always exist, determining the best approximation has proven elusive thus far.

While these questions undoubtedly deserve further investigation, an equally important research direction lies in extending the model to encompass various real-life scenarios. Indeed, many practical applications of fair division cannot be adequately addressed within the confines of the basic framework. For example, when dividing inheritance among relatives, it is typical that closer relatives are entitled to a larger share of the inheritance, thereby rendering the usual notion of envy-freeness inappropriate. In a similar vein, when distributing office space between research groups, it is desirable for each group to receive a connected set of offices in order to facilitate communication, so a method that ignores this constraint can lead to an unusable solution. Investigating alternative paradigms is therefore crucial for broadening the applicability of social choice theory. The same holds for other domains of social choice such as voting, where the classic model involves selecting a winning candidate from voter rankings.

This paper provides an overview of my endeavors to expand the reach of social choice theory in the areas of fair division, voting, and tournaments, as well as to bridge the gap between the developed theory and its practical application.

2 Fair Division

In fair division, the aim is to allocate resources fairly among interested agents with possibly differing preferences [Thomson, 2016]. The literature considers both divisible resources, such as land and time, as well as indivisible resources, such as books, furniture, and electronic devices.

2.1 Unequal Entitlements

As mentioned earlier, some applications of fair division involve agents with unequal entitlements which can be represented by weights. Besides inheritance division, this is the case when allocating usage rights of a facility to investors who have made varying amounts of investment.

Envy-freeness can be extended to the weighted setting in a natural manner. For example, if Alice's weight is twice of Bob's, then Alice is "weighted envy-free" toward Bob if she finds her bundle to be worth at least twice of Bob's bundle. In the same spirit, we say that agent i is weighted EF1 (WEF1) toward agent j if, whenever j's bundle Aj is nonempty, there exists an item g ⊆ Aj such that

where vi denotes agent i's valuation function, Ai denotes i's bundle, and wi and wj denote i's and j's weights, respectively. In our work, we showed that a WEF1 allocation always exists and can be found efficiently using a weighted picking sequence, where agents take turns picking their favorite items and each subsequent pick is assigned to an agent who has picked least frequently relative to her weight [Chakraborty et al., 2021a]. This demonstrates that a strong fairness guarantee can be made even in the presence of arbitrary entitlements.

Among numerous ways in which the weighted setting differs from its unweighted counterpart, one of the most notable is the trade-off between satisfying higher-weight agents and lower-weight ones. This is exhibited by a simple instance where there are n agents and n identical items, but one of the agents has a larger weight than all the remaining agents combined. The only WEF1 allocation assigns one item to each agent; this is also the only allocation that leaves no agent empty-handed. However, the allocation can be reasonably objected as unfair by the high-weight agent. To address this inevitable trade-off, we generalized WEF1 to WEF(x, 1-x), where x ∈ [0, 1] is a parameter [Chakraborty et al., 2022]. WEF1 corresponds to WEF(1, 0), and higher x favors lowerweight agents. We proved that for any x, WEF(x, 1 - x) can be satisfied by a weighted picking sequence where the assignment of the next pick is adjusted according to x. In another paper, we showed that unlike several other methods, these picking sequences possess strong monotonicity propertiesfor example, resource-monotonicity states that when an extra item is added, no agent should receive lower value as a consequence [Chakraborty et al., 2021b]. We also generalized these fairness notions and guarantees from additive valuations to submodular valuations (i.e., valuations that exhibit decreasing marginal returns) [Montanari et al., 2024].

In addition to picking sequences, another important fair allocation method is the maximum weighted Nash welfare (MWNW) rule, which returns an allocation that maximizes the weighted product of the agents' values, where the weights appear in the exponents. Even in the unweighted setting, MWNW fails monotonicity and strategyproofness properties and is hard to compute. However, we showed that all of these desirable properties can be recovered under arbitrary weights, provided that the agents have binary additive valuations [Suksompong and Teh, 2022]. In a subsequent paper, we proved that these attractive properties continue to hold for arbitrary "weighted additive welfarist rules" with concave functions, of which MWNW is a special case, and for agents with binary submodular valuations [Suksompong and Teh, 2023].

2.2 Group Preferences

Another natural extension of the basic fair division setting is the extension to groups. In this model, agents in the same group receive the same bundle of items but may have differing preferences over them. This occurs, for instance, when distributing household goods among families-members of the same family may have varying thoughts about having a television or a fitness equipment in their house.

In a paper that introduced this setting, we proved that when all groups are of the same size and the agents' valuations are drawn randomly from probability distributions, an envy-free allocation exists with high probability as long as the number of items exceeds the number of agents by at least a logarithmic factor [Manurangsi and Suksompong, 2017]. We also showed that when the number of groups is constant, there exists an allocation that is envy-free up to Θ(√n) items (where n denotes the total number of agents across all groups) [Manurangsi and Suksompong, 2022], and established the existence of EF1 allocations for small groups [Kyropoulou et al., 2020]. In addition, we investigated democratic fairness, which aims to satisfy a fraction of the agents in each group when satisfying all of them is impossible [Segal-Halevi and Suksompong, 2019]. For instance, we proved that with two groups, there always exists an allocation that is EF1 to at least 1/2 of the agents in each group, and the fraction 1/2 is tight.

As discussed earlier, when allocating indivisible items, another popular fairness notion is MMS. Unfortunately, even for two groups with three agents each, there may not exist an allocation that gives every agent any positive fraction of her MMS. This can be seen in a simple instance with three items such that each agent has value 1 for two of the items and 0 for the remaining item, where the three agents in each group value distinct pairs of items. In the case of two groups, I characterized the group sizes for which a positive MMS approximation can be attained [Suksompong, 2018]. Nevertheless, to provide guarantees for larger groups, cardinal approximations are insufficient. In light of this, we considered ordinal approximations, where instead of partitioning into g parts (where g denotes the number of groups), we partition into k parts for some parameter k > g. For arbitrary group sizes, we determined the asymptotically tight bound on k such that an ordinal MMS approximation with parameter k can be guaranteed [Manurangsi and Suksompong, 2024].

Furthermore, we considered the allocation of divisible resources, often referred to as cake cutting, among groups. We showed that it is possible to partition the agents into groups of any desired sizes and divide an interval cake so that each group receives a single connected piece of the cake and the resulting allocation is envy-free [Segal-Halevi and Suksompong, 2021]. 1 We also established an analogous result for chore division [Segal-Halevi and Suksompong, 2023].

2.3 Constraints

The majority of the fair division literature assumes that any allocation of the resource is feasible. However, there are several applications where this assumption does not hold due to constraints on the allocation. In my survey, I summarized the types of constraints that have been explored in the literature thus far [Suksompong, 2021a]. In particular, my research has focused on connectivity and separation constraints.

1 If we are not allowed to partition the agents, it is not difficult to see that this task may be impossible.

Connectivity constraints are relevant when the items form a linear structure, such as retail units on a street or time slots for using a conference center. In my work, I studied the existence of connected allocations that satisfy approximate versions of envy-freeness as well as two other fundamental fairness notions, proportionality (each agent receives at least 1/n of her value for the entire set of items) and equitability (every agent's value for her own bundle is the same) [Suksompong, 2019]. Bouveret et al. [2017] introduced a more general model where the items can form an arbitrary graph. In this model, we studied the price of connectivity, which captures the loss of fairness or social welfare due to the connectivity requirement [Bei et al., 2022a; Bei et al., 2024]. Our results reveal that the price depends significantly on the structure of the graph; their proofs involve applying a number of tools from graph theory. In another paper, we showed that deciding whether there exists a connected fair allocation is NP-hard even when the agents have binary valuations and the items lie on a line [Goldberg et al., 2020]. This hardness holds for each of the three fairness notionsenvy-freeness, proportionality, and equitability-as well as any combination of them. In the same work, we also explored envy-freeness in connected cake cutting. Specifically, we devised an efficient algorithm that computes an approximately envy-free allocation and established the NP-hardness of various decision problems on the existence of envy-free allocations, e.g., when we fix the ordering of the agents or constrain the positions of certain cuts.

In some scenarios, not only do we want each agent's share to be connected, but we also want different agents' shares to be sufficiently separated from one another. Indeed, this may be necessary in order to respect social distancing guidelines, allow time to erase data between machine processes, or prevent cross-fertilization of crops from different land plots. We initiated the study of separation constraints in fair division by examining them in the context of cake cutting [Elkind et al., 2022]. While an MMS allocation does not always exist, if we relax the MMS notion in an ordinal manner by partitioning the cake into n + 1 instead of n pieces (cf. Section 2.2), we showed that we can recover guaranteed existence. In a follow-up work, we examined the more general setting of land division, where geometric considerations play a crucial role since, for example, a long but thin piece of land may offer little value [Elkind et al., 2023a]. Once again, we illustrated the usefulness of ordinal MMS by providing guarantees in terms of this notion for a variety of geometric shapes.

2.4 Other Settings

Next, I briefly describe other contexts that I have introduced or contributed to within the domain of fair division.

Two-Sided Preferences. In fair division with two-sided preferences, not only do the "agents" have preferences over the "items", but the items also have preferences over the agents. This is the case when allocating players to sports teams or volunteers to community service clubs. We devised algorithms that are fair and stable with respect to the preferences of both sides [Igarashi et al., 2023].

Externalities. Some applications of fair division involve externalities: an agent getting a high-value item can make you feel better if that agent is your friend, but worse if she is your enemy. We extended envy-based notions to accommodate the externalities that may arise [Aziz et al., 2023].

Differential Privacy. In certain situations, one may desire an allocation that is not only fair, but also private. We applied the well-established framework of differential privacy and examined the trade-off between fairness and privacy in this setting [Manurangsi and Suksompong, 2023a].

Reachability. Given an initial fair allocation and a target fair allocation, how can we make local changes (e.g., exchanging a pair of items) to reach the latter from the former in such a way that every intermediate allocation is also fair? Applications of this reachability problem include a company that wishes to redistribute some of its employees between its teams or a museum that plans to reallocate certain exhibits among its branches. We derived results on the feasibility and complexity of this task for different valuation classes and numbers of agents [Igarashi et al., 2024].

House Allocation. In the house allocation problem, each agent is required to receive exactly one item; in particular, the number of items is at least the number of agents and some items may be left unallocated. Our works were among the first to inspect fairness considerations for this problem [Gan et al., 2019; Kamiyama et al., 2021; Choo et al., 2024].

Graphical Cake Cutting. The cake in the cake-cutting literature is typically represented by an interval. However, this representation is insufficient when dividing complex resources such as road networks. In light of this, we introduced a more general model of graphical cake cutting, where the cake corresponds to the edges of an arbitrary graph. We investigated the existence and computation of approximately fair allocations when the fairness notion is proportionality [Bei and Suksompong, 2021], MMS [Elkind et al., 2021], and envy-freeness [Yuen and Suksompong, 2023].

3 Voting

Voting is a cornerstone of social choice theory, with traditional models assuming ranked ballots submitted by voters [Zwicker, 2016]. Nevertheless, practical applications often feature a range of alternative input and output formats.

3.1 Budget Aggregation

A natural voting setting that has received little attention until recently is the aggregation and coordination of budget.

When the budget is not owned by the agents, this problem is also known as portioning. Formally, each agent submits a preference on how she prefers a central budget to be divided among a set of alternatives-e.g., time for different activities at a conference or money for various government initiativesand the goal is to aggregate these preferences into the actual division. Under the assumption that an agent's preference depends linearly on the distance between her ideal distribution and the actual distribution, we analyzed common aggregation rules with respect to desirable axioms [Elkind et al., 2023b]. We found that a simple rule that takes the average of the agents' preferences performs well in relation to these axioms. In addition, while any two of three properties capturing efficiency, strategyproofness, and fairness can be satisfied, we showed in another paper that no rule can fulfill all three simultaneously [Brandt et al., 2024]. We also proposed a different valuation model, motivated by representation considerations, under which the three properties are satisfiable together.

On the other hand, when the budget is owned by the agents, the problem is sometimes referred to as donor coordination. Under two well-known valuation models from the economics literature, we demonstrated that the Nash product rule, which selects an allocation that maximizes the product of the agents' values, satisfies strong incentive and efficiency properties [Brandl et al., 2022; Brandt et al., 2023]. In light of the substantial volume of contributions made to donation programs around the world every year, these findings have the potential to help vastly improve the effectiveness of the donations.

3.2 Cake Sharing

Consider a scenario where a group of agents need to decide the time periods to reserve a sports facility or a conference room for their joint usage. Given their limited budget, they can only reserve the facility for a certain amount of time, so they need to aggregate their preferences in order to make this decision. To capture such scenarios, we introduced the model of cake sharing as a voting analog of cake cutting, where the cake represents a heterogeneous divisible item [Bei et al., 2022b]. We then showed that when agents have approval preferences-meaning that each of them either approves or disapproves each part of the resource-there exists a rule that is both fair and strategyproof.

In a follow-up work, we considered a more general setting where the resource may consist of both divisible and indivisible items [Lu et al., 2024]. This serves to model, for example, time slots for which some must be reserved as a whole while others may be booked fractionally. Our framework generalizes both cake sharing and multiwinner voting, another well-studied variant of voting. We formulated representation notions for this context and assessed the degree to which important voting rules satisfy these notions.

4 Tournaments

Tournaments are frequently used in order to select among alternatives whose relations are given by pairwise comparisons, such as players or teams in sports competitions [Suksompong, 2021b]. In particular, a tournament solution is a function that maps these relations to a subset of the alternatives. Perhaps surprisingly, Fey [2008] showed that several common tournament solutions are likely to select all alternatives in large random tournaments, thereby limiting their usefulness as discriminators. To address this issue, we introduced the concept of margin of victory (MoV) for tournament solutions and studied it from the axiomatic and computational perspectives [Brill et al., 2022]. Furthermore, our experiments show that MoV exhibits a significant degree of discriminatory power, thereby enabling effective differentiation among alternatives.

A popular tournament format for organizing sports competitions is that of knockout tournaments-this format is exciting due to its "do-or-die" nature, with players immediately eliminated after only a single loss. Since an outcome of a knockout tournament can depend heavily on the chosen bracket, a line of work has investigated the question of whether the tournament organizers can fix the bracket in such a way that their favorite player wins the tournament. While this line of work assumes that any bracket can be chosen, in real-world tournaments there are often seed constraints. We therefore examined the problem in the presence of seeds, and uncovered similarities and differences in comparison to the unseeded setting [Manurangsi and Suksompong, 2023b].

5 FromTheory to Practice

Social choice theory has undoubtedly made significant strides in recent years, leading to better methods for collective decision making. Nevertheless, work remains to be done in order to make it more useful in practical applications. I highlight two paths that the community can pursue toward this goal.

First, we need a broader and ideally more unified theory for handling the diverse applications that can arise. Let me illustrate this with a message from my department head when we discussed lab seat allocation in our department [Lee, 2022].

We have large labs (capacity of 50 to 100 seats) and multiple faculty members sharing the labs. Each faculty member prefers to fit all their students in the same lab, and would like to have all their students to be seated in the same region of the large lab. If everyone fits, it may not be too difficult. It gets tricky (and requires fair policy) if the lab is not large enough and some students need to be seated in other labs that may be further away. An even harder problem is the dynamic one, where students leave and new students arrive-maybe the policy can include allowing faculty members to swap the seats of their students in the dynamic case?

Although this problem contains elements that have been explored in the fair division literature-including connectivity requirements, cardinality constraints, and the online naturethe current literature does not offer a readily applicable solution to their combination, thereby restricting its practicality.

Second, rather than limiting the solutions that we develop to research papers, we should endeavor to make their implementations publicly avaliable. My recent effort toward this goal is reflected by Fast & Fair, an open-source platform for fair division applications [Han and Suksompong, 2024]. Not only does Fast & Fair provide implementations of algorithms for practical fair division scenarios, but unlike the few existing platforms in this domain, it is also open to community contributions. This allows other researchers and developers to contribute code for their own applications and benefit from our standardized graphical widgets and interfaces. I believe that such efforts can serve to highlight the usefulness of social choice to a broader audience and, in the process, bring its rich and captivating theory closer to practice.

Acknowledgments

My research has been partially supported by the Singapore Ministry of Education under grant number MOET2EP20221-0001 and by an NUS Start-up Grant. Furthermore, I would like to thank all of my collaborators, without whom much of this research would not have been possible.