Точный делёж

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

Рассмотрим торт, который наполовину состоит из шоколадной части, а вторая половина ванильная. Алисе нужна только шоколадная часть, а Джорджу только ванильная. Торт делится на три части: один кусок состоит на 20 % из шоколадной части и на 20 % из ванильной, вторая часть состоит на 50 % из шоколадной части и на 50 % из ванильной, а третья часть содержит остаток торта. Этот делёж согласованный, так как и Алиса, и Джордж оценивают три части в 20 %, 50 % и 30 % соответственно.

Как иллюстрирует пример, согласованный делёж не обязательно справедлив. Например, если кусок в 20 % отдать Алисе, а кусок в 50 % Джорджу, это, очевидно, несправедливо для Алисы. В теории разрезания торта согласованные дележи часто используются как подпроцедуры для создания справедливых дележей.

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

Определения

Пусть $w_{1},w_{2},\ldots ,w_{k}$ будут k весами, сумма которых равна 1. Предположим, что все участники оценивают весь торт C в 1.

Точный делёж (или согласованный делёж) в отношениях $w_{1},w_{2},\ldots ,w_{k}$ — это разбиение торта на k кусков: $C=X_{1}\sqcup \cdots \sqcup X_{k}$, так что для любого участника i и любого куска j:

$V_{i}(X_{j})=w_{j}$

То есть имеется согласие среди всех участников, что значение куска j в точности равно $w_{j}$.

Почти точный делёж

Для любого $\varepsilon >0$ $\varepsilon$-почти точный делёж в отношениях $w_{1},w_{2},\ldots ,w_{k}$ — это делёж, в котором

$|V_{i}(X_{j})-w_{j}|<\varepsilon$

То есть имеется согласие среди всех участников, что значение куска j почти точно равно $w_{j}$ и разница меньше $\varepsilon$.

Совершенный делёж

Совершенный делёж — это делёж, в котором ресурс делится среди n участников с субъективными оценками, дающий каждому участнику в точности 1/n ресурса согласно оценкам всех участников. Это специальный случай точного дележа, в котором все веса равны 1/n.

Точный делёж с произвольным числом разрезов

Кусочно-однородный торт, много участников, любые веса

Торт называется кусочно-однородным, если его можно разбить на R областей так, что все участники соглашаются, что значение плотности меры ценности в каждой области однородна. Например, рассмотрим круглый торт, в котором 4 четвертинки имеют различные виды украшений (из крема, глазури, фруктов и шоколада). Участники могут оценить каждый вид украшения различно, но они не делают отличия между различными частями торта с теми же украшениями. Это означает, что значение каждого куска для каждого участника зависит только от количества, которое они получают от каждой области.

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

Когда торт кусочно-однороден (и оценки кусочно-постоянны), согласованный делёж может быть получен следующим образом:

• Разобьём каждую область на k подобластей, таких, что подобласть j содержит в точности $w_{j}$ регионов.
• Пусть кусок j будет объединением j-х подобластей во всех R областях. Это определяет согласованный делёж для заданных весов.

Этот алгоритм может быть обобщён до слегка более общего семейства мер ценности, таких как кусочно-линейные меры.

Количество требуемых разрезов равно $kR$, где R равно количеству областей.

Торт общего вида, много участников, любые веса

Если меры стоимости являются счётно аддитивными и безатомными, согласованное разбиение существует для любого набора весов, сумма которых равна 1. Это следствие теоремы выпуклости Дубинса — Спеньера.

Вудал показал, что можно построить такое разбиение на интервальном торте как счётное объединение интервалов.

Набросок: Рассмотрим процедуру дележа для кусочно-однородных тортов, описанную выше. В общем случае торт не является кусочно-однородным. Однако, поскольку меры цены непрерывны, можно разбить торт на меньшие и меньшие области, такие, что области становятся более и более однородными. При $R\to \infty$ этот процесс сходится к согласованному дележу.

Фремлин показал, что можно построить такой делёж в виде конечного объединения интервалов.

Стромквист и Вудал показали, что это возможно с минимальным количеством интервалов, см. Теорема Стромквиста — Вудала.

Точный делёж с минимальным числом разрезов

Предположим, что торт является интервалом, состоящим из n различных подинтервалов, и каждый из n участников оценивает только одну область. Тогда согласованный делёж торта на k подмножеств требует $n\cdot (k-1)$ разрезов, поскольку каждая из областей должна быть разрезана на k кусков, которые равны в глазах участника, оценивающего эту область. Следовательно, есть интересный вопрос, всегда ли имеется возможность получить согласованный делёж с этим точным числом разрезов.

Интервальный торт, два участника, много подмножеств, любые веса

Два участника могут получить согласованный делёж с помощью процедуры «Движущийся нож» Остина.

Простейшим случаем являются веса 1/2, то есть они хотят разрезать торт так, что оба согласны получать половину значения торта. Это делается следующим образом. Один из участников передвигает два ножа над тортом слева направо, всегда сохраняя значение между ножами в точности равным 1/2. Можно доказать (по теореме о промежуточном значении), что в некоторой точке значение между ножами для другого участника также будет в точности равно 1/2. Другой участник восклицает «стоп!» в этой точке и кусок отрезается.

Тот же протокол может быть использован для отрезания куска, для которого оба игрока согласны, что его ценность в точности равна $1/n$.

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

Более хороший путь получить согласованный делёж заключается в отождествлении двух конечных точек торта, так что его можно считать окружностью. То есть, когда правый нож доходит до правого конца, он немедленно переходит на левый конец и куском между ножами теперь считается объединение куска справа от правого ножа (который был до этого левым ножом) и куска слева от левого ножа (который до этого был правым ножом). Тогда можно найти согласованный делёж для любого $p\in [0,1]$. Один участник двигает ножи циклически по торту, всегда сохраняя значение между ними в точности равным p. Можно доказать, что в некоторой точке значение между ножами для другого участника станет в точности равным p. Другой участник восклицает «стоп!» в этой точке и кусок отрезается. Это требует только двух разрезаний.

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

На 2015 год не было известно никакого обобщения этой процедуры «движущегося ножа» для более чем 2 участников.

Интервальный торт, много участников, два подмножества, равные веса

Предположим, что торт является интервалом с полным значением 1. Его следует разделить на $k=2$ подмножеств, каждое из которых имеет значение в точности 1/2 для всех n участников. Мы хотим использовать минимальное число разрезов, которое равно $n(k-1)=n$.

Делёж, подобный этому, всегда существует. Это прямое следствие теоремы Хобби — Райса. Это можно показать также на основе теоремы Борсука — Улама:

• Любое разбиение интервала с помощью $n$ разрезов может быть представлен как вектор длины $n+1$, в котором элементы являются длинами подинтервалов.
• Любой элемент вектора может быть либо положительным (если принадлежит куску №1) или отрицательным (если он принадлежит куску №2).
• Множество всех разбиений является сферой $S^{n}$.
• Определим $V:S^{n}\to \mathbb {R} ^{n}$ следующим образом: для любого разбиения x $V(x)$ будет вектором, i-й элемент которого является значением куска №1 в этом разбиении согласно оценке участника i минус 1/2.
• Функция V непрерывна. Более того, для всех x $V(x)+V(-x)=0$.
• Следовательно, по теореме Борсука — Улама, существует x, такой, что $V(x)=0$. В этом разбиении все участники оценивают кусок №1 (и кусок №2) в точности в 1/2.

Согласованный делёж на два подмножества можно найти на основе леммы Такера, которая является дискретной версией теоремы Борсука — Улама.

Хотя предпочтения участников моделируются мерами, доказательства не требуют, чтобы меры оценок были аддитивными по подмножествам. Меры оценок могут также быть непрерывными функциями на множествах, определённых на борелевских полных алгебрах и удовлетворяющих всем свойствам мер, за исключением счётной аддитивности. Тогда не требуется, чтобы оценки участников подмножеств торта были аддитивно разделяемы.

Интервальный торт, много участников, много подмножеств, равные веса

Теорема существования из предыдущей секции может быть обобщена с $k=2$ кусков до произвольного числа кусков. Это доказал Нога Алон в своей статье 1987 года о дележе ожерелья.

Есть $n$ различных мер на интервале, все абсолютно непрерывны по отношению к длине. Мера всего ожерелья, согласно мере $i$, равна $k\cdot a_{i}$. Тогда можно разбить интервал на $k$ частей (не обязательно непрерывных), таких, что значение каждой части, согласно мере $i$, равна в точности $a_{i}$. Нужно не более $(k-1)n$ разрезов и это значение оптимально.

Интервальный торт, много участников, два подмножества, произвольные веса

Теорема существования из предыдущей секции обобщается на произвольные веса по теореме Стромквиста — Вудала.

Многомерный торт, много участников, много подмножеств, равные веса

Теорема Стоуна — Тьюки утверждает, что заданные n измеримые «объекты» в n-мерном пространстве, можно разделить все из них пополам (согласно их мерам, то есть объём) единственной (n − 1)-мерной гиперплоскостью.

Другими словами: если торт является пространством $\mathbb {R} ^{n}$, и меры оценок участников конечны и равны нулю на любой $n-1$-мерной гиперплоскости, то существует полупространство, значение которого равно в точности 1/2 для каждого участника. Следовательно, существует согласованный делёж единичным разрезом.

Оригинальная версия этой теоремы работает, только если число торта равно числу участников. Например, невозможно применить эту теорему для дележа 3-мерного сэндвича на четырёх участников.

Однако имеются обобщения, позволяющие такой делёж. Они не используют нож в виде гиперплоскости, а используют более сложные полиномиальные поверхности.

Процедуры почти точного дележа

Процедура «кроши-и-упаковывай»

Для заданного $\varepsilon >0$ можно дать каждому участнику кусок, такой, что все участники верят, что все значения отличаются менее чем на $\varepsilon$, то есть для любого i и любого j:

$|V_{i}(X_{j})-w_{j}|<\varepsilon$

Процедура почти точного дележа имеет два шага: крошение и упаковка.

Шаг крошения: целью является разрезание торта на мелкие кусочки («крошки»), такие, что каждый участник назначает достаточно малое значение каждой крошке. Делается это следующим образом. Пусть k будет некоторой константой. Попросим участника №1 разрезать торт на k кусков так, что цена каждого кусочка равна 1/k. Попросим участника №2 разбить кусочки (с помощью не более k-1 разрезов) так, что каждый кусочек имеет цену не более 1/k. Эти новые кусочки, конечно, по-прежнему имеют значение, не превосходящее 1/k для участника №1. Продолжаем процедуру с партнёрами №3, №4, …, №n. Наконец, цены для всех n участников каждой крошки не превосходят 1/k.

Шаг упаковки: целью здесь заключается в разбиении крошек на n подмножеств так, что сумма значений в каждом подмножестве j была близка к w_j. Ниже приведено нестрогое объяснение шага упаковки для двух участников (Алисы и Джорджа), когда веса равны 1/2.

1. Берём пустую чашку.
2. Помещаем в чашку одну из крошек.
3. Если величина чашки становится больше 1/2 для любого из участников, отдаём чашку этому участнику и остальные крошки отдаём другому участнику.
4. В противном случае (значение в чашке меньше 1/2 для обоих участников), если значение в чашке больше для Алисы, чем для Джорджа, находим крошку, которая для Джорджа более ценна, чем для Алисы (такая крошка должна существовать, поскольку сумма значений крошек равна 1 как для Алисы, так и для Джорджа). Добавим эту крошку в чашку и перейдём к шагу 2 алгоритма.

Можно доказать по индукции, что разница в оценке чашки Алисой и Джорджем всегда не превосходит 1/k. Следовательно, когда один партнёр получает чашку, оба участника оценивают её между 1/2-1/k и 1/2+1/k.

Формально, каждый кусок может быть представлен как вектор значений по одному на участника. Длина каждого вектора ограничена, то есть для каждого такого вектора v: $||v||\leqslant {\sqrt {n}}/k$. Нашей целью является создать для каждого участника j вектор, все элементы которого близки к w_j. Чтобы это осуществить, нам нужно разделить вектора на подмножества, такие, что сумма векторов для каждого подмножества j достаточно близка к вектору, все элементы которого равны w_j. Это возможно по теореме В.Бергстрёма.

Процедура «кроши-и-упаковывай» является подпроцедурой в протоколе Робертсона — Уэбба. Этот протокол образует делёж, который и почти точен, и свободен от зависти.

Другое объяснение процедуры «кроши-и-упаковывай» дали Брамс и Тейлор.

Механизмы честности

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

Наиболее простым механизмом правдивого дележа является: выбираем одного участника случайно (с вероятностью, определяемой весами) и отдаём ему весь торт. Этот механизм тривиально правдив, поскольку он не задаёт никаких вопросов. Однако он является согласованным по ожиданию: ожидаемое значение каждого участника в точности равна весу и это верно для любых мер ценности. Однако получающееся разбиение никак не является согласованным дележом.

Лучше механизм правдивого дележа, который работает для торта, в котором все веса равны 1/n, и он может быть построен из любого существующего алгоритма (или оракула) для поиска согласованного дележа:

1. Просим каждого участника сообщить их меры оценок.
2. Используем существующий алгоритм/оракул для генерации разбиения, в котором все n кусков стоят в точности 1/n согласно функциям, сообщённым участниками.
3. Осуществляем случайную перестановку на согласованном разбиении и даём каждому участнику один из кусков.

Здесь ожидаемое значение каждого участника по-прежнему равно 1/n независимо от сообщённой функции оценок, так что механизм остаётся правдивым – никто из участников не может выиграть от вранья. Более того, правдивый участник гарантирует значение в точности равное 1/n с вероятностью 1 (не только по математическому ожиданию). Следовательно, участники имеют стимул показать истинные функции оценок.

Невозможность

Невозможно достичь точного дележа за конечное число запросов даже для двух участников и весов, в точности равных 1/2. Это означает, что лучшее, чего можно достичь с помощью дискретного алгоритма, это почти точный делёж.

Доказательство: Если протокол находится на шаге k, он имеет коллекцию максимум k кусков. Чтобы осуществить точный делёж, протокол должен найти точное подмножество – подмножество кусков, которые оба партнёра оценивают точно в 1/2. Мы собираемся доказать, что для любого k имеются ситуации, в которых на шаге k не существует точного подмножества, а следовательно, протокол будет продолжаться бесконечно.

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

Предположим теперь, что мы находимся на шаге k и имеется k кусков. Без потери общности мы можем предположить, что каждый кусок имеет ненулевое значение для обоих участников. Это потому, что если Алиса (например) разрежет кусок, который она оценивает в 0, Джордж может также оценивать этот кусок в 0, так что мы можем отбросить этот кусок и продолжать с другими кусками.

Общее количество различных подмножеств теперь равно 2^k и по предположению индукции ни одно из них не является точным разбиением. На шаге k протокол может попросить Алису или Джорджа разрезать некоторый кусок на две части. Предположим, не уменьшая общности, что разрезающим был Джордж и что он режет кусок X на два подкуска: X1 и X2. Теперь общее число подмножеств равно 2^k+1: половина из них уже существует и по предположению не являются точными, так что единственный шанс найти точное подмножество, это приглядеться к новым подмножествам. Каждое новое подмножество сделано из старого подмножества, в котором кусок X заменяется либо X1, либо X2. Поскольку Джордж является разрезающим, он может разрезать способом, который делает один из этих подмножеств точным подмножеством для него (например, если некоторое подмножество, содержащее кусок X, имеет значение 3/4, Джордж может разрезать X так, что X1 имеет значение 1/4, по его мнению, так что новое подмножество имеет значение в точности равное 1/2). Однако Джордж не знает оценок Алисы и не может учитывать их при разрезании. Поэтому существует несчётное количество различных значений, которые могут иметь оценки кусков X1 и X2 для Алисы. Поскольку число новых подмножеств конечно, имеется бесконечное число случаев, в которых никакое новое подмножество имеет значение 1/2 для Алисы, следовательно, никакое новое подмножество не является точным.

Сравнение с другими критериями

Точный делёж с равными весами ($1/n$) является, в частности, также и пропорциональным, свободным от зависти и беспристрастным.

Однако он не обязательно эффективен по Парето, поскольку во многих случаях можно получить улучшение субъективных оценок и разделить ресурсы так, что все участники получат более их справедливой доли в $1/n$.

Точные дележи много проще, если участники кооперируются в определении долей, а не соревнуются как при справедливом дележе. Некоторые авторы называют его согласованным дележом.

Итоговая таблица

Название	Тип	Торт	Оценки	число участников (n)	число подмножеств (k)	число разрезов	веса
Остина	Процедура «Движущийся нож»	Интервал	Con	2	Много	$2(k-1)$ (оптимально)	Любые
Кусочно-однородные	Дискретная процедура	Кусочно-однородный	Con+Add+Pwl	Много	Много	Число областей	Любые
Дубинса — Спеньера	Доказательство существования	Любое	Con+Add	Много	Любое	Неограниченное	Любые
Согласованное деление	Бесконечная процедура	Интервал	Con	Любое	2	n (оптимально)	Равные
Разрезание ожерелья	Доказательство существования	Интервал	Con(+Add?)	Любое	Любое	$n(k-1)$ (оптимально)	Равные
Стромквиста – Вудала	Доказательство существования	Круглый	Con+Add	Любое	2	$2n-2$ (оптимальное для некоторых весов)	Любые
Стоуна – Тьюки	Доказательство существования	n-мерный	Con(+Add?)	n	2	1 полуплоскость	Равные
«кроши-и-упаковывай»	Почти точная процедура	Любое	Con+Add	Любое	Много	Неограниченное	Любые

См. также

• Задача справедливого разрезания торта