Рынок Фишера - Fisher market

Рынок Фишера является экономическая модель приписывается Ирвинг Фишер. В его состав входят следующие ингредиенты:^[1]

• Набор ${\displaystyle m}$ делимые продукты с заранее заданными количествами (обычно нормализованные таким образом, что количество каждого товара равно 1).
• Набор ${\displaystyle n}$ покупатели.
• Каждому покупателю ${\displaystyle i=1,\dots ,n}$, есть заранее определенный денежный бюджет ${\displaystyle B_{i}}$(обычно нормализуется так, что сумма бюджетов равна 1).

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

Каждый продукт ${\displaystyle j}$ имеет цену ${\displaystyle p_{j}}$; цены определяются методами, которые мы описываем ниже. Цена на пучок of products - сумма цен на товары в комплекте. Пучок представлен вектором ${\displaystyle x=x_{1},\dots ,x_{m}}$, куда ${\displaystyle x_{j}}$ количество продукта ${\displaystyle j}$. Итак, цена пачки ${\displaystyle x}$ является ${\displaystyle p(x)=\sum _{j=1}^{m}p_{j}\cdot x_{j}}$.

Связка доступный для покупателя, если цена этого комплекта не превышает его бюджета. Т.е. пучок ${\displaystyle x}$ доступен покупателю ${\displaystyle i}$ если ${\displaystyle p(x)\leq B_{i}}$.

У каждого покупателя есть отношение предпочтений над связками, что может быть представлено функцией полезности. Функция полезности покупателя ${\displaystyle i}$ обозначается ${\displaystyle u_{i}}$. В набор спроса покупателя - это набор доступных пакетов, которые максимизируют полезность покупателя среди всех доступных пакетов, то есть:

${\displaystyle {\text{Demand}}_{i}(p):=\arg \max _{p(x)\leq B_{i}}u_{i}(x)}$.

А конкурентное равновесие (CE) - это вектор цены ${\displaystyle p_{1},\dots ,p_{m}}$в котором каждому агенту можно выделить набор из его набора спроса, так что общее распределение в точности равно предложению продуктов. Соответствующие цены называются рыночные цены. Основная проблема при анализе рынков Fisher - это поиск CE.^{[2]:103–105}

Наличие конкурентного равновесия

Существование СЕ может быть доказано на основе известного Лемма Спернера.^[3]:67

Предположим, что количества нормализованы так, что на продукт приходится 1 единица, а бюджеты нормализованы так, что их сумма равна 1. Также предположим, что все продукты хороши, т.е. агент всегда строго предпочитает иметь больше каждого продукта, если он может себе это позволить.

Рассмотрим стандартный симплекс с м вершины. Каждая точка в этом симплексе соответствует вектору цен, где сумма всех цен равна 1; следовательно, цена всех товаров вместе равна 1.

В каждом ценовом векторе п, мы можем найти набор спроса для каждого агента, затем вычислить сумму всех наборов спроса, а затем найти общую цену этого совокупного спроса. Поскольку цена каждого набора спроса не превышает бюджета агента, а сумма бюджетов не превышает 1, цена совокупного спроса не превышает 1. Следовательно, для каждого п, есть хотя бы один товар, суммарный спрос на который не превышает 1. Назовем такой товар "дорогим товаром" в п.

Триангулировать м-vertex симплекс, и обозначить каждую вершину триангуляции п с индексом произвольного дорогого товара в п. В каждой грани симплекса некоторые продукты стоят 0. Поскольку все продукты хороши, спрос каждого агента на продукт, который стоит 0, всегда равен 1; следовательно, продукт, который стоит 0, никогда не может считаться дорогим. Следовательно, указанная выше разметка удовлетворяет граничному условию Спернера.

По лемме Спернера существует бэби-симплекс, вершины которого помечены м разные этикетки. Поскольку функция спроса непрерывна, с помощью все более тонкой триангуляции мы находим единый вектор цен п*, при котором все товары дорогие, т.е. совокупный спрос на каждый продукт не более 1.

Но, поскольку сумма всех бюджетов равна 1, совокупный спрос на каждый продукт в п* должно быть ровно 1. Следовательно п* - вектор рыночных цен.

Расчет конкурентного равновесия

Хотя лемму Спернера можно использовать для нахождения CE, она очень неэффективна в вычислительном отношении. Есть гораздо более эффективные методы, которые обычно основаны на выпуклое программирование или же линейное программирование.

Однородные инженерные сети

Допустим, коммунальные услуги всех покупателей однородные функции (это, в частности, утилиты с постоянная эластичность замещения ).

Тогда условия равновесия в модели Фишера могут быть записаны как решения выпуклая оптимизация программа называется Выпуклая программа Айзенберга-Гейла.^[4] Эта программа находит распределение, которое максимизирует взвешенный среднее геометрическое коммунальных услуг покупателей, где вес определяется бюджетом. Эквивалентно, он максимизирует взвешенное среднее арифметическое логарифмов полезностей:

Максимизировать ${\displaystyle \sum _{i=1}^{n}\left(B_{i}\cdot \log {(u_{i})}\right)}$

При условии:

Неотрицательные количества: Каждому покупателю ${\displaystyle i}$ и продукт ${\displaystyle j}$: ${\displaystyle x_{i,j}\geq 0}$

Достаточно припасов: Для каждого продукта ${\displaystyle j}$: ${\displaystyle \sum _{i=1}^{n}x_{i,j}\leq 1}$

(поскольку запасы нормированы на 1).

Эту проблему оптимизации можно решить с помощью Условия Каруша – Куна – Таккера. (ККТ). Эти условия вводят множители Лагранжа, которые можно интерпретировать как Цены, ${\displaystyle p_{1},\dots ,p_{m}}$. При каждом распределении, которое максимизирует программу Айзенберга-Гейла, каждый покупатель получает требуемый пакет. То есть решение программы Айзенберга-Гейла представляет собой рыночное равновесие.^{[5]:141–142}

Линейные утилиты

Особый случай однородных коммунальных услуг - это когда все покупатели имеют линейная полезность функции. Это означает, что для каждого покупателя ${\displaystyle i}$ и продукт ${\displaystyle j}$, есть постоянная ${\displaystyle u_{i,j}}$ (полезность покупателя ${\displaystyle i}$ для продукта ${\displaystyle j}$) таким образом, что общая полезность, которую покупатель получает от пакета, составляет:

${\displaystyle u_{i}(x_{1},\dots ,x_{j})=\sum _{j=1}^{m}u_{i,j}\cdot x_{j}}$, куда ${\displaystyle u_{i,j}\geq 0}$

Мы предполагаем, что у каждого продукта есть потенциальный покупатель - покупатель, который получает положительную полезность от этого продукта. Согласно этому предположению, клиринговые цены существуют и уникальны. Доказательство основано на программе Айзенберга-Гейла. Из условий ККТ следует, что оптимальные решения (распределения ${\displaystyle x_{i,j}}$ и цены ${\displaystyle p_{j}}$) удовлетворяют следующим неравенствам:

1. Все цены неотрицательны: ${\displaystyle p_{j}\geq 0}$.
2. Если у товара положительная цена, то весь его запас исчерпан: ${\displaystyle p_{j}>0\implies \sum _{i=1}^{n}x_{i,j}=1}$.
3. Общая полезность на монету покупателя (общая полезность, деленная на общий бюджет) немного больше, чем его полезность на монету от каждого отдельного продукта: ${\displaystyle {\frac {\sum _{k=1}^{m}u_{i,k}\cdot x_{i,k}}{B_{i}}}\geq {\frac {u_{i,j}}{p_{j}}}}$
4. Если покупатель покупает положительное количество продукта, то его общая полезность на монету равна его полезности на монету этого продукта: ${\displaystyle x_{i,j}>0\implies {\frac {\sum _{k=1}^{m}u_{i,k}\cdot x_{i,k}}{B_{i}}}={\frac {u_{i,j}}{p_{j}}}}$

Предположим, что каждый продукт ${\displaystyle j}$ есть потенциальный покупатель - покупатель ${\displaystyle i}$ с ${\displaystyle u_{i,j}>0}$. Тогда из неравенства 3 следует, что ${\displaystyle p_{j}>0}$, т.е. все цены положительные. Тогда неравенство 2 означает, что все запасы исчерпаны. Неравенство 4 означает, что бюджеты всех покупателей исчерпаны. То есть рынок очищается.

Поскольку функция журнала строго вогнутая функция, если существует более одного равновесного распределения, то полезность, полученная каждым покупателем в обоих распределениях, должна быть одинаковой (уменьшение полезности покупателя не может быть компенсировано увеличением полезности другого покупателя). Это вместе с неравенством 4 означает, что цены уникальны.^[2]:107

Слабо полиномиальный алгоритм

Существует слабо полиномиальный алгоритм нахождения равновесных цен и распределения на линейном рынке Фишера. Алгоритм основан на условии 4 выше. Условие подразумевает, что в состоянии равновесия каждый покупатель покупает только те продукты, которые дают ему максимальную полезность на монету. Предположим, покупателю «нравится» продукт, если этот продукт дает ему максимальную полезность на монету в текущих ценах. Учитывая вектор цен, мы можем построить проточная сеть в котором емкость каждого ребра представляет собой общую сумму денег, "текущих" через это ребро. Сеть выглядит следующим образом:

• Есть исходный узел, s.
• Для каждого продукта есть узел; есть край от s к каждому продукту j, с емкостью ${\displaystyle p_{j}}$ (это максимальная сумма денег, которую можно потратить на товар j, так как подача нормирована на 1).
• На каждого покупателя есть узел; есть преимущество от продукта к покупателю с неограниченной емкостью, если покупателю нравится продукт (в текущих ценах).
• Есть целевой узел, т; есть преимущество от каждого покупателя я к т, с емкостью ${\displaystyle B_{i}}$ (максимальный расход я).

Ценовой вектор п является вектором равновесной цены тогда и только тогда, когда два сокращения ({s}, V {s}) и (V {t}, {t}) равны min-cuts. Следовательно, вектор равновесной цены можно найти по следующей схеме:

• Начните с очень низких цен, которые гарантированно будут ниже равновесных цен; в этих ценах у покупателей остается некоторый бюджет (т.е. максимальный поток не достигает емкости узлов в т).
• Постоянно повышайте цены и соответствующим образом обновляйте потоковую сеть, пока не будут исчерпаны все бюджеты.

Есть алгоритм, решающий эту проблему за слабо полиномиальное время.^{[2]:109–121}

Рынки Fisher с неделимыми предметами

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

Дэн и др.^[6] изучили рынок, на котором каждый агент приходит с начальным капиталом (а не с начальным доходом), и все оценки являются аддитивными. Они доказали, что решить, существует ли CE, NP-сложно даже с 3 агентами. Они представили алгоритм аппроксимации, который ослабляет условия CE двумя способами: (1) набор, выделенный каждому агенту, оценивается по крайней мере в 1-эпсилон от оптимума с учетом цен, и (2) спрос не менее 1-эпсилон-кратного поставки.

Бувере и Леметр^[7] изучили CE-from-equal-yields (CEEI) как правило для справедливого распределения предметов. Они связали это с четырьмя другими критериями справедливости, предполагая, что у всех агентов есть аддитивные функции оценки. Они спросили, какова вычислительная сложность определения существования CEEI.

На этот вопрос вскоре ответил Азиз:^[8] который доказал, что задача является слабо NP-сложной, когда есть два агента и м предметы, и сильно NP-трудный, когда есть п агенты и 3п Предметы. Он также представил более сильное условие, называемое CEEI-FRAC, которое, что интересно, легче проверить - оно может быть проверено за полиномиальное время. Мильтерсен, Хоссейни и Бранцеи^[9] Доказано, что даже проверка того, является ли данное распределение CEEI, сопряжена с NP-трудностью. Они изучали CEEI также для целенаправленных агентов. В этом случае проверка того, является ли данное распределение CEEI, является полиномиальным, но проверка того, существует ли CEEI, является совместно NP-полной.

Heinen et al.^[10] расширил работу Бувере и Леметра с аддитивной до k-аддитивные функции полезности, в котором каждый агент сообщает значение для пакетов, содержащих не более k элементов, а значения более крупных пакетов определяются путем сложения и вычитания значений основных пакетов.

Будиш^[11] изучили наиболее общие условия, в которых агенты могут иметь произвольные отношения предпочтения перед связками. Он изобрел механизм Приблизительное конкурентное равновесие на основе равных доходов, что ослабляет условия CEEI двумя способами: (1) доходы агентов не совсем равны, и (2) небольшое количество предметов может остаться нераспределенным. Он доказал, что приблизительный CEEI существует всегда (хотя Othman et al.^[12] недавно доказал, что вычисление приближенного CEEI PPAD завершен ).

Бармен и Кришнамурти^[13] изучите рынки Fisher, на которых все агенты имеют дополнительные услуги. Они показывают, что дробный CE (где некоторые товары разделены) всегда можно округлить до целого CE (где товары остаются неделимыми), изменяя бюджеты агентов. Изменение каждого бюджета может достигать максимальной цены товара в дробной CE.

Бабайофф, Нисан и Талгам-Коэн^[14] изучили, существует ли CE, когда доходы общий, т.е. не удовлетворяют конечному набору равенств. Другими словами: существует ли КЭ для почти все доход-векторы. Они доказали существование трех товаров, четырех товаров и двух агентов. Они доказали отсутствие пяти товаров и двух агентов. Позже было доказано, что с четырьмя товарами и тремя агентами CE может не существовать, когда оценки неаддитивны, но всегда существует, когда оценки аддитивны.^[15]

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

• В Модель Эрроу – Дебре является обобщением модели Фишера, в которой каждый агент может быть как покупателем, так и продавцом. То есть каждый агент приходит с комплектом продуктов, а не только с деньгами.
• Общее равновесие
• Рынки Айзенберга – Гейла - еще одно обобщение линейного рынка Фишера.^[16]

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

1. Ишай Мансур (2011). «Лекция 10: Рыночное равновесие» (PDF). Продвинутые темы машинного обучения и алгоритмической теории игр. Получено 15 марта 2016.
2. Вазирани, Виджай В.; Нисан, Ноам; Roughgarden, Тим; Тардос, Ива (2007). "Глава 5: Комбинаторные алгоритмы рыночного равновесия / Виджай В. Вазирани". Алгоритмическая теория игр (PDF). Кембридж, Великобритания: Издательство Кембриджского университета. ISBN  0-521-87282-0.
3. Шарф, Герберт (1967). «Суть игры N человек». Econometrica. 35 (1): 50–69. Дои:10.2307/1909383. JSTOR  1909383.
4. Айзенберг, Э. (1961). «Агрегирование служебных функций». Наука управления. 7 (4): 337–350. Дои:10.1287 / mnsc.7.4.337.
5. Вазирани, Виджай В.; Нисан, Ноам; Roughgarden, Тим; Тардос, Ива (2007). «Глава 6: Вычисление рыночных равновесий с помощью выпуклого программирования / Бруно Коденотти и Кастури Варадараджан». Алгоритмическая теория игр (PDF). Кембридж, Великобритания: Издательство Кембриджского университета. ISBN  0-521-87282-0.
6. Дэн, Сяотэ; Пападимитриу, Христос; Сафра, Шмуэль (01.09.2003). «О сложности ценовых равновесий». Журнал компьютерных и системных наук. 67 (2): 311–324. Дои:10.1016 / S0022-0000 (03) 00011-4. ISSN  0022-0000.
7. Лемэтр, Мишель; Бувере, Сильвен (01.03.2016). «Характеризация конфликтов при справедливом разделении неделимых товаров по шкале критериев». Автономные агенты и мультиагентные системы. 30 (2): 259–290. Дои:10.1007 / s10458-015-9287-3. ISSN  1573-7454. S2CID  16041218.
8. Азиз, Харис (01.11.2015). «Конкурентное равновесие с равными доходами для размещения неделимых объектов». Письма об исследованиях операций. 43 (6): 622–624. arXiv:1501.06627. Bibcode:2015arXiv150106627A. Дои:10.1016 / j.orl.2015.10.001. ISSN  0167-6377. S2CID  11495811.
9. Милтерсен, Питер Бро; Хоссейни, Хади; Brânzei, Simina (28 сентября 2015 г.). Характеристика и вычисление равновесий для неделимых товаров. Алгоритмическая теория игр. Конспект лекций по информатике. Шпрингер, Берлин, Гейдельберг. С. 244–255. arXiv:1503.06855. Дои:10.1007/978-3-662-48433-3_19. ISBN  9783662484326. S2CID  656603.
10. Роте, Йорг; Нгуен, Нхан-Там; Хайнен, Тобиас (27 сентября 2015 г.). Справедливость и взвешенный по рангам утилитаризм в распределении ресурсов. Теория алгоритмических решений. Конспект лекций по информатике. Спрингер, Чам. С. 521–536. Дои:10.1007/978-3-319-23114-3_31. ISBN  9783319231136.
11. Будиш, Эрик (2011). "Комбинаторная проблема распределения: приблизительное конкурентное равновесие от равных доходов". Журнал политической экономии. 119 (6): 1061–1103. CiteSeerX  10.1.1.357.9766. Дои:10.1086/664613.
12. Осман, Авраам; Пападимитриу, Христос; Рубинштейн, Авиад (01.08.2016). «Сложность справедливости через равновесие». Сделки ACM по экономике и вычислениям. 4 (4): 20:1–20:19. CiteSeerX  10.1.1.747.956. Дои:10.1145/2956583. ISSN  2167-8375.
13. Бармен, Сиддхартх; Кришнамурти, Санат Кумар (21.11.2018). «О близости рынков с интегральными равновесиями». arXiv:1811.08673 [cs.GT ].
14. Талгам-Коэн, Инбал; Нисан, Ноам; Бабайофф, Моше (23 марта 2017 г.). «Конкурентное равновесие с неделимыми товарами и общими бюджетами». arXiv:1703.08150 [cs.GT ].
15. Сегал-Халеви, Эрель (20.02.2020). «Конкурентное равновесие почти для всех доходов: существование и справедливость». Автономные агенты и мультиагентные системы. 34 (1): 26. arXiv:1705.04212. Дои:10.1007 / s10458-020-09444-z. ISSN  1573-7454. S2CID  210911501.
16. Джайн, Камаль; Вазирани, Виджай В. (2010). «Рынки Эйзенберга – Гейла: алгоритмы и теоретико-игровые свойства». Игры и экономическое поведение. 70: 84–106. Дои:10.1016 / j.geb.2008.11.011.