Número de Nakamura

Límite de las reglas de toma de decisiones colectivas

En la teoría de los juegos cooperativos y la teoría de la elección social , el número de Nakamura mide el grado de racionalidad de las reglas de agregación de preferencias (reglas de decisión colectiva), como las reglas de votación. Es un indicador del grado en que una regla de agregación puede producir elecciones bien definidas.

• Si el número de alternativas (candidatos; opciones) a elegir es menor que este número, entonces la regla en cuestión identificará las “mejores” alternativas sin ningún problema.

Por el contrario,

• Si el número de alternativas es mayor o igual a este número, la regla no podrá identificar las "mejores" alternativas para algún patrón de votación (es decir, para algún perfil ( tupla ) de preferencias individuales), porque surgirá una paradoja de votación (un ciclo generado como alternativa socialmente preferida a alternativa , a , y a ). ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle c}$ ${\displaystyle a}$

Cuanto mayor sea el número de Nakamura de una regla, mayor será el número de alternativas que puede abordar racionalmente. Por ejemplo, dado que (excepto en el caso de cuatro individuos (votantes)) el número de Nakamura de la regla de la mayoría es tres, la regla puede abordar hasta dos alternativas racionalmente (sin causar una paradoja). El número recibe su nombre de Kenjiro Nakamura  [ja] (1947–1979), un teórico de juegos japonés que demostró el hecho antes mencionado de que la racionalidad de la elección colectiva depende críticamente del número de alternativas. ^[1]

Descripción general

Para introducir una definición precisa del número de Nakamura, daremos un ejemplo de un "juego" (que subyace a la regla en cuestión) al que se le asignará un número de Nakamura. Supongamos que el conjunto de individuos consta de los individuos 1, 2, 3, 4 y 5. Detrás de la regla de la mayoría se encuentra la siguiente colección de coaliciones ("decisivas") (subconjuntos de individuos) que tienen al menos tres miembros:

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

A estos conjuntos se les puede asignar un número de Nakamura, que llamamos juegos simples . Más precisamente, un juego simple es simplemente un conjunto arbitrario de coaliciones; se dice que las coaliciones que pertenecen al conjunto son ganadoras ; las otras, perdedoras . Si todos los miembros de una coalición ganadora (al menos tres, en el ejemplo anterior) prefieren la alternativa x a la alternativa y, entonces la sociedad (de cinco individuos, en el ejemplo anterior) adoptará la misma clasificación ( preferencia social ).

El número de Nakamura de un juego simple se define como el número mínimo de coaliciones ganadoras con intersección vacía . (Al intersecar este número de coaliciones ganadoras, a veces se puede obtener un conjunto vacío. Pero al intersecar menos de este número, nunca se puede obtener un conjunto vacío). El número de Nakamura del juego simple anterior es tres, por ejemplo, ya que la intersección de dos coaliciones ganadoras cualesquiera contiene al menos un individuo, pero la intersección de las siguientes tres coaliciones ganadoras está vacía: , , . ${\displaystyle \{1,2,3\}}$ ${\displaystyle \{4,5,1\}}$ ${\displaystyle \{2,3,4\}}$

El teorema de Nakamura (1979 ^[2] ) establece la siguiente condición necesaria (también suficiente si el conjunto de alternativas es finito) para que un juego simple tenga un "núcleo" no vacío (el conjunto de alternativas socialmente "mejores") para todos los perfiles de preferencias individuales: el número de alternativas es menor que el número de Nakamura del juego simple. Aquí, el núcleo de un juego simple con respecto al perfil de preferencias es el conjunto de todas las alternativas tales que no hay ninguna alternativa que cada individuo en una coalición ganadora prefiera ; es decir, el conjunto de elementos máximos de la preferencia social. Para el ejemplo de juego mayoritario anterior, el teorema implica que el núcleo estará vacío (ninguna alternativa se considerará "mejor") para algún perfil, si hay tres o más alternativas. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$

Existen variantes del teorema de Nakamura que proporcionan una condición para que el núcleo no esté vacío (i) para todos los perfiles de preferencias acíclicas ; (ii) para todos los perfiles de preferencias transitivas ; y (iii) para todos los perfiles de órdenes lineales . Hay un tipo diferente de variante (Kumabe y Mihara, 2011 ^[3] ), que prescinde de la aciclicidad , el requisito débil de racionalidad. La variante proporciona una condición para que el núcleo no esté vacío para todos los perfiles de preferencias que tienen elementos máximos .

Para clasificar alternativas, existe un resultado muy conocido llamado " teorema de imposibilidad de Arrow " en la teoría de la elección social, que señala la dificultad para un grupo de individuos de clasificar tres o más alternativas. Para elegir entre un conjunto de alternativas (en lugar de clasificarlas ), el teorema de Nakamura es más relevante. ^[5] Una pregunta interesante es cuán grande puede ser el número de Nakamura. Se ha demostrado que para que un juego simple (finito o) computable algorítmicamente que no tiene un jugador con veto (un individuo que pertenece a cada coalición ganadora) tenga un número de Nakamura mayor que tres, el juego tiene que ser no fuerte . ^[6] Esto significa que hay una coalición perdedora (es decir, no ganadora) cuyo complemento también es perdedor. Esto a su vez implica que la no vacuidad del núcleo está asegurada para un conjunto de tres o más alternativas solo si el núcleo puede contener varias alternativas que no se pueden clasificar estrictamente. ^[8]

Estructura

Sea un conjunto no vacío (finito o infinito) de individuos . Los subconjuntos de se denominan coaliciones . Un juego simple (juego de votación) es una colección de coaliciones. (Equivalentemente, es un juego de coalición que asigna 1 o 0 a cada coalición). Suponemos que no está vacío y no contiene un conjunto vacío. Las coaliciones que pertenecen a están ganando ; las otras están perdiendo . Un juego simple es monótono si e implican . Es propio si implica . Es fuerte si implica . Un jugador con veto (vetador) es un individuo que pertenece a todas las coaliciones ganadoras. Un juego simple no es débil si no tiene ningún jugador con veto. Es finito si hay un conjunto finito (llamado portador ) tal que para todas las coaliciones , tenemos si y solo si . ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle W}$ ${\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}$ ${\displaystyle T\subseteq N}$ ${\displaystyle S}$ ${\displaystyle S\in W}$ ${\displaystyle S\cap T\in W}$

Sea un conjunto (finito o infinito) de alternativas , cuyo número cardinal (el número de elementos) es al menos dos. Una preferencia (estricta) es una relación asimétrica en : si (léase " se prefiere a "), entonces . Decimos que una preferencia es acíclica (no contiene ciclos ) si para cualquier número finito de alternativas , siempre que , ,…, , tenemos . Nótese que las relaciones acíclicas son asimétricas, por lo tanto, preferencias. ${\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}}$

Un perfil es una lista de preferencias individuales . Esto significa que el individuo prefiere alternativas a ese perfil . ${\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}$

Un juego simple con preferencias ordinales es un par formado por un juego simple y un perfil . Dado , una relación de dominancia (preferencia social) se define en por si y solo si hay una coalición ganadora que satisface a todos . El núcleo de es el conjunto de alternativas no dominadas por (el conjunto de elementos máximos de con respecto a ): ${\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)}$si y sólo si no existe tal que . ${\displaystyle y\in X}$ ${\displaystyle y\succ _{W}^{p}x}$

Definición y ejemplos

El número de Nakamura de un juego simple es el tamaño (número cardinal) de la colección más pequeña de coaliciones ganadoras con intersección vacía: ^[9] ${\displaystyle \nu (W)}$ ${\displaystyle W}$

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

si (ningún jugador con veto); ^[2] en caso contrario, (mayor que cualquier número cardinal). ${\displaystyle \cap W=\cap _{S\in W}S=\emptyset }$ ${\displaystyle \nu (W)=+\infty }$

Es fácil demostrar que si es un juego simple sin jugador con veto, entonces . ${\displaystyle W}$ ${\displaystyle 2\leq \nu (W)\leq \#N}$

Ejemplos para un número finito de individuos ( ) (véase Austen-Smith y Banks (1999), Lema 3.2 ^[4] ). Sea un juego simple que es monótono y propio. ${\displaystyle N=\{1,\ldots ,n\}}$ ${\displaystyle W}$

• Si es fuerte y sin jugador con veto, entonces . ${\displaystyle W}$ ${\displaystyle \nu (W)=3}$
• Si es el juego mayoritario (es decir, una coalición está ganando si y sólo si está formada por más de la mitad de los individuos), entonces si ; si . ${\displaystyle W}$ ${\displaystyle \nu (W)=3}$ ${\displaystyle n\neq 4}$ ${\displaystyle \nu (W)=4}$ ${\displaystyle n=4}$
• Si es una -regla (es decir, una coalición está ganando si y sólo si está formada por al menos individuos) con , entonces , donde es el entero más pequeño mayor o igual a . ${\displaystyle W}$ ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle n/2<q<n}$ ${\displaystyle \nu (W)=[n/(n-q)]}$ ${\displaystyle [x]}$ ${\displaystyle x}$

Ejemplos para un número contable de individuos ( ). Kumabe y Mihara (2008) estudian exhaustivamente las restricciones que imponen varias propiedades (monotonía, propiedad, fortaleza, no debilidad y finitud) para juegos simples a su número de Nakamura (la Tabla "Posibles números de Nakamura" a continuación resume los resultados). En particular, muestran que un juego simple computable algorítmicamente ^[10] sin un jugador con veto tiene un número de Nakamura mayor que 3 solo si es propio y no fuerte. ^[6] ${\displaystyle N=\{1,2,\ldots \}}$

Teorema de Nakamura para preferencias acíclicas

Teorema de Nakamura (Nakamura, 1979, Teoremas 2.3 y 2.5 ^[2] ). Sea un juego simple. Entonces el núcleo no está vacío para todos los perfiles de preferencias acíclicas si y solo si es finito y . ${\displaystyle W}$ ${\displaystyle C(W,p)}$ ${\displaystyle p}$ ${\displaystyle X}$ ${\displaystyle \#X<\nu (W)}$

Observaciones

• El teorema de Nakamura se cita a menudo en la siguiente forma, sin referencia al núcleo (por ejemplo, Austen-Smith y Banks, 1999, Teorema 3.2 ^[4] ): La relación de dominancia es acíclica para todos los perfiles de preferencias acíclicas si y solo si para todos los finitos (Nakamura 1979, Teorema 3.1 ^[2] ). ${\displaystyle \succ _{W}^{p}}$ ${\displaystyle p}$ ${\displaystyle \#B<\nu (W)}$ ${\displaystyle B\subseteq X}$
• El enunciado del teorema sigue siendo válido si reemplazamos "para todos los perfiles de preferencias acíclicas " por "para todos los perfiles de preferencias transitivas negativas " o por "para todos los perfiles de preferencias ordenadas linealmente (es decir, transitivas y totales)". ^[12] ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$

• El teorema se puede extender a juegos -simples. Aquí, la colección de coaliciones es un álgebra booleana arbitraria de subconjuntos de , como el -álgebra de conjuntos medibles de Lebesgue . Un juego -simple es una subcolección de . Los perfiles se restringen adecuadamente a los medibles: un perfil es medible si para todo , tenemos . ^[3] ${\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}}}$

Una variante del teorema de Nakamura para preferencias que pueden contener ciclos

En esta sección, descartamos el supuesto habitual de preferencias acíclicas. En su lugar, restringimos las preferencias a aquellas que tienen un elemento máximo en una agenda dada ( conjunto de oportunidades al que se enfrenta un grupo de individuos), un subconjunto de algún conjunto subyacente de alternativas. (Esta restricción débil sobre las preferencias podría ser de cierto interés desde el punto de vista de la economía del comportamiento ). En consecuencia, es apropiado pensar en una agenda aquí. Una alternativa es un elemento máximo con respecto a (es decir, tiene un elemento máximo ) si no existe tal que . Si una preferencia es acíclica sobre el conjunto subyacente de alternativas, entonces tiene un elemento máximo en cada subconjunto finito . ${\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}$

Introducimos un fortalecimiento del núcleo antes de enunciar la variante del teorema de Nakamura. Una alternativa puede estar en el núcleo incluso si hay una coalición ganadora de individuos que están "insatisfechos" con (es decir, cada uno prefiere algo a ). La siguiente solución excluye tal : ^[3] ${\displaystyle x}$ ${\displaystyle C(W,p)}$ ${\displaystyle i}$ ${\displaystyle x}$ ${\displaystyle i}$ ${\displaystyle y_{i}}$ ${\displaystyle x}$ ${\displaystyle x}$

Una alternativa está en el núcleo sin insatisfacción mayoritaria si no hay una coalición ganadora tal que para todos , no es máxima (existe alguna satisfaciente ). ${\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}$

Es fácil demostrar que depende únicamente del conjunto de elementos máximos de cada individuo y está incluido en la unión de tales conjuntos. Además, para cada perfil , tenemos . ${\displaystyle C^{+}(W,p)}$ ${\displaystyle p}$ ${\displaystyle C^{+}(W,p)\subseteq C(W,p)}$

Una variante del teorema de Nakamura (Kumabe y Mihara, 2011, Teorema 2 ^[3] ). Sea un juego simple. Entonces, las tres afirmaciones siguientes son equivalentes: ${\displaystyle W}$

1. ${\displaystyle \#X<\nu (W)}$;
2. el núcleo sin insatisfacción mayoritaria no está vacío para todos los perfiles de preferencias que tienen un elemento máximo; ${\displaystyle C^{+}(W,p)}$ ${\displaystyle p}$
3. El núcleo no está vacío para todos los perfiles de preferencias que tienen un elemento máximo. ${\displaystyle C(W,p)}$ ${\displaystyle p}$

Observaciones

• A diferencia del teorema original de Nakamura, ser finito no es una condición necesaria para que todos los perfiles sean no vacíos . Incluso si una agenda tiene infinitas alternativas, hay un elemento en los núcleos para los perfiles apropiados, siempre que se cumpla la desigualdad. ${\displaystyle X}$ ${\displaystyle C^{+}(W,p)}$ ${\displaystyle C(W,p)}$ ${\displaystyle p}$ ${\displaystyle X}$ ${\displaystyle \#X<\nu (W)}$
• El enunciado del teorema sigue siendo válido si reemplazamos "para todos los perfiles de preferencias que tienen un elemento máximo" en los enunciados 2 y 3 por "para todos los perfiles de preferencias que tienen exactamente un elemento máximo" o "para todos los perfiles de preferencias ordenados linealmente que tienen un elemento máximo" (Kumabe y Mihara, 2011, Proposición 1). ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$
• Al igual que el teorema de Nakamura para preferencias acíclicas, este teorema se puede extender a juegos -simples. El teorema se puede extender aún más (1 y 2 son equivalentes; implican 3) a conjuntos de conjuntos ganadores extendiendo la noción del número de Nakamura. ^[13] ${\displaystyle {\mathcal {B}}}$ ${\displaystyle W'\subseteq {\mathcal {B}}'}$

Véase también

• Teorema de Gibbard-Satterthwaite
• Teorema de May
• Paradoja de la votación

Notas

1. Suzuki, Mitsuo (1981). Teoría de juegos y elección social: artículos seleccionados de Kenjiro Nakamura . Keiso Shuppan.Nakamura recibió el título de Doctor en Ingeniería Social en 1975 del Instituto de Tecnología de Tokio.
2. Nakamura, K. (1979). "Los vetadores en un juego simple con preferencias ordinales". Revista Internacional de Teoría de Juegos . 8 : 55–61. doi :10.1007/BF01763051. S2CID  120709873.
3. Kumabe, M.; Mihara, HR (2011). "Teoría de agregación de preferencias sin aciclicidad: el núcleo sin insatisfacción mayoritaria" (PDF) . Juegos y comportamiento económico . 72 : 187–201. arXiv : 1107.0431 . doi :10.1016/j.geb.2010.06.008. S2CID  6685306.
4. Austen-Smith, David; Banks, Jeffrey S. (1999). Teoría política positiva I: preferencia colectiva. Ann Arbor: University of Michigan Press. ISBN 978-0-472-08721-1.
5. original de Nakamura es directamente relevante para la clase de reglas de agregación de preferencias simples , las reglas completamente descritas por su familia de coaliciones decisivas (ganadoras). (Dada una regla de agregación, una coalición es decisiva si siempre que cada individuo en prefiere , entonces también lo hace la sociedad). Austen-Smith y Banks (1999), ^[4] un libro de texto sobre la teoría de la elección social que enfatiza el papel del número de Nakamura, extiende el número de Nakamura a la clase más amplia (y empíricamente importante) de reglas de agregación neutrales (es decir, el etiquetado de las alternativas no importa) y monótonas (si se prefiere socialmente a , entonces aumentar el apoyo a sobre preserva esta preferencia social) (Teorema 3.3), y obtiene un teorema (Teorema 3.4) similar al de Nakamua. ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$
6. Kumabe, M.; Mihara, HR (2008). "Los números de Nakamura para juegos simples computables". Elección social y bienestar . 31 (4): 621. arXiv : 1107.0439 . doi :10.1007/s00355-008-0300-5. S2CID  8106333.
7. Kirman, A.; Sondermann, D. (1972). "Teorema de Arrow, muchos agentes y dictadores invisibles". Revista de teoría económica . 5 (2): 267–277. doi :10.1016/0022-0531(72)90106-8.
8. Existen juegos monótonos, propios, fuertes y simples sin un jugador con veto que tienen un número de Nakamura infinito. Un ultrafiltro no principal es un ejemplo, que puede usarse para definir una regla de agregación (función de bienestar social) que satisface las condiciones de Arrow si hay infinitos individuos. ^[7] Una desventaja seria de los ultrafiltros no principales para este propósito es que no son computables algorítmicamente.
9. El elemento mínimo del siguiente conjunto existe ya que todo conjunto no vacío de números ordinales tiene un elemento mínimo.
10. Véase una sección sobre el teorema de Rice para obtener la definición de un juego simple computable. En particular, todos los juegos finitos son computables.
11. En cada entrada se dan los posibles números de Nakamura para juegos simples computables, suponiendo que una coalición vacía está perdiendo. Los dieciséis tipos se definen en términos de las cuatro propiedades: monotonía, propiedad, fortaleza y no debilidad (falta de un jugador con veto). Por ejemplo, la fila correspondiente al tipo 1110 indica que entre los juegos simples computables monótonos (1), propios (1), fuertes (1), débiles (0, porque no son no débiles), los finitos tienen un número de Nakamura igual a y los infinitos no existen. La fila correspondiente al tipo 1101 indica que cualquier (y ningún ) es el número de Nakamura de algún juego simple finito (alternativamente, infinito) de este tipo. Obsérvese que entre los juegos simples no débiles, solo los tipos 1101 y 0101 alcanzan un número de Nakamura mayor que 3. ${\displaystyle +\infty }$ ${\displaystyle k\geq 3}$ ${\displaystyle k<3}$
12. La dirección "si" es obvia mientras que la dirección "solo si" es más fuerte que la afirmación del teorema dado anteriormente (la prueba es esencialmente la misma). Estos resultados a menudo se expresan en términos de preferencias débiles (por ejemplo, Austen-Smith y Banks, 1999, Teorema 3.2 ^[4] ). Defina la preferencia débil por . Entonces es asimétrica si y solo si es completa; es negativamente transitiva si y solo si es transitiva. es total si implica o . ${\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. El marco distingue el álgebra de coaliciones de la colección más amplia de conjuntos de individuos a los que se les puede asignar el estatus de ganadores/perdedores. Por ejemplo, es el álgebra de conjuntos recursivos y es el entramado de conjuntos recursivamente enumerables (Kumabe y Mihara, 2011, Sección 4.2). ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {\mathcal {B}}'}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {\mathcal {B}}'}$