![Cut the Cake (3032677729)](https://upload.wikimedia.org/wikipedia/commons/0/0f/Cut_the_Cake_%283032677729%29.jpg)
Fair cake-cutting is a kind of
fair division
Fair division is the problem in game theory of dividing a set of resources among several people who have an entitlement to them so that each person receives their due share. That problem arises in various real-world settings such as division of inh ...
problem. The problem involves a ''heterogeneous'' resource, such as a cake with different toppings, that is assumed to be ''divisible'' – it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible. The division should be ''unanimously'' fair - each person should receive a piece that he or she believes to be a fair share.
The "cake" is only a
metaphor
A metaphor is a figure of speech that, for rhetorical effect, directly refers to one thing by mentioning another. It may provide (or obscure) clarity or identify hidden similarities between two different ideas. Metaphors are often compared wit ...
; procedures for fair cake-cutting can be used to divide various kinds of resources, such as land estates, advertisement space or broadcast time.
The prototypical procedure for fair cake-cutting is
divide and choose
Divide and choose (also Cut and choose or I cut, you choose) is a procedure for fair division of a continuous resource, such as a cake, between two parties. It involves a heterogeneous good or resource ("the cake") and two partners who have diffe ...
, which is mentioned already in the book of
Genesis
Genesis may refer to:
Bible
* Book of Genesis, the first book of the biblical scriptures of both Judaism and Christianity, describing the creation of the Earth and of mankind
* Genesis creation narrative, the first several chapters of the Book of ...
. It solves the fair division problem for two people. The modern study of fair cake-cutting was initiated during
World War II
World War II or the Second World War, often abbreviated as WWII or WW2, was a world war that lasted from 1939 to 1945. It involved the vast majority of the world's countries—including all of the great powers—forming two opposin ...
, when
Hugo Steinhaus
Hugo Dyonizy Steinhaus ( ; ; January 14, 1887 – February 25, 1972) was a Polish mathematician and educator. Steinhaus obtained his PhD under David Hilbert at Göttingen University in 1911 and later became a professor at the Jan Kazimierz Unive ...
asked his students
Stefan Banach
Stefan Banach ( ; 30 March 1892 – 31 August 1945) was a Polish mathematician who is generally considered one of the 20th century's most important and influential mathematicians. He was the founder of modern functional analysis, and an original ...
and
Bronisław Knaster
Bronisław Knaster (22 May 1893 – 3 November 1980) was a Polish mathematician; from 1939 a university professor in Lwów and from 1945 in Wrocław.
He is known for his work in point-set topology and in particular for his discoveries in 1922 of ...
to find a generalization of divide-and-choose to three or more people. They developed the
last diminisher
A last is a mechanical form shaped like a human foot. It is used by shoemakers and cordwainers in the manufacture and repair of shoes. Lasts typically come in pairs and have been made from various materials, including hardwoods, cast iron, an ...
procedure.
Today, fair cake-cutting is the subject of intense research in
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
,
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
,
economics
Economics () is the social science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goods and services.
Economics focuses on the behaviour and intera ...
and
political science
Political science is the scientific study of politics. It is a social science dealing with systems of governance and power, and the analysis of political activities, political thought, political behavior, and associated constitutions and la ...
.
[
Ariel Procaccia, "Cake Cutting Algorithms". Chapter 13 in: ]
Assumptions
There is a cake ''C'', which is usually assumed to be either a finite 1-dimensional segment, a 2-dimensional polygon or a finite subset of the multidimensional Euclidean plane R
''d''.
There are ''n'' people with
subjective value functions over ''C''. Each person ''i'' has a value function ''V''
''i'' which maps subsets of ''C'' to numbers. All value functions are assumed to be
absolutely continuous
In calculus, absolute continuity is a smoothness property of functions that is stronger than continuity and uniform continuity. The notion of absolute continuity allows one to obtain generalizations of the relationship between the two central oper ...
with respect to the length, area or (in general)
Lebesgue measure
In measure theory, a branch of mathematics, the Lebesgue measure, named after French mathematician Henri Lebesgue, is the standard way of assigning a measure to subsets of ''n''-dimensional Euclidean space. For ''n'' = 1, 2, or 3, it coincides wit ...
. This means that there are no "atoms" – there are no singular points to which one or more agents assign a positive value, so all parts of the cake are divisible. In many cases, the value functions are assumed to be
sigma additive (the value of a whole is equal to the sum of the values of its parts).
''C'' has to be divided to ''n'' disjoint subsets, such that each person receives a disjoint subset. The piece allocated to person ''i'' is called
, and
.
The ''n'' people have equal rights to ''C''. I.e., there is no dispute over the rights of the people – everyone agrees that everyone else is entitled to a fair share. The only problem is how to divide the cake such that each person receives a fair share.
In the following examples the following cake will be used as an illustration.
* The cake has two parts: chocolate and vanilla.
* There are two people: Alice and George.
* Alice values the chocolate as 9 and the vanilla as 1.
* George values the chocolate as 6 and the vanilla as 4.
Justice requirements
Proportionality
The original and most common criterion for justice is ''proportionality'' (PR). In a
proportional cake-cutting A proportional cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the proportionality criterion, namely, that every partner feels that his allocated share is worth at least 1/''n'' of t ...
, each person receives a piece that he values as at least 1/''n'' of the value of the entire cake. In the example cake, a proportional division can be achieved by giving all the vanilla and 4/9 of the chocolate to George (for a value of 6.66), and the other 5/9 of the chocolate to Alice (for a value of 5). In symbols:
:
For ''n'' people with additive valuations, a proportional division always exists. The most common protocols are:
*
Last diminisher
A last is a mechanical form shaped like a human foot. It is used by shoemakers and cordwainers in the manufacture and repair of shoes. Lasts typically come in pairs and have been made from various materials, including hardwoods, cast iron, an ...
, a protocol that can guarantee that the ''n'' pieces are connected (i.e. no person gets a set of two or more disconnected pieces). In particular, if the cake is a 1-dimensional interval then each person receives an interval. This protocol is discrete and can be played in turns. It requires O(''n''
2) actions.
* The Dubins–Spanier
Moving-knife procedure In the mathematics of social science, and especially game theory, a moving-knife procedure is a type of solution to the fair division problem. The canonical example is the division of a cake using a knife.
The simplest example is a moving-knif ...
is a continuous-time version of Last diminisher.
*
Fink protocol The Fink protocol (also known as Successive Pairs or Lone Chooser) is a protocol for proportional division of a cake.
Its main advantage is that it can work in an online fashion, without knowing the number of partners in advance. When a new partner ...
(also known as ''successive pairs'' or ''lone chooser'') is a discrete protocol that can be used for online division: given a proportional division for ''n'' − 1 partners, when a new partner enters the party, the protocol modifies the existing division so that both the new partner and the existing partners remain with 1/''n''. The disadvantage is that each partner receives a large number of disconnected pieces.
* The
Even–Paz protocol, based on recursively halving the cake and the group of agents, requires only O(''n'' log ''n'') actions. This is fastest possible deterministic protocol for proportional division, and the fastest possible protocol for proportional division which can guarantee that the pieces are connected.
*
Edmonds–Pruhs protocol Edmonds–Pruhs protocol is a protocol for fair cake-cutting. Its goal is to create a partially proportional division of a heterogeneous resource among ''n'' people, such that each person receives a subset of the cake which that person values as at ...
is a randomized protocol that requires only O(''n'') actions, but guarantees only a partially proportional division (each partner receives at least 1/''an'', where ''a'' is some constant), and it might give each partner a collection of "crumbs" instead of a single connected piece.
*
Beck land division protocol can produce a proportional division of a disputed territory among several neighbouring countries, such that each country receives a share that is ''both'' connected ''and'' adjacent to its currently held territory.
*
Woodall's super-proportional division protocol produces a division which gives each partner strictly more than 1/''n'', given that at least two partners have different opinions about the value of at least a single piece.
See
proportional cake-cutting A proportional cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the proportionality criterion, namely, that every partner feels that his allocated share is worth at least 1/''n'' of t ...
for more details and complete references.
The proportionality criterion can be generalized to situations in which the rights of the people are not equal. For example, in
proportional cake-cutting with different entitlements In the fair cake-cutting problem, the partners often have different entitlements. For example, the resource may belong to two shareholders such that Alice holds 8/13 and George holds 5/13. This leads to the criterion of ''weighted proportionality'' ...
, the cake belongs to shareholders such that one of them holds 20% and the other holds 80% of the cake. This leads to the criterion of ''weighted proportionality'' (WPR):
:
Where the ''w''
''i'' are weights that sum up to 1.
Envy-freeness
Another common criterion is ''envy-freeness'' (EF). In an
envy-free cake-cutting
An envy-free cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other sha ...
, each person receives a piece that he values at least as much as every other piece. In symbols:
:
In some cases, there are implication relations between proportionality and envy-freeness, as summarized in the following table:
The
divide and choose
Divide and choose (also Cut and choose or I cut, you choose) is a procedure for fair division of a continuous resource, such as a cake, between two parties. It involves a heterogeneous good or resource ("the cake") and two partners who have diffe ...
protocol finds an allocation that is always EF. If the value functions are additive then this division is also PR; otherwise, proportionality is not guaranteed.
An EF division for ''n'' people exists even when the valuations are not additive, as long as they can be represented as consistent preference sets. EF division has been studied separately for the case in which the pieces must be connected, and for the easier case in which the pieces may be disconnected.
For connected pieces the major results are:
*
Stromquist moving-knives procedure The Stromquist moving-knives procedure is a procedure for envy-free cake-cutting among three players. It is named after Walter Stromquist who presented it in 1980.
This procedure was the first envy-free moving knife procedure devised for three play ...
produces an envy-free division for 3 people, by giving each one of them a knife and instructing them to move their knives continuously over the cake in a pre-specified manner.
*
Simmons' protocol can produce an approximation of an envy-free division for ''n'' people with an arbitrary precision. If the value functions are additive, the division will also be proportional. Otherwise, the division will still be envy-free but not necessarily proportional. The algorithm gives a fast and practical way of solving some fair division problems.
Both these algorithms are infinite: the first is continuous and the second might take an infinite time to converge. In fact, envy-free divisions of connected intervals to 3 or more people cannot be found by ''any'' finite protocol.
For possibly-disconnected pieces the major results are:
*
Selfridge–Conway discrete procedure produces an envy-free division for 3 people using at most 5 cuts.
*
Brams–Taylor–Zwicker moving knives procedure produces an envy-free division for 4 people using at most 11 cuts.
* A
reentrant variant of the Last Diminisher protocol finds an additive approximation to an envy-free division in bounded time. Specifically, for every constant
, it returns a division in which the value of each partner is at least the largest value minus
, in time
.
* Three different procedures, one by
Brams and Taylor (1995) and one by
Robertson and Webb (1998) and one by Pikhurko (2000), produce an envy-free division for ''n'' people. Both algorithms require a finite but unbounded number of cuts.
* A procedure by Aziz and Mackenzie (2016) finds an envy-free division for ''n'' people in a bounded number of queries.
The negative result in the general case is much weaker than in the connected case. All we know is that every algorithm for envy-free division must use at least Ω(''n''
2) queries. There is a large gap between this result and the runtime complexity of the best known procedure.
See
envy-free cake-cutting
An envy-free cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other sha ...
for more details and complete references.
Other criteria
A third, less common criterion is ''equitability'' (EQ). In an
equitable division Equitable (EQ) cake-cutting is a kind of a fair cake-cutting problem, in which the fairness criterion is equitability. It is a cake-allocation in which the subjective value of all partners is the same, i.e., each partner is equally happy with his/h ...
, each person enjoys exactly the same value. In the example cake, an equitable division can be achieved by giving each person half the chocolate and half the vanilla, such that each person enjoys a value of 5. In symbols:
:
A fourth criterion is ''exactness''. If the entitlement of each partner ''i'' is ''w''
''i'', then an
exact division Exact division, also called consensus division, is a partition of a continuous resource ("fair cake-cutting, cake") into some ''k'' pieces, such that each of ''n'' people with different tastes agree on the value of each of the pieces. For example, c ...
is a division in which:
:
If the weights are all equal (to 1/''n'') then the division is called ''perfect'' and:
:
Geometric requirements
In some cases, the pieces allocated to the partners must satisfy some geometric constraints, in addition to being fair.
* The most common constraint is ''
connectivity
Connectivity may refer to:
Computing and technology
* Connectivity (media), the ability of the social media to accumulate economic capital from the users connections and activities
* Internet connectivity, the means by which individual terminal ...
''. In case the "cake" is a 1-dimensional interval, this translates to the requirement that each piece is also an interval. In case the cake is a 1-dimensional circle ("pie"), this translates to the requirement that each piece be an arc; see
fair pie-cutting The fair pie-cutting problem is a variation of the fair cake-cutting problem, in which the resource to be divided is circular.
As an example, consider a birthday cake shaped as a disk. The cake should be divided among several children such that no ...
.
* Another constraint is ''adjacency''. This constraint applies to the case when the "cake" is a disputed territory that has to be divided among neighboring countries. In this case, it may required that the piece allocated to each country is adjacent to its current territory; this constraint is handled by
Hill's land division problem.
* In land division there are often two-dimensional geometric constraints, e.g., each piece should be a square or (more generally) a
fat object.
Procedural requirements
In addition to the desired properties of the final partitions, there are also desired properties of the division process. One of these properties is truthfulness (aka
incentive compatibility
A mechanism is called incentive-compatible (IC) if every participant can achieve the best outcome to themselves just by acting according to their true preferences.
There are several different degrees of incentive-compatibility:
* The stronger d ...
), which comes in two levels.
* ''Weak truthfulness'' means that if the partner reveals his true value measure to the algorithm, he is guaranteed to receive his fair share (e.g. 1/''n'' of the value of the entire cake, in case of proportional division), regardless of what other partners do. Even if all other partners make a coalition with the only intent to harm him, he will still receive his guaranteed proportion. Most cake-cutting algorithms are truthful in this sense.
[
* ''Strong truthfulness'' means that no partner can gain from lying. I.e., telling the truth is a ]dominant strategy
In game theory, strategic dominance (commonly called simply dominance) occurs when one strategy is better than another strategy for one player, no matter how that player's opponents may play. Many simple games can be solved using dominance. The ...
. Most cake-cutting protocols are not strongly truthful, but some truthful protocols have been developed; see truthful cake-cutting Truthful cake-cutting is the study of algorithms for fair cake-cutting that are also truthful mechanisms, i.e., they incentivize the participants to reveal their true valuations to the various parts of the cake.
The classic divide and choose proced ...
.
Another property is symmetry: there should not be a difference between different roles in the procedure. Several variants of this property have been studied:
* ''Anonymity'' requires that, if the agents are permuted and the procedure is re-executed, then each agent receives exactly the same piece as in the original execution. This is a strong condition; currently, an anonymous procedure is known only for 2 agents.
* ''Symmetry'' requires that, if the agents are permuted and the procedure is re-executed, then each agent receives the same ''value'' as in the original execution. This is weaker than anonymity; currently, a symmetric and proportional procedure is known for any number of agents, and it takes O(''n''3) queries. A symmetric and envy-free procedure is known for any number of agents, but it takes much longer - it requires ''n''! executions of an existing envy-free procedure.
* ''Aristotelianity'' requires that, if two agents have an identical value-measure, then they receive the same value. This is weaker than symmetry; it is satisfied by any envy-free procedure. Moreover, an aristotelian and proportional procedure is known for any number of agents, and it takes O(''n''3) queries.
See symmetric fair cake-cutting
Symmetric fair cake-cutting is a variant of the fair cake-cutting problem, in which fairness is applied not only to the final outcome, but also to the assignment of roles in the division procedure.
As an example, consider a birthday cake that has ...
for details and references.
A third family of procedural requirements is monotonicity: when a division procedure is re-applied with a smaller/larger cake and a smaller/larger set of agents, the utility of all agents should change in the same direction. See resource monotonicity
Resource monotonicity (RM; aka aggregate monotonicity) is a principle of fair division. It says that, if there are more resources to share, then all agents should be weakly better off; no agent should lose from the increase in resources. The RM pri ...
for more details.
Efficiency requirements
In addition to justice, it is also common to consider the economic efficiency of the division; see efficient cake-cutting Efficient cake-cutting is a problem in economics and computer science. It involves a ''heterogeneous'' resource, such as a cake with different toppings or a land with different coverings, that is assumed to be ''divisible'' - it is possible to cut a ...
. There are several levels of efficiency:
* The weaker notion is Pareto efficiency
Pareto efficiency or Pareto optimality is a situation where no action or allocation is available that makes one individual better off without making another worse off. The concept is named after Vilfredo Pareto (1848–1923), Italian civil engine ...
. It can be easily satisfied by just giving the entire cake to a single person; the challenge is to satisfy it in conjunction with fairness. See Efficient envy-free division Efficiency and fairness are two major goals of welfare economics. Given a set of resources and a set of agents, the goal is to divide the resources among the agents in a way that is both Pareto efficient (PE) and envy-free (EF). The goal was first ...
.
* A stronger notion is utilitarian-maximality - maximizing the sum of utilities. (UM). When the value functions are additive, UM divisions exist. Intuitively, to create a UM division, we should give each piece of cake to the person that values it the most. In the example cake, a UM division would give the entire chocolate to Alice and the entire vanilla to George, achieving a utilitarian value of 9 + 4 = 13. This process is easy to carry out when the value functions are piecewise-constant, i.e. the cake can be divided to pieces such that the value density of each piece is constant for all people. When the value functions are not piecewise-constant, the existence of UM allocations follows from classic measure-theoretic theorems. See Utilitarian cake-cutting Utilitarian cake-cutting (also called maxsum cake-cutting) is a rule for dividing a heterogeneous resource, such as a cake or a land-estate, among several partners with different cardinal utility functions, such that the ''sum'' of the utilities of ...
.
Efficient fair division
For ''n'' people with additive value functions, a PEEF division always exists.
If the cake is a 1-dimensional ''interval'' and each person must receive a connected interval, the following general result holds: if the value functions are strictly monotonic (i.e. each person strictly prefers a piece over all its proper subsets) then every EF division is also PE. Hence, Simmons' protocol produces a PEEF division in this case.
If the cake is a 1-dimensional ''circle'' (i.e. an interval whose two endpoints are topologically identified) and each person must receive a connected arc, then the previous result does not hold: an EF division is not necessarily PE. Additionally, there are pairs of (non-additive) value functions for which no PEEF division exists. However, if there are 2 agents and at least one of them has an additive value function, then a PEEF division exists.
If the cake is 1-dimensional but each person may receive a disconnected subset of it, then an EF division is not necessarily PE. In this case, more complicated algorithms are required for finding a PEEF division.
If the value functions are additive and piecewise-constant, then there is an algorithm that finds a PEEF division. If the value density functions are additive and Lipschitz continuous
In mathematical analysis, Lipschitz continuity, named after German mathematician Rudolf Lipschitz, is a strong form of uniform continuity for functions. Intuitively, a Lipschitz continuous function is limited in how fast it can change: there exis ...
, then they can be approximated as piecewise-constant functions "as close as we like", therefore that algorithm approximates a PEEF division "as close as we like".[
An EF division is not necessarily UM. One approach to handle this difficulty is to find, among all possible EF divisions, the EF division with the highest utilitarian value. This problem has been studied for a cake which is a 1-dimensional interval, each person may receive disconnected pieces, and the value functions are additive.]
Models of computation
Reasoning about the run-time complexity of algorithms requires a model of computation
In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how ...
. Several such models are common in the literature:
* The Robertson–Webb query model In computer science, the Robertson–Webb (RW) query model is a model of computation used by algorithms for the problem of fair cake-cutting. In this problem, there is a resource called a "cake", and several agents with different value measures on t ...
- in which the algorithm may ask each agent a query of one of two kinds: "evaluate a given piece of cake" or "mark a piece of cake with a given value".
* The Moving-knives model - in which the algorithm continuously moves one or more knives above the cake until some agents shout "stop".
* The direct revelation model - in which all agents reveal their entire valuation to the mechanism. This model makes sense only when the valuations can be represented succinctly, for example, when they are piecewise-uniform, piecewise-constant
In mathematics, a function (mathematics), function on the real numbers is called a step function if it can be written as a finite set, finite linear combination of indicator functions of interval (mathematics), intervals. Informally speaking, a s ...
or piecewise-linear.
*The simultanoues reports model - in which agents simultaneously send discretizations of their value-measures. A discretization is a sequence of cut-points, and the values of pieces between these cut-points (for example: a protocol for two agents might require each agent to report a sequence of three cut-points (0,''x'',1) where the values of (0,''x'') and (''x'',1) are 1/2).
Dividing multiple cakes
There is a generalization of the cake-cutting problem in which there are several cakes, and each agent needs to get a piece in each cake.
* Cloutier, Nyman and Su study two-player envy-free multi-cake division. For two cakes, they prove that an EF allocation may not exist when there are 2 agents and each cake is cut into 2 pieces. However, an EF allocation exists when there are 2 agents and one cake is cut into 3 pieces (the least-wanted piece is discarded), or when there are 3 agents and each cake is cut into 2 pieces (one agent is ignored; the allocation is EF for the remaining two).
* Lebert, Meunier and Carbonneaux prove, for two cakes, that an EF allocation always exists when there are 3 agents and each cake is cut into 5 pieces (the two least-wanted pieces in each cake are discarded).
* Nyman, Su and Zerbib prove, for ''k'' cakes, that an EF allocation always exists when there are ''k''(''n''-1)+1 agents and each cake is cut into ''n'' pieces (the allocation is EF for some set of ''n'' agents).
Two related problems are:
* Multi-layered cake-cutting, where the cakes are arranged in "layers" and pieces of the same agent must not overlap (for example, each cake represents the time in which a certain facility is available during the day; an agent cannot use two facilities simultaneously).
* Fair multi-cake cutting,[{{Cite journal, last=Segal-Halevi, first=Erel, date=2021-03-11, title=Fair multi-cake cutting, url=https://www.sciencedirect.com/science/article/pii/S0166218X20304650, journal=Discrete Applied Mathematics, language=en, volume=291, pages=15–35, doi=10.1016/j.dam.2020.10.011, s2cid=219792647, issn=0166-218X] where the agents do not want to get a piece on every cake, on the contrary, they want to get pieces on as few cakes as possible.
See also
* Fair item allocation
Fair item allocation is a kind of a fair division problem in which the items to divide are ''discrete'' rather than continuous. The items have to be divided among several partners who value them differently, and each item has to be given as a whole ...
– a similar problem in which the items to divide are indivisible
References
Further reading
A list of books about fair division
A list of research papers about fair division
Cake-cutting