TEORÍA DE JUEGOS

La Teoría de Juegos consiste en la elaboración de recomendaciones sobre la forma razonable de las acciones de cada uno de los contrincantes en el curso de una situación de conflicto; es prácticamente una teoría matemática de las situaciones en conflicto. En un conflicto de juego los dos oponentes son llamados jugadores y cada uno de ellos tendrá un numero finito o infinito de estrategias; a cada estrategia se encuentra asociada una recompensa que un jugador paga a otro.

Estos juegos se conocen como juegos de suma cero entre dos personas debido a que la ganancia de un jugador es igual a la pérdida del otro y los intereses de los jugadores son completamente opuestos, por lo tanto, es suficiente con resumir el juego en términos del pago a solo uno de los dos jugadores, es decir, al designar dos jugadores A y B con estrategias m y n, respectivamente, el juego se representa mediante una matriz de pagos al jugador A, de la siguiente manera:

	B1	B2	B3	…	Bn
A1	a11	a12	a13	…	a1n
A2	a21	a22	a23	…	a2n
.	.	.	.	.	.
.	.	.	.	.	.
.	.	.	.	.	.
Am	am1	am2	am3	…	amn

La anterior representación indica que si A usa la estrategia i y B la estrategia j, el pago a A es aij y el pago a B es - aij.

En la teoría de juegos se denomina jugada a la elección de una de las estrategia dadas; estas jugadas pueden ser personales, cuando la elección de la estrategia se hace conscientemente, o al azar, cuando la elección de la estrategia es realizada por un mecanismo de elección casual y no por el jugador. Para que el juego esté matemáticamente definido, se debe indicar para cada estrategia la distribución de probabilidad.

Su objetivo principal es elaborar recomendaciones para elegir la estrategia óptima, definida como la estrategia que garantiza al jugador la ganancia media máxima posible o la pérdida media máxima posible a medida que el juego se repite reiteradamente, de cada uno de los jugadores

SOLUCIÓN OPTIMA DE JUEGOS DE SUMA CERO ENTRE DOS PERSONAS

Debido a que los juegos se concentran en conflictos de interés, la solución optima del problema elige una o más estrategias para cada jugador de tal manera que cualquier cambio en las estrategias elegidas no mejore el pago a cualquiera de los dos jugadores.

Estas soluciones pueden realizarse de dos formas: estrategia pura, con una sola estrategia, o estrategia mixta, con varias estrategias que se mezclan de acuerdo con probabilidades predeterminadas.

Ejemplo 1

Dos compañías A y B venden dos marcas de antigripales, La compañía A se anuncia por radio (A1), televisión (A2) y periódicos (A3). La compañía B, además de utilizar radio (B1), televisión (B2) y periódicos (B3), también manda por correo folletos (B4). Dependiendo del ingenio y la intensidad de la campaña de publicidad, cada compañía puede capturar una porción del mercado de la otra. La siguiente matriz resume el porcentaje del mercado capturado o perdido por la compañía A:

	B1		B2	B3		B4	Mínimo de la fila
A1	8		-2	9		-3	-3
A2	6		5	6		8	5	Maximin
A3	-2		4	-9		5	-9
Máximo de la columna		8		5	9		8
		Minimax

La solución del juego se basa en asegurar lo mejor de lo peor para cada jugador. Si la compañía A selecciona la estrategia A1, entonces sin importar lo que haga B, lo peor que le puede suceder es que pierda 3% de la participación del mercado a favor de B. Esto se encuentra representado por el valor mínimo de las entradas de la fila 1. De manera similar, el peor resultado de la estrategia A2 es que capture 5% del mercado de B y el peor resultado de la estrategia A3 es que pierda 9% de la participación del mercado a favor de B. Los anteriores resultados se separan en la columna “mínimo de fila” y, para lograr lo mejor de lo peor, la compañía A escoge la estrategia A2 debido a que a esta corresponde el mayor valor de la columna “mínimo de fila” denominado “Maximin”.

Considerando ahora la estrategia de B se requiere escoger el valor mínimo “Minimax” de la columna “Máximo de la columna” para lograr lo mejor de lo peor de B debido a que la matriz de pago esta dada para A. Tenemos así que la estrategia a escoger es B2.

La solución optima del juego debe seleccionar las estrategias A2 y B2, es decir, ambas compañías deben anunciarse en televisión Esto indica que el resultado estará a favor de A debido a que su participación en el mercado aumentará un 5%, por lo tanto, decimos que el valor del juego es 5% y que A y B usan una solución de punto de equilibrio. Esta solución garantiza que ninguna compañía está tentada a seleccionar otra estrategia debido a que esto ocasionaría perdidas en la participación del mercado, es decir, en caso de que B decida moverse a cualquiera de las otras estrategias, A puede escoger quedarse con la elegida ocasionando así una perdida de participación de mercado para B del 6% u 8% según la estrategia elegida por B, de igual manera, si A decide cambiar a la estrategia A3 , B puede moverse a B3 ocasionando así un incremento del 9% en la participación del mercado a favor de B.

Ejemplo 2

Dos jugadores A y B participan en un juego de lanzamiento al aire de una moneda. Cada jugador, desconocido para el otro, elige cara (C) o cruz (Z). Ambos jugadores revelarán sus elecciones de forma simultánea. Si concuerdan (CC o ZZ), el jugador A recibe 1 dólar de B, de otra forma, A paga 1 dólar a B.

La siguiente matriz de pagos para el jugador A da los valores mínimo de la fila y máximo de la columna que corresponden a las estrategias de A y B, respectivamente:

	Bc	Bz	Mínimo de la fila
Ac	1	-1	-1
Az	-1	1	-1
Máximo de la columna		1	1

Los valores máximo y mínimo del juego son -1 dólar y 1 dólar, respectivamente. Debido a que los valores no son iguales, el juego no tiene una solución de estrategia pura ya que si A utiliza una estrategia que ocasione perdidas a B, B puede moverse de tal forma que no le ocasione perdidas lo que indica que los jugadores pueden cambiar de estrategias según conveniencia y por esto es que una estrategia pura no es aceptable. Tenemos entonces que ambos jugadores deben usar mezclas aleatorias apropiadas de sus respectivas estrategias.

En este caso, el valor óptimo del juego se dará en algún lugar entre los valores maximin y minimax , así:

Valor maximin (más bajo) " valor del juego " valor minimax (más alto)

Así, el valor del juego debe estar entre -1 dólar y 1 dólar.

SOLUCIÓN DE JUEGOS DE ESTRATEGIAS MIXTAS

Al emplear estrategias mixtas se puede obtener para cada juego finito una solución o un par de estrategias que al ser empleadas por los dos jugadores originarán una ganancia igual al valor del juego y en caso de que un jugador decida cambiar su estrategia la ganancia sólo cambiará desfavorablemente para este.

Los juegos de estrategias mixtas se pueden resolver de forma gráfica o mediante programación lineal. La solución gráfica es conveniente para juegos en los que al menos un jugador tiene exactamente dos estrategias puras.

La ganancia obtenida como fruto de la solución se llama valor del juego, denotado como , el cual siempre se encuentra entre los valores mínimo y máximo del juego.

SOLUCIÓN GRÁFICA DE JUEGOS

Comenzamos por el caso en que el jugador A tiene dos estrategias, (2xn)

		y1	y2	…	yn
		B1	B2	…	Bn
x1 :	A1	a11	a12	…	a1n
1 - x1 :	A2	a21	a22	…	a2n

En este juego el jugador A mezcla las estrategias A1 y A2 con sus respectivas probabilidades x1 y 1 - x1 con 0 " x1 " 1 y el jugador B mezcla las estrategias B1 a Bn con las probabilidades y1, y2, …, y yn donde yj " 0 para j = 1,2, …, n y y1+y2 + … + yn = 1. Para este caso el pago esperado de A que corresponde a la j-ésima estrategia pura de B esta dada por:

(a1j - a2j ) x1 ± a2j , j = 1,2, …, n (1)

El jugador A busca entonces determinar el valor de x1 que maximice los pagos mínimos esperados, es decir:

Max min {(a1j - a2j ) x1 ± a2j }

x1 j

Ejemplo 3.

Considere el siguiente juego de 2 x 4. El pago es para el jugador A.

	B1	B2	B3	Bn
A1	2	2	3	-1
A2	4	3	2	6

Este juego no posee una solución de estrategia pura, por lo tanto, las estrategias deben mezclarse. Utilizando la fórmula (1) calculamos los pagos esperados de A correspondientes a las estrategias puras de B, así:

Estrategia pura de B	Pago esperado de A
1	-2x1 + 4
2	- x1 + 3
3	x1 + 2
4	-7x1 + 6

Utilizando las ecuaciones obtenidas para los pagos esperados de A realizamos las gráficas correspondientes, mostradas a continuación:

Esta gráfica presenta las cuatro líneas rectas asociadas con las estrategias puras de B. Para determinar lo mejor de lo peor , la envolvente inferior representa el pago esperado mínimo, es decir lo peor, para A sin tener en cuenta lo que haga B.

El máximo, o sea lo mejor, de la envolvente inferior corresponde al punto de la solución maximin en x*1 = 0.5, que es el punto intersección entre las rectas 3 y 4. La solución óptima del jugador A pide mezclar las estrategias A1 y A2 con probabilidades 0.5 y 0.5, respectivamente. El valor del juego se determina sustituyendo x1 = 0.5 en cualquiera de las ecuaciones 3 y 4, así:

La mezcla óptima del jugador B se determina mediante las dos estrategias que definen la envolvente inferior de la gráfica, por lo tanto B puede mezclar las estrategias B3 y B4 , en cuyo caso y1 = y2 = 0 y y4 = 1 - y3 . Tenemos entonces que los pagos de B correspondientes a las estrategias puras de A están dados como:

Estrategias puras de A	Pago esperado de B
1	4y3 - 1
2	- 4y3 + 6

La solución lo mejor de lo peor para B es el punto mínimo sobre la envolvente superior de las dos líneas dadas. Este proceso es equivalente a resolver la ecuación

La solución de y3 = , que da el valor del juego como:

La solución del juego requiere que el jugador A mezcle A1 y A2 con probabilidades iguales y para el jugador B mezclar B1 y B2 con probabilidades y .

SOLUCIÓN DE JUEGOS CON PROGRAMACIÓN LINEAL

La teoría de juegos tiene una fuerte relación con la programación lineal debido a que un juego de suma cero entre dos personas se puede expresar como un programa lineal y viceversa. Incluso, J. von Neuman, padre de la teoría de juegos, reconoció la relación entre esta teoría y la programación y recalcó el concepto de dualidad en la programación lineal.

Tenemos entonces que las probabilidades óptimas del jugador A xi , con i = 1, 2,…, m se puede determinar resolviendo el siguiente problema máximin:

Para transformar el problema en un programa lineal, sea

La ecuación implica que

El problema del jugador A se puede escribir como:

Maximice z = v

Sujeta a:

El valor del juego no tiene restricciones debido a que su signo puede cambiar dependiendo del resultado de este.

Las estrategias óptimas de B , y1 , y2 , .. , y yn se determinan resolviendo el problema

Mediante un procedimiento al requerido con el problema de A, resolvemos el de B obteniendo que:

Minimice w = v

Sujeta a:

Los dos problemas optimizan la misma variable v, el valor del juego, debido a que el problema B es el dual del problema A, lo que significa que la solución optima de un problema automáticamente de la solución del otro.

Ejemplo 4.

Resuelva el siguiente juego con programación lineal:

	B1	B2	B3	Mínimo de la fila
A1	3	-1	-3	-3
A2	-2	4	-1	-2
A3	-5	-6	2	-6
Máximo de la columna		3	4	2

Notamos que el valor del juego se encuentra entre los valores -2 y 2.

Tenemos entonces que el programa lineal del jugador A es:

Maximice z = v

Sujeta a:

La solución óptima es:

La solución dual asociada es:

La razón por la cual los resultados de las probabilidades de B son negativos es debido a que el problema de A es una maximización con restricciones ", una condición que requiere que las variables duales asociadas sean negativas.

El programa lineal de B esta dado por:

Minimice z = v

Sujeta a:

La solución óptima es:

La solución dual asociada es:

BIBLIOGRAFÍA

• TAHA, Handy A., Investigación de Operaciones, Una Introducción, Sexta Edición, Prentice Hall, México, 1998

• VÉNTSEL, E.S, Elementos de la teoría de los juegos, Editorial MIR, Moscú, 1977