В теории полезности , то в ответ множество ( RS ) расширение является расширение предпочтений-связи по отдельности, с частичным привилегированным-отношением элементов-пучки.
Пример
Предположим, есть четыре элемента: . Человек заявляет, что он ранжирует предметы в следующем общем порядке :
(т.е. z - его лучший предмет, затем y, затем x, затем w). Предполагая, что товары являются независимыми товарами , можно сделать вывод, что:
- - человек предпочитает свои две лучшие вещи двум своим худшим вещам;
- - человек предпочитает свои лучшие и третьи лучшие предметы второму и четвертому лучшим предметам.
Но о связках ничего сделать нельзя. ; мы не знаем, какое из них предпочитает человек.
Расширение рейтинга RS - это частичный порядок пакетов элементов, который включает в себя все отношения, которые могут быть выведены из ранжирования элементов и предположения о независимости.
Определения
Позволять быть набором объектов и полный заказ на .
Расширение RS частичный заказ на . Его можно определить несколькими эквивалентными способами. [1]
Отзывчивый набор (RS)
Исходное расширение RS [2] : 44–48 построено следующим образом. Для каждой пачки, каждый предмет и каждый предмет , возьмем следующие отношения:
- (- добавление предмета улучшает набор)
- Если тогда (- замена предмета на предмет лучшего качества улучшает набор).
Расширение RS - это транзитивное замыкание этих отношений.
Парное доминирование (ПД)
Расширение PD основано на объединении элементов в одном комплекте с элементами в другом комплекте.
Формально, если и только если существует инъективная функция из к так что для каждого , .
Стохастическое доминирование (SD)
Расширение SD (названное в честь стохастического доминирования ) определено не только для дискретных пакетов, но и для дробных пакетов (пакетов, которые содержат доли элементов). Неформально, комплект Y является SD-предпочтительным комплектом X, если для каждого элемента z комплект Y содержит, по крайней мере, столько же объектов, которые по крайней мере так же хороши, как z, что и комплект X.
Формально, iff, для каждого элемента :
где это доля товара в связке .
Если связки дискретны, определение имеет более простой вид. iff, для каждого элемента :
Аддитивная утилита (AU)
Расширение AU основано на понятии аддитивной функции полезности .
Многие различные служебные функции совместимы с данным порядком. Например, заказ совместим со следующими служебными функциями:
Предполагая, что элементы независимы, функция полезности для комплектов является аддитивной, поэтому полезность комплекта является суммой полезностей его элементов, например:
Пакет имеет меньшую полезность, чем согласно обеим функциям полезности. Более того, для каждой функции полезности совместим с приведенным выше рейтингом:
- .
Напротив, полезность пакета может быть меньше или больше, чем полезность .
Это мотивирует следующее определение:
если и только если, для каждой аддитивной функции полезности совместим с :
Эквивалентность
- подразумевает . [1]
- а также эквивалентны. [1]
- подразумевает . Доказательство : если, то идет инъекция такое, что для всех , . Следовательно, для каждой функции полезности совместим с , . Следовательно, если аддитивно, то . [1]
- Известно, что а также эквивалентны, см., например, [3]
Таким образом, четыре расширения а также а также а также все эквивалентны.
Ответная реакция
Общий порядок комплектов называется отзывчивым [4] : 287–288, если он содержит расширение адаптивного набора некоторого общего порядка элементов. То есть, он содержит все отношения, которые подразумеваются лежащим в основе упорядочением элементов, и добавляет еще несколько отношений, которые не подразумеваются и не противоречат друг другу.
Отзывчивость подразумевает аддитивность, но не наоборот:
- Если общий порядок является аддитивным (представлен аддитивной функцией ), то по определению он содержит расширение AU, что эквивалентно , поэтому он отзывчивый.
- С другой стороны, общий порядок может реагировать, но не аддитивно: он может содержать расширение AU, которое согласуется со всеми аддитивными функциями, но может также содержать другие отношения, несовместимые с одной аддитивной функцией.
Например, [5] предположим, что есть четыре элемента с. Отзывчивость ограничивает только отношения между связками одинакового размера с замененным одним элементом или связками разных размеров, когда меньшее содержится в большом. Здесь ничего не говорится о связках разного размера, которые не являются подмножествами друг друга. Так, например, отзывчивый заказ может иметь кака также . Но это несовместимо с аддитивностью: не существует аддитивной функции, для которой пока .
Смотрите также
Рекомендации
- ^ a b c d Азиз, Харис; Гасперс, Серж; Маккензи, Саймон; Уолш, Тоби (2015). «Справедливое присвоение неделимых объектов по порядковым предпочтениям». Искусственный интеллект . 227 : 71–92. arXiv : 1312,6546 . DOI : 10.1016 / j.artint.2015.06.002 .
- ^ Барбера, С., Боссерт, В., Паттанаик, П.К. (2004). «Ранжирование наборов предметов». (PDF) . Справочник по теории полезности . Springer США.CS1 maint: несколько имен: список авторов ( ссылка )
- ^ Катта, Акшай-Кумар; Сетураман, Джей (2006). «Решение проблемы случайного распределения в области полного предпочтения». Журнал экономической теории . 131 (1): 231. DOI : 10.1016 / j.jet.2005.05.001 .
- ^ Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору . Издательство Кембриджского университета. ISBN 9781107060432.( бесплатная онлайн-версия )
- ^ Моше, Бабайофф; Ноам, нисан; Инбал, Талгам-Коэн (23.03.2017). «Конкурентное равновесие с неделимыми товарами и общими бюджетами». arXiv : 1703.08150 . Bibcode : 2017arXiv170308150B . Цитировать журнал требует
|journal=
( помощь )