Расчет рыночного равновесия
Экономическая вычислительная задача

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

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

Определения

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

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

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

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

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

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

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

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

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

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

Кусочно-линейные и вогнутые коммуникации часто называют PLC; если они также разделимы, то их называют SPLC.

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

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

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

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

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

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

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

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

  • Деванур и Каннан [6] доказали PPAD-устойчивость на рынке Эрроу-Дебре с коммунальными услугами Леонтьева — особым случаем коммунальных услуг PLC.
  • Чэнь, Дай, Ду и Тенг [7] доказали PPAD-жесткость на рынке Эрроу-Дебре с коммунальными услугами SPLC. Их доказательство показывает, что эта проблема рыночного равновесия не имеет FPTAS, если PPAD не находится в P.
  • Чэнь и Тэн [8] доказали устойчивость к PPAD на рынке Фишера с использованием утилит SPLC.
  • Чаудхури, Гарг, МакГлафлин и Мехта [9] доказали PPAD-твердость на биржевом рынке (рынке Эрроу-Дебре) с плохими и линейными полезностями, даже при определенном условии, которое гарантирует существование CE.

Точные алгоритмы

Деванур, Пападимитриу, Сабери и Вазирани [10] предложили полиномиальный алгоритм для точного вычисления равновесия для рынков Фишера с линейными функциями полезности. Их алгоритм использует парадигму первичной двойственности в расширенной настройке условий KKT и выпуклых программ. Их алгоритм является слабополиномиальным: он решает задачи максимального потока и, таким образом, работает за время , где u max и B max — максимальная полезность и бюджет соответственно. O ( ( n + m ) 5 log ⁡ ( u max ) + ( n + m ) 4 log ⁡ B max ) {\displaystyle 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 ) {\displaystyle O((n+m)^{8}\log(u_{\max })+(n+m)^{7}\log {B_{\max }})}

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

Деванур и Каннан [6] предложили алгоритмы для рынков Эрроу-Дебре с вогнутыми функциями полезности, где все ресурсы являются товарами (полезности положительны):

  • Когда утилиты — SPLC, а либо n , либо m — константа, их алгоритм полиномиален по другому параметру. Методика заключается в разложении пространства возможных цен на ячейки с использованием постоянного числа гиперплоскостей, так что в каждой ячейке пороговая предельная полезность каждого покупателя известна (когда и n , и m являются переменными, вопрос о существовании поливременного алгоритма оставался открытым).
  • Когда утилиты являются PLC (не обязательно разделимыми) и m является константой, их алгоритм является полиномиальным по n . Когда и m, и n являются переменными, нахождение CE является PPAD-трудным даже для утилит Леонтьева , которые являются особым случаем утилит PLC (когда n является константой, а m является переменной, вопрос о существовании полиномиального алгоритма оставался открытым).

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

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

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

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

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

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

Основные приемы

Банг за доллар

Когда полезности линейны, bang-per-buck агента i (также называемый BPB или полезность-за-монету ) определяется как полезность i , деленная на уплаченную цену. BPB одного ресурса составляет ; общий BPB составляет . b p b i , j := u i , j p j {\displaystyle bpb_{i,j}:={\frac {u_{i,j}}{p_{j}}}} b p b i , t o t a l := ∑ j = 1 m u i , j ⋅ x i , j B i {\displaystyle bpb_{i,total}:={\frac {\sum _{j=1}^{m}u_{i,j}\cdot x_{i,j}}{B_{i}}}}

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

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

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

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

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

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

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

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

Увеличить ∑ i = 1 n ( B i ⋅ log ⁡ ( u i ) ) {\displaystyle \sum _{i=1}^{n}\left(B_{i}\cdot \log {(u_{i})}\right)}
При условии:
Неотрицательные количества : Для каждого покупателя и продукта : i {\displaystyle i} j {\displaystyle j} x i , j ≥ 0 {\displaystyle x_{i,j}\geq 0}
Достаточные запасы : Для каждого продукта : j {\displaystyle j} ∑ i = 1 n x i , j ≤ 1 {\displaystyle \sum _{i=1}^{n}x_{i,j}\leq 1}

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

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

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

Частным случаем однородной полезности является случай, когда все покупатели имеют линейные функции полезности. Мы предполагаем, что у каждого ресурса есть потенциальный покупатель — покупатель, который извлекает положительную полезность из этого ресурса. При этом предположении рыночные цены клиринга существуют и являются уникальными. Доказательство основано на программе Эйзенберга-Гейла. Условия KKT подразумевают, что оптимальные решения (распределения и цены ) удовлетворяют следующим неравенствам: x i , j {\displaystyle x_{i,j}} p j {\displaystyle p_{j}}

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

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

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

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

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

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

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

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

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

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

Ссылки

  1. ^ abcde Вазирани, Виджай В .; Нисан, Ноам ; Рафгарден, Тим ; Тардос, Эва (2007). "Глава 5: Комбинаторные алгоритмы для рыночных равновесий / Виджай В. Вазирани". Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Cambridge University Press. ISBN 0-521-87282-0.
  2. ^ Скарф, Герберт Э. (1967). «О вычислении равновесных цен». Дискуссионные доклады Фонда Коулза .
  3. ^ OH Merrill (1972). Приложения и расширения алгоритма, вычисляющего неподвижные точки некоторых полунепрерывных сверху точек для множеств отображений. Кандидатская диссертация.
  4. ^ Какаде, Шам М.; Кернс, Майкл; Ортис, Луис Э. (2004). Шоу-Тейлор, Джон; Сингер, Йорам (ред.). «Графическая экономика». Теория обучения . Конспект лекций по информатике. 3120. Берлин, Гейдельберг: Springer: 17–32. doi :10.1007/978-3-540-27819-1_2. ISBN 978-3-540-27819-1.
  5. ^ Ньюман, DJ; Примак, ME (1992-12-01). "Сложность методов описанного и вписанного эллипсоида для решения равновесных экономических моделей". Прикладная математика и вычисления . 52 (2): 223–231. doi :10.1016/0096-3003(92)90079-G. ISSN  0096-3003.
  6. ^ abcd Деванур, NR; Каннан, Р. (2008-10-01). "Рыночное равновесие за полиномиальное время для фиксированного количества товаров или агентов". 2008 49-й ежегодный симпозиум IEEE по основам компьютерной науки . стр. 45–53. doi :10.1109/FOCS.2008.30. ISBN 978-0-7695-3436-7. S2CID  13992175.
  7. ^ Чен, X.; Дай, Д.; Ду, И.; Тенг, С. (2009-10-01). «Урегулирование сложности равновесий Эрроу-Дебре на рынках с аддитивно разделяемыми полезностями». 2009 50-й ежегодный симпозиум IEEE по основам компьютерной науки . стр. 273–282. arXiv : 0904.0644 . doi :10.1109/FOCS.2009.29. ISBN 978-1-4244-5116-6. S2CID  580788.
  8. ^ ab Chen, Xi; Teng, Shang-Hua (2009). Dong, Yingfei; Du, Ding-Zhu; Ibarra, Oscar (ред.). «Расходы не легче торговли: о вычислительной эквивалентности равновесий Фишера и Эрроу-Дебре». Алгоритмы и вычисления . Конспект лекций по информатике. 5878. Берлин, Гейдельберг: Springer: 647–656. arXiv : 0907.4130 . doi :10.1007/978-3-642-10631-6_66. ISBN 978-3-642-10631-6. S2CID  7817966.
  9. ^ abc Чаудхури, Бхаскар Рэй; Гарг, Джугал; МакГлафлин, Питер; Мехта, Рута (01.08.2020). «Разделить плохое сложнее, чем разделить хорошее: о сложности справедливого и эффективного разделения обязанностей». arXiv : 2008.00285 [cs.GT].
  10. ^ Деванур, Нихил Р.; Пападимитриу, Христос Х.; Сабери, Амин; Вазирани, Виджай В. (5 ноября 2008 г.). «Рыночное равновесие с помощью примитивно-двойственного алгоритма для выпуклой программы». Журнал АКМ . 55 (5): 22:1–22:18. дои : 10.1145/1411509.1411512. ISSN  0004-5411. S2CID  11836728.
  11. ^ Орлин, Джеймс Б. (2010-06-05). «Улучшенные алгоритмы для вычисления цен на клиринговом рынке рыболовства». Труды сорок второго симпозиума ACM по теории вычислений . STOC '10. Кембридж, Массачусетс, США: Ассоциация вычислительной техники. стр. 291–300. doi :10.1145/1806689.1806731. hdl : 1721.1/68009 . ISBN 978-1-4503-0050-6. S2CID  8235905.
  12. ^ Коденотти, Бруно; Маккьюн, Бентон; Пенумача, Шрирам; Варадараджан, Кастури (2005). Саруккай, Сундар; Сен, Сандип (ред.). "Рыночное равновесие для экономик обмена CES: существование, множественность и вычисления". FSTTCS 2005: Основы технологий программного обеспечения и теоретической информатики . Конспект лекций по информатике. 3821. Берлин, Гейдельберг: Springer: 505–516. doi :10.1007/11590156_41. ISBN 978-3-540-32419-5.
  13. ^ Богомольная, Анна; Мулен, Эрве; Сандомирский, Федор; Яновская, Елена (2019-03-01). «Разделение плохих вещей при аддитивной полезности». Social Choice and Welfare . 52 (3): 395–417. doi : 10.1007/s00355-018-1157-x . ISSN  1432-217X.
  14. ^ Богомольная, Анна; Мулен, Эрве; Сандомирский, Федор; Яновская, Елена (2017). «Конкурентное разделение смешанной манны». Econometrica . 85 (6): 1847–1871. arXiv : 1702.00616 . doi : 10.3982/ECTA14564. ISSN  1468-0262. S2CID  17081755.
  15. ^ Брынзей, Симина; Сандомирский, Федор (03.07.2019). «Алгоритмы конкурентного разделения обязанностей». arXiv : 1907.01766 [cs.GT].
  16. ^ Гарг, Джугал; МакГлафлин, Питер (2020-05-05). «Вычисление конкурентных равновесий со смешанной манной». Труды 19-й Международной конференции по автономным агентам и многоагентным системам . AAMAS '20. Окленд, Новая Зеландия: Международный фонд автономных агентов и многоагентных систем: 420–428. ISBN 978-1-4503-7518-4.
  17. ^ Чаудхури, Бхаскар Рэй; Гарг, Джугал; МакГлафлин, Питер; Мехта, Рута (01 января 2021 г.), «Конкурентное распределение смешанной манны», Труды симпозиума ACM-SIAM 2021 года по дискретным алгоритмам (SODA) , Труды Общества промышленной и прикладной математики, стр. 1405–1424, arXiv : 2008.02753 , doi : 10.1137/1.9781611976465.85 , ISBN 978-1-61197-646-5
  18. ^ Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise (1998). Caviness, Bob F.; Johnson, Jeremy R. (ред.). "Новый алгоритм поиска точки в каждой ячейке, определенной семейством многочленов". Quantifier Elimination and Cylindrical Algebraic Decomposition . Texts and Monographs in Symbolic Computation. Vienna: Springer: 341–350. doi :10.1007/978-3-7091-9459-1_17. ISBN 978-3-7091-9459-1.
  19. ^ Eisenberg, E. (1961). «Агрегирование функций полезности». Management Science . 7 (4): 337–350. doi :10.1287/mnsc.7.4.337. Архивировано из оригинала 23 сентября 2017 г.
  20. ^ Гао, Юань; Пейсахович, Алекс; Кроер, Кристиан (2021). «Рыночное равновесие в Интернете с применением к справедливому разделению». Достижения в области нейронных систем обработки информации . 34. Curran Associates, Inc.: 27305–27318. arXiv : 2103.12936 .
Retrieved from "https://en.wikipedia.org/w/index.php?title=Market_equilibrium_computation&oldid=1213728542"