Процедура Селфриджа — Конвея

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Процедура Селфриджа — Конвея — это дискретная процедура, дающая разрезание торта без зависти для трёх участников[1]. Процедура названа именем Джона Селфриджа и Джона Конвея. Селфридж обнаружил процедуру в 1960 году и рассказал о ней Ричарду Гаю, который рассказал о ней многим людям, но Селфридж не опубликовал её. Джон Конвей позднее раскрыл её независимо и тоже никогда её не публиковал[2]. Эта процедура была первой дискретной процедурой деления без зависти для трёх участников и она выстлала путь для более продвинутых процедур для n участников (см. Завистливое разрезание торта).

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

Процедура[править | править код]

Разрезание Селфриджа — Конвея

Пусть у нас имеется три участника, , и . Там, где процедура даёт критерий для решения, этот критерий является оптимальным для игрока.

  1. делит торт на три части, которые он считает одинаковыми.
  2. Пусть будет самым крупным куском по мнению .
  3. отрезает часть от , чтобы сделать его равным со вторым по размеру куском. Теперь разделён на и отрезанный кусок . Откладываем пока в сторону.
    • Если считает, что два самых крупных куска равны (так что никакого урезания не нужно), то каждый игрок выбирает свой кусок в следующем порядке: , и, наконец, .
  4. выбирает кусок среди и двух оставшихся кусков.
  5. выбирает кусок с ограничением, что если не выбирает , должен забрать его.
  6. забирает оставшийся кусок, оставляя кусок для дальнейшего деления.

Остаётся разделить кусок . Кусок был выбран либо игроком , либо игроком . Обозначим забравшего этот кусок игрока как , а второму игроку присвоим имя .

  1. или (но обязательно ) режет на три равные (по его мнению) части.
  2. забирает часть куска , пусть это будет .
  3. (пускай это будет ) забирает часть куска , а именно .
  4. (в нашем случае это ) забирает оставшуюся часть куска , обозначим её как .

Анализ[править | править код]

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

  • получил .
  • получил .
  • получил .

В последующем анализе «самый большой» означает «самый большой согласно оценке игрока»:

  • получил . Для него и . И он считает, что он выбрал как самую большую часть куска . Так что никакой другой игрок не получил больше, чем он: .
  • получил . Для него и , поскольку он выбрал . Также он разрезал часть на 3 куска, так что для него все эти куски одинаковы.
  • получил . Он не может провести сравнение кусков также, как или , т. к. куски и уже были выбраны, а ему достался последний кусок , но:
    • считает, что не получил больше чем он. Другими словами, . Вспомним, что выбрал свою часть перед , так что с его точки зрения.
    • считает, что не получил больше его. Другими словами, . Вспомним, что выбрал свою часть перед , так что с его точки зрения.
    • cчитает, что и не получили больше чем он, т. к. кусок равен , а также равен , поскольку он разрезал торт в самом начале. Тогда, . Даже если или забрал весь кусок , а не получил , не станет завидовать, ведь ).

Обобщения[править | править код]

Заметим, что если всё, что мы хотим, это справедливое разрезание без зависти для части торта (то есть мы разрешаем выбрасывание части торта), то нам достаточно использовать первую часть процедуры, то есть:

  • делит торт на три одинаковые (по его мнению) части;
  • урезает не более одного куска так, чтобы получить по меньшей мере два одинаковых (по его мнению) куска.
  • берёт кусок, затем берёт , затем .

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

  • делит торт на 5 частей, одинаковых по его мнению;
  • урезает не более 2 кусков, так что теперь имеется 3 три одинаковых по его мнению кусков;
  • урезает не более 1 куска, так что теперь имеется 2 куска, одинаковых для него;
  • берёт кусок, затем , затем , затем .

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

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

Примечания[править | править код]

Литература[править | править код]

  • Jack Robertson, William Webb. Cake-Cutting Algorithms: Be Fair If You Can.. — CRC Press, 1998. — ISBN 978-1-56881-076-8.
  • Steven J. Brams, Alan D. Taylor. Fair Division: From cake-cutting to dispute resolution. — Cambridge University Press, 1996. — ISBN 0521556449.