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

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

Фон

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

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

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

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

Предположения

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

Процедура

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

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

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

Гарантии

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

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

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

Вычисление

Распределение A-CEEI трудно вычислить: оно завершено по PPAD . ^{[ 2 ]}

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

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

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

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

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

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

Оба алгоритма находят распределение EF-кроме-1.
Оба алгоритма приближаются к максимин-гарантии доли.

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

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

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

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

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

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

Сравнение с конкурентным равновесием

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

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

См. также

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

Ссылки

^ Будиш, Эрик (2011). «Комбинаторная задача о назначениях: приблизительное конкурентное равновесие при равных доходах». Журнал политической экономии . 119 (6): 1061–1103. дои : 10.1086/664613 . S2CID 1161325 .
^ Осман, Авраам; Пападимитриу, Христос; Рубинштейн, Авиад (2016). «Сложность справедливости через равновесие». Транзакции ACM по экономике и вычислениям . 4 (4): 1. arXiv : 1312,6249 . дои : 10.1145/2956583 .
^ Авраам Осман; Туомас Сандхольм и Эрик Будиш (2010). Поиск приблизительного конкурентного равновесия: эффективное и справедливое распределение курсов (PDF) . ААМАС '10. acm.org
^ Будиш, Эрик; Кесслер, Джадд Б. (2016). «Привлечение реальных предпочтений реальных участников рынка в лабораторию: эксперимент, который изменил механизм распределения курсов в Wharton» (PDF) . Архивировано из оригинала (PDF) 7 марта 2017 г. Проверено 6 марта 2017 г.
^ Караяннис, Иоаннис; Курокава, Дэвид; Мулен, Эрве; Прокачча, Ариэль Д.; Шах, Нисарг; Ван, Цзюньсин (2016). Необоснованная справедливость максимального благосостояния Нэша (PDF) . Материалы конференции ACM по экономике и вычислениям 2016 г. - EC '16. п. 305. дои : 10.1145/2940716.2940726 . ISBN 9781450339360 .
^ Jump up to: ^а ^б Курокава, Дэвид; Прокачча, Ариэль Д.; Ван, Цзюньсин (01 февраля 2018 г.). «Достаточно справедливо: гарантия примерного количества акций Maximin». Дж. АКМ . 65 (2): 8:1–8:27. дои : 10.1145/3140756 . ISSN 0004-5411 . S2CID 1525401 .

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

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

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

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

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

[:0-6] Jump up to: ^а ^б Курокава, Дэвид; Прокачча, Ариэль Д.; Ван, Цзюньсин (01 февраля 2018 г.). «Достаточно справедливо: гарантия примерного количества акций Maximin». Дж. АКМ . 65 (2): 8:1–8:27. дои : 10.1145/3140756 . ISSN 0004-5411 . S2CID 1525401 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]