Валовые заменители (неделимые статьи)

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

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

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

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

Определения

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

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

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

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

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

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

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

Недополняющий (NC)

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

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

М ^♮ Вогнутый (MX)

Их ^♮-состояние ^[3] происходит в результате выпуклого анализа (этот символ является «естественным» символом, аналогичным его использованию в музыке ). Там написано, что для всех наборов $X,Y$ и для каждого предмета $x\in X$ , хотя бы одно из следующих условий должно быть истинным:

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

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

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

Сильные некомплементарии (SNC)

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

u(X)+u(Y)\leq u(X\setminus X'\cup Y')+u(Y\setminus Y'\cup X')

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

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

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

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

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

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

Состояние DDF ^[5] связано с изменениями ценового вектора. Если расположить товары в порядке возрастания их цены, то спрос агентов ГЦ течет только вниз – от товаров, цена которых выросла больше, к товарам, цена которых выросла меньше, или от товаров, цена которых выросла, к товарам, цена которых снизилась. , или от предметов, цена которых снизилась меньше, к предметам, цена которых снизилась больше.

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

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

Сохранение

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

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

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

Субмодуль, который не является GS
Пучок	Стоимость ($)
$\emptyset$	0
х	40
и	40
С	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.
NC нарушается с ценами $p_{x}=p_{y}=10$ и $p_{z}=6$ , поскольку есть два требуемых пакета: {x,y} и {z} (оба имеют чистую полезность 60). Но если y взят из первого набора, во втором наборе нет ничего, что могло бы его заменить ({x} имеет чистую полезность 30, а {x,z} имеет чистую полезность 59 - ни один из них не является спросом).
GS нарушается с ценами $p_{x}=p_{y}=p_{z}=10$ , поскольку требуемый пакет тогда равен {x,y}, но когда $p_{x}$ увеличивается, например, до 200 (так что x больше не требуется), новый требуемый пакет равен {z}. Увеличение $p_{x}$ снизился спрос на товар y.
СИ нарушается с ценами $p_{x}=p_{y}=p_{z}=10$ , поскольку связка {z} не является оптимальной, и единственный способ ее улучшить — изменить ее на {x,y}, что потребует добавления двух элементов.

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

для всех целых чисел

k_{x},k_{y}

и для каждого

k_{x}'\leq k_{x}

, существует целое число

k_{y}'\leq k_{y}

такой, что:

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

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

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

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

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

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

Внешние ссылки

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

Ссылки

^ Jump up to: ^а ^б Келсо, А.С.; Кроуфорд, вице-президент (1982). «Подбор должностей, формирование коалиций и валовые заменители». Эконометрика . 50 (6): 1483. дои : 10.2307/1913392 . JSTOR 1913392 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Гюль, Ф.; Стакетти, Э. (1999). «Вальрасово равновесие с валовыми заменителями». Журнал экономической теории . 87 : 95–124. дои : 10.1006/jeth.1999.2531 .
^ Jump up to: ^а ^б ^с Фудзисигэ, Сатору; Ян, Зайфу (2003). «Заметка о состоянии валовых замен Келсо и Кроуфорда». Математика исследования операций . 28 (3): 463–469. дои : 10.1287/moor.28.3.463.16393 .
^ Jump up to: ^а ^б ^с ^д Мурота, Кадзуо (2018). «Множественное обменное свойство для M ^♮-вогнутые функции и оцененные матроиды». Математика исследования операций . 43 (3): 781–788. arXiv : 1608.07021 . Bibcode : 2016arXiv160807021M . doi : 10.1287/moor.2017.0882 .
^ Jump up to: ^а ^б Сегал-Халеви, Эрель; хасидим, Авинатан; Ауманн, Йонатан (2016). «Поток спроса агентов с оценками валового замещения». Письма об исследованиях операций . 44 (6): 757–760. arXiv : 1607.01989 . дои : 10.1016/j.orl.2016.09.012 . S2CID 14017704 .
^ Бен-Цви, Орен; Лави, Рон; Ньюман, Илан (2013). «Восходящие аукционы и вальрасовское равновесие». arXiv : 1301.1153 [ cs.GT ].
^ Паес Леме, Ренато (01 ноября 2017 г.). «Валовая заменимость: алгоритмический обзор» . Игры и экономическое поведение . 106 : 294–316. дои : 10.1016/j.geb.2017.10.016 . ISSN 0899-8256 .

[kc82-1] Jump up to: ^а ^б Келсо, А.С.; Кроуфорд, вице-президент (1982). «Подбор должностей, формирование коалиций и валовые заменители». Эконометрика . 50 (6): 1483. дои : 10.2307/1913392 . JSTOR 1913392 .

[gs99-2] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Гюль, Ф.; Стакетти, Э. (1999). «Вальрасово равновесие с валовыми заменителями». Журнал экономической теории . 87 : 95–124. дои : 10.1006/jeth.1999.2531 .

[fy03-3] Jump up to: ^а ^б ^с Фудзисигэ, Сатору; Ян, Зайфу (2003). «Заметка о состоянии валовых замен Келсо и Кроуфорда». Математика исследования операций . 28 (3): 463–469. дои : 10.1287/moor.28.3.463.16393 .

[m16-4] Jump up to: ^а ^б ^с ^д Мурота, Кадзуо (2018). «Множественное обменное свойство для M ^♮-вогнутые функции и оцененные матроиды». Математика исследования операций . 43 (3): 781–788. arXiv : 1608.07021 . Bibcode : 2016arXiv160807021M . doi : 10.1287/moor.2017.0882 .

[sha16-5] Jump up to: ^а ^б Сегал-Халеви, Эрель; хасидим, Авинатан; Ауманн, Йонатан (2016). «Поток спроса агентов с оценками валового замещения». Письма об исследованиях операций . 44 (6): 757–760. arXiv : 1607.01989 . дои : 10.1016/j.orl.2016.09.012 . S2CID 14017704 .

[bl13-6] Бен-Цви, Орен; Лави, Рон; Ньюман, Илан (2013). «Восходящие аукционы и вальрасовское равновесие». arXiv : 1301.1153 [ cs.GT ].

[7] Паес Леме, Ренато (01 ноября 2017 г.). «Валовая заменимость: алгоритмический обзор» . Игры и экономическое поведение . 106 : 294–316. дои : 10.1016/j.geb.2017.10.016 . ISSN 0899-8256 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]