Рынок Fisher

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

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

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

Каждый продукт $j\; \{\backslash \; displaystyle\; j\}$имеет цену $p\; j\; \{\backslash \; displaystyle\; p\_\; \{j\}\}$; цены определяются методами, которые мы описываем ниже. Цена пакета товаров - это сумма цен товаров в пакете. Пакет представлен вектором $x\; =\; x\; 1,\dots ,\; xm\; \{\backslash \; displaystyle\; x\; =\; x\_\; \{1\},\; \backslash \; dots,\; x\_\; \{m\}\}$, где $xj\; \{\backslash \; displaystyle\; x\_\; \{j\}\}$- количество товара $j\; \{\backslash \; displaystyle\; j\}$. Таким образом, цена пакета $x\; \{\backslash \; displaystyle\; x\}$равна $p\; (x)\; =\; \sum \; j\; =\; 1\; mpj\; \cdot \; xj\; \{\backslash \; displaystyle\; p\; (x)\; =\; \backslash \; sum\; \_\; \{j\; =\; 1\}\; ^\; \{m\}\; p\_\; \{j\}\; \backslash \; cdot\; x\_\; \{j\}\}$.

Пакет доступен для покупателя, если его цена не превышает бюджета покупателя. То есть, набор $x\; \{\backslash \; displaystyle\; x\}$доступен покупателю $i\; \{\backslash \; displaystyle\; i\}$, если $p\; (x)\; \le \; B\; i\; \{\; \backslash \; displaystyle\; p\; (x)\; \backslash \; leq\; B\_\; \{i\}\}$.

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

$Спрос\; i\; (p):\; =\; arg\; \; max\; p\; (x)\; \le \; B\; iui\; (x)\; \{\backslash \; displaystyle\; \{\backslash \; text\; \{Demand\}\}\; \_\; \{i\}\; (p):\; =\; \backslash \; arg\; \backslash \; max\; \_\; \{p\; (x)\; \backslash \; leq\; B\_\; \{i\}\}\; u\_\; \{i\}\; (x)\}$.

A конкурентное равновесие (CE) - вектор цен $p\; 1,\dots ,\; pm\; \{\backslash \; displaystyle\; p\_\; \{1\},\; \backslash \; dots,\; p\_\; \{m\}\}$, в котором можно выделить, каждый агент представляет собой набор из его набора спроса, так что общее распределение в точности равно предложению продуктов. Соответствующие цены называются рыночными ценами. Основная проблема при анализе рынков Fisher - это поиск CE.

• 1 Наличие конкурентного равновесия
• 2 Расчет конкурентного равновесия
  • 2.1 Однородные полезности
  • 2.2 Линейные полезности
  • 2.3 Слабо полиномиальные -временной алгоритм
• 3 Рынки Фишера с неделимыми объектами
• 4 См. также
• 5 Ссылки

Существование 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, это очень неэффективно с вычислительной точки зрения. Существуют гораздо более эффективные методы, которые обычно основаны на выпуклом программировании или линейном программировании.

Однородные утилиты

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

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

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

При условии:

неотрицательные количества: для каждого покупателя $i\; \{\backslash \; displaystyle\; i\; \}$и продукт $j\; \{\backslash \; displaystyle\; j\}$: $xi,\; j\; \ge \; 0\; \{\backslash \; displaystyle\; x\_\; \{i,\; j\}\; \backslash \; geq\; 0\}$

Достаточно расходных материалов: для каждого продукта $j\; \{\backslash \; displaystyle\; j\}$: $\sum \; i\; =\; 1\; nxi,\; j\; \le \; 1\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; x\_\; \{i,\; j\}\; \backslash \; leq\; 1\}$

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

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

Линейные полезности

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

$ui\; (x\; 1,\dots ,\; xj)\; =\; \sum \; j\; =\; 1\; mui,\; j\; \cdot \; xj\; \{\backslash \; displaystyle\; u\_\; \{i\}\; (x\_\; \{1\},\; \backslash \; dots,\; x\_\; \{j\})\; =\; \backslash \; sum\; \_\; \{j\; =\; 1\}\; ^\; \{m\}\; u\_\; \{i,\; j\}\; \backslash \; cdot\; x\_\; \{j\}\}$, где $ui,\; j\; \ge \; 0\; \{\backslash \; displaystyle\; u\_\; \{i,\; j\}\; \backslash \; geq\; 0\}$

Мы предполагаем, что у каждого продукта есть потенциальный покупатель - покупатель, который получает положительную пользу от этого продукта. Согласно этому предположению, клиринговые цены существуют и уникальны. Доказательство основано на программе Айзенберга-Гейла. Условия KKT подразумевают, что оптимальные решения (распределения $xi,\; j\; \{\backslash \; displaystyle\; x\_\; \{i,\; j\}\}$и цены $pj\; \{\backslash \; displaystyle\; p\_\; \{j\}\}$) удовлетворяют следующим неравенствам:

1. Все цены неотрицательны: $pj\; \ge \; 0\; \{\backslash \; displaystyle\; p\_\; \{j\}\; \backslash \; geq\; 0\}$.
2. Если у товара положительная цена, то все его предложение исчерпано: $pj>0\; ⟹\; \sum \; я\; =\; 1\; nxi,\; j\; =\; 1\; \{\backslash \; displaystyle\; p\_\; \{j\}>0\; \backslash \; подразумевает\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; x\_\; \{i,\; j\}\; =\; 1\; \}$.
3. Общая полезность на монету покупателя (общая полезность, разделенная на общий бюджет) немного больше чем его полезность на монету от каждого отдельного продукта: $\sum \; k\; =\; 1\; mui,\; k\; \cdot \; xi,\; k\; B\; i\; \ge \; ui,\; jpj\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{\backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{m\; \}\; u\_\; \{i,\; k\}\; \backslash \; cdot\; x\_\; \{i,\; k\}\}\; \{B\_\; \{i\}\}\}\; \backslash \; geq\; \{\backslash \; frac\; \{u\_\; \{i,\; j\}\}\; \{p\_\; \{j\}\}\}\}$
4. Если покупатель покупает положительное количество продукта, тогда его общая сумма ility-per-coin равняется его полезности на монету из этого продукта: $xi,\; j>0\; ⟹\; \sum \; k\; =\; 1\; mui,\; k\; \cdot \; xi,\; k\; B\; i\; =\; ui,\; jpj\; \{\backslash \; displaystyle\; x\_\; \{i,\; j\; \}>0\; \backslash \; подразумевает\; \{\backslash \; frac\; \{\backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{m\}\; u\_\; \{i,\; k\}\; \backslash \; cdot\; x\_\; \{i,\; k\}\}\; \{B\_\; \{i\}\}\}\; =\; \{\backslash \; frac\; \{u\_\; \{\; i,\; j\}\}\; \{p\_\; \{j\}\}\}\}$

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

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

Алгоритм с слабым полиномиальным временем

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

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

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

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

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

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

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

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

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

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

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

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

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

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