Однопиковые предпочтения

Однопиковые предпочтения представляют собой класс отношений предпочтения . Группа имеет одновершинные предпочтения по набору результатов, если результаты можно упорядочить по линии так, что:

Каждый агент имеет «лучший результат» в наборе, и
Для каждого агента результаты, которые далеки от его или ее наилучшего результата, менее предпочтительны.

Однопиковые предпочтения типичны для одномерных областей. Типичным примером является ситуация, когда нескольким потребителям приходится принимать решение о количестве общественного блага, которое они приобретут. Сумма является одномерной переменной. Обычно каждый потребитель выбирает определенное количество, которое лучше всего для него или нее, и если фактическое количество больше/меньше идеального количества, агент тогда менее удовлетворен.

При однопиковых предпочтениях существует простой и правдивый механизм выбора результата, который заключается в выборе медианного количества; это приводит к теореме о медианном избирателе . ^{[ нужна ссылка ]} Это верно, поскольку медианная функция удовлетворяет сильному свойству монотонности .

Идея была впервые предложена Дунканом Блэком. ^[1] и позже Кеннетом Эрроу . ^[2]

Определения

Позволять $X=\{x_{1},\ldots ,x_{m}\}$ быть набором возможных результатов. Позволять $N=\{1,\ldots ,n\}$ быть множеством агентов. Отношение предпочтения агента i обозначается через $\succ _{i}$ . Максимальный элемент $\succ _{i}$ в X обозначается $x_{i}^{*}$ _.

Определение с использованием общего порядка

группа N Говорят, что имеет одновершинные предпочтения над X , если существует такой порядок результатов, что для каждого агента i в N :

$x_{k}<x_{j}\leq x_{i}^{*}\Rightarrow x_{j}\succ _{i}x_{k}$
$x_{k}>x_{j}\geq x_{i}^{*}\Rightarrow x_{j}\succ _{i}x_{k}$

Другими словами, $x_{i}^{*}$ является идеальной точкой для агента i . Когда агент сравнивает два результата, которые находятся справа или слева от его идеальной точки, он строго отдает предпочтение тому варианту, который ближе всего к нему. $x_{i}^{*}$ .

Обратите внимание, что отношения предпочтения $\succ _{i}$ различны, но порядок результатов должен быть одинаковым для всех агентов.

Необходимое условие

Баллестер и Херингер ^[3] доказал следующее необходимое условие однопиковых предпочтений.

Если группа N имеет одновершинные предпочтения над X , то для каждой тройки исходов в X существует исход, который не занимает последнее место ни у одного агента N. из

Некоторые примеры

Однопиковые предпочтения

На следующем графике показан набор из трех предпочтений, которые имеют один пик по сравнению с результатами {A,B,C,D,E}. На вертикальной оси число представляет собой рейтинг предпочтения результата, где 1 означает наиболее предпочтительный. Два исхода, которые одинаково предпочтительны, имеют одинаковый рейтинг.

Порядок результатов следующий: A < B < C < D < E. Идеальный результат для зеленого агента — A, для красного — B, для синего — C. Для каждого агента, когда мы удаляемся от его идеальный результат, рейтинг снижается.

Также можно убедиться, что для каждой тройки исходов один из них никогда не занимает последнее место — тот, что посередине. Например, в {A,B,C} B никогда не занимает последнее место; в {C,D,E} D никогда не занимает последнее место; и т. д.

Неоднопиковые предпочтения

Если каждое из двух предпочтений, представленных следующими двумя графиками, добавить к трем предпочтениям, указанным выше, то результирующая группа из четырех предпочтений не будет однопиковой:

Что касается предпочтений синего цвета, можно видеть, что рейтинг предпочтений резко снижается для «D», а затем резко возрастает для «E». Это доказывает, что предпочтения синего цвета не являются однопиковыми относительно порядка A<B<C<D<E, но это еще не доказывает, что не существует другого порядка, при котором все четыре предпочтения были бы однопиковыми. Чтобы формально доказать это, рассмотрим набор из трех исходов {A, D, E}. Каждый из этих исходов является худшим исходом для некоторого агента: A — худший для красного агента, D — худший для синего агента, а E — худший для зеленого агента, указанного выше. Следовательно, никакое упорядочение по X не может сделать множество предпочтений одновершинным.

Зеленые предпочтения формально не являются однопиковыми, поскольку имеют два наиболее предпочтительных исхода: «B» и «C». Такие предпочтения иногда называют одноплато .

Интерпретации

Однопиковые предпочтения имеют множество интерпретаций для разных приложений.

Простое применение идеологических предпочтений — это подумать о пространстве результатов. $\{x_{1},x_{2},\ldots ,x_{n}\}$ как локации на улице и в каждом $x_{i}$ как адрес физического лица. Предположим, что на улице должна быть расположена единственная автобусная остановка, и каждый человек желает дойти до остановки как можно меньше пешком. Тогда индивиды имеют одновершинные предпочтения: индивидуальные $i$ идеальная точка это $x_{i}$ и ей не нравятся другие места, чем дальше они находятся на западе, либо чем дальше на восток.

Пространство результатов также можно рассматривать как различные политики в идеологическом спектре: политика левых и политика правых; более либеральная политика по сравнению с более консервативной политикой; политика, поддерживающая свободный рынок, и политика, поддерживающая государственное вмешательство. Избиратели имеют одновершинные предпочтения, если у них есть идеальный баланс между двумя направлениями идеологического спектра, и если им не нравится политика, тем дальше они от своей идеальной точки.

Связанные домены предпочтений

Говорят, что группа агентов имеет однонаправленные предпочтения в отношении набора возможных результатов, если результаты можно упорядочить по такой линии, что:

У каждого агента есть « худший исход» в наборе, и -
результаты, которые дальше от его худшего предпочтительны Для каждого агента более результата .

Лакнер и Питерс ^[4] изучить класс предпочтений, имеющих одну вершину на окружности.

Признание

Проблема распознавания с одной вершиной представляет собой следующую проблему принятия решения : учитывая набор предпочтений для набора результатов, решить, существует ли общий порядок результатов, для которых предпочтения являются однопиковыми. Обычно требуется также найти этот общий порядок, если он существует.

Обманывать ^[5] представляет алгоритм с полиномиальным временем для распознавания одновершинных предпочтений на дереве.

Эскофье, испанка и Тидричева ^[6] изучить задачу распознавания одновершинных предпочтений на общем графе.

См. также

Однопараметрический механизм

Ссылки

^ Блэк, Дункан (1 февраля 1948 г.). «Обоснование группового принятия решений» . Журнал политической экономии . 56 (1): 23–34. дои : 10.1086/256633 . ISSN 0022-3808 . S2CID 153953456 .
^ Баумол, Уильям Дж.; Эрроу, Кеннет Дж. (1 января 1952 г.). «Социальный выбор и индивидуальные ценности» . Эконометрика . 20 (1): 110. дои : 10.2307/1907815 . hdl : 2027/inu.30000082056718 . ISSN 0012-9682 . JSTOR 1907815 .
^ Баллестер, Мигель А.; Херингер, Гийом (15 июля 2010 г.). «Характеристика однопикового домена» . Социальный выбор и благосостояние . 36 (2): 305–322. дои : 10.1007/s00355-010-0476-3 . ISSN 0176-1714 . S2CID 14975233 .
^ Петерс, Доминик; Лакнер, Мартин (24 июня 2020 г.). «Предпочтения одновершинные по кругу» . Журнал исследований искусственного интеллекта . 68 : 463–502. дои : 10.1613/jair.1.11732 . ISSN 1076-9757 .
^ Трик, Майкл А. (1 июня 1989 г.). «Распознавание одновершинных предпочтений на дереве» . Математические социальные науки . 17 (3): 329–334. дои : 10.1016/0165-4896(89)90060-7 . ISSN 0165-4896 .
^ Эскофье, Бруно; Спанджаард, Оливье; Тидрихова, Магдалена (2020). «Распознавание однопиковых предпочтений на произвольном графе: сложность и алгоритмы» . В Харксе, Тобиас; Климм, Макс (ред.). Алгоритмическая теория игр . Конспекты лекций по информатике. Том. 12283. Чам: Springer International Publishing. стр. 291–306. arXiv : 2004.13602 . дои : 10.1007/978-3-030-57980-7_19 . ISBN 978-3-030-57980-7 . S2CID 216562247 .

Остин-Смит, Дэвид и Джеффри Бэнкс (2000). Позитивная политическая теория I: Коллективные предпочтения . Издательство Мичиганского университета. ISBN 978-0-472-08721-1 .
Мас-Колелл, Андреу, Майкл Д. Уинстон и Джерри Р. Грин (1995). Микроэкономическая теория . Издательство Оксфордского университета. ISBN 978-0-19-507340-9 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
Мулен, Эрве (1991). Аксиомы совместного принятия решений . Издательство Кембриджского университета. ISBN 978-0-521-42458-5 .

[1] Блэк, Дункан (1 февраля 1948 г.). «Обоснование группового принятия решений» . Журнал политической экономии . 56 (1): 23–34. дои : 10.1086/256633 . ISSN 0022-3808 . S2CID 153953456 .

[2] Баумол, Уильям Дж.; Эрроу, Кеннет Дж. (1 января 1952 г.). «Социальный выбор и индивидуальные ценности» . Эконометрика . 20 (1): 110. дои : 10.2307/1907815 . hdl : 2027/inu.30000082056718 . ISSN 0012-9682 . JSTOR 1907815 .

[3] Баллестер, Мигель А.; Херингер, Гийом (15 июля 2010 г.). «Характеристика однопикового домена» . Социальный выбор и благосостояние . 36 (2): 305–322. дои : 10.1007/s00355-010-0476-3 . ISSN 0176-1714 . S2CID 14975233 .

[4] Петерс, Доминик; Лакнер, Мартин (24 июня 2020 г.). «Предпочтения одновершинные по кругу» . Журнал исследований искусственного интеллекта . 68 : 463–502. дои : 10.1613/jair.1.11732 . ISSN 1076-9757 .

[5] Трик, Майкл А. (1 июня 1989 г.). «Распознавание одновершинных предпочтений на дереве» . Математические социальные науки . 17 (3): 329–334. дои : 10.1016/0165-4896(89)90060-7 . ISSN 0165-4896 .

[6] Эскофье, Бруно; Спанджаард, Оливье; Тидрихова, Магдалена (2020). «Распознавание однопиковых предпочтений на произвольном графе: сложность и алгоритмы» . В Харксе, Тобиас; Климм, Макс (ред.). Алгоритмическая теория игр . Конспекты лекций по информатике. Том. 12283. Чам: Springer International Publishing. стр. 291–306. arXiv : 2004.13602 . дои : 10.1007/978-3-030-57980-7_19 . ISBN 978-3-030-57980-7 . S2CID 216562247 .

[1]

[2]

[3]

[4]

[5]

[6]