Валовые заменители (неделимые позиции) - Gross substitutes (indivisible items) - Wikipedia

Для использования в других целях см. Валовые заменители.

В экономика, валовые заменители (GS) это класс полезные функции для неделимых товаров. Говорят, что агент иметь оценку GS если всякий раз, когда цены на одни товары увеличиваются, а цены на другие остаются постоянными, спрос агента на товары, цена которых остается постоянной, возрастает слабо.

Пучок	Оценка Алисы (GS)	Оценка Боба (не GS)
${\displaystyle \emptyset }$	$0	$0
яблоко	$5	$5
хлеб	$7	$7
яблоко + хлеб	$9	$15

Пример показан справа. В таблице показаны оценки (в долларах) Алисы и Боба для четырех возможных подмножеств набора из двух предметов: {яблоко, хлеб}. Оценка Алисы - GS, но оценка Боба - не GS. Чтобы убедиться в этом, предположим, что изначально и яблоко, и хлеб были оценены в 6 долларов. Оптимальный набор для Боба - яблоко + хлеб, так как он дает ему чистую стоимость в 3 доллара. Теперь цена на хлеб увеличивается до 10 долларов. Теперь оптимальный набор для Боба - это пустой набор, так как все остальные пакеты дают ему отрицательную чистую стоимость. Таким образом, спрос Боба на яблоко снизился, хотя выросла только цена на хлеб.

Условие GS было введено Келсо и Кроуфорд в 1982 году.^[1] и был широко разрекламирован Гюлом и Стаккетти.^[2]С тех пор он нашел множество применений, в основном в теория аукционов и конкурентное равновесие теория.

Определения

У условия GS есть много эквивалентных определений.

Валовые заменители (GS)

Исходное определение GS^[1] основан на вектор цен и набор спроса.

• Вектор цен ${\displaystyle p}$ - вектор, содержащий цену каждого товара.
• Учитывая функцию полезности ${\displaystyle u}$ и ценовой вектор ${\displaystyle p}$, множество ${\displaystyle X}$ называется требовать если он максимизирует чистую полезность агента: ${\displaystyle u(X)-p\cdot X}$.
• В набор спроса ${\displaystyle D(u,p)}$ это набор всех требований.

Свойство GS означает, что когда цена на одни товары увеличивается, спрос на другие товары не уменьшается. Формально для любых двух векторов цен ${\displaystyle q}$ и ${\displaystyle p}$ такой, что ${\displaystyle q\geq p}$, и любые ${\displaystyle X\in D(u,p)}$, Существует ${\displaystyle Y\in D(u,q)}$ такой, что ${\displaystyle Y\supseteq \{x\in X|p_{x}=q_{x}\}}$ (Y содержит все предметы из X, цена которых осталась постоянной).

Единичное улучшение (SI)

Условие СИ^[2] говорит, что неоптимальный набор может быть улучшен путем добавления, удаления или замены одного элемента. Формально для любого ценового вектора ${\displaystyle p}$ и связать ${\displaystyle X\notin D(u,p)}$, существует пучок ${\displaystyle Y}$ такой, что ${\displaystyle u(Y)-p\cdot Y>u(X)-p\cdot X}$, ${\displaystyle |X\setminus Y|\leq 1}$ и ${\displaystyle |Y\setminus X|\leq 1}$.

Нет дополнительных (NC)

Условие NC^[2] говорит, что каждое подмножество требуемого пакета имеет замену. Формально: на любой вектор цен ${\displaystyle p}$ и востребованные связки ${\displaystyle X,Y\in D(u,p)}$, и для каждого подмножества ${\displaystyle X'\subseteq X}$, есть подмножество ${\displaystyle Y'\subseteq Y}$ такой, что: ${\displaystyle X\setminus X'\cup Y'\in D(u,p)}$

Если функция оценки монотонна, то GS подразумевает SI, SI подразумевает NC, а NC подразумевает GS,^{[2]:117–120} так что эти три условия эквивалентны.

M # вогнутый (MX)

Условие MX^[3] происходит от выпуклый анализ. Там сказано, что для всех комплектов ${\displaystyle X,Y}$ и для каждого предмета ${\displaystyle x\in X}$, должно выполняться хотя бы одно из следующего:

• ${\displaystyle u(X)+u(Y)\leq u(X\setminus \{x\})+u(Y\cup \{x\})}$, или же -
• там есть предмет ${\displaystyle y\in Y}$ такой, что ${\displaystyle u(X)+u(Y)\leq u(X\setminus \{x\}\cup \{y\})+u(Y\setminus \{y\}\cup \{x\})}$.

Свойство M # -вогнутости также называют M # -обмен свойство.^[4] Имеет следующую интерпретацию. Предположим, что у Алисы и Боба есть функция полезности. ${\displaystyle u}$, и наделены связками ${\displaystyle X}$ и ${\displaystyle Y}$ соответственно. Для каждого предмета, который Алиса передает Бобу, Боб может передать Алисе не более одного предмета, так что их общая полезность после обмена сохраняется или увеличивается.

SI подразумевает MX, а MX подразумевает SI,^[3] так что они эквивалентны.

Строгое отсутствие дополнительных (SNC)

Состояние SNC^[2] говорит, что для всех наборов ${\displaystyle X}$ и ${\displaystyle Y}$ и для каждого подмножества ${\displaystyle X'\subseteq X}$, есть подмножество ${\displaystyle Y'\subseteq Y}$ такой, что:

${\displaystyle u(X)+u(Y)\leq u(X\setminus X'\cup Y')+u(Y\setminus Y'\cup X')}$

Свойство SNC также называют M # -множественный обмен свойство.^[4] Имеет следующую интерпретацию.^[2] Предположим, что у Алисы и Боба есть функция полезности. ${\displaystyle u}$, и наделены связками ${\displaystyle X}$ и ${\displaystyle Y}$ соответственно. Для каждого подмножества ${\displaystyle X'}$ что Алиса передает Бобу, существует эквивалентное подмножество ${\displaystyle Y'}$ что Боб может управлять Алисой, так что их общая полезность после обмена сохраняется или увеличивается. Обратите внимание, что это очень похоже на условие MC - с той лишь разницей, что в MC Алиса передает Бобу ровно один элемент, а Боб возвращает Алисе не более одного элемента.

Примечание: чтобы проверить, ты имеет SNC, достаточно рассмотреть случаи, когда ${\displaystyle X'\subseteq X\setminus Y}$. И достаточно проверить нетривиальные подмножества, т.е. случаи, когда ${\displaystyle X'\neq \emptyset }$ и ${\displaystyle X'\neq X\setminus Y}$. И для этих случаев нам нужно только искать среди пакетов ${\displaystyle Y'\subseteq Y\setminus X}$.

Казуо Мурота доказал^[4] что MX подразумевает SNC.

Очевидно, что SNC подразумевает NC.^[2] Доказательство: Исправьте служебную функцию SNC ${\displaystyle u}$ и ценовой вектор ${\displaystyle p}$. Позволять ${\displaystyle A,B}$ быть двумя связками в наборе спроса ${\displaystyle D(u,p)}$. Это означает, что у них одна и та же сетевая утилита, например, ${\displaystyle U_{p}:=u_{p}(A)=u_{p}(B)}$, а все остальные пакеты имеют сетевую полезность не более ${\displaystyle U_{p}}$. По условию SNC для каждого ${\displaystyle A'\subset A}$, Существует ${\displaystyle B'\subseteq B}$ такой, что ${\displaystyle u_{p}(A\setminus A'\cup B)+u_{p}(B\setminus B'\cup A)\geq u_{p}(A)+u_{p}(B)=2\cdot U_{p}}$. Но ${\displaystyle u_{p}(A\setminus A'\cup B)}$ и ${\displaystyle u_{p}(B\setminus B'\cup A)}$ оба не более ${\displaystyle U_{p}}$. Следовательно, оба должны быть точно ${\displaystyle U_{p}}$. Следовательно, оба они также находятся в ${\displaystyle D(u,p)}$.

Мы уже говорили, что NC подразумевает GS, что влечет SI, и что^[3] SI подразумевает MX. Это замыкает цикл и показывает, что все эти свойства эквивалентны (есть также прямое доказательство^[4] что SNC подразумевает MX).

Нисходящий поток спроса (DDF)

Условие DDF^[5] связано с изменением ценового вектора. Если мы упорядочиваем товары в порядке возрастания их увеличения цены, то спрос агентов GS будет течь только вниз - от товаров, цена которых выросла больше, до предметов, цена которых выросла меньше, или от предметов, цена которых увеличилась, до предметов, цена которых снизилась. , или от предметов, цена которых снизилась меньше, до предметов, цена которых снизилась больше.

Формально пусть ${\displaystyle p,q}$ - два вектора цен и пусть ${\displaystyle \Delta :=q-p}$ быть вектором роста цен. Если предмет ${\displaystyle x}$ требуется под ${\displaystyle p}$ и не востребован под ${\displaystyle q}$, то есть еще один предмет ${\displaystyle y}$ с ${\displaystyle \Delta _{y}<\Delta _{x}}$ это не требуется при ${\displaystyle p}$ и востребован под ${\displaystyle q}$.

Легко видеть, что из DDF следует GS (GS - частный случай DDF, в котором ${\displaystyle \Delta }$ имеет только нулевые или положительные значения).^[5] докажите, что MX влечет DDF, так что все эти условия эквивалентны.

Сохранение

Состояние ГЦБ сохраняется при изменении цен. То есть функция полезности ${\displaystyle u}$ имеет GS, если и только если для каждого вектора цен ${\displaystyle p}$, функция чистой полезности ${\displaystyle u-p}$ также есть GS. Это легче всего увидеть сквозь условия MC или SNC, поскольку очевидно, что эти условия инвариантны к цене.

Характеристики

Субмодульность

Субмодульный, который не является GS

Пучок	Стоимость ($)
${\displaystyle \emptyset }$	0
Икс	40
у	40
z	66
х, у	80
х, г	75
у, г	75
х, у, г	80

Каждая оценка GS - это функция субмодульного набора.^[2]

Обратное не всегда верно.^[6] Это показано на примере справа. Утилита является субмодульной, поскольку она удовлетворяет свойству убывающей предельной полезности: предельная полезность элемента составляет 40–66 при добавлении к пустому набору, 9–40 при добавлении к одному элементу и 0–5 при добавлении. к паре предметов. Но это нарушает эквивалентные условия семейства GS:

• MX нарушается наборами {x, y} и {z}. Предположим, что Алиса имеет {x, y}, а Боб - {z}, поэтому их общая полезность равна 146. Алиса передает x Бобу. Затем, независимо от того, возвращает ли Боб z или ничего не возвращает, их общая полезность падает до 115.
• НК нарушена ценами ${\displaystyle p_{x}=p_{y}=10}$ и ${\displaystyle p_{z}=6}$, поскольку есть два требуемых пакета: {x, y} и {z} (оба имеют сетевую полезность 60). Но если y берется из первого набора, ничто из второго набора не может его заменить ({x} имеет чистую полезность 30, а {x, z} имеет чистую полезность 59 - ни один из них не является требованием).
• GS нарушают цены ${\displaystyle p_{x}=p_{y}=p_{z}=10}$, так как тогда требуемый пакет равен {x, y}, но когда ${\displaystyle p_{x}}$ увеличивается, например, до 200 (так что x больше не требуется), новый требуемый пакет равен {z}. Увеличение ${\displaystyle p_{x}}$ снизился спрос на товар y.
• SI нарушается ценами ${\displaystyle p_{x}=p_{y}=p_{z}=10}$, так как набор {z} не является оптимальным, но единственный способ улучшить его - это изменить его на {x, y}, что требует добавления двух элементов.

Субмодульность действительно подразумевает GS в особом случае, когда существует единственный тип элемента, так что значение пакета зависит только от количества элементов в пакете. Это легче всего увидеть, используя характеристику SNC, которая в данном случае означает:

для всех целых чисел ${\displaystyle k_{x},k_{y}}$ и для каждого ${\displaystyle k_{x}'\leq k_{x}}$, есть целое число ${\displaystyle k_{y}'\leq k_{y}}$ такой, что:

${\displaystyle u(k_{x})+u(k_{y})\leq u(k_{x}-k_{x}'+k_{y}')+u(k_{y}-k_{y}'+k_{x}')}$

Действительно, если ${\displaystyle k_{x}'\leq k_{y}}$ тогда мы можем взять ${\displaystyle k_{y}'=k_{x}'}$ что делает две стороны идентичными; если ${\displaystyle k_{x}'>k_{y}}$ мы можем взять ${\displaystyle k_{y}'=k_{y}}$ что делает неравенство:

${\displaystyle u(k_{x})+u(k_{y})\leq u(k_{y}+k_{x}-k_{x}')+u(k_{x}')}$

что эквивалентно:

${\displaystyle u(k_{x}'+[k_{x}-k_{x}'])-u(k_{x}')\leq u(k_{y}+[k_{x}-k_{x}'])-u(k_{y})}$

Это следует из субмодулярности, поскольку ${\displaystyle k_{x}'>k_{y}}$.

внешняя ссылка

• Учебник по валовым заменителям на конференции EC 2018: Абстрактный, Часть I (Ренато Паес-Леме), Часть II (Инбал Талгам-Коэн).
• Валовая заменяемость: алгоритмический обзор.^[7]

Рекомендации

1. Kelso, A. S .; Кроуфорд, В. П. (1982). «Подбор должностей, формирование коалиции и валовые заменители». Econometrica. 50 (6): 1483. Дои:10.2307/1913392. JSTOR  1913392.
2. Залив.; Стаккетти, Э. (1999). «Вальрасовское равновесие с валовыми заменителями». Журнал экономической теории. 87: 95. Дои:10.1006 / jeth.1999.2531.
3. Фудзишигэ, Сатору; Ян, Зайфу (2003). «Примечание о состоянии валовых заменителей Келсо и Кроуфорда». Математика исследования операций. 28 (3): 463. Дои:10.1287 / moor.28.3.463.16393.
4. Казуо Мурота (2016). «Свойство множественного обмена для M # -вогнутых функций и оцененных матроидов». arXiv:1608.07021. Bibcode:2016arXiv160807021M.
5. Сегал-Халеви, Эрель; Хасидим, Авинатан; Ауманн, Йонатан (2016). «Поток спроса агентов с брутто-замещающей оценкой». Письма об исследованиях операций. 44 (6): 757. arXiv:1607.01989. Дои:10.1016 / j.orl.2016.09.012.
6. Бен-Цви, Орен; Лави, Рон; Ньюман, Илан (2013). «Восходящие аукционы и вальрасовское равновесие». arXiv:1301.1153 [cs.GT ].
7. Паес Леме, Ренато (01.11.2017). «Полная взаимозаменяемость: алгоритмический обзор». Игры и экономическое поведение. 106: 294–316. Дои:10.1016 / j.geb.2017.10.016. ISSN  0899-8256.