Numer Nakamury

W teorii gier kooperacyjnych i teorii wyboru społecznego liczba Nakamury mierzy stopień racjonalności reguł agregacji preferencji (reguł zbiorowego podejmowania decyzji), takich jak zasady głosowania. Jest to wskaźnik stopnia, w jakim reguła agregacji może dawać dobrze zdefiniowane wybory.

• Jeśli liczba alternatyw (kandydatów; opcji) do wyboru jest mniejsza niż ta liczba, wówczas dana reguła bez problemu zidentyfikuje „najlepsze” alternatywy.

W przeciwieństwie,

• jeśli liczba alternatyw jest większa lub równa tej liczbie, reguła nie zidentyfikuje „najlepszych” alternatyw dla jakiegoś wzorca głosowania (tj. dla pewnego profilu ( krotki ) indywidualnych preferencji), ponieważ powstanie paradoks głosowania ( wygenerowany cykl , taki jak alternatywa $}$ preferowana do alternatywy , $do$${\ displaystyle b}$ do $displaystyle c$ i ${\ displaystyle c}$ do za $\ displaystyle a}$ ).

Im większa liczba Nakamury ma reguła, tym większa liczba alternatyw, z którymi reguła może racjonalnie sobie poradzić. Na przykład, ponieważ (z wyjątkiem przypadku czterech osób (wyborców)) liczba reguły większości Nakamury wynosi trzy, reguła może racjonalnie radzić sobie z maksymalnie dwiema alternatywami (bez powodowania paradoksu). Liczba została nazwana na cześć Kenjiro Nakamury (1947–1979), japońskiego teoretyka gier, który udowodnił powyższy fakt, że racjonalność zbiorowego wyboru zależy krytycznie od liczby alternatyw.

Przegląd

Aby wprowadzić precyzyjną definicję liczby Nakamury, podajemy przykład „gry” (podstawowej dla omawianej reguły), której zostanie przypisana liczba Nakamura. Załóżmy, że zbiór jednostek składa się z osób 1, 2, 3, 4 i 5. Za regułą większości stoi następujący zbiór („decydujących”) koalicji ( podzbiorów jednostek) mających co najmniej trzech członków:

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

Takim zbiorom, które nazywamy prostymi grami , można przypisać numer Nakamury . Mówiąc dokładniej, prosta gra jest po prostu arbitralnym zbiorem koalicji; o koalicjach należących do kolekcji mówi się, że wygrywają ; inni przegrywają . Jeśli wszyscy (co najmniej trzej, w powyższym przykładzie) członkowie zwycięskiej koalicji wolą alternatywę x od alternatywy y, to społeczeństwo (złożone z pięciu osób, w powyższym przykładzie) przyjmie ten sam ranking (preferencja społeczna ) .

Liczba Nakamura prostej gry jest zdefiniowana jako minimalna liczba zwycięskich koalicji z pustym przecięciem . (Przecinając tę ​​liczbę zwycięskich koalicji, można czasem otrzymać pusty zestaw. Ale przecinając liczbę mniejszą niż ta liczba, nigdy nie można uzyskać pustego zestawu). Na przykład liczba Nakamury w powyższej prostej grze wynosi trzy, ponieważ przecięcie dowolnych dwóch zwycięskich koalicji zawiera co najmniej jedną osobę, ale przecięcie następujących trzech zwycięskich koalicji jest puste: ${\ Displaystyle \ {1,2,3 \}}$ , ${\ Displaystyle \ {4,5,1 \}}$ , ${\ Displaystyle \ {2,3 ,4\}}$ .

Twierdzenie Nakamury (1979) daje następujący warunek konieczny (również wystarczający, jeśli zbiór alternatyw jest skończony) aby prosta gra miała niepusty „rdzeń” (zbiór społecznie „najlepszych” alternatyw) dla wszystkich profili indywidualnych preferencji: liczba alternatyw jest mniejsza niż liczba Nakamury prostej gry. Tutaj rdzeniem prostej gry w odniesieniu do profilu preferencji jest zbiór wszystkich alternatyw takich, że nie ma alternatywy $y}$$displaystyle$ że każda osoba w zwycięskiej koalicji $;$ czyli zbiór maksymalnych elementów preferencji społecznej. W przypadku powyższego przykładu gry większościowej twierdzenie oznacza, że ​​rdzeń będzie pusty (żadna alternatywa nie zostanie uznana za „najlepszą”) dla pewnego profilu, jeśli istnieją trzy lub więcej alternatyw.

Istnieją warianty twierdzenia Nakamury, które stawiają warunek, aby rdzeń był niepusty (i) dla wszystkich profili preferencji acyklicznych ; (ii) dla wszystkich profili przechodnich ; oraz (iii) dla wszystkich profili rzędów liniowych . Istnieje inny rodzaj wariantu (Kumabe i Mihara, 2011), który rezygnuje z acykliczności , słabego wymogu racjonalności. Wariant stawia warunek, aby rdzeń był niepusty dla wszystkich profili preferencji, które mają elementy maksymalne .

Jeśli chodzi o ranking alternatyw, istnieje bardzo dobrze znany wynik zwany „ twierdzeniem Arrowa o niemożliwości ” w teorii wyboru społecznego, który wskazuje na trudność grupy osób w uszeregowaniu trzech lub więcej alternatyw. Za wybór z zestawu alternatyw (zamiast rankingu im), twierdzenie Nakamury jest bardziej odpowiednie. Interesującym pytaniem jest, jak duża może być liczba Nakamury. Wykazano, że aby (skończona lub) algorytmicznie obliczalna prosta gra, która nie ma gracza weta (osoby należącej do każdej zwycięskiej koalicji), miała liczbę Nakamury większą niż trzy, gra musi być słaba . Oznacza to, że istnieje przegrywająca (tj. nie wygrywająca) koalicja, której uzupełnienie również przegrywa. To z kolei implikuje, że niepustość rdzenia jest zapewniona dla zestawu trzech lub więcej alternatyw tylko wtedy, gdy rdzeń może zawierać kilka alternatyw, których nie można ściśle uszeregować.

Struktura

Niech będzie ( $)$ niepustym zbiorem indywiduów . Podzbiory nazywane są $_$ . Prosta gra ( $gra$ w głosowanie) to zbiór . (Równoważnie jest to gra koalicyjna, w której każdej koalicji przypisuje się $W$ is nonempty and does not contain an empty set. The coalitions belonging to $W$ are wygrana ; inni przegrywają . Prosta gra ${$ monotoniczna , jeśli $\ Displaystyle S \ in W}$ i ${\ displaystyle S \ subseteq T}$ implikują ${\ displaystyle T \ in W}$ . Jest właściwe , jeśli implikuje ${\ Displaystyle S \ in W}$${\ Displaystyle N \ setminus S \ notin W}$ . Jest silny $Displaystyle N \ setminus S \ in$ jeśli implikuje $S$ \ Gracz weto (wetoer) to osoba należąca do wszystkich zwycięskich koalicji. Prosta gra nie jest słaba , jeśli nie ma w niej gracza weta. Jest skończony , jeśli istnieje skończony zbiór (nazywany nośnikiem ) ${\ Displaystyle T \ subseteq N}$ tak, że dla wszystkich koalicji mamy $S \ w W}$$Displaystyle$ iff ${\ Displaystyle S \ cap T \ in W}$ .

Niech będzie (skończonym lub nieskończonym $)$ zbiorem alternatyw , którego $wynosi$ kardynalna liczba elementów) co najmniej dwa (ścisła) preferencja jest relacją asymetryczną ${\ displaystyle$$X}$ : jeśli (czytaj " $succ y}$$\ displaystyle x}$ jest preferowana do \ ${\ Displaystyle y}$ "), a następnie ${\ Displaystyle y \ nie \ succ x}$$.$ Mówimy, że preferencja acykliczna ( nie zawiera cykli ), jeśli dla dowolnej skończonej liczby alternatywy ${\ Displaystyle x_ {1}, \ ldots, x_ {m}}$ , zawsze ${\ Displaystyle x_ {1} \ succ x_ {2}}$ , ${\ Displaystyle x_ {2} \ succ x_ {3}}$ ,…, ${\ Displaystyle x_ {m-1} \ succ x_ {m}}$ , mamy ${\ Displaystyle x_ {m} \ nie \ succ x_ {1}}$ . Zauważ, że relacje acykliczne są asymetryczne, stąd preferencje.

Profil to lista indywidualnych preferencji ${\ Displaystyle p = (\ succ _ {i} ^ {p}) _ {i \$$} succ _{i}^{p}}$ . Tutaj $i} ^ {p} y}$${\ displaystyle y}$ oznacza, że ​​jednostka $displaystyle$ alternatywę $x}$ y w profilu ${\ displaystyle p}$ .

Prosta $gra$ z preferencjami $to$ para $_$ z prostej Biorąc pod uwagę ${\ Displaystyle (W, p)}$$X}$${$ dominacji ( preferencje społeczne) jest zdefiniowana przez X ${\ Displaystyle x \ succ _ {W} ^ {p} y}$ wtedy i tylko wtedy, gdy istnieje zwycięska koalicja ${\ Displaystyle S \ in W}$ satysfakcjonująca ${\ Displaystyle x \ succ _ {i} ^ {p} y}$ dla wszystkich ${\ Displaystyle i \ w S}$ . rdzeń z ${\ Displaystyle$ , ${\ Displaystyle (W, p)}$ to zbiór alternatyw niezdominowanych przez $odniesieniu$ zbiór maksymalnych elementów ${\ Displaystyle X}$ ≻ $\ Displaystyle \ succ _ {W} ^ {p}})$ :

${\ Displaystyle x \ in C (W, p)}$ wtedy i tylko wtedy, gdy nie ma takiego, że ${\ Displaystyle y \ in X}$${\ Displaystyle y \succ _{W}^{p}x}$ .

Definicja i przykłady

Liczba Nakamury prostej gry to rozmiar (liczba kardynalna) najmniejszego zbioru zwycięskich koalicji z pustym przecięciem: $W) }$$\ nu ($

${\ Displaystyle \ nu (W) = \ min \ {\ # W ': W '\ subseteq W; \ czapka W' = \ pusty zestaw \}}$

jeśli $_$ _ w przeciwnym razie ${\ Displaystyle \ nu (W) = + \ infty}$ (większy niż jakakolwiek liczba główna).

$\ Displaystyle 2 \ równoważnik \ nu (W) \ równoważnik \# N}$ udowodnić, że jeśli jest to prosta gra bez gracza weta, to $2$ .

Przykłady $patrz Austen$ skończenie wielu indywiduów ( Smith i Banks (1999) Niech $będzie$ prostą grą, która jest monotonna i właściwa

• Jeśli jest $3$ i bez gracza weta, to ${\ Displaystyle \ nu (W) = 3$ }
• Jeśli jest grą $większościową$ (tj. koalicja wygrywa wtedy i tylko wtedy, gdy składa się z więcej niż połowy jednostek), to $displaystyle \ nu (W) = 3}$ jeśli ${\ Displaystyle n \ neq 4}$ ; ${\ Displaystyle \ nu (W) = 4}$ jeśli ${\ Displaystyle n = 4}$ .
• Jeśli $gdy składa$ regułą $)$$wtedy,$ z co najmniej osób z ${ \ Displaystyle n/2 <q <n}$ , wtedy ${\ Displaystyle \ nu (W) = [n/(nq)]}$ , gdzie ${\ Displaystyle [x]}$ jest najmniejszą liczbą całkowitą większą lub równą ${\ Displaystyle x}$ .

Przykłady dla co najwyżej policzalnie wielu osobników ( ${\ Displaystyle N = \ {1,2, \ ldots \}} )$ . Kumabe i Mihara (2008) kompleksowo badają ograniczenia, jakie różne właściwości (monotoniczność, poprawność, siła, niesłabość i skończoność) prostych gier nakładają na ich liczbę Nakamura (tabela „Możliwe liczby Nakamury” poniżej podsumowuje wyniki). W szczególności pokazują, że algorytmicznie obliczalna prosta gra bez gracza weta ma liczbę Nakamura większą niż 3 tylko wtedy, gdy jest właściwa i niesilna.

Możliwe liczby Nakamury

Typ	Gry skończone	Nieskończone gry
1111	3	3
1110	+∞	nic
1101	≥3	≥3
1100	+∞	+∞
1011	2	2
1010	nic	nic
1001	2	2
1000	nic	nic
0111	2	2
0110	nic	nic
0101	≥2	≥2
0100	+∞	+∞
0011	2	2
0010	nic	nic
0001	2	2
0000	nic	nic

Twierdzenie Nakamury dla preferencji acyklicznych

Twierdzenie Nakamury (Nakamura, 1979, Twierdzenia 2.3 i 2.5). Niech $będzie$ grą. ${\ Displaystyle \ # X <\ nu (W)}$ rdzeń $nie$$X$ pusty dla wszystkich profili wtedy i $jest$ i .

Uwagi

• $: jest acykliczny$ odniesienia do rdzenia (np. Austen-Smith i Banks, 1999, twierdzenie 3.2 $}$ wszystkich profili acyklicznych preferencji wtedy i tylko wtedy, gdy wszystkich skończonych $X}$$displaystyle$$B$ (Nakamura 1979, Twierdzenie 3.1).
• Stwierdzenie twierdzenia pozostaje ważne, jeśli zastąpimy „dla wszystkich profili $dla$ acyklicznych” przez „dla wszystkich profili preferencji ujemnie przechodnich ” lub przez „ wszystkich profili $p}$${\ displaystyle$$p$ liniowo uporządkowanych ( tj. przechodnich i całkowitych) preferencji”.

• Twierdzenie można rozszerzyć na $.$ gry Tutaj zbiór $Lebesgue'a$$jest$ dowolną algebrą Boole'a , takich jak $mierzalnych$ zbiorów . ZA ${\ Displaystyle {\ mathcal {B}}}$ - prosta gra jest podkolekcją ${\ displaystyle {\ mathcal {B}}}$ . Profile ${\ Displaystyle \ {i: x \ succ _ {i} ^ {p} y \} \ w {\ mathcal {B}}}$$, y \ in X}$ do mierzalnych: profil $\ displaystyle$ mierzalny , jeśli dla wszystkich p .

Wariant twierdzenia Nakamury dla preferencji, które mogą zawierać cykle

W tej sekcji odrzucamy zwykłe założenie preferencji acyklicznych. Zamiast tego ograniczamy preferencje do tych, które mają maksymalny element w danym planie ( zestaw możliwości , z którym ma do czynienia grupa osób), podzbiór pewnego podstawowego zestawu alternatyw. $ograniczenie$ To słabe preferencji może być interesujące z punktu widzenia ekonomii behawioralnej ). W związku z tym należy pomyśleć o programie tutaj. Alternatywa ${\ Displaystyle x \ w X}$ ≻ ja $_ {i} ^ {p}}$$}$ ma element maksymalny x $\ displaystyle x}$ } ja $}$ ), jeśli nie ma takiego, że $\$$Displaystyle y \ succ _ {i} ^ {p} x} y ∈ X {\ Displaystyle y \$ . Jeśli preferencja jest acykliczna w stosunku do podstawowego zestawu alternatyw, to ma maksymalny element na każdym skończony podzbiór ${\ Displaystyle X}$ .

Wprowadzamy wzmocnienie rdzenia przed podaniem wariantu twierdzenia Nakamury. Alternatywa $nawet$ w rdzeniu, jeśli istnieje zwycięska koalicja jednostek $,$ które są „niezadowolone $}$${\ Displaystyle x}$$($ tj. każdy trochę ${\ Displaystyle y_ {i}}$ do ${\ displaystyle x}$ ). Poniższe rozwiązanie wyklucza takie : ${\ displaystyle x$ }

Alternatywny ${\ displayStyle x \ in x}$ znajduje się w rdzeniu ${\ displayStyle c^{ +} (w, p)} bez$$\ \ displish I \ in S}$ większości, jeśli nie ma koalicji wygranej ${\ displayStyle s \ in W}$ że ​​dla wszystkich , ${\ scards x {\ scards$ -maksimal ( istnieje trochę ${\ Displaystyle y_ {i} \ w X}$ satysfakcjonujące ${\ Displaystyle y_ {i} \ succ _ {i} ^ {p} x})$ .

Łatwo jest udowodnić, że $zależy tylko od$ elementów każdego osobnika i jest zawarta Ponadto dla każdego profilu mamy do $\ Displaystyle C ^ {+} (W, p) \ subseteq C (W, p$$⊆$ .

Wariant twierdzenia Nakamury (Kumabe i Mihara, 2011, Twierdzenie 2). Niech $będzie$ grą. Wtedy następujące trzy stwierdzenia są równoważne:

1. ${\ Displaystyle \ # X <\ nu (W)}$ ;
2. rdzeń bez niezadowolenia $,$ wszystkich $maksymalny$ które
3. rdzeń nie $jest pusty$ dla wszystkich $.$

Uwagi

• $C (W, p)}$$Displaystyle$$twierdzenia$ Nakamury, nie jest dla do ( $\$ niepuste dla wszystkich profili ${\ displaystyle p}$ . Nawet jeśli program jest ${\ displaystyle X}$$wiele alternatyw$ element dla odpowiednich profili, o ile nierówność spełniona
• Stwierdzenie twierdzenia pozostaje ważne, jeśli zastąpimy „dla wszystkich profili $,$ które mają element maksymalny” w stwierdzeniach 2 i 3, przez „dla wszystkich profili $,$ które mają dokładnie jeden maksymalny element” lub „dla wszystkich profili $uporządkowanych$ preferencji , które mają maksymalny element” (Kumabe i Mihara, 2011, Propozycja 1) .
• Podobnie jak twierdzenie Nakamury dotyczące preferencji acyklicznych, twierdzenie to można rozszerzyć na $.$ gry Twierdzenie można rozszerzyć jeszcze dalej (1 i 2 są równoważne; implikują $zbiory$ zestawów poprzez pojęcia Numer Nakamury.

Zobacz też

• Twierdzenie Gibbarda-Satterthwaite'a
• Twierdzenie Maya
• Paradoks głosowania