Вычисление рыночного равновесия (также называемое вычислением конкурентного равновесия или вычислением клиринговых цен ) представляет собой вычислительную проблему на стыке экономики и информатики . Входом в эту проблему является рынок , состоящий из набора ресурсов и набора агентов . Существуют различные виды рынков, таких как рынок Фишер и рынок Эрроу-Дебре , с делимых или неделимых ресурсов. Требуемый выпуск - это конкурентное равновесие , состоящее из вектора цен.(цена для каждого ресурса) и распределение (пакет ресурсов для каждого агента), так что каждый агент получает наилучший возможный пакет (для него) с учетом бюджета, и рынок очищается (все ресурсы распределяются).
Вычисление рыночного равновесия интересно тем, что конкурентное равновесие всегда эффективно по Парето . Особый случай рынка Фишера, на котором все покупатели имеют равные доходы, особенно интересен, поскольку в этом случае конкурентное равновесие также не вызывает зависти . Следовательно, расчет рыночного равновесия - это способ найти справедливое и эффективное распределение.
Определения
Вход на рынок-равновесном-вычислений состоит из следующих ингредиентов: [1] : chap.5
- Набор из ресурсы с заранее оговоренными расходными материалами. Ресурсы могут быть делимыми (в этом случае их запас wlog нормализован к 1) или неделимым .
- Пучок представлен вектором, где количество ресурса . Когда ресурсы неделимы, все x j являются целыми числами; когда ресурсы делятся, x j могут быть произвольно действительными числами (обычно нормализованными до [0,1]).
- Набор из агенты . Для каждого агента существует отношение предпочтения перед связками, которое может быть представлено функцией полезности. Функция полезности агента обозначается .
- Первоначальный вклад для каждого агента.
- На рынке Фишера пожертвования - это бюджет.«бумажных денег» - денег, не имеющих ценности вне рынка и, следовательно, не участвующих в функции полезности. Поскольку агенты приходят только с деньгами, их часто называют покупателями .
- На рынке Эрроу – Дебре эндаумент представляет собой произвольный набор; в этой модели агенты могут быть как покупателями, так и продавцами.
Требуемый выход должен содержать следующие ингредиенты:
- Цена-вектор ; цена за каждый ресурс. Цена пакета - это сумма цен ресурсов в, поэтому цена пакета является .
- Распределение - расслоениедля каждого агента i .
Выходные данные должны удовлетворять следующим требованиям:
- Пакет должен быть доступным для i , т. е. его цена должна быть не выше цены капитала i-го агента .
- На рынке Фишера это означает, что .
- На рынке Эрроу-Дебре это означает, что .
- Пакет должен быть в наборе спроса на I :, определяемый как набор пакетов, максимизирующий полезность агента среди всех доступных пакетов (независимо от предложения), например, на рынке Фишера:
- Рынок очищается , т. Е. Все ресурсы распределяются. Соответствующие цены называются рыночными ценами .
Ценовые и распределение , удовлетворяющее эти требования, называются в конкурентное равновесии (CE) или рыночное равновесие ; цены также называются равновесными ценами или клиринговыми ценами .
Виды служебных функций
Вычисление рыночного равновесия изучалось при различных предположениях относительно функций полезности агентов.
- Вогнутость : наиболее общее предположение (сделанное Фишером, Эрроу и Дебре) состоит в том, что служебные программы агентов являются вогнутыми функциями , т. Е. Отображают убывающую отдачу .
- Однородность : в некоторых случаях предполагается, что коммунальные услуги являются однородными функциями . Это, в частности, касается коммунальных предприятий с постоянной эластичностью замещения .
- Разделимость : функция полезности называется разделимой, если полезность пакета является суммой полезностей отдельных ресурсов в пакете, т. Е..
- Кусочно-линейность - это частный случай разделимости, в котором функция полезности для каждого отдельного ресурса,, является кусочно-линейной функцией от x j.
- Линейность - это еще более частный случай, в котором функция полезности для каждого отдельного ресурса является линейной функцией . Это,, где являются константами.
Утилиты, которые являются кусочно-линейными и вогнутыми, часто называют ПЛК; если они также разделимы, то их называют SPLC.
Основные результаты
Примерные алгоритмы
Шарф [2] был первым, кто показал существование CE с помощью леммы Спернера (см. Рынок Фишера ). Он также дал алгоритм для вычисления приблизительного CE.
Меррилл [3] дал расширенный алгоритм для приближенного CE.
Какаде, Кирнс и Ортис [4] дали алгоритмы для приблизительного CE на обобщенном рынке Эрроу-Дебре, на котором агенты расположены на графе, а торговля может происходить только между соседними агентами. Они считали нелинейные коммунальные услуги.
Результаты твердости
В некоторых случаях вычисление приблизительного CE затруднительно для PPAD :
- Деванур и Каннан [5] доказали устойчивость к PPAD на рынке Эрроу-Дебре с утилитами Леонтьева - частным случаем утилит PLC.
- Чен, Дай, Ду и Тенг [6] доказали твердость PPAD на рынке Эрроу-Дебре с утилитами SPLC. Их доказательство показывает, что эта проблема рыночного равновесия не имеет FPTAS, если PPAD не находится в P.
- Чен и Тенг [7] доказали твердость PPAD на рынке Fisher с помощью служебных программ SPLC.
- Чаудхури, Гарг, МакГлафлин и Мета [8] доказали стойкость к PPAD на рынке Fisher с дефектами и линейными утилитами, даже при определенных условиях, гарантирующих существование CE.
Точные алгоритмы
Деванур, Пападимитриу, Сабери и Вазирани [9] дали алгоритм с полиномиальным временем для точного вычисления равновесия для рынков Фишера с линейными функциями полезности. В их алгоритме используется парадигма прямого и двойственного действия в расширенной настройке условий KKT и выпуклых программ. Их алгоритм слабо полиномиален: он решает проблемы с максимальным потоком , поэтому он работает вовремя, где u max и B max - максимальная полезность и бюджет соответственно.
Орлин [10] дал улучшенный алгоритм для модели рынка Фишера с линейными полезностями, работающими во времени.. Затем он улучшил свой алгоритм, чтобы он работал за строго полиномиальное время :.
Деванур и Каннан [5] дали алгоритмы для рынков Эрроу-Дебре с вогнутыми функциями полезности, где все ресурсы являются товарами (полезности положительны):
- Когда утилиты являются SPLC и либо n, либо m является константой, их алгоритм полиномиален по другому параметру. Этот метод заключается в разбиении пространства возможных цен на ячейки с использованием постоянного количества гиперплоскостей, так что в каждой ячейке известна предельная предельная полезность каждого покупателя (когда и n, и m являются переменными, оставалось открытым, существует ли алгоритм полифайма) .
- Когда утилиты являются ПЛК (не обязательно разделяемыми) и m является постоянным, их алгоритм полиномиален от n . Когда и m, и n являются переменными, поиск CE затруднен для PPAD даже для утилит Леонтьева , которые являются частным случаем утилит PLC (когда n постоянное, но m переменное, оставалось открытым, существует ли алгоритм polytime).
Коденотти, МакКьюн, Пенумача и Варадараджан [11] представили алгоритм для маркеров Эрроу-Дебре с утилитами CES, где эластичность замещения составляет не менее 1/2.
Бад и смешанная манна
Богомольная и Мулен, Сандомирский и Яновская изучали существование и свойства CE на рынке Фишера с плохими товарами (товарами с отрицательной полезностью) [12] и смесью товаров и плохих товаров. [13] В отличие от настройки с товарами, когда ресурсы плохие, CE не решает никаких задач выпуклой оптимизации даже с линейными полезностями. Распределения CE соответствуют локальным минимумам, локальным максимумам и седловым точкам продукта полезностей на границе Парето набора допустимых полезностей. Правило СЕ становится многозначным. Эта работа привела к нескольким работам по алгоритмам поиска CE на таких рынках:
- Бранзей и Сандомирский [14] дали алгоритм для поиска всех CE на рынке Фишера с плохими доходами и линейными полезностями. Их алгоритм работает за сильно полиномиальное время, если фиксировано либо n, либо m . Их подход объединяет три идеи: все графики потребления распределения PO могут быть перечислены за полиномиальное время; для данного графика потребления кандидат в CE может быть построен с помощью явной формулы; и данное распределение может быть проверено на предмет соответствия CE с использованием вычисления максимального потока .
- Гарг и МакГлафлин [15] представили алгоритм для вычисления всех CE на рынке Фишера со смешанными маннами и линейными полезностями. Их алгоритм работает за полиномиальное время, если фиксировано либо n, либо m .
- Чаудхури, Гарг, МакГлафлин и Мета [16] представили алгоритм для вычисления одного CE на рынке Фишера со смешанными утилитами manna и SPLC. Их алгоритм похож на симплекс и основан на схеме Лемке . Хотя его время выполнения в наихудшем случае не является полиномиальным (проблема связана с PPAD-сложностью даже с товарами [7] ), оно работает быстро на случайных экземплярах. Это также доказывает, что проблема находится в PPAD, решения рациональные, а количество решений нечетное. Их алгоритм работает за полиномиальное время в особом случае, когда все полезности отрицательны.
Если и n, и m являются переменными, проблема становится вычислительно сложной:
- Чаудхури, Гарг, МакГлафлин и Мета [8] : Теория 3 показывает, что на рынке Фишера с плохими качествами и линейными полезностями NP-сложно решить, существует ли CE. Такая же трудность сохраняется даже для нахождения (11/12 + δ) -CE для любого δ> 0 и даже при равных доходах. Они также доказывают достаточное условие, основанное на связности графа, для существования CE. При этом условии CE всегда существует, но найти его с помощью PPAD сложно. [8] : Thm.5
Основные техники
Взрыв за доллар
Когда полезности линейны, отдача агента i (также называемая BPB или полезность на монету ) определяется как полезность i, деленная на уплаченную цену. BPB отдельного ресурса; общий BPB составляет.
Ключевое наблюдение для поиска CE на рынке Fisher с линейными полезностями заключается в том, что в любом CE и для любого агента i : [1]
- Общий BPB немного больше, чем BPB от любого отдельного ресурса, .
- Агент i потребляет только ресурсы с максимально возможным BPB, т. Е..
Предположим, что каждый продукт есть потенциальный покупатель - покупатель с участием . Тогда из приведенных выше неравенств следует, что, т.е. все цены положительные.
Разложение клеток
Ячеечная декомпозиция [5] - это процесс разбиения пространства возможных цен.на маленькие «клетки» либо гиперплоскостями, либо, в более общем смысле, полиномиальными поверхностями. Ячейка определяется указанием, на какой стороне каждой из этих поверхностей она лежит (в случае полиномиальных поверхностей ячейки также известны как полуалгебраические множества ). Для каждой ячейки мы либо находим вектор цен клиринга рынка (т. Е. Цену в той ячейке, для которой существует распределение клиринга рынка), либо проверяем, что эта ячейка не содержит вектор цен клиринга рынка. Задача состоит в том, чтобы найти декомпозицию со следующими свойствами:
- Общее количество ячеек полиномиально от размера ввода. При этом используется тот факт, что любой набор из k гиперплоскостей в разделяет пространство на клетки. [5] : Thm.2 Это полиномиально, если m фиксировано. Более того, любой набор из k полиномиальных поверхностей степени не выше d разбивает пространство нанепустые ячейки, и они могут быть пронумерованы во времени линейно по размеру вывода. [17]
- Нахождение вектора цены клиринга рынка в каждой ячейке может быть выполнено за полиномиальное время, например, с помощью линейного программирования.
Выпуклая оптимизация: однородные коммунальные услуги
Если полезности всех агентов являются однородными функциями , то условия равновесия в модели Фишера могут быть записаны как решения выпуклой программы оптимизации, называемой выпуклой программой Эйзенберга-Гейла . [18] Эта программа находит распределение, которое максимизирует средневзвешенное геометрическое значение коммунальных услуг покупателей, где веса определяются бюджетами. Эквивалентно, он максимизирует взвешенное среднее арифметическое логарифмов коммунальных услуг:
- Максимизировать
- При условии:
- Неотрицательные количества : для каждого покупателя и продукт :
- Достаточно расходных материалов : для каждого продукта :
(поскольку запасы нормированы на 1).
Эта оптимизационная задача может быть решена с помощью условий Каруша – Куна – Таккера (KKT). Эти условия вводят множители Лагранжа, которые можно интерпретировать как цены ,. При каждом распределении, которое максимизирует программу Айзенберга-Гейла, каждый покупатель получает требуемый пакет. То есть решение программы Айзенберга-Гейла представляет собой рыночное равновесие. [1] : 141–142
Алгоритм Вазирани: линейные утилиты, слабо полиномиальное время
Частный случай однородных коммунальных услуг - это когда все покупатели имеют линейные функции полезности . Мы предполагаем, что у каждого ресурса есть потенциальный покупатель - покупатель, который получает положительную полезность от этого ресурса. Согласно этому предположению, клиринговые цены существуют и уникальны. Доказательство основано на программе Айзенберга-Гейла. Из условий ККТ следует, что оптимальные решения (распределения и цены ) удовлетворяют следующим неравенствам:
- Все цены неотрицательны: .
- Если у товара положительная цена, то весь его запас исчерпан: .
- Общий BPB немного больше, чем BPB от любого отдельного ресурса, .
- Агент i потребляет только ресурсы с максимально возможным BPB, т. Е..
Предположим, что каждый продукт есть потенциальный покупатель - покупатель с участием . Тогда из неравенства 3 следует, что, т.е. все цены положительные. Тогда неравенство 2 означает, что все запасы исчерпаны. Неравенство 4 означает, что бюджеты всех покупателей исчерпаны. Т.е. рынок очищается. Поскольку логарифмическая функция является строго вогнутой функцией , при наличии более одного равновесного распределения полезность, полученная каждым покупателем в обоих распределениях, должна быть одинаковой (снижение полезности покупателя не может быть компенсировано увеличением полезности. другого покупателя). Это вместе с неравенством 4 означает, что цены уникальны. [1] : 107
Вазирани [1] : 109–121 представил алгоритм поиска равновесных цен и распределения на линейном рынке Фишера. Алгоритм основан на условии 4 выше. Условие подразумевает, что в состоянии равновесия каждый покупатель покупает только те продукты, которые дают ему максимальную BPB. Скажем, покупателю "нравится" товар, если этот товар дает ему максимальную цену за баррель в текущих ценах. Учитывая вектор цен, постройте сеть потоков, в которой пропускная способность каждого ребра представляет собой общую сумму денег, "текущих" через это ребро. Сеть выглядит следующим образом:
- Есть исходный узел, s .
- Для каждого продукта есть узел; есть ребро от s к каждому продукту j , с емкостью(это максимальная сумма денег, которую можно потратить на продукт j , поскольку предложение нормировано на 1).
- На каждого покупателя есть узел; есть преимущество от продукта к покупателю с неограниченной емкостью, если покупателю нравится продукт (в текущих ценах).
- Имеется целевой узел t ; есть преимущество от каждого покупателя i до t , с пропускной способностью(максимальный расход i ).
Вектор цен p является вектором равновесных цен тогда и только тогда, когда два сокращения ({s}, V \ {s}) и (V \ {t}, {t}) являются минимальными сокращениями . Следовательно, вектор равновесной цены может быть найден по следующей схеме:
- Начните с очень низких цен, которые гарантированно будут ниже равновесных цен; в этих ценах у покупателей остается некоторый бюджет (т. е. максимальный поток не достигает емкости узлов в t ).
- Постоянно повышайте цены и соответствующим образом обновляйте потоковую сеть, пока не будут исчерпаны все бюджеты.
Есть алгоритм, решающий эту задачу за слабо полиномиальное время.
Смотрите также
- Эффективное деление без зависти
- Эффективное приблизительно справедливое распределение предметов
Рекомендации
- ^ a b c d e Вазирани, Виджай В .; Нисан, Ноам ; Roughgarden, Тим ; Тардос, Ева (2007). "Глава 5: Комбинаторные алгоритмы рыночного равновесия / Виджай В. Вазирани". Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.
- ^ Шарф, Герберт Э. (1967). «О вычислении равновесных цен» . Цитировать журнал требует
|journal=
( помощь ) - ^ ОН Меррилл (1972). Приложения и расширения алгоритма, который вычисляет неподвижные точки определенной верхней полунепрерывной точки для установки отображений. Кандидатская диссертация.
- ^ Какаде, Шам М .; Кирнс, Майкл; Ортис, Луис Э. (2004). Шоу-Тейлор, Джон; Певец, Йорам (ред.). «Графическая экономика» . Теория обучения . Конспект лекций по информатике. Берлин, Гейдельберг: Springer. 3120 : 17–32. DOI : 10.1007 / 978-3-540-27819-1_2 . ISBN 978-3-540-27819-1.
- ^ а б в г Деванур, Северная Каролина; Каннан, Р. (2008-10-01). «Рыночные равновесия в полиномиальное время для фиксированного количества товаров или агентов» . 2008 49-й ежегодный симпозиум IEEE по основам информатики : 45–53. DOI : 10.1109 / FOCS.2008.30 . ISBN 978-0-7695-3436-7. S2CID 13992175 .
- ^ Чен, X .; Dai, D .; Du, Y .; Тенг, С. (01.10.2009). «Урегулирование сложности равновесия Эрроу-Дебре на рынках с аддитивно разделяемыми утилитами» . 2009 50-й ежегодный симпозиум IEEE по основам информатики : 273–282. arXiv : 0904.0644 . DOI : 10.1109 / FOCS.2009.29 . ISBN 978-1-4244-5116-6. S2CID 580788 .
- ^ а б Чен, Си; Тэн, Шан-Хуа (2009). Дун, Инфэй; Ду, Дин-Чжу; Ибарра, Оскар (ред.). «Тратить не легче, чем торговать: о вычислительной эквивалентности равновесий Фишера и Эрроу-Дебре» . Алгоритмы и вычисления . Конспект лекций по информатике. Берлин, Гейдельберг: Springer. 5878 : 647–656. arXiv : 0907.4130 . DOI : 10.1007 / 978-3-642-10631-6_66 . ISBN 978-3-642-10631-6. S2CID 7817966 .
- ^ а б в Чаудхури, Бхаскар Рэй; Гарг, Джугал; МакГлафлин, Питер; Мехта, Рута (01.08.2020). «Разделить неудач сложнее, чем разделить блага: о сложности справедливого и эффективного разделения дел». arXiv : 2008.00285 [ cs.GT ].
- ^ Деванур, Нихил Р .; Papadimitriou, Christos H .; Сабери, Амин; Вазирани, Виджай В. (2008-11-05). «Рыночное равновесие с помощью первично-двойственного алгоритма для выпуклой программы» . Журнал ACM . 55 (5): 22: 1–22: 18. DOI : 10.1145 / 1411509.1411512 . ISSN 0004-5411 . S2CID 11836728 .
- ^ Орлин, Джеймс Б. (05.06.2010). «Усовершенствованные алгоритмы расчета клиринговых цен на рынке Fisher: расчет клиринговых цен на рынке Fisher» . Материалы сорок второго симпозиума ACM по теории вычислений . СТОК '10. Кембридж, Массачусетс, США: Ассоциация вычислительной техники: 291–300. DOI : 10.1145 / 1806689.1806731 . ЛВП : 1721,1 / 68009 . ISBN 978-1-4503-0050-6. S2CID 8235905 .
- ^ Коденотти, Бруно; МакКьюн, Бентон; Пенумача, Шрирам; Варадараджан, Кастури (2005). Саруккай, Сундар; Сен, Сандип (ред.). «Рыночное равновесие для стран ЕЭП с биржевой экономикой: существование, множественность и расчет» . FSTTCS 2005: Основы программных технологий и теоретической информатики . Конспект лекций по информатике. Берлин, Гейдельберг: Springer. 3821 : 505–516. DOI : 10.1007 / 11590156_41 . ISBN 978-3-540-32419-5.
- ^ Богомольная, Анна; Мулен, Эрве; Сандомирский, Федор; Яновская, Елена (01.03.2019). «Разделение бэдов под аддитивные утилиты» . Социальный выбор и благосостояние . 52 (3): 395–417. DOI : 10.1007 / s00355-018-1157-х . ISSN 1432-217X .
- ^ Богомольная, Анна; Мулен, Эрве; Сандомирский, Федор; Яновская, Елена (2017). «Соревновательный дивизион смешанной манны» . Econometrica . 85 (6): 1847–1871. arXiv : 1702.00616 . DOI : 10.3982 / ECTA14564 . ISSN 1468-0262 . S2CID 17081755 .
- ^ Brânzei, Simina; Сандомирский, Федор (2019-07-03). «Алгоритмы конкурсного разделения дел». arXiv : 1907.01766 [ cs.GT ].
- ^ Гарг, Джугал; МакГлафлин, Питер (05.05.2020). «Вычисление конкурентного равновесия со смешанной манной» . Материалы 19-й Международной конференции по автономным агентам и мультиагентным системам . AAMAS '20. Окленд, Новая Зеландия: Международный фонд автономных агентов и многоагентных систем: 420–428. ISBN 978-1-4503-7518-4.
- ^ Чаудхури, Бхаскар Рэй; Гарг, Джугал; МакГлафлин, Питер; Мехта, Рута (2021-01-01), «Конкурентное распределение смешанной манны» , Труды Симпозиума ACM-SIAM 2021 по дискретным алгоритмам (SODA) , Труды, Общество промышленной и прикладной математики, стр. 1405–1424, DOI : 10.1137 / 1.9781611976465.85 , ISBN 978-1-61197-646-5, дата обращения 06.03.2021
- ^ Басу, Саугата; Поллак, Ричард; Рой, Мари-Франсуаза (1998). Полость, Боб Ф .; Джонсон, Джереми Р. (ред.). «Новый алгоритм для поиска точки в каждой ячейке, определяемой семейством многочленов» . Исключение кванторов и цилиндрическая алгебраическая декомпозиция . Тексты и монографии по символическому вычислению. Вена: Springer: 341–350. DOI : 10.1007 / 978-3-7091-9459-1_17 . ISBN 978-3-7091-9459-1.
- ^ Айзенберг, Э. (1961). «Агрегирование служебных функций» . Наука управления . 7 (4): 337–350. DOI : 10.1287 / mnsc.7.4.337 .