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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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