마지막 감쇠기

마지막 체감자 절차는 공정한 케이크 커팅을 위한 절차다.생일 케이크와 같이 특정한 이질적이고 분리할 수 없는 자원과 케이크의 다른 부분보다 다른 선호를 가진 n개의 파트너를 포함한다.그것은 n명이 비례분할, 즉 각자가 자신의 주관적 가치평가에 따라 총액의 1/n 이상의 가치를 지닌 작품을 받을 수 있도록 케이크를 나누도록 한다.예를 들어, 앨리스가 케이크 전체를 100달러로 소중히 여기고 5명의 파트너가 있다면 앨리스는 다른 파트너가 어떻게 생각하든, 무엇을 하든 상관없이 적어도 20달러는 소중히 여기는 작품을 받을 수 있다.

역사

제2차 세계 대전 당시 나치를 피해 숨어 있던 폴란드-유대인 수학자 휴고 스타인하우스가 자원을 공정하게 나눌 수 있는 방법에 대한 문제로 몸을 사렸다.분열과 두 형제의 케이크 나누기에 대한 선택 절차에 영감을 받아, 그는 그의 제자인 스테판 바나흐와 브론스와프 크나스터에게 어떤 수의 사람들에게도 효과가 있는 절차를 찾아달라고 부탁하고, 그들의 해결책을 발표했다.^[1]

이 출판물은 현재 여러 분야의 많은 연구자들에 의해 연구되고 있는 새로운 연구 주제를 시작했다. 공정한 분열을 보라.

설명

다음과 같은 저자의 말로 분할 프로토콜에 대한 설명이다.

"A, B, C,...N, A는 케이크에서 임의의 부분을 잘라낸다.B는 이제 절단을 줄일 권리가 있지만 의무가 없다.그가 무엇을 하든지 간에 C는 이미 줄어든(또는 줄지 않은) 슬라이스를 감량할 권리가 있으며, N까지 감량할 권리가 있다.이 규칙은 "마지막 감점자"에게 그가 마지막으로 만진 부분을 의무적으로 자신의 몫으로 삼도록 한다.따라서 이 파트너는 처분되고, 나머지 n-1명은 나머지 케이크와 같은 게임을 시작한다.참가자가 2명으로 줄어든 뒤 나머지 절반은 고전적 규칙을 적용한다고 말했다.

각 파트너는 최소 1/n의 값으로 슬라이스를 받는 것을 보장하는 방법을 가지고 있다.방법은: 항상 현재 슬라이스를 잘라 나머지 슬라이스가 1/n 값을 갖도록 하는 것이다.두 가지 옵션이 있다: 당신이 잘라낸 슬라이스를 받거나 다른 사람이 당신을 위한 값이 1/n 미만인 더 작은 슬라이스를 받는다.후자의 경우, n-1의 파트너가 남아 있고, 나머지 케이크의 가치는 (n-1)/n보다 높다.따라서 유도를 통해 수신된 값이 최소 1/n임을 증명할 수 있다.

공통 선호함수의 변질된 사례

알고리즘은 슬라이스를 최적으로 먼저 자르는 파트너도 마지막 감쇠기가 되기 때문에 모든 파트너가 동일한 선호 기능을 갖는 퇴보적인 경우 단순화한다.동등하게,^{[citation needed]} 각각의 파트너 1, 2, ..., n-1은 차례로 남은 케이크에서 슬라이스를 자른다.그런 다음 역순으로 각 파트너 n, n-1, ..., 1 차례로 아직 클레임되지 않은 슬라이스를 선택한다.가치 1/n이 아닌 다른 슬라이스를 자른 첫 번째 파트너는 그들보다 더 많은 것으로 끝난 다른 파트너를 부러워할 것이다.

분석

마지막 제거자 프로토콜은 분리되어 있으며 교대로 재생할 수 있다.최악의 경우, $n$ $\times (n-1) / 2$ = $O (n 2)$ 동작이 필요하다: 턴당 한 동작씩.

그러나 이러한 O(n²) 작용의 대부분은 실제 절단(즉, 실제 절단)이 아니다.앨리스는 원하는 슬라이스를 종이에 표시하고 다른 플레이어로 하여금 같은 종이에 그것들을 줄이도록 할 수 있다.; 오직 "마지막 감소자"만이 실제로 케이크를 자르면 된다.그래서 n-1 절단만 하면 된다.

삭감에 관해서는 절차가 매우 자유롭다.파트너에 의해 만들어진 절단부들은 어떤 모양도 가질 수 있다; 그것들은 심지어 분리될 수도 있다.한편, 조각들이 좋은 모양을 하고 있다는 것을 보증하기 위해 절단을 제한할 수도 있다.특히:

만약 원래의 케이크가 연결되어 있다면, 각각의 조각이 연결되어 있다고 보증하는 것이 가능하다(연속적이다).
만약 원래의 케이크가 볼록 세트라면, 각각의 조각이 볼록하다는 보장이 가능하다.
만약 원래의 케이크가 직사각형이라면, 각각의 조각이 직사각형임을 보증하는 것이 가능하다.
만약 원래의 케이크가 삼각형이라면, 각각의 조각이 삼각형임을 보증하는 것이 가능하다.

연속 버전

이 프로토콜의 연속 시간 버전은 Dubins-Spanier Moving-knife 절차를 사용하여 실행할 수 있다.^[2]공정한 분업에서 연속적인 시술의 첫 사례였다.칼이 케이크를 왼쪽 끝에서 오른쪽으로 넘긴다.어떤 플레이어가 케이크 1 $[\displaystyle$ 1 $/n}$ 이 $1/n$ 칼의 왼쪽에 있다고 생각하면, 케이크를 자르고 말을 한 플레이어가 그 조각을 얻을 때 멈추라고 말할 수 있다.남은 케이크와 플레이어로 반복하면 마지막 플레이어가 남은 케이크를 얻는다.마지막 감산기 절차와 유사하게, 각 플레이어의 케이크를 인접한 부분으로 자르는 데 사용할 수 있다.

근사치-인비-프리 버전

협력사가 3명 이상일 때, 마지막 제거자 프로토콜로 얻은 분할이 항상 부러움이 없는 것은 아니다.예를 들어, 첫 번째 파트너 앨리스가 (총액의 1/3로 소중하게 여기는) 작품을 받는다고 가정합시다.그러면 나머지 두 파트너인 밥과 찰리는 공평한 방법으로 나머지를 나누지만 앨리스의 의견으로는 밥의 몫이 2/3인 반면 찰리의 몫은 0인 것이다.그때 앨리스는 밥을 부러워한다.

간단한 해결책은^[3] 재입국을 허용하는 것이다.즉, 마지막 감점자가 되어 한 점을 이긴 파트너는 경기를 떠날 필요가 없고, 오히려 남아서 더 많은 스텝에 참여할 수도 있다.만약 그가 다시 우승한다면, 그는 현재 자신의 작품을 발매해야 하고 그것은 다시 우승컵으로 돌아온다.프로토콜이 종료되도록 하기 위해 특정 상수 $\epsilon$ $\epsilon$ 을(를) 선택하고 $\epsilon$ 각 파트너가 최대 $1/\epsilon$ / $1/\epsilon$ $1/\epsilon$ 번 $1/\epsilon$ 재입력할 수 있는 규칙을 추가한다.

reentrant 버전에서, 각 파트너는 최소한 값이 가장 큰 $[\displaystyle \epsilon }}$ 의 슬라이스를 수신할 수 있도록 보장하는 방법을 가지고 $\epsilon$ 있다. 방법은: 항상 현재 슬라이스를 잘라 나머지 값이 $\epsilon$ [\ $displaystyle \epsilon }$ 에 현재 값을 더하는 $\epsilon$ 것이다.이것은 당신이 이길 때마다 $\epsilon$ 당신의 가치가 $\epsilon$ $\epsilon$ 만큼 증가한다는 것을 보장하며, 만약 당신이 이기지 못한다면 - 우승자의 가치는 당신의 가치보다 최대 $\epsilon$ $\epsilon$ 더 많다 $\epsilon$ .따라서 질투의 수준은 최대 $\epsilon$ ${\displaystyle \epsilon }($ 첨가 상수)이다.

실행 시간은 최대 $n/\epsilon$ / $n/\epsilon$ $n^{2}/\epsilon$ 단계에 $n/\epsilon$ 있으며, 각 단계에서 각 $n$ {\ $displaystyle$ n $/\epsilon$ } 파트너에게 질의하기 때문에 최대 $n^{2}/\epsilon$ / $\$ {\ $displaystyle n}$ 개 입니다 $n$ $n^{2}/\epsilon$

근사치 없는 변종의 단점은 조각들이 끊임없이 케이크에 되돌려지고 다시 나누어지기 때문에 조각들이 반드시 연결되지 않는다는 것이다.이 문제에 대한 다른 해결책은 질투 없는 케이크 커팅#연결된 조각을 참조하십시오.

개선사항

마지막 감쇠기 시술은 나중에 여러 가지 면에서 개선되었다.자세한 내용은 비례분할을 참조하십시오.

참조

^ Steinhaus, Hugo (1948). "The problem of fair division". Econometrica. 16 (1): 101–4. JSTOR 1914289.
^ Dubins, Lester Eli; Spanier, Edwin Henry (1961). "How to Cut a Cake Fairly". The American Mathematical Monthly. 68: 1. doi:10.2307/2311357. JSTOR 2311357.
^ Brams, Steven J.; Taylor, Alan D. (1996). Fair division: from cake-cutting to dispute resolution. Cambridge University Press. pp. 130–131. ISBN 0-521-55644-9.

[steinhaus48-1] Steinhaus, Hugo (1948). "The problem of fair division". Econometrica. 16 (1): 101–4. JSTOR 1914289.

[ds61-2] Dubins, Lester Eli; Spanier, Edwin Henry (1961). "How to Cut a Cake Fairly". The American Mathematical Monthly. 68: 1. doi:10.2307/2311357. JSTOR 2311357.

[bramstaylor130-3] Brams, Steven J.; Taylor, Alan D. (1996). Fair division: from cake-cutting to dispute resolution. Cambridge University Press. pp. 130–131. ISBN 0-521-55644-9.

[1]

[2]

[3]

Search

마지막 감쇠기

네임스페이스

더

목차

역사

설명

공통 선호함수의 변질된 사례

분석

연속 버전

근사치-인비-프리 버전

개선사항

참조