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

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

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

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

Представление предпочтений

Важным различием между правилами голосования является формат бюллетеней, используемых избирателями для представления своих предпочтений. Два наиболее распространенных формата — это бюллетени одобрения и порядковые ранги.

В бюллетенях одобрения каждый избиратель одобряет некоторых кандидатов, которые ему нравятся. Дальнейшей дифференциации или иерархии среди одобренных кандидатов нет. То же самое касается и не одобренных кандидатов. Таким образом, такие бюллетени также называются дихотомическими . Бюллетени одобрения используются, например, при голосовании по удовлетворению одобрения и пропорциональном голосовании одобрения .

Напротив, порядковые ранги требуют от избирателя ранжировать всех кандидатов от лучшего к худшему. Этот тип бюллетеня используется, например, в правиле Борда или в голосовании Баклина .

В литературе описано множество других типов форматов бюллетеней, например, бюллетени с усеченными рангами, трихотомические бюллетени или бюллетени с кардинальной полезностью.

Некоторые исследования в области вычислительного социального выбора сосредоточены на том, насколько репрезентативны форматы бюллетеней, и на разработке выразительных, но компактных форматов бюллетеней. Это особенно важно в комбинаторных условиях, таких как голосование с несколькими победителями .

Другие темы

Решения для турниров

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

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

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

Выборы с несколькими победителями

В то время как большинство традиционных правил голосования фокусируются на выборе одного победителя, во многих ситуациях требуется выбор нескольких победителей. Это тот случай, когда необходимо избрать парламент или комитет фиксированного размера, хотя правила голосования с несколькими победителями также могут использоваться для выбора набора рекомендаций или объектов или общего набора элементов. Работа в области вычислительного социального выбора была сосредоточена на определении таких правил голосования, понимании их свойств и изучении сложности связанных с ними проблем определения победителя. См. голосование с несколькими победителями .

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

Ссылки

  1. ^ ab Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016-04-25). Справочник по вычислительному социальному выбору. Cambridge University Press. ISBN 9781107060432.
  2. ^ Шульце, Маркус (2010-07-11). "Новый монотонный, клононезависимый, реверсивно симметричный и кондорсе-согласованный метод выборов с одним победителем". Social Choice and Welfare . 36 (2): 267– 303. doi :10.1007/s00355-010-0475-4. S2CID  1927244.
  3. ^ Брилл, Маркус; Фишер, Феликс (2012-01-01). «Цена нейтральности для метода ранжированных пар». Труды Двадцать шестой конференции AAAI по искусственному интеллекту . AAAI'12: 1299– 1305.
  4. ^ ab Bartholdi III, J.; Tovey, CA; Trick, MA (1989-04-01). «Схемы голосования, в которых может быть трудно сказать, кто победил на выборах». Social Choice and Welfare . 6 (2): 157– 165. doi :10.1007/BF00303169. S2CID  154114517.
  5. ^ Хемаспаандра, Эдит ; Спаковски, Хольгер; Фогель, Йорг (16 декабря 2005 г.). «Сложность выборов в Кемени». Теоретическая информатика . 349 (3): 382–391 . doi : 10.1016/j.tcs.2005.08.031 .
  6. ^ Хемаспаандра, Эдит ; Хемаспаандра, Лейн А.; Роте, Йорг (1997). «Точный анализ выборов Доджсона: система голосования Льюиса Кэрролла 1876 года завершена для параллельного доступа к NP». J. ACM . 44 (6): 806–825 . arXiv : cs/9907036 . doi :10.1145/268999.269002. S2CID  367623.
  7. ^ Роте, Йорг; Спаковски, Хольгер; Фогель, Йорг (2003-06-06). «Точная сложность проблемы победителя для молодых выборов». Теория вычислительных систем . 36 (4): 375–386 . arXiv : cs/0112021 . doi :10.1007/s00224-002-1093-z. S2CID  3205730.
  8. ^ Caragiannis, Ioannis; Covey, Jason A.; Feldman, Michal ; Homan, Christopher M.; Kaklamanis, Christos; Karanikolas, Nikos; Procaccia, Ariel D.; Rosenschein, Jeffrey S. (2012-08-01). «Об аппроксимируемости выборов Доджсона и Янга». Искусственный интеллект . 187 : 31–51 . doi : 10.1016/j.artint.2012.04.004 .
  9. ^ Ailon, Nir; Charikar, Moses; Newman, Alantha (2008-11-01). «Aggregating Inconsistent Information: Ranking and Clustering». J. ACM . 55 (5): 23:1–23:27. doi :10.1145/1411509.1411513. S2CID  5674305.
  10. ^ Betzler, Nadja; Fellows, Michael R.; Guo, Jiong; Niedermeier, Rolf ; Rosamond, Frances A. (2008-06-23). ​​"Алгоритмы с фиксированными параметрами для оценок Кемени". В Fleischer, Rudolf; Xu, Jinhui (ред.). Алгоритмические аспекты в информации и управлении . Конспект лекций по информатике. Том 5034. Springer Berlin Heidelberg. стр.  60–71 . CiteSeerX 10.1.1.145.9310 . doi :10.1007/978-3-540-68880-8_8. ISBN  9783540688655.
  11. ^ Фишберн, П. (1 ноября 1977 г.). «Функции общественного выбора Кондорсе». Журнал SIAM по прикладной математике . 33 (3): 469– 489. doi :10.1137/0133030.
  12. ^ Ласлье, Жан-Франсуа (1997). Решения турниров и голосование большинства . Springer Verlag.
  13. ^ Мун, Джон У. (1968-01-01). Темы о турнирах. Холт, Райнхарт и Уинстон.
  14. ^ Блэк, Дункан (1948-01-01). «О рациональности группового принятия решений». Журнал политической экономии . 56 (1): 23– 34. doi :10.1086/256633. JSTOR  1825026. S2CID  153953456.
  15. ^ Ротштейн, П. (1990-12-01). «Порядок ограниченных предпочтений и правило большинства». Социальный выбор и благосостояние . 7 (4): 331– 342. doi :10.1007/BF01376281. S2CID  153683957.
  16. ^ Эрроу, Кеннет Дж. (2012-06-26). Социальный выбор и индивидуальные ценности. Yale University Press. ISBN 978-0300186987.
  17. ^ Сен, Амартья; Паттанаик, Прасанта К (1969-08-01). «Необходимые и достаточные условия для рационального выбора при решении большинства». Журнал экономической теории . 1 (2): 178– 202. doi :10.1016/0022-0531(69)90020-9.
  18. ^ Элкинд, Эдит ; Лакнер, Мартин; Питерс, Доминик (2016-07-01). «Ограничения предпочтений в вычислительном социальном выборе: недавний прогресс» (PDF) . Труды 25-й Международной конференции по искусственному интеллекту . IJCAI'16: 4062– 4065.
  19. ^ ab Брандт, Феликс; Брилл, Маркус; Хемаспандра, Эдит ; Хемаспандра, Лейн (2015-01-01). «Обход комбинаторной защиты: полиномиальные алгоритмы для электоратов с одним пиком». Журнал исследований искусственного интеллекта . 53 : 439–496 . doi : 10.1613/jair.4647 . hdl : 1802/10425 .
  20. ^ Н., Бетцлер; А., Слинко; Дж., Ульманн (2013). «О вычислении полностью пропорционального представления». Журнал исследований искусственного интеллекта . 47 (2013): 475–519 . arXiv : 1402.0580 . Bibcode : 2014arXiv1402.0580B. doi : 10.1613/jair.3896. S2CID  2839179.
  21. ^ Сковрон, Петр; Ю, Лан; Фалишевский, Петр; Элкинд, Эдит (2015-03-02). «Сложность полностью пропорционального представительства для электоратов с одним пересечением». Теоретическая информатика . 569 : 43–57 . arXiv : 1307.1252 . doi : 10.1016/j.tcs.2014.12.012. S2CID  5348844.
  22. ^ Фалишевски, Петр; Хемаспандра, Эдит ; Хемаспандра, Лейн А.; Роте, Йорг (2011-02-01). «Щит, которого никогда не было: общества с однопиковыми предпочтениями более открыты для манипуляций и контроля». Информация и вычисления . 209 (2): 89– 107. arXiv : 0909.3257 . doi :10.1016/j.ic.2010.09.001.
  23. ^ Питерс, Доминик (25.02.2016). «Распознавание многомерных евклидовых предпочтений». arXiv : 1602.08109 [cs.GT].
  24. ^ Дуаньон, Дж. П.; Фалмань, Дж. К. (1994-03-01). "Алгоритм полиномиального времени для одномерных разворачивающихся представлений" (PDF) . Журнал алгоритмов . 16 (2): 218– 233. doi :10.1006/jagm.1994.1010.
  25. ^ Эскофье, Бруно; Ланг, Жером; Озтюрк, Мелтем (2008-01-01). «Одновершинная согласованность и ее сложность». Труды конференции 2008 года по ECAI 2008: 18-я Европейская конференция по искусственному интеллекту : 366–370 . ISBN 9781586038915.
  • Веб-сайт COMSOC, предлагающий коллекцию материалов, связанных с вычислительным социальным выбором, таких как академические семинары, докторские диссертации и список рассылки.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Computational_social_choice&oldid=1251379390"