Число Накамура

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

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

В отличие,

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

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

Обзор

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

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

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

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

Для ранжирования альтернатив существует очень известный результат, называемый « теоремой Эрроу о невозможности » в теории социального выбора. что указывает на трудность для группы людей ранжировать три или более альтернатив.Для выбора из множества альтернатив (вместо их ранжирования ) более актуальна теорема Накамуры. Интересный вопрос: насколько большим может быть число Накамуры?Было показано, что для (конечной или) алгоритмически вычислимой простой игры, в которой нет игрока с правом вето (человек, принадлежащий к каждой победившей коалиции)Чтобы число Накамуры было больше трех, игра должна быть несильной . Это означает, что существует проигравшая (т.е. не выигравшая) коалиция, состав которой также проигрывает.Это, в свою очередь, означает, что непустота ядра обеспечивается для набора из трех и более альтернатив.только в том случае, если ядро ​​может содержать несколько альтернатив, которые не могут быть строго ранжированы.

Рамки

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

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

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

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

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

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

Число Накамура $\nu (W)$ из простой игры $W$ размер (количественное число)наименьшего набора выигрышных коалиций с пустым пересечением:

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

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

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

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

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

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

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

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

Примечания

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

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

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

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

Прежде чем сформулировать вариант теоремы Накамуры, мы введем усиление ядра.Альтернатива $x$ может быть в ядре $C(W,p)$ даже если существует победившая коалиция отдельных лиц $i$ которые «недовольны» $x$ (т.е. каждый $i$ предпочитает некоторые $y_{i}$ к $x$).Следующее решение исключает такую ​​возможность. $x$:

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

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

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

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

Примечания

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

См. также

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