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

Процедура Селфриджа — Конвея — это дискретная процедура, дающая разрезание торта без зависти для трёх участников^[1]. Процедура названа именем Джона Селфриджа и Джона Конвея. Селфридж обнаружил процедуру в 1960 году и сообщил о ней Ричарду Гаю, который рассказал о ней многим людям, но сам Селфридж не опубликовал свое открытие официально. Джон Конвей позднее открыл процедуру независимо и также не публиковал^[2]. Это было первой дискретной процедурой деления торта без зависти для трёх участников и открыла путь для более продвинутых процедур для 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 участников следующим образом^[3]:

• ${\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}}$ от всего торта.

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