Процедура Селфриджа-Конвея - Selfridge–Conway procedure

В Процедура Селфриджа-Конвея дискретная процедура, которая производит резка торта без зависти для трех партнеров.[1]:13–14 Он назван в честь Джон Селфридж и Джон Хортон Конвей. Селфридж обнаружил его в 1960 году и рассказал Ричард Гай, который рассказал об этом многим, но Селфридж не опубликовал. Джон Конвей позже обнаружил его независимо, но также никогда не публиковал.[2] Эта процедура была первой свободной от зависти дискретной процедурой, разработанной для трех партнеров, и проложила путь для более продвинутых процедур для п партнеры (см. резка торта без зависти ).

Процедура не вызывает зависти, если каждый получатель считает, что (в соответствии с ее мерой) ни один другой получатель не получил больше, чем он. В их решении максимальное количество разрезов в процедуре - пять. Кусочки не всегда смежны.

Процедура

Подразделение Селфридж-Конвей

Предположим, у нас есть три игрока P1, P2 и P3. Если процедура дает критерий для решения, это означает, что критерий дает игроку оптимальный выбор.

  1. P1 делит торт на три части, которые он считает равными.
  2. Давай позвоним А самый большой кусок согласно P2.
  3. P2 отрезает немного А чтобы он был такого же размера, как второй по величине. Сейчас же А делится на: обрезанный кусок A1 и обрезки A2. Оставьте обрезки A2 в сторону пока.
    • Если P2 считает, что две самые большие части равны (так что обрезка не требуется), затем каждый игрок выбирает часть в следующем порядке: P3, P2 и наконец P1.
  4. P3 выбирает кусок среди A1 и две другие части.
  5. P2 выбирает кусок с ограничением, что если P3 не выбирал A1, P2 должен выбрать это.
  6. P1 выбирает последний кусок, оставляя только обрезки A2 быть разделенным.

Осталось разделить обрезки A2. Обрезанный кусок A1 был выбран либо P2 или же P3; назовем игрока, который его выбрал PA и другой игрок PB.

  1. PB порезы A2 на три равные части.
  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 ≥ B и A1 ≥ C. И он считает свой выбор A21 быть самой большой частью A2. Так что ни один другой игрок не получил больше, чем он: A1 + A21  ≥  B + A23, C + A22.
  • PB получила B + A23. Для него, B ≥ A1 и B ≥ C так как он выбрал B. Кроме того, он тот, кто разрезал A2 в 3 штуки, так что для него все эти части равны.
  • P1 получила C + A22. Для него, C ≥ A1 и C = B.
    • P1 считает, что PB не получил больше, чем получил. Другими словами: C + A22  ≥ B + A23. Помни это P1 выбрал свой кусок A2 перед PB, таким образом A22  ≥ A23 по его мнению.
    • P1 считает, что PA не получил больше, чем получил. Другими словами: C + A22  ≥ A1 + A21. Помните, что для P1, C равно А так как он разрезал торт в первом туре. Также, А = A1 + A2 = A1 + (A21 + A22 + A23); следовательно C  ≥ A1 + A21. (Даже если PA взял весь A2 и P1 не получил A22, P1 не позавидовал бы PA.)

Обобщения

Обратите внимание: если все, что нам нужно, это разделение без зависти на Кроме торта (т.е. мы допускаем бесплатная утилизация ), то нам нужно использовать только первую часть процедуры Селфриджа – Конвея, а именно:

  • P1 делит торт на три равных ему части;
  • P2 отрезает максимум один кусок так, чтобы у него было два одинаковых предмета;
  • P3 берет кусок, затем P2, тогда P1.

Это гарантирует отсутствие зависти, и дополнительно каждый партнер получает ценность не менее 1/4 от общей суммы (так как общее количество фигур равно 4).

Эту процедуру можно обобщить на 4 партнеров следующим образом:[3]

  • P1 делит торт на 5 равные ему штуки;
  • P2 обрезки не более 2 штук, таких, что сейчас 3 равные ему штуки;
  • P3 обрезки не более 1 кусок, такой что есть 2 равные ему штуки;
  • P4 берет кусок, затем P3, тогда P2, тогда P1.

Это гарантирует отсутствие зависти, и дополнительно каждый партнер получает значение не менее 1/8 от общей суммы (так как общее количество фигур равно 8).

По индукции. процедура может быть обобщена на п партнеров, первый делит торт на равные части, а остальные партнеры выполняют обрезку. В результате получается разделение без зависти, и каждый партнер получает значение не менее от общей суммы.

Мы можем применить ту же процедуру еще раз к остальным. Делая это бесконечное количество раз, мы получаем разделение без зависти весь торт.[4] Уточнение этой бесконечной процедуры дает конечную процедуру деления без зависти - Процедура Брамса – Тейлора.

Рекомендации

  1. ^ Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы резки торта: будьте честны, если можете. Натик, Массачусетс: А. К. Петерс. ISBN  978-1-56881-076-8. LCCN  97041258. ПР  2730675W.
  2. ^ Брамс, Стивен Дж .; Тейлор, Алан Д. (1996). Ярмарка Дивизиона [От резки торта до разрешения споров]. С. 116–120. ISBN  0521556449.
  3. ^ Брамс, Стивен Дж .; Тейлор, Алан Д. (1996). Ярмарка Дивизиона [От резки торта до разрешения споров]. С. 131–137. ISBN  0521556449.
  4. ^ Брамс, Стивен Дж .; Тейлор, Алан Д. (1996). Ярмарка Дивизиона [От резки торта до разрешения споров]. п. 137. ISBN  0521556449.