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 la votación ( un ciclo generado como alternativa socialmente preferido a alternativo , a , y a ).
Cuanto mayor sea el número de Nakamura que tenga una regla, mayor será el número de alternativas con las que la regla puede tratar racionalmente. Por ejemplo, dado que (excepto en el caso de cuatro individuos (votantes)) el número de Nakamura de la regla de mayoría es tres, la regla puede tratar hasta dos alternativas de manera racional (sin causar una paradoja). El número lleva el nombre de Kenjiro Nakamura (1947-1979), un teórico de juegos japonés que demostró el hecho anterior de que la racionalidad de la elección colectiva depende de manera crítica 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. Suponga 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}}
Se puede asignar un número de Nakamura a tales colecciones, que llamamos juegos simples . Más precisamente, un juego simple es simplemente una colección arbitraria de coaliciones; se dice que las coaliciones pertenecientes a la colección 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 contiene al menos un individuo, pero la intersección de las tres coaliciones ganadoras siguientes está vacía:, , .
El teorema de Nakamura (1979 [2] ) da 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. tal que no hay alternativa que cada individuo en una coalición ganadora prefiere ; 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.
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 , la débil exigencia de la racionalidad. La variante da una condición para que el núcleo no esté vacío para todos los perfiles de preferencias que tienen elementos máximos .
Para la clasificación de 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 de un grupo de individuos para 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 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 está perdiendo. Esto, a su vez, implica que el no vacío del núcleo está asegurado para un conjunto de tres o más alternativas solo si el núcleo puede contener varias alternativas que no pueden clasificarse estrictamente. [8]
Marco de referencia
Dejar ser un conjunto (finito o infinito) no vacío de individuos . Los subconjuntos dese llaman coaliciones . Un juego simple ( juego de votación) es una colecciónde coaliciones. (De manera equivalente, es un juego de coalición que asigna 1 o 0 a cada coalición). Suponemos queno está vacío y no contiene un conjunto vacío. Las coaliciones pertenecientes aestán ganando ; los demás están perdiendo . Un juego simplees monótono si y implicar . 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 un jugador con veto. Es finito si hay un conjunto finito (llamado portador ) tal que para todas las coaliciones , tenemos si .
Dejar ser 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 (leer " se prefiere a "), luego . Decimos que una preferenciaes acíclico (no contiene ciclos ) si para cualquier número finito de alternativas, cuando sea , ,…, , tenemos . Tenga en cuenta que las relaciones acíclicas son asimétricas, por lo tanto, preferencias.
Un perfil es una lista de preferencias individuales . Aquí significa que el individuo prefiere alternativa a en el perfil .
Un juego simple con preferencias ordinales es un par que consiste en 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 satisfactorio para todos . El núcleo de es el conjunto de alternativas no dominado por (el conjunto de elementos máximos de con respecto a ):
- si y solo si no hay tal que .
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]
Si (sin jugador con veto); [2] de lo contrario, (mayor que cualquier número cardinal).
es fácil demostrar que si es un juego simple sin un jugador con veto, entonces .
Ejemplos para un número finito de individuos () (véase Austen-Smith y Banks (1999), Lema 3.2 [4] ). Dejar Sea un juego simple, monótono y apropiado.
- Si es fuerte y sin un jugador con veto, entonces .
- Si es el juego de la mayoría (es decir, una coalición está ganando si y solo si está formada por más de la mitad de los individuos), entonces Si ; Si .
- Si es un -regla (es decir, una coalición está ganando si y solo si consta de al menos individuos) con , luego , dónde es el número entero más pequeño mayor o igual que .
Ejemplos para, como mucho, innumerables personas (). Kumabe y Mihara (2008) estudian exhaustivamente las restricciones que diversas propiedades (monotonicidad, propiedad, fuerza, no debilidad y finitud) de los juegos simples imponen sobre 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 apropiado y no fuerte. [6]
Tipo | Juegos finitos | Juegos infinitos |
---|---|---|
1111 | 3 | 3 |
1110 | + ∞ | ninguno |
1101 | ≥3 | ≥3 |
1100 | + ∞ | + ∞ |
1011 | 2 | 2 |
1010 | ninguno | ninguno |
1001 | 2 | 2 |
1000 | ninguno | ninguno |
0111 | 2 | 2 |
0110 | ninguno | ninguno |
0101 | ≥2 | ≥2 |
0100 | + ∞ | + ∞ |
0011 | 2 | 2 |
0010 | ninguno | ninguno |
0001 | 2 | 2 |
0000 | ninguno | ninguno |
Teorema de Nakamura para preferencias acíclicas
Teorema de Nakamura (Nakamura, 1979, Teoremas 2.3 y 2.5 [2] ). Dejarsea 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 .
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íclico para todos los perfiles de preferencias acíclicas si y sólo si para todo finito (Nakamura 1979, Teorema 3.1 [2] ).
- El enunciado del teorema sigue siendo válido si reemplazamos "para todos los perfiles de preferencias acíclicas "por" para todos los perfilesde preferencias transitivas negativas "o por" para todos los perfilesde preferencias linealmente ordenadas (es decir, transitivas y totales) ". [12]
- El teorema se puede extender a -Juegos sencillos. Aquí, la colecciónde coaliciones es un álgebra booleana arbitraria de subconjuntos de, tales como el -álgebra de conjuntos medibles de Lebesgue . A- juego simple es una subcolección de. Los perfiles se restringen adecuadamente a los mensurables: un perfiles medible si para todos, tenemos . [3]
Una variante del teorema de preferencias de Nakamura que puede contener ciclos
En esta sección, descartamos el supuesto habitual de preferencias acíclicas. En cambio, restringimos las preferencias a aquellos que tienen un elemento máximo en una agenda determinada ( 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 de las preferencias puede ser de algún interés desde el punto de vista de la economía del comportamiento ). En consecuencia, es apropiado pensar encomo una agenda aquí. Una alternativaes un elemento máximo con respecto a (es decir, tiene un elemento máximo ) si no hay tal que . Si una preferencia es acíclica sobre el conjunto subyacente de alternativas, entonces tiene un elemento máximo en cada subconjunto finito..
Introducimos un fortalecimiento del núcleo antes de enunciar la variante del teorema de Nakamura. Una alternativa puede estar en el centro incluso si hay una coalición ganadora de individuos que están "insatisfechos" con (es decir, cada prefiere algunos a ). La siguiente solución excluye tal: [3]
- Una alternativa está en el núcleosin descontento mayoritario si no hay coalición ganadora tal que para todos , es no máxima (existe alguna satisfactorio ).
Es fácil demostrar que Depende únicamente del conjunto de elementos máximos de cada individuo y se incluye en la unión de tales conjuntos. Además, para cada perfil, tenemos .
Una variante del teorema de Nakamura (Kumabe y Mihara, 2011, Teorema 2 [3] ). Dejarsea un juego simple. Entonces las siguientes tres declaraciones son equivalentes:
- ;
- el núcleo sin mayor insatisfacción no está vacío para todos los perfiles de preferencias que tienen un elemento máximo;
- el núcleo no está vacío para todos los perfiles de preferencias que tienen un elemento máximo.
Observaciones
- A diferencia del teorema original de Nakamura, ser finito no es una condición necesaria para o no estar vacío para todos los perfiles . Incluso si una agenda tiene infinitas alternativas, hay un elemento en los núcleos para perfiles apropiados, siempre que la desigualdad Está satisfecho.
- El enunciado del teorema sigue siendo válido si reemplazamos "para todos los perfiles de preferencias que tienen un elemento máximo "en las declaraciones 2 y 3 por" para todos los perfiles de preferencias que tienen exactamente un elemento máximo "o" para todos los perfilesde preferencias ordenadas linealmente que tienen un elemento máximo ”(Kumabe y Mihara, 2011, Proposición 1).
- Como el teorema de Nakamura para las preferencias acíclicas, este teorema puede extenderse a -Juegos sencillos. El teorema puede extenderse aún más (1 y 2 son equivalentes; implican 3) a colecciones de ganar sets ampliando la noción del número de Nakamura. [13]
Ver también
Notas
- ^ 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.
- ^ a b c d Nakamura, K. (1979). "Los vetores en un juego sencillo con preferencias ordinales". Revista Internacional de Teoría de Juegos . 8 : 55–61. doi : 10.1007 / BF01763051 .
- ^ a b c d Kumabe, M .; Mihara, HR (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 .
- ^ a b c d Austen-Smith, David; Banks, 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. Enlace externo en
|title=
( ayuda ) - ↑ Elteorema original de Nakamuraes directamente relevante para la clase dereglas 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ónes decisivo si siempre que cada individuo en prefiere a , 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 neutrales (es decir, el etiquetado de las alternativas no importa) y monótonas (si es socialmente preferido a , luego aumentando el soporte para encima conserva esta preferencia social) reglas de agregación (Teorema 3.3), y obtiene un teorema (Teorema 3.4) similar al de Nakamua.
- ^ a b 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 .
- ^ Kirman, A .; Sondermann, D. (1972). "Teorema de Arrow, muchos agentes y dictadores invisibles". Revista de teoría económica . 5 : 267. doi : 10.1016 / 0022-0531 (72) 90106-8 .
- ^ Existen juegos simples, monótonos, adecuados y fuertes sin un jugador con veto que tienen un número infinito de Nakamura. Un ultrafiltro no principal es un ejemplo, que puede usarse para definir una regla de agregación (función de bienestar social) que satisfaga las condiciones de Arrow si hay infinitos individuos. [7] Un serio inconveniente de los ultrafiltros no principales para este propósito es que no son computables algorítmicamente.
- ^ El elemento mínimo del siguiente conjunto existe ya que cada conjunto no vacío de números ordinales tiene un elemento mínimo.
- ^ Consulte una sección del teorema de Rice para conocer la definición de un juego simple computable. En particular, todos los juegos finitos son computables.
- ^ Los posibles números de Nakamura para juegos simples computables se dan en cada entrada, asumiendo que una coalición vacía está perdiendo. Los dieciséis tipos se definen en términos de las cuatro propiedades: monotonicidad, 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 monotónicos (1), propios (1), fuertes (1), débiles (0, porque no no débiles), los finitos tienen un número de Nakamura igual ay los infinitos no existen. La fila correspondiente al tipo 1101 indica que cualquier (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, solo los tipos 1101 y 0101 alcanzan un número de Nakamura mayor que 3.
- ^ 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 demostración es esencialmente la misma). Estos resultados a menudo se expresan en términos depreferencias débiles (por ejemplo, Austen-Smith y Banks, 1999, Teorema 3.2 [4] ). Definir la preferencia débil por . Luego es asimétrico iff Esta completo; es negativamente transitivo iff es transitivo. es total si implica o .
- ^ El marco distingue el álgebrade coaliciones de la colección más grandede los conjuntos de individuos a los que se les puede asignar el estatus de ganador / perdedor. Por ejemplo,es el álgebra de conjuntos recursivos yes el enrejado de conjuntos recursivamente enumerables (Kumabe y Mihara, 2011, Sección 4.2).