Fair cake-cutting

Fair cake-cutting is a kind of fair division 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; 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, which is mentioned already in the book of Genesis. It solves the fair division problem for two people. The modern study of fair cake-cutting was initiated during World War II, when Hugo Steinhaus asked his students Stefan Banach and Bronisław Knaster to find a generalization of divide-and-choose to three or more people. They developed the last diminisher procedure.^[1] Today, fair cake-cutting is the subject of intense research in mathematics, computer science, economics and political science.^[2]

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 with respect to the length, area or (in general) Lebesgue measure.^[3] 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 ${\displaystyle X_{i}}$, and ${\displaystyle C=X_{1}\sqcup \cdots \sqcup X_{n}}$.

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

${\displaystyle \forall {i}:\ V_{i}(X_{i})\geq 1/n}$

For n people with additive valuations, a proportional division always exists. The most common protocols are:

• Last diminisher, 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²) actions.
• The Dubins–Spanier Moving-knife procedure is a continuous-time version of Last diminisher.^[4]
• Fink protocol (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 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.

자세한 내용 및 전체 참조사항은 비례 케이크 자르기를 참조하십시오.

비례성 기준은 국민의 권리가 평등하지 않은 상황에 일반화할 수 있다. 예를 들어 다른 자격을 가진 비례 케이크 커팅의 경우, 케이크는 주주들 소유로 그들 중 한 명은 20%, 다른 한 명은 80%의 케이크를 보유하고 있다. 이는 가중 비례성(WPR)의 기준으로 이어진다.

$모든 i:V_{i}(X_{i})\geq w_{i}}}$

w가_i 1에 해당하는 가중치인 경우.

부러움-자유

또 다른 일반적인 기준은 질투-자유(EF)이다. 부러움이 없는 케이크 커팅에서, 각 사람은 적어도 다른 모든 조각들만큼 그가 소중히 여기는 조각을 받는다. 기호:

${\displaystyle \all i,j:\ V_{i}(X_{i})\geq V_{i}(X_{j})}$

어떤 경우에는 다음 표에 요약한 비례성과 시기-자유 사이에 함축적 관계가 있다.

에이전트	가치평가	EF는 PR을 의미하나?	PR은 EF를 의미하나?
2	첨가제의	네	네
2	일반적	아니요.	네
3+	첨가제의	네	아니요.
3+	일반적	아니요.	아니요.

분할 및 선택 프로토콜은 항상 EF인 할당을 찾는다. 값 함수가 가법적이면 이 구획도 PR이고, 그렇지 않으면 비례성이 보장되지 않는다.

N인에 대한 EF 부문은 일관된 선호도 집합으로 표현될 수 있는 한 부가 가치가 없는 경우에도 존재한다. EF 분할은 파편이 연결되어야 하는 경우와 파편이 분리될 수 있는 보다 쉬운 경우를 위해 별도로 연구되었다.

연결된 조각의 주요 결과는 다음과 같다.

• 스트롬퀴스트 무빙 나이브 시술은 미리 정해진 방식으로 케이크 위로 칼을 계속 옮기라고 지시해 3명이 부러움을 느끼지 않는 분열을 연출한다.
• 시몬스의 프로토콜은 임의의 정밀도로 n명의 사람들에게 질투가 없는 분단의 근사치를 산출할 수 있다. 가치함수가 가법적이면 분할도 비례한다. 그렇지 않으면 분단은 여전히 부러움이 없겠지만 반드시 비례하지는 않을 것이다. 그 알고리즘은 몇몇 공정한 분할 문제를 해결하는 빠르고 실용적인 방법을 제공한다.^[5][6]

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 ${\displaystyle \epsilon >0}$, it returns a division in which the value of each partner is at least the largest value minus ${\displaystyle \epsilon }$, in time ${\displaystyle O(n^{2}/\epsilon )}$.
• 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²) queries. There is a large gap between this result and the runtime complexity of the best known procedure.

See envy-free cake-cutting for more details and complete references.

Other criteria

A third, less common criterion is equitability (EQ). In an equitable division, 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:

${\displaystyle \ forall i,j:\ V_{i}(X_{i})=V_{j}(X_{j})}$

네 번째 기준은 정확성이다. 각 파트너 i의 자격이 w인_i 경우, 정확한 중분류는 다음과 같은 중분류에 해당한다.

${\displaystyle \forall {i,j}\ V_{i}(X_{j})=w_{j}}}$

가중치가 모두 같을 경우(1/n) 분할을 완전이라고 하며, 다음과 같이 한다.

${\displaystyle \ forall i,j:\ V_{i}(X_{j})=1/n}$

기하학적 요구 사항

경우에 따라, 파트너에게 할당된 조각들은 공정할 뿐만 아니라 일부 기하학적 제약을 충족시켜야 한다.

• 가장 일반적인 제약조건은 연결성이다. "케이크"가 1차원 간격인 경우, 이것은 각 조각이 또한 간격이라는 요구조건으로 해석된다. 케이크가 1차원 원("파이")인 경우, 이것은 각 조각이 호가 되어야 한다는 것을 의미하며, 공정한 파이 자르기를 참조한다.
• 또 다른 제약조건은 인접성이다. 이 제약조건은 '케이크'가 주변국 간에 분단해야 하는 분쟁지역인 경우에 적용된다. 이 경우, 각 국가에 할당된 조각이 현재의 영토에 인접하도록 요구할 수 있다. 이 제약은 힐의 토지 분할 문제에 의해 처리된다.
• 토지 분할에는 종종 2차원 기하학적 제약이 있다. 예를 들어 각 조각은 정사각형 또는 (더 일반적으로) 뚱뚱한 물체가 되어야 한다.^[7]

절차요구사항

최종 파티션의 원하는 속성 외에도 분할 프로세스의 원하는 속성도 있다. 이러한 속성 중 하나는 진실성(일명 인센티브 호환성)이며, 두 가지 수준으로 나온다.

• 진실성이 약하다는 것은 파트너가 알고리즘에 자신의 진가치를 공개하면 다른 파트너가 어떤 일을 하든 상관없이 공정한 몫(예: 비례분할의 경우 케이크 전체 값의 1/n)을 받을 수 있다는 것을 의미한다. 다른 모든 파트너들이 그를 해칠 유일한 의도를 가지고 연합을 한다고 해도, 그는 여전히 그의 보장된 비율을 받을 것이다. 대부분의 케이크 커팅 알고리즘은 이런 의미에서 진실하다.^[1]
• 진실성이 강하다는 것은 어떤 파트너도 거짓말을 해서 얻을 수 없다는 것을 의미한다. 즉, 진실을 말하는 것이 지배적인 전략이다. 대부분의 케이크 커팅 프로토콜은 강하게 진실하지 않지만, 일부 진실된 프로토콜은 개발되었다; 진실된 케이크 커팅을 보라.

또 다른 특성은 대칭이다. 즉, 절차상 서로 다른 역할 사이에 차이가 있어서는 안 된다. 이 특성의 몇 가지 변형이 연구되었다.

• 익명성을 위해서는 대리인이 권한을 부여받고 절차를 재실행할 경우 각 대리인은 원래 집행과 정확히 동일한 부분을 받게 된다. 이것은 강력한 조건이다; 현재 익명의 절차는 2명의 요원에게만 알려져 있다.
• 대칭성은 에이전트를 순열하고 절차를 다시 실행할 경우 각 에이전트는 원래 실행에서와 동일한 값을 수신해야 한다. 이것은 익명성보다 약하다; 현재 대칭적이고 비례적인 절차는 모든 수의 에이전트에 대해 알려져 있으며, O(n³) 질의가 필요하다. 대칭적이고 질투 없는 절차는 많은 수의 에이전트에게 알려져 있지만, 훨씬 더 오래 걸린다 - 기존의 질투 없는 절차의 실행이 필요하다.
• 아리스토텔레스주의에서는 두 대리인이 동일한 가치 측정치를 갖는 경우 동일한 가치를 제공받을 것을 요구한다. 이것은 대칭보다 약하다; 그것은 어떤 질투 없는 절차로도 만족한다. 더욱이 아리스토텔레스적, 비례적 절차는 임의의 수의 에이전트에 대해 알려져 있으며, O(n³) 질의가 필요하다.

자세한 내용 및 참조 사항은 대칭적인 공정한 케이크 커팅을 참조하십시오.

제3의 절차적 요건은 단조로움이다. 더 작은/더 큰 케이크와 더 작은/더 큰 에이전트 세트로 분할 절차를 다시 적용할 때, 모든 에이전트의 효용성은 동일한 방향으로 변경되어야 한다. 자세한 내용은 리소스 단일화를 참조하십시오.

효율성 요구사항

정의와 더불어 분업의 경제적 효율을 고려하는 것이 일반적이다; 효율적인 케이크 커팅을 보라. 몇 가지 수준의 효율성이 있다.

• 더 약한 개념은 파레토 효율이다. 케이크 전체를 한 사람에게 주는 것만으로도 쉽게 만족할 수 있는데, 공정성과 연계해 이를 충족시키는 것이 과제다. Efficient suppy-free division을 참조하십시오.
• 보다 강력한 개념은 실용성-최대성 - 효용성의 합을 최대화한다. (UM). 가치 함수가 가미되어 있을 때 UM 분할이 존재한다. 직관적으로 UM 부문을 만들려면 케이크 한 조각을 가장 소중하게 여기는 사람에게 나눠줘야 한다. 예시 케이크에서 UM 사단은 전체 초콜릿을 앨리스에게 주고 바닐라 전체를 조지에게 주면서 9 + 4 = 13이라는 공리주의적 가치를 달성하게 된다. 이 과정은 가치 함수가 조각처럼 일정할 때, 즉 케이크를 조각으로 나누어 모든 사람에게 가치 밀도가 일정하게 유지될 수 있을 때 수행하기가 쉽다. 값 함수가 조각처럼 일정하지 않은 경우, UM 할당 존재는 고전적인 측정-이론적 이론에서 따른다. 공리주의 케이크 자르기를 참조하십시오.

Efficient fair division

For n people with additive value functions, a PEEF division always exists.^[8]

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.^[9] 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.^[10]

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.^[11] If the value density functions are additive and Lipschitz continuous, 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".^[11]

An EF division is not necessarily UM.^[12][13] 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.^[14]

Models of computation

Reasoning about the run-time complexity of algorithms requires a model of computation. Several such models are common in the literature:

• The Robertson–Webb query model - 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".
• Moving-nives 모델 - 알고리즘이 일부 에이전트들이 "Stop"을 외칠 때까지 케이크 위로 하나 이상의 칼을 계속 이동시킨다.
• 모든 대리인이 메커니즘에 대한 전체 가치 평가를 공개하는 직접적 계시 모델. 이 모형은 예를 들어, 가치평가가 조각이 통일되어 있거나 조각이 일정하거나 조각이 선형이 될 때 간결하게 표현될 수 있을 때만 타당하다.
• 시뮬타누스는 에이전트들이 가치 측정의 분석을 동시에 보내는 모델을 보고한다. 디스커트화는 컷포인트의 순서와 이들 컷포인트 사이의 조각 값(예: 두 에이전트에 대한 프로토콜)이다. 각 에이전트는 컷포인트의 순서가 (0,x)와 (x,1)의 값이 1/2인 3개 컷포인트(0,x,1)로 보고해야 할 수 있다.^[15]

여러 케이크를 나누는 중

케이크가 여러 개 있는 케이크 커팅 문제가 일반화돼 있고, 각 대리점은 케이크 한 개에 한 조각을 넣어야 한다.

• 클라우티어, 나이만, 쑤는^[16] 두 명의 선수를 부러워하지 않는 멀티 케이크 부문을 공부한다. 두 개의 케이크에 대해, 그들은 두 개의 에이전트가 있고 각각의 케이크를 두 조각으로 자르면 EF 할당이 존재하지 않을 수 있다는 것을 증명한다. 그러나 EF 할당은 2개의 에이전트가 있고 1개의 케이크를 3조각으로 자르거나(최소원료 조각은 폐기), 3개의 에이전트가 있고 각 케이크를 2조각으로 자르거나(하나의 에이전트는 무시되고, 나머지 2개는 EF 할당)할 때 존재한다.
• 레버트, 마우니에, 카보르노^[17] 두 케이크의 경우, 세 개의 에이전트가 있고 각각의 케이크를 5조각으로 자르면 EF 할당이 항상 존재한다는 것을 증명한다(각 케이크에서 가장 적게 원했던 두 조각은 버려진다).
• 나이만, 수, 제르빕은^[18] 케이크의 경우 k(n-1)+1 에이전트가 있고 각 케이크를 n조각으로 자르면 EF 할당이 항상 존재한다는 것을 증명한다(일부 n 에이전트의 경우 할당이 EF이다).

관련된 두 가지 문제는 다음과 같다.

• 케이크가 "레이어"로 배열되고 동일한 에이전트의 조각이 중복되지 않아야 하는 다중 레이어 케이크 커팅(^[19]예: 각 케이크는 낮에 특정 시설을 이용할 수 있는 시간을 나타내며, 에이전트는 두 개의 설비를 동시에 사용할 수 없다)
• 요원들이 케이크 하나하나에 한 조각도 얹고 싶어하지 않는 공정한 멀티 케이크 커팅은 반대로 가능한 한 적은 케이크에 한 조각도 얹고 싶어 한다.^[20]

참고 항목

• 공정한 항목 할당 – 나눌 항목이 분리될 수 없는 유사한 문제.

참조

추가 읽기

• 공정한 분배에 관한 책 목록
• 공정분할에 관한 연구논문 목록