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

Additive Valuations

For indivisible items, it’s common to assume that valuations are additive, i.e, the value that an agent has for a bundle of items S is the same as the sum of the values that it has for each of the individual items, i.e: v(S,a) = \sum_{x \in S}v(\{x\},a).

Normalized Valuations

To make apples-to-apples comparisons between agents, it is common to assume that the values themselves are normalized: imagine that every agent has 100 points that they must use fully to express their desires.

In other words, if R is the set of all resources, we have: v(R,a) = 100 for all agents a.

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:

  1. Every resource is allocated to some agent.
  2. 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 R1 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.

Proportional Division

The allocation D is proportional if every agent gets at least their “due” share according to his own value function. In particular, each of the n agents gets a subset of R which they value as at least 1/n of the total value:

V(D_a,a)\geqslant V_{a}(R)/n ~~~ \forall a \in A.

Envy-Freeness

The allocation D is envy-free if no agent values someone else’s bundle more than their own: i.e, if an agent a considers agent b’s bundle, they find that they value their own bundle at least as much as they value b’s:

v(D_a,a) \geqslant v(D_b,a) ~~~ \forall a,b \in A.

Equitability

The allocation D is equitable if all agents have the same value for their bundles:

v(D_a,a) = v(D_b,b) ~~~ \forall a,b \in A.

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.

Pareto Optimality

The allocation D is Pareto optimal if no other allocation would make someone better off without making someone else worse off. In other words, for any allocation D^\prime \neq D, if there exists an agent a for whom:

v(D^\prime_a,a) > v(D_a,a),

then there is also an agent b for whom: v(D^\prime_b,b) < v(D_b,b).

Fix any notion of happiness2 — say P, and efficiency — say Q. Two questions are of immediate interest:

  1. Do allocations that satisfy P and Q always exist?
  2. 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:

  1. What if3 the allocations could be approximately envy-free/equitable?
  2. What if4 the valuations were not completely arbitrary?
  3. What if5 we could introduce some dummy items or money into the systsem to make things work?
  4. What if6 we didn’t have to allocate everything?
  5. What if7 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!

Credits. Many thanks to Rohit Vaish for inputs and pointers!

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):

    1. Ayumi Igarashi (NII Tokyo): Fair Division of House Chores
    2. Warut Suksompong (Singapore): Picking Sequences and Monotonicity in Weighted Fair Division
    3. Erel Segal-Halevi (Ariel): Fair Division of Electricity
    4. Maria Kyropoulou (Essex): On Interim Envy-Free Allocation Lotteries
    5. Anna Bogomolnaia (Glasgow): Guarantees in Fair Division
    6. Francis Su (Harvey Mudd): Multilabeled Versions of Sperner’s and Fan’s Lemmas and Applications
    7. Xiaohui Bei (Nanyang Technological University): Fair Division of Mixed Divisible and Indivisible Goods
    8. 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:

    1. Introduction to Cake Cutting
    2. Introduction to the setting of Indivisible Goods
    3. Cake Cutting Revisited
    4. Algorithms for Indivisible Goods
    5. Open Problems

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

    1. An Introduction to Cake-Cutting
    2. Two Algorithms for Finding Proportional Allocations
    3. Envy-Freenes and Approximate EF
    4. Sperner’s Lemma and Applications
    5. Cake Cutting with a Secret Agent
    6. Fairness Notions for Indivisible Goods
    7. Computing EF1 Allocations: Cycle Trading and Round Robin
    8. An Introduction to Rent Division
    9. Rent Division and Maximum Weight Matchings
    10. 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

Amanatidis, Georgios, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A. Voudouris, and Xiaowei Wu. 2022. “Fair Division of Indivisible Goods: A Survey.” arXiv. https://doi.org/10.48550/ARXIV.2208.08782.
Brandt, Felix, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, eds. 2016. Handbook of Computational Social Choice. Cambridge University Press. https://doi.org/10.1017/CBO9781107446984.

Footnotes

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

  2. Note: the official word is fairness.↩︎

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

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

  5. Fair division with subsidies.↩︎

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

  7. Fractional fair division or fair division with sharing.↩︎

© 2022 • Neeldhara Misra • Credits •

 

Corrections? Please leave a comment here or a PR in this repository, thanks!

I’d rather be a failure at something I love than a success at something I hate.

George Burns

You live and you learn — at any rate, you live.

Douglas Adams

A problem worthy of attack proves its worth by fighting back.

Paul Erdos