Теорема Веллерса - Википедия - Wellers theorem

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

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

Фон

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

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

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

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

Обозначение

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

А перегородка для торта, обозначаемый ${ displaystyle X}$, является ппара ${ Displaystyle X_ {1}, точки, X_ {n}}$ подмножеств ${ displaystyle C}$; ${ displaystyle X_ {i}}$ часть отдана партнеру ${ displaystyle i}$.

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

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

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

• Конкурентное равновесие: Для каждого агента я, каждый положительный срез ${ Displaystyle Z_ {я} substeq X_ {я}}$ и каждый положительный кусочек ${ Displaystyle Z substeq C}$: ${ Displaystyle v_ {я} (Z_ {я}) / P (Z_ {я}) geq v_ {я} (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}}$ - положительный вес.

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

Очевидно, что каждое подразделение WUM является физическим лицом. Однако разделение WUM может быть очень несправедливым; например, если ${ displaystyle w_ {i}}$ очень большой, тогда агент ${ displaystyle i}$ может получить только небольшую часть торта (весовой вектор ${ displaystyle w}$ очень близок к агенту ${ displaystyle i}$вершина единичного симплекса, что означает, что ${ displaystyle i}$ получит только те точки множества Радона-Никодима, которые находятся очень близко к его вершине). Напротив, если ${ displaystyle w_ {i}}$ очень маленький, тогда агент ${ displaystyle i}$ может получить весь торт.

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

1. Функция ${ displaystyle Par}$: для каждого положительного вектора веса ${ Displaystyle ш = [ш_ {1}, точки, ш_ {п}]}$, ${ displaystyle Par (w)}$ набор перегородок WUM с утяжелениями ${ displaystyle w}$. Функция ${ displaystyle Par}$ это многозначная функция из блока-симплекс-интерьер в пространство комплектов ПЭ торта-перегородок.

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 (ш)}$ набор новых весовых векторов. Это многозначная функция изнутри единичного симплекса в множество подмножеств единичного симплекса. Векторы в ${ Displaystyle Wel (ш)}$ в некотором смысле противоположны ${ displaystyle w}$: если ${ displaystyle w_ {i}}$ мала, то перегородки в ${ displaystyle Par (w)}$ дать агенту ${ displaystyle i}$ большое значение и его вес в ${ Displaystyle Wel (ш)}$ большой. Напротив, если ${ displaystyle w_ {i}}$ велико, то перегородки в ${ displaystyle Par (w)}$ дать агенту ${ displaystyle i}$ небольшое значение и его вес в ${ Displaystyle Wel (ш)}$ большой. Это намекает на то, что если ${ displaystyle Wel}$ имеет фиксированную точку, то эта фиксированная точка соответствует разделу PEEF, который мы ищем.

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

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

Следовательно, ${ 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}}} geq { frac {V_ {i} (X_ {j})} {w_ {i}}} подразумевает { frac {V_ {j} (X_ {j})} {V_ {i} (X_ {j})}} geq { 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})}} geq { frac {V_ {j} (X_ {j})} {V_ {i} (X_ {i})}} подразумевает 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})}$
• Цена каждой части, разделенной между несколькими агентами, является суммой цен ее подмножеств, удерживаемых этими агентами.

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

${ Displaystyle P (X_ {i}) = V_ {i} (X_ {i}) / V_ {i} (X_ {i}) = 1}$

Пример

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

Партнер	Шоколад	Ваниль
Алиса	9	1
Джордж	6	4

Поскольку агентов два, вектор ${ 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, гарантированном Weller, часть, выделенная каждому партнеру, может быть отключена. Вместо одной смежной фигуры каждый партнер может получить стопку «крошек». Действительно, когда части должны быть соединены, разделы CEEI могут не существовать. Рассмотрим следующие кусочно-постоянные оценки:

Алиса	2	2	2	2	2	2
Джордж	1	1	4	4	1	1

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

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

Алиса	2	0	3	0	2	0	0
Боб	0	0	0	0	0	7	0
Карл	0	2	0	2	0	0	3

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

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

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

Следовательно, PEEF не выделяется.

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

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

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

Рекомендации