В кооперативной теории игр и теории общественного выбора , то число Накамура измеряет степень рациональности правил агрегирования предпочтений (правила коллективного принятия решений), такие как правила голосования. Это индикатор того, в какой степени правило агрегирования может давать четко определенный выбор.
- Если количество альтернатив (кандидатов; вариантов) для выбора меньше этого числа, то рассматриваемое правило без проблем определит «лучшие» альтернативы.
В отличие,
- если количество альтернатив больше или равно этому количеству, правило не сможет определить «лучшие» альтернативы для некоторой модели голосования (т. е. для некоторого профиля ( кортежа ) индивидуальных предпочтений), потому что возникнет парадокс голосования ( цикл генерируется таким как альтернатива социально предпочитаемый альтернативе , к , а также к ).
Чем больше число Накамуры у правила, тем с большим количеством альтернатив правило может рационально работать. Например, поскольку (за исключением случая четырех человек (избирателей)) правило с числом большинства Накамуры равняется трем, это правило может рационально рассматривать до двух альтернатив (не вызывая парадокса). Номер назван в честь Кендзиро Накамуры (1947–1979), японского теоретика игр, который доказал вышеупомянутый факт, что рациональность коллективного выбора критически зависит от количества альтернатив. [1]
Обзор
Чтобы ввести точное определение числа Накамуры, мы приводим пример «игры» (лежащей в основе рассматриваемого правила), которой будет присвоен номер Накамуры. Предположим, что набор индивидов состоит из индивидов 1, 2, 3, 4 и 5. За правилом большинства стоит следующая совокупность («решающих») коалиций (подмножеств индивидов), состоящая как минимум из трех членов:
- {{1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5}, { 2,3,4}, {2,3,5}, {2,4,5}, {3,4,5}, {1,2,3,4}, {1,2,3,5} , {1,2,4,5}, {1,3,4,5}, {2,3,4,5}, {1,2,3,4,5}}
Номер Накамуры можно присвоить таким коллекциям, которые мы называем простыми играми . Точнее, простая игра - это просто произвольный набор коалиций; коалиции, входящие в коллекцию, считаются выигрышными ; остальные проигрывают . Если все (как минимум трое, в приведенном выше примере) члены победившей коалиции предпочитают альтернативу x альтернативе y, тогда общество (из пяти человек, в приведенном выше примере) примет тот же рейтинг ( социальное предпочтение ).
Число Накамуры в простой игре определяется как минимальное количество выигрышных коалиций с пустым пересечением . (Пересекая это количество выигрышных коалиций, иногда можно получить пустое множество. Но, пересекая меньшее, чем это число, нельзя получить пустое множество.) Число Накамуры в простой игре выше, например, равно трем, поскольку пересечение любых двух выигрышных коалиций содержит по крайней мере одного человека, но пересечение следующих трех выигрышных коалиций пусто:, , .
Теорема Накамуры (1979 [2] ) дает следующее необходимое (также достаточное, если множество альтернатив конечно) условие для того, чтобы простая игра имела непустое «ядро» (множество социально «лучших» альтернатив) для всех профилей индивидуума. предпочтения: количество альтернатив меньше числа Накамуры в простой игре. Здесь ядром простой игры по профилю предпочтений является набор всех альтернатив. так что нет альтернативы что каждый человек в выигрышной коалиции предпочитает ; то есть набор максимальных элементов социального предпочтения. Для приведенного выше примера большинства игр теорема подразумевает, что ядро будет пустым (никакая альтернатива не будет считаться «лучшей») для некоторого профиля, если есть три или более альтернатив.
Существуют варианты теоремы Накамуры, которые обеспечивают условие непустости ядра (i) для всех профилей ациклических предпочтений; (ii) для всех профилей переходных предпочтений; и (iii) для всех профилей линейных порядков . Существует вариант другого типа (Kumabe and Mihara, 2011 [3] ), в котором отсутствует ацикличность , слабое требование рациональности. Вариант дает условие непустости ядра для всех профилей предпочтений, имеющих максимальные элементы .
Для ранжирования альтернатив существует очень известный результат, называемый « теоремой невозможности Эрроу » в теории социального выбора, который указывает на сложность ранжирования для группы людей трех или более альтернатив. Для выбора из набора альтернатив (вместо их ранжирования ) теорема Накамуры более уместна. [5] Интересный вопрос - насколько большим может быть число Накамуры. Было показано, что для (конечной или) алгоритмически вычислимой простой игры, у которой нет игрока с правом вето (индивидуума, который принадлежит каждой выигрышной коалиции), чтобы иметь число Накамуры больше трех, игра должна быть несильной . [6] Это означает, что существует проигрывающая (то есть не выигрывающая) коалиция, чей состав также проигрывает. Это, в свою очередь, означает, что непустота ядра гарантируется для набора из трех или более альтернатив, только если ядро может содержать несколько альтернатив, которые не могут быть строго ранжированы. [8]
Фреймворк
Позволять быть (конечным или бесконечным) непустым множеством индивидов . Подмножестваназываются коалициями . Простая игра (голосование игра) представляет собой наборкоалиций. (Эквивалентно, это коалиционная игра, в которой каждой коалиции присваивается либо 1, либо 0.) Мы предполагаем, чтонепусто и не содержит пустого множества. Коалиции, принадлежащиеявляются победы ; другие проигрывают . Простая играявляется монотонной , если а также подразумевать . Это правильно, если подразумевает . Это сильно, если подразумевает . Игрок с правом вето (vetoer) - это лицо, принадлежащее ко всем выигравшим коалициям. Простая игра неслабая, если в ней нет игрока с правом вето. Это конечно, если есть конечное множество (называемое носителем ) так что для всех коалиций , у нас есть если только .
Позволять быть (конечным или бесконечным) набором альтернатив , кардинальное число (количество элементов) которогокак минимум два. (Строгое) предпочтение - это асимметричное отношение на : если (читать " предпочтительнее "), тогда . Мы говорим, что предпочтениеявляется ацикличным (не содержит циклов ), если для любого конечного числа альтернатив, в любое время , ,…, , у нас есть . Обратите внимание, что ациклические отношения асимметричны, отсюда и предпочтения.
Профиль список индивидуальных предпочтений . Здесь означает, что человек предпочитает альтернативу к в профиль .
Простая игра с порядковыми предпочтениями пара состоящий из простой игры и профиль . Дано, отношение доминирования (социального предпочтения) определяется на от тогда и только тогда, когда есть победившая коалиция удовлетворение для всех . ядро из это набор альтернатив, не доминирующий (множество максимальных элементов относительно ):
- если и только если нет такой, что .
Определение и примеры
Число Накамуры простой игры - размер (кардинальное число) наименьшего набора выигрышных коалиций с пустым пересечением: [9]
если (без вето); [2] в противном случае (больше любого кардинального числа).
легко доказать, что если это простая игра без вето игрока, тогда .
Примеры для конечного числа индивидов () (см. Остен-Смит и Бэнкс (1999), лемма 3.2 [4] ). Позволять быть простой игрой, монотонной и правильной.
- Если сильный и без игрока вето, то .
- Если является игрой большинства (т. е. коалиция выигрывает тогда и только тогда, когда она состоит из более чем половины людей), то если ; если .
- Если это -правило (т. е. коалиция побеждает тогда и только тогда, когда она состоит не менее чем из лиц) с , тогда , где наименьшее целое число, большее или равное .
Примеры для не более чем счетного количества людей (). Кумабе и Михара (2008) всесторонне изучают ограничения, которые различные свойства (монотонность, правильность, сила, неслабость и конечность) простых игр накладывают на их число Накамуры (таблица «Возможные числа Накамуры» ниже суммирует результаты). В частности, они показывают, что алгоритмически вычислимая простая игра [10] без игрока, имеющего право вето, имеет число Накамуры больше 3, только если она правильная и не сильная. [6]
Тип | Конечные игры | Бесконечные игры |
---|---|---|
1111 | 3 | 3 |
1110 | + ∞ | никто |
1101 | ≥3 | ≥3 |
1100 | + ∞ | + ∞ |
1011 | 2 | 2 |
1010 | никто | никто |
1001 | 2 | 2 |
1000 | никто | никто |
0111 | 2 | 2 |
0110 | никто | никто |
0101 | ≥2 | ≥2 |
0100 | + ∞ | + ∞ |
0011 | 2 | 2 |
0010 | никто | никто |
0001 | 2 | 2 |
0000 | никто | никто |
Теорема Накамуры об ациклических предпочтениях
Теорема Накамуры (Накамура, 1979, теоремы 2.3 и 2.5 [2] ). Позволятьбыть простой игрой. Тогда ядро непусто для всех профилей ациклических предпочтений тогда и только тогда, когда конечно и .
Замечания
- Теорема Накамуры часто цитируется в следующей форме без ссылки на основную (например, Austen-Smith and Banks, 1999, теорема 3.2 [4] ): Отношение доминирования ацикличен для всех профилей ациклических предпочтений тогда и только тогда, когда для всех конечных (Накамура, 1979, теорема 3.1 [2] ).
- Утверждение теоремы останется в силе, если заменить «для всех профилей из ациклических предпочтений «на» для всех профилейиз отрицательно транзитивных предпочтений «или» для всех профилейиз линейно упорядоченных (то есть, транзитивное и всего) предпочтения». [12]
- Теорема распространяется на -простые игры. Здесь коллекциякоалиций - произвольная булева алгебра подмножеств, такой как -алгебра измеримых множеств по Лебегу . А- простая игра представляет собой сборник. Профили соответственно ограничиваются измеримыми: профильявляется измеримой , если для всех, у нас есть . [3]
Вариант теоремы Накамуры о предпочтениях, который может содержать циклы
В этом разделе мы отбрасываем обычное предположение об ациклических предпочтениях. Вместо этого мы ограничиваем предпочтения теми, у кого есть максимальный элемент в данной повестке дня ( набор возможностей , с которым сталкивается группа людей), подмножество некоторого основного набора альтернатив. (Это слабое ограничение предпочтений может представлять определенный интерес с точки зрения поведенческой экономики .) Соответственно, уместно подумать окак повестка дня здесь. Альтернативаявляется максимальным элементом относительно (т.е. имеет максимальный элемент ) если нет такой, что . Если предпочтение ациклично по отношению к базовому набору альтернатив, то оно имеет максимальный элемент на каждом конечном подмножестве.
Мы вводим усиление ядра перед формулировкой варианта теоремы Накамуры. Альтернатива может быть в основе даже если есть победившая коалиция людей которые "недовольны" (т.е. каждый предпочитает некоторые к ). Следующее решение исключает такой: [3]
- Альтернатива в основебез недовольства большинства, если нет победившей коалиции такое, что для всех , не является максимальным (существуют некоторые удовлетворение ).
Легко доказать, что зависит только от множества максимальных элементов каждого индивида и входит в объединение таких множеств. Причем для каждого профиля, у нас есть .
Вариант теоремы Накамуры (Кумабе, Михара, 2011, теорема 2 [3] ). Позволятьбыть простой игрой. Тогда следующие три утверждения эквивалентны:
- ;
- ядро без недовольства большинства непусто для всех профилей предпочтений, имеющих максимальный элемент;
- ядро непусто для всех профилей предпочтений, которые имеют максимальный элемент.
Замечания
- В отличие от первоначальной теоремы Накамуры, конечность не является необходимым условием для или же быть непустым для всех профилей . Даже если повестка дня имеет бесконечно много альтернатив, есть элемент в сердечниках для соответствующих профилей, главное, чтобы выполнялось неравенство доволен.
- Утверждение теоремы останется в силе, если заменить «для всех профилей предпочтений, которые имеют максимальный элемент "в утверждениях 2 и 3 по" для всех профилей предпочтений, которые имеют ровно один максимальный элемент "или" для всех профилейиз линейно упорядоченных предпочтений , которые имеют максимальный элемент»(Kumabe и Михар, 2011, предложение 1).
- Подобно теореме Накамуры для ациклических предпочтений, эту теорему можно распространить на -простые игры. Теорема может быть расширена еще дальше (1 и 2 эквивалентны; из них следует 3) на наборы выигрышных наборов , расширяя понятие числа Накамуры. [13]
Смотрите также
Заметки
- Перейти ↑ Suzuki, Mitsuo (1981). Теория игр и социальный выбор: Избранные статьи Кенджиро Накамуры . Кейсо Шуппан. Накамура получил степень доктора социальной инженерии в Токийском технологическом институте в 1975 году.
- ^ а б в г Накамура, К. (1979). «Ветеры в простой игре с порядковыми предпочтениями». Международный журнал теории игр . 8 : 55–61. DOI : 10.1007 / BF01763051 .
- ^ а б в г Кумабе, М .; Михара, HR (2011). «Теория агрегирования предпочтений без ацикличности: ядро без недовольства большинства» (PDF) . Игры и экономическое поведение . 72 : 187–201. arXiv : 1107.0431 . DOI : 10.1016 / j.geb.2010.06.008 .
- ^ а б в г Остин-Смит, Дэвид; Бэнкс, Джеффри С. (1999). Позитивная политическая теория I: Коллективное предпочтение . Анн-Арбор: Мичиганский университет Press. ISBN 978-0-472-08721-1. Внешняя ссылка в
|title=
( помощь ) - ^ Исходная теоремаНакамурыимеет прямое отношение к классу простых правил агрегирования предпочтений, правил, полностью описываемых их семейством решающих (выигрышных) коалиций. (Учитывая правило агрегирования, коалицияимеет решающее значение, если каждый человек в предпочитает к , то же самое делает и общество.) Austen-Smith and Banks (1999) [4], учебник по теории социального выбора, в котором подчеркивается роль числа Накамуры, расширяет число Накамуры на более широкий (и эмпирически важный) класс нейтральных (т. е. маркировка альтернатив не имеет значения) и монотонная (если социально предпочтительнее , затем увеличивая поддержку над сохраняет это социальное предпочтение) правила агрегации (теорема 3.3) и получить теорему (теорема 3.4), аналогичную теореме Накамуа.
- ^ а б Кумабе, М .; Михара, HR (2008). «Числа Накамуры для вычислимых простых игр» . Социальный выбор и благосостояние . 31 (4): 621. arXiv : 1107.0439 . DOI : 10.1007 / s00355-008-0300-5 .
- ^ Кирман, А .; Зондерманн, Д. (1972). «Теорема Эрроу, много агентов и невидимые диктаторы». Журнал экономической теории . 5 : 267. DOI : 10.1016 / 0022-0531 (72) 90106-8 .
- ^ Существуют монотонные, правильные, сильные простые игры без игрока с правом вето, у которых есть бесконечное число Накамуры. Непринципиальный ультрафильтр является примером, который можно использовать для определения правила агрегации (функции общественного благосостояния), удовлетворяющего условиям Эрроу, если существует бесконечно много индивидуумов. [7] Серьезным недостатком неглавных ультрафильтров для этой цели является то, что они не являются алгоритмически вычисляемыми.
- ^ Минимальный элемент следующего набора существует, поскольку каждый непустой набор порядковых чисел имеет минимальный элемент.
- ^ См. Раздел теоремы Райса для определения вычислимой простой игры. В частности, все конечные игры вычислимы.
- ^ Возможные числа Накамуры для вычислимых простых игр даны в каждой записи, предполагая, что пустая коалиция проигрывает. Шестнадцать типов определены в терминах четырех свойств: монотонности, правильности, силы и неслабости (отсутствие игрока с правом вето). Например, строка, соответствующая типу 1110, указывает, что среди монотонных (1), собственных (1), сильных (1), слабых (0, потому что не неслабых) вычислимых простых игр конечные имеют число Накамуры, равноеа бесконечных не существует. Строка, соответствующая типу 1101, указывает, что любой (и нет ) - число Накамуры некоторой конечной (или бесконечной) простой игры этого типа. Обратите внимание, что среди неслабых простых игр только типы 1101 и 0101 достигают числа Накамуры больше 3.
- ^ Направление «если» очевидно, в то время как направление «только если» сильнее, чем утверждение теоремы, данной выше (доказательство по существу то же). Эти результаты часто формулируются в терминах слабых предпочтений (например, Austen-Smith and Banks, 1999, теорема 3.2 [4] ). Определите слабое предпочтение от . потом асимметричен тогда и только тогда завершено; отрицательно транзитивен тогда и только тогда, когда транзитивен. в общей сложности, если подразумевает или же .
- ^ Рамка отличает алгебрув коалициях из большого собраниянаборов лиц, которым может быть присвоен статус выигрыша / проигрыша. Например,является алгеброй рекурсивных множеств иэто решетка из рекурсивно перечислимых множеств (Kumabe и Михар, 2011, раздел 4.2).