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

Вычислительный социальный выбор — это область на стыке теории социального выбора , теоретической информатики и анализа многоагентных систем . ^[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]

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

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

См. также

Ссылки

^ Jump up to: ^а ^б Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (25 апреля 2016 г.). Справочник по вычислительному социальному выбору . Издательство Кембриджского университета. ISBN 9781107060432 .
^ Шульце, Маркус (11 июля 2010 г.). «Новый монотонный, независимый от клонов, обратно-симметричный и последовательный по Кондорсе метод выборов с одним победителем». Социальный выбор и благосостояние . 36 (2): 267–303. дои : 10.1007/s00355-010-0475-4 . S2CID 1927244 .
^ Брилл, Маркус; Фишер, Феликс (1 января 2012 г.). «Цена нейтральности для метода ранжированных пар» . Материалы двадцать шестой конференции AAAI по искусственному интеллекту . АААИ'12: 1299–1305.
^ Jump up to: ^а ^б Бартольди III, Дж.; Тови, Калифорния; Трик, Массачусетс (1 апреля 1989 г.). «Схемы голосования, при которых может быть сложно определить, кто победил на выборах». Социальный выбор и благосостояние . 6 (2): 157–165. дои : 10.1007/BF00303169 . S2CID 154114517 .
^ Хемаспаандра, Эдит ; Спаковски, Хольгер; Фогель, Йорг (16 декабря 2005 г.). «Сложность выборов в Кемени» . Теоретическая информатика . 349 (3): 382–391. дои : 10.1016/j.tcs.2005.08.031 .
^ Хемаспаандра, Эдит ; Хемаспаандра, Лейн А.; Роте, Йорг (1997). «Точный анализ выборов Доджсона: система голосования Льюиса Кэрролла 1876 года готова для параллельного доступа к NP». Дж. АКМ . 44 (6): 806–825. arXiv : cs/9907036 . дои : 10.1145/268999.269002 . S2CID 367623 .
^ Роте, Йорг; Спаковски, Хольгер; Фогель, Йорг (6 июня 2003 г.). «Точная сложность проблемы победителя на молодых выборах». Теория вычислительных систем . 36 (4): 375–386. arXiv : cs/0112021 . дои : 10.1007/s00224-002-1093-z . S2CID 3205730 .
^ Караяннис, Иоаннис; Кови, Джейсон А.; Фельдман, Михал ; Хоман, Кристофер М.; Какламанис, Христос; Караниколас, Никос; Прокачча, Ариэль Д.; Розеншайн, Джеффри С. (1 августа 2012 г.). «О приближаемости выборов Доджсона и Янга» . Искусственный интеллект . 187 : 31–51. дои : 10.1016/j.artint.2012.04.004 .
^ Эйлон, Нир; Чарикар, Моисей; Ньюман, Аланта (1 ноября 2008 г.). «Агрегирование противоречивой информации: ранжирование и кластеризация». Дж. АКМ . 55 (5): 23:1–23:27. дои : 10.1145/1411509.1411513 . S2CID 5674305 .
^ Бецлер, Надя; Товарищи, Майкл Р.; Го, Цзюн; Нидермайер, Рольф ; Розамонд, Фрэнсис А. (23 июня 2008 г.). «Алгоритмы с фиксированными параметрами для оценки Кемени». У Флейшера, Рудольфа; Сюй, Цзиньхуэй (ред.). Алгоритмические аспекты информации и управления . Конспекты лекций по информатике. Том. 5034. Шпрингер Берлин Гейдельберг. стр. 60–71. CiteSeerX 10.1.1.145.9310 . дои : 10.1007/978-3-540-68880-8_8 . ISBN 9783540688655 .
^ Фишберн, П. (1 ноября 1977 г.). «Функции социального выбора Кондорсе». SIAM Journal по прикладной математике . 33 (3): 469–489. дои : 10.1137/0133030 .
^ Ласлье, Жан-Франсуа (1997). Решения для турниров и голосование большинством . Спрингер Верлаг.
^ Мун, Джон В. (1 января 1968 г.). Темы о турнирах . Холт, Райнхарт и Уинстон.
^ Блэк, Дункан (1 января 1948 г.). «Обоснование группового принятия решений». Журнал политической экономии . 56 (1): 23–34. дои : 10.1086/256633 . JSTOR 1825026 . S2CID 153953456 .
^ Ротштейн, П. (1 декабря 1990 г.). «Порядок ограниченных предпочтений и правило большинства». Социальный выбор и благосостояние . 7 (4): 331–342. дои : 10.1007/BF01376281 . S2CID 153683957 .
^ Эрроу, Кеннет Дж. (26 июня 2012 г.). Социальный выбор и индивидуальные ценности . Издательство Йельского университета. ISBN 978-0300186987 .
^ Сен, Амартья; Паттанаик, Прасанта К. (1 августа 1969 г.). «Необходимые и достаточные условия рационального выбора при решении большинства». Журнал экономической теории . 1 (2): 178–202. дои : 10.1016/0022-0531(69)90020-9 .
^ Элкинд, Эдит ; Лакнер, Мартин; Петерс, Доминик (01 июля 2016 г.). «Ограничения предпочтений в вычислительном социальном выборе: недавний прогресс» (PDF) . Материалы 25-й Международной конференции по искусственному интеллекту . IJCAI'16: 4062–4065.
^ Jump up to: ^а ^б Брандт, Феликс; Брилл, Маркус; Хемаспаандра, Эдит ; Хемаспаандра, Лейн (01 января 2015 г.). «Обход комбинаторной защиты: алгоритмы полиномиального времени для однопиковых электоратов» . Журнал исследований искусственного интеллекта . 53 : 439–496. дои : 10.1613/jair.4647 . hdl : 1802/10425 .
^ Н., Бетцлер; А., Слинько; Дж., Ульманн (2013). «О расчете полностью пропорционального представительства» . Журнал исследований искусственного интеллекта . 47 (2013): 475–519. arXiv : 1402.0580 . Бибкод : 2014arXiv1402.0580B . дои : 10.1613/jair.3896 . S2CID 2839179 .
^ Сковрон, Петр; Ю, Лан; Фалишевский, Петр; Элкинд, Эдит (2 марта 2015 г.). «Сложность полностью пропорционального представительства для избирательных округов с одним пересечением». Теоретическая информатика . 569 : 43–57. arXiv : 1307.1252 . дои : 10.1016/j.tcs.2014.12.012 . S2CID 5348844 .
^ Фалишевский, Петр; Хемаспаандра, Эдит ; Хемаспаандра, Лейн А.; Роте, Йорг (01 февраля 2011 г.). «Щит, которого никогда не было: общества с одновершинными предпочтениями более открыты для манипуляций и контроля». Информация и вычисления . 209 (2): 89–107. arXiv : 0909.3257 . дои : 10.1016/j.ic.2010.09.001 .
^ Петерс, Доминик (25 февраля 2016 г.). «Распознавание многомерных евклидовых предпочтений». arXiv : 1602.08109 [ cs.GT ].
^ Дуаньон, Япония; Фальмань, JC (1 марта 1994 г.). «Алгоритм полиномиального времени для одномерных представлений развертки» (PDF) . Журнал алгоритмов . 16 (2): 218–233. дои : 10.1006/jagm.1994.1010 .
^ Эскофье, Бруно; Ланг, Жером; Озтюрк, Мелтем (1 января 2008 г.). «Одновершинная согласованность и ее сложность» . Материалы конференции 2008 г. по ECAI 2008: 18-я Европейская конференция по искусственному интеллекту : 366–370. ISBN 9781586038915 .

Внешние ссылки

Веб-сайт COMSOC , предлагающий коллекцию материалов, связанных с вычислительным социальным выбором, таких как академические семинары, докторские диссертации и список рассылки.

[:1-1] Jump up to: ^а ^б Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (25 апреля 2016 г.). Справочник по вычислительному социальному выбору . Издательство Кембриджского университета. ISBN 9781107060432 .

[2] Шульце, Маркус (11 июля 2010 г.). «Новый монотонный, независимый от клонов, обратно-симметричный и последовательный по Кондорсе метод выборов с одним победителем». Социальный выбор и благосостояние . 36 (2): 267–303. дои : 10.1007/s00355-010-0475-4 . S2CID 1927244 .

[3] Брилл, Маркус; Фишер, Феликс (1 января 2012 г.). «Цена нейтральности для метода ранжированных пар» . Материалы двадцать шестой конференции AAAI по искусственному интеллекту . АААИ'12: 1299–1305.

[:0-4] Jump up to: ^а ^б Бартольди III, Дж.; Тови, Калифорния; Трик, Массачусетс (1 апреля 1989 г.). «Схемы голосования, при которых может быть сложно определить, кто победил на выборах». Социальный выбор и благосостояние . 6 (2): 157–165. дои : 10.1007/BF00303169 . S2CID 154114517 .

[5] Хемаспаандра, Эдит ; Спаковски, Хольгер; Фогель, Йорг (16 декабря 2005 г.). «Сложность выборов в Кемени» . Теоретическая информатика . 349 (3): 382–391. дои : 10.1016/j.tcs.2005.08.031 .

[6] Хемаспаандра, Эдит ; Хемаспаандра, Лейн А.; Роте, Йорг (1997). «Точный анализ выборов Доджсона: система голосования Льюиса Кэрролла 1876 года готова для параллельного доступа к NP». Дж. АКМ . 44 (6): 806–825. arXiv : cs/9907036 . дои : 10.1145/268999.269002 . S2CID 367623 .

[7] Роте, Йорг; Спаковски, Хольгер; Фогель, Йорг (6 июня 2003 г.). «Точная сложность проблемы победителя на молодых выборах». Теория вычислительных систем . 36 (4): 375–386. arXiv : cs/0112021 . дои : 10.1007/s00224-002-1093-z . S2CID 3205730 .

[8] Караяннис, Иоаннис; Кови, Джейсон А.; Фельдман, Михал ; Хоман, Кристофер М.; Какламанис, Христос; Караниколас, Никос; Прокачча, Ариэль Д.; Розеншайн, Джеффри С. (1 августа 2012 г.). «О приближаемости выборов Доджсона и Янга» . Искусственный интеллект . 187 : 31–51. дои : 10.1016/j.artint.2012.04.004 .

[9] Эйлон, Нир; Чарикар, Моисей; Ньюман, Аланта (1 ноября 2008 г.). «Агрегирование противоречивой информации: ранжирование и кластеризация». Дж. АКМ . 55 (5): 23:1–23:27. дои : 10.1145/1411509.1411513 . S2CID 5674305 .

[10] Бецлер, Надя; Товарищи, Майкл Р.; Го, Цзюн; Нидермайер, Рольф ; Розамонд, Фрэнсис А. (23 июня 2008 г.). «Алгоритмы с фиксированными параметрами для оценки Кемени». У Флейшера, Рудольфа; Сюй, Цзиньхуэй (ред.). Алгоритмические аспекты информации и управления . Конспекты лекций по информатике. Том. 5034. Шпрингер Берлин Гейдельберг. стр. 60–71. CiteSeerX 10.1.1.145.9310 . дои : 10.1007/978-3-540-68880-8_8 . ISBN 9783540688655 .

[11] Фишберн, П. (1 ноября 1977 г.). «Функции социального выбора Кондорсе». SIAM Journal по прикладной математике . 33 (3): 469–489. дои : 10.1137/0133030 .

[12] Ласлье, Жан-Франсуа (1997). Решения для турниров и голосование большинством . Спрингер Верлаг.

[13] Мун, Джон В. (1 января 1968 г.). Темы о турнирах . Холт, Райнхарт и Уинстон.

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

[15] Ротштейн, П. (1 декабря 1990 г.). «Порядок ограниченных предпочтений и правило большинства». Социальный выбор и благосостояние . 7 (4): 331–342. дои : 10.1007/BF01376281 . S2CID 153683957 .

[16] Эрроу, Кеннет Дж. (26 июня 2012 г.). Социальный выбор и индивидуальные ценности . Издательство Йельского университета. ISBN 978-0300186987 .

[17] Сен, Амартья; Паттанаик, Прасанта К. (1 августа 1969 г.). «Необходимые и достаточные условия рационального выбора при решении большинства». Журнал экономической теории . 1 (2): 178–202. дои : 10.1016/0022-0531(69)90020-9 .

[18] Элкинд, Эдит ; Лакнер, Мартин; Петерс, Доминик (01 июля 2016 г.). «Ограничения предпочтений в вычислительном социальном выборе: недавний прогресс» (PDF) . Материалы 25-й Международной конференции по искусственному интеллекту . IJCAI'16: 4062–4065.

[:2-19] Jump up to: ^а ^б Брандт, Феликс; Брилл, Маркус; Хемаспаандра, Эдит ; Хемаспаандра, Лейн (01 января 2015 г.). «Обход комбинаторной защиты: алгоритмы полиномиального времени для однопиковых электоратов» . Журнал исследований искусственного интеллекта . 53 : 439–496. дои : 10.1613/jair.4647 . hdl : 1802/10425 .

[20] Н., Бетцлер; А., Слинько; Дж., Ульманн (2013). «О расчете полностью пропорционального представительства» . Журнал исследований искусственного интеллекта . 47 (2013): 475–519. arXiv : 1402.0580 . Бибкод : 2014arXiv1402.0580B . дои : 10.1613/jair.3896 . S2CID 2839179 .

[21] Сковрон, Петр; Ю, Лан; Фалишевский, Петр; Элкинд, Эдит (2 марта 2015 г.). «Сложность полностью пропорционального представительства для избирательных округов с одним пересечением». Теоретическая информатика . 569 : 43–57. arXiv : 1307.1252 . дои : 10.1016/j.tcs.2014.12.012 . S2CID 5348844 .

[22] Фалишевский, Петр; Хемаспаандра, Эдит ; Хемаспаандра, Лейн А.; Роте, Йорг (01 февраля 2011 г.). «Щит, которого никогда не было: общества с одновершинными предпочтениями более открыты для манипуляций и контроля». Информация и вычисления . 209 (2): 89–107. arXiv : 0909.3257 . дои : 10.1016/j.ic.2010.09.001 .

[23] Петерс, Доминик (25 февраля 2016 г.). «Распознавание многомерных евклидовых предпочтений». arXiv : 1602.08109 [ cs.GT ].

[:3-24] Дуаньон, Япония; Фальмань, JC (1 марта 1994 г.). «Алгоритм полиномиального времени для одномерных представлений развертки» (PDF) . Журнал алгоритмов . 16 (2): 218–233. дои : 10.1006/jagm.1994.1010 .

[25] Эскофье, Бруно; Ланг, Жером; Озтюрк, Мелтем (1 января 2008 г.). «Одновершинная согласованность и ее сложность» . Материалы конференции 2008 г. по ECAI 2008: 18-я Европейская конференция по искусственному интеллекту : 366–370. ISBN 9781586038915 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]