# Overview

# Fair Division

Studies of fair division aim to find ways of allocating resources among people (aka agents) — who have preferences over said resources — in such a way that makes everyone happy.

That was a loaded statement, and as we will see, there are a number of ways in which it can be made precise.

The language in this short essay is deliberately informal. Please take a look at some of the references for proper definitions, notation, and etiquette. The goal here is to just convey, briefly, the major lines of inquiry in fair division research.

### What are resources?

Resources, broadly speaking, refer to the thing(s) we want to allocate. It might refer to discrete items (e.g, cars) that are typically infeasible to “break” further, or a continuous object (e.g, a piece of land). In the former setting, one simply models the resources as a finite set, while in the latter, it is convenient to think of the resource as the interval [0,1]. These scenarios are usually called the settings of *indivisible goods* and *cake cutting*, respectively.

Although it doesn’t sound like it, a resource may also refer to something not entirely empowering, such as a (usually tiresome) task that needs to be done. Such resources are often called *chores*.

In short: resources are thing(s) that need to be handed out or assigned.

### What (umm… who?) are agents?

Agents lie the heart of the problem: to keep things meanigful we assume there’s more than one, and rest assured, things already get interesting with just two of them, although we often have more of them to worry about. These are the folks who are eyeing (or avoiding, depending on the situation) a large share of the resources.

### What are preferences?

Our agents have… opinions. They all come with their own perspectives on resources. These preferences can be expressed with a valuation function v, which takes as input a subset of resources and a choice of agent, and reports the value that said agent has for said resources.

For instance, in the indivisible setting: if S is a subset of items and a is an agent, we could probe v(S,a) to appreciate the utility that the agent derives if s/he were to be given all the items in S (and nothing else).

### What is an allocation of resources among agents?

An allocation is simply a partition of our resources into n labeled parts, where the labels correspond to agents. As you might guess, this is to say that the agent a “recieves” the part labeled a. Note that our choice of the word *partition* implies two important things:

- Every resource is allocated to some agent.
- No resource is allocated to more than one agent.

The first point implies that no resources are thrown away, while the second point implies that there is no sharing. Sometimes, we may want to relax these aspects of the definition: this is nonetheless a good place to start.

### What about making everyone happy?

Ah well. This, as you might have guessed, is: (a) the hard part, and (b) not always possible, depending on your definition.

There are several notions of “happiness” proposed in the fair division literature. Suppose we are trying to divide R^{1} among a set of n agents A whose valuations are given by v, and we have come up with an allocation D. For an agent a, we use D_a to denote the part labeled a in D.

Here are a few notions suggestive that D is a “desirable” allocation, making everyone in A happy.

Notice that if we didn’t insist on D allocating every item to some agent, then we could resort to the happiness-by-Zen approach: in particular, the trivial allocation that gives nobody anything would vacuously satisfy most definitions of happiness. Implicitly, our demand for a “complete” allocation can be thought of as an *efficiency* requirement, and one could also push the bar on this front. For example, a common efficiency notion, borrowed from economics, is Pareto optimality.

Fix any notion of happiness^{2} — say `P`

, and efficiency — say `Q`

. Two questions are of immediate interest:

- Do allocations that satisfy
`P`

and`Q`

always exist? - For instances that admit allocations that satisfy
`P`

and`Q`

, can such allocations be computed efficiently? And can we quickly determine if such allocations do not exist for a given instance?

For example, notice that allocations in the sense that we defined them (with an implicit requirement of completeness) that are envy-free need not always exist: consider the situation where you have two agents and one item, and both agents value said item at 100. Any complete allocation will assign this item to one of these two agents, making the other envious. The same example shows that we cannot guarantee the existence of complete equitable allocations.

Non-existence of nice allocations is always a bit of a bummer, so much research has been devoted to reasonable workarounds, for example:

- What if
^{3}the allocations could be*approximately*envy-free/equitable? - What if
^{4}the valuations were not completely arbitrary? - What if
^{5}we could*introduce*some dummy items or money into the systsem to make things work? - What if
^{6}we didn’t*have*to allocate*everything*? - What if
^{7}the parts were allowed to*overlap*?

Apart from making sense of reasonable workarounds, research on fair division also aims to understand tradeoffs *between* fairness and efficiency. Given an allocation, there are ways in which you can measure its *welfare* — it’s usually a function of the utilities that all agents derive from the allocation. The “gap” between the maximum welfare you can generate if you were not restricted by fairness requirements v/s the best welfare attainable subject to fairness constraints — known as the *price of fairness* — is also the topic of much research.

If any of this piqued your interest, here’s a non-exhaustive list of pointers that I hope will help with finding out more!

## References

Part II in the Handbook of Computational Social Choice (Brandt et al. 2016) is a great place to start (the handbook can be downloaded from here).

For indivisible goods, (Amanatidis et al. 2022) is an excellent and — at least at the time of this writing — recent survey covering the state of the art and highlighting major open problems.

Several talks in the COMSOC Seminar Series are focused on problems in fair division. Watch out for (among others):

- Ayumi Igarashi (NII Tokyo): Fair Division of House Chores
- Warut Suksompong (Singapore): Picking Sequences and Monotonicity in Weighted Fair Division
- Erel Segal-Halevi (Ariel): Fair Division of Electricity
- Maria Kyropoulou (Essex): On Interim Envy-Free Allocation Lotteries
- Anna Bogomolnaia (Glasgow): Guarantees in Fair Division
- Francis Su (Harvey Mudd): Multilabeled Versions of Sperner’s and Fan’s Lemmas and Applications
- Xiaohui Bei (Nanyang Technological University): Fair Division of Mixed Divisible and Indivisible Goods
- Jérôme Lang (Paris): Collective Decision Making under Incomplete Knowledge: Possible and Necessary Solutions

Rohit Vaish taught an excellent mini-course on Fair Division at IIT Gandhinagar in 2018:

Several lectures in the ACM Summer School on Game Theory (by Siddarth Barman and Nidhi Rathi) were on themes related to Fair Division:

- An Introduction to Cake-Cutting
- Two Algorithms for Finding Proportional Allocations
- Envy-Freenes and Approximate EF
- Sperner’s Lemma and Applications
- Cake Cutting with a Secret Agent
- Fairness Notions for Indivisible Goods
- Computing EF1 Allocations: Cycle Trading and Round Robin
- An Introduction to Rent Division
- Rent Division and Maximum Weight Matchings
- Hall’s Theorem and Maximin Share

Check out the talks on

*Algorithms for Fair Division and Collective Welfare*by Siddharth Barman (Part 1, Part 2) at Recent Trends in Algorithms, 2022.Visualize several fair division algorithms at MatchU, a project by Hadi Hosseini.

This is a lovely popular lecture on Cake Cutting by Francis Su.

## References

*Handbook of Computational Social Choice*. Cambridge University Press. https://doi.org/10.1017/CBO9781107446984.

## Footnotes

I will implicitly assume the indivisble setting, but the ideas carry over naturally to cake cutting.↩︎

Note: the official word is

*fairness*.↩︎Envy-freeness up to one/any good, equitability up to one/any good, and so on.↩︎

The hope is that restricted sub-classes of valuations may “behave” better.↩︎

Fair division with subsidies.↩︎

Fair division with charity, hidden items, and so on.↩︎

Fractional fair division or fair division with sharing.↩︎