ESTADÍSTICA ESPAÑOLA Núms. 112-113, 1986, p^ga. 3i a 43

Juegos matriciales y su aplicación a la teoría de Perron-Frobenius _

por BEG(JNA SUBIZA MARTINEZ Universidad de Al^cante

RESUMEN En este trabajo se presenta una prueba alternativa del Teorema de Perron-Frobenius, a partir de la Teoría de Juegos, utilizando el Teorema de von Neumann que garantiza la existencia de estrategias mixtas en equilibrio para juegos matriciales.

Palabras clave: 1Viatrices no negativas, raiz de Frobenius, Juego matricial, Estrategias mixtas en equilibrio, Valor del juego.

I.

INTRODUCCIQN

Los teoremas de Perron-Frobenius garantizan la existencia de un valor propio ^,* (A) > 0, que acota en módulo el resto de valores propios de la matriz, y tíene asociado un vector propio semipositivo. Este hecho juega un papel importante como instrumento para conseguir condiciones de existencia, unicidad, positividad y estabilidad de las soluciones en rnodelos lineales multisectoriales tanto estáticos como dinámicos. En la literatura aparecen diversas pruebas alternativas a las iniciales de Perron (1907) y Frobenius (1908, * E1 autor agradece las sugerencias dadas a este trabajo por C. Herrero.

32

EST'AUfSTIC'A ESPAN()LA

19()^, 1^ 1?): entre ellas, la rnás conocida entre los economistas es probabiemente la cíe VVielandt (1 ^5O) yue utilila el teorema del punto fijo de Brouwer, y yue se pupularizó por el trahajo de Debreu & Herstein (1 ^53). Las pruebas de ^arlín (1959) y Nikaido (19fi9) son elementales sin utilizar teoremas de punto fija, Murata (197?) ofrece una prueba parecida a la inicial de Frobenius, rnientras que la yue aparece en el libro de Arrow & I--Iahn es muy similar a la de Karlin, En este trabajo se presenta una nueva prueba del Teorema de PerronFrobenius, a partir cie la Teoría de Juegos, utilizando en particular el Teorema de ^on Neu^nann que garantiza la existencia de estrategias mixtas en equilibrio, para juegos bipersonales de suma cero. Simultáneamente a la existencia de la raír de F robenius, se obtienen, a lo largo de la prueba, las ac;otaciones de F^isher (1965) que sitúan este valor propio entre el máximo y el mínimo de las sumas de columnas (o filas} cíe la matriz. En la sección II, se presenta un resumen de los resultados de Juegos Matriciales, utiliza.dos a lo largo del trabajo; en la sección III se ofrece, como resultado principal, la prueba del teorema de Perron-Frobenius para matrices indescomponibles, y como corolarios el resultado análogo para matrices descomponibles y el teorema de acotación de Fisher. Algunas observaciones finales, en la sección IV, cierran el trabajo. La notación utilizada a lo largo del trabajo es la usual. Señalemos, no obstan te, q ue en la comparación de vectores: .^ ? y significa .^; > _y; i = l , 2, ..., n. _^ > ^^ significa .ti > y con ^ ^ ^^. x> y^ significa x; > y; i= 1, 2, ..., rz.

II.

JUEGQS MATRIC'IALES

Un juego bipersonal queda descrito por una terna (S, T; M), donde S y T son los conjuntos cie estrategias puras para 1os jugadores I y II respectivamente, y n: S x T-^ R2 ^(s, t) =(^ 1( s, t), T2{s, t))

es la función de resultados del juego.

s E S, t E T

JUEGOS MATRICIALES Y SU APLICACIÓN A LA TEORÍA DE PERRON-FROBENIUS

^3

Se dice que el juego es de suma cerca, cuando

^I(s, t}+n2(s, t}=^

s E S, r^ T

Si además el número de estrategias para cada jugador es finito, estos juegos se denominan matriciales, ya que es posible representarlos mediante una matriz que proporciona los resultados para el jugador I. De esta forma si S = '^S1,

S2, ..., SnÍ

T`^ ^tl,

t2, ..., tm^^

la matriz de pagos al j ugador I es A =(u;^)n x rn,

donde u^.i ^ ^1 (S^^ t^).

La matriz de resultados para el jugador II vendrá, obviamente, representada por -A. Def nición

Una situación (sk, t^) E S x T es un equilibrio de Nash si ^ ^(sk^ t^) ^ ^ ^ (s^ ^ t^)

i= 1, 2, ..., n

^z(sk, tr) ^^2(Sk^ t^)

j= 1, 2, ..., m

es decir, ningún jugador puede obtener un mejor resultado cambiando de estrategia unilateralmente. En los juegos matriciales (sk, t^) es un equilibrio de Nash si, y sólo si, uk^^uk^^a^^

i= 1, 2, ..., n; j

, ..., m

o, lo que es lo rnismo, ak^ es un punto de silla de la matriz A(valir mínimo de su fila y máximo de su columna). No todas las matrices poseen punto de silla y, por tanto, no todos los juegos matriciales tienen equilibrio de Nash. Así pues, es necesario ampliar el concepto de estrategia para los jugadores.

E^rADiSTICA ESPAIriol.A

l^^^nic•ic'^n Una estrategia mixta para el jugador I es un vector de conjunto

^ ^ x^= 1 ^=^ donde cada coordenada x; indica la probabilidad con que el primer jugador utiliza la estrate,gia pura s^. De forma análoga y con la misma interpretación, se define una estrategia mixta para el segundo jugador como un vector de m

^ y^ _ i=1

}

La función de resultados se extenderá, para estas nuevas estrategias (x, y) E^„ x E,„, en términos de esperanza matemática, siendo el pago esperado para el jugador I ^e^(x, y)-x A y'. E1 conjunto de situaciones posibles S x T queda, de esta forma, ampliado a^(S) x C(T), donde C(S) y C(T) son las envolturas convexas de S y T, generalizándose el concepto de equilibrio para este conjunto. Con esta generalización se puede garantizar la existencia de situaciones en equilibrio. Teoremu (Von Newmann, 1928) Todo juega bipersonal finito de suma cero posee estrategias mixtas en equilibrio. Nota Si (x*, y* ) y (^c, y) son dos situaciones en equilíbrio para el juego dado por la matriz A, se curnple x*Ay*'=zAy' lo que supone que el pago esperado, cuando se ^ uegan situaciones de equilibrio, es constante.

JUEGOS MATRIC[ALES Y SU APLICACIÓN A LA TEORÍA DE PERRUN-FROBEN[US

3S

Definición Dado un juego bipersonal de suma cero, definido por la matriz A, si

(x*, y*) es un par de estrategias en equilibrio, al número v(A)=x* A y*'

se le denomina valor del j uego.

Propiedades Si (x*, y* ) es un equilibrio del juego que describe la matriz A, se verihca: (1)

x* A? v(A) e

x* E^,,,

(2)

A y*' ^ v(A) e'

y* E E„,

donde e es el vector con todas sus coordenadas iguales a la unidad. Además, v(A) es el valor máximo que curnple (1), para un vector x E^n, y el mínimo que cumple (2}, para y E^,„ .

Proposición (Owen) Sea M„xm (R) el espacio de matrices reales de orden nxm, entonces: i)

La función u: M,,,rm(IZ) --^ R

que a cada matriz le hace corresponder el valor del juego que representa, es contínua. Veamos, por último, como la existencia, en algunos casos, de estrategias que hacen que el resultado del juego sea independiente del comportamiento del oponente, puede dar un método sencillo para determinar las estrategias en equilibrio y el valor del juego.

Definición (Shubik)

En un juego matricial, de matriz A, una estrategia mixta x*, es un igualador para el jugador I si x* A= k e, k E R constante Análogamente se de^ne el igualador para el segundo jugador.

ESTA©ISTICA ESPAÑOLA

f'rotnc?s i E^ i ^^n

Si un juego posee igualadores x*, ti^* para ambas jugadores, x*Á-k,e Ay*,lk^e, entonces: i)

(x*, y*) son estrategias en equilibrio. kl-k2=v(A).

TEOREMA DE PERI^OI'^I-FROBENIUS

III.

Tearemc^ ( Perron-Frobenius, 1907-1912) Sea A=( a^; ) una rnatriz cuadrada de orden n semipositiva e indecomponible*. En estas condiciones. i)

A posee un valor propio ^,* (A), positivo.

ii) Asociado a^,* (A), existe un vector propio x*, con todas sus componentes positivas. iii)

^,* (A) crece cuando alguna componente de A aumenta.

iv) Si ^, es otro valor propio de A, distinto de ^,* (A), no existe ningún vector propio semipositivo asociado a él. v)

E1 módulo de los restantes valores prapios de A, no excede a^,* (A). ^,* (A) es un valor propio simple.

* Una matriz A es descomponible si, por medio de permutaciones simultáneas de filas y columnas, se puede expresar en la forma f4>>

AiZ

^

A22

A=

donde A11, A22, son matrices cuadradas, no necesariamente del mismo orden. Una matriz es indescomponible, cuando no es descomp©nible.

JUEGOS MATRICIALES Y SU APLICACIÓN A LA TEORÍA DE PERRON-I"ROBENIUS

37

Demostración:

i)

Consideremos las matrices B( í^ )-- A-- ^.1,

i^^ E R

como matrices de un juego bipersonal de surna cero, y sea v(^,)^_= v(B(^)) su valor; v es así función continua de i^^. vearnos que existe ^,*, para el cual el juego definido por la matriz B{^,*) tiene valor cero. n

Dado ^,1, tal que ^, I< min ^ ui^ , el vector x--= (1 /n) e E^„ , con lo cual, f ^_^ n

A--^^ll)=(1/n)

> 0;

^ a^;!%^^ i=i

l zn

por tanto v (í^ 1) > (^. n

Por otro lado, si ^,2 > máx ^ ai^ , para todo _x E^,,, la k-ésima coorde.1

i- 1

nada del vector x(A -- ^.21), siendo x k= máx x; , es n

n

^ xi Sik - xk /^,2 C ^

i-1

(xi ^ ^k)aik ^ Os

i-1

por 1 o q ue v ( í^ 2)< o. De la continuidad de v, se deduce que existe un ^,*, cornprendido entre n

h

mín ^ ai^ y máx ^ ui^ , tal que L^ (^,*) = 0. Además, como A es indescom.1

i- 1

^

i- 1

n

ponible,

mín ^ ut^ > 0, con lo cual ^,* es positivo. .%

i=1

Para el juego que la matriz B(^,*) = B defÍne, el teorema de ^on Neumann asegura la existencia de estrategias mixtas en equilibrio, Tendremos, por tanto, x*, y* tales que x* B y*' =0

38

ESTADfSTiCA ESPAÑOLA

B ^., * ^ ^ x* B > 0 Si x* B^ 0, mediante las permutaciones de filas y columnas en x*, y*, B necesarias obtendriamos

* B 11 .B 12 = (0, Z,Í Con Z> o B x 8=(x^`, x^) B 22

21

_., ^` o=X*By*^Z ) y^ i(o^ ^ ^y Y

de donde y^ = o. Suponienda y^` > 0 B11

B12

v^`

B21

B22

^

B11 yl

co

- B21 y1

como B21 = A21 >^, se obtiene que A21 = o, en contra de la indescomponibilidad de A. f7^e este modo x* B= o, con lo que ^,* es valor propio de A, siendo x* un vector propio por la izquierda asociado a él. De forma análoga se prueba que y* es vector propio por la derecha asociado a ^,*. ii} Veamos que x* > 0. Si posee alguna componente nula, efectuando una reordenación conveniente en x*, y la correspondiente permutación de filas y columnas en B, podemos escribir x* B-(o, x)

B11

B12

B21

B22

=(o, 0) con x>0

luego x B21 = x A21 =^, que contradice la indescomponibilidad de A. Por tanto, el vector x* es estrictamente positivo. 111) Sea M otra matriz cuadrada del mismo orden que A tal que M> A> 0. Existen, por la condición i), ^,* (A) y ^* (M) positivos tales que los juegos que rep^resentan las matrices A-^.* (A) I y M-^* (M)1 tienen valor cero. Si í^* (A) >^,* (M), M-^.* (M)1 > A-^.* (A) I y tomando x* la estrategia óptima para el primer j ugador, de A-- ^,* (A)1, se deduce que x* (M - ^,* ( M) I ) > x* (A - ^.* (A) I ) = 0,

JUEGOS MATRIC[ALES Y SU APLICACIbN A LA TE©RÍA DE PERRON-FROBENIUS

39

siendo x* estrategia en equilibrio del primer jugador, para el juego M - ^,* (M)1. can lo cual .t*(M-^.*(M) I)=x*(A-^.*(A) 1)=0.

Esto implica que 0 ^ x* (M -- A) = (^.* ( M) - ^.* (A)) x*, lo cual contradice que ^,* (M) ^.^* (A). Por tanta, í^* (A) 0. iv) Sea ^^ valor propio de A con vectores propias a izquierda y derecha semipositivos, x* e y* respectivamente, que pueden tomarse en ^„ x* (A - ^,I) _ (A -- ^,1) y* = 4,

De este modo, x* e y* serian igualadares uno para cada jugador, del juego que representa la matriz A-- ^.1 que tendría por tanto valor cero. Veamos que los juegos de la forma A-- ^.I, donde A es indescomponible, tienen valor cero para un único ^, y se tendrá probado iv). Supongamos ^, > µ tales que B = A-^,1 y C= A- µI representan juegos con valor cero. Sea x estrategia óptima del primer jugador en el _juego representado por B, entonces xB=O, x>0

xC=xA --µx=(^,--µ) x>0 en contra de que el valor del juego dado por C sea cero.

Las condiciones v) y vi) se obtienen por cálculo matricial y pueden encontrarse en [6], capítulo I. Una versión más débil de este teoremá, para matrices descornponibles, se deduce como consecuencia del resultado anterior. Corolario 1 Sea A una matriz cuadrada de orden n semipositiva. Entonces i)

A posee un valor propio ^,* (A) > 0.

40

ESTAD^STICA ESPA[VOi_A

ii) iii ^ iv)

Asociado a^.*(A), existe un vector propio .x* >(). Si A> B> 0, entonces ^*( A 3>,^.* ( B). ^^* (A) >^^.^, siendo^ ^t otro valor propio de A.

Demostraeión: Si la matriz A es descomponible, A=

AI1

A12

0

A22

podemos definir para cualquier t, > 0 A f^ -

Aii

A^2

T(^^

A22

donde T(F) es una matriz con todos sus elementos iguales a E. Para esta nueva matriz A^> 0, indescomponible, se deduce del teorema anterior la existencia de ^,^> 0 y x; vector de ^„ estrictamente positivo, tales que xf^(A -^.^^1)=0. Construyendo una sucesión de números positivos {Ek} con limite cero, obtendríamos las sucesiones: ^ AEk} que converge a la matriz A, {^.Ek} con ^.^k > 0 para cualquier k, ^ JC^ k} d onde X^'k E^„ .

Estas dos últimas sucesiones están acotadas y tienen, por tanto, subsucesiones convergentes a^,* > 0 y x* > 0, respectivamente. De este modo, como x* {A -^.* I)=^, ^.* será valor propio de A y x* un vector propio asociado a él. Las restantes condiciones se prueban de forma análoga a como se ha hecho en el teorema anterior. Es interesante señalar que una acotación de la raíz de Frobenius, ^,*{A), se deduce de f©rma inmediata en esta prueba del Teorema de Perron-Frobenius.

JUEGOS MATRICIALES Y sU APLICACICSN A LA TEORfA DE PERRON-FRQBENIUS

41

^orolurir^ 2 (Fisher, 1965) Sea A=(u^;) una matriz semipositiva. Se verihca la siguiente acotación n

mín .^

n

^ ui^ ^ ^,* (A) < máx ^ i= 1

.1

U^ j.

i= 1

Este resultado, en el caso de matrices indescomponibles, se obtiene simultáneamente a la existencia de ^,* (A) en la condici©n i) del teorerna. En el caso de matrices descomponibles, esta acotación resulta evidente observando que ^,*(A) es el límite de la sucesión {^,^^. Una acotación semejante, para suma de filas, se deduce razonando con las estrategias del segundo jugador. IV.

CJBSERVACI(^NES FINALES

En este trabajo se ha presentado un nuevo método para estudiar las propiedades de las matrices semipositivas (en particular la existencia de la denominada raíz de Frobenius) utilizando resultados de Teoría de Juegos y, por medio de éstós Programación lineal. Inversamente, la Teoría de Matrices 5emipositivas puede aplicarse a la Teoria de Juegos. r

Por ejemplo, la propiedad ergódica (1) permite hallar las estrategias mixtas en equilibrio de determinados j uegos mediante un proceso iterativo. En efecto, dado un juego matricial, cuya matriz es de la forma B=A-^.*(A)I, A>0

(2)

entonces i)

v(B)=0 , * Akx x =1^m ,^ ^^A x^^

y

* = lím

x E ^n

XAk

IIx^lkll A kx

(1) Dada A> 0, x^ 0, ^^x^^ = 1, se cumple que la sucesión xk =----- -- - converge al vector prollAk-x^l pio asociado a la raíz de Frobenius de A. La norma yue se utiliza es x=^ (x,^. (2) También se podría aplicar a matrices de la forma Bk=(A-^*(A)1)+k

I

1

1

1

k^R n.xn

42

ESTADÍSTiCA ESPAÑOLA

son estrategias mixtas en eyuilibrio del juega definido por B. Queda así abierta una vía, en dos sentidos de relación entre la Teoría de Juegos y la Ter^ria de Matrices Semipositivas.

REFERENCIAS [1]

ARR©w, IC. & HAHN, F. General Competitive Anatysis. Holden Day, San Francisco. 1971.

[^]

DEBREU, G. & HERSTEIN, I. N. «Non negative Square Matrices». Ecvnometricu 21 (597607 ). 195 3.

[3]

FROBENIUS, G.