나카무라 번

협동 게임 이론과 사회 선택 이론에서 나카무라 번호는 투표 규칙과 같은 선호 집적 규칙(집적 결정 규칙)의 합리성의 정도를 측정한다. 그것은 집합 규칙이 정확히 정의된 선택을 산출할 수 있는 정도를 나타내는 지표다.

• 선택할 대안(후보자, 옵션)의 수가 이 숫자보다 적으면 해당 규칙은 문제 없이 "최상의" 대안을 식별한다.

그에 반해서

• 대안의 수가 이 수보다 크거나 같으면, 규칙은 투표의 역설(대안보다 사회적으로$$ $선호$되는 ${\displaystyle a$}과 같은 사이클)이 발생하기 때문에, 일부 투표 패턴(즉, 개인 선호의 일부 프로파일(튜플)에 대해)에 대한 "최선의" 대안을 식별하지 못할 것이다.$b{\displaystyle }$ ${\displaystyle$ $b$$\},$ $b{\displaystyle }$ ${\$$displaystyle b$$},$$$$c{\displaystyle }$ ${\$displaystyle c$},$ c ${\displaystyle c}$을(를) ${\displaystyle a}$에(를) 각각 표시한다.$$

나카무라 숫자가 클수록 규칙이 합리적으로 다룰 수 있는 대안의 수는 더 많다. 예를 들어, (4명의 개인(관객)의 경우 제외) 나카무라 다수결 원칙이 3이므로, 규칙은 (역설을 일으키지 않고) 합리적으로 최대 2개의 대안을 다룰 수 있다. 집단 선택의 합리성이 결정적으로 대안의 수에 달려 있다는 위의 사실을 입증한 일본의 게임 이론가 나카무라 겐지로(1947~1979)의 이름을 따온 것이다.^[1]

개요

나카무라 번호의 정확한 정의를 소개하기 위해, 나카무라 번호가 할당되는 「게임」(해당 규칙의 아래)의 예를 제시한다. 개인들의 집합이 개인 1, 2, 3, 4, 5로 구성되어 있다고 가정해보자. 다수결 원칙의 이면에는 적어도 3명의 구성원이 있는 다음과 같은 ("결정적") 연합(개인의 하위 집합)이 있다.

{ {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} }

나카무라 번호는 그런 수집품에 할당될 수 있는데, 우리는 이것을 단순한 게임이라고 부른다. 더 정확히 말하면, 간단한 게임은 임의의 연합체 모음일 뿐이다; 그 집합에 속하는 연합체들이 이기고 있고, 다른 연합체들은 지고 있다고 한다. 승리하는 연합의 모든 구성원(위 예에서 적어도 3명)이 대안 y보다 대안 x를 선호한다면, 사회(위의 예에서 5명의 개인 중)는 같은 순위(사회적 선호)를 채택할 것이다.

단순한 게임의 나카무라 번호는 빈 교차점이 있는 최소 승리한 연합의 수로 정의된다. (이 정도의 승리한 연합을 교차시킴으로써 때때로 빈 세트를 얻을 수 있다. 그러나 이 숫자보다 적게 교차함으로써 결코 빈 세트를 얻을 수 없다.) 위의 간단한 게임의 나카무라 번호는, 예를 들어, 어떤 두 개의 승리 연합의 교차점이 적어도 한 개인을 포함하지만, 다음 세 개의 승리 연합의 교차점이 비어 있기 때문에, 3개의 승리 연합의 교차점은 비어 있다:${\displaystyle }${ ${\displaystyle 1}$,${\displaystyle 2}$,${\displaystyle 3}$}, {1, 2, $3 \},${${\displaystyle 4,}$ ${\displaystyle 2}$, ${\displaystyle 3}$${\displaystyle \backslash \backslash \},}$ ${\displaystyle 1}$ $\},$ ${\daystylease$ $\backslash \},{\displaystyle }$ {${\displaystyle 4,}$$5$$1$$\}$$isplaystyle \{2,3,4$

나카무라의 정리(1979^[2])는 단순한 게임이 개인의 선호도에 대한 모든 프로파일에 대해 비어 있지 않은 "핵심"(사회적으로 "최상의" 대안의 집합)을 갖기 위해 필요한 다음과 같은 조건(대안의 집합이 유한한 경우에도 충분)을 부여한다: 대안의 수는 단순 게임의 나카무라 수보다 적다. 여기서 선호 프로파일과 관련된 간단한 게임의 핵심은 승리하는 연합의 모든 개인이 x ${\displaystyle x}$을(를) 선호하는$$ $대안{\displaystyle }$ y ${\displaystyle y}$이(가) 없는 모든$$ 대안 $x{\displaystyle }$ ${\displaystyle x}$의 집합$,$ 즉 사회적 선호의 최대 요소 집합이다. 위의 대다수의 게임 예에 대해, 그 정리는 세 가지 이상의 대안이 있을 경우, 일부 프로파일에 대해 코어가 비어 있을 것이라는 것을 암시한다(대안은 "최상"으로 간주되지 않는다).

나카무라 정리의 변형은 코어가 비고정(i) (i) 모든 반복적 선호 프로파일에, (ii) 전이적 선호 프로파일에, (iii) 모든 선형 순서 프로파일에 대해 조건을 제공하는 것이 존재한다. 합리성의 약한 요건인 악순환성을 발산하는 다른 종류의 변종(쿠마베와 미하라, 2011^[3])이 있다. 이 변형은 최대 요소가 있는 모든 선호도 프로파일에 대해 코어가 비어 있지 않은 조건을 제공한다.

대안의 순위를 매기는 것에 대해서는, 사회 선택 이론에 「화로의 불가능 정리」라고 하는 아주 잘 알려진 결과가 있는데, 이것은 대안의 순위를 3개 이상 매기는 데 있어서 개인 집단의 난이도를 지적한다. (순위를 매기는 대신) 일련의 대안 중에서 선택하기 위해서는 나카무라의 정리가 더 목적적합하다.^[5] 흥미로운 질문은 나카무라 숫자가 얼마나 클 수 있느냐 하는 것이다. 거부권 플레이어가 없는 (마인드 또는) 알고리즘으로 계산 가능한 간단한 게임(모든 승리 연합에 속하는 개인)이 나카무라 숫자를 3 이상 갖기 위해서는 게임이 강하지 않아야 한다는 것이 밝혀졌다.^[6] 보완책도 지고 있는 패전(즉, 승리하지 못한) 연합이 있다는 뜻이다. 이는 결국 코어에 엄밀하게 순위를 매길 수 없는 여러 가지 대안을 포함할 수 있는 경우에만 세 가지 이상의 대안에 대해 코어의 비빈도가 보장된다는 것을 의미한다.^[8]

틀

$N{\displaystyle }$ ${\displaystyle N}$을(를) 비어 있지 않은 개인 집합으로$$ 두십시오. $N{\displaystyle }$ ${\displaystyle N}$의 하위 집합을 연합이라고 한다$$. 간단한 게임(투표 게임)은 연합의 $집합$ W ${\displaystyle W}$이다. (동일하게 각 연합에 1 또는 0을 할당하는 연합 게임이다.) $W{\displaystyle }$ ${\displaystyle W}$이(가) 비어 있지 않고 빈 세트를 포함하지 않는다고 가정한다. $W{\displaystyle }$ ${\displaystyle W}$에 속한 연합군이 승리하고 있고, 다른 연합군은 패배하고 있다. A simple game ${\displaystyle W}$ is monotonic if ${\displaystyle S\in W}$ and ${\displaystyle S\subseteq T}$ imply ${\displaystyle T\in W}$. It is proper if ${\displaystyle S\in W}$ implies ${\displaystyle N\setminus S\notin W}$. It is strong if ${\displaystyle S$$\notin W}$은(는) $N{\displaystyle }$ ${\displaystyle \setminus }$ ${\displaystyle S}$ ${\displaystyle \in }$ ${\displaystyle W}$ ${\displaystyle N\setminus S\in W}$을(를) 암시한다$.$ 거부권 행사자(베토르)는 모든 승리한 연합에 속하는 개인이다. 간단한 게임은 거부권이 없으면 약하지 않다. 유한 집합(통신사라고 함) $T{\displaystyle }$ ${\displaystyle \subseteq }$ ${\displaystyle N}$ ${\displaystyle$ $T$$\subseteq$ N$}$이$($가) 있는 경우 유한하므로 모든 연립 $S{\displaystyle }$ ${\displaystyle$ S$}$에 대해 $S{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle W}$ ${\displaystyle S\cap T\in W}$이(가)가 있다$.$

X ${\displaystyle X}$을(를) 대안 집합으로 두 개 이상의 기본 번호(원소$$ 수) # ${\displaystyle X}$ ${\displaystyle \#X}$이(가) 있는 대체 집합으로 설정하십시오. A (strict) preference is an asymmetric relation ${\displaystyle \succ }$ on ${\displaystyle X}$: if ${\displaystyle x\succ y}$ (read "${\displaystyle x}$ is preferred to ${\displaystyle y}$"), then ${\displaystyle y\not \succ x}$. We say that a preference ${\displaystyle \succ }$ is acyclic (does not contain cycles) if for any finite number of alternatives ${\displaystyle x_{1},\ldots ,x_{m}}$, whenever ${\displaystyle x_{1}\succ x_{2}}$, ${\displaystyle x_{2}\succ x_{3}}$,…, ${\displaystyle x_{m-1}\succ x_{m}}$, we have $$${\displaystyle x_{}}$ ${\displaystyle m_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$ 주기적 관계는 비대칭이므로 선호한다는 점에 유의하십시오.

A profile is a list ${\displaystyle p=(\succ _{i}^{p})_{i\in N}}$ of individual preferences ${\displaystyle \succ _{i}^{p}}$. Here ${\displaystyle x\succ _{i}^{p}y}$ means that individual ${\displaystyle i}$ prefers alternative ${\displaystyle x}$ to ${\displaystyle y}$$$프로파일 $p{\displaystyle }$ ${\displaystyle p$에 있는 ${\displaystyle y}$

A simple game with ordinal preferences is a pair ${\displaystyle (W,p)}$ consisting of a simple game ${\displaystyle W}$ and a profile ${\displaystyle p}$. Given ${\displaystyle (W,p)}$, a dominance (social preference) relation ${\displaystyle \succ _{W}^{p}}$ is defined on ${\displaystyle X}$${\displaystyle X}$ by ${\displaystyle x\succ _{W}^{p}y}$ if and only if there is a winning coalition ${\displaystyle S\in W}$ satisfying ${\displaystyle x\succ _{i}^{p}y}$ for all ${\displaystyle i\in S}$. The core ${\displaystyle C(W,p)}$ of ${\di$$splaystyle$($W$$,p)}$은(는$){\displaystyle {}_{}^{}}$ $\succ {\displaystyle {}_{}^{}}$ W ${\displaystyle {}_{}^{}}$ ${\$$}}}$에 의해 지배되지 않는 대안의 집합이다.$$$$

${\displaystyle x}$ ${\displaystyle \in }$ ${\displaystyle C}$( ${\displaystyle W}$, p${\displaystyle }$) ${\displaystyle$ x$\$$in$ $C($$W,p)}$이($가)$ 없는 경우에만($와{\displaystyle }$${\displaystyle )}$ ${\displaystyle y_{}^{}}$≻ W ${\displaystyle {}_{}^{}}$ {\$displaystyle$ y$\such _${W}^{$p}x$

정의 및 예제

간단한 게임 $W{\displaystyle }$ ${\displaystyle W}$의 나카무라 번호 $\nu {\displaystyle (W}$) ${\displaystyle \nu(W)}$은 빈 교차로와 함께 승리한 연합의 최소 집합 크기(카드 번호)이다$$.^[9]

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

만약 $\cap {\displaystyle }$ ${\displaystyle W}$= ${\displaystyle {}_{}}$ ${\displaystyle S_{}}$ W${\displaystyle }$S = ${\displaystyle \mathrm{\varnothing }}$ ${\displaystyle \cap$ W$=\cap _{S\in W}s=\emptyeset$}($$거부권 없음);^[2] ${\displaystyle (}$(${\displaystyle W}$)${\displaystyle }$= + $∞ (W)=+\flotty }.$

$W{\displaystyle }$ ${\displaystyle W}$이(가) 거부권이 없는 단순한 게임이라면${\displaystyle \mathrm{,}}$ $2{\displaystyle \mathrm{}\le (W}$ )${\displaystyle }$≤ # $(\displaystyle 2\leq \nu(W)\leq$\#$N}$임을 입증하는 것은 쉽다$.$

많은 개인에 대한 예(${\displaystyle }$= { ${\displaystyle 1}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle n}$ ${\displaystyle \}}$ ${\displaystyle N=\{1,\ldots$ ,$n$ (Austen-Smith and Banks (1999), Lema 3.2 참조^[4]). $W{\displaystyle }$ ${\displaystyle W}$을(를) 단조롭고 적절한 단순한 게임이 되게$$ 하라.

• $W{\displaystyle }$ ${\displaystyle W}$이(가) 강하고 거부권 플레이어가 없으면 ${\displaystyle \mathrm{\nu }}$(${\displaystyle W}$)${\displaystyle }$= 3 ${\displaystyle \nu(W)=3$ .
• If ${\displaystyle W}$ is the majority game (i.e., a coalition is winning if and only if it consists of more than half of individuals), then ${\displaystyle \nu (W)=3}$ if ${\displaystyle n\neq 4}$; ${\displaystyle \nu (W)=4}$ if ${\displaystyle n=4}$.
• n만약 W{W\displaystyle}은q{\displaystyle q}-rule(만일 적어도 q로 구성되어 있{\displaystyle q}사람들 즉, 승리 연합은)/2<q<>n{\displaystyle n/2<, q<, n},(W))[n/(n− q)]{\displaystyle \nu(W)[n/(n-q)]},[)]{\display ν.스타일[)]} $x{\displaystyle }${\$displaystyle x}$보다 크거나 같은 최소 정수 입니다$.$

가장 많은 개인에 대한 예(${\displaystyle }$= { ${\displaystyle 1}$, ${\displaystyle 2}$, …${\displaystyle \}}$ ${\displaystyle$ N$=\{1,2,\ldots \}).$ 쿠마베와 미하라(2008)는 간단한 게임의 다양한 속성(단조성, 적절성, 강인성, 비약성, 미세성)이 나카무라 번호에 부과하는 제한(아래 표 "가능 나카무라 번호"는 결과를 요약한 것이다)을 종합적으로 연구한다. 특히 이들은 거부권 플레이어가 없는 알고리즘적으로 계산 가능한 간단한 게임이 적절하고 강하지 않은 경우에만 나카무라 번호가 3보다 크다는 것을 보여준다.^[6]

나카무라의 순환 선호를 위한 정리

나카무라 정리(나카무라, 1979년, 정리 2.3, 2.5^[2]). $W{\displaystyle }$ ${\displaystyle W}$을(를) 간단한 게임으로 합시다$$. $그런{\displaystyle }$ 다음 X ${\displaystyle X}$이$(가$) 하고 X< ( ) ${\displaystyle \#X<\nu (W)}$인 경우에만 코어 $C{\displaystyle }$$(W$) ${\displaystyle$ $p}$의 모든 프로파일 p ${\displaystystyle$ p}에 대해 비어 있지 않다$$

언급

• 나카무라의 정리는 핵심(예: 오스틴-스미스와 뱅크스, 1999, 정리 3.2^[4])을 참조하지 않고 다음과 같은 형태로 인용되는 경우가 많다. The dominance relation ${\displaystyle \succ _{W}^{p}}$ is acyclic for all profiles ${\displaystyle p}$ of acyclic preferences if and only if ${\displaystyle \#B<\nu (W)}$ for all finite ${\displaystyle B\subseteq X}$ (Nakamura 1979, Theorem 3.1^[2]).
• "모든 $프로파일{\displaystyle }$ p ${\displaystyle p}$을(를) "부정 전이적 선호의 모든$$ 프로파일 $p{\displaystyle }$ ${\displaystyle p}"$ 또는 "선형으로 정렬된 (즉, 전이적 및 총체적) 선호의$$ $모든{\displaystyle }$ 프로파일$$p {\$displaystyle$ p$}"$로 대체하는 경우, 정리의 문장은 유효하다.^[12]

• $정리$는 B ${\${\$mathcal{B}}$ -단순$$ 게임으로 확장할 수 있다. 여기에서 연합의 집합$$ $B{\displaystyle \mathcal{}}$ ${\$ {$B}$은(는) $\sigma {\displaystyle }$ ${\displaystyle \sigma}$ -algebra$$(레베그 측정 가능 집합)와 같은$$N ${\displaystystyle N}$의 하위 집합에 대한 임의의 부울 대수학이다. A ${\displaystyle {\mathcal {B}}}$-simple game is a subcollection of ${\displaystyle {\mathcal {B}}}$. Profiles are suitably restricted to measurable ones: a profile ${\displaystyle p}$ is measurable if for all ${\displaystyle x,y\in X}$, we have ${\displaystyle$$\{i:x\such _{i}^{p}y\}\in {\mathcal {B$^[3]

사이클을 포함할 수 있는 선호도에 대한 나카무라 정리의 변형

이 절에서는 반복적 선호에 대한 일반적인 가정을 폐기한다. 대신에, 우리는 일부 근본적인 대안 집합의 하위 집합인 주어진 의제에 최대적 요소(개인의 집단이 직면하게 되는 기회 집합)를 가진 사람들로 선호를 제한한다. (이 약한 선호 제한은 행동 경제학의 관점에서 어느 정도 관심의 대상이 될 수 있다.) 따라서 여기서 $X{\displaystyle }$ ${\displaystyle X}$를 의제로 생각하는$$ 것이 적절하다. An alternative ${\displaystyle x\in X}$ is a maximal element with respect to ${\displaystyle \succ _{i}^{p}}$ (i.e., ${\displaystyle \succ _{i}^{p}}$ has a maximal element ${\displaystyle x}$) if there is no ${\displaystyle y\in X}$ such that ${\displaystyle y$$\such _{i}^{p}x$ 기본 대안의 집합보다 기본 설정이 반복적인 경우, 모든 유한 부분 집합 $X에 최대$ 요소가 있다$.$

나카무라 정리의 변종을 말하기 전에 코어의 강화를 소개한다. $대체{\displaystyle }$ $x{\displaystyle }$ ${\displaystyle$ x}$$은$($는) x ${\displaystyle x}($$즉,$ 각 $i{\displaystyle }$ ${\displaystyle$ i$}$과(는$)$ "불만족"$한{\displaystyle {}_{}}$ $개인{\displaystyle }$ i$${\$displaystyle$ $i}$의 승리한 연대가 $있더라도$ 코어 ${\displaystyle C_{}}$${\displaystyle (W}$, $p$에 있을 수 있다$$$.$$splaystyle x}$ $$) 다음 솔루션에서는 이러한 $x{\displaystyle }$ ${\displaystyle x}$을(를) 제외한다$.$^[3]

An alternative ${\displaystyle x\in X}$ is in the core ${\displaystyle C^{+}(W,p)}$ without majority dissatisfaction if there is no winning coalition ${\displaystyle S\in W}$ such that for all ${\displaystyle i\in S}$, ${\displaystyle x}$ is non-maximal (there exists some ${\displaystyle y_i}$${\displaystyle {}_{}\in }$ ${\displaystyle X}$ ${\displaystyle y_{i}\in$ X$}$ $y{\displaystyle {}_{}}$ ${\displaystyle {}_{}{}_{}^{}}$ ${\displaystyle i_{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle y_{i}\such _{i}^{p}x}$ $$.

$C{\displaystyle {}^{}}$+${\displaystyle {}^{}}$( ${\displaystyle W}$, p${\displaystyle }$) ${\displaystyle C^{+}(W,p)}}$은(는) 각 개인의 최대 요소$$ 집합에만 의존하며 그러한 집합의 조합에 포함됨을 증명하기 쉽다. 더욱이 각 프로파일 $p{\displaystyle }$ ${\displaystyle$ p$}$에 대해$,$ $우리$는 C +${\displaystyle {}^{}}$(${\displaystyle {}^{}}$W ,${\displaystyle p}$ )${\displaystyle \subseteq }$ C (${\displaystyle W}$ ${\displaystyle ,p}$ $){\displaystyle C^{+}(W,p)\subseteq$C$(W,p$)}을$($W,p$)}$을(를) 가지고 있다.

나카무라 정리의 변종 (쿠마베와 미하라, 2011년 정리 2^[3]) $W{\displaystyle }$ ${\displaystyle W}$을(를) 간단한 게임으로 합시다$$. 그 다음 세 가지 진술은 동일하다.

1. < () ${\displaystyle \#X<\nu (W)}$;
2. 대다수의${\displaystyle {}^{}}불만$이${\displaystyle {}^{}}$없는 ${\displaystyle \mathrm{코어}C}$ +${\displaystyle }$( W$$, p ) {\$displaystyle$C^{+}(W$$$,p)}$은(는) 최대 요소가 있는 모든$$ $프로파일{\displaystyle }$ p ${\displaystyle p}$에 대해 비어 있지 않다.
3. 코어 $C{\displaystyle (W}$, p${\displaystyle }$) ${\displaystyle C(W,p)}$은(는) 최대 요소가 있는 기본 설정의 모든$$ 프로파일 $p{\displaystyle }$ ${\displaystyle p}$에 대해 비어 있지 않다$$.

언급

• Unlike Nakamura's original theorem, ${\displaystyle X}$ being finite is not a necessary condition for ${\displaystyle C^{+}(W,p)}$ or ${\displaystyle C(W,p)}$ to be nonempty for all profiles ${\displaystyle p}$. Even if an agenda ${\displaystyle X}$ has infinitely many alternatives, 불평등# < ( ) ${\displaystyle \#X<\nu (W)}$이(가) 충족되는 한 적절한 프로파일에 대한 요소가 코어에 있다.
• 정리의 문장은 만약 우리가 문 2와 3에서 "최대 요소가 있는 모든 $프로파일{\displaystyle }$ p ${\displaystyle p}$의 선호도를 "정확히 하나의 최대 요소가 있는 모든$$ 프로파일 $p{\displaystyle }$ ${\displaystyle p}"$ 또는 "선형으로 정렬된 선호도의 $모든$ 프로파일 p ${\displaystyle$ p$}"$로 대체한다면 유효하다.es는 최대 요소를 가지고 있다." (쿠마베와 미하라, 2011, 발의안 1)
• 나카무라의 악순환 선호에 대한 정리처럼, 이 정리는 $B{\displaystyle \mathcal{}}$ ${\${\$mathcal{B}$ -단순$$ 게임으로 확장될 수 있다. 정리는 나카무라 번호의 개념을 확장하여 우승 세트의 W ${\displaystyle \prime }$ ⊆ ${\displaystyle {\mathcal{}}^{}}$ {\^[13]$displaystyle W'\subseteq$ {\$mathcal {B}}$까지 연장할 수 있다(1과 2는 동등하다).

참고 항목

• 기바르-사테르스와이트 정리
• 메이 정리
• 투표의 역설

메모들