Адаптивное расширение набора

В теории полезности ( отзывчивого множества RS ) представляет расширение собой расширение отношения предпочтения отдельных предметов до частичного отношения предпочтения наборов предметов.

Пример

Предположим, есть четыре предмета: $w,x,y,z$ . Человек утверждает, что он ранжирует предметы в следующем общем порядке :

w\prec x\prec y\prec z

(т. е. z — его лучший предмет, затем y, затем x, затем w). Предполагая, что товары являются независимыми товарами , можно сделать вывод, что:

\{w,x\}\prec \{y,z\}

– человек предпочитает два своих лучших предмета двум худшим вещам;

\{w,y\}\prec \{x,z\}

– человек предпочитает свои лучшие и третьи лучшие предметы своим вторым и четвертым лучшим предметам.

Но о связках ничего сделать нельзя. $\{w,z\},\{x,y\}$ ; мы не знаем, какой из них предпочитает человек.

Расширение рейтинга RS $w\prec x\prec y\prec z$ — это частичный порядок наборов элементов, который включает в себя все отношения, которые можно вывести из ранжирования элементов и предположения независимости.

Определения

Позволять $O$ быть набором объектов и $\preceq$ общий порядок на $O$ .

Расширение RS $\preceq$ это частичный заказ на $2^{O}$ . Его можно определить несколькими эквивалентными способами. ^{[ 1 ]}

Адаптивный набор (RS)

Исходное расширение RS ^{[ 2 ]}^: 44–48 строится следующим образом. За каждый пакет $X\subseteq O$ , каждый предмет $x\in X$ и каждый предмет $y\notin X$ , возьмем следующие соотношения:

$X\setminus \{x\}\prec ^{RS}X$ (- добавление предмета улучшает комплект)
Если $x\preceq y$ затем $X\preceq ^{RS}(X\setminus \{x\})\cup \{y\}$ (- замена предмета на более качественный улучшает комплект).

Расширение RS является транзитивным замыканием этих отношений.

Парное доминирование (ПД)

Расширение PD основано на объединении предметов в одном комплекте с предметами в другом комплекте.

Формально, $X\preceq ^{PD}Y$ если и только если существует инъективная функция $f$ от $X$ к $Y$ такой, что для каждого $x\in X$ , $x\preceq f(x)$ .

Стохастическое доминирование (SD)

Расширение SD (названное в честь стохастического доминирования ) определяется не только для дискретных пакетов, но и для дробных пакетов (пакетов, которые содержат дробные элементы). Неформально, пакет Y является SD-предпочтительным перед пакетом X, если для каждого элемента z пакет Y содержит по крайней мере столько же объектов, которые по крайней мере не хуже z, чем пакет X.

Формально, $X\preceq ^{SD}Y$ если, для каждого предмета $z$ :

\sum _{x\succeq z}X[x]\leq \sum _{y\succeq z}Y[y]

где $X[x]$ это доля элемента $x$ в комплекте $X$ .

Если расслоения дискретны, определение имеет более простой вид. $X\preceq ^{SD}Y$ если, для каждого предмета $z$ :

|\{x\in X|x\succeq z\}|\leq |\{y\in Y|y\succeq z\}|

Аддитивная полезность (AU)

Расширение AU основано на понятии аддитивной функции полезности .

Многие различные служебные функции совместимы с заданным порядком. Например, порядок $w\prec x\prec y\prec z$ совместим со следующими служебными функциями:

u_{1}(w)=0,u_{1}(x)=2,u_{1}(y)=4,u_{1}(z)=7

u_{2}(w)=0,u_{2}(x)=2,u_{2}(y)=4,u_{2}(z)=5

Предполагая, что элементы независимы, функция полезности пакетов является аддитивной, поэтому полезность пакета представляет собой сумму полезностей его элементов, например:

u_{1}(\{w,x\})=2,u_{1}(\{w,z\})=7,u_{1}(\{x,y\})=6

u_{2}(\{w,x\})=2,u_{2}(\{w,z\})=5,u_{2}(\{x,y\})=6

Пакет $\{w,x\}$ имеет меньшую полезность, чем $\{w.z\}$ согласно обеим функциям полезности. Более того, для каждой функции полезности $u$ соответствует приведенному выше рейтингу:

u(\{w,x\})<u(\{w,z\})

.

Напротив, полезность пакета $\{w,z\}$ может быть как меньше, так и больше полезности $\{x,y\}$ .

Это мотивирует следующее определение:

$X\preceq ^{AU}Y$ если и только если для каждой аддитивной функции полезности $u$ совместим с $\preceq$ :

u(X)\leq u(Y)

Эквивалентность

$X\preceq ^{SD}Y$ подразумевает $X\preceq ^{RS}Y$ . ^{[ 1 ]}
$X\preceq ^{RS}Y$ и $X\preceq ^{PD}Y$ эквивалентны. ^{[ 1 ]}
$X\preceq ^{PD}Y$ подразумевает $X\preceq ^{AU}Y$ . Доказательство : если $X\preceq ^{PD}Y$ , затем происходит инъекция $f:X\to Y$ такой, что для всех $x\in X$ , $x\preceq f(x)$ . Следовательно, для каждой функции полезности $u$ совместим с $\preceq$ , $u(x)\leq u(f(x))$ . Следовательно, если $u$ является аддитивным, то $u(X)\leq u(Y)$ . ^{[ 1 ]}
Известно, что $\preceq ^{AU}$ и $\preceq ^{SD}$ эквивалентны, см., например ^{[ 3 ]}

Таким образом, четыре расширения $\preceq ^{RS}$ и $\preceq ^{PD}$ и $\preceq ^{SD}$ и $\preceq ^{AU}$ все эквивалентны.

Оперативные заказы и оценки

Полный заказ на пакеты называется адаптивным. ^{[ 4 ]}^{: 287–288} если он содержит расширение адаптивного набора некоторого общего порядка элементов. Т.е. он содержит все отношения, подразумеваемые базовым порядком элементов, и добавляет еще несколько отношений, которые не подразумеваются и не противоречат друг другу.

Аналогично, функция полезности для пакетов называется отзывчивой , если она вызывает адаптивный порядок. Чтобы быть более явным, ^{[ 5 ]} функция полезности u является отзывчивой, если для каждого набора X и каждых двух предметов y , z, не входящих в X : $u(y)\geq u(z)\implies u(X\cup \{y\})\geq u(X\cup \{z\})$ .

Отзывчивость подразумевается аддитивностью, но не наоборот:

Если общий порядок является аддитивным (представленным аддитивной функцией ), то по определению он содержит расширение AU $\preceq ^{AU}$ , что эквивалентно $\preceq ^{RS}$ , поэтому он отзывчив. Аналогично, если функция полезности аддитивна, то $u(X\cup \{y\})-u(X\cup \{z\})=u(y)-u(z)$ , поэтому отзывчивость удовлетворена.
С другой стороны, общий порядок может быть отзывчивым, но не аддитивным: он может содержать расширение AU, согласующееся со всеми аддитивными функциями, но может также содержать другие отношения, несовместимые с одной аддитивной функцией.

Например, ^{[ 6 ]} предположим, что есть четыре элемента с $w\prec x\prec y\prec z$ . Отзывчивость ограничивает только отношения между пакетами одного размера с замененным одним элементом или пакетами разных размеров, где маленькое содержится в большом. В нем ничего не говорится о связках разных размеров, которые не являются подмножествами друг друга. Так, например, адаптивный заказ может иметь как $\{z\}\prec \{x,y\}$ и $\{w,z\}\succ \{w,x,y\}$ . Но это несовместимо с аддитивностью: не существует аддитивной функции, для которой $u(\{z\})<u(\{x,y\})$ пока $u(\{w,z\})>u(\{w,x,y\})$ .

См. также

Ссылки

^ Перейти обратно: ^а ^б ^с ^д Азиз, Харис; Гасперс, Серж; Маккензи, Саймон; Уолш, Тоби (2015). «Справедливое распределение неделимых объектов по порядковым предпочтениям». Искусственный интеллект . 227 : 71–92. arXiv : 1312.6546 . дои : 10.1016/j.artint.2015.06.002 . S2CID 1408197 .
^ Барбера С., Боссерт В., Паттанаик П.К. (2004). «Рейтинг наборов объектов». (PDF) . Справочник по теории полезности . Спрингер США. {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Катта, Акшай-Кумар; Сетураман, Джей (2006). «Решение проблемы случайного назначения в области полных предпочтений». Журнал экономической теории . 131 (1): 231. doi : 10.1016/j.jet.2005.05.001 .
^ Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору . Издательство Кембриджского университета. ISBN 9781107060432 . ( бесплатная онлайн-версия )
^ Киропулу, Мария; Суксомпонг, Варут; Вудурис, Александрос А. (12 ноября 2020 г.). «Почти отсутствие зависти при распределении групповых ресурсов» (PDF) . Теоретическая информатика . 841 : 110–123. дои : 10.1016/j.tcs.2020.07.008 . ISSN 0304-3975 . S2CID 59222796 .
^ Бабаёв, Моше; Нисан, Ноам ; Талгам-Коэн, Инбал (2021). «Конкурентное равновесие с неделимыми товарами и родовыми бюджетами». Математика исследования операций . 46 (1): 382–403. arXiv : 1703.08150 . дои : 10.1287/moor.2020.1062 . МР 4224433 .

[agmw15-1] Перейти обратно: ^а ^б ^с ^д Азиз, Харис; Гасперс, Серж; Маккензи, Саймон; Уолш, Тоби (2015). «Справедливое распределение неделимых объектов по порядковым предпочтениям». Искусственный интеллект . 227 : 71–92. arXiv : 1312.6546 . дои : 10.1016/j.artint.2015.06.002 . S2CID 1408197 .

[bbp04-2] Барбера С., Боссерт В., Паттанаик П.К. (2004). «Рейтинг наборов объектов». (PDF) . Справочник по теории полезности . Спрингер США. {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

[3] Катта, Акшай-Кумар; Сетураман, Джей (2006). «Решение проблемы случайного назначения в области полных предпочтений». Журнал экономической теории . 131 (1): 231. doi : 10.1016/j.jet.2005.05.001 .

[handbook-4] Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору . Издательство Кембриджского университета. ISBN 9781107060432 . ( бесплатная онлайн-версия )

[5] Киропулу, Мария; Суксомпонг, Варут; Вудурис, Александрос А. (12 ноября 2020 г.). «Почти отсутствие зависти при распределении групповых ресурсов» (PDF) . Теоретическая информатика . 841 : 110–123. дои : 10.1016/j.tcs.2020.07.008 . ISSN 0304-3975 . S2CID 59222796 .

[6] Бабаёв, Моше; Нисан, Ноам ; Талгам-Коэн, Инбал (2021). «Конкурентное равновесие с неделимыми товарами и родовыми бюджетами». Математика исследования операций . 46 (1): 382–403. arXiv : 1703.08150 . дои : 10.1287/moor.2020.1062 . МР 4224433 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]