Число Накамура - Nakamura number

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

• Если количество альтернатив (кандидатов; вариантов) для выбора меньше этого количества, то рассматриваемое правило без проблем определит «лучшие» альтернативы.

В отличие,

• если количество альтернатив больше или равно этому количеству, правило не сможет определить «лучшие» альтернативы для некоторой модели голосования (т. е. для некоторых профиль (кортеж ) индивидуальных предпочтений), поскольку парадокс голосования возникнет (а цикл генерируется как альтернатива ${\displaystyle a}$ социально предпочитаемый альтернативе ${\displaystyle b}$, ${\displaystyle b}$ к ${\displaystyle c}$, и ${\displaystyle c}$ к ${\displaystyle a}$).

Чем больше число Накамуры в правиле, тем с большим количеством альтернатив правило может рационально работать. Например, поскольку (за исключением случая четырех человек (избирателей)) правило с числом Накамуры большинства равно трем, правило может иметь дело с двумя альтернативами рационально (не вызывая парадокса). Это число названо в честь Кендзиро Накамура (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, тогда общество (из пяти человек, в приведенном выше примере) примет тот же рейтинг (социальные предпочтения).

В Число Накамура простой игры определяется как минимальное количество выигрышных коалиций с пустыми пересечение (Пересекая это количество выигрышных коалиций, иногда можно получить пустое множество, но, пересекая меньшее, чем это число, нельзя получить пустое множество.) Число Накамуры в простой игре выше равно трем, например, поскольку пересечение любых двух выигрышных коалиций содержит по крайней мере одного человека, но пересечение следующих трех выигрышных коалиций пусто: ${\displaystyle \{1,2,3\}}$, ${\displaystyle \{4,5,1\}}$, ${\displaystyle \{2,3,4\}}$.

Теорема Накамуры (1979^[2]) дает следующее необходимое (также достаточное, если множество альтернатив конечно) условие того, чтобы простая игра имела непустое «ядро» (множество социально «лучших» альтернатив) для всех профилей индивидуальных предпочтений: количество альтернатив равно меньше числа Накамуры в простой игре. основной простой игры по профилю предпочтений - это множество всех альтернатив ${\displaystyle x}$ так что альтернативы нет ${\displaystyle y}$что каждый человек в выигрышной коалиции предпочитает ${\displaystyle x}$; то есть набор максимальный элементы социальных предпочтений. Для приведенного выше примера игры большинства теорема подразумевает, что ядро ​​будет пустым (никакая альтернатива не будет считаться «лучшей») для некоторого профиля, если есть три или более альтернатив.

Существуют варианты теоремы Накамуры, которые обеспечивают условие непустоты ядра (i) для всех профилей ациклический предпочтения; (ii) для всех профилей переходный предпочтения; и (iii) для всех профилей линейные порядкиЕсть и другой вариант (Kumabe, Mihara, 2011).^[3]), что обходится без ацикличность- слабое требование рациональности. Вариант дает условие непустоты ядра для всех профилей предпочтений, имеющих максимальные элементы.

За рейтинг альтернатив, есть очень известный результат под названием "Теорема о невозможности Эрроу "в теории социального выбора, которая указывает на трудности для группы людей при ранжировании трех или более альтернатив. выбор из набора альтернатив (вместо рейтинг их), теорема Накамуры более актуальна.^[5]Интересный вопрос заключается в том, насколько большим может быть число Накамуры. Было показано, что для (конечной или) алгоритмически вычислимой простой игры, в которой нет игрока с правом вето (индивидуума, принадлежащего к каждой победившей коалиции), число Накамуры должно быть больше трех , игра должна быть несильный.^[6]Это означает, что есть проигрыш (т. е. не выигрывающая) коалиция, дополнение которой также проигрывает. Это, в свою очередь, означает, что непустота ядра гарантируется для набора из трех или более альтернатив, только если ядро ​​может содержать несколько альтернатив, которые не могут быть строго ранжированы.^[8]

Рамки

Позволять ${\displaystyle N}$ быть (конечным или бесконечным) непустым множеством отдельные лица.Подмножества ${\displaystyle N}$ называются коалиции.A простая игра (игра с голосованием) - это сборник ${\displaystyle W}$ коалиций (эквивалентно, это коалиционная игра, в которой каждой коалиции присваивается либо 1, либо 0). ${\displaystyle W}$ непусто и не содержит пустого множества. коалиции, принадлежащие ${\displaystyle W}$ находятся победа; другие проигрыш.Простая игра ${\displaystyle W}$ является монотонный если ${\displaystyle S\in W}$ и ${\displaystyle S\subseteq T}$подразумевать ${\displaystyle T\in W}$. это правильный если ${\displaystyle S\in W}$ подразумевает ${\displaystyle N\setminus S\notin W}$.Это сильный если ${\displaystyle S\notin W}$ подразумевает ${\displaystyle N\setminus S\in W}$.A игрок с вето (вето) - это лицо, принадлежащее ко всем выигрышным коалициям. неслабый если у него нет игрока с правом вето. конечный если существует конечное множество (называемое перевозчик) ${\displaystyle T\subseteq N}$ так что для всех коалиций ${\displaystyle S}$, у нас есть ${\displaystyle S\in W}$ если только ${\displaystyle S\cap T\in W}$.

Позволять ${\displaystyle X}$ быть (конечным или бесконечным) набором альтернативы, чей количественное числительное (количество элементов) ${\displaystyle \#X}$ не меньше двух.А (строгий) предпочтение является асимметричный связь ${\displaystyle \succ }$ на ${\displaystyle X}$:если ${\displaystyle x\succ y}$ (читать "${\displaystyle x}$ предпочтительнее ${\displaystyle y}$"), тогда ${\displaystyle y\not \succ x}$.Мы говорим, что предпочтение ${\displaystyle \succ }$ является ациклический (не содержит циклы), если для любого конечного числа альтернатив ${\displaystyle x_{1},\ldots ,x_{m}}$, в любое время ${\displaystyle x_{1}\succ x_{2}}$, ${\displaystyle x_{2}\succ x_{3}}$,…, ${\displaystyle x_{m-1}\succ x_{m}}$,у нас есть ${\displaystyle x_{m}\not \succ x_{1}}$. Обратите внимание, что ациклические отношения асимметричны, отсюда и предпочтения.

А профиль это список ${\displaystyle p=(\succ _{i}^{p})_{i\in N}}$ индивидуальных предпочтений ${\displaystyle \succ _{i}^{p}}$.Здесь ${\displaystyle x\succ _{i}^{p}y}$ означает, что человек ${\displaystyle i}$ предпочитает альтернативу ${\displaystyle x}$к ${\displaystyle y}$ в профиль ${\displaystyle p}$.

А простая игра с порядковыми предпочтениями пара ${\displaystyle (W,p)}$ состоящий из простой игры ${\displaystyle W}$ и профиль ${\displaystyle p}$.Данный ${\displaystyle (W,p)}$, а господство (социальные предпочтения) отношение ${\displaystyle \succ _{W}^{p}}$ определяется на ${\displaystyle X}$ к ${\displaystyle x\succ _{W}^{p}y}$ если и только если есть победившая коалиция ${\displaystyle S\in W}$удовлетворение ${\displaystyle x\succ _{i}^{p}y}$ для всех ${\displaystyle i\in S}$. основной ${\displaystyle C(W,p)}$ из ${\displaystyle (W,p)}$ - это набор альтернатив, не доминирующий ${\displaystyle \succ _{W}^{p}}$(множество максимальных элементов ${\displaystyle X}$ относительно ${\displaystyle \succ _{W}^{p}}$):

${\displaystyle x\in C(W,p)}$ если и только если нет ${\displaystyle y\in X}$ такой, что ${\displaystyle y\succ _{W}^{p}x}$.

Определение и примеры

В Число Накамура ${\displaystyle \nu (W)}$ простой игры ${\displaystyle W}$ - размер (кардинальное число) наименьшего набора выигрышных коалиций с пустым пересечением:^[9]

${\displaystyle \nu (W)=\min\{\#W':W'\subseteq W;\cap W'=\emptyset \}}$

если ${\displaystyle \cap W=\cap _{S\in W}S=\emptyset }$ (без вето);^[2] иначе, ${\displaystyle \nu (W)=+\infty }$ (больше любого кардинального числа).

легко доказать, что если ${\displaystyle W}$ это простая игра без вето игрока, тогда ${\displaystyle 2\leq \nu (W)\leq \#N}$.

Примеры для конечного числа индивидов (${\displaystyle N=\{1,\ldots ,n\}}$) (см. Остен-Смит и Бэнкс (1999), лемма 3.2^[4]).Позволять ${\displaystyle W}$ быть простой игрой, монотонной и правильной.

• Если ${\displaystyle W}$ сильный и без игрока вето, то ${\displaystyle \nu (W)=3}$.
• Если ${\displaystyle W}$ является игрой большинства (т.е. коалиция выигрывает тогда и только тогда, когда она состоит из более чем половины людей), то ${\displaystyle \nu (W)=3}$ если ${\displaystyle n\neq 4}$; ${\displaystyle \nu (W)=4}$ если ${\displaystyle n=4}$.
• Если ${\displaystyle W}$ это ${\displaystyle q}$-правило (т.е. коалиция побеждает тогда и только тогда, когда она состоит не менее чем из ${\displaystyle q}$ лиц) с ${\displaystyle n/2<q<n}$, тогда ${\displaystyle \nu (W)=[n/(n-q)]}$, куда ${\displaystyle [x]}$ это наименьшее целое число, большее или равное ${\displaystyle x}$.

Примеры для не более чем счетного количества людей (${\displaystyle N=\{1,2,\ldots \}}$Кумабе и Михара (2008) всесторонне изучают ограничения, которые различные свойства (монотонность, правильность, сила, неслабость и конечность) простых игр накладывают на их число Накамуры (таблица «Возможные числа Накамуры» ниже суммирует результаты). В частности, они показывают, что алгоритмически вычислимая простая игра ^[10]без права вето у игрока число Накамуры больше 3, только если оно правильное и не сильное.^[6]

Возможные числа Накамуры^[11]

Тип	Конечные игры	Бесконечные игры
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]).Позволять ${\displaystyle W}$ быть простой игрой. Тогда ядро ${\displaystyle C(W,p)}$ непусто для всех профилей ${\displaystyle p}$ ациклических предпочтений тогда и только тогда, когда ${\displaystyle X}$ конечно и ${\displaystyle \#X<\nu (W)}$.

Замечания

• Теорема Накамуры часто цитируется в следующей форме без ссылки на основную (например, Austen-Smith and Banks, 1999, теорема 3.2^[4]): Отношение доминирования ${\displaystyle \succ _{W}^{p}}$ ацикличен для всех профилей ${\displaystyle p}$ ациклических предпочтений тогда и только тогда, когда ${\displaystyle \#B<\nu (W)}$ для всех конечных ${\displaystyle B\subseteq X}$ (Накамура 1979, теорема 3.1^[2]).
• Утверждение теоремы останется в силе, если заменить «для всех профилей ${\displaystyle p}$ из ациклический предпочтения "по" для всех профилей ${\displaystyle p}$ из отрицательно переходный предпочтения "или по" для всех профилей ${\displaystyle p}$ из линейно упорядоченный (т.е. переходные и общие) предпочтения ".^[12]

• Теорема распространяется на ${\displaystyle {\mathcal {B}}}$-простые игры. Здесь коллекция ${\displaystyle {\mathcal {B}}}$ коалиций является произвольным Булева алгебра подмножеств ${\displaystyle N}$, такой как ${\displaystyle \sigma }$-алгебра Измеримый по Лебегу наборы. А ${\displaystyle {\mathcal {B}}}$-простая игра это подколлекция ${\displaystyle {\mathcal {B}}}$. Профили соответственно ограничены измеримыми: профиль ${\displaystyle p}$ является измеримый если для всех ${\displaystyle x,y\in X}$, у нас есть ${\displaystyle \{i:x\succ _{i}^{p}y\}\in {\mathcal {B}}}$.^[3]

Вариант теоремы Накамуры о предпочтениях, который может содержать циклы

В этом разделе мы отбрасываем обычное предположение об ациклических предпочтениях, а ограничиваем предпочтения теми, у кого есть максимальный элемент на заданном уровне. повестка дня (набор возможностей (с которыми сталкивается группа людей), подмножество некоторого основного набора альтернатив (это слабое ограничение предпочтений может представлять некоторый интерес с точки зрения поведенческая экономика.) Соответственно, уместно подумать о ${\displaystyle X}$ как повестка дня здесь. Альтернатива ${\displaystyle x\in X}$ это максимальный элемент по отношению к ${\displaystyle \succ _{i}^{p}}$(т.е. ${\displaystyle \succ _{i}^{p}}$ имеет максимальный элемент ${\displaystyle x}$) если нет ${\displaystyle y\in X}$ такой, что ${\displaystyle y\succ _{i}^{p}x}$. Если предпочтение ациклично по отношению к базовому набору альтернатив, то оно имеет максимальный элемент на каждом конечный подмножество ${\displaystyle X}$.

Перед формулировкой варианта теоремы Накамуры мы вводим усиление ядра. ${\displaystyle x}$ может быть в основе ${\displaystyle C(W,p)}$ даже если есть победившая коалиция людей ${\displaystyle i}$ которые "недовольны" ${\displaystyle x}$ (т.е. каждый ${\displaystyle i}$ предпочитает некоторые ${\displaystyle y_{i}}$ к ${\displaystyle x}$Следующее решение исключает такой ${\displaystyle x}$:^[3]

Альтернатива ${\displaystyle x\in X}$ находится в основной ${\displaystyle C^{+}(W,p)}$ без недовольства большинства если нет победившей коалиции ${\displaystyle S\in W}$ такое, что для всех ${\displaystyle i\in S}$, ${\displaystyle x}$ является немаксимальный (есть некоторые ${\displaystyle y_{i}\in X}$ удовлетворение ${\displaystyle y_{i}\succ _{i}^{p}x}$).

Легко доказать, что ${\displaystyle C^{+}(W,p)}$ зависит только от набора максимальных элементов каждого индивидуума и входит в объединение таких наборов. Причем для каждого профиля ${\displaystyle p}$, у нас есть ${\displaystyle C^{+}(W,p)\subseteq C(W,p)}$.

Вариант теоремы Накамуры (Кумабе и Михара, 2011, теорема 2^[3]).Позволять ${\displaystyle W}$ быть простой игрой. Тогда следующие три утверждения эквивалентны:

1. ${\displaystyle \#X<\nu (W)}$;
2. ядро ${\displaystyle C^{+}(W,p)}$ без недовольства большинства непусто для всех профилей ${\displaystyle p}$ предпочтений, которые имеют максимальный элемент;
3. ядро ${\displaystyle C(W,p)}$ непусто для всех профилей ${\displaystyle p}$ предпочтений, у которых есть максимальный элемент.

Замечания

• В отличие от первоначальной теоремы Накамуры, ${\displaystyle X}$ быть конечным не необходимое условие за ${\displaystyle C^{+}(W,p)}$ или же ${\displaystyle C(W,p)}$ быть непустым для всех профилей ${\displaystyle p}$. Даже если повестка дня ${\displaystyle X}$ имеет бесконечно много альтернатив, есть элемент в сердечниках для соответствующих профилей, главное, чтобы выполнялось неравенство ${\displaystyle \#X<\nu (W)}$ доволен.
• Утверждение теоремы останется в силе, если заменить «для всех профилей ${\displaystyle p}$ предпочтений с максимальным элементом "в утверждениях 2 и 3 по" для всех профилей ${\displaystyle p}$ предпочтений, которые имеют ровно один максимальный элемент "или" для всех профилей ${\displaystyle p}$ из линейно упорядоченный предпочтения, имеющие максимальный элемент »(Kumabe and Mihara, 2011, Proposition 1).
• Подобно теореме Накамуры для ациклических предпочтений, эту теорему можно распространить на ${\displaystyle {\mathcal {B}}}$-простые игры. Теорема может быть расширена еще дальше (1 и 2 эквивалентны; из них следует 3) на коллекции ${\displaystyle W'\subseteq {\mathcal {B}}'}$ выигрышных сетов путем расширения понятия числа Накамуры.^[13]

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

• Теорема Гиббарда – Саттертуэйта
• Теорема мая
• Парадокс голосования

Примечания

1. Сузуки, Мицуо (1981). Теория игр и социальный выбор: Избранные статьи Кенджиро Накамуры. Кейсо Шуппан. Накамура получил степень доктора социальной инженерии в Токийском технологическом институте в 1975 году.
2. Накамура, К. (1979). «Ветеры в простой игре с порядковыми предпочтениями». Международный журнал теории игр. 8: 55–61. Дои:10.1007 / BF01763051.
3. Кумабе, М .; Михара, Х. Р. (2011). «Теория агрегирования предпочтений без ацикличности: ядро ​​без недовольства большинства» (PDF). Игры и экономическое поведение. 72: 187–201. arXiv:1107.0431. Дои:10.1016 / j.geb.2010.06.008.
4. Остин-Смит, Дэвид; Бэнкс, Джеффри С. (1999). Позитивная политическая теория I: Коллективное предпочтение. Анн-Арбор: Мичиганский университет Press. ISBN  978-0-472-08721-1. Внешняя ссылка в | название = (помощь)
5. Накамуры оригинал Теорема имеет прямое отношение к классу просто правила агрегации предпочтений, правила, полностью описываемые их семейством решающих (выигрышных) коалиций (с учетом правила агрегации коалиция ${\displaystyle S}$ является решающий если каждый человек в ${\displaystyle S}$ предпочитает ${\displaystyle x}$ к ${\displaystyle y}$, то же самое делает и общество.) Austen-Smith and Banks (1999),^[4]учебник по теории социального выбора, в котором подчеркивается роль числа Накамуры, расширяет число Накамуры на более широкий (и эмпирически важный) класс нейтральный(т.е. маркировка альтернатив не имеет значения) имонотонный (если ${\displaystyle x}$ социально предпочтительнее ${\displaystyle y}$, а затем увеличивая поддержку ${\displaystyle x}$ над ${\displaystyle y}$ сохраняет это социальное предпочтение) правила агрегации (теорема 3.3) и получить теорему (теорема 3.4), аналогичную теореме Накамуа.
6. Кумабе, М .; Михара, Х. Р. (2008). «Числа Накамуры для вычислимых простых игр». Социальный выбор и благосостояние. 31 (4): 621. arXiv:1107.0439. Дои:10.1007 / s00355-008-0300-5.
7. Кирман, А .; Зондерманн, Д. (1972). «Теорема Эрроу, множество агентов и невидимые диктаторы». Журнал экономической теории. 5: 267. Дои:10.1016/0022-0531(72)90106-8.
8. Существуют монотонные, правильные, сильные простые игры без игрока с вето, у которых есть бесконечное число Накамуры. Неглавный ультрафильтр это пример, который можно использовать для определения правила агрегирования (функции общественного благосостояния), удовлетворяющего условиям Эрроу, если существует бесконечно много индивидов.^[7]Серьезным недостатком неглавных ультрафильтров для этой цели является то, что они алгоритмически не вычислимы.
9. Минимальный элемент следующего набора существует, так как каждый непустой набор порядковые номера имеет наименьший элемент.
10. Видеть раздел теоремы Райса для определения вычислимой простой игры. В частности, все конечные игры вычислимы.
11. Возможные числа Накамуры для вычислимых простых игр даны в каждой записи, предполагая, что пустая коалиция проигрывает. Шестнадцать типов определены в терминах четырех свойств: монотонности, правильности, силы и неслабости (отсутствие игрока с правом вето). Например, строка, соответствующая типу 1110, указывает, что среди монотонных (1), собственных (1), сильных (1), слабых (0, потому что не неслабых) вычислимых простых игр конечные имеют число Накамуры, равное ${\displaystyle +\infty }$ и бесконечных не существует. строка, соответствующая типу 1101, указывает, что любая ${\displaystyle k\geq 3}$ (и нет ${\displaystyle k<3}$) является числом Накамуры некоторой конечной (альтернативно бесконечной) простой игры этого типа. Отметим, что среди неслабых простых игр только типы 1101 и 0101 достигают числа Накамуры больше 3.
12. Направление «если» очевидно, в то время как направление «только если» сильнее, чем утверждение теоремы, данной выше (доказательство по существу то же самое). Эти результаты часто формулируются в терминах слабый предпочтения (например, Остен-Смит и Бэнкс, 1999, теорема 3.2^[4]). Определите слабое предпочтение ${\displaystyle \succeq }$ к ${\displaystyle x\succeq y\iff y\not \succ x}$. потом ${\displaystyle \succ }$ асимметричен тогда и только тогда ${\displaystyle \succeq }$ завершено; ${\displaystyle \succ }$ отрицательно транзитивен тогда и только тогда, когда ${\displaystyle \succeq }$ транзитивен.${\displaystyle \succ }$ является общий если ${\displaystyle x\neq y}$ подразумевает ${\displaystyle x\succ y}$ или же ${\displaystyle y\succ x}$.
13. Каркас отличает алгебру ${\displaystyle {\mathcal {B}}}$ из коалиции из большой коллекции ${\displaystyle {\mathcal {B}}'}$ наборов лиц, которым может быть присвоен статус выигрыша / проигрыша. Например, ${\displaystyle {\mathcal {B}}}$ это алгебра рекурсивные множества и ${\displaystyle {\mathcal {B}}'}$ это решетка из рекурсивно перечислимые множества (Кумабе и Михара, 2011, раздел 4.2).