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

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

Процедура

Пусть у нас имеется три участника, ${\displaystyle P1}$ , ${\displaystyle P2}$ и ${\displaystyle P3}$ . Там, где процедура даёт критерий для решения, этот критерий является оптимальным для игрока.

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

Остаётся разделить кусок ${\displaystyle A2}$ . Кусок ${\displaystyle A1}$ был выбран либо игроком ${\displaystyle P2}$ , либо игроком ${\displaystyle P3}$ . Обозначим забравшего этот кусок игрока как ${\displaystyle PA}$ , а второму игроку присвоим имя ${\displaystyle PB}$ .

1. ${\displaystyle PA}$ или ${\displaystyle PB}$ (но обязательно ${\displaystyle P3}$ ) режет ${\displaystyle A2}$ на три равные (по его мнению) части.
2. ${\displaystyle P1}$ забирает часть куска ${\displaystyle A2}$ , пусть это будет ${\displaystyle A22}$ .
3. ${\displaystyle P2}$ (пускай это будет ${\displaystyle PA}$ ) забирает часть куска ${\displaystyle A2}$ , а именно ${\displaystyle A21}$ .
4. ${\displaystyle P3}$ (в нашем случае это ${\displaystyle PB}$ ) забирает оставшуюся часть куска ${\displaystyle A2}$ , обозначим её как ${\displaystyle A23}$ .

Анализ

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

• ${\displaystyle PA}$ получил ${\displaystyle A1+A21}$ .
• ${\displaystyle PB}$ получил ${\displaystyle B+A23}$ .
• ${\displaystyle P1}$ получил ${\displaystyle C+A22}$ .

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

• ${\displaystyle PA}$ получил ${\displaystyle A1+A21}$ . Для него ${\displaystyle A1\geqslant B}$ и ${\displaystyle A1\geqslant C}$ . И он считает, что он выбрал ${\displaystyle A21}$ как самую большую часть куска ${\displaystyle A2}$ . Так что никакой другой игрок не получил больше, чем он: ${\displaystyle A1+A21\geqslant B+A23,C+A22}$ .
• ${\displaystyle PB}$ получил ${\displaystyle B+A23}$ . Для него ${\displaystyle B\geqslant A1}$ и ${\displaystyle B\geqslant C}$ , поскольку он выбрал ${\displaystyle B}$ . Также он разрезал часть ${\displaystyle A2}$ на 3 куска, так что для него все эти куски одинаковы.
• ${\displaystyle P1}$ получил ${\displaystyle C+A22}$ . Он не может провести сравнение кусков также, как ${\displaystyle PA}$ или ${\displaystyle PB}$ , т. к. куски ${\displaystyle A}$ и ${\displaystyle B}$ уже были выбраны, а ему достался последний кусок ${\displaystyle C}$ , но:
  • ${\displaystyle P1}$ считает, что ${\displaystyle PB}$ не получил больше, чем он. Другими словами, ${\displaystyle C+A22\geqslant B+A23}$ . Вспомним, что ${\displaystyle P1}$ выбрал свою часть ${\displaystyle A2}$ перед ${\displaystyle PB}$ , так что ${\displaystyle A22\geqslant A23}$ с его точки зрения.
  • ${\displaystyle P1}$ считает, что ${\displaystyle PA}$ не получил больше его. Другими словами, ${\displaystyle C+A22\geqslant A1+A21}$ . Вспомним, что ${\displaystyle P1}$ выбрал свою часть ${\displaystyle A2}$ перед ${\displaystyle PA}$ , так что ${\displaystyle A22\geqslant A21}$ с его точки зрения.
  • ${\displaystyle P1}$ считает, что ${\displaystyle PA}$ и ${\displaystyle PB}$ не получили больше, чем он, т. к. кусок ${\displaystyle C}$ равен ${\displaystyle A}$ , а также равен ${\displaystyle B}$ , поскольку он разрезал торт в самом начале. Тогда, ${\displaystyle A=A1+A2=A1+(A21+A22+A23)=B=C}$ . Даже если ${\displaystyle PA}$ или ${\displaystyle PB}$ забрал весь кусок ${\displaystyle A2}$ , а ${\displaystyle P1}$ не получил ${\displaystyle A22}$ , ${\displaystyle P1}$ не станет завидовать, ведь ${\displaystyle A=B=C}$ ).

Обобщения

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

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

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

• ${\displaystyle P1}$ делит торт на 5 частей, одинаковых, по его мнению;
• ${\displaystyle P2}$ урезает не более 2 кусков, так что теперь имеется 3 три одинаковых, по его мнению кусков;
• ${\displaystyle P3}$ урезает не более 1 куска, так что теперь имеется 2 куска, одинаковых для него;
• ${\displaystyle P4}$ берёт кусок, затем ${\displaystyle P3}$ , затем ${\displaystyle P2}$ , затем ${\displaystyle P1}$ .

По индукции процедура может быть обобщена для n участников, первый из которых делит торт на части, каждая из которых равна ${\displaystyle 2^{n-2}+1}$ торта, а остальные участники следуют процедуре урезания. Получающееся разрезание свободно от зависти, а каждый партнёр получает значение по меньшей мере равное ${\displaystyle 1/2^{n-1}}$ от всего торта.

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

Примечания

Литература