Вычислительный социальный выбор - Computational social choice

Вычислительный социальный выбор это поле на пересечении теория социального выбора, теоретическая информатика, а анализ мультиагентные системы.[1] Он состоит из анализа проблем, возникающих в результате агрегирования предпочтения группы агентов с вычислительной точки зрения. В частности, вычислительный социальный выбор связан с эффективным вычислением результатов правила голосования, с вычислительной сложностью различных форм манипуляция, а также вопросы, связанные с проблемой представляющий и выявление предпочтений в комбинаторных условиях.

Определение победителя

Полезность конкретного система голосования могут быть сильно ограничены, если вычисление победителя выборов занимает очень много времени. Поэтому важно быстро разрабатывать алгоритмы которые могут оценить правило голосования, если дано бюллетени как вход. Как это принято в теория сложности вычислений, алгоритм считается эффективным, если он требует полиномиальное время. Многие популярные правила голосования могут быть вычислены за полиномиальное время простым способом (т. Е. Подсчетом), например Граф Борда, одобрительное голосование, или правило множественности. Для таких правил, как Метод Шульце или ранжированные пары, можно использовать более сложные алгоритмы для отображения полиномиального времени выполнения.[2][3] Однако некоторые системы голосования сложно оценить с помощью вычислений.[4] В частности, определение победителя для Метод Кемени-Янга, Метод Доджсона, и Метод Юнга все NP-сложные проблемы.[4][5][6][7] Это привело к развитию аппроксимационные алгоритмы и управляемые алгоритмы с фиксированными параметрами улучшить теоретический расчет таких задач.[8][9][10]

Жесткость манипуляции

Посредством Теорема Гиббарда-Саттертуэйта, все нетривиальные правила голосования можно манипулируют в том смысле, что избиратели иногда могут добиться лучшего результата, искажая свои предпочтения, то есть они подают неправдивые бюллетень к системе голосования. Теоретики социального выбора давно рассматривали способы обойти эту проблему, например, предложение Бартольди, Тови и Трика в 1989 г., основанное на теории сложности вычислений.[11] Они считали правило Коупленда второго порядка (который можно оценить за полиномиальное время), и доказал, что это НП-полный избиратель, зная, как проголосовали все остальные, должен решить, можно ли манипулировать таким образом, чтобы победителем стал какой-нибудь предпочтительный кандидат. То же свойство имеет место для единственный передаваемый голос.[12]

Следовательно, если принять широко распространенную гипотезу о том, что P ≠ NP, есть случаи, когда полиномиального времени недостаточно, чтобы установить, возможна ли полезная манипуляция. Из-за этого правила голосования, которые связаны с NP-трудной проблемой манипуляции, «устойчивы» к манипуляции. Следует отметить, что эти результаты относятся только к худший случай: вполне возможно, что проблема манипуляции обычно легко решается и требует только сверхполиномиального времени на очень необычных входных данных.[13]

Другие темы

Турнирные решения

А турнирное решение это правило, которое назначает каждому турнир набор победителей. Поскольку профиль предпочтений стимулирует турнир через отношение большинства, каждое турнирное решение также можно рассматривать как правило голосования, которое использует только информацию о результатах соревнований попарного большинства.[14] Было предложено множество турнирных решений, и теоретики вычислительной теории социального выбора изучили сложность связанных проблем определения победителя.[15][1]

Ограничения предпочтений

Домены с ограниченным доступом, например односторонний или одинарный переход предпочтения, являются важной областью изучения в теория социального выбора, поскольку предпочтения из этих доменов избегают Парадокс Кондорсе и, таким образом, может обойти такие результаты невозможности, как Теорема Эрроу и Теорема Гиббарда-Саттертуэйта.[16][17][18][19] С вычислительной точки зрения такие ограничения области полезны для ускорения задач определения победителя, как вычислительно трудные правила с одним победителем, так и с несколькими победителями могут быть вычислены за полиномиальное время, если предпочтения структурированы соответствующим образом.[20][21][22][23] С другой стороны, проблема манипулирования в этих областях также обычно упрощается, поэтому защита от манипуляций менее эффективна.[21][24] Другая вычислительная проблема, связанная с ограничениями предпочтений, заключается в распознавании того, что данный профиль предпочтений принадлежит некоторой ограниченной области. Эта задача решается за полиномиальное время во многих случаях, в том числе для предпочтений с одним пиком и с одним пересечением, но может быть трудной для более общих классов.[25][26][27]

Выборы многократных победителей

Хотя большинство традиционных правил голосования сосредоточено на выборе одного победителя, во многих ситуациях требуется выбрать несколько победителей. Это тот случай, когда фиксированный размер парламент или комитет подлежит избранию, хотя правила голосования нескольких победителей также могут использоваться для выбора набора рекомендации или удобства или общий набор предметов. Работа в области вычислительного социального выбора была сосредоточена на определении таких правил голосования, понимании их свойств и изучении сложности связанных с ними проблем определения победителя.[28][29][30][31][32]

Смотрите также

Рекомендации

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

внешняя ссылка

  • Сайт КОМСОК, предлагающий сборник материалов, связанных с вычислительным социальным выбором, например академические семинары, кандидатские диссертации и список рассылки.