Симметричное справедливое разрезание торта

Симметричное справедливое разрезание торта — это вариант задачи справедливого разрезания торта, в котором справедливость рассматривается не только в отношении конечных частей торта, но и роли участника в процессе дележа.

Обсуждение

В качестве примера рассмотрим торт на день рождения, который следует разделить между двумя детьми с разными вкусами, так чтобы каждый ребёнок чувствовал, что его/её доля «справедлива», то есть оценивается по меньшей мере в 1/2 от полного торта. Они могут использовать классическую процедуру «дели-и-выбирай» — Алиса режет торт на две части, которые в её глазах оцениваются ровно в 1/2, а Джордж выбирает кусок, который он считает более ценным. Результат всегда справедлив. Однако процедура не симметрична — хотя Алиса получает всегда значение ровно в 1/2 по её оценке, Джордж может получить больше 1/2 по его оценке. Тогда, хотя Алиса не завидует доле Джорджа, она завидует роли Джорджа в процедуре.

Рассмотрим альтернативную процедуру, в которой Алиса и Джордж оба делают метки, соответствующие половинам по их мнению, то есть каждый из них помечает место, в котором торт следует разрезать, так что два куска равны в его/её глазах. Затем торт режется ровно посередине между этим метками — если a, это метка Алисы, а g, это метка Джорджа, то торт режется пополам в $(a+g)/2$. Если a < g, Алиса получает кусок слева, а Джордж забирает кусок справа, в противном случае Алиса получает правый кусок, а Джорджу достаётся левый. Конечный делёж остаётся справедливым, но здесь роли симметричны — единственный случай, когда роли отличаются по результатам дележа, это случай a=g, но в этом случае оба партнёра получают ровно 1/2, так что роли никак не влияют на конечные оценки. Следовательно, альтернативная процедура и справедлива, и симметрична.

Идею первыми предложили Монабе и Окамото, которые назвали её метасвободной от зависти.

Было предложено несколько вариантов симметричного справедливого разрезания торта:

• Анонимное справедливое разрезание торта требует, чтобы не только значения были одинаковыми, но и сами куски были равны. Из этого следует симметричная справедливость, но условие строже. Например, такое разрезание не обеспечивается вышеприведённой симметричной процедурой «дели-и-выбирай», поскольку в случае a=g, первый агент получает всегда самый левый кусок, а второй всегда получает самый правый кусок.
• Аристотелево справедливое разрезание торта требует только, чтобы агенты с идентичными мерами получили куски с тем же самым значением оценки. Из этого следует симметричная справедливость, но условие слабее. Например, оно удовлетворяется асимметричной версией процедуры «дели-и-выбирай» — если оценки агентов идентичны, оба игрока ровно по 1/2.

Определения

Имеется торт C, обычно представляемый как одномерый отрезок. Имеется n человек, и каждый участник дележа i имеет функцию оценки V_i, которая отображает подмножества C в неотрицательные числа.

Процедура дележа — это функция F, которая отображает n функций оценок в разбиение отрезка C. Кусок, который функция F выделяет агенту i, обозначим как $F(V_{1},\dots ,V_{n};i)$.

Симметричная процедура

Процедура дележа F называется симметричной, если при любой перестановке p индексов (1,...,n) и любом i

$V_{i}(F(V_{1},\dots ,V_{n};i))=V_{i}(F(V_{p(1)},\dots ,V_{p(n)};p^{-1}(i)))$

В частности, при n=2 процедура симметрична, если

$V_{1}(F(V_{1},V_{2};1))=V_{1}(F(V_{2},V_{1};2))$ и $V_{2}(F(V_{1},V_{2};2))=V_{2}(F(V_{2},V_{1};1))$.

Это означает, что агент 1 получает то же самое значение независимо от того, играет ли он первым или вторы, и то же самое верно для агента 2.

В другом примере, когда n=3, из требования симметрии следует (среди прочего):

$V_{1}(F(V_{1},V_{2},V_{3};1))=V_{1}(F(V_{2},V_{3},V_{1};3))=V_{1}(F(V_{3},V_{1},V_{2};2))$

Анонимная процедура

Процедура дележа F называется анонимной, если для любой перестановки p индексов (1,...,n) и для любого $i$

$F(V_{1},\dots ,V_{n};i)=F(V_{p(1)},\dots ,V_{p(n)};p^{-1}(i))$

Любая анонимная процедура симметрична, поскольку в случае равенства кусков из оценки заведомо равны.

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

Аристотелева процедура

Процедура дележа F называется аристотелевой, если при $V_{i}=V_{k}$:

$V_{i}(F(V_{1},\dots ,V_{n};i))=V_{k}(F(V_{1},\dots ,V_{n};k))$

Критерий называется по имени Аристотеля, который писал в своей книге по этике: «... когда при одинаковом владении предоставляются неравные доли, или когда лица не равны при равных долях, растёт число споров и жалоб».

Любая симметричная процедура аристотелева. Пусть p будет перестановкой, меняющей местами i и k. Из симметерии следует, что

$V_{i}(F(V_{1},\dots ,V_{i},\dots ,V_{k},\dots ,V_{n};i))=V_{i}(F(V_{1},\dots ,V_{k},\dots ,V_{i},\dots ,V_{n};k))$

Но, поскольку V_i=V_k, эти две последовательности мер идентичны, откуда следует определение аристотелевости.

Более того, любая процедура завистливого разрезания торта аристотелева — из отсутствия зависти следует, что

$V_{i}(F(V_{1},\dots ,V_{n};i))\geqslant V_{i}(F(V_{1},\dots ,V_{n};k))V_{k}(F(V_{1},\dots ,V_{n};k))\geqslant V_{k}(F(V_{1},\dots ,V_{n};i))$

Однако, поскольку $V_{i}=V_{k}$, из двух противоположных неравенств следует, что оба значения равны.

Однако процедура, удовлетворяющая более слабому условию пропорционального разрезания торта не обязательно будет аристотелевой. Чиз привёл пример с 4 агентами, в котором процедура Эвена — Паза для пропорционального разрезания торта может дать различные значения для агентов с идентичными оценочными мерами.

Следующее подытоживает отношения между критериями:

• Анонимный $\to$ Симметричный $\to$ Аристотелев
• Без зависти $\to$ Аристотелев
• Без зависти $\to$ Пропорциональный

Процедуры

Любая процедура может быть сделана «априори симметричной» путём рандомизации. Например, при асимметричной процедуре «дели-и-выбирай» делящий может быть выбран бросанием монеты. Однако, такая процедура не будет симметричной по факту. Поэтому исследования относительно симметричного справедливого разрезания торта фокусируются на детерминированных алгоритмах.

Монабе и Окамото предложили симметричные детерминированные процедуры без зависти («метасвободные от зависти») для двух и трёх агентов.

Николо и Ю предложили протокол анонимного и эффективного по Парето дележа без зависти для двух агентов. Протокол реализует равновесие, совершенное по подыграм, в предположении, что каждый агент обладает полной информацией об оценках других агентов.

Процедура симметричного разрезания и выбора для двух агентов изучали эмпирически в лабораторных экспериментах. Альтернативными процедурами симметричного справедливого разрезания торта для двух участников являются самая правая отметка и самый левый остаток.

Чиз предложил несколько процедур:

• Общая схема преобразования любой процедуры завистливого дележа в симметричную детерминированную процедуру: проводим исходную процедуру n! раз, по разу для каждой перестановки агентов, и выбираем результат согласно топологическому критерию (то есть, по минимуму разрезов). Эта процедура становится практически неприменимой при больших n.
• Аристотелева пропорциональная процедура для n агентов, которая требует $O(n^{3})$ запросов и полиномиальное число арифметических операций.
• Симметричная пропорциональная процедура для n агентов, которая требует $O(n^{3})$ запросов, но может требовать экспоненциальное число арифметических операций.

Аристотелева пропорциональная процедура

Аристотелева процедура Чиза для пропорционального разрезания торта расширяет процедуру «одиночный делящий». Для удобства нормализуем функции оценок, чтобы значение всего торта для всех агентов было равно n. Целью является выделение каждому агенту доли, которая не меньше 1.

1. Выбирается один игрок произвольным образом, который называется делящим, он режет торт на n частей, которые он/она оценивает ровно в 1.
2. Строится двудольный граф $G=(X+Y,E)$, в котором каждая вершина X является агентом, каждая вершина Y является куском торта и имеется ребро между агентом x и куском торта y тогда и только тогда, когда x оценивает кусок y по меньшей мере в 1.
3. Ищем максимальное по размеру паросочетание без зависти (ПБЗ) в G (паросочетание, в котором нет агента, не принадлежащего паросочетанию, но смежного принадлежащено паросоченанию куску торта). Заметим, что делящий смежен всем n кускам торта, так что $|N_{G}(X)|=n\geqslant |X|$ (где $N_{G}(X)$ является множеством соседей X в Y). Следовательно, непустое паросочетание без зависти существует. Предположим без потери общности, что ПБЗ сопоставляет агентов 1,...,k кускам $X_{1},\dots ,X_{k}$, оставляя без соответствия агентов и куски от k+1 др n.
4. Для любого i из 1,...,k, для которого $V_{i}(X_{i})=1$, отдаём X_i агенту i. Теперь делящему и всем агентам, чьи функции оценок идентичны функции делящего, назначены куски, имеющие одинаковые значения.
5. Рассмотрим теперь агентов i из 1,...,k, для которых $V_{i}(X_{i})>1$. Разобьём их на подмножества с равными векторами оценок кусков $X_{1},\dots ,X_{n}$. Для каждого подмножества рекурсивно делим их куски среди них (например, если агенты 1, 3, 4 согласны со значениями всех кусков 1,...,k, то делим куски $X_{1},X_{3},X_{4}$ рекурсивно среди них). Теперь все агенты, функции оценок которых идентичны, назначены тем же самым подмножествам и они делят подторт, значение которого среди них больше, чем их число, так что предусловие для рекурсии выполнено.
6. Рекурсивно делим нераспределённые куски $X_{k+1},\dots ,X_{k}$ среди нераспределённых агентов. Заметим, что согласно отсутствия зависти в паросочетании каждый не распределённый агент оценивает каждый распределённый кусок меньше чем в 1, так что значения оставшихся кусков не меньше числа агентов, так что предусловие для рекурсии сохраняется.