Nakamura číslo - Nakamura number

v teorie kooperativní hry a teorie sociální volby, Nakamura číslo Měří míru racionality pravidel agregace preferencí (pravidla kolektivního rozhodování), jako jsou pravidla hlasování. Je to ukazatel míry, do jaké může pravidlo agregace přinést dobře definované volby.

  • Pokud je počet alternativ (kandidátů; možností) na výběr menší než tento počet, pak dané pravidlo bez problémů identifikuje „nejlepší“ alternativy.

V porovnání,

  • pokud je počet alternativ větší nebo roven tomuto počtu, pravidlo nedokáže určit „nejlepší“ alternativy pro určitý způsob hlasování (tj. pro některé profil (n-tice ) individuálních preferencí), protože a volební paradox vznikne (a cyklus generované jako alternativa společensky upřednostňována před alternativou , na , a na ).

Čím větší číslo má Nakamura, tím větší je počet alternativ, s nimiž se pravidlo může racionálně vypořádat. Například, protože (s výjimkou čtyř osob (voličů)) je Nakamurovo číslo většinového pravidla tři, pravidlo může zabývat se až dvěma alternativami racionálně (aniž by to způsobilo paradox). Číslo je pojmenováno po Kenjiro Nakamura (1947–1979), japonském teoretikovi her, který dokázal výše uvedený fakt, že racionalita kolektivní volby kriticky závisí na počtu alternativ.[1]

Přehled

Abychom představili přesnou definici čísla Nakamura, uvedeme příklad „hry“ (která je základem dotyčného pravidla), ke které bude číslo Nakamura přiřazeno. Předpokládejme, že množinu jednotlivců tvoří jednotlivci 1, 2, 3, 4 a 5. Za většinovým pravidlem je následující kolekce („rozhodující“) koalice (podmnožiny jednotlivců) mající alespoň tři členy:

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

Takovým sbírkám, kterým říkáme, lze přiřadit číslo Nakamura jednoduché hryPřesněji, a jednoduchá hra je jen svévolná sbírka koalic, o koalicích, které do ní patří, se říká, že jsou vítězný; ostatní ztrácíPokud všichni (alespoň tři, v příkladu výše) členové vítězné koalice upřednostňují alternativu x před alternativou y, pak společnost (z pěti jednotlivců, v příkladu výše) přijme stejné hodnocení (sociální preference).

The Nakamura číslo jednoduché hry je definován jako minimální počet vítězných koalic s prázdnými průsečík (Protínáním tohoto počtu vítězných koalic lze někdy získat prázdnou sadu. Ale protínáním menšího než tohoto počtu nelze nikdy získat prázdnou sadu.) Nakamurovo číslo výše uvedené jednoduché hry je například tři, protože křižovatka dvou vítězných koalic obsahuje alespoň jednoho jednotlivce, ale křižovatka následujících tří vítězných koalic je prázdná: , , .

Nakamurova věta (1979[2]) dává následující nezbytnou (také dostatečnou, pokud je sada alternativ konečná) podmínka pro to, aby jednoduchá hra měla neprázdné „jádro“ (soubor sociálně „nejlepších“ alternativ) pro všechny profily individuálních preferencí: počet alternativ je méně než Nakamura číslo jednoduché hry. Zde je jádro jednoduché hry s ohledem na profil preferencí je sada všech alternativ taková, že neexistuje žádná alternativa že každý jednotlivec ve vítězné koalici dává přednost ; tj. soubor maximální prvky sociálního preference. U výše uvedeného příkladu většinové hry věta naznačuje, že jádro bude prázdné (žádná alternativa nebude považována za „nejlepší“) pro nějaký profil, pokud existují tři nebo více alternativ.

Existují varianty Nakamurovy věty, které poskytují podmínku pro neprázdnost jádra (i) pro všechny profily acyklický ii) pro všechny profily tranzitivní preference; a (iii) pro všechny profily lineární objednávkyExistuje jiná varianta (Kumabe a Mihara, 2011[3]), který upustí od acyklicitaVarianta dává podmínku, aby jádro bylo neprázdné pro všechny profily preferencí, které mají maximální prvky.

Pro hodnocení alternativ, existuje velmi dobře známý výsledek zvaný „Věta o nemožnosti šipky „v teorii sociální volby, která poukazuje na obtížnost skupiny jednotlivců při hodnocení tří nebo více alternativ výběr ze sady alternativ (místo hodnocení Nakamurova věta je relevantnější.[5]Zajímavou otázkou je, jak velké může být číslo Nakamury. Ukázalo se, že pro (konečnou nebo) algoritmicky vypočítatelnou jednoduchou hru, která nemá hráče veta (jedinec, který patří do každé vítězné koalice), má číslo Nakamura větší než tři , hra musí být není silný.[6]To znamená, že existuje ztrácí (tj. nevyhrávat) koalice, jejíž doplněk také ztrácí. To zase znamená, že neprázdnost jádra je zajištěna pro sadu tří nebo více alternativ, pouze pokud jádro může obsahovat několik alternativ, které nelze přesně zařadit.[8]

Rámec

Nechat být (konečný nebo nekonečný) neprázdný soubor JednotlivciPodskupiny se nazývají koalice.A jednoduchá hra (hlasovací hra) je sbírka (Rovněž se jedná o koaliční hru, která každé koalici přiřadí buď 1 nebo 0.) Předpokládáme, že je neprázdné a neobsahuje prázdnou množinu jsou vítězný; ostatní jsou ztrácí.Jednoduchá hra je monotóní -li a naznačit . to je správně -li naznačuje .To je silný -li naznačuje .A vetovat hráče (vetoer) je jednotlivec, který patří do všech vítězných koalic. jednoduchá hra je slabý pokud nemá hráče veta konečný pokud existuje konečná množina (nazývá se a dopravce) takové, že pro všechny koalice , my máme iff .

Nechat být (konečnou nebo nekonečnou) množinou alternativy, jehož základní číslovka (počet prvků) je nejméně dva. A (přísné) přednost je asymetrický vztah na :li (přečíst „ se dává přednost "), pak Říkáme, že preference je acyklický (neobsahuje cykly) pokud pro jakýkoli konečný počet alternativ kdykoli , ,…, ,my máme . Všimněte si, že acyklické vztahy jsou asymetrické, tedy preference.

A profil je seznam individuálních preferencí .Tady znamená, že jednotlivec upřednostňuje alternativu na v profilu .

A jednoduchá hra s řadovými preferencemi je pár skládající se z jednoduché hry a profil Uvedeno , a dominance vztah (sociální preference) je definováno na podle jen tehdy, pokud existuje vítězná koalice uspokojující pro všechny .v jádro z je sada alternativ, které nejsou jmenovány (sada maximálních prvků s ohledem na ):

právě tehdy, když není takhle .

Definice a příklady

The Nakamura číslo jednoduché hry je velikost (základní číslo) nejmenší sbírky vítězných koalic s prázdnou křižovatkou:[9]

-li (žádný hráč veta);[2] v opačném případě, (větší než jakékoli hlavní číslo).

je snadné dokázat, že pokud je tedy jednoduchá hra bez hráče veta .

Příklady pro konečně mnoho jednotlivců () (viz Austen-Smith and Banks (1999), Lemma 3.2[4]).Nechat být jednoduchá hra, která je monotónní a správná.

  • Li je tedy silný a bez hráče veta .
  • Li je většinová hra (tj. koalice vyhrává právě tehdy, pokud se skládá z více než poloviny jednotlivců) -li ; -li .
  • Li je -rule (tj. koalice vyhrává právě tehdy, pokud se skládá alespoň z jednotlivci) s , pak , kde je nejmenší celé číslo větší nebo rovno .

Příklady nanejvýš spočetně mnoho jednotlivců (Kumabe a Mihara (2008) komplexně studují omezení, která různé vlastnosti (monotónnost, správnost, silnost, slabost a konečnost) jednoduchých her ukládají na jejich číslo Nakamura (níže uvedená tabulka „Možná čísla Nakamury“ shrnuje výsledky). Zejména ukazují, že jde o algoritmicky vypočítatelnou jednoduchou hru [10]bez hráče veta má číslo Nakamura větší než 3, pouze pokud je správné a neohrožené.[6]

Možná čísla Nakamury[11]
TypKonečné hryNekonečné hry
111133
1110+∞žádný
1101≥3≥3
1100+∞+∞
101122
1010žádnýžádný
100122
1000žádnýžádný
011122
0110žádnýžádný
0101≥2≥2
0100+∞+∞
001122
0010žádnýžádný
000122
0000žádnýžádný

Nakamurova věta o acyklických preferencích

Nakamurova věta (Nakamura, 1979, Věty 2.3 a 2.5[2]).Nechat být jednoduchá hra. Pak jádro je neprázdné pro všechny profily acyklických preferencí právě tehdy je konečný a .

Poznámky

  • Nakamurova věta je často citována v následující formě bez odkazu na jádro (např. Austen-Smith and Banks, 1999, Theorem 3.2[4]): Vztah dominance je acyklický pro všechny profily acyklických preferencí právě tehdy pro všechny konečné (Nakamura 1979, Věta 3.1[2]).
  • Výrok věty zůstane platný, pokud nahradíme „pro všechny profily z acyklický předvolby „od“ pro všechny profily z negativně tranzitivní předvolby „nebo“ pro všechny profily z lineárně uspořádáno (tj. přechodné a celkové) preference ".[12]
  • Věta může být rozšířena na - jednoduché hry. Tady, kolekce koalic je libovolný Booleova algebra podskupin , tak jako -algebra z Lebesgue měřitelný sady. A -jednoduchá hra je podkolekce . Profily jsou vhodně omezeny na měřitelné profily: profil je měřitelný pokud pro všechny , my máme .[3]

Varianta Nakamurovy věty o preferencích, která může obsahovat cykly

V této části zahodíme obvyklý předpoklad acyklických preferencí. Místo toho omezíme preference na ty, které mají v daném okamžiku maximální prvek denní program (sada příležitostí s níž je konfrontována skupina jednotlivců), podmnožina některé základní sady alternativ. (Toto slabé omezení preferencí může být z hlediska behaviorální ekonomie.) Proto je vhodné myslet na jako denní program zde. Alternativa je maximální prvek s ohledem na (tj., má maximální prvek ) pokud není takhle . Pokud je preference acyklická oproti základní sadě alternativ, pak má maximální prvek na každé konečný podmnožina .

Před uvedením varianty Nakamurovy věty představíme posílení jádra. Alternativa může být v jádru i když existuje vítězná koalice jednotlivců s nimiž „nejsou spokojeni“ (tj. každý preferuje některé na Následující řešení vylučuje takový :[3]

Alternativní je v jádro bez většinové nespokojenosti pokud neexistuje vítězná koalice takové, že pro všechny , je ne-maximální (některé existují uspokojující ).

Je snadné to dokázat záleží pouze na množině maximálních prvků každého jednotlivce a je zahrnuto do sjednocení těchto sad. Navíc pro každý profil , my máme .

Varianta Nakamurovy věty (Kumabe and Mihara, 2011, Theorem 2[3]).Nechat být jednoduchá hra. Pak jsou následující tři výroky rovnocenné:

  1. ;
  2. jádro bez většinové nespokojenosti je pro všechny profily neprázdné preferencí, které mají maximální prvek;
  3. jádro je neprázdné pro všechny profily preferencí, které mají maximální prvek.

Poznámky

  • Na rozdíl od Nakamurovy původní věty být konečný je není nutnou podmínkou pro nebo být neprázdný pro všechny profily . I když program má nekonečně mnoho alternativ, existuje prvek v jádrech pro vhodné profily, pokud je nerovnost je spokojen.
  • Výrok věty zůstane platný, pokud nahradíme „pro všechny profily preferencí, které mají u všech profilů maximální prvek „v příkazech 2 a 3 od“ preferencí, které mají přesně jeden maximální prvek „nebo“ pro všechny profily z lineárně uspořádáno preference, které mají maximální prvek “(Kumabe and Mihara, 2011, Proposition 1).
  • Stejně jako Nakamurova věta o acyklických preferencích lze tuto větu rozšířit na - jednoduché hry. Věta může být rozšířena ještě dále (1 a 2 jsou ekvivalentní; znamenají 3) na sbírky výherních sad rozšířením pojmu Nakamurova čísla.[13]

Viz také

Poznámky

  1. ^ Suzuki, Mitsuo (1981). Teorie her a sociální volba: Vybrané příspěvky Kenjira Nakamury. Keiso Shuppan. Nakamura získal doktorát v oboru sociálního inženýrství v roce 1975 na Tokijském technologickém institutu.
  2. ^ A b C d Nakamura, K. (1979). "Vetaři v jednoduché hře s řadovými preferencemi". International Journal of Game Theory. 8: 55–61. doi:10.1007 / BF01763051.
  3. ^ A b C d Kumabe, M .; Mihara, H. R. (2011). „Teorie agregace preferencí bez acyklicity: jádro bez většinové nespokojenosti“ (PDF). Hry a ekonomické chování. 72: 187–201. arXiv:1107.0431. doi:10.1016 / j.geb.2010.06.008.
  4. ^ A b C d Austen-Smith, David; Banks, Jeffrey S. (1999). Pozitivní politická teorie I: Kolektivní preference. Ann Arbor: University of Michigan Press. ISBN  978-0-472-08721-1. Externí odkaz v | název = (Pomoc)
  5. ^ Nakamura originál věta je přímo relevantní pro třídu jednoduchý pravidla agregace preferencí, pravidla zcela popsaná jejich rodinou rozhodujících (vítězných) koalic. (Vzhledem k pravidlu agregace je koalice je rozhodující pokud kdykoli každý jednotlivec v preferuje na , pak také společnost.) Austen-Smith and Banks (1999),[4]učebnice teorie sociální volby, která zdůrazňuje roli Nakamurova čísla, rozšiřuje Nakamurovo číslo na širší (a empiricky důležitou) třídu neutrální(tj. na označování alternativ nezáleží) amonotóní (li je společensky preferováno , pak zvýšení podpory pro přes zachovává tuto sociální preference) pravidla agregace (Theorem 3.3) a získá teorém (Theorem 3.4) podobný Nakamua.
  6. ^ A b Kumabe, M .; Mihara, H. R. (2008). „Čísla Nakamury pro vypočítatelné jednoduché hry“. Sociální volba a sociální péče. 31 (4): 621. arXiv:1107.0439. doi:10.1007 / s00355-008-0300-5.
  7. ^ Kirman, A .; Sondermann, D. (1972). „Arrowova věta, mnoho agentů a neviditelní diktátoři“. Journal of Economic Theory. 5: 267. doi:10.1016/0022-0531(72)90106-8.
  8. ^ Existují monotónní, správné a silné jednoduché hry bez hráče veta, které mají nekonečné číslo Nakamura. Nonprincipal ultrafiltr je příklad, který lze použít k definování agregačního pravidla (funkce sociální péče) splňujícího podmínky Arrowu, pokud existuje nekonečně mnoho jednotlivců.[7]Vážnou nevýhodou neprincipitních ultrafiltrů pro tento účel je, že nejsou algoritmicky vypočítatelné.
  9. ^ Minimální prvek následující sady existuje, protože každá neprázdná sada řadové číslovky má nejmenší prvek.
  10. ^ Vidět část pro Riceovu větu pro definici vypočítatelné jednoduché hry. Zejména všechny konečné hry jsou vypočítatelné.
  11. ^ V každé položce jsou uvedena možná čísla Nakamury pro vypočítatelné jednoduché hry, za předpokladu, že ztrácí prázdná koalice. Šestnáct typů je definováno z hlediska čtyř vlastností: monotónnost, správnost, síla a neoslabení (nedostatek hráče veta). Například řádek odpovídající typu 1110 naznačuje, že mezi monotónními (1), správnými (1), silnými (1), slabými (0, protože nejsou slabé) vypočítatelné jednoduché hry, konečné mají číslo Nakamury rovné a nekonečné neexistují. Řádek odpovídající typu 1101 označuje, že existuje (a žádná ) je Nakamurovo číslo nějaké konečné (alternativně nekonečné) jednoduché hry tohoto typu. Uvědomte si, že mezi slabými jednoduchými hrami pouze typy 1101 a 0101 dosahují Nakamurova čísla většího než 3.
  12. ^ Směr „pokud“ je zřejmý, zatímco směr „pouze pokud“ je silnější než výrok věty uvedený výše (důkaz je v podstatě stejný). Tyto výsledky jsou často uváděny ve smyslu slabý preference (např. Austen-Smith and Banks, 1999, Theorem 3.2[4]Definujte slabé preference podle . Pak je asymetrický iff je kompletní; je negativně tranzitivní iff je tranzitivní. je celkový -li naznačuje nebo .
  13. ^ Rámec rozlišuje algebru z koalice z větší sbírky ze sad jednotlivců, kterým lze přiřadit status vítězství / prohry. Například, je algebra rekurzivní množiny a je mříž z rekurzivně vyčíslitelné sady (Kumabe a Mihara, 2011, oddíl 4.2).