número de nakamura

Límite de las reglas de toma de decisiones colectivas

En la teoría de 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 de hasta qué punto una regla de agregación puede generar opciones bien definidas.

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

A diferencia de,

• si el número de alternativas es mayor o igual a este número, la regla no 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 que tenga una regla, mayor será el número de alternativas que la regla puede abordar racionalmente. Por ejemplo, dado que (excepto en el caso de cuatro individuos (votantes)) el número de regla de mayoría de Nakamura es tres, la regla puede abordar racionalmente hasta dos alternativas (sin causar una paradoja). El número lleva el nombre de Kenjiro Nakamura  [ja] (1947-1979), un teórico de juegos japonés que demostró el hecho anterior de que la racionalidad de la elección colectiva depende fundamentalmente del número de alternativas. ^[1]

Descripción general

Para introducir una definición precisa del número de Nakamura, damos un ejemplo de un "juego" (subyacente 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 está 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 dichas colecciones, que llamamos juegos simples , se les puede asignar un número Nakamura . Más precisamente, un juego simple no es más que una colección arbitraria de coaliciones; las coaliciones pertenecientes a la colección se dice que están ganando ; los demás perdiendo . Si todos los miembros (al menos tres, en el ejemplo anterior) de una coalición ganadora 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 cruzar este número de coaliciones ganadoras, a veces se puede obtener un conjunto vacío. Pero al cruzar 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 el La intersección de dos coaliciones ganadoras cualesquiera contiene al menos un individuo, pero la intersección de las tres coaliciones ganadoras siguientes está vacía: , , . ${\displaystyle \{1,2,3\}}$ ${\displaystyle \{4,5,1\}}$ ${\displaystyle \{2,3,4\}}$

El teorema de Nakamura (1979 ^[2] ) proporciona 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 individuos. preferencias: 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 existe ninguna alternativa que prefiera cada individuo en una coalición ganadora ; 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 . Existe un tipo diferente de variante (Kumabe y Mihara, 2011 ^[3] ), que prescinde de la aciclicidad , el débil requisito de la racionalidad. La variante establece una condición para que el núcleo no esté vacío para todos los perfiles de preferencias que tengan 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 a la hora 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 qué tan grande puede ser el número de Nakamura. Se ha demostrado que para que un juego simple (finito o) algorítmicamente computable que no tiene 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 está perdiendo. Esto, a su vez, implica que la no vacuidad del núcleo está asegurada para un conjunto de tres o más alternativas sólo si el núcleo puede contener varias alternativas que no pueden clasificarse estrictamente. ^[8]

Estructura

Sea un conjunto de individuos (finito o infinito) no vacío . Los subconjuntos de se llaman coaliciones . Un juego simple (juego de votación) es una colección de coaliciones. (De manera equivalente, es un juego de coalición que asigna 1 o 0 a cada coalición). Suponemos que no está vacío y que no contiene un conjunto vacío. Las coaliciones pertenecientes a están ganando ; los demás están perdiendo . Un juego simple es monótono si e implica . Es apropiado si implica . Es fuerte si implica . Un jugador con veto (vetoer) 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 iff . ${\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 . Tenga en cuenta que las relaciones acíclicas son asimétricas, de ahí las 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 . Aquí significa que el individuo prefiere una alternativa al 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 por si y sólo si hay una coalición ganadora que satisfaga 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 eso . ${\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 (sin 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 se trata de 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 ( ) (ver Austen-Smith y Banks (1999), Lema 3.2 ^[4] ). Sea un juego simple, monótono y adecuado. ${\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 gana 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 gana 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, como máximo, un número contable de individuos ( ). Kumabe y Mihara (2008) estudian exhaustivamente las restricciones que varias propiedades (monotonicidad, propiedad, fortaleza, no debilidad y finitud) imponen a su número de Nakamura para juegos simples (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 sólo si es adecuado y no fuerte. ^[6] ${\displaystyle N=\{1,2,\ldots \}}$

Teorema de Nakamura para las 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 sólo 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 de la siguiente forma, sin hacer referencia a su 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 sólo si para todos finito (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 negativamente transitivas " o por "para todos los perfiles de preferencias linealmente ordenadas (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 limitan adecuadamente a los medibles: un perfil es medible si para todos 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 las preferencias que pueden contener ciclos.

En esta sección descartamos el supuesto habitual de preferencias acíclicas. En cambio, restringimos las preferencias a aquellas que tienen un elemento máximo en una agenda determinada ( el conjunto de oportunidades al que se enfrenta un grupo de individuos), un subconjunto de algún conjunto subyacente de alternativas. (Esta débil restricción a las preferencias podría ser de algún interés desde el punto de vista de la economía conductual ). En consecuencia, es apropiado considerarla como 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" (es decir, cada uno prefiere a algunos ). 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 es en el núcleo sin insatisfacción mayoritaria si no hay una coalición ganadora tal que para todos , no sea máxima (exista alguna satisfacción ). ${\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 dichos 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 siguientes tres afirmaciones 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 ni ser no vacío para todos los perfiles . Incluso si una agenda tiene infinitas alternativas, hay un elemento en los núcleos para perfiles apropiados, siempre y cuando se satisfaga 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 linealmente ordenadas". que tienen un elemento maximal" (Kumabe y Mihara, 2011, Proposición 1). ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$
• Al igual que el teorema de Nakamura para las preferencias acíclicas, este teorema se puede extender a juegos simples. El teorema puede extenderse aún más (1 y 2 son equivalentes; implican 3) a colecciones de conjuntos ganadores ampliando la noción del número de Nakamura. ^[13] ${\displaystyle {\mathcal {B}}}$ ${\displaystyle W'\subseteq {\mathcal {B}}'}$

Ver también

• Teorema de Gibbard-Satterthwaite
• teorema de mayo
• 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ó su doctorado en Ingeniería Social en 1975 del Instituto de Tecnología de Tokio.
2. Nakamura, K. (1979). "Los vetantes en un juego sencillo con preferencias ordinales". Revista Internacional de Teoría de Juegos . 8 : 55–61. doi :10.1007/BF01763051. S2CID  120709873.
3. Kumabe, M.; Mihara, recursos humanos (2011). "Teoría de la 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; Bancos, Jeffrey S. (1999). Teoría política positiva I: Preferencia colectiva. Ann Arbor: Prensa de la Universidad de Michigan. 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 cada individuo prefiere hacerlo , 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 de Nakamura número, 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 alternativas no importa) y monótonas (si se prefiere socialmente , entonces aumentar el apoyo a over preserva esta preferencia social) (Teorema 3.3) y obtener 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, recursos humanos (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). "El 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 simples, monótonos, adecuados y fuertes sin un jugador con veto que tienen un número de Nakamura infinito. Un ultrafiltro no principal es un ejemplo, que se puede utilizar para definir una regla de agregación (función de bienestar social) que satisfaga las condiciones de Arrow si hay una cantidad infinita de individuos. ^[7] Un grave inconveniente 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. Consulte una sección sobre el teorema de Rice para conocer 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 cuatro propiedades: monotonicidad, idoneidad, 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), propio (1), fuerte (1), débil (0, porque no no débil), los finitos tienen un número de Nakamura igual e infinito. los que no existen. La fila correspondiente al tipo 1101 indica que any (y no ) es el número de Nakamura de algún juego simple finito (alternativamente, infinito) de este tipo. Observe que entre los juegos simples no débiles, sólo 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 "sólo si" es más fuerte que el enunciado 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étrico si y sólo si es completo; es negativamente transitivo sif es transitivo. 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 ganador/perdedor. Por ejemplo, es el álgebra de conjuntos recursivos y es la red de conjuntos recursivamente enumerables (Kumabe y Mihara, 2011, Sección 4.2). ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {\mathcal {B}}'}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {\mathcal {B}}'}$