Процедура Селфриджа — Конвея (Hjkey;rjg Vylsjn;'g — Tkufyx)

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

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

Процедура

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

$P1$ делит торт на три части, которые он считает одинаковыми.
Пусть $A$ будет самым крупным куском, по мнению $P2$ .
$P2$ $P2$ отрезает часть от $A$ $A$ , чтобы сделать его равным со вторым по размеру куском. Теперь $A$ $A$ разделён на $A1$ $A1$ и отрезанный кусок $A2$ $A2$ . Откладываем $A2$ $A2$ пока в сторону.
- Если $P2$ считает, что два самых крупных куска равны (так что никакого урезания не нужно), то каждый игрок выбирает свой кусок в следующем порядке: $P3$ , $P2$ и, наконец, $P1$ .
$P3$ выбирает кусок среди $A1$ и двух оставшихся кусков.
$P2$ выбирает кусок с ограничением, если $P3$ не выбирает $A1$ , $P2$ должен забрать его.
$P1$ забирает оставшийся кусок, оставляя кусок $A2$ для дальнейшего деления.

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

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

Анализ

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

$PA$ получил $A1+A21$ .
$PB$ получил $B+A23$ .
$P1$ получил $C+A22$ .

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

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

Обобщения

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

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

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

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

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

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

Примечания

↑ Robertson, Webb, 1998, с. 13-14.
↑ Brams, Taylor, 1996, с. 116-120.
↑ Brams, Taylor, 1996, с. 131-137.
↑ Brams, Taylor, 1996, с. 137.

Литература

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.

[_89042fab79883310-1] Robertson, Webb, 1998, с. 13-14.

[_d5f9ac1c8b3cdb14-2] Brams, Taylor, 1996, с. 116-120.

[_827f60a9550bdae5-3] Brams, Taylor, 1996, с. 131-137.

[_5438382b8b038193-4] Brams, Taylor, 1996, с. 137.

[1]

[2]

[3]

[4]