Fair Division: Algorithms, Solution Concepts, and Applications

We address important extensions to the house allocation problem: The agents are partitioned into disjoint groups (based on ethnicities or socio-economic status) and we want the allocation to respect some notion of diversity and/or fairness with respect to these groups. We study two specific incarnations of this general problem. First, we address a constrained optimization problem, inspired by diversity quotas in some real-world allocation problems, where the items are also partitioned into blocks and there is an upper bound on the number of items from each block that can be assigned to agents in each group. We theoretically analyze the price of diversity, the price of stability, the price of anarchy and report experiments based on real-world data sets. Next, instead of imposing hard constraints, we cast the problem as a variant of fair allocation of indivisible goods – we treat each group of agents as a single entity receiving a bundle of items whose valuation is the maximum total utility of matching agents in that group to items in that bundle; we present algorithms that achieve a standard relaxation of envy-freeness in conjunction with specific efficiency criteria, and we propose a new fairness notion better suited to house allocation problems with disjoint groups (using an axiomatic approach).

For the fair division of items among interested agents, envyfreeness is possibly the most favoured and widely studied formalisation of fairness. For indivisible items, envy-free allocations may not exist in trivial cases, and hence research and practice focus on relaxations, particularly envy-freeness up to one item (EF1), which allows the removal of an item to resolve envy. A significant reason for the popularity of EF1 allocations in theory and practice is its simple fact of existence for many valuation classes. In this talk, we present results on the existence of EF1 for agents with nonmonotone valuations, highlighting both results and challenges.

We consider a fair division setting of allocating indivisible items to a set of agents. In order to cope with the well-known impossibility results related to the non-existence of envy-free allocations, we allow the option of selling some of the items so as to compensate envious agents with monetary rewards. In fact, this approach is not new in practice, as it is applied in some countries in inheritance or divorce cases. A drawback of this approach is that it may create a value loss, since the market value derived by selling an item can be less than the value perceived by the agents. Therefore, given the market values of all items, a natural goal is to identify which items to sell so as to arrive at an envy-free allocation, while at the same time maximizing the overall social welfare. Our work is focused on the algorithmic study of this problem, and we provide both positive and negative results on its approximability. When the agents have a commonly accepted value for each item, our results show a sharp separation between the cases of two or more agents. In particular, we establish a PTAS for two agents, and we complement this with a hardness result, that for three or more agents, the best approximation guarantee is provided by essentially selling all items. This hardness barrier, however, is relieved when the number of distinct item values is constant, as we provide an efficient algorithm for any number of agents. We also explore the generalization to heterogeneous valuations, where the hardness result continues to hold, and where we provide positive results for certain special cases.

When allocating indivisible items to agents, it is known that the only strategyproof mechanisms that satisfy a set of rather mild conditions are constrained serial dictatorships: given a fixed order over agents, at each step the designated agent chooses a given number of items (depending on her position in the sequence). With these rules, agents who come earlier in the sequence have a larger choice of items. However, this advantage can be compensated by a higher number of items received by those who come later. How to balance priority in the sequence and number of items received is a nontrivial question. We use a previous model, parameterized by a mapping from ranks to scores, a social welfare functional, and a distribution over preference profiles. For several meaningful choices of parameters, we show that the optimal sequence can be computed exactly in polynomial time or approximated using sampling. Our results hold for several probabilistic models on preference profiles with a particular emphasis on the Plackett-Luce model. We conclude with experimental results illustrating how the optimal sequence is impacted by various parameters of the problem.

We study envy freeness up to any good (EFX) in settings where valuations can be represented via a graph of arbitrary size where vertices correspond to agents and edges to items. An item (edge) has zero marginal value to all agents (vertices) not incident to the edge. Each vertex may have an arbitrary monotone valuation on the set of incident edges. We first consider allocations that correspond to orientations of the edges, where we show that EFX does not always exist, and furthermore that it is NP-complete to decide whether an EFX orientation exists. Our main result is that (EFX) allocations exist for this setting. This is one of the few cases where EFX allocations are known to exist for more than 3 agents.

Amanatidis, Birmpas, Christodoulou and Markakis showed no truthful mechanism exists with a better approximation to the maximin share (MMS) than $\lfloor m/2\rfloor$. I describe how to use predictions to devise truthful mechanisms that obtain improved approximation guarantees when the prediction is accurate (consistency), and have near-optimal fallback guarantees when the prediction is off (robustness).

I later discuss with the audience if my mechanism is useful (it is not), and which incentive properties should we go for instead.

We consider the problem of assigning projects to time slots, in the setting where agents have approval preferences over projects that vary over time, and each project can be implemented at most once. While optimising the utilitarian welfare in this setting is easy, optimising egalitarian welfare turns out to be computationally hard, even under strong constraints on agents’ preferences. However, we describe a randomised algorithm for this problem that runs in polynomial time if the number of agents is bounded by a constant; our proof uses algebraic techniques and extends to other concepts of welfare and fairness.

In this talk, we will see some of the main open problems in fair cake cutting, namely the problem of partitioning a divisible resource in a fair manner. The focus will be on computing connected envy-free divisions of the cake and we will consider various types of valuation functions and different models of computation.

Couples often encounter the challenge of sharing house chores. This raises the fundamental question of how to divide chores. In this paper, we present a new application for a fair division of household chores. Our platform, called Kajibuntan, allows couples to specify the set of chores to be shared, their preferences over them, and the current allocation. Our tool visualizes the current allocation and makes proposals according to their preferences based on the theory of fair division. The goal of our tool is to provide a systematic and transparent system to divide household chores and help creating harmony in the home.

This is a manifesto for a collaborative work. The aim is to build a taxonomy (with some carefully chosen set of labels) of fair division problems and papers, similar to Sandewall’s famous taxonomy of logical systems for reasoning about action and change [1]. It is based on a set of specialties concerning: item; agents; allocations; preferences; evaluation criteria; protocols; knowledge, behaviour and dynamics; nature of work in the paper. Every speciality can take a value on a feature domain. Every problem of paper can be labelled by a set of features. Benefits of such a taxonomy are: one can see in a few seconds what a paper is about; can retrieve efficiently papers sharing some features even if they don’t cite each other or use different terminologies, which will make it easier for a junior research to find their way through the (now huge) bibliography in fair division. The tool is collaborative: features can be added, deleted, renamed, refined, splitted.

Our work studies the fair allocation of indivisible items to a set of agents, and falls within the scope of establishing improved approximation guarantees. It is well known by now that the classic solution concepts in fair division, such as envy-freeness and proportionality, fail to exist in the presence of indivisible items. Unfortunately, the lack of existence remains unresolved even for some relaxations of envy-freeness, and most notably for the notion of EFX, which has attracted significant attention in the relevant literature. This in turn has motivated the quest for approximation algorithms, resulting in the currently best known $(\varphi -1)$-approximation guarantee by Amanatidis et al. (2020), where $\varphi$ equals the golden ratio. So far, it has been notoriously hard to obtain any further advancements beyond this factor. Our main contribution is that we achieve better approximations, for certain special cases, where the agents agree on their perception of some items in terms of their worth. In particular, we first provide an algorithm with a $2/3$-approximation, when the agents agree on what are the top $n$ items (but not necessarily on their exact ranking), with $n$ being the number of agents. To do so, we also propose a general framework that can be of independent interest for obtaining further guarantees. Secondly, we establish the existence of exact EFX allocations in a different scenario, where the agents view the items as split into tiers w.r.t. their value, and they agree on which items belong to each tier. Overall, our results provide evidence that improved guarantees can still be possible by exploiting ordinal information of the valuations.

In fair division, local envy-freeness is a desirable property which has been thoroughly studied in recent years. We study explanations which can be given to explain that no allocation of items can satisfy this criterion, in the house allocation setting where agents receive a single item. While Minimal Unsatisfiable Subsets (MUSes) are key concepts to extract explanations, they cannot be used as such: (i) they highly depend on the initial encoding of the problem; (ii) they are flat structures which fall short of capturing the dynamics of explanations; (iii) they typically come in large number and exhibit great diversity. In this work we provide two SAT encodings of the problem which allow us to extract MUS when instances are unsatisfiable. We build a dynamic graph structure which allows to follow step-by-step the explanation. Finally, we propose several criteria to select MUSes, some of them being based on the MUS structure, while others rely on this original graphical explanation structure.

Federated learning provides an effective paradigm to jointly optimize a model that benefits from rich distributed data while protecting data privacy. Nonetheless, the heterogeneous nature of distributed data makes it challenging to define and ensure fairness among local agents and create incentive issues. For instance, it is intuitively “unfair” for agents with high-quality data to sacrifice their performance due to other agents with low-quality data. Furthermore, on the one hand, agents benefit from the global model trained on shared data, while on the other hand, by participating in federated learning, they may also incur costs (related to privacy and communication) due to data sharing. This may give rise to incentive issues and free riding.

In this talk, I will use social choice theory and game theory to address these fairness and incentive issues. I will show how FL and SCT can inform each other, leading to new insights and avenues for exploration.

The design of welfare guarantees for the division of resources in common property is historically the first modern (i. e., mathematical) principle of fair division and still the focus of a large body of current research. This tutorial defines the concept and corresponding mathematical question in an abstract context-free model of “welfare division” before reviewing instances of the problem where the answer is easy, as well as where it is not: cake cutting, indivisible objects, sharing of a production function and probabilistic voting.

In this talk, I will discuss the ways some non-profits address food insecurity, and what fair division has offered and has to offer to this domain.

The notion of envy-freeness up to any item (EFX) is considered to be the most fascinating fairness concept in fair division of indivisible items. Unfortunately, despite significant efforts, existence of EFX allocations is a major open problem in fair division, thereby making the study of approximations and relaxations of EFX a natural line of research. Recently, Caragiannis et al. introduced a promising relaxation of EFX, called epistemic EFX (EEFX). We say an allocation to be EEFX if, for every agent, it is possible to shuffle the items in the remaining bundles so that she becomes EFX-satisfied”. Caragiannis et al. [IJCAI’23] prove existence and polynomial-time computability of EEFX allocations for additive valuations. A natural question asks what happens when we consider valuations more general than additive?

We address this important open question and answer it affirmatively by establishing the existence of EEFX allocations for an arbitrary number of agents with general monotone valuations. To the best of our knowledge, besides EF1, EEFX is the only known relaxation of EFX to have such strong existential guarantees. Furthermore, we complement our existential result by proving computational and information-theoretic lower bounds. We prove that for an arbitrary number of (more than one) agents (even) with identical submodular valuations, it is PLS-hard to compute EEFX allocations and it requires exponentially-many value queries to do so.

The talk is based on a work that will appear in AAAI 2025.

The classic house allocation problem is primarily concerned with finding a matching between a set of agents and a set of houses that guarantees some notion of economic efficiency (e.g. utilitarian welfare). While recent works have shifted focus on achieving fairness (e.g. minimizing the number of envious agents), they often come with notable costs on efficiency notions such as utilitarian or egalitarian welfare. We investigate the trade-offs between these welfare measures and several natural fairness measures that rely on the number of envious agents, the total (aggregate) envy of all agents, and maximum total envy of an agent. In particular, by focusing on envy-free allocations, we first show that, should one exist, finding an envy-free allocation with maximum utilitarian or egalitarian welfare is computationally tractable. We highlight a rather stark contrast between utilitarian and egalitarian welfare by showing that finding utilitarian welfare maximizing allocations that minimize the aforementioned fairness measures can be done in polynomial time while their egalitarian counterparts remain intractable (for the most part) even under binary valuations. We complement our theoretical findings by giving insights into the relationship between the different fairness measures and conducting empirical analysis.

We study the problem of allocating a set of indivisible goods to a set of agents with additive valuation functions, aiming to achieve approximate envy-freeness up to any good.

The state-of-the-art results on the problem include that (exact) EFX allocations exist when (a) there are at most three agents, or (b) the agents’ valuation functions can take at most two values, or (c) the agents’ valuation functions can be represented via a graph. In this work, by relaxing the notion of EFX to 2/3-EFX, we obtain existence results for strict generalizations of the settings for which exact EFX allocations are known to exist. We show that 2/3-EFX allocations exist when (a) there are at most seven agents, (b) the agents’ valuation functions can take at most three values, or (c) the agents’ valuation functions can be represented via a multigraph.

From a different viewpoint, for approximate EFX, it is known that a 0.618-EFX allocation exists for any number of agents with additive valuation functions. Our results beat the barrier of 0.618 and achieve an approximation guarantee of 2/3, but we need to impose restrictions on the setting. Therefore, our results push the frontier of existence and computation of approximate EFX allocations, and provide insights into the challenges of settling the existence of exact EFX allocations.

In the strategic facility location problem, a set of agents report their locations in a metric space and the goal is to use these reports to open a new facility, minimizing an aggregate distance measure from the agents to the facility. However, agents are strategic and may misreport their locations to influence the facility’s placement in their favor. The aim is to design truthful mechanisms, ensuring agents cannot gain by misreporting. This problem was recently revisited through the learning-augmented framework, aiming to move beyond worst-case analysis and design truthful mechanisms that are augmented with (machine-learned) predictions. The focus of this prior work was on mechanisms that are deterministic and augmented with a prediction regarding the optimal facility location. In this paper, we provide a deeper understanding of this problem by exploring the power of randomization as well as the impact of different types of predictions on the performance of truthful learning-augmented mechanisms. We study both the single-dimensional and the Euclidean case and provide upper and lower bounds regarding the achievable approximation of the optimal egalitarian social cost.

We will discuss the problem of fairly assigning a set of discrete tasks, or chores, among a set of agents. Each chore has a designated start and finish time, and each agent can perform at most one chore at any time. We will explore the existence and computation of “fair” (specifically, envy-free up to one chore) and “efficient” (specifically, maximal or Pareto optimal) schedules under various settings. The presentation will cover novel technical ideas, including a color-switching technique and an application of the “cycle-plus-triangles” theorem (originally conjectured by Erdös) for achieving approximate envy-freeness. We will also highlight several open problems and directions for future work.

Randomized mechanisms can have good normative properties compared to their deterministic counterparts. However, randomized mechanisms are problematic in several ways such as in their verifiability. We propose here to de-randomize such mechanisms by having agents play a game instead of tossing a coin. The game is designed so agents play randomly, and this play injects “randomness” into the mechanism. Surprisingly this de-randomization retains many of the good normative properties of the original randomized mechanism but gives a mechanism that is deterministic and easy, for instance, to audit. We consider three general purpose methods to de-randomize mechanisms, and apply these to six different domains: voting, facility location, task allocation, school choice, peer selection, and resource allocation. We propose a number of novel de-randomized mechanisms for these six domains with good normative properties (such as equilibria in which agents sincerely report preferences over the original problem). In one domain, we additionally show that a new and desirable normative property emerges as a result of de-randomization.

In this talk we provide a brief overview of the course allocation problem. We need to assign a set of class seats to students with subjective preferences over the classes they want to take. In addition, students’ assigned classes are constrained; for example, a student may not take two classes with overlapping schedules, nor can they take a seat in the same class twice. Furthermore, students are often constrained in the number of classes they are allowed to take in a semester.

Unlike other instances of the problem of fair allocation of indivisible items, course scheduling often involves thousands of agents (students) and items (course seats). Our goal is to design scalable, computationally efficient mechanisms that compute assignments with both fairness and efficiency guarantees. We argue for the design of simple, sequential allocation protocols prove to be surprisingly effective in these settings.

We show that our approach is effective both in theory and in practice. We offer a comprehensive mathematical analysis of our algorithmic framework, based on the Yankee Swap mechanism proposed by Viswanathan and Zick (2023). In addition, we collect survey responses from over 1000 students at UMass Amherst, at both the undergraduate and graduate level. We show that the Yankee Swap framework outperforms several standard benchmarks on allocative efficiency, fairness, and computational efficiency.