Социальный выбор, теорема стрелы и открытые проблемы?

22

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

Прочитав об исходных результатах, я спросил себя о том, что происходит с предпочтениями частичного порядка, ответ в статье Pini et al. : Агрегирование частично упорядоченных предпочтений: невозможность и возможность результатов . Затем я подумал, можно ли найти характеристику допустимых функций социального выбора. И снова кто-то сделал это ( Полная характеристика функций, удовлетворяющих условиям теоремы Эрроу, Мосселя и Тамуза). Я не буду приводить полный список, но любые проблемы, связанные с социальным выбором, я могу придумать, где все решено за последние 5 лет :(

Итак, знаете ли вы, существует ли опрос о том, что было сделано недавно на местах, а что не было сделано?

Другой вопрос: знаете ли вы о сложностях и проблемах, связанных с социальным выбором (например, сложность поиска наибольшего подмножества пользователей, совместимых хотя бы с одной функцией социального выбора, или вопрос такого рода).

Сильвен Пейроннет
источник

Ответы:

18

Ваш вопрос очень вовремя, потому что в последнем выпуске CACM есть статья, которая делает именно это: http://cacm.acm.org/magazines/2010/11/100640-using-complexity-to-protect-elections /полный текст

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

Суреш Венкат
источник
1
Я принимаю этот, потому что это наиболее одобренный, но все ответы были интересны для меня. Спасибо вам всем!
Сильвен Пейроннет
12

Есть много проблем сложности, которые связаны со многими темами, которые возникают в так называемой теории социального выбора. Они включают в себя сложность определения того, кто является победителем, когда конкретный метод используется для объединения бюллетеней определенного типа в выбор для общества. Есть также проблемы сложности, связанные с попыткой найти способ голосовать стратегически (вместо использования своих истинных предпочтений), когда может быть доступна информация о предпочтениях другого избирателя, когда конкретный метод используется в надежде получить лучший результат для конкретного человека. или группа людей. Сложность также возникает при разработке «безопасных» систем онлайн-голосования.

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

Дональд Саари, Решения и выборы, Кембридж У. Пресс, 2001.

Дональд Саари, Уничтожение диктаторов, демистификация парадоксов голосования, Cambridge U. Press, 2008.

Алан Тейлор, «Социальный выбор и математика манипулирования», Cambridge U. Press, 2005.

Иосиф Малкевич
источник
9

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

http://www.illc.uva.nl/COMSOC/

ха
источник
7

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

Мой общий совет для студентов, изучающих экономику: «держитесь подальше от теоремы, если только вы не можете связать свой вклад с некоторыми недавними идеями (например, аксиомами, которые были предложены недавно, решениями, которые были немного изучены, и поведенческими предположениями в моде) Попытайтесь найти проблему, не связанную с теоремой Эрроу. Таких проблем много, даже в теории социального выбора ". Только после того, как у вас появится общее представление о том, какую проблему вы хотите решить, ознакомьтесь со Справочником социального выбора и социального обеспечения .

Вычислительные проблемы могут быть одной из таких «недавних» идей. Хотя исследование сложности (правил или манипуляций, или решения и т. Д.) Является основной задачей для компьютерных ученых (как это было предложено другими), существуют документы выхода (такие как Mihara, 1997, Теорема Эрроу и вычислимость Тьюринга). , Экономическая теория 10: 257-276), которая изучает (фундаментальную?) Проблему вычислимости в рамках Эрроу. ;-)

Позвольте мне прокомментировать две предложенные вами проблемы.

  1. Я не уверен, что теоретики социального выбора пренебрегали частичными заказами. Если они это сделали, то сделали это, вероятно, потому, что «пристрастность» может быть выражена строгими предпочтениями (как мы это делаем в Кумабе и Михаре, «Теория агрегации предпочтений без ацикличности: ядро ​​без недовольства большинства», « Игры и экономическое поведение» в прессе). (В этом случае лучше забыть о слабом предпочтении R или определить его по-другому [чтобы оно не стало полным): определяя xRy [x слабо предпочтительнее y], если не yPx [не y предпочтительнее x], мы имеем P асимметричен, если R завершен !)

  2. Некоторые авторы нет, но я полагаю, что большинство теоретиков социального выбора достаточно осторожны, чтобы не утверждать, что любая диктаторская функция социального обеспечения удовлетворяет МИС. Например, я говорю (Михара, 1997), что в рамках функций социального обеспечения, удовлетворяющих МИС , правило является диктаторским, если оно удовлетворяет определенному условию. Таким образом, они знали, что проблема открыта, но, вероятно, не были заинтересованы в дальнейшей классификации диктаторских функций. (Возможно, Моссель и Тамуз могут прокомментировать опечатки Армстронга, на которые ссылается Михара. Он идентифицирует последовательность диктаторов или ультрафильтров.) Это предлагает другую стратегию исследования (которую я не могу рекомендовать): попытаться найти проблему, которая была бы неинтересна теоретикам социального выбора.

Х. Рейджу Михара
источник