Вычислительный социальный выбор - это область на пересечении теории социального выбора , теоретической информатики и анализа многоагентных систем . [1] Он состоит из анализа проблем, возникающих в результате агрегирования предпочтений группы агентов, с вычислительной точки зрения. В частности, вычислительный социальный выбор связан с эффективным вычислением результатов правил голосования , вычислительной сложностью различных форм манипуляции и проблемами, возникающими из проблемы представления и выявления предпочтений в комбинаторных условиях.
Определение победителя
Полезность той или иной системы голосования может быть сильно ограничена, если вычисление победителя выборов занимает очень много времени. Следовательно, важно разработать быстрые алгоритмы, которые могут оценивать правило голосования при вводе бюллетеней . Как это принято в теории сложности вычислений , алгоритм считается эффективным, если он занимает полиномиальное время . Многие популярные правила голосования можно оценить за полиномиальное время простым способом (т. Е. Подсчетом), например, подсчетом Борды , одобрительным голосованием или правилом множественности . Для таких правил, как метод Шульце или ранжированные пары , можно использовать более сложные алгоритмы, чтобы показать полиномиальное время выполнения. [2] [3] Однако некоторые системы голосования сложно оценить с помощью вычислений. [4] В частности, определение победителя по методу Кемени-Янг , метод Доджсона и метод Юнга все NP-трудные проблемы. [4] [5] [6] [7] Это привело к разработке алгоритмов аппроксимации и управляемых алгоритмов с фиксированными параметрами для улучшения теоретических расчетов таких проблем. [8] [9] [10]
Жесткость манипуляции
Согласно теореме Гиббарда-Саттертуэйта , всеми нетривиальными правилами голосования можно манипулировать в том смысле, что избиратели иногда могут добиться лучшего результата, искажая свои предпочтения, то есть они подают неверный бюллетень в систему голосования. Теоретики социального выбора давно рассматривают способы обойти эту проблему, например, предложение Бартольди, Тови и Трика в 1989 г., основанное на теории сложности вычислений. [11] Они рассмотрели правило Коупленда второго порядка (которое может быть вычислено за полиномиальное время) и доказали, что избиратель NP-полно решает, зная, как проголосовали все остальные, можно ли манипулировать таким образом, чтобы победителем стал какой-нибудь предпочтительный кандидат. То же свойство имеет место и для единственного передаваемого голоса . [12]
Следовательно, если принять широко распространенную гипотезу о том, что P ≠ NP , бывают случаи, когда полиномиального времени недостаточно, чтобы установить, возможна ли полезная манипуляция. Из-за этого правила голосования, которые связаны с NP-трудной проблемой манипуляции, «устойчивы» к манипуляции. Следует отметить, что эти результаты относятся только к худшему случаю : вполне возможно, что проблема манипуляции обычно легко решается и требует только сверхполиномиального времени для очень необычных входных данных. [13]
Другие темы
Турнирные решения
Решение турнира является правилом , которое возлагает на каждый турнир набор из победителей. Поскольку профиль предпочтений вызывает турнир через отношение большинства , каждое решение турнира также можно рассматривать как правило голосования, которое использует только информацию о результатах соревнований попарного большинства. [14] Было предложено множество турнирных решений, и теоретики вычислительной теории социального выбора изучили сложность связанных проблем определения победителя. [15] [1]
Ограничения предпочтений
Запрещенная привилегированная домены, такие как однопиковые или одного пересечения предпочтения, является важной областью исследований в теории общественного выбора , поскольку предпочтения из этих областей избежать парадокса Кондорса и , таким образом , можно обойти результаты невозможности , как теорема Эрьей и теорему Gibbard-Саттервейт . [16] [17] [18] [19] С вычислительной точки зрения такие ограничения области полезны для ускорения задач определения победителя, как вычислительно сложные правила с одним победителем, так и с несколькими победителями могут быть вычислены за полиномиальное время, когда предпочтения структурированы. соответственно. [20] [21] [22] [23] С другой стороны, проблема манипуляции также имеет тенденцию быть легкой в этих областях, поэтому защита сложности от манипуляций менее эффективна. [21] [24] Другая вычислительная проблема, связанная с ограничениями предпочтений, заключается в распознавании того, что данный профиль предпочтений принадлежит некоторой ограниченной области. Эта задача решается за полиномиальное время во многих случаях, в том числе для предпочтений с одним пиком и одним пересечением, но может быть трудной для более общих классов. [25] [26] [27]
Выборы многократных победителей
Хотя большинство традиционных правил голосования сосредоточено на выборе одного победителя, во многих ситуациях требуется выбрать несколько победителей. Это тот случай , когда фиксированного размера парламент или комитет должен быть избран, хотя multiwinner правила голосования также могут быть использованы для выбора набора рекомендаций или объектов или общий пакет элементов. Работа в области вычислительного социального выбора была сосредоточена на определении таких правил голосования, понимании их свойств и изучении сложности связанных с ними проблем определения победителя. [28] [29] [30] [31] [32]
Смотрите также
- Альгократия
- Алгоритмическая теория игр
- Разработка алгоритмического механизма
- Резка торта
- Справедливое деление
- Гедонические игры
Рекомендации
- ^ a b Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (25 апреля 2016 г.). Справочник по вычислительному социальному выбору . Издательство Кембриджского университета. ISBN 9781107060432.
- ^ Шульце, Маркус (11.07.2010). «Новый монотонный, независимый от клонов, реверсивно-симметричный и согласованный с кондорсе метод выборов с одним победителем». Социальный выбор и благосостояние . 36 (2): 267–303. DOI : 10.1007 / s00355-010-0475-4 . S2CID 1927244 .
- ^ Брилл, Маркус; Фишер, Феликс (01.01.2012). «Цена нейтральности для метода ранжированных пар» . Труды двадцать шестой конференции AAAI по искусственному интеллекту . AAAI'12: 1299–1305.
- ^ а б Bartholdi III, J .; Тови, Калифорния; Уловка, Массачусетс (1989-04-01). «Схемы голосования, по которым бывает сложно сказать, кто победил на выборах». Социальный выбор и благосостояние . 6 (2): 157–165. DOI : 10.1007 / BF00303169 . S2CID 154114517 .
- ^ Хемаспандра, Эдит; Спаковски, Хольгер; Фогель, Йорг (16 декабря 2005 г.). «Сложность выборов в Кемени» . Теоретическая информатика . 349 (3): 382–391. DOI : 10.1016 / j.tcs.2005.08.031 .
- ^ Хемаспандра, Эдит; Hemaspaandra, Lane A .; Роте, Йорг (1997). «Точный анализ выборов Доджсона: система голосования 1876 года Льюиса Кэрролла завершена для параллельного доступа к NP». J. ACM . 44 (6): 806–825. arXiv : cs / 9907036 . DOI : 10.1145 / 268999.269002 . S2CID 367623 .
- ^ Роте, Йорг; Спаковски, Хольгер; Фогель, Йорг (06.06.2003). «Точная сложность проблемы победителя на выборах молодежи». Теория вычислительных систем . 36 (4): 375–386. arXiv : cs / 0112021 . DOI : 10.1007 / s00224-002-1093-z . S2CID 3205730 .
- ^ Карагианнис, Иоаннис; Кови, Джейсон А .; Фельдман, Михал ; Хоман, Кристофер М .; Какламанис, Христос; Караниколас, Никос; Procaccia, Ariel D .; Розеншайн, Джеффри С. (01.08.2012). «О приближении выборов Доджсона и Янга» . Искусственный интеллект . 187 : 31–51. DOI : 10.1016 / j.artint.2012.04.004 .
- ^ Айлон, Нир; Чарикар, Моисей; Ньюман, Аланта (1 ноября 2008 г.). «Агрегирование противоречивой информации: ранжирование и кластеризация». J. ACM . 55 (5): 23: 1–23: 27. DOI : 10.1145 / 1411509.1411513 . S2CID 5674305 .
- ^ Бецлер, Надя; Товарищи, Майкл Р .; Го, Цзюн; Нидермайер, Рольф; Розамонд, Фрэнсис А. (23.06.2008). Флейшер, Рудольф; Сюй, Цзиньхуэй (ред.). Алгоритмы с фиксированными параметрами для оценок Кемени . Конспект лекций по информатике. Springer Berlin Heidelberg. С. 60–71. CiteSeerX 10.1.1.145.9310 . DOI : 10.1007 / 978-3-540-68880-8_8 . ISBN 9783540688655.
- ^ Бартольди, JJ; Тови, Калифорния; Уловка, Массачусетс (1989). «Вычислительная сложность манипулирования выборами». Социальный выбор и благосостояние . 6 (3): 227–241. DOI : 10.1007 / BF00295861 . S2CID 16158098 .
- ^ Бартольди, Джон Дж .; Орлин, Джеймс Б. (1991). «Единый передаваемый голос препятствует стратегическому голосованию». Социальный выбор и благосостояние . 8 (4): 341–354. CiteSeerX 10.1.1.127.97 . DOI : 10.1007 / BF00183045 . S2CID 17749613 .
- ^ Фалишевский, Петр; Прокачча, Ариэль Д. (23 сентября 2010 г.). «Война искусственного интеллекта с манипуляциями: победим ли мы?» . Журнал AI . 31 (4): 53–64. CiteSeerX 10.1.1.205.2873 . DOI : 10,1609 / aimag.v31i4.2314 .
- ^ Фишберн, П. (1977-11-01). «Функции социального выбора Кондорсе». Журнал SIAM по прикладной математике . 33 (3): 469–489. DOI : 10.1137 / 0133030 .
- ^ Луна, Джон В. (1968-01-01). Темы о турнирах . Холт, Райнхарт и Уинстон.
- ^ Блэк, Дункан (1948-01-01). «Об основаниях принятия групповых решений». Журнал политической экономии . 56 (1): 23–34. DOI : 10.1086 / 256633 . JSTOR 1825026 . S2CID 153953456 .
- ^ Ротштейн, П. (1990-12-01). «Порядок ограниченных предпочтений и правила большинства». Социальный выбор и благосостояние . 7 (4): 331–342. DOI : 10.1007 / BF01376281 . S2CID 153683957 .
- ^ Стрелка, Кеннет Дж. (26.06.2012). Социальный выбор и индивидуальные ценности . Издательство Йельского университета. ISBN 978-0300186987.
- ^ Сен, Амартия; Паттанаик, Прасанта К. (1969-08-01). «Необходимые и достаточные условия для рационального выбора при решении большинства». Журнал экономической теории . 1 (2): 178–202. DOI : 10.1016 / 0022-0531 (69) 90020-9 .
- ^ Элкинд, Эдит ; Лакнер, Мартин; Петерс, Доминик (01.07.2016). «Ограничения предпочтений в вычислительном социальном выборе: недавний прогресс» (PDF) . Материалы 25-й Международной конференции по искусственному интеллекту . IJCAI'16: 4062–4065.
- ^ а б Брандт, Феликс; Брилл, Маркус; Хемаспандра, Эдит; Хемаспандра, переулок (01.01.2015). «Обход комбинаторных защит: полиномиальные алгоритмы для однопиковых электоратов» . Журнал исследований искусственного интеллекта . 53 : 439–496. DOI : 10.1613 / jair.4647 .
- ^ Н., Бетцлер; А., Слинько; Дж., Ульманн (2013). «О вычислении полностью пропорционального представления» . Журнал исследований искусственного интеллекта . 47 (2013): 475–519. arXiv : 1402.0580 . Bibcode : 2014arXiv1402.0580B . DOI : 10.1613 / jair.3896 . S2CID 2839179 .
- ^ Сковрон, Петр; Ю, Лань; Фалишевский, Петр; Элкинд, Эдит (2015-03-02). «Сложность полностью пропорционального представительства для однонаправленных электоратов». Теоретическая информатика . 569 : 43–57. arXiv : 1307.1252 . DOI : 10.1016 / j.tcs.2014.12.012 .
- ^ Фалишевский, Петр; Хемаспандра, Эдит; Hemaspaandra, Lane A .; Роте, Йорг (01.02.2011). «Щит, которого никогда не было: общества с односторонними предпочтениями более открыты для манипуляции и контроля». Информация и вычисления . 209 (2): 89–107. arXiv : 0909.3257 . DOI : 10.1016 / j.ic.2010.09.001 .
- ^ Петерс, Доминик (25 февраля 2016 г.). «Признание многомерных евклидовых предпочтений». arXiv : 1602.08109 [ cs.GT ].
- ^ Дуаньон, JP; Фалмань, JC (1994-03-01). «Алгоритм с полиномиальным временем для одномерных разворачивающихся представлений». Журнал алгоритмов . 16 (2): 218–233. DOI : 10.1006 / jagm.1994.1010 .
- ^ Эскофье, Бруно; Ланг, Жером; Озтюрк, Мельтем (1 января 2008 г.). Однопиковая консистенция и ее сложность . Материалы конференции 2008 г. по ECAI 2008: 18-я Европейская конференция по искусственному интеллекту . С. 366–370. ISBN 9781586038915.
- ^ Сковрон, Петр; Фалишевский, Петр; Ланг, Джером (01.01.2015). Нахождение коллективного набора элементов: от пропорционального множественного представительства к групповой рекомендации . Труды двадцать девятой конференции AAAI по искусственному интеллекту . AAAI'15. 1402 . С. 2131–2137. arXiv : 1402.3044 . Bibcode : 2014arXiv1402.3044S . ISBN 978-0262511292.
- ^ Элкинд, Эдит ; Фалишевский, Петр; Сковрон, Петр; Слинко, Аркадий (01.01.2014). Свойства правил голосования мульти-победителей . Труды 2014 Международная конференция по автономных агентов и многоагентных систем . AAMAS '14. 1506 . С. 53–60. arXiv : 1506.02891 . Bibcode : 2015arXiv150602891E . ISBN 9781450327381.
- ^ Procaccia, Ariel D .; Rosenschein, Jeffrey S .; Зохар, Авив (19 апреля 2007 г.). «О сложности достижения пропорционального представительства». Социальный выбор и благосостояние . 30 (3): 353–362. DOI : 10.1007 / s00355-007-0235-2 . S2CID 18126521 .
- ^ Лу, Тайлер; Бутилье, Крейг (01.01.2011). Бюджетный социальный выбор: от консенсуса к индивидуальному принятию решений . Материалы двадцать второй международной совместной конференции по искусственному интеллекту . IJCAI'11. С. 280–286. DOI : 10.5591 / 978-1-57735-516-8 / IJCAI11-057 . ISBN 9781577355137.
- ^ Сковрон, Петр; Фалишевский, Петр; Слинко, Аркадий (01.05.2015). «Достижение полностью пропорционального представительства: приближаемость результатов». Искусственный интеллект . 222 : 67–103. arXiv : 1312,4026 . DOI : 10.1016 / j.artint.2015.01.003 . S2CID 467056 .
Внешние ссылки
- Веб-сайт COMSOC , предлагающий сборник материалов, связанных с вычислительным социальным выбором, например академические семинары, кандидатские диссертации и список рассылки.