FACULTAD DE MATEM´
ATICAS
DEPARTAMENTO DE AN´
ALISIS MATEM´
ATICO
T abajo Fin de G ado
OPTIMIZACI ´
ON LINEAL APLICADA A
TEOR´
IA DE JUEGOS
Alejand o Se ano Galla do
Di igido po :
Vic o ia Ma ´ın M´a quez
Se illa, Junio 2017.
´
Indice gene al
B e e in oducci´on his ´o ica 1
1. P elimina es 9
1.1. Concep os b´asicos de la Teo ´ıa de Juegos . . . . . . . . . . . . 9
1.2. Concep os b´asicos de la P og amaci´on Lineal . . . . . . . . . . 11
2. Juegos no coope a i os 15
2.1. In oducci´on a los Juegos en Fo ma Es a ´egica . . . . . . . . 15
2.2. El Equilib io de Nash en Juegos en Fo ma Es a ´egica . . . . . 18
2.3. Juegos Bipe sonales de Suma Nula . . . . . . . . . . . . . . . 21
2.4. Es a egias Mix as en Juegos Fini os . . . . . . . . . . . . . . 26
2.5. Juegos Ma iciales y Algo i mos . . . . . . . . . . . . . . . . . 30
2.6. Juegos Ma iciales y P og amaci´on Lineal . . . . . . . . . . . 40
3. Juegos Coope a i os 47
3.1. In oducci´on............................ 47
3.2. El Co e y Concep os Relacionados . . . . . . . . . . . . . . . . 49
3.3. Juegos de p oducci´on lineal . . . . . . . . . . . . . . . . . . . 54
3.4. ElNucleolus............................ 60
Bibliog a ´ıa 68
i
ii Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
ABSTRACT
In he ollowing TFG we deal wi h he Game Theo y and wi h he ap-
plica ion ha he Linea P og amming has on i . We s a de ining some
key concep s ha will se e us as a base. Wi hin he Game Theo y he e
a e manly wo heo ies: he coope a i e one and he non-coope a i e one.
We conside ha he non-coope a i e app oach is he mos app op ia e o
analyse ou p oblem, ha is: e e y single playe migh ind i s own s a egies
conside ing ha he o he s will use hei bes s a egies as well. To his e ec ,
we will use he Linea P og amming o ob ain he mos accu a e solu ion.
On he o he side, he coope a i e app oach deals wi h he assump ion ha
he hypo he ical playe s a e going o coope a e and, o his espec , hey will
ac acco ding o he mos sui able social way, ocusing on how he playe s
should di ide ou he bene i s o i s coope a ion. Due o hose easons, we
will use he Co e and he Nucleolus and e ise he Linea P oduc ion Games,
in which he Linea P og amming u nishes on how o sp ead he bene i s
wi hin ex ensi e coali ions.
iii

i Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
B e e in oducci´on his ´o ica
La P og amaci´on Lineal es udia el p oblema de minimiza o maximiza
una unci´on lineal en p esencia de desigualdades lineales. Desde que Geo ge
B. Dan zig desa oll´o el m´e odo simplex en 1947, la p og amaci´on lineal
se ha u ilizado ex ensamen e en el ´a ea mili a , indus ial, gube namen al
y de plani icaci´on u bana, en e o as. Su popula idad se puede a ibui a
muchos ac o es, incluyendo su po encial pa a modela p oblemas g andes y
complejos, y la habilidad de los usua ios pa a esol e p oblemas a g an escala
en un in e alo de iempo azonable median e el uso del m´e odo simplex y de
compu ado as. A pa i de la Segunda Gue a Mundial se hizo e iden e que
e a esencial la plani icaci´on y coo dinaci´on en e a ios p oyec os, as´ı como
el uso e icaz de los ecu sos disponibles. En junio de 1947 se inici´o un abajo
in ensi o del equipo de la Fue za A´e ea de los EE.UU. conocido como SCOOP
(Scien i ic Compu a ion o Op imum P og ams). Como esul ado, Geo ge
B. Dan zig desa oll´o el m´e odo simplex a inales del e ano de 1947. El
in e ´es de la p og amaci´on lineal se di undi´o ´apidamen e en e economis as,
ma em´a icos, es ad´ıs icos e ins i uciones gube namen ales.
Desde la c eaci´on del m´e odo simplex mucha gen e ha con ibuido al c e-
cimien o de la p og amaci´on lineal, ya sea desa ollando su eo ´ıa ma em´a i-
ca, dise˜nando c´odigos y m´e odos compu acionales e icien es, expe imen ando
nue as aplicaciones, y ambi´en u ilizando la p og amaci´on lineal como una
he amien a auxilia pa a esol e p oblemas m´as complejos como son p o-
1
2 Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
g amas en e os, p og amas disc e os, p og amas no lineales, p oblemas com-
bina o ios, p oblemas de p og amaci´on es oc´as ica y p oblemas de con ol
´op imo.
La Teo ´ıa de Juegos como al ue c eada po el ma em´a ico h´unga o
John on Neumann (1903-1957) y po Oska Mo gens e n (1902-1976) en
1944 g acias a la publicaci´on de su lib o ”The Theo y o Games Beha io ”.
An e io men e los economis as Cou no y Edgewo h hab´ıan an icipado ya
cie as ideas, a las que se suma on o as pos e io es de los ma em´a icos Bo el
y Ze melo que en uno de sus abajos (1913) mues a que juegos como el
ajed ez son esolubles. Sin emba go, no ue has a la apa ici´on del lib o de
on Neumann y Mo gens e n cuando se comp endi´o la impo ancia de la
Teo ´ıa de Juegos pa a es udia las elaciones humanas.
Von Neumann y Mo gens e n in es iga on dos plan eamien os dis in os
de la Teo ´ıa de Juegos. El p ime o de ellos es el plan eamien o es a ´egico
o no coope a i o. Es e plan eamien o equie e especi ica de alladamen e lo
que los jugado es pueden y no pueden hace du an e el juego, y despu´es cada
jugado busca ´a una es a egia ´op ima.
En la segunda pa e de su lib o, on Neumann y Mo gens e n desa olla-
on el plan eamien o coalicional o coope a i o, en el que busca on desc ibi
la conduc a ´op ima en juegos con muchos jugado es. Pues o que ´es e es un
p oblema mucho m´as di ´ıcil, sus esul ados ue an mucho menos p ecisos que
los alcanzados pa a el caso de suma ce o y dos jugado es, ambos juegos no
coope a i os.
En los a˜nos 50 hubo un desa ollo impo an e de es as ideas en P ince on,
con Luce and Rai a (1957), di undiendo los esul ados en su lib o in oduc-
o io, Kuhn (1953) que pe mi i´o es ablece una o ma de a aca los juegos
coope a i os, y po in Nash (1950) quien de ini´o el equilib io que lle a su
nomb e, lo que pe mi i´o ex ende la Teo ´ıa de Juegos no-coope a i os m´as
BREVE INTRODUCCI ´
ON HIST ´
ORICA 3
gene ales que los de suma ce o. Du an e esa ´epoca, el Depa amen o de De-
ensa de los EE.UU. ue el que inanci´o las in es igaciones en el ema, debido
a que la mayo pa e de las aplicaciones de los juegos de ipo suma-ce o se
concen aban en emas de es a egia mili a .
John Fo bes Nash (1928-2015) es el nomb e m´as des acado elacionado
con la Teo ´ıa de Juegos. A los 21 a˜nos esc ibi´o una esina de menos de ein a
p´aginas en la que expuso po p ime a ez su soluci´on pa a juegos es a ´egicos
no coope a i os, lo que desde en onces se llam´o “el equilib io de Nash”, que
u o un inmedia o econocimien o en e odos los especialis as.
El pun o de equilib io de Nash es una si uaci´on en la que ninguno de
los jugado es sien e la en aci´on de cambia de es a egia ya que cualquie
cambio implica ´ıa una disminuci´on en sus pagos. Von Neumann y Oska
Mo gens e n hab´ıan ya o ecido una soluci´on simila pe o s´olo pa a los juegos
de suma ce o. Pa a la soluci´on o mal del p oblema, Nash u iliz´o unciones
de mejo espues a y el eo ema del pun o ijo de los ma em´a icos B ouwe
y Kaku ani.
En los a˜nos siguien es public´o nue os esc i os con o iginales soluciones
pa a algunos p oblemas ma em´a icos y de la Teo ´ıa de Juegos, des acando
la “soluci´on de ega eo de Nash” pa a juegos bipe sonales coope a i os. P o-
puso ambi´en lo que se ha dado en llama “el p og ama de Nash” pa a la
educci´on de odos los juegos coope a i os a un ma co no coope a i o. A los
ein inue e a˜nos se le diagnos ic´o una esquizo enia pa anoica que lo dej´o
p ´ac icamen e ma ginado de la sociedad e in´u il pa a el abajo cien ´ı ico
du an e dos d´ecadas. Pasado ese lapsus, en los a˜nos se en a, ecupe ´o su sa-
lud men al y pudo ol e a la docencia y la in es igaci´on con nue as geniales
apo aciones, consiguiendo en 1994 el P emio N´obel de Econom´ıa compa -
ido con John C. Ha sanyi y Reinha Sel en po sus pione os an´alisis del
equilib io en la Teo ´ıa de los Juegos no coope a i os.
10 Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
cada uno, mien as que en el en oque no coope a i o se analiza que decisiones
oma ´ıa cada jugado en ausencia de acue do p e io. En e los juegos no
coope a i os cabe hace dos dis inciones b´asicas, juegos es ´a icos o din´amicos,
y juegos con o sin in o maci´on comple a.
Aunque se explica ´a con m´as de alle cada uno de los ´e minos, se incluye
a con inuaci´on una p ime a de inici´on de la e minolog´ıa b´asica que se u iliza
habi ualmen e en la Teo ´ıa de Juegos.
•Jugado es: Pa icipan es que oman decisiones con el in de maximiza
su u ilidad.
•Acciones de cada jugado : Decisiones que puede oma cada jugado .
El conjun o de acciones de un jugado puede se ini o o in ini o.
•Resul ados del juego: Dis in os modos en que puede conclui un juego.
Cada esul ado conlle a unas consecuencias pa a cada jugado .
•Pagos: Valo aci´on que pa a cada jugado ienen las consecuencias de
alcanza un de- e minado esul ado. Cada jugado ecibe un pago al
acaba el juego.
•Es a egias: Plan comple o de acciones con las que cada jugado pa i-
cipa en el juego.
•Fo ma no mal y o ma ex ensi a: Son o mas de desc ibi un juego.
Ambas especi ican los jugado es, las acciones y los pagos.
La o ma no mal o o ma es a ´egica o ganiza la desc ipci´on cen ando
su ´en asis en las es a egias de los jugado es. La o ma ex ensi a lo hace en
o ma de ´a bol, esal ando la secuencia del juego.
En es e abajo nos cen a emos en juegos coope a i os y juegos no coope-
a i os. Veamos aho a un ejemplo:

PRELIMINARES 11
Ejemplo 1.1.1. Pied a, papel o ije a. Dos indi iduos, a los que denomi-
na emos Jugado I y Jugado II, escogen simul ´aneamen e una de las es
opciones (pied a, papel o ije a). Si uno escoge la pied a y el o o papel, gana
quien escoge papel. Si uno escoge la pied a y el o o la ije a, gana el que
escoge pied a. Si uno escoge el papel y el o o la ije a, gana quien escoge i-
je a. Si los dos jugado es eligen la misma opci´on se empa a. La in o maci´on
ele an e la podemos esumi en la abla siguien e:
Pied a Papel Tije
Pied a 0 -1 1
Papel 1 0 -1
Tije a -1 1 0
1.2. Concep os b´asicos de la P og amaci´on
Lineal
En es e apa ado e emos los concep os b´asicos que necesi a emos de
aho a en adelan e de la p og amaci´on lineal.
De inici´on 1.2.1. Un p oblema de p og amaci´on lineal es un p oblema
de op imizaci´on con es icciones en el que an o la unci´on a op imiza ,
ambi´en llamada unci´on obje i o, como las es icciones son lineales. Todo
p oblema de p og amaci´on lineal se puede exp esa como:
minimiza cx
suje o a xA ≥b,
x≥0,
(P)
donde A es una ma iz m×n,ces un ec o 1×mybes un ec o
1×n. Que emos encon a una soluci´on ac ible pa a el p oblema (es deci ,
un ec o x∈Rmque sa is aga las desigualdades) de modo que minimice la
12 Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
unci´on obje i o cx den o del conjun o de soluciones ac ibles; de al soluci´on
decimos que es ´op ima pa a es e p oblema.
De inici´on 1.2.2. El dual del p oblema de la de inici´on an e io es el
siguien e p oblema de p og amaci´on:
maximiza by
suje o a Ay ≤c ,
y≥0.
(D)
Aho a que emos encon a una soluci´on ac ible pa a el p oblema (es de-
ci , un ec o y∈Rnque sa is aga las desigualdades) de modo que maximice
la unci´on obje i o by den o del conjun o de soluciones ac ibles; de al
soluci´on decimos que es ´op ima pa a es e p oblema.
Si enemos un pa de p oblemas como los de las dos de iniciones an e io es,
nos e e imos al p ime o como el p oblema p imal (P) y al segundo como el
p oblema dual (D). A con inuaci´on enunciamos un impo an e esul ado que
elaciona ambos p oblemas.
Teo ema 1.2.3. [Teo ema de dualidad ]. Sean (P) y (D) un pa de p oblemas
de p og amaci´on lineal duales. En onces,
1. (P) iene una soluci´on ´op ima si y solo si (D) iene una soluci´on ´op i-
ma.
2. Supongamos que x e y son soluciones ac ibles de los p oblemas (P) y
(D), espec i amen e. En onces, x es una soluci´on ´op ima de (P) e y
es una soluci´on ´op ima de (D) si y solo si cx =by .
Pa a llega a la soluci´on de un p oblema de P og amaci´on Lineal se u ili-
zan di e en es m´e odos de soluci´on. Los m´as di undidos son: el m´e odo g ´a ico
y el M´e odo Simplex. La soluci´on de un p oblema de P og amaci´on Lineal
u ilizando un p ocedimien o g ´a ico es posible si se ienen no m´as de dos
PRELIMINARES 13
a iables. El M´e odo Simplex ue el p ime m´e odo su gido pa a soluciona
p oblemas de P og amaci´on Lineal, po lo que se le conside a el m´e odo de
soluci´on cl´asico po excelencia. Teniendo en cuen a la iloso ´ıa de es e m´e odo
han su gido o os m´e odos cuyas en ajas undamen ales se concen an en
las posibilidades de los mismos pa a se p og amados po compu ado as.
El p ocedimien o g ´a ico comienza elabo ando una g ´a ica que mues e
las soluciones posibles ( alo es x1yx2). La g ´a ica end ´a alo es los alo es
x1en el eje ho izon al y los alo es x2en el eje e ical. El p ocedimien o
pa a halla la soluci´on g ´a ica consis e en lo siguien e:
1. Pa a cada inecuaci´on del sis ema de es icciones (medio espacio ce a-
do) se oma la ec a co espondien e y se de e minan los in e cep os
con la g ´a ica. Si la ec a pasa po el o igen del eje de coo denadas, el
´e mino independien e es ce o, en onces se aza la ec a omando el
o igen y o o pun o de e minado dando un alo a bi a io a una de las
a iables.
2. Pa a de e mina los pun os que sa is acen cada inecuaci´on se sus i-
uye un pun o cualquie a del espacio (se ecomienda el o igen cuyas
coo denadas son (0,0)), y de es a o ma se de e mina si los pun os que
sa is acen la misma es ´an hacia el lado que es ´a el o igen o hacia el lado
con a io, se˜nalando con una lecha ese lado. Cuando la ec a pasa po
el o igen en onces se oma o o pun o cualquie a pe o que sean sencillos
los alo es de sus coo denadas, po ejemplo, (0,1) , (1,0), (1,1), e c.
3. Luego se de e mina la egi´on soluci´on que es la egi´on del plano que
sa is ace odas las es icciones al mismo iempo y que debe es a en el
p ime cuad an e. La igu a o mada es un polied o con exo que iene
un conjun o de pun os ex emos.
4. Se busca el pun o ´op imo en e el conjun o de pun os ex emos. Pa a
14 Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
eso se sus i uye cada pa de pun os (x1, x2) de los pun os ex emos en
la unci´on obje i o y se calcula el alo de Z. Si se es ´a maximizando el
alo de la misma, el pun o ´op imo se ´a aquel que p opo cione el alo
mayo pa a Z y si el c i e io de op imizaci´on es de minimiza , en onces
el pun o ´op imo se ´a aquel que p opo cione el alo m´ınimo de Z.
Es e m´e odo g ´a ico iene la des en aja que s´olo pe mi e la soluci´on de
p oblemas que engan dos a iables de aqu´ı que la mayo ´ıa de los p oblemas
de p og amaci´on lineal se esuel an u ilizando como base el m´e odo simplex.
El m´e odo del Simplex cons i uye un p ocedimien o i e a i o algeb aico
que esuel e cualquie p oblema en un n´ume o ini o de pasos. La concep-
ci´on de es e m´e odo ha acili ados que o os especialis as del ema desa ollen
o os m´e odos de soluci´on con la misma iloso ´ıa, pe o m´as adecuados pa a la
p og amaci´on po compu ado as. Pa a explica el m´e odo simplex es necesa-
io de ini un conjun o de concep os b´asicos necesa ios pa a la comp ensi´on
del mismo. Los pasos a ene en cuen a son los siguien es:
Paso 1. Pone el p oblema en o ma es anda : La unci´on obje i o se
minimiza y las es icciones son de igualdad.
Paso 2. Encon a una soluci´on b´asica ac ible.
Paso 3. Tes a la op imalidad.
Paso 4. Elegi una a iable de en ada.
Paso 5. Elegi una a iable de salida.
Paso 6.Ac ualiza la base y la soluci´on b´asica ac ible.
Paso 7. Aho a enemos una soluci´on b´asica ac ible mejo que la inicial.
Necesi amos sabe si ´es a es la ´op ima. Pa a ello necesi amos aplica el es
de op imalidad, el paso 3.
Pa a los que quie an en a en m´as de alle pueden hace uso de Paul R.
Thie y Ge a d E. Keough [9].
Cap´ı ulo 2
Juegos no coope a i os
2.1. In oducci´on a los Juegos en Fo ma Es-
a ´egica
Un juego en o ma es a ´egica es un modelo es ´a ico que desc ibe p o-
blemas de decisi´on en los que in e accionan a ios jugado es. De acue do a
es e modelo, los jugado es oman sus decisiones simul ´anea e independien-
emen e y, aunque los jugado es pod ´ıan comunica se y oma acue dos in-
o males an es de que el juego comience, se supone que no disponen de me-
canisms que les pe mi an oma acue dos inculan es. De aho a en adelan e
asumi emos que odos los jugado es son acionales en el sen ido de que in-
en an maximiza su p opia u ilidad. Da emos aho a la de inici´on o mal de
juego en o ma es a ´egica.
De inici´on 2.1.1. Un juego en o ma es a ´egica G con conjun o de ju-
gado es N= 1, ..., n es una 2n- upla G= (X1, ..., Xn,H1, ..., Hn) donde,
pa a odo i∈N,Xies el conjun o de es a egias del jugado iyHi:X=
Qn
i=1 Xi→Res su unci´on de pago, que asigna a cada pe il de es a egias
x∈Xel pago que iob iene si se juega de acue do a al pe il.
15

16 Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
En ealidad, en un p oblema de decisi´on en el que in e accionan los juga-
do es de N es ´an in oluc ados los siguien es elemen os:
• {Xi}i∈N, los conjun os de es a egias de los jugado es.
•R, el conjun o de posibles esul ados.
•Una aplicaci´on :X=Qn
i=nXi−→ Rque asigna a cada pe il de
es a egias xsu co espondien e esul ado (x).
• {i}i∈N, las p e e encias de los jugado es sob e R ( elaciones bina ias
comple as y ansi i as).
La de inici´on de juego en o ma es a ´egica asume que las p e e encias
de los jugado es pueden ep esen a se a a ´es de unciones de u ilidad. Si
pa a cada i∈Ndeno amos po hisu unci´on de u ilidad, la co espondien e
unci´on de pago Hi iene dada, pa a odo pe il de es a egias x∈X, po
Hi(x) = hi( (x)). Veamos aho a un ejemplo muy conocido en la Teo ´ıa de
Juegos.
Ejemplo 2.1.2. Dilema del p isione o. Dos sospechosos de un deli o g a e y
de un peque˜no hu o son ubicados en celdas di e en es. Se sabe que son cul-
pables de ambos hechos, pe o no hay p uebas de que hayan come ido el deli o.
A ambos se les da la opo unidad de con esa . Si ambos con iesan el deli o,
cada uno de ellos pasa ´a 10 a˜nos en la c´a cel. Si s´olo uno con iesa, ac ua ´a
como es igo con a el o o (que pasa ´a 15 a˜nos en la c´a cel) y no ecibi ´a
ning´un cas igo. Finalmen e, si ninguno con iesa, se ´an juzgados po el hu -
o y cada uno de ellos pasa ´a en la c´a cel 1 a˜no. Siguiendo la e minolog´ıa
com´un pa a es e juego, nos amos a e e i a la con esi´on como “dela a ”
(D) y a la no con esi´on como “no dela a ” (ND). En al caso, el juego del
dilema del p isione o se puede ep esen a como el juego en o ma es a ´egica
(X1, X2, H1, H2)dado po :
JUEGOS NO COOPERATIVOS 17
•X1=X2={ND, D};
•H1(ND, ND) = -1, H1(ND, D) = -15, H1(D, ND) = 0, H1(D, D) =
-10;
•H2(ND, ND) = -1, H2(ND, D) = 0, H2(D, ND) = -15, H2(D, D) =
-10.
La siguien e abla mues a una ep esen aci´on m´as con enien e de es e
juego, que es la o ma habi ual de ep esen a juegos en o ma es a ´egica
bipe sonales con conjun os ini os de es a egias.
ND D
ND -1, -1 -15,0
D 0, -15 -10, -10
El dilema del p isione o es un cl´asico en Teo ´ıa de Juegos. Ha sido am-
pliamen e u ilizado en ´ambi os e´o icos, aunque ambi´en pa a p op´osi os m´as
aplicados en sociolog´ıa o econom´ıa. El esul ado “coope a i o”, (-1,-1), es
bas an e bueno pa a ambos jugado es; es “casi” odo lo que pueden ob ene
en el juego. Aho a bien, pa a cada jugado , la es a egia D conduce a un pago
es ic amen e m´as al o que ND, independien emen e de la es a egia elegida
po el o o jugado . De es a o ma, un deciso acional debe ´ıa juga siem-
p e D. As´ı, si ambos jugado es se compo an acionalmen e, ob ienen pagos
(-10,-10), que son muchos peo es que los pagos en el esul ado “coope a i o”.
Muchas si uaciones de la ida eal pueden se is as como un juego del dilema
del p isione o. Po ejemplo, en la ca e a nuclea en e los EEUU y la URSS
du an e la denominada Gue a F ´ıa, ambos pa´ıses deb´ıan decidi si p oduci
o no a mas nuclea es; en es a si uaci´on, los pagos end ´ıan una es uc u a
simila a la abla is a an es. 
18 Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
2.2. El Equilib io de Nash en Juegos en Fo -
ma Es a ´egica
El concep o de soluci´on m´as impo an e pa a juegos en o ma es a ´egica
es el equilib io de Nash. Po su impac o en la eo ´ıa econ´omica, John Nash
ecibi´o el P emio Nobel de Econom´ıa en 1994. En Kohlbe g [16] se dice que
la idea p incipal del equilib io de Nash es hace una impo an e simpli ica-
ci´on y, en ez de p eocupa se de c´omo se desa olla ´a la in e acci´on en e los
jugado es, p egun a se cu´ales se ´an los esul ados es ables de al in e acci´on.
De hecho, un equilib io de Nash de un juego en o ma es a ´egica no es m´as
que un pe il de es a egias al que ning´un jugado gana des i´andose unila-
e almen e de ´el; en es e sen ido puede deci se que el concep o de equilib io
de Nash busca esul ados es ables de la si uaci´on in e ac i a desc i a po el
juego en o ma es a ´egica.
De inici´on 2.2.1. Sea G = (X1, ..., Xn, H1, ..., Hn)un juego en o ma es-
a ´egica. Un equilib io de Nash de G es un pe il de es a egias x∈X
que cumple que
Hi(x)≥Hi(x−i, x0
i),
pa a odo x0
i∈Xi, y odo i∈N, donde el pe il (x−i, x0
i)es:
(x1, ..., xi−1, x0
i, xi+1, ..., xn).
Vemos aho a un pa de ejemplos.
Ejemplo 2.2.2. El ´unico equilib io de Nash del dilema del p isione o es (D,
D). De hecho, como ya hemos a gumen ado, (D, D) es el ´unico compo a-
mien o acional en un con ex o no coope a i o.
Ejemplo 2.2.3. Pa es o nones. Los jugado es 1 y 2 ienen que escoge si-
mul ´anea e independien emen e un n´ume o na u al. Si la suma de los n´ume-
os escogidos es pa , en onces gana el jugado 1 y si la suma es impa en onces
JUEGOS NO COOPERATIVOS 19
gana el jugado 2. Esencialmen e, odo lo que impo a pa a es e juego es si
el n´ume o escogido es pa (P) o impa (I) y, po an o, el juego en o ma es-
a ´egica que desc ibe es a si uaci´on es el que se ecoge en la siguien e abla;
cla amen e, es e juego no iene equilib ios de Nash.
P I
P 1,-1 -1,1
I -1,1 1,-1
A con inuaci´on amos a p esen a el eo ema de Nash, que da una con-
dici´on su icien e pa a la exis encia de equilib ios de Nash en un juego en
o ma es a ´egica. Pa a enuncia y demos a el eo ema de Nash debemos
in oduci algunos concep os y esul ados de an´alisis de co espondencias.
De inici´on 2.2.4. Sea X ⊂Rne Y ⊂Rm.
1) Una co espondencia F de X en Y es una aplicaci´on de X en 2Y(la
clase de odos los subconjun os de Y).
2) Se dice que una co espondencia F es semicon inua supe io men e
si pa a oda sucesi´on {xk} ⊂ Xque con e ge a x ∈Xy odo abie o G de Y
que con iene a F(x), exis e k0∈N al que F(xk)⊂Gpa a odo k≥k0.
3) Se dice que una co espondencia F es no ac´ıa, ce ada o con exa
si, pa a odo x∈X, F(x) es un subconjun o de Y no ac´ıo, ce ado o con exo,
espec i amen e.
4) Una aplicaci´on →Res cuasi-c´onca a si pa a odo ∈R, el con-
jun o {x∈X: (x)≥ }es con exo o, equi alen emen e si pa a cualesquie a
x, ˆx∈Xy pa a odo α∈[0,1], (αx + (1−α) ˆx)≥m´ın{ (x), (ˆx)}. Cla a-
men e la conca idad implica cuasi-conca idad ya que la conca idad equie e
que
(αx + (1 −α)ˆx)≥α (x) + (1 −α) (ˆx)
y
α (x) + (1 −α) (ˆx)≥min{ (x), (ˆx)}.
26 Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
No a 2.3.8. Po las p oposiciones an e io es, si (x, y)y(x0, y0)son equili-
b ios de Nash del juego bipe sonal de suma nula G, en onces (x, y0)y(x0, y)
son ambi´en equilib ios de Nash de G, y adem´as,
H(x, y) = H(x0, y0) = H(x, y0) = H(x0, y).
Sin emba go, es o no es cie o pa a cualquie juego bipe sonal como e emos,
po ejemplo, al es udia los juegos bima iciales.
No a 2.3.9. Un juego bipe sonal de suma cons an e es un juego en
o ma es a ´egica G= (X, Y, H1, H2) al que, pa a odo pe il de es a egias
(x, y)∈X×Y, H1(x, y) + H2(x, y) = k, siendo k una cons an e eal. Ob ia-
men e, un juego de suma nula es un juego de suma cons an e con k = 0. Sin
emba go, desde el pun o de is a es a ´egico, analiza el juego G es lo mismo
que analiza el juego de suma nula G1= (X, Y, H1)ya que (x, y)∈X×Y
es un equilib io de Nash de G si y s´olo si es un equilib io de Nash de G1.
2.4. Es a egias Mix as en Juegos Fini os
A pa i de aho a nos cen a emos en la clase de los juegos ini os, que
de inimos a con inuaci´on.
De inici´on 2.4.1. Un juego ini o es un juego en o ma es a ´egica
G= (X1, ..., Xn, H1, ..., Hn)
cuyos jugado es ienen conjun os de es a egias ini os, es deci , al que |Xi|=
mipa a odo i∈N(siendo cada miun n´ume o na u al).
El eo ema de Nash is o an e io men e no se puede aplica a los juegos
ini os, ya que los conjun os de es a egias no son con exos. Po o o lado, ya
hemos is o un juego ini o sin equilib ios de Nash: el juego de pa es o nones.

JUEGOS NO COOPERATIVOS 27
Sin emba go, hay un “ingenio e´o ico” que nos pe mi e ex ende el juego y
ga an iza la exis encia de equilib ios de Nash en la e isi´on ex endida de odo
juego ini o: al ingenio consis e en aumen a las posibilidades es a ´egicas
de los jugado es y conside a que no s´olo ienen sus es a egias iniciales (que
pasa emos a denomina es a egias pu as), sino que ambi´en pueden escoge
lo e ´ıas sob e sus conjun os ini os de es a egias pu as. Es a ex ensi´on del
juego o iginal se llama ex ensi´on mix a y las es a egias de los jugado es en
la ex ensi´on mix a se llaman es a egias mix as.
Aunque nos hemos e e ido a la ex ensi´on mix a de un juego como un
“ingenio e´o ico”, las es a egias mix as su gen de modo na u al en muchas
si uaciones en la p ´ac ica. Vamos a discu i b e emen e es a cues i´on en el
ejemplo siguien e, en el que in oducimos in o malmen e la ex ensi´on mix a
de un juego en o ma es a ´egica. Despu´es del ejemplo da emos una de inici´on
o mal.
Ejemplo 2.4.2. Conside emos de nue o el juego de pa es y nones y supon-
gamos aho a que los jugado es, adem´as de escoge P o I, pueden escoge
ambi´en una lo e ia L que selecciona P con p obabilidad 1/2 e I con p o-
babilidad 1/2. Supongamos ambi´en que los jugado es ienen unciones de
u ilidad de on Neumann y Mo gens e n y, po an o, sus unciones de pago
se pueden ex ende al conjun o de pe iles de es a egias mix as calculando
sus co espondien es espe anzas ma em´a icas. El juego esul an e iene dado
po la abla siguien e:
P I L
P 1,-1 -1,1 0,0
I -1,1 1,-1 0,0
L 0,0 0,0 0,0
Pa a calcula las unciones de pago del juego ex endido hemos enido en cuen-
a que, dado que es amos en un juego en o ma es a ´egica, los jugado es
28 Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
eligen sus lo e ´ıas independien emen e. As´ı, po ejemplo:
H1(L, L) = 1
4H1(P, P) + 1
4H1(P, I) + 1
4H1(I, P) + 1
4H1(I, I) = 0
Obse amos que es e juego iene un equilib io de Nash: (L, L). La ex en-
si´on mix a del juego de pa ida es un nue o juego en o ma es a ´egica en
el que los jugado es pueden escoge cualquie lo e ´ıa sob e {P, I}. Es ´acil
comp ob a que el ´unico equilib io de Nash de es e juego es (L, L). Una po-
sible in e p e aci´on de es o es la siguien e. En el juego de pa es o nones es
muy impo an e pa a cada uno de los jugado es que el o o no enga ninguna
in o maci´on sob e si elegi ´a inalmen e P o I. Pa a ello, lo mejo es que ni
´el mismo lo sepa, lo cual puede lle a se a e ec o seleccionando la es a egia
de L. 
De inici´on 2.4.3. Sea G= (X1, ..., Xn, H1, ..., Hn)un juego ini o. La ex-
ensi´on mix a de G es el juego en o ma es a ´egica
E(G) = (S1, ...Sn, H1, ..., Hn)
donde, pa a cada jugado i∈N,
1. Si={si∈RXi:si(xi)≥0∀xi∈Xi,Pxi∈Xisi(xi)=1}
2. Hi(s) = Px∈XHi(x)s(x),pa a odo s∈S, donde S=Qi∈NSiy s(x)
deno a el p oduc o s1(x1)×... ×sn(xn).
No a 2.4.4. La ex ensi´on mix a de un juego ini o s´olo iene sen ido cuando
los jugado es ienen p e e encias sob e el conjun o de lo e ´ıas de inidas sob e
el conjun o de posibles esul ados y sus unciones de u ilidad son unciones
de u ilidad de on Neumann y Mo gens e n.
No a 2.4.5. E(G) es una ex ensi´on de G en el sen ido de que, pa a odo
jugado i, cada elemen o de Xi, o es a egia pu a, puede se iden i icado con
JUEGOS NO COOPERATIVOS 29
un elemen o de Si, o es a egia mix a, po lo que podemos esc ibi Xi⊂Si.
Po o o lado, las unciones de pago de los jugado es en E(G) son ex ensiones
de las unciones de pago de los jugado es en G.
No a 2.4.6. El conjun o de es a egias del jugado ilo amos a iden i ica
en ocasiones con el s´ımplex de Rmidado po :
{si∈Rmi:sk
i≥0∀k∈ {1, ..., mi},
mi
X
k=1
sk
i= 1}.
No a 2.4.7. La ex ensi´on mix a de un juego ini o cumple las hip´o esis del
eo ema de Nash y, po lo an o, un co ola io de al eo ema es que la ex en-
si´on mix a de un juego ini o iene siemp e, al menos, un equilib io de Nash.
De hecho, ´es e ue el esul ado p obado po John Nash en su a ´ıculo o iginal.
Pa a e mina con es a secci´on da emos algunas de iniciones y esul ados
b´asicos en elaci´on con los juegos ini os.
De inici´on 2.4.8. Sea E(G) la ex ensi´on mix a de un juego ini o y sean
si∈Si, una es a egia del jugado i, y s∈Sun pe il de es a egias.
1. El sopo e de sies el conjun o C(si)dado po :
{xi∈Xi:si(xi)>0},
2. El sopo e de ses el conjun o C(s)dado po :
Y
i∈N
C(si) = {x∈X:s(x)>0}.
3. Se dice que sies comple amen e mix a si C(si) = Xi. Se dice que
s es comple amen e mix a si C(s) = Xo, equi alen emen e, si sies
comple amen e mix a pa a odo i∈N.
30 Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
4. El conjun o de mejo es espues as pu as del jugado ias−ies
el conjun o
PBi(s−i) = {xi∈Xi:Hi(s−i, xi)≥Hi(s−i, x0
i)∀x0
i∈Xi}.
Usa emos la no aci´on PB(s) = Qi∈NPBi(s−i).
P oposici´on 2.4.9. En la ex ensi´on mix a de un juego ini o, pa a odo
i∈N, si∈Siys∈S, se cumple:
1. si∈Bi(s−i)si y s´olo si C(si)⊂PBi(s−i).
2. s es un equilib io de Nash de E(G) si y solo si C(s)⊂PB(s).
3. s es un equilib io de Nash de E(G) si y solo si Hi(s)≥Hi(s−i, xi)pa a
odo xi∈Xiy odo i∈N.
Demos aci´on. Es ´acil e que Hi(s) = Pxi∈XiHi(s−i, xi)si(xi), con lo que
la p oposici´on se sigue inmedia amen e.
Obs´e ese que el apa ado 3) de la p oposici´on an e io implica que si un
pe il de es a egias es un equilib io de Nash de un juego ini o G ambi´en lo
es de E(G).
2.5. Juegos Ma iciales y Algo i mos
En es a secci´on comp oba emos que esol e un juego ma icial es, en
cie o modo, equi alen e a esol e un pa de p oblemas de p og amaci´on
lineal duales y ob end emos un algo i mo pa a esol e juegos ma iciales.
De inici´on 2.5.1. Un juego bima icial es la ex ensi´on mix a de un juego
bipe sonal ini o (M, N, H1, H2), donde M={1, .., m}yN={1, .., n}. Po
an o, un juego bima icial es una 4- upla (Sm, Sn, H1, H2) al que:
JUEGOS NO COOPERATIVOS 31
1. Sm={x∈Rm:xi≥0∀i∈M, Pi∈Mxi= 1}.
2. Sn={y∈Rn:yj≥0∀j∈N, Pj∈Nyj= 1}.
3. Pa a odo (x, y)∈Sm×Sn,
H1(x, y) = X
i∈MX
j∈N
H1(i, j)xiyj=xAy ,
donde A= (H1(i, j))i∈M,j∈Nes una ma iz m×n.
4. Pa a odo (x, y)∈Sm×Sn,
H2(x, y) = X
i∈MX
j∈N
H2(i, j)xiyj=xBy ,
donde B= (H2(i, j))i∈M,j∈Nes una ma iz m×n.
N´o ese que pa a ca ac e iza un juego bima icial es su icien e conoce el
pa de ma ices (A, B).
De inici´on 2.5.2. Un juego ma icial es la ex ensi´on mix a de un juego
bipe sonal de suma nula ini o (M, N, H), donde M={1, ..., m}yN=
{1, ..., n}. Po an o, un juego ma icial es una e na (Sm, Sn, H) al que:
1. Sm={x∈Rm:xi≥0∀i∈M, Pi∈Mxi= 1}.
2. Sn={y∈Rn:yi≥0∀j∈N, Pj∈Nyj= 1}.
3. Pa a odo (x, y)∈Sm×Sn,
H(x, y) = X
i∈MX
j∈N
H(i, j)xiyj=xAy ,
donde A= (H(i, j))i∈M,j∈Nes la ma iz m×nque con iene los pagos
del jugado 1.

32 Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
V´ease que pa a ca ac e iza un juego ma icial es su icien e da la ma iz
A. Ob iamen e odo juego ma icial puede e se como un juego bima icial,
aunque el ec´ıp oco no es cie o. Po an o, el eo ema de Nash implica que
odo juego ma icial iene un equilib io de Nash. Po la P oposici´on 2.3.7,
se iene en onces que odo juego ma icial es ´a es ic amen e de e minado.
´
Es e es el esul ado conocido como eo ema minimax, p obado po John
on Neumann en 1928.
Teo ema 2.5.3. [Teo ema minimax de on Neumann ]. Todo juego ma icial
iene un alo (en es a egias mix as), es deci ,
m´ax
x∈Xm´ın
y∈Yx Ay = m´ın
y∈Ym´ax
x∈Xx Ay.
El lec o in e esado en la demos aci´on del Teo ema 2.5.3 puede encon-
a la en Isabel Fe n´andez [6].
Exis en di e en es p uebas di ec as del eo ema minimax, algunas de ellas
muy elegan es: una basada en un lema de al e na i as pa a ma ices, una
basada en un eo ema de pun o ijo de B owe ; incluso hay una que u iliza
´unicamen e el p incipio de inducci´on. El lec o in e esado puede encon a
algunas de es as demos aciones en Owen [8] y Gonz´alez-D´ıaz y o os [11].
Vamos a e a con inuaci´on dos m´e odos pa a esol e juegos ma iciales
(po “ esol e un juego ma icial” en endemos encon a su alo y los con-
jun os de es a egias ´op imas de los jugado es). Comenzamos po un m´e odo
geom´e ico pa a juegos ma iciales 2 ×n. Pa a desc ibi lo necesi amos el
siguien e esul ado.
P oposici´on 2.5.4. Conside emos un juego ma icial m×ndado po la
ma iz A. En onces, pa a odo x∈Smy odo y∈Sn,
Λ(x) = m´ın
j∈NxPj,
Γ(y) = m´ax
i∈MQiy ,
JUEGOS NO COOPERATIVOS 33
donde PjyQideno an la columna j-´esima y la ila i-´esima de A, espec i a-
men e.
Demos aci´on. S´olo amos a p oba la p ime a de las igualdades (la segunda
se p oba ´ıa analogamen e). Sea x∈Sm, Cla amen e,
Λ(x) = ´ın
y∈Sn
xAy ≤m´ın
j∈NxPj.
Po o o lado, dado y∈Sn.
xAy =X
k∈N
(xPk)yk≥X
k∈N
(m´ın
j∈NxPj)yk= m´ın
j∈NxPj.
Po an o, Λ(x) = ´ın y∈SnxAy ≥m´ınj∈NxPj,con lo que se iene el esul ado.
Conside amos aho a un juego ma icial 2×ndado po la siguien e ma iz:


a11 ... a1j... a1n
a21 ... a2j... a2n

Podemos iden i ica una es a egia del jugagado 1, x∈S2, con su p ime a
componen e, y u ilizando la p oposici´on an e io se iene que:
V= m´ax
x∈[0,1] Λ(x) = m´ax
x∈[0,1] m´ın
j∈N[(x, 1−x)a1j
a2j]
= m´ax
x∈[0,1] m´ın
j∈N[a2j+ (a1j−a2j)x].
Po lo an o, pa a calcula el alo del juego y el conjun o de es a egias
´op imas del jugado 1, se ´a su icien e ep esen a , pa a cada j∈N, los
segmen os {(x, a2j+ (aij −a2j)x) : x∈[0,1]}, ob ene su en ol u a in e io
y busca el conjun o de pun os ¯x∈Smque maximiza esa en ol u a.
Aho a, pa a calcula el conjun o de es a egias ´op imas del jugado 2,
debemos ene en cuen a que y∈Snes una de ales es a egias si y s´olo si:
34 Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
V= Γ(y) = m´ax
x∈[0,1] H(x, y)
= m´ax
x∈[0,1] xAy = m´ax
x∈[0,1][X
j∈N
[a2j+ (a1j−a2j)x]yj].
En consecuencia, una es a egia ´op ima del jugado 2 end ´a dada po un
elemen o de Snque p opo ciona una combinaci´on con exa de los segmen os
{(x, a2j+(aij −a2j)x) : x∈[0,1]}que se encuen a bajo el segmen o {(x, V ) :
x∈[0,1]}. A con inuaci´on lo emos con un ejemplo.
Ejemplo 2.5.5. Resol amos el juego ma icial dado po la ma iz
A=

2 2 3
1 4 3 

Los segmen os co espondien es a las columnas de A son, {(x, 1 + x) :
x∈[0,1]},{(x, 4−2x) : x∈[0,1]},{(x, 3) : x∈[0,1]}. Cla amen-
e, el alo de es e juego es V= 2, el conjun o de es a egias del juga-
do 1 es O1(A) = {(1,0)}y el conjun o de es a egias ´op imas del juga-
do 2 es la en ol u a con exa de (1,0,0) y(2/3,1/3,0), es o es O2(A) =
con ({(1,0,0),(2/3,1/3,0)}). Pa a ob ene O2(A), la o ma m´as sencilla
se ´a combina una ec a c ecien e y o a dec ecien e de en e las que co -
an a la ec a y=V(y= 2) y consegui que la pendien e de esa combinaci´on
sea nula. La ec a se ´a pa alela al eje de abcisas y pasa po los pun os (0, V )
y(1, V ). Si aho a omamos una combinaci´on con exa de las exp esiones 1+x
y4−2xde la o ma α(1 + x) + (1 −α)(4 −2x) = (3α−2)x+ 4 −3α, con
α∈[0,1], en onces po la condici´on de pendien e nula, α= 2/3.
A con inuaci´on amos a desc ibi el denominado m´e odo de las sub-
ma ices, que es un algo i mo pa a esol e cualquie juego ma icial m×n.
Se basa en la ca ac e izaci´on de los pun os ex emos de los conjun os de
es a egias ´op imas de los jugado es.
JUEGOS NO COOPERATIVOS 35
P oposici´on 2.5.6. Sea A un juego ma icial m×ny omemos x∈Sme
y∈Sn. En onces:
1. x∈O1(A)si y s´olo si xPj≥V, pa a odo j∈N.
2. y∈O2(A)si y s´olo si Qiy ≤V, pa a odo i∈M.
Demos aci´on. P obamos s´olo la p ime a equi alencia (la segunda se p o-
ba ´ıa an´alogamen e).
“⇒” Supongamos que x∈O1(A). En onces, po la P oposici´on 2.5.4,
V= Λ(x) = m´ınj∈NxPj. Consecuen emen e, V≤xPjpa a odo j∈N.
“⇐” Supongamos que xPj≥Vpa a odo j∈N. Aplicamos nue amen e
la P oposici´on 2.5.4:
V= m´ax
x0∈Sm
Λ(x0)≥Λ(x) = m´ın
j∈NxPj≥V
con lo que concluye la demos aci´on.
P oposici´on 2.5.7. Sea A un juego ma icial m×n. En onces, los conjun-
os de es a egias ´op imas de los jugado es, O1(A)yO2(A), son conjun os
con exos y compac os.
Demos aci´on. En i ud de la P oposici´on 2.5.6, los conjun os son cla amen-
e con exos. Tambi´en es ´a cla o que son aco ados. Son ce ados ya que las
unciones Λ y Γ son con inuas y O1(A) = Λ−1({V}) y O2(A)=Λ−1({V}).
P oposici´on 2.5.8. Sea A un juego ma icial m×n, y omemos x∈Sm,
y∈Sn. En onces, x∈O1(A)ey∈O2(A)si y s´olo si xPj≥Qiy pa a odo
i∈My odo j∈N.
Demos aci´on. “⇒” Es a implicaci´on es una consecuencia de la P oposici´on
2.5.6.
“⇐” Si xPj≥Qiy pa a odo i∈My odo j∈N, en onces
V=γ≤Γ(y) = m´ax
i∈MQiy ≤m´ın
j∈NxPj= Λ(x)≤λ=V.
42 Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
b) Si u es una soluci´on ´op ima del p oblema (2.2), en onces (x, Λ) es una
soluci´on ´op ima del p oblema (2.1) donde, pa a odo i∈M,
xi=1
uJ
m
ui,yΛ = 1
uJ
m
.
Aho a podemos p ocede de modo an´alogo desde el pun o de is a del
jugado 2. Pa a encon a el alo del juego y el conjun o de es a egias
´op imas del jugado 2 bas a esol e el siguien e p oblema de p og amaci´on
lineal:
minimiza Γ
suje o a Qiy ≤Γ,∀i∈M,
yJ
n= 1,
y≥0.
Cla amen e es e p oblema es equi alen e al siguien e:
maximiza 1
Γ
suje o a Ay ≤ΓJ
m,(2.3)
yJ
n= 1,
y≥0.
Conside emos aho a el p oblema que desc ibimos a con inuaci´on (que es
el dual del p oblema (2.2):
maximiza wJ
n
suje o a Aw ≤J
m,(2.4)
w≥0.

JUEGOS NO COOPERATIVOS 43
De nue o, es un eje cicio sencillo p oba el siguien e esul ado.
P oposici´on 2.6.2. a) Si el pa (y, Γ) es una soluci´on ´op ima del p oblema
(2.3), en onces wes una soluci´on ´op ima del p oblema (2.4) donde, pa a odo
j∈N,
wj=1
Γyj.
b) Si wes una soluci´on ´op ima del p oblema (2.4), en onces (y, Γ) es una
soluci´on ´op ima del p oblema 2.3 donde, pa a odo j∈N,
yj=1
wJ
n
wj,yΓ = 1
wJ
n
.
Como conclusi´on podemos deci que, pa a esol e un juego ma icial,
es su icien e esol e los p oblemas (2.2) y (2.4) que son un pa de p oble-
mas de p og amaci´on lineal duales. N´o ese que es e esul ado implica que el
algo i mo del s´ımplex puede se usado pa a esol e un juego ma icial.
Vamos a e aho a que, pa a esol e un pa de p oblemas de p og ama-
ci´on lineal, es su icien e esol e un cie o juego ma icial. Pa a ello p ecisa-
mos de unas de iniciones y esul ados b´asicos.
De inici´on 2.6.3. Un juego ma icial n×nca ac e izado po la ma iz A
se dice sim´e ico si los jugado es son in e cambiables, es o es, si A=−A .
P oposici´on 2.6.4. Sea A un juego ma icial n×nsim´e ico. En onces, su
alo V es ce o y, adem´as, O1(A) = O2(A).
De inici´on 2.6.5. Sea A un juego ma icial m×n. Una ila Qise denomina
ele an e si exis e x∈O1(A) al que xi>0. Una columna Pjse denomina
ele an e si exis e y∈O2(A) al que yj>0.
P oposici´on 2.6.6. Sea A un juego ma icial m×n.
1. Si Pjes una columna ele an e, en onces se iene que xPj=Vpa a
odo x∈O1(A).
44 Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
2. Si Qies una ila ele an e, en onces se iene que Qiy =Vpa a odo
y∈O2(A).
Conside emos aho a un pa de p oblemas de p og amaci´on lineal duales
(P)y(D) seg´un las de iniciones . Conside emos el siguien e juego ma icial
B:
B=



0A−c
−A 0b
c−b0




Obs´e ese que se a a de un juego ma icial sim´e ico, po lo que su alo
es ce o y adem´as O1(B) = O2(B).A pa i de aho a en juegos ma iciales
sim´e icos, al e e i nos a una es a egia ´op ima de los jugado es di emos
sencillamen e una es a egia ´op ima del juego.
Teo ema 2.6.7. Los p oblemas (P) y (D) ienen soluciones ´op imas si y s´olo
si el juego ma icial B iene una es a egia ´op ima cuya ´ul ima componen e
es posi i a.
Ejemplo 2.6.8. La ma iz de pagos del jugado 1 es


2 4 3
7 2 5 

Es cla o que no hay es a egias pu as en equilib io.
Fo mulamos uno de los p oblemas de p og amaci´on lineal, o el del jugado
1
m´ax
suje o a 2p1+ 7p2≥
4p1+ 2p2≥
3p1+ 5p2≥
p1 + p2= 1
p1, p2≥0
JUEGOS NO COOPERATIVOS 45
o bien, el del jugado 2
m´ın w
suje o a 2q1+ 4q2+ 3q3≤w
7q1+ 2q2+ 5q3≤w
q1+q2+q3= 1
q1, q2, q3≥0
Si po ejemplo esol emos es e ´ul imo p oblema, la soluci´on ´op ima es
q1= 2/7, q2= 5/7, q3= 0, siendo w= = 24/7, y las a iables duales son
(−5/7,−2/7), de donde se deduce que la es a egia ´op ima del jugado 1 es
p1= 5/7, p2= 2/7.
46 Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
Cap´ı ulo 3
Juegos Coope a i os
En es e cap´ı ulo a amos de es udia c´omo pueden ac ua g upos de
jugado es, sin de ene nos en las acciones indi iduales de los mismos. El p o-
blema undamen al que amos a es udia es el de c´omo puede hace se una
dis ibuci´on de pagos en e los jugado es que o man una coalici´on y han
ob enido una ganancia ac uando coo dinalmen e, de mane a coope a i a y
c´omo la p og amaci´on lineal acili a el c´alculo. Pa a esol e dicho p oblema,
y al igual que en el caso de los juegos no coope a i os, se han p opues o
di e sos concep os de soluci´on. En es e cap´ı ulo se es udian dos de ellos: el
co e y el nucleolus.
3.1. In oducci´on
En los juegos coope a i os se pa e de que es posible que algunos juga-
do es puedan llega a acue dos inculan es (a los que queda ´ıan obligados
de mane a ineludible), po lo que se a a es de es udia los esul ados que
puede ob ene cada una de las coaliciones de jugado es que se pueden o ma .
Se a a, po an o de es udia c´omo pueden ac ua g upos de jugado es, in-
e es´andonos los compo amien os colec i os y sin que haga al a de ene se
47

48 Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
en las acciones indi iduales de cada uno de los miemb os de una coalici´on.
A con inuaci´on, as eco da la de inici´on de juego en o ma coalicional
(o juego en o ma de unci´on ca ac e ´ıs ica), se in oducen o as de iniciones
que se an a u iliza a lo la go del cap´ı ulo.
De inici´on 3.1.1. Un juego en o ma coalicional o en o ma unci´on
ca ac e ´ıs ica con u ilidades ans e ibles consis e en:
1. Un conjun o ini o de jugado es N={1,2, ..., n}.
2. Una unci´on ca ac e ´ıs ica, que asocia a cada subconjun o S de N un
n´ume o eal (S)( alo de coalici´on), siendo (∅)=0.
Po an o, G= (N, )es un juego en o ma coalicional con u ilidades ans-
e ibles si Ny es ´an especi icados.
Si al c ece el n´ume o de jugado es que o man una coalici´on se cumple que
el bene icio o ganancia que ob iene la coalici´on no disminuye, es amos an e un
juego coope a i o mon´o ono, al como se de ine o malmen e a con inuaci´on.
De inici´on 3.1.2. Se dice que un juego G= (N, )es mon´o ono si ∀S, T ⊂
N, con S⊂T, se e i ica que
(S)≤ (T).
A con inuaci´on se de ine el concep o de juego supe adi i o, en el cual
cuando dos coaliciones con in e secci´on ac´ıa se unen el bene icio o ganancia
de la nue a coalici´on es al menos igual a la suma de los bene icios de las
coaliciones que se unen.
De inici´on 3.1.3. Se dice que un juego G= (N, )es supe adi i o si
∀S, T ⊂N, con S∩T=∅, se e i ica que
(S) + (T)≤ (S∪T)
JUEGOS COOPERATIVOS 49
Si la desigualdad de la de inici´on an e io se da en sen ido opues o se
dice que el juego es subadi i o.
Aho a se in oduce una p opiedad m´as ue e que la an e io . Si dos coa-
liciones (con in e secci´on no necesa iamen e ac´ıa) se unen, en onces la suma
de los bene icios de la uni´on e in e secci´on es al menos igual a la suma de
bene icios de las coaliciones que se unen.
De inici´on 3.1.4. Se dice que un juego G= (N, )es con exo si ∀S, T ⊂
N, se e i ica que
(S) + (T)≤ (S∪T) + (S∩T)
Si la desigualdad an e io se da en sen ido opues o se dice que el juego es
c´onca o.
De inici´on 3.1.5. Sean (N, )y(N, w)dos juegos coope a i os, con N=
{1,2, ..., N}. Sea λ∈R. Se de ine:
( +w)(S) = (S) + w(S),∀S⊂N;
(λ )(S) = λ[ (S)],∀S⊂N;
( w)(S) = (s)w(S),∀S⊂N.
Se comp ueba acilmen e que el conjun o de juegos coope a i os con n
jugado es, sob e el cue po de los n´ume os eales, con las ope aciones de inidas
de suma y de p oduc o po un escala , iene es uc u a de espacio ec o ial
de dimensi´on 2n−1.
3.2. El Co e y Concep os Relacionados
Sea G= (N, ) un juego en su o ma coalicional, en donde N={1, ..., n}
es el conjun o de jugado es y es la unci´on ca ac e ´ıs ica. Si en un juego los
50 Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
jugado es deciden abaja conjun amen e, es deci , coope an, el p oblema
que se p esen a consis e en c´omo epa i el alo (N) en e los njugado es.
Sea x= (x1, x2, ..., xn)∈Rnun ec o de dis ibuci´on de pagos, en donde
pa a cada i= 1,2, .., n,xi ep esen a el pago que ecibe el jugado i. Pa a
cualquie coalici´on S⊂N, se u iliza ´a la siguien e no aci´on:
x(S) = X
i∈S
xi.
Po an o,
x(N) =
n
X
i=1
xi.
De inici´on 3.2.1. El conjun o de p eimpu aciones de un juego G= (N, )
es el siguien e conjun o de ec o es de dis ibuci´on de pagos:
PI(N, ) = {x= (x1, x2, .., xn)∈Rn:x(J) = (J)}.
Cabe pensa que ning´un jugado acep a ´a un pago in e io al que ob-
end ´ıa po s´ı mismo sin pa icipa en ninguna coalici´on. Su ge en onces el
concep o que se de ine a con inuaci´on.
De inici´on 3.2.2. El conjun o de impu aciones de un juego G= (N, )
es el siguien e conjun o de ec o es de pagos:
I(N, ) = {x= (x1, x2, ..., xn)∈Rn:x(N) = (n), xi≥ ({i}),pa a i= 1,2, .., n}
La condici´on de que pa a cada jugado i iene que cumpli se que xi≥
({i}) ecibe el nomb e de p incipio de acionalidad indi idual.
La siguien e p oposici´on nos da una condici´on necesa ia y su icien e pa a
que el conjun o de impu aciones de un juego sea no ac´ıo.
P oposici´on 3.2.3. Sea G= (N, )un juego en su o ma unci´on ca ac-
e ´ıs ica.
I(N, )6=∅ ⇔
n
X
i=1
({i})≤ (N)
JUEGOS COOPERATIVOS 51
De inici´on 3.2.4. Se dice que el juego G= (N, )es esencial si e i ica
que I(N, )6=∅.
El p incipio de acionalidad indi idual que se ecoge en el conjun o de
impu aciones puede ex ende se a odas las coaliciones median e el p incipio
de acionalidad coalicional. Llegamos en onces al concep o de co e de un
juego coope a i o.
De inici´on 3.2.5. El co e de un juego G= (N, )es el siguien e conjun o
de ec o es de pagos:
C(N, ) = {x= (x1, x2, .., xn)∈Rn:x(N) = (N), x(S)≥ (S),∀S∈P(N)}
A pa i de la de inici´on se e que el co e es un subconjun o del conjun o de
impu aciones. Se a a de las asignaciones que pod ´ıan cons i ui acue dos de
dis ibuci´on es ables, en el sen ido de que ning´un g upo de jugado es pod ´ıa
impugna unila e almen e ninguno de esos acue dos. En e ec o, ning´un g upo
consegui ´ıa po s´ı mismo m´as de lo que cualquie a de esos acue dos le pe mi e
ob ene .
P oposici´on 3.2.6. Sea G= (N, )un juego coope a i o. El conjun o C(N, )
es ce ado, aco ado y con exo.
Ejemplo 3.2.7. Una inca es ´a alo ada po su ac ual p opie a io en 350.000
eu os. Un emp esa io le o ece acondiciona la pa a su u ilizaci´on como pol´ıgono
indus ial, con lo que su alo de me cado alcanza ´ıa los 700.000 eu os. Una
emp esa cons uc o a le o ece u baniza la inca pa a su posible subdi isi´on
en pa celas des inadas a i iendas uni amilia es. Con es a u banizaci´on el
alo de la inca se ´ıa de 775.000 eu os.
Rep esen amos el juego en o ma coalicional. Sea
N={1,2,3}
58 Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
somb a a los que se alo an los ecu sos, es deci a los agen es se les alo an
sus ecu sos de acue do al ec o de p ecios somb a, que p oduce un ec o
Owen, siendo dicho ec o un epa o del n´ucleo del juego. La soluci´on que
p opo cionan los Conjun os de Owen no iene po que se ´unica. Si (DN)
iene soluci´on m´ul iple, odas las alo aciones duales que dichas soluciones
ep esen an son ´alidas pa a ob ene elemen os del conjun o de Owen. A´un en
el caso en que (DN) enga soluci´on ´unica, si hay holgu a posi i a en alguno de
los ecu sos, eliminando el ecu so sob an e ob enemos una soluci´on m´ul iple
dual y algunas de las alo aciones duales que dichas soluciones ep esen an
nos pe mi en ob ene elemen os en el conjun o de Owen del juego o iginal.
Ejemplo 3.3.4. Conside emos es agen es o jugado es que apo an al p o-
ceso p oduc i o es ecu sos necesa ios, seg´un se mues a a con inuaci´on:
B=



139 181 110
140 87 183
130 225 215




Se p oducen es bienes que se enden en el me cado ob eni´endose unos
bene icios uni a ios p= (2,5,5,4) . La ma iz ecnol´ogica del p oblema es:
A=



2 9 3,5
6 4 9
8 9 7




Veamos el juego. Si se o ma la g an coalici´on, el p oblema a esol e es:

JUEGOS COOPERATIVOS 59
m´ax 2,5x1+ 5x2+ 4x3
suje o a: 2x1+ 9x2+ 3,5x3≤430
6x1+ 4x2+ 9x3≤410
8x1+ 9x2+ 7x3≤570
x1, x2, x3≥0
Si esol emos el p oblema, u ilizando el so wa e LINDO ob enemos que
el esquema ´op imo de p oducci´on consis e en p oduci exclusi amen e de los
bienes segundo y e ce o, es deci , x∗(N) = (0,36,343,29,403).
La soluci´on ´op ima del p oblema dual (DN), es: u∗(N) = (0,4328,0,2761,0).
Resol iendo el p oblema (PN)hemos ob enido el alo de la unci´on ca ac-
e ´ıs ica pa a la g an coalici´on en el juego de la p oducci´on (N, ), siendo
dicho alo de (N) = 299,328. Resol iendo los p oblemas (PS)pa a ca-
da coalici´on, S, ob enemos odos los alo es de la unci´on ca ac e ´ıs ica del
juego:
S{1} {2} {3} {1,2} {1,3} {2,3}N
(S) 73,774 102,336 98,142 198,528 194,868 200,507 299,328
Ob engamos el epa o de Owen, alo ando los ecu sos apo ados po
cada jugado a los p ecios duales, u∗(N). Se ob iene el siguien e epa o:
Ow(N, )=(u∗(N)bi) =
= ((0,4328,0,2761,0)(139,140,130) ,(0,4328,0,2761,0)(181,87,225) ,
(0,4328,0,2761,0)(110,183,215) ) =
= (98,821,102,366,98,142).
A con inuaci´on se p esen a una abla que con iene los alo es de la unci´on
ca ac e ´ıs ica con las asignaciones del epa o de Owen, pudi´endose comp o-
ba que dicho epa o es del n´ucleo del juego. Ow(S) = Pi∈SOw(i), ep esen-
60 Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
a la asignaci´on que conjun amen e ob iene la coalici´on Scon el epa o de
Owen.
S{1} {2} {3} {1,2} {1,3} {2,3}N
(S) 73,774 102,336 98,142 198,528 194,868 200,507 299,328
Ow(S)98,821 102,366 98,142 201,19 196,96 200,507 299,328
En ´es e ejemplo la m´axima u ilidad que se ob iene de la coope aci´on de los
es agen es que pa icipan en el p oceso de p oducci´on es (N) = 299,3283.
Pe o aho a en ´es e caso sob an ecu sos. En conc e o sob an 37,0895 unida-
des del e ce ecu so. En es e caso los agen es pueden conside a la posibi-
lidad de apo a al p oceso de p oducci´on los ecu sos jus os, eliminando el
ecu so sob an e.
3.4. El Nucleolus
Hemos is o en la secci´on an e io que el co e es un concep o de soluci´on
que iene una di icul ad impo an e: en algunas ocasiones es un conjun o muy
g ande y en o as es un conjun o ac´ıo. El concep o de nucleolus p opone una
soluci´on que, siemp e que el conjun o de impu aciones sea no ac´ıo, supe a
la di icul ad an e io , pues es no ac´ıo y ´unico. Adem´as, pe enece al co e si
´es e es no ac´ıo. Se conside a un juego coope a i o (N, ).
Sea una dis ibuci´on de pagos x= (x1, x2, .., xn)∈Rne icien e en e los
jugado es, es deci , al que
n
X
i=1
xi= (N)
De inici´on 3.4.1. El exceso oqueja de una coalici´on Scon espec o a una
dis ibuci´on de pagos xes la di e encia en e el alo de la coalici´on Sy lo
JUEGOS COOPERATIVOS 61
que ecibe dicha coalici´on po la dis ibuci´on x. Es deci ,
e(S, x) = (S)−x(S) = (S)−X
i∈S
xi
Se a a de una medida del g ado de insa is acci´on de la coalici´on Scon
la dis ibuci´on x. Cuan o mayo es e(S, x) mayo es la insa is acci´on.
De inici´on 3.4.2. Pa a cada x∈I(N, ), se de ine el ec o de excesos como
el siguien e ec o θ(x), con 2ncomponen es:
θ(x) = (e(S, x))S∈P(N)= (θ1(x), θ2(x), .., θ2n(x))
en donde
θk(x)≥θk+1(x),∀k= 1,2, .., 2n−1.
Se conside a el o den lexicog ´a ico que de inimos o malmen e a con inua-
ci´on.
De inici´on 3.4.3. Sean x, x0∈I(N, x).
a)
θ(x)≤Lθ(x0)⇔θ1(x)< θ1(x0),
o bien, pa a j > 1,
θj(x)< θj(x0)yθi(x) = θi(x0), i = 1, ..., j −1.
b)
θ(x) =Lθ(x0)⇔θj(x) = θj(x0),∀j.
c)
θ(x)≤Lθ(x)<Lθ(x0)o bien θ(x) =Lθ(x0).
Po an o, dados dos ec o es de excesos, pa a compa a los seg´un el o den
lexicog ´a ico, se obse an s´olo las p ime as componen es; si la p ime a com-
ponen e de un ec o es meno que la p ime a componen e del o o ec o , el
62 Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
p ime ec o es meno que el segundo seg´un el o den lexicog ´a ico de inido.
Si los dos ec o es ienen iguales sus p ime as componen es se compa an sus
segundas componen es, siendo meno seg´un el o den lexicog ´a ico aquel ec-
o cuya segunda componen e sea meno . Si sus segundas componen es son
iguales, se compa an con sus e ce as componen es y as´ı sucesi amen e.
De inici´on 3.4.4. El nucleolus de un juego (N, ) es el conjun o N(N, )
de inido de la siguien e o ma:
N(N, ) = {x∈I(N, ) : θ(x)≥Lθ(y),∀y∈I(N, )}
Po an o, se puede deci que el nucleolus con iene aquellas dis ibuciones
de pagos que son impu aciones, y pa a las cuales se minimiza el mayo de los
g ados de insa is acci´on.
El siguien e eo ema, del que amos a da el enunciado sin la demos a-
ci´on, se debe a Schemeidle [15].
Teo ema 3.4.1. Sea (N, )un juego esencial (lo cual quie e deci que su
conjun o de impu aciones es no ac´ıo). En onces se e i ica que el nucleolus
exis e y es ´unico.
P oposici´on 3.4.5. Una condici´on su icien e pa a que el nucleolus exis a y
sea ´unico es que n
X
i=1
({i})≤ (N).
Demos aci´on. Supongamos que Pn
i=1 ({i})≤ (N). En onces po la P o-
posici´on 3.2.3 se iene que I(N, )6=∅de donde se deduce la exis encia y
unicidad del nucleolus po el Teo ema 3.4.1
A con inuaci´on, se dan dos de iniciones que se u iliza ´an pos e io men e
en una p oposici´on en que se p esen a ´an algunas p opiedades impo an es
del nucleolus, que nos pe mi i ´an calcula lo en algunos casos.
JUEGOS COOPERATIVOS 63
De inici´on 3.4.6. Se dice que dos jugado es i,json sim´e icos en un juego
(N, )si ealizan apo aciones equi alen es pa a cada coalici´on. Es deci , si
se cumple que
(S∪ {i}) = (S∪ {j}),∀S∈P(N), i, j /∈S
De inici´on 3.4.7. Se dice que el jugado ies un jugado pasi o en el juego
(N, ) si no apo a ning´un bene icio adicional al es o de los jugado es. Es
deci , si se cumple que
(S) = (S− {i}) + ({i}),pa a oda coalicion Scon i∈S
P oposici´on 3.4.8. Se conside a el juego (N, ). El nucleolus N(N, ) e-
i ica las siguien es p opiedades:
1. Si el co e del juego es no ac´ıo, en onces el ´unico elemen o del nucleolus
pe enece al co e.
2. Si el co e del juego es uni a io, en onces el co e coincide con el nucleolus.
3. Sea N(N, ) = (N1,N2, ..., Nn)el nucleolus. Si i, j son jugado es sim´e i-
cos, en onces Ni=Nj.
4. Sea N(N, )=(N1,N2, ..., Nn)el nucleolus. Si i∈Nes un jugado
pasi o, en onces Ni= ({i}).
El lec o in e esado puede e la demos aci´on en Joaqu´ın P´e ez y o os
[1]
M´e odo pa a calcula el nucleolus u ilizando p og amaci´on lineal
Pa a calcula el nucleolus x = (x1, x2, ..., xn) del juego (N, ), se esuel e

64 Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
el siguien e p og ama lineal:
m´ın α1
(S)−X
i∈S
xi≤αi,pa a S ∈P(N), S 6=∅, S 6=N
x∈I(N, )
Sea α∗
1el m´ınimo de ese p oblema. Si al m´ınimo se alcanza en un ´unico
pun o ˆx, en onces ˆxes el nucleolus y el c´alculo es ´a comple o. No malmen e
dicho m´ınimo no se alcanza ´a en un ´unico pun o xsino en un conjun o X1.
En al caso no malmen e hab ´a una amilia =1de coaliciones, al que pa a
odo S∈ =1yx∈X1es e(S, x) = α1. En onces se esue e el p og ama lineal
m´ın α2
(S)−X
i∈S
xi≤α2,pa a S ∈P(N)− =1, S 6=∅, S 6=N
x∈X1.
Si el m´ınimo se alcanza en un ´unico xse e mina, si no es as´ı se sigue
como an e io men e.
Ejemplo 3.4.9. En un depa amen o uni e si a io hay es in es igado es
consolidados que abajan en la misma linea de in es igaci´on. Se disponen a
p esen a solici udes pa a op a a inanciaci´on de p oyec os de in es igaci´on.
Han p egun ado a una pe sona de con ianza que iene oda la in o maci´on
sob e los c i e ios y candida os y les ha comen ado lo que es p e isible que
ocu a con la esoluci´on ace ca de las posibles solici udes, a la is a del his-
o ial y m´e i os de los candida os.
Si el doc o D´ıaz p esen a de mane a indi idual la solici ud, lo p e isible
es que le concedan ein a mil eu os, el doc o Ga c´ıa no consegui ´a nada si
JUEGOS COOPERATIVOS 65
a solo, mien as que la doc o a L´opez consegui ´ıa indi idualmen e cincuen a
mil eu os. Si los doc o es D´ıaz y Ga c´ıa p esen an un p oyec o conjun o ob-
end ´an una inanciaci´on de 50, D´ıaz y L´opez ob end ´ıan 80 y Ga c´ıa y L´opez
ob end ´ıan ambien 80 (siemp e en miles de eu os). Si los es in es igado es
solici an el p oyec o de mane a conjun a, p e isiblemen e ob end ´ıan 100(en
miles de eu os). Cada in es igado s´olo puede igu a en una solici ud.
La ep esen aci´on del juego en o ma coalicional es inmedia a en es e
caso:
N={1,2,3}
en donde el jugado 1 es el doc o D´ıaz, el jugado 2 es el doc o Ga c´ıa y la
jugado a 3 es la doc o a L´opez.
La unci´on ca ac e ´ıs ica es la unci´on
:P(N)→R, con
(∅)=0,
({1}) = 30, ({2}) = 0, ({3}) = 50,
({1,2}) = 50, ({1,3}) = 80, ({2,3}) = 80,
({1,2,3}) = 100
Calculemos el nucleolus. Pa a es e juego se e i ica que
({1}) + ({2}) + ({3}) = 80 < ({1,2,3}) = 100,
po lo que el conjun o de impu aciones es no ac´ıo y el nucleolus exis e y
es ´unico. Sea x= (x1, x2, x3)el nucleolus. Po pe enece el nucleolus, po
de inici´on, al conjun o de impu aciones se ienen que cumpli las siguien es
condiciones:
x1≥30, x2≥0, x3≥50, x1+x2+x3= 100
Los alo es de e(S, x)pa a S∈P(N), con S6=∅yS6=N, y x= (x1, x2, x3)
son los siguien es:
66 Op imizaci´on Lineal aplicada a Teo ´ıa de Juego
S{1} {2} {3} {1,2} {1,3} {2,3}
e(S, x) 30 −x1−x250 −x350 −x1−x280 −x1−x380 −x2−x3
Pa a calcula el nucleolus hay que esol e el siguien e p oblema:
m´ın
x1,x2,x3
{m´ax{30 −x1,−x2,50 −x3,50 −x1−x2,80 −x1−x3,80 −x2−x3}},
suje o a: x1≥30, x2≥0, x3≥50, x1+x2+x3= 100
Pa a esol e el an e io p oblema minimax se p ocede de la siguien e
o ma, se de ine:
m´ax{30 −x1,−x2,50 −x3,50 −x1−x2,80 −x1−x3,80 −x2−x3}=α1
Cada una de las unciones a las que a ec a la maximizaci´on an e io debe
se meno o igual a α1. El p oblema minimax o mulado es equi alen e al
siguien e p og ama lineal:
m´ın
x1,x2,x3,α1
α1
30 −x1≤α1
−x2≤α1
50 −x3≤α1
50 −x1−x2≤α1
80 −x1−x3≤α1
80 −x2−x3≤α1
x1≥30
x2≥0
x3≥50
x1+x2+x3= 100.
JUEGOS COOPERATIVOS 67
Resol emos el p oblema an e io con alg´un p og ama in o m´a ico pa a p o-
g amas lineales, y ob enemos que el p og ama iene soluci´on ´op ima que no es
´unica. Dicha soluci´on ´op ima se alcanza pa a α1= 10, x1= 30 yx2, x3 ales
que x2≥0, x3≥50 yx2+x3= 70. (En la soluci´on ´op ima del p og ama lineal
no se sa u a ninguna de las 5 p ime as es icciones y s´ı se sa u a la sex a
es icci´on.) Podemos asegu a que la p ime a componen e del nucleolus es
x1= 30 pe o a´un no podemos conc e a su segunda y e ce a componen e.
Pa a ello hay que esol e el siguien e p og ama:
m´ın
x1,x2,x3,α1
α2
−x2≤α2
50 −x3≤α2
20 −x2≤α2
50 −x3≤α2
x2≥0
x3≥50
x2+x3= 70
El p oblema iene soluci´on ´unica, que es x2= 20, x3= 50, α2= 0. Po
an o, el nucleolus del juego es
N= (30,20,50).