Juegos cooperativos: alianzas, asignaciones y núcleo

@[toc]

Juego cooperativo: una simetría del juego no cooperativo, un tipo de juego. Un tipo de juego en el que los participantes pueden unir fuerzas para llegar a un acuerdo vinculante y ejecutable. Los juegos cooperativos enfatizan la racionalidad, la eficiencia, la justicia y la equidad colectivas.

Los dos conceptos más importantes de los juegos cooperativos son alianza y asignación. El ingreso asignado por cada participante de la alianza es exactamente el ingreso total máximo de varias formas de alianza. El ingreso asignado por cada participante de la alianza no es menor que el ingreso obtenido al operar solo.

La forma básica de juego cooperativo es el juego de alianza. Su supuesto implícito es que existe un medio de intercambio (como la moneda) que puede fluir libremente entre los participantes, y que la utilidad de cada participante es lineal con él. . Importante. Estos juegos se denominan juegos de "pago unilateral" o juegos de utilidad transferible (TU).

El resultado de un juego cooperativo debe ser una mejora de Pareto. Los intereses de ambas partes en el juego han aumentado, o al menos los intereses de una de las partes han aumentado sin perjudicar los intereses de la otra parte. El juego cooperativo estudia cómo las personas distribuyen los beneficios obtenidos de la cooperación cuando cooperan, es decir, el problema de la distribución del ingreso. El juego cooperativo adopta un método cooperativo. La razón por la que la cooperación puede mejorar los intereses de ambas partes es que el juego cooperativo puede producir un excedente cooperativo. En cuanto a cómo se distribuye el excedente de cooperación entre los partidos del juego, depende del equilibrio de poder y del diseño del sistema de los partidos del juego. Por lo tanto, la distribución del excedente de cooperación es tanto el resultado de la cooperación como la condición para lograr la cooperación.

La cuestión central de los juegos cooperativos es cómo los participantes forman alianzas y cómo redistribuir los pagos de las alianzas. Analicemos primero el concepto de alianza. Asociada con la alineación está la función característica.

En un juego de n jugadores, el conjunto de participantes está representado por , y cualquier subconjunto S de N se llama coalición. El conjunto vacío y el conjunto completo N también pueden considerarse una alianza, y el conjunto de un solo punto {i} también es una alianza.

Dado un juego de n jugadores, S es una coalición, v(S) se refiere a la utilidad máxima de S en el juego de dos personas entre S y , y se denomina función característica de la coalición S. .

Reglamento. Según la definición, representa el valor máximo de utilidad del participante i cuando juega con todas las demás personas, expresado como .

Utilice (N, v) para representar un juego cooperativo en el que el conjunto de participantes es N y la función característica es v, donde v es una asignación de valor real definida en .

En muchos casos, los pagos que puede recibir una alianza dependen de las acciones realizadas por otros participantes. A veces se interpreta como el pago máximo que la alianza S puede garantizar independientemente de las acciones de la alianza N-S.

La clasificación de las estrategias cooperativas se basa principalmente en las propiedades de las funciones características. A continuación se presentan varios tipos de estrategias cooperativas especiales basadas en las propiedades de la función característica.

Por ejemplo, en un juego de votación, el peso de cada participante es ,

Si , entonces (N, v) se llama juego convexo.

La razón por la que v se llama función característica es porque la naturaleza de este juego cooperativo está básicamente determinada por v. Esto muestra la importancia de v para los juegos cooperativos.

La fórmula anterior muestra que sólo cuando la función característica satisface la superaditividad, es necesario formar una nueva alianza. De lo contrario, si la función característica de un juego cooperativo no satisface la superaditividad, entonces sus miembros no tendrán motivación para formar una alianza, y la alianza ya formada enfrentará la amenaza de disolución.

Lo contrario del Teorema 3 también es correcto, es decir: N es un conjunto, v es una función de valor real no negativo definida en . v satisface: , si , entonces hay un juego cooperativo en N, de modo que v se convierte en la función característica del juego cooperativo.

Para los juegos cooperativos, la función característica v satisface la superaditividad y, naturalmente, tiene:

Según la desigualdad anterior, la función característica v se divide en dos tipos:

Tipo 1 :v se cumple. Es decir, la utilidad de Dalian Alliance es la suma de la utilidad de cada participante. Esto demuestra que a través de la alianza no se crea ningún nuevo excedente de cooperación, la alianza no tiene valor y es imposible mantener esta alianza. Este tipo de contramedida se denomina "contramedida no sustantiva" y no tiene valor de investigación. No es el alcance de este capítulo.

Para contramedidas no sustantivas, existe , si .

Tipo 2: v satisface. Es decir, la utilidad de Dalian Alliance es mayor que la suma de las utilidades de cada participante. Esto muestra que se crea un nuevo excedente de cooperación a través de la alianza, y que la alianza sea significativa si esta alianza puede mantenerse depende de cómo distribuir el excedente de cooperación para mejorar el pago de cada participante. Este tipo de contramedida se denomina contramedida sustantiva y es el alcance de este capítulo.

La llamada distribución es un conjunto de vectores de n dimensiones del juego. La razón por la que es un vector de n dimensiones es que cada participante debe recibir una distribución correspondiente. El vector de asignación de n dimensiones se denomina "solución" del juego.

Para los juegos cooperativos, a cada participante se le asigna un parámetro de valor real para formar un vector n-dimensional que satisface:

Entonces se dice que x es un plan de asignación para la alianza S.

En la definición de distribución, se basa en la racionalidad personal. Los beneficios de la cooperación no pueden ser menores que los beneficios de la no cooperación, reflejando los requisitos de participación de los participantes. Si , entonces es imposible que el participante i se una a la alianza. Se basa en la racionalidad colectiva y la suma de la distribución de cada participante no puede exceder el excedente colectivo v(N). Además, si no se asigna todo v(N), es obvio que X no es un plan de asignación óptimo de Pareto y no será aceptado por los participantes.

En la asignación del Ejemplo 8.1, la asignación obviamente no es una, sino infinita. Las asignaciones infinitas forman un conjunto de asignaciones. Para los juegos reales, siempre hay un número infinito de asignaciones. Por ejemplo, para el juego real (N, v), dado que hay infinitos vectores positivos, satisface. Obviamente, las siguientes son todas las asignaciones, donde E (v) representa la composición de todos los planes de asignación. un juego v colección.

Supongamos que E(v) tiene dos distribuciones x e y, y que S es una unión. Si los planes de asignación xey satisfacen

(i)

(ii)

entonces se dice que el plan de asignación x es superior a y, o se llama plan de asignación. Si y es inferior a x en S, se registra como

Si el plan de asignación x es mejor que y en S, la alianza S rechazará el plan de asignación y, y el plan y no puede implementarse efectivamente. Porque de y a x, el ingreso de cada participante en S ha mejorado y el excedente v(S) creado por S es suficiente para satisfacer su distribución en x.

En la relación superior, las características de la alianza S son:

Aunque el conjunto de asignación factible E (v) tiene asignaciones infinitas, de hecho, muchas asignaciones no se ejecutarán. o no aceptable para los participantes. Obviamente, todos los miembros de la alianza no prefieren planes de asignación inferiores. Por lo tanto, un plan de asignación real y viable debería eliminar los planes de asignación inferiores.

En un juego cooperativo de n personas (N, v), el conjunto de todos los planes de asignación óptimos se denomina núcleo del juego, denotado como C(v). Obviamente lo hay.

Explicación:

1. El núcleo C(v) es un conjunto convexo cerrado en E(v).

2. Si se utiliza el vector X in como distribución, X satisface tanto la racionalidad individual como la racionalidad colectiva.

3. El mayor defecto de utilizar el núcleo como solución al juego es que C(v) puede ser un conjunto vacío.

Las condiciones necesarias y suficientes para el plan de asignación en el núcleo C(v) son:

(i)

(ii)

Prueba: Si, x satisface (i) (ii), entonces x no puede ser superior, es decir,

Prueba por contradicción: Supongamos que existe S, de modo que. Según la definición de Youchao, existe:

Luego está, lo cual es una contradicción.

Si , x no satisface (ii), entonces x debe ser superado, es decir, .

Para, hay una coalición S, y la hay, entonces se define que está uniformemente distribuida en S y uniformemente distribuida en N-S, obteniendo así una nueva distribución de la siguiente manera:

Obviamente se define de esta manera Un vector es una asignación, y la hay.

En los juegos cooperativos, utilizar núcleos en lugar de asignaciones tiene ventajas obvias, concretamente la estabilidad de C(v). Para cada asignación en C(v), cada alianza no tiene objeciones, no hay una mejor asignación y cada asignación puede ejecutarse. Por supuesto, usar C(v) en lugar de E(v) también tiene un defecto fatal, es decir, C(v) puede ser un conjunto vacío y .

Para un juego de alianza de n personas, la condición necesaria y suficiente para el núcleo no vacío C(v) es que la programación lineal (P) tenga una solución.

El significado intuitivo del teorema es obvio. Si la programación lineal (L) tiene una solución, la solución óptima debe pertenecer a C(v) si, entonces, todo vector en C(v) es factible; solución, la programación lineal natural (L) tiene una solución óptima.

Para el programa lineal original (P), escribe su programa dual (DP)

Teorema: Las condiciones necesarias y suficientes para el juego (N, v) son:

Para el vector que satisface, existe

Definición: Supongamos que (N, v) es un juego simple 0-1. Si hay un participante i que satisface, entonces i se llama vetante. .

Teorema: En el juego simple (N,v), la condición necesaria y suficiente es que haya veto en N.

Prueba: Supongamos que j es un veto en N, defina $e_i = (0, 0,…,1,0,…,0), 1 está en la i-ésima posición.

Según el Teorema 8.3.2, es una asignación, y .

Usa la prueba por contradicción. Supongamos que no hay veto, es decir,

Por lo tanto, lo hay, por lo tanto hay una contradicción.

Evaluar la satisfacción de S con Cuanto mayor sea e(S, más satisfechos estarán con

Para una misma x, existen S***, que se pueden expresar como . Por tanto, podemos calcular. La satisfacción de la alianza con x depende del mayor en, por lo que se pueden ordenar de mayor a menor para obtener un vector de:

Entre ellos. La satisfacción de la alianza con x depende del tamaño de Cuanto más pequeña es la alianza, más satisfecha está con x.

Para dos asignaciones diferentes x, y, calcule respectivamente. Si es pequeño, entonces la satisfacción de la alianza con x es mayor que la satisfacción de la alianza con y y, naturalmente, x es mejor que y. Por supuesto, esta comparación de tamaños de vectores es diferente de la comparación de números. Utiliza un método de comparación lexicográfica. El método de comparación del orden lexicográfico es el siguiente:

Para vectores y

Si hay un subíndice a la izquierda, de modo que, se dice que el orden lexicográfico es menor que _, representado por el símbolo.

Con la definición anterior, podemos dar la definición de nucleolo.

Definición: Para un juego cooperativo (N,v), el nucleolo es un conjunto de asignaciones, es decir, tal que cualquiera de ellas es lexicográficamente más pequeña, es decir,

Para un juego cooperativo (N, v), su nucleolo, y contiene solo un elemento x.

Para el juego cooperativo (N, v), si el núcleo es , entonces existe .

Prueba: Utiliza la prueba por contradicción. Supongamos que hay una asignación

Según las propiedades del núcleo, Juqian lo sabe: debe haber una alianza S que satisfaga 2gt;lt;heart), de lo cual se puede ver que *, 》)= *)-

Considere el siguiente juego cooperativo (N, v), N = {1, 2, 3}, y la función característica es la siguiente:

v ({1}) = 4, v({2}) = v({3}) = 0

v({1, 2}) = 5, v({1, 3}) = 7, v({2, 3}) = 6; v({1,2,3}) = 10. Encuentra el núcleo del juego.

Solución: primero busque el núcleo del juego y luego busque el núcleo.

Según las condiciones del núcleo, condiciones necesarias y suficientes:

Resolviendo este conjunto de desigualdades, obtenemos

, entonces comenzamos a . encontrar el núcleo.

Para el núcleo, comience a buscar

Cuando, la fórmula anterior se alcanza en x = 4, entonces hay. Este resultado verificado