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

Теорема Веллера ^[1] — это теорема в экономике . Она гласит, что неоднородный ресурс («торт») может быть разделен между n партнерами с разными оценками таким образом, чтобы это было и Парето-эффективно (PE), и без зависти (EF). Таким образом, можно справедливо разделить торт, не жертвуя экономической эффективностью.

Более того, теорема Веллера утверждает, что существует цена, такая, что распределение и цена являются конкурентным равновесием (CE) с равными доходами (EI). Таким образом, она связывает две области исследований, которые ранее не были связаны: справедливое разделение торта и общее равновесие .

Фон

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

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

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

Разрезание торта сложнее, чем распределение однородного товара, поскольку торт неоднороден. В некотором смысле торт — это континуум товаров: каждая точка в торте — это другой товар. Это тема теоремы Веллера.

Обозначение

Торт обозначен как . Количество партнёров обозначено как . ${\displaystyle C}$ ${\displaystyle n}$

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

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

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

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

• Конкурентное равновесие : Для каждого агента i , каждого положительного среза и каждого положительного среза : . ${\displaystyle Z_{i}\subseteq X_{i}}$ ${\displaystyle Z\subseteq C}$ ${\displaystyle V_{i}(Z_{i})/P(Z_{i})\geq V_{i}(Z)/P(Z)}$
• Равные доходы: Для каждого агента i: . ${\displaystyle P(X_{i})=1}$

CEEI намного сильнее PEEF: каждое распределение CEEI является PEEF, но существует много распределений PEEF, которые не являются CEEI.

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

Эскиз доказательства

Представленная ниже презентация основана на статье Веллера и частично на ^{[2] : 341–351} .

Доказательство Веллера основано на делениях торта с весовым утилитарным максимумом (WUM) . Деление WUM — это деление, максимизирующее функцию следующего вида:

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

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

Следствием теоремы компактности Дубинса–Спаньера является то, что для каждого вектора веса существуют распределения WUM. Интуитивно понятно, что каждый крошечный кусок торта должен быть отдан тому, для кого он больше. Если есть два или более человека, для которых это значение одинаково, то любое произвольное деление этого куска между ними приводит к разделению WUM (распределения WUM также можно определить с помощью множества Радона–Никодима . Каждый вектор веса , как точка на -мерном единичном симплексе , определяет разбиение этого симплекса. Это разбиение индуцирует распределение множества Радона–Никодима торта, которое индуцирует одно или несколько распределений торта) . ${\displaystyle w}$ ${\displaystyle Z}$ ${\displaystyle i}$ ${\displaystyle {V_{i}(Z) \over w_{i}}}$ ${\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. Функция : для каждого положительного вектора веса , есть множество WUM-разделов с весами . Функция является функцией множества значений из единичного-симплекса-внутренности в пространство множеств PE-разделов торта. ${\displaystyle \operatorname {Par} }$ ${\displaystyle w=[w_{1},\dots ,w_{n}]}$ ${\displaystyle \operatorname {Par} (w)}$ ${\displaystyle w}$ ${\displaystyle \operatorname {Par} }$

2. Функция : для каждого разбиения , является вектором, пропорциональным значениям партнеров: . Функция отображает пространство торт-разбиений в единичный симплекс. ${\displaystyle \operatorname {Val} }$ ${\displaystyle X=X_{1},\dots ,X_{n}}$ ${\displaystyle \operatorname {Val} (X)}$ ${\displaystyle \operatorname {Val} (X)={\frac {[V_{1}(X_{1}),\dots ,V_{n}(X_{n})]}{V_{1}(X_{1})+\cdots +V_{n}(X_{n})}}}$ ${\displaystyle \operatorname {Val} }$

3. Функция : для каждого положительного вектора веса , является набором новых векторов веса. Это функция со множеством значений из внутренней части единичного симплекса в набор подмножеств единичного симплекса. Векторы в в некотором смысле противоположны : если мало, то разбиения в дают агенту большое значение и его вес в велико. Напротив, если велико, то разбиения в дают агенту малое значение и его вес в велико. Это намекает, что если имеет фиксированную точку, то эта фиксированная точка соответствует разбиению PEEF, которое мы ищем. ${\displaystyle \operatorname {Wel} =\operatorname {Val} \circ \operatorname {Par} }$ ${\displaystyle w}$ ${\displaystyle \operatorname {Wel} (w)}$ ${\displaystyle \operatorname {Wel} (w)}$ ${\displaystyle w}$ ${\displaystyle w_{i}}$ ${\displaystyle \operatorname {Par} (w)}$ ${\displaystyle i}$ ${\displaystyle \operatorname {Wel} (w)}$ ${\displaystyle w_{i}}$ ${\displaystyle \operatorname {Par} (w)}$ ${\displaystyle i}$ ${\displaystyle \operatorname {Wel} (w)}$ ${\displaystyle \operatorname {Wel} }$

Чтобы доказать, что функция имеет неподвижную точку, мы хотели бы использовать теорему Какутани о неподвижной точке . Однако есть техническая проблема, которую следует решить: функция определена только внутри единичного симплекса, в то время как ее областью действия является весь единичный симплекс. К счастью, ее можно расширить до границы единичного симплекса таким образом, чтобы гарантировать, что никакая неподвижная точка НЕ ​​будет на границе. ^{[2] : 343–344} Расширенная функция, , действительно является функцией из единичного симплекса в подмножества единичного симплекса. удовлетворяет требованиям теоремы Какутани о неподвижной точке, поскольку: ^{[2] : 345–349} ${\displaystyle \operatorname {Wel} }$ ${\displaystyle \operatorname {Wel} }$ ${\displaystyle \operatorname {Wel} }$ ${\displaystyle \operatorname {Wel} '}$ ${\displaystyle \operatorname {Wel} '}$

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

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

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

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

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

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

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

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

• ${\displaystyle W=\operatorname {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})}}\geq {\frac {V_{j}(X_{j})}{V_{i}(X_{i})}}\implies V_{i}(X_{j})\leq V_{i}(X_{i})}$

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

Расчет меры цены

После распределения PEEF показатель цены можно рассчитать следующим образом: ${\displaystyle X}$ ${\displaystyle P}$

• Для каждой части , которая полностью принадлежит агенту , ${\displaystyle Z_{i}}$ ${\displaystyle i}$ ${\displaystyle P(Z_{i})=V_{i}(Z_{i})/V_{i}(X_{i})}$
• Для каждой части, разделенной между несколькими агентами, цена представляет собой сумму цен ее подмножеств, принадлежащих этим агентам.

Можно доказать, что пара удовлетворяет условиям конкурентного равновесия с равными доходами (CEEI). В частности, доход каждого агента, при ценовой мере , равен ровно 1, поскольку ${\displaystyle X,P}$ ${\displaystyle P}$

${\displaystyle P(X_{i})=V_{i}(X_{i})/V_{i}(X_{i})=1.}$

Пример

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

Поскольку агентов двое, вектор можно представить одним числом – отношением веса Алисы к весу Джорджа: ${\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.

Обобщения и расширения

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

Дополнительные результаты по теме можно найти в разделах Эффективное разрезание торта и Утилитарное разрезание торта .

Алгоритмы

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

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

Азиз и Йе разработали более эффективный с вычислительной точки зрения алгоритм. ^[6]

Фактически, каждое разбиение торта CEEI максимизирует произведение полезностей, и наоборот – каждое разбиение, максимизирующее произведение полезностей, является CEEI. ^[7] Следовательно, CEEI можно найти, решив выпуклую программу, максимизирующую сумму логарифмов полезностей.

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

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

Ограничения

В разбиении CEEI, гарантированном Уэллером, часть, выделенная каждому партнеру, может быть разъединенной. Вместо одной непрерывной части каждый партнер может получить кучу "крошек". Действительно, когда части должны быть соединены, разбиения CEEI могут не существовать. Рассмотрим следующие кусочно-постоянные оценки:

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

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

EF подразумевает, что Боб получает по крайней мере часть своего 7-значного среза (тогда PE подразумевает, что он получает его весь).

По подключению есть три варианта:

• Часть Карла находится справа от части Боба. Поэтому Карл получает самую правую часть, и его ценность равна 3. PE тогда подразумевает, что Алиса получает все пять частей слева от части Боба, которые стоят 4 для Карла. Поэтому Карл завидует Алисе.
• Фигура Карла находится слева от фигуры Боба, и он получает свои две фигуры стоимостью 2. Тогда ценность Алисы не превышает 2, а фигура Карла стоит для Алисы 3. Поэтому Алиса завидует Карлу.
• Фигура Карла находится слева от фигуры Боба, и он получает максимум одну фигуру стоимостью 2. Тогда распределение не является PE, поскольку Карл может увеличить свою ценность до 3, переместившись вправо от Боба, не причиняя никому вреда.

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

В приведенном выше примере, если мы рассматриваем торт как «пирог» (т. е. если части разрешено обойти границу торта и перейти на другую границу), то распределение PEEF существует; однако Стромквист ^[9] продемонстрировал более сложный пример, в котором распределение PEEF не существует даже в пироге.

Смотрите также

• Парето-эффективный дележ без зависти – аналогичная задача для однородных делимых благ.

Ссылки

1. Веллер, Дитрих (1985). «Справедливое разделение измеримого пространства». Журнал математической экономики . 14 : 5–17. doi :10.1016/0304-4068(85)90023-0.
2. Барбанель, Джулиус Б. (2005). Геометрия эффективного справедливого деления. Введение Алана Д. Тейлора. Кембридж: Cambridge University Press. doi : 10.1017/CBO9780511546679. ISBN 0-521-84248-4. МР  2132232. Краткое изложение доступно по адресу: Barbanel, J. (2010). "Геометрический подход к справедливому делению". The College Mathematics Journal . 41 (4): 268. doi :10.4169/074683410x510263.
3. Берлиант, М.; Томсон, В.; Данц, К. (1992). «О справедливом разделе разнородного товара». Журнал математической экономики . 21 (3): 201. doi :10.1016/0304-4068(92)90001-n.
4. Берлиант, Маркус; Данц, Карл (2004). «Основание теории размещения: существование равновесия, теоремы о благосостоянии и ядро». Журнал математической экономики . 40 (5): 593. doi :10.1016/s0304-4068(03)00077-6.
5. Reijnierse, JH; Potters, JAM (1998). «О поиске свободного от зависти Парето-оптимального деления». Математическое программирование . 83 (1–3): 291–311. doi :10.1007/bf02680564.
6. Ye, Chun; Aziz, Haris (2014-12-14). "Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations". Web and Internet Economics . Lecture Notes in Computer Science. Vol. 8877. Springer, Cham. pp. 1–14. CiteSeerX 10.1.1.743.9056 . doi :10.1007/978-3-319-13129-0_1. ISBN  978-3-319-13128-3.
7. Шиклай, Балаж Р.; Сегал-Халеви, Эрель (26 мая 2018 г.). «Монотонность и конкурентное равновесие в разрезании тортов». Экономическая теория . 68 (2): 363–401. arXiv : 1510.05229 . дои : 10.1007/s00199-018-1128-6. ISSN  0938-2259.
8. Сегал-Халеви, Эрель; Шиклай, Балаж Р. (01 сентября 2018 г.). «Ресурсная монотонность и популяционная монотонность в связанном разрезании торта». Математические социальные науки . 95 : 19–30. arXiv : 1703.08928 . doi : 10.1016/j.mathsocsci.2018.07.001. ISSN  0165-4896.
9. Стромквист, Уолтер (2007). «Пирог, который нельзя разрезать честно» (PDF) . Труды семинара в Дагштуле .