Приблизительное конкурентное равновесие на основе равных доходов

Приблизительное конкурентное равновесие на основе равных доходов ( A-CEEI ) - это процедура справедливого распределения позиций . Его разработал Эрик Будиш. ^[1]

Фон [ править ]

CEEI (конкурентное равновесие на основе равных доходов) - это фундаментальное правило справедливого разделения делимых ресурсов. Он разделяет ресурсы в соответствии с результатом следующего гипотетического процесса:

Каждый агент получает одну единицу фиатных денег . Это часть CEEI, посвященная равным доходам.
Агенты торгуют свободно, пока рынок не достигнет конкурентного равновесия . Это вектор цен и распределение, так что (а) каждый выделенный пакет является оптимальным для своего агента с учетом его / ее дохода - агент не может купить лучший пакет с тем же доходом, и (б) рынок очищается - сумма всех отчислений в точности равна первоначальному взносу.

Равновесное распределение доказуемо свободно от зависти и эффективно по Парето . Более того, когда агенты имеют линейные функции полезности, распределение CEEI может быть эффективно вычислено.

К сожалению, когда есть неделимость, CEEI не всегда существует, поэтому его нельзя использовать напрямую для справедливого присвоения номенклатуры . Однако его можно приблизить, и это приближение обладает хорошей справедливостью, эффективностью и стратегическими свойствами.

Предположения [ править ]

A-CEEI предполагает только, что агенты знают, как ранжировать наборы предметов. Рейтинг не обязательно должен быть слабо аддитивным или даже монотонным.

Процедура [ править ]

A-CEEI с параметрами делит ресурсы в соответствии с результатом следующего гипотетического процесса: ${\ displaystyle \ alpha, \ beta}$

Приблизительный EI: каждый агент получает доход от 1 до . Точный доход каждого агента можно определить случайным образом или по стажу (пожилые люди могут получить немного больший доход). ${\ displaystyle 1+ \ beta}$
Приблизительный CE: рассчитывается вектор цен и распределение, так что (a) каждый выделенный пакет является оптимальным для своего агента с учетом его бюджета, и (b) рынок "почти" очищается: евклидово расстояние между суммой всех ассигнований и начального капитала не больше . ${\ displaystyle \ alpha}$

Будиш доказывает, что для любого существует -CEEI, где это зависит от минимума между количеством различных типов предметов и количеством различных предметов, которые может получить агент. ${\ displaystyle \ beta> 0}$ ${\ displaystyle \ alpha, \ beta}$ ${\ displaystyle \ alpha}$

Гарантии [ править ]

Распределение удовлетворяет следующим свойствам:

Предмет без зависти, кроме 1 (см. Назначение предмета без зависти ).
${\ Displaystyle (п + 1)}$ -maximin-доля-гарантия.
Эффективность Парето по выделенным позициям. То есть между агентами нет торговли, улучшающей Парето, но между агентом и маркет-мейкером могут быть трейдеры, улучшающие Парето.

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

Вычисление [ править ]

Распределение A-CEEI сложно вычислить: это PPAD-файл . ^[2]

Однако в задачах реалистичного размера A-CEEI может быть вычислен с использованием двухуровневого процесса поиска:

Мастер-уровень: центр использует табу-поиск, чтобы предлагать цены;
Уровень агента: смешанные целочисленные программы решаются для поиска запросов агентов по текущим ценам.

Программа на уровне агента может выполняться параллельно для всех агентов, поэтому этот метод почти оптимально масштабируется по количеству процессоров. ^[3]

Механизм был рассмотрен для задачи назначения студентов на курсы в Уортонской школе Университета Пенсильвании .^[4]

Сравнение с максимальным благосостоянием по Нэшу [ править ]

Максимум-Нэш-благосостояние алгоритма (MNW) находит распределение , которое максимизирует продукт утилита агентов. Он похож на A-CEEI в нескольких отношениях: ^[5]

Оба алгоритма находят выделение EF-except-1.
Оба алгоритма приближают максимальную гарантию акций.

Однако у A-CEEI есть несколько преимуществ:

Он работает с произвольными функциями полезности - не только с субмодульными . Это даже не требует однообразия предпочтений.
Он работает с порядковым вводом - агенты должны сообщать только о своем рейтинге по пакетам, а не о своей числовой оценке предметов.
Это доказательство стратегии "в целом".

С другой стороны, A-CEEI имеет несколько недостатков:

Имеется ошибка аппроксимации в распределенных позициях - некоторые позиции могут иметь избыточный спрос или избыточное предложение. ^[6]
В частности, возвращенное распределение не является эффективным по Парето - некоторые элементы остаются нераспределенными (оно эффективно по Парето только по отношению к выделенным элементам).

Ошибка аппроксимации A-CEEI растет с количеством отдельных элементов, но не с количеством игроков или количеством копий каждого элемента. Следовательно, A-CEEI лучше, когда есть много агентов и много копий каждого элемента. Типичное приложение - это когда агенты являются студентами, а элементы - позициями на курсах. ^[6]

Напротив, MNW лучше, когда есть несколько агентов и много разных элементов, например, при разделении наследования.

Сравнение с конкурентным равновесием [ править ]

A-CEEI (и CEEI в целом) связано, но не идентично, с концепцией конкурентного равновесия .

Конкурентное равновесие (CE) - это описательное понятие: оно описывает ситуацию на свободном рынке, когда цена стабилизируется, а спрос равен предложению.
CEEI - нормативное понятие: оно описывает правило разделения товаров между людьми.

См. Также [ править ]

Комбинаторный аукцион

Ссылки [ править ]

^ Будиш, Эрик (2011). «Комбинаторная проблема распределения: приблизительное конкурентное равновесие от равных доходов». Журнал политической экономии . 119 (6): 1061–1103. DOI : 10.1086 / 664613 .
↑ Осман, Авраам; Пападимитриу, Христос; Рубинштейн, Авиад (2016). «Сложность справедливости через равновесие». ACM Сделки по экономике и вычислениям . 4 (4): 1. arXiv : 1312.6249 . DOI : 10.1145 / 2956583 .
↑ Авраам Осман; Туомас Сандхольм и Эрик Будиш (2010). Нахождение приблизительного конкурентного равновесия: эффективное и справедливое распределение курса (PDF) . AAMAS '10. acm.org
^ Будиш, Эрик; Кесслер, Джадд Б. (2016). «Привлечение реальных предпочтений участников рынка в лабораторию: эксперимент, изменивший механизм распределения курсов в Wharton» (PDF) . Архивировано из оригинального (PDF) 07 марта 2017 года . Проверено 6 марта 2017 .
^ Карагианнис, Иоаннис; Курокава, Дэвид; Мулен, Эрве; Procaccia, Ariel D .; Шах, Нисарг; Ван, Цзюньсин (2016). Необоснованная справедливость максимального благосостояния Нэша (PDF) . Труды конференции ACM по экономике и вычислениям 2016 года - EC '16. п. 305. DOI : 10,1145 / 2940716,2940726 . ISBN 9781450339360.
^ a b Курокава, Дэвид; Procaccia, Ariel D .; Ван, Цзюньсин (01.02.2018). «Достаточно честно: гарантия приблизительного максимального количества акций». J. ACM . 65 (2): 8: 1–8: 27. DOI : 10.1145 / 3140756 . ISSN 0004-5411 .

[b11-1] Будиш, Эрик (2011). «Комбинаторная проблема распределения: приблизительное конкурентное равновесие от равных доходов». Журнал политической экономии . 119 (6): 1061–1103. DOI : 10.1086 / 664613 .

[2] Осман, Авраам; Пападимитриу, Христос; Рубинштейн, Авиад (2016). «Сложность справедливости через равновесие». ACM Сделки по экономике и вычислениям . 4 (4): 1. arXiv : 1312.6249 . DOI : 10.1145 / 2956583 .

[osb10-3] Авраам Осман; Туомас Сандхольм и Эрик Будиш (2010). Нахождение приблизительного конкурентного равновесия: эффективное и справедливое распределение курса (PDF) . AAMAS '10. acm.org

[bk16-4] Будиш, Эрик; Кесслер, Джадд Б. (2016). «Привлечение реальных предпочтений участников рынка в лабораторию: эксперимент, изменивший механизм распределения курсов в Wharton» (PDF) . Архивировано из оригинального (PDF) 07 марта 2017 года . Проверено 6 марта 2017 .

[ckmpsw16-5] Карагианнис, Иоаннис; Курокава, Дэвид; Мулен, Эрве; Procaccia, Ariel D .; Шах, Нисарг; Ван, Цзюньсин (2016). Необоснованная справедливость максимального благосостояния Нэша (PDF) . Труды конференции ACM по экономике и вычислениям 2016 года - EC '16. п. 305. DOI : 10,1145 / 2940716,2940726 . ISBN 9781450339360.

[:0-6] Курокава, Дэвид; Procaccia, Ariel D .; Ван, Цзюньсин (01.02.2018). «Достаточно честно: гарантия приблизительного максимального количества акций». J. ACM . 65 (2): 8: 1–8: 27. DOI : 10.1145 / 3140756 . ISSN 0004-5411 .

[1]