Теорема Веллерса - Wellers theorem - Wikipedia

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

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

Фон

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

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

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

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

Обозначение

Торт обозначается . Количество партнеров обозначается .

А перегородка для торта, обозначаемый , является ппара подмножеств ; часть отдана партнеру .

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

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

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

  • Конкурентное равновесие: Для каждого агента я, каждый положительный срез и каждый положительный кусочек : .
  • Равные доходы: Для каждого агента i: .

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

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

Доказательство эскиза

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

Доказательство Веллера опирается на взвешенно-утилитарно-максимальный (WUM) части торта. Подразделение WUM - это подразделение, максимизирующее функцию следующей формы:

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

Следствие Теорема Дубинса – Спаниера о компактности состоит в том, что для каждого вектора веса , Выделение WUM существует. Интуитивно каждый крошечный кусок торта следует дать человеку для кого самый большой. Если есть два или более людей, для которых это значение одинаково, то каждое произвольное разделение этой части между ними приводит к разделению WUM. (Распределение WUM также можно определить с помощью Набор Радон – Никодим. Каждый вектор веса , как точка на -размерный блок симплекс, определяет разбиение этого симплекса. Это разбиение индуцирует выделение множества Радона – Никодима торта, которое индуцирует одно или несколько распределений торта).

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

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

1. Функция : для каждого положительного вектора веса , набор перегородок WUM с утяжелениями . Функция это многозначная функция из блока-симплекс-интерьер в пространство комплектов ПЭ торта-перегородок.

2. Функция : для каждого раздела , - вектор, пропорциональный значениям партнеров: . Функция отображает пространство тортов-разбиений на единичный симплекс.

3. Функция : для каждого положительного вектора веса , набор новых весовых векторов. Это многозначная функция изнутри единичного симплекса в множество подмножеств единичного симплекса. Векторы в в некотором смысле противоположны : если мала, то перегородки в дать агенту большое значение и его вес в большой. Напротив, если велико, то перегородки в дать агенту небольшое значение и его вес в большой. Это намекает на то, что если имеет фиксированную точку, то эта фиксированная точка соответствует разделу PEEF, который мы ищем.

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

  • Это точечное отображение единичного симплекса, который является компактным и выпуклым подмножеством евклидова пространства;
  • это верхний полунепрерывный;
  • Для каждого в модуле-симплексе, непусто, замкнуто и выпукло;

Следовательно, имеет фиксированную точку - вектор в единичном симплексе такой, что . Построением , можно показать, что неподвижная точка должен быть в блок-симплекс-интерьер, где . Следовательно:

По определению , , значит существует раздел такой, что:

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

  • следует, что X максимизирует взвешенную сумму с весами . Это означает, что каждая фракция торта передается агенту, для которого взвешенная плотность ценности максимальна. Следовательно, для каждых двух агентов :
.
  • означает, что соотношение между ценностями каждых двух агентов равна соотношению их весов:
.

Объединение двух последних неравенств дает для каждых двух агентов :

что и есть определение свободы от зависти.

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

Как только у нас есть распределение PEEF , мера цены можно рассчитать следующим образом:

  • За каждую штуку который полностью принадлежит агенту ,
  • Цена каждой части, разделенной между несколькими агентами, является суммой цен ее подмножеств, удерживаемых этими агентами.

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

Пример

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

ПартнерШоколадВаниль
Алиса91
Джордж64

Поскольку агентов два, вектор может быть представлено одним числом - отношением веса Алисы к весу Джорджа:

  • Если соотношение меньше 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 могут не существовать. Рассмотрим следующие кусочно-постоянные оценки:

Алиса222222
Джордж114411

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

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

Алиса2030200
Боб0000070
Карл0202003

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

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

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

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

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

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

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

  1. ^ Веллер, Дитрих (1985). «Честное разделение измеримого пространства». Журнал математической экономики. 14: 5–17. Дои:10.1016/0304-4068(85)90023-0.
  2. ^ а б c Barbanel, Julius B .; с введением Алана Д. Тейлора (2005). Геометрия эффективного выставочного деления. Кембридж: Издательство Кембриджского университета. Дои:10.1017 / CBO9780511546679. ISBN  0-521-84248-4. МИСТЕР  2132232. Краткое резюме доступно по адресу: Барбанель, Дж. (2010). «Геометрический подход к справедливому разделению». Математический журнал колледжа. 41 (4): 268. Дои:10.4169 / 074683410x510263.
  3. ^ Берлиант, М .; Thomson, W .; Данц, К. (1992). «О справедливом разделении разнородного товара». Журнал математической экономики. 21 (3): 201. Дои:10.1016 / 0304-4068 (92) 90001-н.
  4. ^ Берлиант, Маркус; Данц, Карл (2004). «Основы теории местоположения: существование равновесия, теоремы о благосостоянии и ядро». Журнал математической экономики. 40 (5): 593. Дои:10.1016 / s0304-4068 (03) 00077-6.
  5. ^ а б Reijnierse, J. H .; Поттерс, Дж. А. М. (1998). «О поиске оптимального по Парето деления без зависти». Математическое программирование. 83 (1–3): 291–311. Дои:10.1007 / bf02680564.
  6. ^ Йе, Чун; Азиз, Харис (2014-12-14). Алгоритмы нарезки торта для кусочно-постоянных и кусочно-однородных оценок. Интернет и Интернет-экономика. Конспект лекций по информатике. 8877. Спрингер, Чам. С. 1–14. CiteSeerX  10.1.1.743.9056. Дои:10.1007/978-3-319-13129-0_1. ISBN  978-3-319-13128-3.
  7. ^ Sziklai, Balázs R .; Сегал-Халеви, Эрель (26.05.2018). «Монотонность и конкурентное равновесие в нарезке торта». Экономическая теория. 68 (2): 363–401. arXiv:1510.05229. Дои:10.1007 / s00199-018-1128-6. ISSN  0938-2259.
  8. ^ Сегал-Халеви, Эрель; Шиклай, Балаж Р. (01.09.2018). «Ресурсо-монотонность и популяционно-монотонность в связном разрезании торта». Математические социальные науки. 95: 19–30. arXiv:1703.08928. Дои:10.1016 / j.mathsocsci.2018.07.001. ISSN  0165-4896.
  9. ^ Стромквист, Уолтер (2007). «Пирог, который нельзя разрезать по-честному» (PDF). Материалы семинара в Дагштуле.