Рыбацкий рынок

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

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

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

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

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

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

( Конкурентное равновесие CE) – это вектор цен. $p_{1},\dots ,p_{m}$в котором можно распределить каждому агенту набор из его набора спроса так, чтобы общее распределение точно равнялось предложению продуктов. Соответствующие цены называются рыночными ценами . Основная задача при анализе рынков Fisher — найти CE.

Похожие модели

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

Рыбацкий рынок с делящимися предметами

Существование равновесия

Когда все товары на рынке являются делимыми, CE всегда существует. Это можно доказать с помощью знаменитой леммы Спернера .

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

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

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

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

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

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

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

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

Деванур, Пападимитриу, Сабери и Вазирани предоставил алгоритм с полиномиальным временем для точного расчета равновесия на Фишера рынках с линейными функциями полезности. Их алгоритм использует парадигму «просто-двойственный» в расширенной настройке условий ККТ и выпуклых программ. Их алгоритм слабополиномиален: он решает $O((n+m)^{5}\log(u_{\max })+(n+m)^{4}\log {B_{\max }})$ проблемы с максимальным потоком , и поэтому он работает вовремя $O((n+m)^{8}\log(u_{\max })+(n+m)^{7}\log {B_{\max }})$, где u _max и B _max — максимальная полезность и бюджет соответственно.

Орлин предоставил улучшенный алгоритм для модели рынка Фишера с линейными полезностями, работающими во времени. $O((n+m)^{4}\log(u_{\max })+(n+m)^{3}B_{\max })$. Затем он улучшил свой алгоритм, чтобы он работал за строго полиномиальное время : $O((m+n)^{4}\log(m+n))$.

Чен и Тенг доказал, что, когда утилиты агентов могут быть произвольными функциями SPLC (сепарабельные кусочно-линейные вогнутые), найти CE является PPAD-трудной задачей .

Бады и смешанная манна

Богомольная, Мулен, Сандомирский и Яновская изучали существование и свойства СЕ на рынке Фишера с бадами (предметами с отрицательной полезностью). и со смесью добра и зла. В отличие от ситуации с товарами, когда ресурсы плохие, CE не решает никаких задач выпуклой оптимизации даже с линейными полезностями. Распределения CE соответствуют локальным минимумам, локальным максимумам и седловым точкам произведения полезностей на границе Парето множества возможных полезностей. Правило CE становится многозначным. Эта работа привела к созданию нескольких работ по алгоритмам поиска CE на таких рынках:

• Бранзей и Сандомирский дал алгоритм поиска всех СЕ на рынке Фишера с бэдами и линейными полезностями. Их алгоритм работает за сильно полиномиальное время, если либо n , либо m фиксировано. Их подход сочетает в себе три идеи: все графики потребления распределения PO могут быть перечислены за полиномиальное время; для данного графика потребления кандидат CE может быть построен с помощью явной формулы; и данное распределение может быть проверено на предмет CE, используя вычисление максимального потока .
• Гарг и МакГлафлин дал алгоритм для расчета всех CE на рынке Фишера со смешанной манной и линейными полезностями. Их алгоритм работает за полиномиальное время, если либо n , либо m фиксировано.
• Чаудхури, Гарг, МакГлафлин и Мехта дал алгоритм для вычисления одного CE на рынке Fisher со смешанными утилитами Manna и SPLC. Их алгоритм симплексный и основан на Лемке схеме . Хотя время его выполнения в худшем случае не является полиномиальным (проблема PPAD-сложна даже с товарами). ), он работает быстро в случайных случаях. Это также доказывает, что проблема в PPAD, решения рациональнозначны, а количество решений нечетно. Их алгоритм работает за полиномиальное время в особом случае, когда все полезности отрицательны.

Если и n, и m являются переменными, проблема становится вычислительно сложной:

• Чаудхури, Гарг, МакГлафлин и Мехта покажите, что на рынке Фишера с плохими и линейными полезностями NP-трудно решить, существует ли CE. Такая же сложность сохраняется даже для нахождения (11/12+δ)-ВЭ при любом δ>0 и даже при равных доходах. Они также доказывают достаточное условие существования CE, основанное на связности графов. При этом условии CE всегда существует, но найти его PPAD-трудно.

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

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

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

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

Вскоре на этот вопрос ответил Азиз: который доказал, что задача является слабо NP-трудной при наличии двух агентов и m предметов и сильно NP-трудной при наличии n агентов и 3 n предметов. Он также представил более сильное условие под названием CEEI-FRAC, которое, что интересно, легче проверить — его можно проверить за полиномиальное время. Мильтерсен, Хоссейни и Бранзей доказал, что даже проверка того, является ли данное распределение CEEI, является сложной задачей для NP. Они изучали CEEI также для целеустремленных агентов. В этом случае проверка того, является ли данное распределение CEEI, является полиномиальной, но проверка существования CEEI является ко-NP-полной.

Хейне и др. расширил работу Бувере и Леметра от аддитивных функций полезности до k-аддитивных функций полезности, в которых каждый агент сообщает значение для наборов, содержащих не более k предметов, а значения более крупных наборов определяются путем сложения и вычитания значений базовых наборов.

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

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

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

См. также

• Общее равновесие