Точный делёж, называемый также дележом поровну или согласованным дележом, — это делёж неоднородного ресурса (например, торта) на несколько подмножеств, таких, что каждый из людей с различными вкусами соглашается об оценке кусков.
Рассмотрим торт, который наполовину состоит из шоколадной части, а вторая половина ванильная. Алисе нужна только шоколадная часть, а Джорджу только ванильная. Торт делится на три части: один кусок состоит на 20 % из шоколадной части и на 20 % из ванильной, вторая часть состоит на 50 % из шоколадной части и на 50 % из ванильной, а третья часть содержит остаток торта. Этот делёж согласованный, так как и Алиса, и Джордж оценивают три части в 20 %, 50 % и 30 % соответственно.
Как иллюстрирует пример, согласованный делёж не обязательно справедлив. Например, если кусок в 20 % отдать Алисе, а кусок в 50 % Джорджу, это, очевидно, несправедливо для Алисы. В теории разрезания торта согласованные дележи часто используются как подпроцедуры для создания справедливых дележей.
Согласованные дележи всегда существуют, но их нельзя найти дискретными протоколами (с конечным числом запросов). В некоторых случаях точные дележи можно найти протоколами «движущегося ножа». Почти точные дележи можно найти дискретными протоколами.
Определения Пусть будут k весами, сумма которых равна 1. Предположим, что все участники оценивают весь торт C в 1.
Точный делёж (или согласованный делёж) в отношениях — это разбиение торта на k кусков: , так что для любого участника i и любого куска j:
То есть имеется согласие среди всех участников, что значение куска j в точности равно .
Почти точный делёж Для любого -почти точный делёж в отношениях — это делёж, в котором
То есть имеется согласие среди всех участников, что значение куска j почти точно равно и разница меньше .
Совершенный делёж Совершенный делёж — это делёж, в котором ресурс делится среди n участников с субъективными оценками, дающий каждому участнику в точности 1/n ресурса согласно оценкам всех участников. Это специальный случай точного дележа, в котором все веса равны 1/n.
Точный делёж с произвольным числом разрезов Кусочно-однородный торт, много участников, любые веса
Торт называется кусочно-однородным, если его можно разбить на R областей так, что все участники соглашаются, что значение плотности меры ценности в каждой области однородна. Например, рассмотрим круглый торт, в котором 4 четвертинки имеют различные виды украшений (из крема, глазури, фруктов и шоколада). Участники могут оценить каждый вид украшения различно, но они не делают отличия между различными частями торта с теми же украшениями. Это означает, что значение каждого куска для каждого участника зависит только от количества, которое они получают от каждой области.
Утверждение, что торт кусочно-однороден, эквивалентно утверждению, что оценки различных участников дележа кусочно-постоянны — каждый кусок торта однороден тогда и только тогда, когда он является пересечением n кусков n участников.
Когда торт кусочно-однороден (и оценки кусочно-постоянны), согласованный делёж может быть получен следующим образом: Разобьём каждую область на k подобластей, таких, что подобласть j содержит в точности регионов. Пусть кусок j будет объединением j-х подобластей во всех R областях. Это определяет согласованный делёж для заданных весов.
Этот алгоритм может быть обобщён до слегка более общего семейства мер ценности, таких как кусочно-линейные меры.
Количество требуемых разрезов равно , где R равно количеству областей.
Торт общего вида, много участников, любые веса
Если меры стоимости являются и безатомными, согласованное разбиение существует для любого набора весов, сумма которых равна 1. Это следствие теоремы выпуклости Дубинса — Спеньера.
Вудал показал, что можно построить такое разбиение на интервальном торте как счётное объединение интервалов.
Набросок: Рассмотрим процедуру дележа для кусочно-однородных тортов, описанную выше. В общем случае торт не является кусочно-однородным. Однако, поскольку меры цены непрерывны, можно разбить торт на меньшие и меньшие области, такие, что области становятся более и более однородными. При этот процесс сходится к согласованному дележу.
Фремлин показал, что можно построить такой делёж в виде конечного объединения интервалов.
Стромквист и Вудал показали, что это возможно с минимальным количеством интервалов, см. .
Точный делёж с минимальным числом разрезов Предположим, что торт является интервалом, состоящим из n различных подинтервалов, и каждый из n участников оценивает только одну область. Тогда согласованный делёж торта на k подмножеств требует разрезов, поскольку каждая из областей должна быть разрезана на k кусков, которые равны в глазах участника, оценивающего эту область. Следовательно, есть интересный вопрос, всегда ли имеется возможность получить согласованный делёж с этим точным числом разрезов.
Интервальный торт, два участника, много подмножеств, любые веса
Два участника могут получить согласованный делёж с помощью процедуры «Движущийся нож» Остина.
Простейшим случаем являются веса 1/2, то есть они хотят разрезать торт так, что оба согласны получать половину значения торта. Это делается следующим образом. Один из участников передвигает два ножа над тортом слева направо, всегда сохраняя значение между ножами в точности равным 1/2. Можно доказать (по теореме о промежуточном значении), что в некоторой точке значение между ножами для другого участника также будет в точности равно 1/2. Другой участник восклицает «стоп!» в этой точке и кусок отрезается.
Тот же протокол может быть использован для отрезания куска, для которого оба игрока согласны, что его ценность в точности равна .
Путём комбинации нескольких таких кусков можно получить согласованный делёж для любых отношений, являющихся рациональными числами. Однако это может потребовать большого числа разрезов.
Более хороший путь получить согласованный делёж заключается в отождествлении двух конечных точек торта, так что его можно считать окружностью. То есть, когда правый нож доходит до правого конца, он немедленно переходит на левый конец и куском между ножами теперь считается объединение куска справа от правого ножа (который был до этого левым ножом) и куска слева от левого ножа (который до этого был правым ножом). Тогда можно найти согласованный делёж для любого . Один участник двигает ножи циклически по торту, всегда сохраняя значение между ними в точности равным p. Можно доказать, что в некоторой точке значение между ножами для другого участника станет в точности равным p. Другой участник восклицает «стоп!» в этой точке и кусок отрезается. Это требует только двух разрезаний.
Путём повторения вышеприведённой процедуры можно достичь согласованного дележа для двух участников для любого числа подмножеств. Число разрезов равно , где равно числу подмножеств.
На 2015 год не было известно никакого обобщения этой процедуры «движущегося ножа» для более чем 2 участников.
Интервальный торт, много участников, два подмножества, равные веса Предположим, что торт является интервалом с полным значением 1. Его следует разделить на подмножеств, каждое из которых имеет значение в точности 1/2 для всех n участников. Мы хотим использовать минимальное число разрезов, которое равно .
Делёж, подобный этому, всегда существует. Это прямое следствие теоремы Хобби — Райса. Это можно показать также на основе теоремы Борсука — Улама: Любое разбиение интервала с помощью разрезов может быть представлен как вектор длины , в котором элементы являются длинами подинтервалов. Любой элемент вектора может быть либо положительным (если принадлежит куску №1) или отрицательным (если он принадлежит куску №2). Множество всех разбиений является сферой . Определим следующим образом: для любого разбиения будет вектором, -й элемент которого является значением куска №1 в этом разбиении согласно оценке участника минус 1/2. Функция непрерывна. Более того, для всех . Следовательно, по теореме Борсука — Улама, существует , такой, что . В этом разбиении все участники оценивают кусок №1 (и кусок №2) в точности в 1/2.
Согласованный делёж на два подмножества можно найти на основе леммы Такера, которая является дискретной версией теоремы Борсука — Улама.
Хотя предпочтения участников моделируются мерами, доказательства не требуют, чтобы меры оценок были аддитивными по подмножествам. Меры оценок могут также быть непрерывными функциями на множествах, определённых на борелевских полных алгебрах и удовлетворяющих всем свойствам мер, за исключением счётной аддитивности. Тогда не требуется, чтобы оценки участников подмножеств торта были аддитивно разделяемы.
Интервальный торт, много участников, много подмножеств, равные веса Теорема существования из предыдущей секции может быть обобщена с кусков до произвольного числа кусков. Это доказал Нога Алон в своей статье 1987 года о дележе ожерелья.
Есть различных мер на интервале, все абсолютно непрерывны по отношению к длине. Мера всего ожерелья, согласно мере , равна . Тогда можно разбить интервал на частей (не обязательно непрерывных), таких, что значение каждой части, согласно мере , равна в точности . Нужно не более разрезов и это значение оптимально.
Интервальный торт, много участников, два подмножества, произвольные веса Теорема существования из предыдущей секции обобщается на произвольные веса по .
Многомерный торт, много участников, много подмножеств, равные веса Теорема Стоуна — Тьюки утверждает, что заданные измеримые «объекты» в -мерном пространстве, можно разделить все из них пополам (согласно их мерам, то есть объём) единственной -мерной гиперплоскостью.
Другими словами: если торт является пространством , и меры оценок участников конечны и равны нулю на любой -мерной гиперплоскости, то существует полупространство, значение которого равно в точности 1/2 для каждого участника. Следовательно, существует согласованный делёж единичным разрезом.
Оригинальная версия этой теоремы работает, только если число торта равно числу участников. Например, невозможно применить эту теорему для дележа 3-мерного сэндвича на четырёх участников.
Однако имеются обобщения, позволяющие такой делёж. Они не используют нож в виде гиперплоскости, а используют более сложные полиномиальные поверхности.
Процедуры почти точного дележа Процедура «кроши-и-упаковывай»
Для заданного можно дать каждому участнику кусок, такой, что все участники верят, что все значения отличаются менее чем на , то есть для любого i и любого j:
Процедура почти точного дележа имеет два шага: крошение и упаковка.
Шаг крошения: целью является разрезание торта на мелкие кусочки («крошки»), такие, что каждый участник назначает достаточно малое значение каждой крошке. Делается это следующим образом. Пусть k будет некоторой константой. Попросим участника №1 разрезать торт на k кусков так, что цена каждого кусочка равна 1/k. Попросим участника №2 разбить кусочки (с помощью не более k-1 разрезов) так, что каждый кусочек имеет цену не более 1/k. Эти новые кусочки, конечно, по-прежнему имеют значение, не превосходящее 1/k для участника №1. Продолжаем процедуру с партнёрами №3, №4, …, №n. Наконец, цены для всех n участников каждой крошки не превосходят 1/k.
Шаг упаковки: целью здесь заключается в разбиении крошек на n подмножеств так, что сумма значений в каждом подмножестве j была близка к wj. Ниже приведено нестрогое объяснение шага упаковки для двух участников (Алисы и Джорджа), когда веса равны 1/2. Берём пустую чашку. Помещаем в чашку одну из крошек. Если величина чашки становится больше 1/2 для любого из участников, отдаём чашку этому участнику и остальные крошки отдаём другому участнику. В противном случае (значение в чашке меньше 1/2 для обоих участников), если значение в чашке больше для Алисы, чем для Джорджа, находим крошку, которая для Джорджа более ценна, чем для Алисы (такая крошка должна существовать, поскольку сумма значений крошек равна 1 как для Алисы, так и для Джорджа). Добавим эту крошку в чашку и перейдём к шагу 2 алгоритма.