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

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

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

Полезность той или иной системы голосования может быть сильно ограничена, если вычисление победителя выборов занимает очень много времени. Следовательно, важно разработать быстрые алгоритмы, которые могут оценивать правило голосования при вводе бюллетеней . Как это принято в теории сложности вычислений , алгоритм считается эффективным, если он занимает полиномиальное время . Многие популярные правила голосования можно оценить за полиномиальное время простым способом (т. Е. Подсчетом), например, подсчетом Борда , одобрительным голосованием или правилом множественности . Для таких правил, как метод Шульце или ранжированные пары , можно использовать более сложные алгоритмы, чтобы показать полиномиальное время выполнения. Однако некоторые системы голосования сложно оценить с помощью вычислений. В частности, определение победителя по методу Кемени-Янг , метод Доджсона и метод Юнга все NP-трудные проблемы. Это привело к разработке алгоритмов аппроксимации и управляемых алгоритмов с фиксированными параметрами для улучшения теоретического расчета таких проблем.

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

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

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

Другие темы

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

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

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

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

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

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

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

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

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

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