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

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

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

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

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

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

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

${\displaystyle 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) и для любого ${\displaystyle i}$

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

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

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

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

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

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

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

${\displaystyle 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, эти две последовательности мер идентичны, откуда следует определение аристотелевости.

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

${\displaystyle 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))}$

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

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

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

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

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

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