셀프리지-콘웨이 절차

Selfridge–Conway procedure

Selfridge-Conway 절차는 세 [1]: 13–14 파트너에게 부러움 없는 케이크 커팅을 제공하는 개별 절차입니다.그것은 존 셀프리지와 존 호튼 콘웨이의 이름을 따서 지어졌다.Selfridge는 1960년에 그것을 발견하고 Richard Guy에게 말했고, Richard Guy는 그것을 많은 사람들에게 말했지만 Selfridge는 그것을 출판하지 않았다.존 콘웨이는 나중에 독립적으로 그것을 발견했고,[2] 출판하지도 않았다.이 절차는 3개 파트너를 위해 개발된 최초의 선망 없는 개별 절차로, n개 파트너를 위한 보다 고급 절차를 위한 기반을 마련했습니다(선망 없는 케이크 커팅 참조).

각 수취인이 (자신의 측정치에 따라) 다른 수취인이 더 큰 몫을 받지 못했다고 믿는다면 절차는 선망의 여지가 없다.시술의 최대 절단 횟수는 5회입니다.그 조각들이 항상 연속적인 것은 아니다.

순서

셀프리지-콘웨이 디비전

P1, P2, P3가 세 명 있다고 가정해 봅시다.절차가 결정의 기준을 제공하는 경우, 그 기준은 참가자에게 최적의 선택을 제공한다는 것을 의미한다.

  1. P1은 같은 크기의 케이크를 세 조각으로 나눈다.
  2. P2에 따르면 A를 가장 큰 조각이라고 하자.
  3. P2는 A의 일부를 잘라내어 두 번째로 큰 크기로 만듭니다.이제 A는 트리밍된 조각 A1과 트리밍 A2로 나뉩니다.트리밍 A2는 일단 옆에 두세요.
    • P2가 가장 큰 2개의 부품이 동일하다고 생각되면(트림을 할 필요가 없는 경우), 각 플레이어는 P3, P2, 마지막으로 P1의 순서로 부품을 선택한다.
  4. P3는 A1과 다른 2개의 피스 중 하나를 선택한다.
  5. P2는 P3가 A1을 선택하지 않은 경우 P2가 선택해야 한다는 제한이 있는 부분을 선택합니다.
  6. P1은 트리밍 A2만을 남기고 마지막 조각을 선택한다.

트리밍 A2를 분할해야 합니다.잘라낸 조각 A1은 P2와 P3 중 하나가 선택했으므로 선택한 플레이어는 PA, 다른 플레이어는 PB라고 합니다.

  1. PB는 A2를 3등분 합니다.
  2. PA는 A2의 일부를 선택합니다.이것을 A21이라고 부릅니다.
  3. P1은 A2의 일부를 선택합니다.이것을 A22라고 부릅니다.
  4. PB는 A2의 마지막 부분을 선택합니다.이것을 A23이라고 부릅니다.

분석.

왜 선망의 대상이 되지 않는지 봅시다.각 선수는 다른 선수가 더 큰 몫을 받지 못했다고 믿는다는 것을 보여줘야 한다.일반성을 잃지 않고 다음을 쓸 수 있습니다(위 그림 참조).

  • PA 수신: A1 + A21.
  • 수신 PB: B + A23.
  • P1 수신: C + A22.

다음 분석에서 "최대"는 "해당 참가자에 따라 최대"를 의미합니다.

  • PA는 A1 + A21을 수신했습니다.이 경우 A1 bB 및 A1 cC 입니다.그리고 그들은 A21을 A2의 가장 큰 부분으로 생각합니다.따라서 A1 + A21 b B + A23, C + A22의 점유율이 더 높은 플레이어는 없었습니다.
  • PB가 B + A23을 수신했습니다.B 를 선택했기 때문에, B a A1 및 B c C 가 됩니다.또한 A2를 3조각으로 자른 것이므로 모두 동등합니다.
  • P1은 C + A22를 수신했습니다.이 경우 C ≤ A1 및 C = B이다.
    • P1은 PB가 더 큰 몫을 받지 못했다고 본다.즉, C + A22 b B + A23 입니다.P1은 PB보다 A2를 먼저 선택했기 때문에 A22 a A23을 선택했다는 점에 유의하십시오.
    • P1은 PA가 더 큰 몫을 받지 못했다고 생각합니다.즉, C + A22 a A1 + A21 입니다.P1의 경우 첫 번째 라운드에서 케이크를 자르기 때문에 C는 A와 같다는 것을 기억하십시오.또한 A = A1 + A2 = A1 + (A21 + A22 + A23)이므로 C ) A1 + A21이다(PA가 A2 전체를 가져가고 P1이 A22를 수신하지 않아도 P1은 PA를 부러워하지 않는다).

일반화

만약 우리가 원하는 것이 케이크의 일부에 대한 선망 없는 분할(무료 폐기 허용)이라면, 우리는 셀프리지-콘웨이 절차의 첫 부분만 사용하면 됩니다.

  • P1은 케이크를 세 조각으로 나눈다.
  • P2는 가장 큰 두 조각이 동일하도록 최대 한 조각을 트리밍한다.
  • P3는 한 조각, P2, P1을 가져갑니다.

이것은 질투가 없다는 것을 보증한다.

이 절차는 다음과 같은 방법으로 [3]4개 파트너로 일반화할 수 있습니다.

  • P1은 케이크를 5조각으로 나눈다.
  • 최대 3개의 조각이 동일하도록 P2 트림은 최대 2개입니다.
  • 최대 2개의 조각이 동일하도록 P3 트림은 최대 1개입니다.
  • P4는 한 조각, P3, P2, P1을 취합니다.

이것은 질투가 없다는 것을 보증한다.

유도에 의해 절차를 n개의 파트너로 일반화할 수 있으며, 첫 번째 파트너에서는 를 + 2}개씩 균등하게 나누고 다른 파트너들은 트리밍을 수행합니다.결과적으로 생기는 분열은 부러움이 없다.

나머지 부분에 대해서도 같은 절차를 다시 적용할 수 있습니다.그렇게 함으로써 케이크 [4]전체를 부러움 없이 분할할 수 있습니다.이 무한 절차의 개선은 유한한 선망 없는 분할 절차를 산출합니다: 브램–테일러 시술.

레퍼런스

  1. ^ Robertson, Jack; Webb, William (1998). Cake-Cutting Algorithms: Be Fair If You Can. Natick, Massachusetts: A. K. Peters. ISBN 978-1-56881-076-8. LCCN 97041258. OL 2730675W.
  2. ^ Brams, Steven J.; Taylor, Alan D. (1996). Fair Division [From cake-cutting to dispute resolution]. pp. 116–120. ISBN 0521556449.
  3. ^ Brams, Steven J.; Taylor, Alan D. (1996). Fair Division [From cake-cutting to dispute resolution]. pp. 131–137. ISBN 0521556449.
  4. ^ Brams, Steven J.; Taylor, Alan D. (1996). Fair Division [From cake-cutting to dispute resolution]. p. 137. ISBN 0521556449.