Теорема Веллера

Справедливое разрезание торта изучалось с 1940 годов. Имеется разнородный делимый ресурс, такой как торт или участок земли. Есть n участников, каждый из которых имеет личную функцию плотности ценности частей торта. Значение куска для участника — это интеграл плотности значения по куску торта (это означает, что оценка участника является безатомной мерой на торте). Задача о разрезании торта без зависти (англ. envy-free cake-cutting) заключается в таком дележе торта на n непересекающихся кусков, по одному куску на участника, что для каждого участника значение получаемого им куска не меньше, чем значения всех других кусков (так, что никакой участник не завидует доле другого участника).

Следствием теоремы о выпуклости Дубинса — Спеньера (1961) является то, что всегда имеется «согласованное разбиение» — разбиение торта на n кусков, таких, что значение для любого участника любого куска в точности составляет ${\displaystyle 1/n}$. Согласованное разбиение, конечно, является EF, но оно не PE. Более того, другим следствием вышеупомянутой теоремы является то, что, когда по меньшей мере два участника имеют различные меры ценности, существует делёж, который даёт каждому участнику строго больше ${\displaystyle 1/n}$. Это означает, что согласованное разбиение даже не слабее PE.

Отсутствие зависти, как критерий справедливого распределения, было предложено в экономике в 1960-х годах и изучалось интенсивно в течение 1970-х годов. Теорема Вариана изучает отсутствие зависти в контексте дележа однородных благ. При небольших ограничениях на функции полезности агентов существуют распределения, одновременно являющиеся PE и EF. Доказательством является результат существования конкурентного равновесия равных доходов (англ. competitive equilibrium from equal incomes, CEEI). Дэвид Гейл доказал аналогичное существование для агентов с линейной полезностью.

Задача о разрезании торта является более трудной, чем распределение однородных благ. Отчасти торт имеет большое разнообразие благ — каждая точка торта имеет отличное значение. Это предмет теоремы Веллера.

Торт обозначим буквой ${\displaystyle C}$. Число участников дележа обозначим буквой ${\displaystyle n}$.

Разбиение торта, обозначаемое буквой ${\displaystyle X}$, является n-кортежем ${\displaystyle X_{1},\dots ,X_{n}}$ подмножеств торта ${\displaystyle C}$. Здесь ${\displaystyle X_{i}}$ является куском торта, который отдаётся участнику ${\displaystyle i}$.

Разбиение называется PEEF, если удовлетворяет следующим двум условиям:

• Эффективность по Парето: никакой другой делёж не хуже для всех участников и строго лучше для одного из них.
• Отсутствие зависти: никакой участник не желает получить кусок, отданный другому участнику.

Разбиение ${\displaystyle X}$ и мера цены ${\displaystyle P}$ на ${\displaystyle C}$ называются CEEI, если они удовлетворяют следующим двум условиям:

• Конкурентное равновесие: Для любого агента i любой ломоть с положительной оценкой ${\displaystyle Z_{i}\subseteq X_{i}}$ и любого ломтя с положительной оценкой ${\displaystyle Z\subseteq C}$: ${\displaystyle v_{i}(Z_{i})/P(Z_{i})\geqslant v_{i}(Z)/P(Z)}$.
• Равные доходы: Для любого агента i: ${\displaystyle P(X_{i})=1}$.

CEEI много строже PEEF: любое CEEI-распределение является PEEF, но имеется много PEEF-распределений, не являющихся CEEI.

Теорема Веллера доказывает существование CEEI-распределения, откуда следует существование PEEF-распределения.

Представление ниже основано на статье Веллера и частично на статье Барбанеля[2].

Доказательство Веллера опирается на взвешенное максимальное по полезности разрезание торта (англ. weighted-utilitarian-maximal, WUM). WUM является дележом, максимизирующим функцию следующего вида:

${\displaystyle \sum _{i=1}^{n}{V_{i}(X_{i}) \over w_{i}}}$,

где ${\displaystyle i}$ является индексом агента, ${\displaystyle V_{i}}$ является значением меры агента, ${\displaystyle X_{i}}$ является куском торта, передаваемого агенту, а ${\displaystyle w_{i}}$ является положительным весом.

Следствие теоремы компактности Дубинса — Спеньера гласит, что для любого вектора весов ${\displaystyle w}$, WUM-распределения существуют. Интуитивно, каждый кусочек торта ${\displaystyle Z}$ должен быть отдан лицу ${\displaystyle i}$, для которого ${\displaystyle {V_{i}(Z) \over w_{i}}}$ наибольший. Если существует два и более человека, для которых это значение то же самое, то любой произвольный делёж куска между ними приводит к WUM-дележу (WUM распределения можно также определить с помощью множества Радона — Никодима. Каждый вектор весов ${\displaystyle w}$, как точка в ${\displaystyle (n-1)}$-мерном единичном симплексе, определяет разбиение этого симплекса. Это разбиение порождает распределением множества Радона — Никодима для торта, которое порождает одно или более распределений торта).

Любой WUM делёж очевидно PE. Однако WUM-делёж может быть очень несправедливым. Например, если ${\displaystyle w_{i}}$ очень велико, то агент ${\displaystyle i}$ может дать только малую долю торта (вектор весов ${\displaystyle w}$ очень близок к вершине агента ${\displaystyle i}$ единичного симплекса, это означает, что ${\displaystyle i}$ получит только точки множества Радона — Никодима, которые очень близки к его вершине). Для сравнения, если ${\displaystyle w_{i}}$ очень мало, то агент ${\displaystyle i}$ может получить весь торт.

Веллер доказал, что существует вектор весов, для которого WUM делёж является также EF. Сделал он путём определения нескольких функций:

1. Функция ${\displaystyle Par}$: для любого вектора положительных весов ${\displaystyle w=[w_{1},\dots ,w_{n}]}$, ${\displaystyle Par(w)}$ является множеством WUM разбиений с весами ${\displaystyle w}$. Функция ${\displaystyle Par}$ является многозначной функцией из внутренности единичного симплекса в пространство множеств PE разрезаний торта.
2. Функция ${\displaystyle Val}$: для любого разбиения ${\displaystyle X=X_{1},\dots ,X_{n}}$, ${\displaystyle Val(X)}$ является вектором, пропорциональным значениям участников: ${\displaystyle Val(X)={\frac {[V_{1}(X_{1}),\dots ,V_{n}(X_{n})]}{V_{1}(X_{1})+\cdots +V_{n}(X_{n})}}}$. Функция ${\displaystyle Val}$ отображает пространство разрезаний торта в единичный симплекс.
3. Функция ${\displaystyle Wel=Val\circ Par}$: для любого положительного вектора весов ${\displaystyle w}$, ${\displaystyle Wel(w)}$ является множеством новых векторов весов. Это многозначная функция из внутренности единичного симплекса в множество подмножеств единичного симплекса. Вектора в ${\displaystyle Wel(w)}$ являются, отчасти, противоположными ${\displaystyle w}$ — если ${\displaystyle w_{i}}$ мало, то разбиения в ${\displaystyle Par(w)}$ дают агенту ${\displaystyle i}$ большое значение и его вес в ${\displaystyle Wel(w)}$ большой. Для сравнения, если ${\displaystyle w_{i}}$ большое, то разбиения в ${\displaystyle Par(w)}$ даёт агенту ${\displaystyle i}$ малое значение и его веса в ${\displaystyle Wel(w)}$ малы. Это подсказывает, что если ${\displaystyle Wel}$ имеет неподвижную точку, то эта неподвижная точка соответствует PEEF разбиению, которое мы ищем.

Чтобы доказать, что функция ${\displaystyle Wel}$ имеет неподвижную точку, нам следует использовать теорему Какутани о неподвижной точке. Однако имеется техническая проблема, которую нужно решить — функция ${\displaystyle Wel}$ определена только на внутренних точках единичного симплекса, а не на всём симплексе. К счастью, можно распространить ${\displaystyle Wel}$ на границы единичного симплекса способом, который гарантирует, что неподвижная точка НЕ окажется на границе[3]. Расширенная функция ${\displaystyle Wel'}$, более того, является функцией из единичного симплекса в подмножества единичного симплекса. ${\displaystyle Wel'}$ удовлетворяет требованиям теоремы Какутани о неподвижной точке, поскольку[4]:

• Это отображение точки в множества единичного симплекса, который является компактным и выпуклым подмножеством евклидова пространства;
• Она полунепрерывна сверху;
• Для любого ${\displaystyle w}$ в единичном симплексе ${\displaystyle Wel'(w)}$ не пусто, замкнуто и выпукло;

Поэтому ${\displaystyle Wel'}$ имеет неподвижную точку — вектор ${\displaystyle W}$ в единичном симплексе, такой, что ${\displaystyle W\in Wel'(W)}$. По построению ${\displaystyle Wel'}$ можно показать, что неподвижная точка ${\displaystyle W}$ должна быть внутренней в единичном симплексе, где ${\displaystyle Wel'\equiv Wel}$. Следовательно:

${\displaystyle W\in Wel(W)}$

По определению ${\displaystyle Wel}$, ${\displaystyle W\in Val(Par(W))}$, так что существует разбиение ${\displaystyle X}$, такое, что:

• ${\displaystyle X\in Par(W)}$
• ${\displaystyle W=Val(X)}$

Ясно, что ${\displaystyle X}$ является PE разбиением, поскольку оно WUM (с вектором весов W). Оно также EF, поскольку:

• из ${\displaystyle X\in Par(W)}$ следует, что X максимизирует взвешенную сумму с весами ${\displaystyle W=[W_{1},\dots ,W_{n}]}$. Это означает, что любая часть торта передаётся агенту, для которого взвешенная плотность оценки максимальна. Следовательно, для любых двух агентов ${\displaystyle i,j}$:

${\displaystyle {\frac {V_{j}(X_{j})}{w_{j}}}\geqslant {\frac {V_{i}(X_{j})}{w_{i}}}\implies {\frac {V_{j}(X_{j})}{V_{i}(X_{j})}}\geqslant {\frac {w_{j}}{w_{i}}}}$.

• из ${\displaystyle W=Val(X)}$ следует, что отношение между значениями для любых двух агентов ${\displaystyle i,j}$ равно отношению их весов:

${\displaystyle {\frac {V_{j}(X_{j})}{V_{i}(X_{i})}}={\frac {w_{j}}{w_{i}}}}$.

Комбинация двух последних неравенств даёт для любых двух агентов ${\displaystyle i,j}$:

${\displaystyle {\frac {V_{j}(X_{j})}{V_{i}(X_{j})}}\geqslant {\frac {V_{j}(X_{j})}{V_{i}(X_{i})}}\implies V_{i}(X_{j})\leqslant V_{i}(X_{i})}$

что в точности является определением отсутствия зависти.

В качестве иллюстрации рассмотрим торт с двумя частями, шоколадным и ванильным, и два участника, Алиса и Джордж, со следующими оценками:

Поскольку имеется два агента, вектор ${\displaystyle w}$ может быть представлен одним числом — отношением веса Алисы к весу Джорджа:

• Если отношение меньше 1:4, то WUM делёж должен дать весь торт Алисе. Отношение значений удовлетворения людей будет бесконечным (или 1:0), так что, конечно, никакие неподвижные точки не будут найдены в этой области.
• Если отношение в точности равно 1:4, то всю шоколадную часть следует отдать Алисе, а ванильную часть можно разделить произвольно между Алисой и Джорджем. Отношение значений WUM дележей меняется от 1:0 до 9:4. Эта область не содержит отношение 1:4, следовательно, неподвижная точка здесь не находится.
• Если отношение находится между 1:4 и 9:6, то всю ванильную часть следует отдать Джорджу, а всю шоколадную часть следует отдать Алисе. Отношение значений 9:4 не находится в этих границах, так что неподвижная точка не найдена.
• Если отношение в точности равно 9:6, то вся ванильная часть должна быть отдана Джорджу, но шоколадную часть можно поделить произвольно между Алисой и Джорджем. Отношение значений WUM дележей находится между 9:4 и 0:1. Мы видим, что 9:6 находится в этих пределах, так что мы имеем неподвижную точку. Её можно получить путём передачи Джорджу всей ванильной части и 1/6 шоколадной (для полного значения 5) и передаче Алисе оставшейся 5/6 шоколадной части (с полным значением 7,5). Этот делёж является PEEF-разбиением.

Берлянт, Томсон и Данц[5] ввели критерий отсутствия групповой зависти, который обобщает как эффективность по Парето, так и свободу от зависти. Они доказали существование распределений с отсутствием групповой зависти для аддитивных функций полезности. Позднее Берлянт и Данц[6] изучали некоторые естественные неаддитивные функции полезности, навеянные задачами деления участков земли. Когда функции полезности не аддитивны, существование CEEI-распределения не гарантируется, но оно существует при некоторых ограничениях.

Дополнительные связанные результаты можно найти в описании эффективного разрезания торта и разрезания торта согласно полезности.

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

Первый алгоритм нахождения CEEI-разбиения в этом случае разработали Райниэрс и Поттерс[7].

Более (вычислительно) эффективный алгоритм разработали Азиз и Йе[8].

Фактически любое CEEI-разрезание торта максимизирует произведение полезностей и наоборот, любое разрезание, максимизирующее произведение полезностей, является CEEI-дележом[9]. Поэтому CEEI-делёж может быть найден путём решения задачи выпуклого программирования максимизации суммы логарифмов полезностей.

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

Все вышеупомянутые алгоритмы могут быть обобщены до непрерывных по Липшицу мер ценности. Поскольку такие функции можно аппроксимировать кусочно-постоянными функциями «как хотим близко», вышеприведённые алгоритмы можно аппроксимировать PEEF-распределениями «как хотим близко»[7].

В CEEI-разбиении, гарантированном теоремой Веллера, куски, передаваемые каждому участнику, могут быть несвязными. Вместо одного непрерывного куска каждый участник получает гору «крошек». Более того, если куски должны быть связными, CEEI-разбиение может не существовать. Рассмотрим следующие кусочно-постоянные функции оценок:

Из условия CE следует, что все периферальные ломти должны иметь одну и ту же цену (скажем, p), и оба центральных ломтя должны иметь одинаковую цену (скажем, q). Из условия EI следует, что полная стоимость торта должна быть равна 2, так что ${\displaystyle q+2p=1}$. Из условия EI снова вытекает, что при любом связном CEEI дележе торт делится в середине. И Алиса, и Джордж получают по два периферальных ломтя и один центральный. Из условия CE для Алисы следует, что ${\displaystyle q=p}$, но из того же условия для Джорджа следует, что ${\displaystyle q=4p}$, получили противоречие.

В то время как условие CEEI может быть недосягаемым со связными частями, более слабое условие PEEF всегда достижимо, если имеется два участника. Это потому, что для двух участников отсутствие зависти эквивалентно пропорциональности, а пропорциональность сохраняется при улучшениях по Парето. Однако когда число партнёров равно трём и более, даже более слабое условие PEEF может оказаться недосягаемым. Рассмотрим следующие кусочно-постоянные оценки[10]:

Из EF следует, что Боб получает по меньшей мере часть ломтя ценой 7 (из PE тогда следует, что он получает его весь).

Согласно связности имеется три варианта:

• Кусок Карла находится справа от куска Боба. Таким образом, Карл получает крайний справа ломоть и его значение (по его оценке) равно 3. Из PE затем следует, что Алиса получает все пять ломтей слева от куска Боба, которые по оценке Карла стоят 4, так что Карл завидует Алисе.
• Кусок Карла находится слева от куска Боба и он получает два куска ценой 2. Тогда значение для Алисы не превосходит 2, а кусок Карла Алиса оценивает в 3, так что теперь Алиса завидует Карлу.
• Кусок Карла находится слева от куска Боба и он получает максимум один кусок ценой 2. Тогда распределение не будет PE, поскольку Карл может увеличить своё значение путём перемещения на правый край от Боба без ущерба для кого-либо.

Следовательно, никакое распределение не будет PEEF.

В примере выше, если мы рассматриваем торт как «пирог» (обычно предполагается, что торт можно представить как отрезок, пирог тогда представляется как окружность, то есть края отождествляются), то PEEF существует. Однако Стромквист[11] привёл более тонкий пример, когда PEEF-разбиение не существует даже для пирога.

• Эффективное по Парето распределение без зависти — аналогичная проблема для однородного разделимого блага.

• Dietrich Weller. Fair division of a measurable space // Journal of Mathematical Economics. — 1985. — Т. 14. — doi:10.1016/0304-4068(85)90023-0.
• Julius B. Barbanel. The geometry of efficient fair division. — Cambridge: Cambridge University Press, 2005. — ISBN 0-521-84248-4. — doi:10.1017/CBO9780511546679. Краткое изложение можно найти в статье
  • Barbanel J. A Geometric Approach to Fair Division // The College Mathematics Journal. — 2010. — Т. 41, вып. 4. — С. 268. — doi:10.4169/074683410x510263.
• Reijnierse J. H., Potters J. A. M. On finding an envy-free Pareto-optimal division // Mathematical Programming. — 1998. — Т. 83, вып. 1–3. — doi:10.1007/bf02680564.
• Chun Ye, Haris Aziz. Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations (англ.). — Web and Internet Economics. — Springer, Cham, 2014. — Vol. 8877. — (Lecture Notes in Computer Science). — ISBN 978-3-319-13128-3. — doi:10.1007/978-3-319-13129-0_1.
• Balázs R. Sziklai, Erel Segal-Halevi. Monotonicity and competitive equilibrium in cake-cutting (англ.) // Economic Theory. — 2018. — ISSN 0938-2259. — doi:10.1007/s00199-018-1128-6. — arXiv:1510.05229.
• Berliant M., Thomson W., Dunz K. On the fair division of a heterogeneous commodity // Journal of Mathematical Economics. — 1992. — Т. 21, вып. 3. — doi:10.1016/0304-4068(92)90001-n.
• Marcus Berliant, Karl Dunz. A foundation of location theory: Existence of equilibrium, the welfare theorems, and core // Journal of Mathematical Economics. — 2004. — Т. 40. — doi:10.1016/s0304-4068(03)00077-6.
• Walter Stromquist. A Pie That Can't Be Cut Fairly // Dagstuhl Seminar Proceedings. — 2007.