Раздел наследства, расторжение брака с разделом имущества или распределение комнат и арендной платы между соседями неизменно сталкивают человека с понятием справедливости.
Древнейший житейский алгоритм для двух участников гласит: «Один делит, другой выбирает (Cut and Choose)». Делящий стремится разрезать пирог ровно пополам, чтобы защитить себя от потерь, а выбирающий забирает наиболее желанный кусок.
Но как быть, если участников трое или больше? А если пирог неоднороден — с одной стороны шоколад, с другой клубника — и вкусы участников кардинально различаются? Простое геометрическое деление на равные части вызовет протест того, кто терпеть не может клубнику.
Существует ли математический алгоритм, гарантирующий, что каждый участник получит долю, которую считает справедливой, и при этом никто не будет завидовать доле соседа?
Это центральный вопрос теории справедливого дележа (Fair Division), или задачи о дележе пирога (Cake-Cutting Problem). Сформулированная в 1940-х годах Гуго Штейнгаузом, эта задача объединяет теорию меры, топологию (лемму Шпернера и теоремы о неподвижной точке), теорию игр и вычислительную сложность. В 2016 году Харис Азиз и Саймон Маккензи совершили научный прорыв, представив первый конечный ограниченный алгоритм дележа без зависти для произвольного числа участников.
1. Теоретико-вероятностная модель Штейнгауза
Пирог моделируется единичным отрезком $X = [0, 1]$. Каждый участник $i \in \{1, \dots, n\}$ обладает субъективной неотрицательной безатомной мерой ценности $V_i: \mathcal{B}(X) \to [0, 1]$, где $V_i(X) = 1$. Это означает, что вкусы у всех участников индивидуальны и непрерывны.
2. Четыре критерия справедливости
| Критерий | Формальное определение | Смысл |
|---|---|---|
| Пропорциональность (PROP) | $\forall i, \quad V_i(X_i) \ge \frac{1}{n}$ | Каждый получает не менее $1/n$ общей ценности в своих глазах |
| Отсутствие зависти (EF) | $\forall i, j, \quad V_i(X_i) \ge V_i(X_j)$ | Никто не считает чужую долю лучше собственной |
| Эквивалентность (EQ) | $\forall i, j, \quad V_i(X_i) = V_j(X_j)$ | Числовое субъективное удовлетворение у всех одинаково |
| Парето-эффективность (PE) | Невозможно улучшить положение одного, не ухудшив положение другого | Полное использование ресурсов без потерь |
При $n \ge 3$ пропорциональность не спасает от зависти: если Алиса получила $35\%$ ($> 33.3\%$), но Боб получил кусок, который Алиса оценивает в $50\%$, возникнет острая зависть. Поэтому золотым стандартом является отсутствие зависти (Envy-Freeness).
3. Протокол Селфриджа — Конвея для 3 участников (1960)
- Этап 1 (Основной пирог и подравнивание):
- Игрок 1 делит пирог на 3 равных по своей оценке куска ($A, B, C$).
- Игрок 2 подравнивает наибольший кусок ($A$), срезая излишек $T$, чтобы уравнять его со вторым по величине ($A'$).
- Выбор долей: Игрок 3 выбирает первым, затем Игрок 2 (обязан взять $A'$, если его не взял Игрок 3), затем Игрок 1.
- Игрок 1 получает нетронутый кусок ценностью $1/3$, поэтому на этом этапе зависти нет!
- Этап 2 (Раздел обрезков $T$):
- Получивший $A'$ обозначается как $T_{\text{in}}$, второй из пары $\{P_2, P_3\}$ — как $T_{\text{out}}$.
- $T_{\text{out}}$ делит обрезки $T$ на 3 равные части.
- Очередность выбора: $T_{\text{in}} \to P_1 \to T_{\text{out}}$.
- Игрок 1 никогда не завидует $T_{\text{in}}$, так как даже целиком кусок $A' \cup T$ в глазах Игрока 1 не превышает $1/3$.
4. Топология аренды: Лемма Шпернера
Фрэнсис Су в 1999 году доказал, что распределение комнат и арендной платы между соседями всегда может быть осуществлено без зависти с помощью комбинаторной леммы Шпернера (Rental Harmony).
5. Заключение
Справедливость — это не слепое уравнивание, а уважение к индивидуальным ценностям через грамотно спроектированные правила игры.