Fair Division
The study of how to divide resources among agents so that each receives a fair share according to some criterion.
Definition
An allocation is proportional if each of agents receives at least of the total value by their own measure. It is envy-free if no agent prefers another's bundle to their own.
Fair division problems are categorized as divisible (cake-cutting) or indivisible (goods/items), and as homogeneous or heterogeneous.
Intuition
Fair division asks: what does each person deserve, and how can algorithms guarantee it without knowing their private valuations?
The canonical cake-cutting problem asks for a protocol guaranteeing each player a piece they value at of the whole.
Worked example
The "I cut, you choose" protocol for two players guarantees envy-free division.
Dubins-Spanier (1961) moving-knife protocol achieves proportional division for players.
The math
The Robertson-Webb query model formalizes cake-cutting algorithms that ask "evaluate" and "cut" queries.
Envy-free division for players with arbitrary valuations requires a number of queries that is (Even-Paz) or more, and is not guaranteed to exist for indivisible goods.
Where it is used
Estate settlement, divorce proceedings, international treaty negotiations (e.g., maritime boundaries), and resource allocation in computing.
Increasingly applied in AI for multi-agent resource allocation.
More in Game theory
Assembled from the ReLU.chat curated knowledge base. These explanations are concise on purpose; check the sources for anything important.