케이크 공평하게 자르기

다양한 토핑이 올려진 케이크를 단순히 동일한 크기의 조각으로 자르면, 서로 다른 사람들이 각기 다른 양의 토핑을 받게 되며, 일부는 이를 케이크의 공평한 분배로 여기지 않을 수 있다.

케이크 공평하게 자르기는 공평한 분할 문제의 한 유형이다. 이 문제는 케이크와 같이 서로 다른 토핑이 올려진 이질적인 자원을 대상으로 하며, 이 자원은 분할 가능한 것으로 가정된다. 즉, 가치를 훼손하지 않고 임의로 작은 조각으로 자를 수 있다. 이 자원은 케이크의 각기 다른 부분에 대해 서로 다른 선호도를 가진 여러 당사자들 사이에서 나누어져야 한다. 예를 들어, 어떤 이는 초콜릿 토핑을 선호하고, 어떤 이는 체리를 선호하며, 또 어떤 이는 단순히 가능한 한 큰 조각을 원할 수 있다. 분배는 만장일치로 공평해야 한다. 즉, 각자가 받은 조각이 공평한 몫이라고 믿을 수 있어야 한다.

여기서 "케이크"는 단지 은유일 뿐이다. 공평한 케이크 자르기 절차는 토지, 광고 공간 또는 방송 시간과 같은 다양한 종류의 자원을 분배하는 데 사용될 수 있다.

공평한 케이크 자르기의 전형적인 절차는 '나누고 선택하기'이다. 이는 창세기에서 아브라함과 롯의 갈등을 해결하기 위해 언급된 바 있다. 이 절차는 두 사람 사이의 공평한 분배 문제를 해결한다. 공평한 케이크 자르기에 대한 현대적 연구는 제2차 세계 대전 중 후고 스테인하우스가 그의 학생인 스테판 바나흐와 브로니스와프 크나스터에게 '나누고 선택하기'를 세 사람 이상으로 일반화하는 방법을 찾아달라고 요청하면서 시작되었다. 그들은 '마지막 감축자' 절차를 개발했다. 오늘날 공평한 케이크 자르기는 수학, 컴퓨터 과학, 경제학, 정치학 분야에서 집중적인 연구의 대상이 되고 있다.

가정

케이크 C가 있으며, 이는 일반적으로 유한한 1차원 선분, 2차원 다각형, 또는 다차원 유클리드 평면 R^d의 유한 부분집합으로 가정된다.

C에 대해 주관적 가치 함수를 가진 n명의 사람이 있다. 각 사람 i는 C의 부분집합을 숫자에 대응시키는 가치 함수 V_i를 가진다. 모든 가치 함수는 길이, 면적 또는 (일반적으로) 르베그 측도에 대해 절대 연속인 것으로 가정된다. 이는 "원자"가 없다는 것을 의미한다. 즉, 한 명 이상의 당사자가 양의 가치를 부여하는 특이점이 없으므로 케이크의 모든 부분이 분할 가능하다. 많은 경우, 가치 함수는 시그마 가법적(전체의 가치가 그 부분들의 가치의 합과 같음)인 것으로 가정된다.

C는 n개의 서로 소인 부분집합으로 나누어져야 하며, 각 사람은 서로 소인 부분집합을 받는다. 사람 i에게 할당된 조각을 $X_{i}$라고 하며, $C=X_{1}\sqcup \cdots \sqcup X_{n}$이다.

n명의 사람들은 C에 대해 동등한 권리를 가진다. 즉, 사람들의 권리에 대한 분쟁은 없으며, 모두가 다른 모든 사람이 공평한 몫을 받을 자격이 있다는 데 동의한다. 유일한 문제는 각 사람이 공평한 몫을 받도록 케이크를 어떻게 나누느냐 하는 것이다.

다음 예시에서는 아래와 같은 케이크를 사용하여 설명한다.

• 케이크는 초콜릿과 바닐라 두 부분으로 구성되어 있다.
• 앨리스와 조지, 두 사람이 있다.
• 앨리스는 초콜릿을 9, 바닐라를 1로 평가한다.
• 조지는 초콜릿을 6, 바닐라를 4로 평가한다.

정의 요건

비례성

정의에 대한 원래의 가장 일반적인 기준은 '비례성'(PR)이다. 비례적 케이크 자르기에서 각 사람은 전체 케이크 가치의 최소 1/n만큼의 가치가 있다고 여기는 조각을 받는다. 예시 케이크에서 비례적 분배는 조지에게 모든 바닐라와 초콜릿의 4/9를 주고(6.66의 가치), 앨리스에게 나머지 초콜릿 5/9를 줌으로써(5의 가치) 달성할 수 있다. 기호로 표현하면 다음과 같다.

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

가법적 가치 평가를 하는 n명의 사람들에 대해, 비례적 분배는 항상 존재한다. 가장 일반적인 프로토콜은 다음과 같다.

• 마지막 감축자: n개의 조각이 연결되어 있음을 보장할 수 있는 프로토콜(즉, 어느 누구도 두 개 이상의 분리된 조각 집합을 받지 않음). 특히 케이크가 1차원 구간일 경우 각 사람은 하나의 구간을 받는다. 이 프로토콜은 이산적이며 차례로 진행할 수 있다. O(n²)의 행동이 필요하다.
• 두빈스-스패니어 움직이는 칼 절차: 마지막 감축자의 연속 시간 버전이다.
• 핑크 프로토콜(연속 쌍 또는 외로운 선택자로도 알려짐): 온라인 분배에 사용할 수 있는 이산 프로토콜이다. n - 1명의 파트너에 대한 비례적 분배가 주어졌을 때, 새로운 파트너가 참여하면 이 프로토콜은 새 파트너와 기존 파트너 모두가 1/n을 유지하도록 기존 분배를 수정한다. 단점은 각 파트너가 많은 수의 분리된 조각을 받는다는 것이다.
• 이븐-파즈 프로토콜: 케이크와 당사자 그룹을 재귀적으로 반으로 나누는 방식으로, O(n log n)의 행동만 필요하다. 이는 비례적 분배를 위한 가장 빠른 결정론적 프로토콜이며, 조각들이 연결되어 있음을 보장할 수 있는 가장 빠른 프로토콜이다.
• 에드먼즈-프루스 프로토콜: O(n)의 행동만 필요한 무작위화된 프로토콜이지만, 부분적으로 비례적인 분배만을 보장한다(각 파트너는 최소 1/an을 받으며, 여기서 a는 어떤 상수임). 또한 각 파트너에게 하나의 연결된 조각 대신 '부스러기' 모음을 줄 수 있다.
• 벡 토지 분할 프로토콜: 여러 인접 국가 간의 분쟁 영토에 대해 비례적 분할을 생성할 수 있으며, 각 국가는 현재 보유한 영토에 '연결되고' 인접한 몫을 받는다.
• 우달의 초비례적 분할 프로토콜: 최소 두 명의 파트너가 최소 하나의 조각에 대해 서로 다른 의견을 가지고 있다는 전제하에, 각 파트너에게 1/n보다 엄격히 더 많이 주는 분할을 생성한다.

더 자세한 내용과 완전한 참고 문헌은 비례적 케이크 자르기를 참조하라.

비례성 기준은 사람들의 권리가 동등하지 않은 상황으로 일반화될 수 있다. 예를 들어, 다른 권리를 가진 비례적 케이크 자르기에서 케이크는 한 사람이 20%, 다른 사람이 80%를 소유한 주주들의 것이다. 이는 '가중 비례성'(WPR) 기준으로 이어진다.

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

여기서 w_i는 합이 1인 가중치이다.

무질투성

또 다른 일반적인 기준은 '무질투성'(EF)이다. 무질투 케이크 자르기에서 각 사람은 다른 모든 조각만큼이나 가치 있다고 여기는 조각을 받는다. 기호로 표현하면 다음과 같다.

$\forall 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명에 대한 무질투 분할의 근사치를 임의의 정밀도로 생성할 수 있다. 가치 함수가 가법적이면 분할은 비례적이기도 할 것이다. 그렇지 않으면 분할은 여전히 무질투이지만 반드시 비례적일 필요는 없다. 이 알고리즘은 일부 공평한 분할 문제를 해결하는 빠르고 실용적인 방법을 제공한다.

이 두 알고리즘은 모두 무한하다. 첫 번째는 연속적이고 두 번째는 수렴하는 데 무한한 시간이 걸릴 수 있다. 사실, 3명 이상에 대한 연결된 구간의 무질투 분할은 '어떤' 유한한 프로토콜로도 찾을 수 없다.

가능한 분리된 조각에 대한 주요 결과는 다음과 같다.

• 셀프리지-컨웨이 이산 절차: 최대 5번의 자르기로 3명에 대한 무질투 분할을 생성한다.
• 브램스-테일러-즈위커 움직이는 칼 절차: 최대 11번의 자르기로 4명에 대한 무질투 분할을 생성한다.
• 마지막 감축자 프로토콜의 재진입 변형: 제한된 시간 내에 무질투 분할에 대한 가법적 근사치를 찾는다. 구체적으로, 모든 상수 $\epsilon >0$에 대해, $O(n^{2}/\epsilon )$ 시간 내에 각 파트너의 가치가 최대 가치에서 $\epsilon$을 뺀 것 이상인 분할을 반환한다.
• 브램스와 테일러(1995), 로버트슨과 웹(1998), 피쿠르코(2000)가 각각 제안한 세 가지 다른 절차: n명에 대한 무질투 분할을 생성한다. 세 알고리즘 모두 유한하지만 제한되지 않은 수의 자르기가 필요하다.
• 아지즈와 매켄지(2016)의 절차: 제한된 수의 질의로 n명에 대한 무질투 분할을 찾는다.

일반적인 경우의 부정적 결과는 연결된 경우보다 훨씬 약하다. 우리가 알고 있는 것은 무질투 분할을 위한 모든 알고리즘이 최소 Ω(n²)의 질의를 사용해야 한다는 것뿐이다. 이 결과와 알려진 가장 좋은 절차의 실행 시간 복잡도 사이에는 큰 격차가 있다.

더 자세한 내용과 완전한 참고 문헌은 무질투 케이크 자르기를 참조하라.

기타 기준

세 번째로 덜 일반적인 기준은 '공평성'(EQ)이다. 공평한 분할에서 각 사람은 정확히 같은 가치를 누린다. 예시 케이크에서 공평한 분할은 각 사람에게 초콜릿 절반과 바닐라 절반을 주어 각자 5의 가치를 누리게 함으로써 달성될 수 있다. 기호로 표현하면 다음과 같다:

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

네 번째 기준은 '정확성'이다. 각 파트너 i의 권리가 w_i라면, 정확한 분할은 다음과 같은 분할이다.

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

가중치가 모두 동일하다면(1/n), 이 분할을 '완벽'하다고 하며, 다음과 같은 분할이다.

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

기하학적 요건

일부 경우에는 공평함 외에도 파트너들에게 할당된 조각들이 일정한 기하학적 제약을 만족해야 한다.

• 가장 일반적인 제약은 '연결성'이다. "케이크"가 1차원 구간인 경우, 이는 각 조각도 구간이어야 한다는 요구 사항으로 해석된다. 케이크가 1차원 원("파이")인 경우, 이는 각 조각이 호여야 한다는 요구 사항으로 해석된다. 파이 공평하게 자르기를 참조하라.
• 또 다른 제약은 '인접성'이다. 이 제약은 "케이크"가 인접 국가들 사이에서 분할되어야 하는 분쟁 영토인 경우에 적용된다. 이 경우, 각 국가에 할당된 조각이 그 국가의 현재 영토와 인접해야 할 수 있다. 이 제약은 힐의 토지 분할 문제에서 다루어진다.
• 토지 분할에서는 종종 2차원 기하학적 제약이 있다. 예를 들어, 각 조각이 정사각형이거나 (더 일반적으로) 뚱뚱한 객체여야 할 수 있다.

절차적 요건

최종 분할의 바람직한 속성 외에도 분할 과정에 대한 바람직한 속성들이 있다. 이러한 속성 중 하나는 진실성(또는 인센티브 호환성)이며, 이는 두 가지 수준으로 나뉜다.

• '약한 진실성'은 파트너가 알고리즘에 자신의 진정한 가치 측정을 밝히면, 다른 파트너들이 어떻게 하든 상관없이 자신의 공평한 몫(예: 비례적 분할의 경우 전체 케이크 가치의 1/n)을 받는 것이 보장된다는 것을 의미한다. 다른 모든 파트너들이 그를 해치려는 의도로만 연합을 형성하더라도, 그는 여전히 보장된 비율을 받게 될 것이다. 대부분의 케이크 자르기 알고리즘은 이러한 의미에서 진실하다.
• '강한 진실성'은 어떤 파트너도 거짓말을 통해 이득을 얻을 수 없다는 것을 의미한다. 즉, 진실을 말하는 것이 지배적인 전략이다. 대부분의 케이크 자르기 프로토콜은 강하게 진실하지 않지만, 일부 진실한 프로토콜들이 개발되었다. 진실한 케이크 자르기를 참조하라.

또 다른 속성은 대칭성으로, 절차의 다른 역할들 사이에 차이가 없어야 한다. 이 속성의 여러 변형이 연구되었다.

• '익명성'은 당사자들이 순열되고 절차가 다시 실행될 때, 각 당사자가 원래 실행에서와 정확히 동일한 조각을 받는 것을 요구한다. 이는 강한 조건이다. 현재, 익명 절차는 2명의 당사자에 대해서만 알려져 있다.
• '대칭성'은 당사자들이 순열되고 절차가 다시 실행될 때, 각 당사자가 원래 실행에서와 동일한 가치를 받는 것을 요구한다. 이는 익명성보다 약하다. 현재, 대칭적이고 비례적인 절차는 임의의 수의 당사자들에 대해 알려져 있으며, O(n³)의 질의가 필요하다. 대칭적이고 무질투인 절차는 임의의 수의 당사자들에 대해 알려져 있지만, 훨씬 더 오래 걸린다(기존의 무질투 절차를 n!번 실행해야 함).
• '아리스토텔레스성'은 두 당사자가 동일한 가치 측정을 가지고 있다면, 그들이 동일한 가치를 받는 것을 요구한다. 이는 대칭성보다 약하다. 모든 무질투 절차는 이를 만족한다. 더욱이, 아리스토텔레스적이고 비례적인 절차는 임의의 수의 당사자들에 대해 알려져 있으며, O(n³)의 질의가 필요하다.

자세한 내용과 참고 문헌은 대칭으로 공평하게 케이크 자르기를 참조하라.

세 번째 절차적 요건 집합은 단조성이다. 분할 절차가 더 작거나 큰 케이크와 더 작거나 큰 당사자 집합으로 재적용될 때, 모든 당사자의 효용은 같은 방향으로 변해야 한다. 더 자세한 내용은 자원 단조성을 참조하라.

효율성 요건

공평성 외에도 분할의 경제적 효율성을 고려하는 것이 일반적이다. 효율적 케이크 자르기를 참조하라. 효율성에는 여러 수준이 있다.

• 더 약한 개념은 파레토 효율이다. 이는 전체 케이크를 한 사람에게 주는 것만으로도 쉽게 만족될 수 있다. 도전 과제는 공평성과 함께 이를 만족시키는 것이다. 효율적 무질투 분할을 참조하라.
• 더 강한 개념은 공리주의적 최대성 - 효용의 합을 최대화하는 것이다(UM). 가치 함수가 가법적일 때 UM 분할이 존재한다. 직관적으로, UM 분할을 만들기 위해서는 각 케이크 조각을 그것을 가장 높게 평가하는 사람에게 주어야 한다. 예시 케이크에서 UM 분할은 모든 초콜릿을 앨리스에게, 모든 바닐라를 조지에게 주어 9 4 = 13의 공리주의적 가치를 달성할 것이다. 이 과정은 가치 함수가 구간별 상수일 때, 즉 케이크를 모든 사람에 대해 각 조각의 가치 밀도가 상수인 조각들로 나눌 수 있을 때 쉽게 수행할 수 있다. 가치 함수가 구간별 상수가 아닐 때, UM 할당의 존재는 고전적인 측도론적 정리들로부터 따라온다. 공리주의적 케이크 자르기를 참조하라.

효율적 공평 분할

가법적 가치 함수를 가진 n명의 사람들에 대해, 파레토 효율적이고 무질투인(PEEF) 분할은 항상 존재한다. 이는 웰러의 정리이다.

케이크가 1차원 구간이고 각 사람이 연결된 구간을 받아야 하는 경우, 다음과 같은 일반적인 결과가 성립한다: 가치 함수가 엄격히 단조증가(즉, 각 사람이 조각을 그것의 모든 진부분집합보다 엄격히 선호)한다면 모든 무질투(EF) 분할은 또한 파레토 효율적(PE)이다. 따라서 이 경우 시몬스 프로토콜은 PEEF 분할을 생성한다.

케이크가 1차원 '원'(즉, 두 끝점이 위상적으로 동일시되는 구간)이고 각 사람이 연결된 호를 받아야 하는 경우, 이전의 결과는 성립하지 않는다. (EF 분할이 반드시 PE인 것은 아니다) 또한, PEEF 분할이 존재하지 않는 (비가법적) 가치 함수 쌍들이 있다. 그러나 2명의 당사자가 있고 그 중 적어도 한 명이 가법적 가치 함수를 가지고 있다면 PEEF 분할이 존재한다.

케이크가 1차원이지만 각 사람이 그것의 분리된 부분집합을 받을 수 있는 경우, EF 분할이 반드시 PE인 것은 아니다. 이 경우 PEEF 분할을 찾기 위해서는 더 복잡한 알고리즘이 필요하다.

가치 함수가 가법적이고 구간별 상수라면, PEEF 분할을 찾는 알고리즘이 있다. 가치 밀도 함수가 가법적이고 립시츠 연속이라면, 그것들은 "우리가 원하는 만큼 가깝게" 구간별 상수 함수로 근사될 수 있으므로, 그 알고리즘은 PEEF 분할을 "우리가 원하는 만큼 가깝게" 근사한다.

EF 분할이 반드시 UM인 것은 아니다. 이 어려움을 다루는 한 가지 접근 방법은 가능한 모든 EF 분할 중에서 가장 높은 공리주의적 가치를 가진 EF 분할을 찾는 것이다. 이 문제는 케이크가 1차원 구간이고, 각 사람이 분리된 조각들을 받을 수 있으며, 가치 함수가 가법적인 경우에 대해 연구되었다.

컴퓨팅 모델

알고리즘의 실행 시간 복잡도에 대해 추론하려면 컴퓨팅 모델이 필요하다. 문헌에서 몇 가지 일반적인 모델은 다음과 같다.

• 로버트슨-웹 질의 모델: 알고리즘이 각 당사자에게 두 가지 종류의 질문 중 하나를 할 수 있다: "주어진 케이크 조각을 평가하라" 또는 "주어진 가치로 케이크 조각을 표시하라".
• 움직이는 칼 모델: 알고리즘이 일부 당사자들이 "멈춰!"라고 외칠 때까지 케이크 위에서 하나 이상의 칼을 연속적으로 움직인다.
• 직접 공개 모델 - 모든 당사자가 자신의 전체 가치 평가를 메커니즘에 공개한다. 이 모델은 가치 평가가 간결하게 표현될 수 있을 때만 의미가 있다. 예를 들어, 가치 평가가 구간별 균일, 구간별 상수 또는 구간별 선형일 때이다.
• 동시 보고 모델 - 당사자들이 자신의 가치 측정의 이산화를 동시에 보낸다. 이산화는 절단점의 순서와 이 절단점들 사이 조각들의 가치이다(예: 두 당사자를 위한 프로토콜은 각 당사자가 세 개의 절단점 (0,x,1)의 순서를 보고하도록 요구할 수 있으며, 여기서 (0,x)와 (x,1)의 가치는 1/2이다).

여러 케이크 자르기

케이크 자르기 문제의 일반화로, 여러 개의 케이크가 있고 각 당사자가 각 케이크에서 조각을 받아야 하는 경우가 있다.

• 클라우티어, 나이먼, 수는 두 명의 플레이어 간 무질투 다중 케이크 분할을 연구했다. 두 개의 케이크에 대해, 그들은 2명의 당사자가 있고 각 케이크가 2조각으로 잘릴 때 EF 할당이 존재하지 않을 수 있음을 증명했다. 그러나 2명의 당사자가 있고 한 케이크가 3조각으로 잘리거나(가장 덜 원하는 조각은 버림), 3명의 당사자가 있고 각 케이크가 2조각으로 잘릴 때(한 당사자는 무시됨; 나머지 두 명에 대해 할당은 EF임) EF 할당이 존재한다.
• 르베르, 뫼니에, 카르보노는 두 개의 케이크에 대해, 3명의 당사자가 있고 각 케이크가 5조각으로 잘릴 때(각 케이크에서 가장 덜 원하는 두 조각은 버림) EF 할당이 항상 존재함을 증명했다.
• 나이먼, 수, 제르비브는 k개의 케이크에 대해, k(n-1) 1명의 당사자가 있고 각 케이크가 n조각으로 잘릴 때 EF 할당이 항상 존재함을 증명했다(할당은 n명의 당사자 집합에 대해 EF임).

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

• 다층 케이크 자르기: 케이크들이 "층"으로 배열되어 있고 동일한 당사자의 조각들이 겹치지 않아야 한다(예: 각 케이크는 특정 시설이 하루 동안 사용 가능한 시간을 나타낸다; 한 당사자가 두 시설을 동시에 사용할 수 없다).
• 공평한 다중 케이크 자르기: 당사자들이 모든 케이크에서 조각을 받기를 원하지 않고, 반대로 가능한 한 적은 수의 케이크에서 조각을 받기를 원한다.

케이크 공유

베이, 루, 숙솜퐁이 제시한 모델에서는 각 당사자에게 개별적인 케이크 조각을 나누는 대신, 당사자들이 함께 공유할 케이크 조각을 선택해야 한다. 이는 후보들이 분할 가능한 위원회 선거의 변형으로 볼 수 있다. 후보들의 연속체가 실수 구간 [0,c]로 표현되며, 목표는 이 구간의 부분집합을 선택하되 총 길이가 최대 k가 되도록 하는 것이다. 여기서 k와 c는 0<k<c를 만족하는 임의의 실수가 될 수 있다. 그들은 이러한 설정에 대해 정당화된 대표성 개념을 일반화했다. 루, 피터스, 아지즈, 베이, 숙솜퐁은 이러한 정의를 분할 가능한 후보와 분할 불가능한 후보가 혼합된 설정으로 확장했다(정당화된 대표성 참조).

같이 보기

• 공정한 품목 할당 - 분할할 품목이 불가분인 유사한 문제

더 읽어보기

• 공평한 분할에 관한 책 목록

• 공평한 분할에 관한 연구 논문 목록