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

Вычисление рыночного равновесия (также называемое вычислением конкурентного равновесия или вычислением клиринговых цен ) — это вычислительная задача на стыке экономики и информатики . Входными данными для этой проблемы является рынок , состоящий из набора ресурсов и набора агентов . Существуют различные виды рынков, такие как рынок Фишера и рынок Эрроу-Дебре , с делимыми или неделимыми ресурсами. Требуемый выпуск — это конкурентное равновесие , состоящее из вектора цен (цены на каждый ресурс) и распределения (набора ресурсов для каждого агента), так что каждый агент получает наилучший возможный набор (для него) с учетом бюджет, и рынок очищается (все ресурсы распределяются).

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

Определения

Входные данные для расчета рыночного равновесия состоят из следующих ингредиентов:

1. Набор $m$ ресурсы с заранее указанными запасами. Ресурсы могут быть делимыми (в этом случае их запас нормализуется к 1) или неделимыми .
   • Пучок вектором представлен $\mathbf {x} =x_{1},\dots ,x_{m}$, где $x_{j}$ это количество ресурса $j$. Когда ресурсы неделимы, все x _j являются целыми числами; когда ресурсы делятся, x _j может быть сколь угодно действительным числом (обычно нормализованным к [0,1]).
2. Набор $n$ агенты . Для каждого агента существует отношение предпочтения по отношению к пакетам, которое можно представить функцией полезности. Функция полезности агента $i$ обозначается $u_{i}$.
3. Начальный вклад для каждого агента.
   • На рынке Фишера вклад представляет собой бюджет. $B_{i}$ «бумажных денег» — денег, которые не имеют стоимости вне рынка и, следовательно, не входят в функцию полезности. Поскольку агенты приходят только с деньгами, их часто называют покупателями .
   • На рынке Эрроу-Дебре запас представляет собой произвольный набор $\mathbf {e} ^{i}$; в этой модели агенты могут быть как покупателями, так и продавцами.

Требуемый результат должен содержать следующие ингредиенты:

1. Ценовой вектор $\mathbf {p} =p_{1},\dots ,p_{m}$; цена за каждый ресурс. Цена пакета представляет собой сумму цен ресурсов в нем, поэтому цена пакета $\mathbf {x}$ является $\mathbf {p} \cdot \mathbf {x} =\sum _{j=1}^{m}p_{j}\cdot x_{j}$.
2. Распределение связка – $\mathbf {x} ^{i}$ для каждого агента i .

Выходные данные должны удовлетворять следующим требованиям:

1. Пакет $\mathbf {x} ^{i}$ должна быть доступной для i , то есть ее цена не должна превышать цену агента i вклада .
   • На рынке Фишера это означает, что $\mathbf {p} \cdot \mathbf {x} ^{i}\leq B_{i}$.
   • На рынке Эрроу-Дебре это означает, что $\mathbf {p} \cdot \mathbf {x} ^{i}\leq \mathbf {p} \cdot \mathbf {e} ^{i}$.
2. Пакет $\mathbf {x} ^{i}$ должно быть в спроса наборе i : $\mathbf {x} ^{i}\in {\text{Demand}}_{i}(\mathbf {p} )$, определяемый как набор наборов, максимизирующих полезность агента среди всех доступных наборов (независимо от предложения), например, на рынке Фишера: ${\text{Demand}}_{i}(\mathbf {p} ):=\arg \max _{\mathbf {p} \mathbf {x} \leq B_{i}}u_{i}(\mathbf {x} )$
3. Рынок очищается , т. е. все ресурсы распределяются. Соответствующие цены называются рыночными ценами .

Цена и распределение, удовлетворяющие этим требованиям, называются конкурентным равновесием (CE) или рыночным равновесием ; цены также называются равновесными ценами или клиринговыми ценами .

Виды полезных функций

Вычисление рыночного равновесия изучалось при различных предположениях относительно функций полезности агентов.

• Вогнутость : наиболее общее предположение (сделанное Фишером и Эрроу и Дебре) состоит в том, что полезности агентов представляют собой вогнутые функции , т. е. демонстрируют убывающую доходность .
• Однородность : в некоторых случаях предполагается, что полезности являются однородными функциями . Сюда входят, в частности, полезности с постоянной эластичностью замещения .
• Сепарабельность : функция полезности называется разделимой, если полезность пакета представляет собой сумму полезностей отдельных ресурсов в пакете, т. е. $u_{i}(\mathbf {x} )=\sum _{j=1}^{m}u_{i,j}(x_{j})$.
• Кусочная линейность — это частный случай разделимости, при котором функция полезности для каждого отдельного ресурса $u_{i,j}(x_{j})$, является кусочно-линейной функцией от x j.
• Линейность — это еще более частный случай, когда функция полезности для каждого отдельного ресурса является линейной функцией . То есть, $u_{i}(\mathbf {x} )=\sum _{j=1}^{m}u_{i,j}\cdot x_{j}$, где $u_{i,j}$ являются константами.

Кусочно-линейные и вогнутые утилиты часто называют ПЛК; если они еще и разделимые, то их называют СПЛК.

Основные результаты

Приблизительные алгоритмы

Шарф был первым, кто показал существование ВЭ, используя лемму Спернера (см. Рынок Фишера ). Он также дал алгоритм вычисления приблизительного CE.

Меррилл дал расширенный алгоритм приблизительного CE.

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

Ньюман и Примак изучили два варианта эллипсоидного метода поиска CE на рынке Эрроу-Дебре с линейными полезностями. Они доказывают, что метод вписанного эллипсоида более эффективен в вычислительном отношении, чем метод описанного эллипсоида.

Результаты твердости

В некоторых случаях вычисление приблизительного CE является PPAD-сложным :

• Деванур и Каннан доказала устойчивость PPAD на рынке Эрроу-Дебре с помощью утилит Леонтьева - особого случая утилит PLC.
• Чен, Дай, Ду и Тенг доказал PPAD-стойкость на рынке Эрроу-Дебре с помощью утилит SPLC. Их доказательство показывает, что эта проблема рыночного равновесия не имеет FPTAS, если PPAD не находится в P.
• Чен и Тенг доказал PPAD-стойкость на рынке Fisher с помощью утилит SPLC.
• Чаудхури, Гарг, МакГлафлин и Мехта доказала PPAD-твёрдость на рынке Exchange (Arrow-Debreu) ​​с бэдами и линейными утилитами, даже при определённом условии, гарантирующем существование 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 и либо n, либо m является константой, их алгоритм является полиномиальным по другому параметру. Этот метод заключается в разложении пространства возможных цен на ячейки с использованием постоянного числа гиперплоскостей, так что в каждой ячейке порог предельной полезности известен каждого покупателя (когда и n , и m являются переменными, остается открытым вопрос, существует ли политаймовый алгоритм). .
• Когда коммунальные услуги представляют собой ПЛК (не обязательно разделимые) и m постоянно, их алгоритм является полиномиальным по n . Когда и m, и n являются переменными, найти CE сложно с помощью PPAD даже для утилит Леонтьева , которые являются частным случаем утилит PLC (когда n является постоянным, но m является переменным, вопрос о существовании политаймового алгоритма оставался открытым).

Коденотти, МакКьюн, Пенуматча и Варадараджан дал алгоритм маркировки Эрроу-Дебре с утилитами CES , где эластичность замещения не менее 1/2.

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

Богомольная, Мулен, Сандомирский и Яновская изучали существование и свойства СЕ на рынке Фишера с бадами (предметами с отрицательной полезностью). и со смесью добра и зла. В отличие от ситуации с товарами, когда ресурсы плохие, 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-трудно.

Ручные техники

Экономия

Когда полезности линейны, прибыль агента i (также называемая BPB или полезность на монету ) определяется как полезность i, деленная на уплаченную цену. BPB одного ресурса равен $bpb_{i,j}:={\frac {u_{i,j}}{p_{j}}}$; общий BPB составляет $bpb_{i,total}:={\frac {\sum _{j=1}^{m}u_{i,j}\cdot x_{i,j}}{B_{i}}}$.

Ключевое наблюдение для поиска CE на рынке Фишера с линейными полезностями состоит в том, что в любом CE и для любого агента i :

• Общий BPB немного больше, чем BPB любого отдельного ресурса. $\forall j:bpb_{i,j}\leq bpb_{i,total}$.
• Агент i потребляет только ресурсы с максимально возможным BPB, т.е. $\forall j:x_{i,j}>0\implies bpb_{i,j}=bpb_{i,total}$.

Предположим, что каждый продукт $j$ есть потенциальный покупатель - покупатель $i$ с $u_{i,j}>0$. Тогда из приведенных выше неравенств следует, что $p_{j}>0$, т. е. все цены положительны.

Разложение клеток

Разложение клеток это процесс разделения пространства возможных цен $\mathbb {R} _{+}^{m}$ на небольшие «ячейки» либо гиперплоскостями , либо, в более общем смысле, полиномиальными поверхностями. Ячейка определяется путем указания, на какой стороне каждой из этих поверхностей она лежит (в случае полиномиальных поверхностей ячейки также известны как полуалгебраические множества ). Для каждой ячейки мы либо находим вектор равновесной рыночной цены (т. е. цену в этой ячейке, для которой существует равновесное распределение), либо проверяем, что ячейка не содержит вектор равновесной рыночной цены. Задача состоит в том, чтобы найти разложение со следующими свойствами:

• Общее количество ячеек полиномиально зависит от размера входных данных. При этом используется тот факт, что любой набор из k гиперплоскостей в $\mathbb {R} _{+}^{m}$ делит пространство на $O(k^{m})$ клетки. Это полиномиально, если m фиксировано. Более того, любой набор k полиномиальных поверхностей степени не выше d разбивает пространство на $O(k^{m+1}\cdot d^{O(m)})$ непустые ячейки, и их можно перечислять во времени, линейном по выходному размеру.
• Нахождение ценового вектора, обеспечивающего клиринг рынка, в каждой ячейке можно выполнить за полиномиальное время, например, с помощью линейного программирования.

Выпуклая оптимизация: однородные утилиты

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

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

С учетом:

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

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

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

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

Алгоритм Вазирани: линейные полезности, слабо полиномиальное время

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

1. Все цены неотрицательны: $p_{j}\geq 0$.
2. Если товар имеет положительную цену, то весь его запас исчерпан: $p_{j}>0\implies \sum _{i=1}^{n}x_{i,j}=1$.
3. Общий BPB немного больше, чем BPB любого отдельного ресурса. $\forall j:bpb_{i,j}\leq bpb_{i,total}$.
4. Агент i потребляет только ресурсы с максимально возможным BPB, т.е. $\forall j:x_{i,j}>0\implies bpb_{i,j}=bpb_{i,total}$.

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

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

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

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

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

Существует алгоритм, решающий эту задачу за слабо полиномиальное время.

Онлайн-вычисление

Недавно Гао, Пейсахович и Кроер представил алгоритм онлайн-расчета рыночного равновесия.

См. также

• Эффективное разделение без зависти
• Эффективное и примерно справедливое распределение товаров