T abajo Fin de G ado
El p oblema de la asignaci´on de
cos es en p oblemas de
op imizaci´on.
Au o : Jos´e Ram´on S´anchez Leo
Tu o : Jus o Pue o Albandoz
Uni e sidad de Se illa
Facul ad de Ma em´a icas
Junio 2017
Abs ac
The p oblem o cos alloca ion in op imiza ion p oblems can be sol ed by game
heo y, in pa icula wi h coope a i e games. Ac ually, in his wo k we will y
o gi e condi ions so ha he co e o a coope a i e games is nonemp y, since i
i is nonemp y we will ha e a solu ion.
´
Indice gene al
1. In oducci´on 7
2. Juegos Coope a i os 11
2.1. Concep os In oducc o ios . . . . . . . . . . . . . . . . . . . . . . 12
2.2. Co e.................................. 17
2.3. Colecciones equilab adas . . . . . . . . . . . . . . . . . . . . . . . 20
3. Juego de Asignaci´on 29
3.1. Ma chingMa ke s .......................... 33
4. Juego de P oducci´on Lineal 37
4.1. Aplicaci´on con CPLEX . . . . . . . . . . . . . . . . . . . . . . . 41
5. Juegos de Localizaci´on 47
5.1. P oblema Con inuo de Localizaci´on . . . . . . . . . . . . . . . . . 48
5.2. Juego de localizaci´on minimax . . . . . . . . . . . . . . . . . . . 54
5.3. Juego de localizaci´on de Webe , con cos e ijo . . . . . . . . . . . 57
5.4. Juego de localizaci´on de Webe , con cos e ijo a iable . . . . . . 59
6. Juegos de Radio y Di´ame o 65
6.1. Espacios m´e icos de ed . . . . . . . . . . . . . . . . . . . . . . . 70
6.1.1. G a os medianos . . . . . . . . . . . . . . . . . . . . . . . 74
6.1.2. MSTGyMRLG ....................... 75
6.2. Espacios m´e icos disc e os . . . . . . . . . . . . . . . . . . . . . 76
6.3. lpespacio m´e ico sobe Rd...................... 77
6.3.1. Espacios eucl´ıdeos . . . . . . . . . . . . . . . . . . . . . . 82
5

´
Indice gene al
7. Conclusiones 85
A. Aplicaci´on del Juego de P oducci´on Lineal 89
6
Cap´ı ulo 1
In oducci´on
Vamos a analiza el p oblema de asignaci´on de cos es median e la eo ´ıa de
juegos. Es necesa io obse a que dicha eo ´ıa iene dos en oques b´asicos en el
an´alisis, de lo que denomina emos, un juego: coope a i o y no coope a i o.
An es de analiza las di e encias en e ambos ipos de juegos, con ex ualice-
mos his ´o icamen e la eo ´ıa de juegos. Los pos ulados b´asicos de la eo ´ıa de
juegos apa ecen du an e las d´ecadas de los 40 y 50 de la mano de Johan Von
Neumann, Oska Mo gens e n y John Nash. Es a eo ´ıa apa ece con idea de
esol e con lic os me amen e econ´omicos, cuando los p incipales economis as
la conocie on cambia on su o ma de oma sus decisiones. Es o se debe a que
Nash, Neumann y Mo gens e n concluyen que: el in e ´es indi idual, el ego´ısmo
y la acionalidad a la ho a de oma decisiones, conducen a los se es humanos a
una si uaci´on no ´op ima; y, es o a en con a de lo que plan eaba la econom´ıa
cl´asica, dada po Adam Smi h. Los ex os m´as impo an es que apa ecie on
en onces ue on [23] y [19].
La di e encia p incipal en e un juego coope a i o y uno no coope a i o
es que en el coope a i o los jugado es deciden en en a se a una si uaci´on de
o ma conjun a y, si es posible, oma una pos u a an e es a pa a as´ı minimiza
cos es, o maximiza bene icios; luego compa en in o maci´on y las p e e encias
de cada uno con el es o. Sin emba go, en los juegos no coope a i os cada jugado
a a de soluciona una si uaci´on po su cuen a, sin compa i necesa iamen e
in o maci´on con el es o.
7
In oducci´on
En los juegos no coope a i os es necesa io hace dos dis inciones b´asicas en e
juegos es ´a icos y juegos din´amicos. En los juegos es ´a icos los jugado es oman
sus decisiones de o ma simul ´anea (es deci , cada jugado oma su decisi´on sin
conoce la decisi´on del es o), mien as que en los din´amicos puede da se el caso
de que un jugado conozca ya las decisiones de o o an es de decidi .
En los juegos coope a i os se analizan las posibilidades de que algunos o
odos los agen es, jugado es, lleguen a un acue do sob e que decisiones a a
oma cada uno.
Den o de la eo ´ıa de juegos, los juegos coope a i os son la he amien a
m´as con enien e pa a soluciona p oblemas de asignaci´on de cos es, ya que su
obje i o es epa i cos es o bene icios, dependiendo de la si uaci´on, en e a ios
agen es.
Ya que nos amos a cen a en los juegos coope a i os, amos a analiza su
con ex o his ´o ico. Ya en [23], en 1944, apa ece el concep o de juego coope a i o.
En cua o a ´ıculos en e 1950 y 1953 John Nash hizo con ibuciones impo an-
es an o a la eo ´ıa de juegos no coope a i a. Nash demos ´o la exis encia de
un equilib io es a ´egico pa a los juegos no coope a i os -el equilib io de Nash-
y p opuso el ”p og ama de Nash”, en el que sugi i´o ace ca se al es udio de los
juegos coope a i os a a ´es de su educci´on a o ma no coope a i a. En 1963,
O. N. Bonda e a es ableci´o que pa a un juego TU su co e es no ac´ıo si es
equilib ado, eas´e [1]. As´ı se ob u o una condici´on necesa ia pa a que el co e,
de un juego coope a i o, ue a no ac´ıo. Es o es el conocido como Teo ema de
Bonda e a-Shapley que enuncia emos y demos a emos en el Cap´ı ulo 2.
En los juegos coope a i os se pa e de que es posible que algunos jugado es
puedan llega a acue dos inculan es, po lo que se a a de es udia los esul a-
dos que puede ob ene cada una de las coaliciones de jugado es que se puedan
o ma . Se a a, po an o de es udia c´omo pueden ac ua las dis in as po-
sibles coaliciones de jugado es, in e es´andonos los compo amien os colec i os
y sin que haga al a de ene se en las acciones indi iduales de cada uno de los
miemb os de una coalici´on.
En el Cap´ı ulo 2, de es e abajo in de g ado, in oducimos las p ime as
ideas y concep os necesa ios pa a a a juegos coope a i os, dichos concep os
son necesa ios pa a el es o de cap´ı ulos. El obje i o p incipal es in oduci el
8
In oducci´on
concep o de co e, como soluci´on de un juego coope a i o, y da una condici´on
necesa ia y su icien e pa a que sea no ac´ıo.
Du an e el Cap´ı ulo 3, analizamos uno de los ipos de juegos m´as impo an es
pa a la eo ´ıa de juegos: el Juego de Asignaci´on. En pocas palab as pod ´ıamos
deci que se a a de una si uaci´on de epa o, po ejemplo de bienes o a eas,
en e usua ios que demandan dichos se icios. El esul ado p incipal de es e
cap´ı ulo es que el co e de es e juego es no ac´ıo. Adem´as a a emos si uaciones
eales que ue on esuel as median e el es udio de ”Ma ching Ma ke s”, que es a
muy elacionado con el Juego de Asignaci´on. Es o ´ul imo dio luga a un p emio
Nobel.
Seguidamen e en el Cap´ı ulo 4, desa ollamos el Juego de P oducci´on Lineal.
Se a a de un juego en el que di e sos agen es a an de usa de o ma conjun a
sus bienes pa a p oduci de e minados p oduc os que se puedan ende a un
p ecio de me cado ijo. De nue o, el esul ado p incipal es el eo ema que p ueba
que el co e de es e juego es no ac´ıo. Tambi´en, hemos esuel o una si uaci´on de
p oducci´on lineal usando CPLEX median e NEOS-SERVER, el c´odigo se puede
consul a en el Ap´endice A.
A con inuaci´on, en el Cap´ı ulo 5, a amos los Juegos de Localizaci´on. Al
comienzo damos las ideas p incipales de es os juegos, in oduciendo el concep-
o de si uaci´on de localizaci´on. Despu´es, a amos dis in os casos conc e os de
juegos de localizaci´on: el minimax, el de Webe con cos e ijo y el de Webe con
cos e ijo a iable. Como an es, los esul ados m´as impo an es son aquellos que
dan condiciones su icien es pa a que el co e de es os juegos sea no ac´ıo. Aqu´ı
encon a emos una a iedad de ejemplos de cada si uaci´on.
T as es o, en el Cap´ı ulo 6, es udiamos un caso simila a los del cap´ı ulo an-
e io pe o que se de inen de una o ma lige amen e dis in a, e emos los Juegos
de Radio y Di´ame o. En es e cap´ı ulo es udia emos la exis encia de pun os en
el co e y la exis encia de ep esen aciones polinomiales de es e, cen ´andonos en
edes. El juego que es udia emos, p incipalmen e, se ´a el juego de localizaci´on
de adio m´ınimo. De nue o, hemos a˜nadido una g an a iedad de ejemplos de
las dis in as si uaciones.
Pa a e mina , en el ´ul imo cap´ı ulo se incluyen las conclusiones de es e
T abajo Fin de G ado.
9
Cap´ı ulo 2. Juegos Coope a i os
n−2. Si el juego es de suma cons an e, enemos una condici´on adicional.
( ) (n−S) = (N)− (S),∀S⊆N. (2.10)
Con es a nue a condici´on nues o conjun o iene dimensi´on 2n−1−n−1. Po lo
an o, es cla o que la dimensi´on del conjun o de juegos de npe sonas en suma
cons an e es la misma que la del conjun o de juegos de (n−1) pe sonas. De
hecho son conjun os cong uen es.
En pa icula , si ues un juego de (n−1) pe sonas no malizado (0,1), puede
se ampliado a un juego de suma cons an e de npe sonas median e la adicci´on
de un nue o jugado n, de inimos:
(S) = 


u(S) si n6∈ S
1−u(N−S) si x∈S.
Es ´acil comp oba que es un juego de suma cons an e.
De inamos aho a dos ipos de juegos especiales que son de nues o in e ´es:
De inici´on 2.11. Un juego se dice sim´e ico si (S) depende solo del n´ume o
de elemen os de S.
De inici´on 2.12. Un juego no malizado en no ma (0,1) se dice simple si, pa a
cada S⊆N, se iene que, o bien, (S) = 0, o bien, (S) = 1. Un juego es simple
si su no malizaci´on en (0,1) es simple.
Esencialmen e, un juego simple es aquel en el que cualquie coalici´on o bien
gana ( alo 1) o pie de ( alo 0), sin posibilidad de oma alo es in e medios.
Como ales, los juegos simples son aplicables a ciencias pol´ı icas, como juegos
de o aciones en elecciones.
En e los juegos simples, dis inguimos un clase especial: los juegos de mayo
peso:
De inici´on 2.13. Sea (p1, p2, . . . , pn) un ec o no nega i o, y sea qsa is acien-
do:
0< q ≤
n
X
i=1
pi.
16

Cap´ı ulo 2. Juegos Coope a i os
En onces, el juego de mayo peso [q;p1, p2, . . . , pn] es el juego simple de inido
po
(S) = 


0 si Pi∈Spi< q
1 si Pi∈Spi≥q.
2.2. Co e
Aho a amos a p ocede al an´alisis de juegos en ´e minos de elaci´on de
dominio. Comenzamos, ob iamen e, es udiando las impu aciones no dominadas.
De inici´on 2.14. El conjun o de odas las impu aciones no dominadas pa a un
juego es llamado Co e. Lo deno a emos como C( ).
Teo ema 2.3. El co e del juego es el conjun o de odos los ec o es x sa is-
aciendo:
(a)X
i∈S
xi≥ (S),∀S⊆N
(b)X
i∈N
xi= (N).
(2.11)
Lo podemos esc ibi en o ma de conjun o:
Co e( ) = C( ) = {x∈RN
+:x(N) = (N); x(S)≥ (S),∀S⊆N}(2.12)
Demos aci´on. Si S={i}, la p ime a condici´on se educe a xi≥ {i}.
Supongamos que xsa is ace ambas condiciones, y que yi> xi,∀i∈S. Pe o
es o, jun o con (a) , signi ica que
X
i∈S
yi> (S),
luego no es posible que xSy. Po lo an o, x∈C( ).
Po el con a io, supongamos que yno sa is ace las condiciones. Si no sa is-
ace la segunda ni siquie a es una impu aci´on y po lo an o no es a en C( ).
Supongamos, en onces que hay alg´un S⊆Nno ac´ıo al que:
X
i∈S
yi= (S)−ε,
17
Cap´ı ulo 2. Juegos Coope a i os
con ε > 0. Sea:
α= (N)− (S)−X
i∈N−S
xi= ({i})
Es ´acil e , po supe adi i idad, que α≥0. Finalmen e, sea s el ca dinal de S.
Aho a de inimos z como:
zi=


yi+ε
s, i ∈S
({i}) + α
n−s, i 6∈ S.
Se e ´acilmen e que zes una impu aci´on y, adem´as zSy. Po lo an o,
y6∈ C( ). 
Obse aci´on 2.1. M´as adelan e, en el Juego de Localizaci´on el co e se ´a el de
un juego de cos e (N, c) que es el siguien e:
Co e( ) = C( ) = {x∈RN
+:x(N) = (N); x(S)≤ (S),∀S⊆N}(2.13)
El Teo ema 2.3 mues a que C( ) es un conjun o con exo ce ado (ya que
se de ine con desigualdades no es ic as). Es o es muy in e esan e, ya que la
eo ´ıa econ´omica cl´asica suele da el co e como ”soluci´on” a la mayo ´ıa de los
p oblemas de eo ´ıa de juegos.
Gene almen e, po supues o, el Co e puede ene m´as de un pun o. Es o
no es una g an des en aja; simplemen e signi ica que m´as de un esul ado es
es able. La g an di icul ad con el co e es que puede se ac´ıo.
Teo ema 2.4. Si es un juego esencial de suma cons an e, en onces C( ) = ∅.
Demos aci´on. Supongamos x∈C( ). Pa a cualquie i∈N, sabemos que
X
j∈N−{i}
xj≥ (N−{i})
pe o, al se un juego de suma cons an e:
(N−{i}) = (N)− ({i})
y, ya que x es una impu aci´on, enemos xi≤ ({i}). Dado que es esencial,
18
Cap´ı ulo 2. Juegos Coope a i os
enemos
Xxi≤X ({i})< (N).
Pe o es o signi ica que x6∈ E( ). La con adicci´on implica que C( ) = ∅.
Ejemplo 2.1. Aho a analizamos el caso pa icula de los llamados Juegos Sim-
ples. Vamos a comp oba que el co e de es os juegos no malizados (0,1) es no
ac´ıo en cie as condiciones.
Sea un juego simple no malizado (0,1). Decimos que el jugado ies un
jugado e ado si
(N−{i}) = 0
donde, como hemos obse ado an es, Nes el conjun o de odos los jugado es.
Supongamos que no iene jugado es e ados. En onces, pa a cada i∈N,
enemos (N− {i}) = 1. Pa a que la impu aci´on xes e en el co e, iene que
e i ica :
X
j∈N
xj= (N)=1,
X
j6=i
xj≥ (N−{i}) = 1
Po lo an o, xi= 0,∀i, y en onces xno puede se una impu aci´on. Es a con-
adicci´on p ueba que Co e( ) = C( ) = ∅.
Supongamos aho a que iene uno o m´as jugado es e ados; sea Sel con-
jun o de odos ellos. Sea x al que
X
i∈S
xi= 1,
xi≥0 pa a odo i∈S,
xi= 0 pa a i6∈ S.
Aho a, si Tes una coalici´on ganado a, enemos que S⊂T, en onces
X
i∈T
xi≥X
i∈S
xi=1= (T),
y podemos comp oba que x∈C( ) = Co e( ). Po lo an o, C( )6=∅, y
concluimos que, pa a un juego simple , el co e es no ac´ıo si y s´olo si hay al
menos un jugado e ado.
19
Cap´ı ulo 2. Juegos Coope a i os
2.3. Colecciones equilab adas
El Teo ema 2.4 nos p opo ciona un caso en el que el co e es ac´ıo. Es o
pa ece de in e ´es pa a de e mina , de o ma m´as gene al, aquellos juegos que
ienen co e no ac´ıo. Es ´acil comp oba que, pa a cualquie n, el conjun o
de juegos de npe sonas con co e no ac´ıo (pensado como un subconjun o del
espacio eucl´ıdeo de dimensi´on 2n−1) es un cono con exo. Supongamos que
enemos dos juegos ywcon co e no ac´ıo, con x∈C( ), y ∈C(w). Es ´acil
comp oba que, pa a dos escala es no nega i os ys,
x +sy ∈C( +sw).
Con el in de ca ac e iza es e cono con exo, obse emos que C( ) = ∅si y
s´olo si el p oblema de p og amaci´on lineal
(P) m´ın
n
X
i=1
xi=z
s.a.: X
i∈S
xi≥ (S) pa a oda S⊂N.
(2.14)
iene un m´ınimo z∗≤ (N). Pa a, en al caso, cualquie x∗m´ınimo es a en el
co e. A la in e sa, si x∈C( ), en onces xsa is ace la condici´on de (2.14) y,
adem´as, X
i∈N
xi= (N). Po lo an o, el minimo debe se z∗≤ (N).
Aho a conside emos el dual del p oblema (P):
(P∗) m´ax X
S⊂N
yS (S) = q
s.a.: X
i∈S⊂N
yS= 1 pa a odo i∈N,
yS≥0 pa a oda S⊂N.
(2.15)
Ambos p oblemas de p og amaci´on lineal (P) y (P∗) son ac ibles, y en onces
el m´ınimo, z∗, iene que se igual al m´aximo, q∗. Po lo an o, C( )6=∅si y s´olo
si el m´aximo q∗≤ (N). Es o lo podemos esc ibi con las siguien es palab as,
Teo ema 2.5. Una condici´on necesa ia y su icien e pa a que un juego enga
co e no ac´ıo, C( )6=∅, es que, pa a cada ec o no nega i o (yS)S⊂Nque
20
Cap´ı ulo 2. Juegos Coope a i os
e i ique la p ime a condici´on de (2.15), engamos
X
S⊂N
yS (S)≤ (N).(2.16)
En es e o ma o, el Teo ema 2.5 no es una he amien a muy e icien e. Ya que
necesi a esol e el p og ama lineal (P), que no es m´as simple que su dual. Sin
emba go, esul a que podemos ca ac e iza los pun os ex emos del p og ama
dual (P∗) con un concep o bas an e ino: que son las colecciones equilib adas.
De inici´on 2.15. Sea C={S1, S2, . . . , Sm}colecci´on no ac´ıa de subconjun os
de N={1,2, . . . , n}. Di emos que Ces N-equilib ado (o simplemen e, equili-
b ado cuando no haya con usi´on espec o a N) si exis en n´ume os posi i os
y1, y2, . . . , ym ales que, pa a cada i∈N,
X
j;i∈Sj
yj= 1.
En onces y= (y1, y2, . . . , ym) es el ec o de equilib io pa a C; los yjson lla-
mados coe icien es de equilib io.
Ejemplo 2.2. La colecci´on {N}es cla amen e equilib ada y, de hecho, cualquie
pa ici´on de N(cualquie colecci´on de conjun os no ac´ıos disjun os cuya uni´on
es N) es equilib ada. Los coe icien es de equilib io aqu´ı son odos 1.
Ejemplo 2.3. Sea N={1,2,3}. En onces la colecci´on
C={{1,2},{1,3},{2,3}}
es equilib ada con coe icien es de equilib io {1
2,1
2,1
2}. De o ma gene al, pa a
cualquie N, la colecci´on de odos los conjun os n
scon selemen os es equili-
b ada, con odos los coe icien es de equilib io igual a n−1
s−1−1.
Ejemplo 2.4. Sea N={1,2,3,4}. En onces
C={{1,2},{1,3},{1,4},{2,3,4}}
es equilib ada, con ec o de equilib io y= (1
3,1
3,1
3,2
3).
21

Cap´ı ulo 2. Juegos Coope a i os
Esencialmen e, una colecci´on equilib ada es una pa ici´on gene alizada (co-
mo hemos is o en el Ejemplo 2.2). Hay, po supues o, muchas mas colecciones
N-equilib adas que pa iciones de N. La siguien e p opiedad de las colecciones
equilib adas es de in e ´es.
Teo ema 2.6. La uni´on de colecciones equilib adas es equilib ada.
Demos aci´on. Sean C={S1, . . . , Sm}yD{T1, . . . , Tk}colecciones equilib a-
das, con ec o es de equilib io espec i os (y1, . . . , ym)y(z1, . . . , zk). En onces,
C∪D={R1, . . . , Rq}
donde q≤m+k. Pa a cada , 0 < <1, de inimos:
wj=








ylsi Rj=Sl∈C−D
(1 − )zpsi Rj=Tp∈D−C
yl+ (1 − )zpsi Rj=Sl=Tp∈C∪D
Es ´acil comp oba que (w1, . . . , wq) es un ec o de equilib io pa a C∪D. Po lo
an o, la uni´on de dos colecciones equilib adas es equilib ada, y, po inducci´on,
la uni´on de colecciones equilib adas es equilib ada. 
Lema 2.1. Sean CyDcolecciones equilib adas ales que: C⊂Dcon C6=D.
En onces exis e una colecci´on equilib ada B al que:
B∪C=D,
con B6=D. Adem´as, el ec o de equilib io Dno es ´unico.
Demos aci´on. Sean:
C={S1, S2, . . . , Sk},
D={S1, S2, . . . , Sk, . . . , Sm}, m > k,
(2.17)
que ienen como ec o es de equilib io (y1, . . . , yk) y (z1, . . . , zm), espec i a-
men e. Pa a > 0, de inimos:
wj= (1 + )zj− yj,j= 1, . . . , k,
wj= (1 + )zj,j=k+ 1, . . . , m.
(2.18)
22
Cap´ı ulo 2. Juegos Coope a i os
Pa a > 0 peque˜no, emos que odos wj>0. Adem´as, pa a i∈N,
X
j;i∈Sj∈D
wj= (1 + )X
j;i∈Sj∈D
zj− X
j;i∈Sj∈C
yj= 1,
y en onces wes un ec o equilib ado pa a D. Pues o que wj> zjpa a k+ 1 ≤
j≤m, emos que zno es ´unico.
Aho a, debe habe alg´un j, 1 ≤j≤k, al que yj> zj, cuando no sea as´ı,
pa a cualquie i∈Sk+1, end ´ıamos
1 = X
i∈Sj∈C
yj≤X
i∈Sj∈C
zj<X
i∈Sj∈D
zj= 1,
lo cual es una con adicci´on. Es ablecemos, en onces,
= m´ın zj
yj−zj
:yj> zj.
Sea C0={Sj|Sj∈C,(1 + )zj= yj},y el conjun o: B=D−C0.Cla amen e,
C0es una subcolecci´on no ac´ıa de C, y en onces enemos:
B6=D,B∪C=D.
Adem´as, wj>0,∀Sj∈B, y es o es ´acil de comp oba (pa a es e alo de )w
es un ec o de equilib io de la colecci´on B. Po lo an o, Bes como deseamos.

A con inuaci´on, de inimos el concep o de colecci´on m´ınima equilib ada como
una colecci´on equilib ada que no iene subcolecciones p opias equilib adas.
Teo ema 2.7. Cualquie colecci´on equilib ada es uni´on de colecciones m´ınimas
equilib adas.
Demos aci´on. Po inducci´on sob e m(el n´ume o de conjun os en la colecci´on).
El eo ema se e i ica cla amen e cuando m= 1, la ´unica colecci´on equilib ada
con un conjun o es {N}, que e iden emen e es cie o.
Supongamos, en onces, que es o es cie o pa a odas las colecciones con m−1
o menos elemen os. Sea Duna colecci´on equilib ada con melemen os.
23
Cap´ı ulo 2. Juegos Coope a i os
Si Des en s´ı misma m´ınima, en onces es cla amen e uni´on de colecciones
m´ınimas equilib adas.
Si Dno es m´ınima, en onces enemos que p oba que iene una subcolecci´on
p opia equilib ada, C, y, po el lema an e io , exis i ´a o a subcolecci´on p opia
equilib ada, B, al que B∪C=D. Como ByCson subcolecciones p opias,
cada uno end ´a m−1 o menos elemen os, y po lo an o cada uno se puede
exp esa como uni´on de colecciones m´ınimas equilib adas. Pe o en onces Des
ambi´en union de colecciones m´ınimas equilib adas. 
Aho a, amos a demos a un esul ado ´ecnico ela i o a la suma de los
coe icien es de equilib io de la amilia de coaliciones equilib adas. Reco demos
que una colecci´on de coaliciones, B⊂2N, es equilib ada si y s´olo si exis e un
conjun o de coe icien es eales posi i os {γS/S ∈B}(coe icien es de equilib io)
sa is aciendo que PS:ai∈SγS= 1 pa a cada ai∈N. El conjun o de los co-
e icien es de equilib io asociados a una colecci´on equilib ada no iene po que
se ´unico. Sin emba go, cada colecci´on equilib ada m´ınima de coaliciones (en el
sen ido de que no con iene o a ecolecci´on equilib ada) iene un ´unico conjun o
de coe icien es de equilib io (como ya hemos p obado en el Teo ema 2.8). Tam-
bi´en hemos p obado an e io men e que un juego (N,c) iene co e no ac´ıo si y
s´olo si pa a cada coalici´on m´ınima equilib ada B, con coe icien es de equilib io
{γ/S ∈B}, se e i ica que PS∈BγSc(S)≥c(N) (Teo ema de Bonda e a-
Shapley, obse emos que la desigualdad es la con a ia al se un juego de cos e).
Obse emos que solo la colecci´on equilib ada con coe icien es de equilib io
que suman 1 es B= 1. En e ec o, pa a cada colecci´on equilib ada By cada
ai∈N, PS:ai∈SγS= 1; si, adem´as, PS∈BγS= 1 en onces, pa a cada S∈B
y cada ai∈N, ai∈S. Po lo an o, S=N, y po lo an o B={N}. Di emos
que B={N}es la colecci´on i ial.
El siguien e esul ado aco a la suma de los coe icien es de equilib io pa a
cualquie colecci´on no i ial equilib ada.
Lema 2.2. Sea Buna colecci´on no i ial equilib ada con coe icien es de equi-
lib io {yS:S∈B}.En onces,
n
n−1≤X
S∈B
ys≤n.
24
Cap´ı ulo 2. Juegos Coope a i os
Demos aci´on. Conside emos el siguien e p oblema de p og amaci´on lineal (1):
m´ın X
S∈2N {N}
yS
s. a.: X
S∈2N {N}:ai∈S
yS= 1,
ys≥0,∀S∈2n {N}.
La soluci´on de es e p oblema es un conjun o de coe icien es equilib ados de
un una colecci´on no i ial con suma m´ınima (B={S∈2N:yS>0}). Deno e-
mos la coalici´on N {aj}={a1, . . . , aj−1, aj+1, . . . , an}po −j. Conside emos
la base Bdel p oblema (1) cuyas columnas co esponden a y−1, y−2, . . . , y−n.
En es e p oblema la ma iz de B, su in e sa B−1y la ans o maci´on po el
lado de echo B−1bson:
B=








−(n−2) 1 . . . 1
1−(n−2) . . . 1
.
.
..
.
.....
.
.
1 1 . . . −(n−2)








,
B−1=1
n−1








−(n−2) 1 . . . 1
1−(n−2) . . . 1
.
.
..
.
.....
.
.
1 1 . . . −(n−2)








,
B−1b=1
n−1,..., 1
n−1
.
Los cos es educidos pa a cualquie coalici´on Scon 1 ≤k≤n−1 jugado es
son:
cbB−1aS−cS=k
n−1−1<0 sii k < n −1,
cbB−1aS−cS=n−1
n−1−1 = 0 sii k=n−1.
En onces B es una base asociada con una soluci´on ´op ima de (1), que p ueba
el l´ımi e in e io . La p ueba pa a el l´ımi e supe io es di ec a y se sigue oman-
do la colecci´on cuyos elemen os son odos los conjun os de ama˜no uno con
coe icien es iguales a 1. 
Teo ema 2.8. Una colecci´on equilib ada iene un ´unico ec o de equilib io si
25
Cap´ı ulo 3. Juego de Asignaci´on
y en onces odo z0
j≥0. Po lo an o, (y0, z0) es una impu aci´on del juego .
Veamos que pe enece a C( ).
Pa a cualquie S, enemos:
(S) = ci1j1+... +ciqjq,
donde i1, ..., iq, j1, ..., jqson dis in os miemb os de S. En onces
X
i∈S
y0
i+X
m+j∈S
z0
j≥y0
i1+... +y0
iq+z0
i1+... +z0
iq≥
≥ci1j1+... +ciqjq= (S).
y concluimos que (y0;z0)∈C( ).
En algunos casos, (y0;z0) se ´a la ´unica impu aci´on del co e. M´as habi ual-
men e la impu aci´on no se ´a ´unica. De hecho, cualquie ec o m´ınimo (y∗;z∗)
con componen es no nega i as es a ´a si uado en el co e. Lo usual es que la asig-
naci´on ´op ima de endedo es a comp ado es, dada po el p oblema p incipal, es
´unica; sin emba go, el p ecio de me cado, dado po el dual, no es ´unico.
Ejemplo 3.1. Un ejemplo de un juego de asignaci´on.
Un endedo (Juan, j1) iene un coche sin alo pa a ´el, a menos que pueda
ende lo. Dos comp ado as (Roc´ıo, j2, y Ma ´ıa, j3) alo an el obje o en 90e
y en 100e espec i amen e. Si Juan ende el coche a Roc´ıo al p ecio de x, ´el
ob end ´a un bene icio de x, mien as que el bene icio de Roc´ıo se ´a de 90−x. El
bene icio o al de la coalici´on {j1, j2}es en onces 90e. Pa a lo coalici´on {j1, j3}
es simila con un bene icio de 100e. Po lo an o,
({j1, j2}) = 90,
({j1, j3}) = 100.
(3.2)
Po o o lado, un jugado solo, o los dos comp ado es, no ob iene ning´un
bene icio. Po lo an o,
({j1}) = ({j2, j3})=0.
Po ´ul imo, la coalici´on de los es jugado es puede no hace nada mejo que
32

Cap´ı ulo 3. Juego de Asignaci´on
asigna el coche a Ma ´ıa, j3. Po lo an o,
({j1, j2, j3}) = 100.
Po odo es o el co e es ´a o mado po odos los ec o es (x1, x2, x3) que
e i ican:
x1+x2≥90,
x1+x3≥100,
x1+x2+x3= 100,
xi≥0.
Es o implica que x1≥90, x2= 0, x1+x3= 100, x3≥0.Po lo an o,
Co e( ) = C( ) = {( , 0,100 − )|90 ≤ ≤100}.(3.3)
Es o quie e deci que Ma ´ıa, j3, comp a ´a el coche al p ecio de al menos
90e. Roc´ıo, j2, iene un p ecio ue a de me cado - a pa i que la ”puja” supe e
el p ecio de 90e.
Podemos conclui que los Juegos de Asignaci´on ienen siemp e co e no ac´ıo,
luego pod emos da alguna soluci´on al p oblema. Aunque en muchas si uaciones
end emos m´as de una impu aci´on en el co e, luego end emos m´as de una
posible soluci´on.
3.1. Ma ching Ma ke s
Encon amos una si uaci´on muy simila a la an e io en ”Ma ching Ma -
ke s”, la g an di e encia consis e en que aho a el cos e no puede ajus a se pa a
asigna ecu sos, ya que en muchos casos eales el cos e se desca a po mo i-
os ´e icos. Algunos de es os casos son asigna es udian es a colegios o ins i u os,
asigna ´o ganos a pacien es en e mos, m´edicos a hosp iales y o os muchos casos.
Como cu iosidad debemos se˜nala que Al in E. Ro h ob u o su p emio Nobel
de econom´ıa en 2012 po sus con ibuciones a ”Ma ching Ma ke s”.
El algo i mo de Shapley-Gale, desc i o en 1962, pa a asigna pa ejas en e
homb es y muje es, es la p ime a ez en la que apa ecen es e ipo de p oble-
mas. Analiza on, desde un pun o de is a abs ac o, como debe ´ıan asigna se
33
Cap´ı ulo 3. Juego de Asignaci´on
diez homb es y diez muje es, espe ando sus p e e encias. Con el algo i mo de
”acep aci´on en di e ido” (”de e ed accep ance”) die on con una co esponden-
cia es able. El algo i mo puede con igu a se de dos mane as al e na i as: o los
homb es p oponen a las muje es, o las muje es p oponen a los homb es. Si son
las muje es las que p oponen a los homb es, el p oceso comienza con cada muje
p oponi´endose al homb e que m´as le gus a. A con inuaci´on, cada homb e mi a
las di e en es p opues as que ha ecibido (si exis en), e iene la que conside a
como la mejo p opues a y echaza el es o. Las muje es que ue on echazadas
en la p ime a onda se p oponen en onces a sus segundas mejo es elecciones,
mien as que los homb es uel en a man ene su muje p opues a. Es o con i-
nua has a que ninguna muje quie a hace m´as p opues as. Cuando cada uno
de los homb es acep a la p opues a que iene el p oceso inaliza. Gale y Shapley
demos a on que es e algo i mo siemp e conduce a una si uaci´on es able. Es im-
po an e conoce la es uc u a dis ibu i a del algo i mo, ya que si el de echo a
p opone se le da a las muje es, como hemos desc i o an es, el esul ado es mejo
pa a los homb es y, al con a io, si el de echo a p opone es de los homb es.
Al in E. Ro h es udi´o el p oblema de asigna de m´edicos eci´en g aduados
a hospi ales. En Es ado Unidos cuando un es udian e de medicina inaliza sus
es udios, en g an pa e, pasa a abaja de esiden e en un Hospi al. Se pe ca ´o
de que el algo i mo usado po ”Na ional Residen Ma ching P og am (NRMP)”,
pa a asigna eci´en licenciados a hospi ales, es aba muy elacionado con el algo-
i mo de Shapley-Gale. A pesa de unciona co ec amen e, y se usado m´as all´a
de Es ados Unidos, el NRMP no uncionaba a la pe ecci´on. Uno de los p oble-
mas ue que el n´ume o de muje es es udian es c eci´o y, as´ı, el n´ume o de pa ejas
eci´en g aduadas que que ´ıan hace la esidencia de o ma conjun a. Como ya
hemos comen ado an e io men e, el lado que p opone (en es e caso los hospi-
ales) es sis em´a icamen e a o ecido, es o p o oco muchas c ´ı icas. En 1995,
se le pidi´o a Ro h que ayuda a a dise˜na un algo i mo mejo ado que elimina ´a
es os p oblemas. El nue o algo i mo, implemen ado desde 1997, ha unciona-
do bas an e bien. Pa ec´ıa que los solici an es pod´ıan manipula el algo i mo al
echaza o e as que ealmen e p e e ´ıan y man ene las que e an peo es, pa a
as´ı log a un mejo esul ado. En a ios abajos e´o icos Ro h mos ´o que es o
pod´ıa sucede , po ello el algo i mo ue e isado y dise˜nado pa a se inmune a
34
Cap´ı ulo 3. Juego de Asignaci´on
manipulaci´on.
El algo i mo de Gale-Shapley ambi´en se puede usa , po ejemplo, en la
elecci´on de ins i u os o colegios. En 2003, Ro h y sus colabo ado es ayuda on
a edise˜na el p oceso de admisi´on que hab´ıa has a en onces, basado en un
algo i mo del ipo de Gale-Shapley. El algo i mo esul o se exi oso. Hoy, un
n´ume o c ecien e de ´a eas me opoli anas de Es ados Unidos usa alguna a ian e
de ´es e.
Todo es o es ´a cla amen e elacionado con el Juego de Asignaci´on. La ca-
ac e ´ıs ica m´as so p enden e de es os algo i mos es que los p ecios no o man
pa e del p oceso.
35
Cap´ı ulo 3. Juego de Asignaci´on
36
Cap´ı ulo 4
Juego de P oducci´on Lineal
Analicemos aho a el Juego de P oducci´on Lineal. Es e p oblema ue ana-
lizado po p ime a e po G. Owen, en [14]. Se a a de un juego en el que
los jugado es combinan ecu sos pa a p oduci p oduc os e minados que pue-
dan ende se a un p ecio de me cado de e minado. El p oceso de p oducci´on es
lineal, de modo que la unci´on ca ac e ´ıs ica puede ob ene se esol iendo p o-
g amas lineales. La eo ´ıa de la dualidad de la p og amaci´on lineal se u iliza
pa a ob ene ec o es de equilib ios de p ecios y pa a p oba que el co e es no
ac´ıo.
Conside emos en onces el juego de p oducci´on con N={1,2, . . . , n}conjun-
o de jugado es, cada jugado iene un paque e de ama˜no qde p oduc os. M´as
espec´ı icamen e, el jugado i iene bi1unidades del p oduc o C1,bi2unidades
de C2,..., ybiq unidades de Cq. Los p oduc os ca ecen de alo po si mismos,
excep o que pueden se usados pa a p oduci bienes B1, . . . , Bm, que puedan
ende se a p ecios ijos de me cado. Asumimos un p oceso de p oducci´on lineal,
en el que una unidad de Bl equie e a1lunidades de C1,a2lunidades de C2,...,
yaql unidades de Cq, y puede se endido po un p ecio pl.
Cuando se o ma una coalici´on S, sus miemb os pond ´an en com´un sus e-
cu sos (ma e ia p ima) pa a maximiza el alo de en a en el me cado de sus
p oduc os. As´ı, la unci´on ca ac e ´ıs ica iene dada po los p oblemas de p o-
37

Cap´ı ulo 4. Juego de P oducci´on Lineal
g amaci´on lineal
(S) = m´ax
m
X
l=1
plxl
s.a.:
m
X
l=1
aklxl≤bk(S), k = 1,2, . . . , q,
xl≥0, l = 1,2, . . . , m
(4.1)
donde: bk(S) = X
i∈S
bik es la can idad o al de Ckque iene la coalici´on S.
Teo ema 4.1. En es e juego, iene co e no ac´ıo.
Demos aci´on. Sea C={S1, S2, . . . , S }una colecci´on equilib ada, con ec o
de equilib io (y1, y2, . . . , y ). Pa a cada Sj∈C, sea xj= (xj
1, . . . , xj
m) ec o de
op imizaci´on del p og ama an e io de inido pa a Sj, y sea
x∗=
X
j=1
yjxj≥0.
Pa a cada k, enemos:
m
X
l=1
aklx∗
l=
X
j=!
yj
m
X
l=1
aklxj
l
≤
X
j=1
yjX
i∈Sj
bik =X
i∈N
bik X
j;i∈Sj
yj
=X
i∈N
bik =bk(N).
Po lo an o, x∗sa is ace las condiciones del p og ama de inido pa a (N),
luego m
X
l=1
plx∗
l≤ (N).
Aho a,
X
j=1
yj (Sj) =
X
j=1
yj
m
X
l=1
plxj
l=
m
X
l=1
plx∗
l≤ (N).
Como es o es cie o pa a oda colecci´on equilib ada C, concluimos que el
juego iene co e no ac´ıo. 
Hemos demos ado que iene co e no ac´ıo. Sin emba go, es impo an e
encon a pun os en el co e. Pa a ello, conside amos el p og ama dual de (4.1):
38
Cap´ı ulo 4. Juego de P oducci´on Lineal
m´ın
q
X
k=1
bk(S)zk
s.a.:
q
X
l=1
alkzl≥pk, k = 1,2, . . . , m,
zl≥0, l = 1,2, . . . , q,
(4.2)
(S) se ´a igual al m´ınimo del p og ama (4.2). Obse emos, aho a que las es-
icciones del p og ama (4.2) son independien es de S; sin emba go, el ec o
soluci´on (z1, . . . , zq) depende ´a de S.
En pa icula , sea (z∗
1, . . . , z∗
q) el ec o soluci´on de (4.2) cuando S=N.
En onces,
(N) = b1(N)z∗
1+. . . +bq(N)z∗
q(4.3)
mien as que, pa a cualquie S,
(S)≤b1(S)z∗
1+. . . +bq(S)z∗
q(4.4)
ya que (S) es el m´ınimo pa a odos los ec o es ac ibles z.
Aho a, conside emos el ec o de pago u= (u1, . . . , un) de inido como sigue:
ui=bi1z∗
1+bi2z∗
2+. . . +biqz∗
q=
q
X
k=1
bikzk(4.5)
Pa a cualquie S, enemos
X
i∈S
ui=X
i∈S
q
X
k=1
bikz∗
k=
m
X
k=1 X
i∈S
bikz∗
k=
=b1(S)z∗
1+. . . +bq(S)z∗
q
y en onces, po (4.3),
X
i∈N
zi= (N)
y, po (4.4),
X
i∈S
zi≥ (S),
pa a cualquie S⊂N. Po lo an o, zes una impu aci´on del co e. En onces,
enemos un m´e odo pa a ob ene un pun o del co e: calculamos el ec o z∗
39
Cap´ı ulo 4. Juego de P oducci´on Lineal
esol iendo un p og ama lineal de ama˜no azonable (q a iables y m es iccio-
nes). Es o en onces nos da una impu aci´on upo (4.5)
Heu ´ıs camen e, las componen es z∗
1, . . . , z∗
mpueden conside a se p ecios de
equilib io de los ecu sos. A cada uno de los jugado es se les paga po sus ecu sos
seg´un el ec o de equilib io z∗; los pagos esul an es siemp e da ´an un ec o
en el co e.
Vemos que cualquie ec o de equilib io de p ecio z∗da ´a luga a un pun o
en el co e. (Puede habe m´as de un ec o de equilib io y, po lo an o, el co e
puede con ene m´as de un pun o). La p egun a es si el in e so es e dade o, es
deci , si odos los pun os en el co e se pueden ob ene po es e p ocedimien o.
En [20], Shapley y Shubik conside an un ipo especial de p og ama lineal -
un p oblema de asignaci´on - en el cual los ”bienes”p oducidos son o icios. En
ese caso, odos los pun os cen ales se pueden ob ene esol iendo el p og ama
dual; de hecho, las limi aciones del p og ama dual educen a las desigualdades
b´asicas, pe o es o se debe pu amen e al hecho de que es un ipo de p og ama
an especial. Pa a nues os juegos m´as gene ales, es a conje u a no es e dad.
Ejemplo 4.1. Veamos un con aejemplo i ial, conside emos un juego de dos
pe sonas con paque es de ecu sos:
b1= (1,0), b2= (0,2)
y un ´unico p oduc o inal, una unidad equie e una unidad de cada ecu so, y
se ende po 100e. En onces, el p og ama lineal (4.1) oma la siguien e o ma:
(S) = m´ax x
s.a.: x≤b1(S), x ≤b2(S), x ≥0,
que nos da (1) = (2) = 0, ({1,2}) = 1. El co e aqu´ı es a o mado po odos
los pun os (u1, u2) con 0 ≤u1≤1, u1+u2= 1.
Siendo S=N, enemos b(N) = (1,2). En onces el p oblema dual (4.2) es el
siguien e:
m´ın z1+ 2z2,
s.a.: z1+z2≥1, z1, z2≥0,
Es e iene una ´unica soluci´on z∗
1= 1, z∗
2= 0. Po lo an o, el p ecio de equilib io
40
Cap´ı ulo 4. Juego de P oducci´on Lineal
no usa nada pa a el segundo ecu so; ya que el jugado 2 comienza solo con es e
ecu so, no puede ecibi nada po es e esquema. As´ı, s´olo se puede ob ene de
es e mane a u= (1,0), mien as que el co e con iene o os muchos pun os.
Concluimos en onces que el co e del Juego de P oducci´on Lineal es no ac´ıo.
Aunque, el co e puede ene m´as de un pun o po lo que pod ´a habe m´as de
un ec o de equilib io.
4.1. Aplicaci´on con CPLEX
Aho a amos a hace una aplicaci´on del Juego de P oducci´on Lineal median-
e CPLEX usando la p´agina web www.neos-se e .o g. NEOS-SERVER es un
se icio g a ui o de In e ne pa a esol e p oblemas de op imizaci´on num´e ica.
O ganizado po el Wisconsin Ins i u e o Disco e y de la Uni e sidad de Wis-
consin, NEOS-SERVER p opo ciona acceso a m´as de 60 m´e odos pa a esol e
o ganizados en m´as de una docena de ca ego ´ıas.
Vamos a esol e una si uaci´on en la que es emp esas, E1, E2, E3, E4, quie-
en gene a es bienes, B1, B2, B3, que necesi an dis in os p oduc os, en es e
caso son necesa ios sie e p oduc os pa a gene a los es bienes, p1, . . . , p7. Las
emp esas poseen la siguien e can idad de p oduc os, las mos amos median e el
Cuad o 4.1. La can idad de p oduc o necesa io pa a gene a cada bien se dan
en el Cuad o 4.2.
E1E2E3E4
p1100 0 50 150
p240 40 0 0
p30 40 0 80
p40 90 100 200
p560 100 0 40
p640 0 30 30
p710 70 50 0
Cuad o 4.1: Can idad de p oduc o que ienen las emp esas Ej.
Los bienes que p oducen se enden a un p ecio ijo de me cado:
p1= 1 p2= 2 p3= 3.
41
Cap´ı ulo 5. Juegos de Localizaci´on
´acil de p oba , pa a que la soluci´on p opo cionalmen e iguali a ia es e en ´el.
Pa a inaliza el cap´ı ulo a amos el juego de localizaci´on de Webe con cos e
ijo no a iable y con cos e a iable. Ve emos una condici´on necesa ia pa a que
la soluci´on iguali a ia es ´e en el co e y, ambi´en, da emos a ios ejemplos de
ambas si uaciones analizando las di e encias en e ambos juegos.
Pa a es e cap´ı ulo hemos usado las uen es [18] y [9].
5.1. P oblema Con inuo de Localizaci´on
En p ime luga , desc ibimos que es un p oblema con inuo de localizaci´on
de ins alaciones indi iduales. El p oblema consis e en encon a una ubicaci´on
pa a la ins alaci´on que minimice el cos e de anspo e (que depende de la
dis ancia de los usua ios a la ins alaci´on). Fo malmen e, un p oblema con inuo
de localizaci´on de ins alaciones indi iduales es una iple a: (N, Φ, d) donde:
N={a1, . . . , an}conjun o de npun os dis in os en Rm(con n≥2).
Φ : Rn→Res una unci´on de globalizaci´on semicon inua in e io que
e i ica:
1. Φ es de inida, i.e., Φ(x) = 0 si y solo si x= 0;
2. Φ es mon´o ona, i.e., Φ(x)≤Φ(y) pa a x≤y.
d:Rm×Rm→Res una medida de dis ancia, sa is aciendo que, pa a cada
, s ∈Rm, d( , s) = (|| −s||),donde es una aplicaci´on semicon inua
in e io , no dec ecien e y no nega i a de Ren Rcon (0) = 0, y ||·|| es
una no ma sob e Rm.
Resol e el p oblema de localizaci´on con inuo con una ´unica ins alaci´on
(N, Φ, d), pa a S⊂N, consis e en encon a un pun o x∈Rmque mini-
mice Φ(dS(x)), donde dS(x) es el ec o en Rncuya i-´esima componen e es
igual a d(x, ai) si ai∈Se igual a 0 en o o caso. Deno a emos L(S) =
m´ınx∈RmΦ(dS(x)). Obse emos que es e p oblema siemp e iene soluci´on pa-
a cada S⊂N( e [16]).
Es a es la e si´on cl´asica del p oblema de localizaci´on con inuo con una ´unica
ins alaci´on. Vamos a conside a una a ian e, na u al, de es e p oblema en el que
48

Cap´ı ulo 5. Juegos de Localizaci´on
los usua ios en Nes ´an in e esados no s´olo en encon a una ubicaci´on ´op ima
de la ins alaci´on, sino ambi´en en compa i los cos es o ales co espondien es.
Po cos e o al en endemos la suma de los cos es a iables (dependiendo de los
usua ios y de la ubicaci´on de la ins alaci´on, en su mayo pa e se ´an cos es de
anspo e), m´as los cos es ijos (independien e de lo an e io , p incipalmen e los
cos es de la ins alaci´on). Fo malmen e, una si uaci´on de localizaci´on con inua de
una sola ins alaci´on es una 4- upla (N, Φ, d, K) donde (N, Φ, d) es un p oblema
de localizaci´on con inuo con ´unica ins alaci´on y K∈R, K ≥0, es el cos e
ijo de ins alaci´on de la ins alaci´on. Tengamos en cuen a que podemos asocia
(N, Φ, d, K) con un juego (N, c) cuya unci´on ca ac e ´ıs ica cse de ine, pa a
cada S⊂N={a1, . . . , an}, po :
c(S) = 


K+L(S) si S6=∅
0 si S=∅.
Deno a emos po L(N) a la clase de juegos de localizaci´on con el conjun o de
jugado es N(iden i ica emos cada jugado con su posici´on en el plano). Como de
cos umb e, ambi´en iden i ica emos el juego (N, c) con la unci´on ca ac e ´ıs ica
c.
El obje i o de los jugado es, de un p oblema de localizaci´on, es encon a
una ubicaci´on pa a la ins alaci´on que minimice el cos e o al y asigna el cos e
o al m´ınimo co espondien e.
Veamos un pa de si uaciones de localizaci´on:
Ejemplo 5.1. Supongamos que los alcaldes de nciudades ce canas (ciudad i
localizada en el pun o ai∈R2), desean hace un acue do pa a cons ui un
ae opue o conjun amen e. El cos e de cons ucci´on del ae opue o es, ap oxi-
madamen e, Ke. El acue do incluye el comp omiso de in e i en cada ciudad
una can idad de eu os igual a A eces su dis ancia al cuad ado al ae opue o
(con Aun n´ume o eal posi i o) pa a c ea buenas ca e e as e in aes uc-
u a e o ia ia comunicando las ciudades y el ae opue o. Los ayun amien os
quie en encon a una ubicaci´on ´op ima pa a el ae opue o (minimiza el cos e
o al) y compa i los cos es o ales co espondien es. Obse emos que se a a
de una si uaci´on de localizaci´on (N, Φ, d, K) con Φ(dS(x)) = APai∈Skx−aik2
2
pa a odo x∈R2, y oda S⊂N. Obse emos que Φ(x) = APn
i=1 xi,∀x∈
49
Cap´ı ulo 5. Juegos de Localizaci´on
Rn, (y) = y2,∀y∈R, y d=kk2la no ma eucl´ıdea. (Aqu´ı hemos omado kk2,
pe o o as no mas pod ´ıan se m´as na u ales en o as ci cuns ancias).
Ejemplo 5.2. Supongamos que los ayun amien os de nciudades ce canas (ciu-
dad ilocalizada en el pun o ai∈R2), desean hace un acue do pa a c ea una
ele isi´on local. Es o iene un cos e ijo de Keu os (cons ucci´on del edi icio de
o icinas y el es udio) y un cos e a iable. Se ha es imado que el cos e a iable (el
cos e del p opio canal) es A eces el cuad ado del adio de cobe u a del canal
de ele isi´on (el adio de cobe u a de un canal es la dis ancia m´axima a la
ubicaci´on del canal desde la cual la se˜nal de ele isi´on puede se ecibida co ec-
amen e, Aes un n´ume o eal posi i o). Los ayun amien os quie en encon a
una ubicaci´on ´op ima pa a la es aci´on de ele isi´on (de al mane a que odas
las ciudades eciban co ec amen e la se˜nal y a un cos e m´ınimo) y compa i
los cos es o ales co espondien es. Obse emos que es o es una si uaci´on de
localizaci´on (N, Φ, d, K) con Φ(dS(x)) = Am´axai∈Skx−aik2
2,∀x∈Rn, (y) =
y2,∀y∈R,yd=kk2la no ma eucl´ıdea. (De nue o hemos omado kk2, pe o
o as no mas pod ´ıan se m´as na u ales en o as ci cuns ancias).
Un p oblema in e esan e que se plan ea aho a es es udia bajo que con-
diciones el co e del juego de localizaci´on co espondien e es no ac´ıo. Po que
los usua ios no s´olo quie en encon a una ubicaci´on ´op ima pa a la ins alaci´on,
sino ambi´en asigna los cos es o ales. Si es o no sucedie a p obablemen e es os
usua ios no pod ´ıan llega a un acue do y no cons ui ´ıan la ins alaci´on jun os.
Da emos condiciones su icien es pa a que el co e sea no ac´ıo. M´as a de
e emos algunas clases impo an es de juegos de localizaci´on y e emos que
condiciones son necesa ias pa a usa la egla de asignaci´on iguali a ia (que no -
malmen e se usa en la p ´ac ica) que p opo ciona asignaciones.
Veamos aho a algunas p opiedades p elimina es de los juegos de localizaci´on.
P oposici´on 5.1. Tomemos c∈L(N)el juego de localizaci´on co espondien-
e a (N, Φ, d, K). En onces ces mon´o ono, es deci , c(s)≤c(T),∀S, T ⊂
Ncon S⊂T).
Demos aci´on. Sean S⊆Tdos coaliciones. Po de inici´on dS
i(x)≤dT
i(x) pa a
odo iex. En onces, dado que Φ es mon´o ona, Φ(dS(x)) ≤Φ(dT(x)). Po lo
an o, se iene el esul ado. 
50
Cap´ı ulo 5. Juegos de Localizaci´on
P oposici´on 5.2. Tomemos c∈L(N)juego de localizaci´on co espondien e
a(N, Φ, d, K). Si L(N)≤Ken onces ces subadi i io, es deci , c(s∪T)≤
c(S) + c(T)∀S, T ⊂Ncon S∩T=∅.
Demos aci´on. Sean S, T dos coaliciones. En onces, po la mono on´ıa de L( e
la p ueba an e io ) y las p opiedades de Φ,
L(S∪T)−(L(S)−L(T)) ≤L(S∪T)≤L(N).
Aho a, dado que L(N)≤K, se iene que L(S∪T)≤K+L(S) + L(T) y
c(S∪T) = K+L(S∪T)≤K+L(S) + K+L(T) = c(S) + c(T).
Obs´e ese que en el esul ado an e io p obamos que, si L(N)≤K, en onces
c(S∪T)≤c(S) + c(T) pa a cualquie pa de coaliciones SyTdisjun as o no.
El siguien e ejemplo mues a un juego de localizaci´on subadi i o con co e ac´ıo.
Es o mo i a los esul ados pos e io es donde buscamos condiciones su icien es
pa a que el co e del juego de localizaci´on sea no ac´ıo.
Ejemplo 5.3. Sea N={a1, a2, a3}el conjun o de los jugado es, localizados en
los e ices de un i´angulo equil´a e o de lado l. Conside emos que la unci´on de
globalizaci´on es la suma y que des la dis ancia eucl´ıdea ele ada a la po encia
b, (b≥2). En onces,
Φ(dS(x)) X
ai∈Skx−aikb
2,
pa a cada S⊂Ny cada x∈Rm. Es ´acil comp oba que el juego de localizaci´on
asociado con (N, Φ, d, K) es a dado po :
c(a1) = c(a2) = c(a3) = K,
c(a1a2) = c(a1a3) = c(a2a3) = K+ 2(l/2)b,
c(a1a2a3) = K+ 3√3
3lb.
Se puede comp oba que el juego es subadi i o si y s´olo si K≥(lb/√3b−2)−
(lb/2b−1). Sin emba go, omando po ejemplo K= (lb/√3b−2)−(lb/2b−1), se
puede e que el juego de localizaci´on esul an e iene co e ac´ıo. Es deci , dado
que odos sus ac o es son sim´e icos, una condici´on necesa ia y su icien e pa a
51
Cap´ı ulo 5. Juegos de Localizaci´on
ene co e no ac´ıo es que la asignaci´on iguali a ia (c(N)/3, c(N)/3, c(N)/3)
pe enezca al co e. Se puede comp oba que no es el caso cuando b > 2.
Los siguien es esul ados ienen la mo i aci´on de p opo ciona una condici´on
su icien e pa a que el co e del juego de localizaci´on sea no ac´ıo. En la Obse -
aci´on 2.1 desc ibimos el co e de un juego de localizaci´on (N, c), lo eco damos:
Co e( ) = C( ) = {x∈RN
+:x(N) = (N); x(S)≤ (S),∀S⊆N}.(5.1)
U ilizando el Lema 2.2 amos a p oba el eo ema m´as impo an e de es a
secci´on.
Teo ema 5.1. Sea (N, Φ, d, K)una si uaci´on de localizaci´on y sea (N, c)el
co espondien e juego de localizaci´on. Deno amos l2= m´ınS⊂N:|S|=2 L(S).
(a)Supongamos que 2≤n≤2 + l2
K. Si K(n−1) ≥L(N), en onces c iene
co e no ac´ıo.
(b)Supongamos que 2 + l2
K≤n. Si K≥(n−1)L(N)−nl2, en onces c iene
co e no ac´ıo.
Demos aci´on. En un juego de localizaci´on enemos pa a cualquie colecci´on
equilib ada B con coe icien es de equilib io {ys:S∈B}:
X
S∈B
ySc(S) = KX
S∈B
yS+X
S∈B
ySL(S).
Teniendo en cuen a la mono on´ıa de Ly el hecho de que L(S) = 0 pa a cualquie
coalici´on de ama˜no uno, enemos que
X
S∈B
ySc(S) = KX
S∈B
yS+X
S∈B:|S|≥2
ySL(S)
≥KX
S∈B
yS+X
S∈B:|S|≥2
ySl2.
Pa a cualquie colecci´on equilib ada m´ınima Bdeno amos:
m(B) = KX
S∈B
yS+l2X
S∈B:|S|≥2
yS.
52
Cap´ı ulo 5. Juegos de Localizaci´on
(Obse amos que, si Bes m´ınima, los coe icien es de equilib io es ´an de e mi-
nados de o ma ´unica). En onces, una condici´on su icien e pa a que el co e sea
no ac´ıo es:
m´ın
{B:Bno i ial y m´ınima equilib ada}m(B)≥c(N).(5.2)
Supongamos que es e m´ınimo se alcanza en ˆ
B. Si {ai} 6∈ ˆ
Bpa a cada ai∈N,
en onces ˆ
B={−i:ai∈N}( e lema an e io ) y m(ˆ
B)=(K+l2)n
n−1. Si
ˆ
B={{ai}:ai∈N}, en onces m(ˆ
B) = Kn. En o o caso ˆ
Bsolo puede se una
amilia {{ai}, N ai}(pa a un ai∈A) y, en onces, m(ˆ
B)=2K+l2.
Aho a, dado que m(ˆ
B) = m´ın{(K+l2n
n−1, Kn, 2K+l2}, es ´acil comp oba
que:
m(ˆ
B) = 


Kn, si 2 ≤n≤2 + l2
K,
(K+l2)n
n−1,si l2
K< n.
Es o jun o con (5.2) comple a la p ueba. 
Los siguien es ejemplos demues an que los l´ımi es en el eo ema son ajus a-
dos, en el sen ido de que no se puede mejo a pa a odo n. En pa icula , es os
ejemplos mues an que se consiguen pa a n= 2 y n= 3.
Ejemplo 5.4. Sea N={a1, a2}un conjun o de jugado es, localizados en los
ex emos de un segmen o de longi ud 2. Conside e que la unci´on de globaliza-
ci´on es la suma y que des la dis ancia euclidiana cuad ada. Es ´acil comp o-
ba que, el juego de localizaci´on (N, c) asociado a (N, Φ, d, K) es a dado po :
c(a1) = c(a2) = K, c(a1, a2) = K+ 2. Cla amen e, es e juego iene co e no
ac´ıo si y s´olo si K≥2. Obse emos que, en es e caso, bajo la condici´on (a) del
eo ema an e io y K(n−1) ≥L(N) es equi alen e a K≥2, en onces la co a
es ajus ada pa a es e juego.
Ejemplo 5.5. Tomemos la misma si uaci´on de localizaci´on y el mismo juego
de localizaci´on del Ejemplo 5.3 con b= 2. Po lo an o, N={a1, a2, a3}y la
unci´on ca ac e ´ıs ica del juego es:
c(a1) = c(a2) = c(a3) = K,
c(a1a2) = c(a1a3) = c(a2a3) = K+l2/2,
c(a1a2a3) = K+l2.
Ya que los jugado es son sim´e icos en c,co e(c)6=∅si y s´olo si la asignaci´on
53

Cap´ı ulo 5. Juegos de Localizaci´on
iguali a ia c(N)
3,c(N)
3,c(N)
3pe enece a co e(c). Es ´acil comp oba que
es a asignaci´on pe enece co e(c) si y s´olo si K≥l2
2. Obse emos que, en
es e caso, si K > l2
2es amos bajo la condici´on (b); si K≤l2
2es amos bajo
la condici´on (a). En ambos casos, la co a dada po el Teo ema es K≥l2
2.
En onces, de nue o la co a es ajus ada pa a es e ejemplo.
Con el eo ema an e io enemos una condici´on su icien e pa a que el co e
de cualquie juego de localizaci´on sea no ac´ıo. Es a condici´on es buena po que:
a) no puede mejo a se en gene al, y b) puede se comp obada de una mane a
azonablemen e ´acil (s´olo hay que calcula l2yL(N)). O a condici´on su icien e
m´as sencilla que la del Teo ema 5.1 es la siguien e.
P oposici´on 5.3. Sea (N, Φ, d, K)una si uaci´on de localizaci´on y sea (N, c)
su co espondien e juego de localizaci´on. Si K≥(n−1)L(N), en onces c iene
co e no ac´ıo.
Demos aci´on. Comp obemos que la asignaci´on iguali a ia K+L(N)
n,...,K+L(N)
n
pe enece a co e(c). Espec´ı icamen e, pa a cada S⊂Ncon |S| ≤ n−1,
|S|K+L(N)
n≤(n−1)K+L(N)
n≤K≤c(S).
De donde se deduce lo que que ´ıamos p oba . 
Obs´e ese que, aunque la condici´on en la P oposici´on 5.3 es m´as simple que
la condici´on en el Teo ema 5.1, ambi´en es m´as d´ebil. S´olo en el caso de que l2
sea muy peque˜na (es deci , en caso de que haya dos usua ios si uados en dos
pun os muy ce canos), la condici´on en el Teo ema 5.1 iende a se la misma
que la de la P oposici´on 5.3. Pe o, en al caso, al ez se ´ıa m´as con enien e
conside a a es os dos jugado es ce canos como un solo jugado .
5.2. Juego de localizaci´on minimax
Conside emos aho a la clase de Juegos de Localizaci´on Minimax en Rm. Pa a
empeza obse emos que en es a clase, des la dis ancia eucl´ıdea y la unci´on de
54
Cap´ı ulo 5. Juegos de Localizaci´on
globalizaci´on es m´ın m´ax, adem´as:
cM(S) = m´ın
x∈Rmm´ax
a∈Skx−ak2
2+K. (5.3)
Luego:
l2= m´ın
a,b∈N,a6=bka−bk2
2
4.
Po lo an o, l2se puede calcula de una mane a azonablemen e ´acil y las
condiciones del Teo ema 5.1 se pueden comp oba ´acilmen e.
Aho a deno emos lk=minS⊂N:|S|=kL(S), pa a k∈ {2, . . . , n}.En eo ´ıa
de localizaci´on, es una ca ac e ´ıs ica bien conocida que, pa a cada S⊂Ncon
|S| ≥ m+1, L(S) es igual a L(S) pa a un S⊂Scon |S|=m+1 (ya que, en un
p oblema de localizaci´on minimax con un conjun o de pun os S, la soluci´on es
el cen o de la es e a m´as peque˜na que con emga S, y es a es e a es a comple-
amen e de e minada po a lo m´as m+ 1 pun os de S, s´olo es pun os pa a un
c´ı culo en R2). Po lo an o, pues o que Les mon´o ona, lk=lk+1,∀k≥m+ 1.
A con inuaci´on amos a da una condici´on su icien e y ´acil de p oba pa a
que la soluci´on p opo cionalmen e iguali a ia pe enezca al co e en un juego de
localizaci´on minimax. P ime o amos a deci lo que en endemos po soluci´on
p opo cionalmen e iguali a ia en es e con ex o. Como di emos en los juegos de
localizaci´on de Webe , supongamos que aqu´ı hay un ec o de coe icien es de
p opo cionalidad eal posi i o (α1, . . . , αn).Supongamos, sin p´e dida de gene a-
lidad, que α1≤α2≤ ··· ≤ αn. Deno emos α=Pai∈Nαi. Obse emos que, en
los juegos de localizaci´on minimax, un usua io en pa icula no p oduce cos es de
anspo e una ez que se decide la ubicaci´on de la ins alaci´on, en el sen ido de
que los cos es de anspo e se ´ıan iguales si se abandona ´a el juego. (Pensemos
en el Ejemplo 5.2: la ubicaci´on y el adio de cobe u a del canal se ha decidido,
un usua io pa icula no p oduce cos es de anspo e. Es e no es el caso del
juego de localizaci´on de Webe , como en el Ejemplo 5.1. Po lo an o, la o ma co-
ec a de de ini aqu´ı la soluci´on p opo cionalmen e iguali a ia E es la siguien e.
Si (N, cM) es el juego de localizaci´on minimax asociado con la si uaci´on de lo-
calizaci´on minimax (N, Φ, d, K), en onces Ei(cM)=(K+L(N))αi/α, ∀ai∈N.
El siguien e eo ema es ablece una condici´on su icien e pa a que Ep opo cione
asignaciones al co e.
55
Cap´ı ulo 5. Juegos de Localizaci´on
Teo ema 5.2. Sea (N, cM)el co espondien e juego de localizaci´on minimax a
la si uaci´on de localizaci´on minimax (N, Φ, d, K). En onces, E(cM)pe enece al
co e(cM)si
L(N)Pn
j=n−k+1 αj
α− (k)≤K 1−Pn
j=n−k+1 αj
α!,(5.4)
pa a cada k∈ {1, . . . , n}, donde (1) = 0, (k) = lkpa a cada 2≤k≤m+ 1 y
(k) = lm+1,∀k≥m+ 1.
Demos aci´on. E(cM)∈co e(cM) si y s´olo si, pa a odo S⊂N,
X
ai∈S
(K+L(N))αi
α≤K+L(S).(5.5)
Teniendo en cuen a α1≤α2≤ ··· ≤ αny que lk=lm+1 pa a odo k≥m+ 1,
es cla o que, pa a cada k∈ {1, . . . , n}(5.4) implica (5.5) pa a cada S⊂Ncon
|S|=k.
Podemos in e p e a la condici´on (5.4) de la siguien e mane a. La mi ad iz-
quie da de la desigualdad es la pa e del cos e de cobe u a que los jugado es
en {a1, . . . , ak}aho an, menos el cos e de cobe u a m´as peque˜no que debe se
pagado po una coalici´on de kjugado es si s´olo ellos coope an. El lado de e-
cho es la pa e del cos e ijo pagado po los jugado es en {a1, . . . , an}. Po lo
an o, E(cM) pe enece a co e(cM) si y s´olo si los jugado es con coe icien es de
p opo cionalidad peque˜no pagan una pa e su icien emen e g ande del cos e de
cobe u a. Una ez m´as, la condici´on (5.4) se cumple, pa a cada p oblema de lo-
calizaci´on minimax y cada ec o de p opo cionalidad α, si Kes su icien emen e
g ande.
Obs´e ese que se pod ´ıa encon a ´acilmen e una condici´on su icien e m´as
d´ebil. Sin emba go, la del Teo ema 3.8. an e io es especialmen e ´acil de com-
p oba . S´olo hay que conside a n desigualdades, y calcula l2, . . . , lm+1 que en
el caso del plano (R2) se educe a l2yl3.
An e io men e hemos is o un ejemplo de es e juego en el Ejemplo 5.2.
56
Cap´ı ulo 5. Juegos de Localizaci´on
5.3. Juego de localizaci´on de Webe , con cos e
ijo
Aho a conside emos el Juego de Localizaci´on de Webe , cons e ijo no a ia-
ble. En el p oblema de localizaci´on de Webe la unci´on de globalizaci´on es la
suma. El juego de localizaci´on co espondien es iene dado po :
cW(S) = m´ın
x∈RnX
a∈Skx−ak2
2+K, (5.6)
pa a oda S⊂N. Siendo (N, Φ, d, K) si uaci´on de localizaci´on, con ddis an-
cia eucl´ıdea al cuad ado. Obse emos que el Ejemplo 5.1 es una si uaci´on de
localizaci´on de Webe .
Es a clase de p oblemas de localizaci´on es muy conocida. Es ´acil deduci
que la soluci´on ´op ima del p oblema (3) es:
x∗(S) = 1
|S|X
a∈S
a.
Ob iamen e, odos los esul ados an e io es siguen siendo aplicables a es os
juegos.
En muchas si uaciones p ´ac icas, cuando a ios usua ios deciden cons ui
una ins alaci´on conjun amen e, acue dan usa alg´un ipo de soluci´on p opo -
cionalmen e iguali a ia pa a la asignaci´on de los cos es. Pa a las si uaciones de
localizaci´on de Webe , una egla p opo cionalmen e iguali a ia consis e en lo
siguien e:
(a) La ins alaci´on se cons ui ´a en la ubicaci´on x∗(P),
(b) Los cos e ijos K se di iden p opo cionalmen e en e los usua ios, de acue -
do con un ec o de coe icien es de p opo cionalidad (α1, . . . , αn),
(c) Cada usua io paga los cos es de anspo e que p oduce.
Es o signi ica que, si (N, cW) es el juego de localizaci´on asociado con la
si uaci´on de localizaci´on de Webe (N, Φ, d, K), de acue do con es a egla (la
57
Cap´ı ulo 5. Juegos de Localizaci´on
enemos una l´ınea de e oca il y el p oblema es decidi d´onde cons ui una
es aci´on de e oca il pa a mejo a el se icio a los habi an es de la egi´on.
Pa a simpli ica conside emos Ω = [0, L], (L > 0), y el conjun o de ins alacio-
nes N={a1, . . . , an}ubicadas en Ω con coo denadas xa1, . . . , xan. Supongamos
ambi´en que el cos e ijo de inido en Ω es:
K(x) = 


k1x≤¯x,
k2en o o caso,
(5.14)
con 0 < k1< k2y la soluci´on co espondien e al p oblema de Webe es x∗(N) =
¯x. Cen emos el an´alisis en dos ins alaciones consecu i as ai, aj,(xai < xaj ).
Como en la siguien e igu a:
Fig. 1: el p oblema de localizaci´on sob e una ec a.
ai¯xaj
En es e caso si k1+ (xaj −¯x)< k2, enemos que c({ai}) = k1, c({aj}) =
k1+ (xaj −¯x), c({ai, aj}) = k1+ (xaj −xai). Si el alo p opo cional xP
i=
kx∗(N)−aik2+αik1pe enece al co e, po la inecuaci´on (5.13) pa a S={ai}
enemos la co a αi≤1−kx∗(N)−aik2
k1y pa a S={aj}la inecuaci´on i ial αj≤
1. Po o o lado, si el jugado aiy el jugado ajdeciden localiza su ins alaci´on
en x∗({ai, aj}) = ai, la inecuaci´on (5.12) dice αi+αj≤1−2kx∗(N)−aik2
k1, que
no se sa is ace con αi>1−2kx∗(N)−aik2
k1.Si es e es el caso, no enemos el e ec o
de compensaci´on dado po la condici´on (5.11). Tengamos en cuen a que pa a el
jugado aiy el jugado ajes indi e en e ubica x∗({ai, aj}) en cualquie pun o
del in e alo [xai,¯x].
Finalmen e, obse emos que en caso del cos e ijo cons an e la condici´on
(5.11) es simila a la condici´on (5.7), que hemos dado en el p oblema an e io .
64

Cap´ı ulo 6
Juegos de Radio y Di´ame o
Du an e es e cap´ı ulo con inuamos analizando los juegos de localizaci´on,
aunque aho a nos cen amos en un ipo espec´ı ico que se a an de o ma lige-
amen e dis in a. Aqu´ı hemos usado la e e encia [17]. De nue o los jugado es
son los clien es (pun os de demanda) en el p oblema de localizaci´on y el alo
ca ac e ´ıs ico de una coalici´on es el cos e de se i a sus miemb os. Espec´ı ica-
men e, el cos e en es os juegos es el adio de se icio de la coalici´on. A es os
juegos se les conoce como Juegos de Localizaci´on de Radio M´ınimo.
Es udia emos la exis encia de pun os en el co e y la exis encia de ep esen a-
ciones polinomiales de los co es de es os juegos, cen ´andonos en espacios de ed,
es deci , espacios m´e icos ini os inducidos po g a os no di igidos y longi udes
de a is as posi i o y en los espacios m´e icos de inidos sob e Rd.
Adem´as, analiza emos la elaci´on en e los Juegos de Localizaci´on de Radio
M´ınimo y los Juegos de Localizaci´on de Di´ame o M´ınimo. Po es o comenza-
mos el cap´ı ulo con unos concep os in oduc o ios sob e el adio y el di´ame o
de un conjun o ini o de un espacio m´e ico. Demos a emos un eo ema que
p opo ciona una si uaci´on en el que el co e de ambos juegos es igual y no ac´ıo.
Du an e el cap´ı ulo e emos dis in os ejemplos de es e ipo de juegos, en
alguno de ellos comp oba emos dis in as si uaciones en las que el co e puede se
ac´ıo o no ac´ıo.
Sea Xun espacio m´e ico y sea N0={ 0, 1, . . . , k}un conjun o ini o de
pun os de X. El subconjun o N={ 1, . . . , k}se iden i ica con el conjun o
65
Cap´ı ulo 6. Juegos de Radio y Di´ame o
de kjugado es, nos e e imos a es os pun os como ins alaciones exis en es, o
pun os de demanda. Tambi´en hay un pun o 0, que ep esen a la ubicaci´on de
un se ido que p opo ciona se icios a los jugado es, que puede se is o como
un elemen o especial en el sis ema, po ejemplo, cada pun o de demanda debe
ene acceso a 0. Obse emos que 0no es un jugado . Po ejemplo, supongamos
que los pun os de demanda ep esen an a los pacien es y 0es la ubicaci´on de
un m´edico que p es a se icios sani a ios.
Es e es udio es ´a mo i ado po modelos de localizaci´on, donde el iempo
anscu ido has a que se p opo ciona el se icio ( iempo de espues a) es c ´ı i-
co. Con inuando con el ejemplo an e io , el se icio m´edico no se p opo ciona
en su o igen. Po o a pa e, la coalici´on de pacien es Spuede selecciona de
o ma ´op ima la ubicaci´on del cen o (po ejemplo, cl´ınica u hospi al), donde se
p opo ciona ´a el se icio. Cuando hay una llamada de se icio, an o el pacien-
e como el m´edico iaja ´an a la cl´ınica. El cos e del se icio se supone como el
adio de se icio, de inido como la dis ancia m´axima eco ida po un pacien e
o el m´edico al cen o de se icio (cen o). U ilizando la e minolog´ıa de la eo ´ıa
de localizaci´on, el cos e de una coalici´on Ses el alo de soluci´on del p oblema
1-cen o pa a el conjun o S∪{ 0}.
De inamos algunos concep os necesa ios:
De inici´on 6.1. Dado un subconjun o ini o de pun os Y⊆X, su di´ame o
D(Y) se de ine como:
D(Y) = m´ax
y1,y2∈Yd(y1, y2).
Un pa de pun os y1, y2∈Y, que e i iquen: D(Y) = d(y1, y2) se denominan
diame ales.
De inici´on 6.2. Dado un subconjun o ini o de pun os Y⊆X, se de ine el
adio de Ycomo:
R(Y) = ´ın
x∈Xm´ax
y∈Yd(x, y).
Un pun o x∈Xsa is aciendo R(Y) = m´axy∈Yd(x, y) se llama 1-cen o de Y.
Obse emos que po la desigualdad iangula :
R(Y)≤D(Y)≤2R(Y).(6.1)
66
Cap´ı ulo 6. Juegos de Radio y Di´ame o
Obse emos que el co e de (N, ), en el caso de un juego de cos e, como ya
hemos is o en secciones an e io es, es el conjun o:
C(N, ) = {x∈Rk:x(N) = (N), x(S)≤ (S),∀S⊆N}.(6.2)
El Juego de Localizaci´on de Di´ame o M´ınimo (MDLG), (N, I), espec o al
espacio m´e ico Xy el conjun o de pun os N0, iene como unci´on ca ac e ´ıs ica:
I(S) = D(S∪{ 0}).
Aho a de inimos o malmen e la clase de juegos de cos es coope a i os basa-
dos en los p oblemas de localizaci´on de ins alaciones an e io es que es udiamos
a con inuaci´on: el Juego de Localizaci´on de Radios M´ınimo (MRLG). Su unci´on
ca ac e ´ıs ica se de ine como:
II(S) = 2R(S∪{ 0}).
Conside emos el espacio m´e ico de ed inducido po un g a o conec ado no
di igido.
Supongamos G= (V, E) un g a o conec ado no di igido con longi udes de
a is as posi i as {le}, e ∈E, donde V={ 0, 1, . . . , n}.Donde e= ( i, j),
usa emos la no aci´on l( i, j) = le. Suponemos que cada a is a en Ees ec i i-
cable. Nos e e imos a los pun os in e io es de una a is a po su dis ancia (a lo
la go de la a is a) de los dos nodos de la a is a. A(G) es el conjun o con inuo de
pun os en las a is as de G. Pa a cualquie pa de pun os x, y ∈A(G), deno a e-
mos po d(x, y) el camino m´as co o en A(G) conec ando xey. Nos e e imos
aA(G) como el espacio m´e ico inducido po Gy las dis ancias m´ınimas.
Po de inici´on la unci´on ca ac e ´ıs ica II es mon´o ona. Sin emba go, cuando
el espacio m´e ico X es disc e o, es deci , |X|es ini o, el juego de localizaci´on
de adios, (N, II) no iene po que e i ica la p opiedad de supe adi i idad.
Como esul ado los jugado es pueden no ene ning´un incen i o pa a coope a
y el co e puede es a ac´ıo, como se e en el siguien e ejemplo:
Ejemplo 6.1. Conside emos una u a con 5 nodos con el siguien e conjun o de
a is as: E={( 1, 2),( 2, 0),( 0, 3),( 3, 4)}. Las espec i as longi udes son
67
Cap´ı ulo 6. Juegos de Radio y Di´ame o
1,1,2 y 2. El espacio ini o (disc e o) X es a compues o de 5 nodos (pun os) con
unci´on de dis ancia inducida po la longi ud de las a is as. Tambi´en podemos
e Xcomo un conjun o de 5 pun os en la l´ınea eal. Conside emos p ime o el
juego de 2 jugado es sob e Xde inido po N={ 1, 4}. No es subadi i o ya que:
II({ 1, 4})> II ({ 1})+ II({ 4}).Se iene ambi´en que pa a el juego disc e o
comple o sob e el conjun o Xy el conjun o N=X { 0}={ 1, 2, 3, 4}
ampoco e i ica la subadi i idad pues: II ({ 1, 2, 3, 4})=8, II ({ 1, 2}) =
2, II({ 3, 4}) = 4, luego:
II({ 1, 2, 3, 4})> II ({ 1, 2}) + II ({ 3, 4})
Ejemplo 6.2. Veamos aho a un ejemplo que e i ica subadi i idad pe o iene
co e ac´ıo.
Conside emos el espacio m´e ico disc e o de inido po X={ 0, 1, 2, 3},
d( 0, 1) = d( 2, 3) = 2 y d( 0, 2) = d( 0, 3) = d( 1, 2) = d( 1, 3) = 1.
Sea N={ 1, 2, 3}, y conside emos el juego adial (disc e o) (N, II) Tenemos
II(N) = 4 y II (S) = 2 pa a cualquie coalici´on S, con |S| ≤ 2. Es ´acil
comp oba que no hay un ec o xque e i ique
x1+x2+x3= 4
x1+x2≤2
x2+x3≤2
x1+x3≤2
Luego es e juego iene co e ac´ıo.
Cuando el espacio m´e ico Xconsis e en un conjun o con inuo de pun os,
C(N, II) ambi´en puede se ac´ıo pa a un juego de 3 jugado es, como se ilus a
en el siguien e ejemplo de un espacio m´e ico de ed A(G). Es e ejemplo co es-
ponde a una ed de ca e e a plana geom´e ica muy simple, donde las a is as son
segmen os de l´ınea y sus longi udes son las dis ancias euclidianas espec i as.
Ejemplo 6.3. Conside emos el g a o G= (V, E) donde V={ 0, 1, . . . , 6}y
E={( 0, 4),( 0, 5),( 0, 6),( 1, 4),( 1, 6),( 2, 4),( 2, 5),( 3, 5),( 3, 6)}.
Todas las a is as de longi ud 1. Como en la siguien e igu a:
68
Cap´ı ulo 6. Juegos de Radio y Di´ame o
6
1
3
0
4
5
2
Sea X=A(G). Conside emos el juego (N, II ), de inido sob e X, con N0=
{ 0, 1, 2, 3}yN={ 1, 2, 3}. Es ´acil comp oba que pa a cada coalici´on
S⊆Ncon |S| ≤ 2 enemos II (S) = 2, y II (N) = 4.
Po sime ´ıa, si el co e es no ac´ıo la asignaci´on sim´e ica x= (4/3,4/3,4/3)
es a ´ıa en el co e con adiciendo la es icci´on x1+x2≤ II({ 1, 2}) = 2.
Pa a cualquie espacio m´e ico X, la de inici´on de II asegu a la mono on´ıa
del juego (N, II ), mien as que la subadi i idad se demues a en la p oposici´on
siguien e, an es eamos una de inici´on necesa ia pa a pode asegu a la:
De inici´on 6.3. Sea Xun espacio m´e ico al que pa a cada pa de pun os
x, y ∈X, y un eal 0 ≤α≤1, hay un pun o z∈X al que d(x, z) + d(z, y) =
d(x, y) y d(x, z) = αd(x, y).En onces Xse llama espacio m´e ico geod´esico ( e
[15]).
P oposici´on 6.1. Si Xes un espacio m´e ico geod´esico, en onces el juego de
adio (N, II )sob e Xes subadi i o.
Demos aci´on. Conside emos un pa de coaliciones S1yS2. Tenemos que p oba
que
II(S1∪S2)≤ II (S1) + II (S2).
Pa a j= 1,2, sean cjy jel cen o y el adio de la bola m´as peque˜na que
encie a los pun os Sj∪{ 0}, espec i amen e.
Sea P(c1, c2) el camino mas co o en X, conec ando c1yc2. Deno emos
d(c1, c2) como la dis ancia de P(c1, c2). En onces, d(c1, c2)≤d(c1, 0)+d( 0, c2)≤
1+ 2.
Supongamos sin p´e dida de gene alidad que 2≥ 1. Si 2≥ 1+d(c1, c2),
69

Cap´ı ulo 6. Juegos de Radio y Di´ame o
en onces un cen o es ablecido en c2ga an iza ´a un adio de cobe u a 2pa a
odos los nodos en S1∪S2∪{ 0}. Po lo an o, II(S1∪S2)≤ 2= II (S2).
Si 1≤ 2≤ 1+d(c1, c2), en onces conside emos un cen o es ablecido en el
pun o c∗, al que d(c1, c∗)=(d(c1, c2)+ 2− 1)/2, y d(c2, c∗)=(d(c1, c2)− 2+
1)/2. Es ´acil comp oba que es e cen o ga an iza ´a un adio de cobe u a de
d(c1, c2)+ 1+ 2)/2≤ 1+ 2pa a odos los nodos de S1∪S2∪{ 0}. (Obse emos
que 0es ´a en la in e secci´on de las bolas m´as peque˜nas que encie an S1∪{ 0}
yS2∪{ 0}). Po lo an o, II(S1∪S2)≤ II (S1) + II (S2).
6.1. Espacios m´e icos de ed
Aho a amos a conside a espacios m´e icos espec´ı icos que se es udian con
ecuencia en el an´alisis de localizaci´on y mues an que en es os casos el co e
puede se ep esen ado po un n´ume o polin´omico de desigualdades lineales. En
gene al, necesi a emos un n´ume o exponencial de desigualdades lineales pa a
ep esen a el co e de un juego, (6.2).
En p ime luga , amos a conside a el caso donde X=A(G), es espa-
cio m´e ico inducido po un g a o conec ado no di igido G= (V, E), V =
{ 0, 1, . . . , n}, y sus longi udes de a is a posi i as. Supongamos que el con-
jun o de jugado es Nsa is ace que N⊆V { 0}. Adem´as, conside emos sin
p´e dida de gene alidad que N={ 1, 2, . . . , k}, donde k=|N|.
P oposici´on 6.2. Conside emos el juego de adio (N, II ), de inido sob e un
espacio m´e ico de ed A(G), inducido po el g a o G= (V, E)con longi ud de
a is a posi i a. En onces, hay una colecci´on de subconjun os de N, Si,j
p,q,( i, j)∈
E, p, q∈N∪{ 0},(i, j, p, q)∈I, al que |I|=O(m|N|2)y
C(N, II) = nx∈RN
+:x(N) = II (N), x(Si,j
p,q ≤ II(Si,j
p,q),∀(i, j, p, q)∈Io.
Como esul ado, la pe enencia al co e, adem´as de e que el co e es no
ac´ıo, puede se comp obada en iempo ue emen e polinomial.
Demos aci´on. P ime o obse emos que, si N={ 1, . . . , n}, II (N) es igual
al di´ame o de un ´a bol de expansi´on de di´ame o m´ınimo de V. Es e ´a bol de
expansi´on, digamos T∗, esuel e el p oblema con inuo (o absolu o) de 1-cen o
70
Cap´ı ulo 6. Juegos de Radio y Di´ame o
sob e G, y puede encon a se en iempo O(mn +n2logn), ( e [8]).
M´as gene almen e, cuando N⊆V { 0}, II(S) se de ine como la longi ud
del di´ame o de un ´a bol spanning de di´ame o m´ınimo de S∪{ 0},∀S⊆N. Tal
´a bol, digamos T∗(S), esuel e el p oblema de un cen o con inuo pa a el subcon-
jun o de los nodos S∪{ 0}, y se puede encon a en iempo O(mn +n2logn).
Reco demos que el p oblema con inuo de 1-cen o pa a algunos subconjun os
V0⊆V, de ine la ecindad de adio m´as peque˜na es el espacio m´e ico A(G),
que ecub e V0.
Adem´as, T∗(S) iene la siguien e p opiedad. Hay una a is a de G, digamos
( i, j), al que el 1-cen o de T∗(S) es ´a sob e es a a is a, de nue o e [8], y
II(S) = d( p, i) + l( i, j) + d( j, q),
pa a algunos nodos p, q∈S∪{ 0}.
En o al hay a lo m´as O(|N|2) cen os de ´a boles de di´ame o m´ınimo sob e
la a is a ( i, j). Cada uno de es os cen os Ci,j
p,q es ´a asociado con un adio de
la o ma:
i,j
p,q = (d( p, i) + l( i, j) + d( j, q))/2.
Despu´es, pa a cada cen o ci,j
p,q al que d( 0, ci,j
p,q)≤ i,j
p,q, de inamos la coali-
ci´on m´axima:
Si,j
p,q ={u∈N:d(u, ci,j
p,q)≤ i,j
p,q}.
Sea
I={(i, j, p, q):( i, j)∈E, p, q∈N∪{ 0}, d( o, ci,j
p,q)≤ i,j
p,q}
Aho a conside emos la coalici´on S⊆N. En onces, a pa i de lo an e io
se deduce que hay un cie o cen o ci,j
p,q y adio i,j
p,q, al que II (S) = 2 i,j
p,q,
yS⊆Si,j
p,q. Po lo an o, la mono on´ıa del juego implica que la es icci´on
del co e x(S)≤ II(S) que se deduce po la es icci´on xSi,j
p,q≤ II Si,j
p,q.
Es o alida la ep esen aci´on e icien e del n´ucleo indicada en la p oposici´on.
Finalmen e, obse emos que u ilizando los algo i mos an e io es pa a esol e
p oblemas de un cen o, se necesi a iempo polinomial pa a cons ui oda la
colecci´on nSi,j
p,qo,( i, j)∈E, p, q∈N∪{ 0},(i, j, p, q)∈I. En pa icula , la
71
Cap´ı ulo 6. Juegos de Radio y Di´ame o
p opiedad de pe enencia al co e, como se no ac´ıo puede se comp obada en
iempo ue emen e polinomial po el algo i mo que encon amos en [22]. Es o
comple a la p ueba. 
Obse aci´on 6.1. Rela i o al MRLG de inido sob e un espacio m´e ico de
ed podemos supone sin p´e dida de gene alidad que el g a o subyacen e G=
(V, E) es un g a o comple o, y sus longi udes de a is as sa is acen la desigualdad
iangula . En o o caso, siemp e pod emos in oduci una a is a en e cualquie
pa de nodos y es ablece su longi ud igual a la dis ancia en A(G) en e el pa .
Conside emos una coalici´on S. Obse emos que en es e caso cada u a simple
de T∗(S) iene a lo m´as 3 a is as. Sin emba go, incluso en es e caso T∗(S) no es
necesa iamen e un sub´a bol de G 0(S), el subg a o de Ginducido po el conjun o
de nodos S∪{ 0}. Como ejemplo conside emos el g a o comple o con conjun o de
nodos V={ 0, 1, 2, 3}.Con longi udes de las a is as ( 3, 0),( 3, 1),( 3, 2)
igual a 1, y la longi ud del es o igual a 2. Cuando S={ 1, 2}, T∗(S) es la
es ella cen ada en 3, que no es ´a en G 0(S).
Co ola io 6.1. Si Ges un ´a bol, hay una colecci´on de subconjun os de N, {Sp,q},
p, q∈N∪{ 0}, p, q ∈I0, al que |I0|=O(|N|2), y el co e del juego (N, II )
es a de ino po :
C(N, II) = {x∈Rn
+:x(N) = II (N).x(Sp,q)≤ II(Sp,q),∀p, q ∈I0}
Demos aci´on. Si Ges un ´a bol, el n´ume o o al de cen os de los sub´a boles
de exppansi´on de di´ame o m´ınimo es solo O(|N|2). En es e caso, cada pa de
nodos, p, qapo a un cen o candida o, deno ado po cp,q, el pun o medio
de la u a simple ´unica que conec a pcon q. Si d( 0, cp,q)≤d( p, q)/2, la
coalici´on m´aximal espec i a se de ine en onces po
Sp,q ={u∈N:d(u, cp,q)≤d( p, q)/2}
Sea I0={(p, q) : d( 0, cp,q)≤d( p, q)/2}.En onces el esul ado gene al en la
p oposici´on an e io conduce a la desc ipici´on m´as sencilla de C(N, II ) dada
en el co ola io. 
Obse aci´on 6.2. Dado un g a o conec ado no di igido G= (V, E), con
72
Cap´ı ulo 6. Juegos de Radio y Di´ame o
V={ 0, 1, . . . , n}, obse amos que el espacio m´e ico espec i o X=A(G),
inducido po Gy sus longi udes de a is as posi i os, es geod´esico.
El Ejemplo 6.3 ilus a que cuando el conjun o de jugado es Nes el subcon-
jun o p opio V { 0}, el co e del juego de locaci´on adial puede se ac´ıo. Sin
emba go, oda ´ıa no sabemos si el co e del juego (N, II ) de inido sob e el es-
pacio X=A(G) es siemp e no ac´ıo en el caso donde G= (V, E) es un g a o no
di igido conec ado gene al y N={ 1, . . . , n}. Nos e e imos a es e caso como
el juego de localizaci´on comple o de adio m´ınimo (CMRLG) sob e edes.
Aho a nos cen amos en algunas obse aciones y casos especiales del juego
de adio comple o, CMRLG. P ime o obse amos que la unci´on II no puede
se submodula si la g ´a ica Gcon iene un ciclo.
Ejemplo 6.4. Conside emos el 4-ciclo con longi ud de a is a 1, y V={ 0, 1, 2, 3}.
Como en la igu a:
1
0
3
2
1
1 1
1
Sea S1={ 1, 2}yS2={ 3, 2}. En onces, II (S1) = II(S2)=2, II (S1∪
S2)=3, II(S1∩S2) = 2, y po lo an o II(S1∪S2) + II (S1∩S2)> II(S1) +
II(S2).
Hemos obse ado en la in oducci´on que hay una asignaci´on del co e pa a
el juego de di´ame o (N, I) que di ide I(N) en e un pa de jugado es que
co esponden al di´ame o de V. Po el con a io, el n´ucleo del juego comple o
de localizaci´on de adio (N, II ) no puede con ene en gene al una asignaci´on
en la que s´olo 2 jugado es paguen un cos e posi i o. Po ejemplo, en el Ejemplo
6.4, d( 0, 2) = 2, y d( 0, 1) = d( 0, 3) = 1. Sin emba go, la asignaci´on del
co e ´unica es el ec o (1,1,1).
73
Cap´ı ulo 6. Juegos de Radio y Di´ame o
Como an es, obse amos que pa a cada subconjun o S⊆N, hay un sub-
conjun o Sj, j ∈Jyk= 1, . . . , c1
j(n, d), al que la es icci´on x(S)≤ II (S), es
dominada po la es icci´on xS1
j(k)≤ II(Sj). Es o comple a la p ueba. 
Con la excepci´on del caso p=∞, oda ´ıa no se conoce si C(N, II ) es no
ac´ıo pa a odo espacio m´e ico lpsob e Rd. Asumimos sin p´e dida de gene a-
lidad que i6= 0,∀i= 1, . . . , n.
Teo ema 6.4. El co e del juego (N, II ), de inido en el espacio m´e ico l∞
sob e Rd, es no ac´ıo. Espec´ı icamen e, C(N, I) = C(N, II ).
Adem´as, si D(N0) = d( 0, j), pa a alg´un j∈N, la dimensi´on de C(N, II )
es n−1, y hay un x∗∈C(N, II ) al que x∗
>0, pa a cualquie ∈N.
Tambi´en, si D(N0) = d( i, j), pa a alg´un i, j∈Nyd( i, j)< d( i, 0) +
d( j, 0), en onces la dimensi´on de C(N, II )es n−1,y hay un x∗∈C(N, II)
al que x∗
>0, pa a cualquie ∈N.
Demos aci´on. Cuando p=∞, es ´acil e que pa a cualquie conjun o S ene-
mos I(S) = D(S∪{ 0})=2R(S∪{ 0}) = II (S). Po lo an o, C(N, I) =
C(N, II), y la p opiedad de co e no ac´ıo se sigue de la Obse aci´on 6.3.
Supongamos sin p´e dida de gene alidad que D(N0) = d( 0, 1). Sea α=
(α1, α2, . . . , αn) un ec o eal a bi a io que e i ica 0 ≤α0≤m´ın =1,...,n d( 0, ),
α1=Pn
j=2 αjyαj≥0, j = 2, . . . , n. Conside emos aho a una coalici´on S⊆N.
Si 1∈S, en onces xα(S)≤α1≤m´ın =1,...,n d( 0, )≤ II (S).
Pa a e que la dimensi´on a ´ın de C(N, II ) en es e caso es n−1, amos a
p oba que el co e con iene n ec o es independien es. Uno de ellos es el ec o
x1= (x1
1, . . . , x1
n), de inido po x1
1=d( 0, 1) y x1
j= 0,pa a j= 2,3, . . . , n.
Los o os n−1 ec o es se de inen como sigue:
Sea εun eal posi i o su icien emen e peque˜no, y conside emos las n−1
asignaciones independien es del co e {xα(q)}, q = 2, . . . , n, donde α(q) es el
ec o de inido po α1(q) = ε, αq(q) = εyα (q) = 0, pa a cualquie =
2, . . . , n; 6=q. La asignaci´on x∗=Pn
q=2 xα(q)/(n−1) es a en el co e y iene
componen es es ic amen e posi i as.
Aho a, supongamos sin p´e dida de gene alidad que D(N0) = d( 1, 2) y
d( 1, 2)< d( 0, 1) + d( 0, 2). Sean δ1, δ2 eales posi i os que e i ican 0 <
δ1< d( 0, 1),0< δ2< d( 0, 2), y δ1+δ2=d( 1, 0) + d( 2, 0)−d( 1, 2).
80

Cap´ı ulo 6. Juegos de Radio y Di´ame o
Sea α= (α1, α2, . . . , αn) un ec o eal a bi a io e i cando α1≤d( 1, 0)−
δ1, α2≤d( 2, 0)−δ2,0≤α1+α2≤m´ın =1,...,n d( 0, ),0≤α1+α2≤
m´ın δ1, δ2, α1+α2=Pn
j=3 αjyαj≥0, j = 1, . . . , n.
Demos a emos que la asignaci´on:
xα= (d( 0, 1)−δ1−α1, d( 0, 2)−δ2−α2, α3, . . . , αn)
es a en C(N, II). P ime o, po de inici´on xα(N) = d( 1, 2) = D(N0) =
II(N). Aho a conside emos la coalici´on S⊆N. Si 1, 2∈S, en onces xα(S)≤
d( 1, 2) = II(S). Si 1∈S, 26=S, en onces xα(S)≤d( 1, 0)−δ1, α1+
Pn
q=3 αq≤d( 1, 0)−α2−α1+Pn
q=3 αq≤d( 1, 0)≤ II(S). Simila men e, si
16=S, 2∈S, ob enemos xα(S)≤d( 2, 0)≤ II (S). Finalmen e, supongamos
que 1, 26=S. En onces xα(S)≤α1+α2≤m´ın =1,...,n d( 0, )≤ II (S).
Pa a e que la dimensi´on a ´ın de C(N, II ) en es e caso es n−1, demos-
emos que el co e con iene n ec o es independien es. Dos de ellos son los ec-
o es x1= (x1
1, . . . , x1
n) y x2= (x2
1, . . . , x2
n), de inidos po x1
1=d( 1, 0), x1
2=
d( 1, 2)−d( 1, 0), x1
j= 0 pa a j= 3,4, . . . , n, x2
1=d( 1, 2)−d( 2, 0), x2
2=
d( 2, 0) y x2
j= 0 pa a j= 3,4, . . . , n. Los o os n−2 ec o es se de inen como
sigue:
Sea εun eal posi i o su icien emen e peque˜no, y conside emos la colecci´on
de n−2 asignaciones independien es del co e {xα(q)}, q = 3, . . . , n, donde α(q)
es un ec o de inido po α1(q) = ε, αq(q) = ε, y α (q) = 0, pa a cualquie
= 2, . . . , n; 6=q. La asignaci´on x∗= (x1+x2+Pn
q=3 xα(q))/n es a en el co e
y sus componen es son es ic ame e posi i as. Es o comple a la p ueba. 
Aumen ando el esul ado del eo ema an e io , el siguien e ejemplo ilus a
que cuando no se sa is acen las condiciones del eo ema, la dimensi´on del co e
puede incluso se ce o. Espec´ı icamen e, pa a cualquie n´ume o de jugado es,
incluso en el caso plano l∞, el co e puede se un ´unico pun o donde solo dos
jugado es compa an el cos e o al, a pesa de que la dis ancia de cada jugado
al se ido 0sea posi i a.
Ejemplo 6.10. Conside emos el conjun o de pun os N0={ 0, 1, . . . , k}don-
de 0= (0,0), 1= (0,1), 2= (0,−1), 3= (1,0) y i= (ai,0),0< ai<
1,pa a i= 4,5, . . . , k. Dado que I(S) = 2, si 1, 2⊆N, y I(S)≤1, en o o
81
Cap´ı ulo 6. Juegos de Radio y Di´ame o
caso, es ´acil p oba que C(N, I) = C(N, II) = {(1,1,0,...,0)}.
Co ola io 6.2. El co e del juego (N, II )de inido en el espacio m´e ico l1es
no ac´ıo. Espec´ı icamen e, C(N, I) = C(N, II ).
Demos aci´on. Dado que la no ma ec ilineal l1, es equi alen e a la no ma l∞
sob e el plano, pa a cualquie subconjun o S, D(S∪{ 0})=2R(S∪{ 0}) pa a
el caso del plano. Po lo an o, el co e del espec i o juego de adio m´ınimo en
el plano es no ac´ıo. 
6.3.1. Espacios eucl´ıdeos
Vol iendo al caso eucl´ıdeo, en gene al, la igualdad I(N) = II (N) no se
e i ica incluso en el caso plano. De la P oposici´on 6.1 se deduce que la unci´on
ca ac e ´ıs ica II(S) es subaddi i a ambi´en pa a el modelo eucl´ıdeo. Sin em-
ba go, no se sigue del an´alisis gene al en secciones an e io es que el n´ucleo del
juego plano eucl´ıdeo sea no ac´ıo.
A pesa de ello, amos a p oba que C(N, II ) es no ac´ıo pa a el caso del
plano eucl´ıdeo. M´as espec´ı icamen e, hay una asignaci´on b´asica donde al menos
3 jugado es (pun os) pagan can idades posi i as. Es os son pun os que de inen
C(V), el c´ı culo m´ınimo en el plano que encie a el conjun o V.
Teo ema 6.5. El co e C(N, II )del juego de localizaci´on de adio m´ınimo
(N, II)en el caso del plano eucl´ıdeo es no ac´ıo.
Demos aci´on. Ve ap´endice de [17].
Obse aci´on 6.4. En el juego de localizaci´on de adio m´ınimo (N, II), pa a
cada coalici´on S, II se de ine como el doble del alo de la soluci´on pa a el
p oblema de un cen o pa a el conjun o de nodos S∪{ 0}. Del mismo modo,
podemos conside a los juegos de localizaci´on de inidos po o os c i e ios de
op imizaci´on comunes que se usan con ecuencia en los modelos de localizaci´on
de ins alaciones. Po ejemplo, conside emos el juego de localizaci´on de mediana
m´ınima, (N, III), donde pa a cada coalici´on S, III se de ine como el alo de
la soluci´on al p oblema 1-mediana pa a conjun o de los nodos S∪{ 0}.
Obse amos que desde del pun o de is a coope a i o la de inici´on an e io
ni siquie a induce la p opiedad deseable de la subadi i idad. Po lo an o, los
82
Cap´ı ulo 6. Juegos de Radio y Di´ame o
jugado es pueden no ene incen i os pa a coope a , como se mues a en el
siguien e ejemplo.
Ejemplo 6.11. Conside emos una u a de 4 nodos con el siguien e conjun o
de a is as: E={( 1, 0),( 0, 2),( 2, 3)}. A is as de longi ud 1. Es ´acil e
que III (N) = 4, III ({ 1}) = 1 y III({ 2, 3}) = 2. Po lo an o, III ({ 1}) +
III ({ 2, 3})=3<4 = III (N). El co e es ac´ıo en es e ejemplo, ya que el
conjun o de es icciones, x1≤1, x2+x3≤2 y x1+x2+x3= 4 es inconsis en e.
83
Cap´ı ulo 6. Juegos de Radio y Di´ame o
84
Cap´ı ulo 7
Conclusiones
Pa a ealiza es e T abajo Fin de G ado he necesi ado los conocimien os
adqui idos, p incipalmen e, en dos asigna u as del G ado en Ma em´a icas: P o-
g amaci´on Ma em´a ica y M´e odos de In es igaci´on Ope a i a. Donde conoc´ı
como esol e un p og ama lineal de op imizaci´on y la u ilidad del espec i o
p og ama dual.
Como conclusi´on gene al del T abajo Fin de G ado, podemos deci que una
o ma e ec i a de esol e p oblemas de asignaci´on de cos es es usa la eo ´ıa
de juegos coope a i os. El Teo ema de Bonda e a-Shapley nos p opo ciona una
condici´on necesa ia y su icien e pa a que un juego coope a i o enga co e no
ac´ıo. Podemos en ende el co e como soluci´on de un juego coope a i o, aunque
en algunos casos el co e es ac´ıo, si e i ica las condiciones del Teo ema de
Bonda e a-Shapley, en o os casos puede habe m´as de un pun o en el co e, lo
que nos p opo ciona ´a m´as de una soluci´on.
Aho a eamos las conclusiones espec´ı icas de cada cap´ı ulo.
Respec o al Juego de Asignaci´on podemos conclui que iene co e no ac´ıo,
luego siemp e pod emos ob ene al menos una soluci´on, aunque en muchas oca-
siones el co e no p opo ciona ´a una soluci´on ´unica.
De los Juegos de P oducci´on Lineal, como en los de Asignaci´on, hemos p o-
bado que su co e es no ac´ıo. Adem´as hemos encon ado un pun o del co e, a
a ´es del espec i o p og ama dual. Aqu´ı hemos a˜nadido una aplicaci´on de una
si uaci´on de p oducci´on lineal usando CPLEX, la cual hemos esuel o median e
85

Cap´ı ulo 7. Conclusiones
NEOS-SERVER, donde hemos comp obado como lo que hemos desa ollado de
o ma e´o ica se e i ica en un ejemplo.
Adem´as, al abaja con CPLEX y NEOS-SERVER he ap endido a esol e
p og amas lineales de op imizaci´on de o ma compu acional.
Despu´es hemos in oducido lo que es una si uaci´on de localizaci´on y los
juegos de localizaci´on pa a es as. Podemos a i ma que exis en condiciones ne-
cesa ias y su icien es pa a que el co e de es os juegos sea no ac´ıo, y as´ı ene
soluciones pa a dichas si uaciones. Hemos desc i o es ipos de juegos de lo-
calizaci´on, donde en cada caso hemos is o ejemplos y hemos p obado que el
co e de cada juego es no ac´ıo. Las si uaciones de localizaci´on son un caso muy
p ´ac ico sob e el que hay una g an a iedad de casos es udiados.
En el caso de Juegos de Radio y Di´ame o hemos abajado en di e en es
espacios m´e icos, hemos is o ejemplos de dis in as si uaciones con co e ac´ıo
o no ac´ıo, y dis in as p opiedades pa a los juegos de adio. Hemos de inido el
co e pa a el caso de es os juegos dependiendo del espacio donde abaj´asemos
y las di e encias en e los dis in os juegos (MSTG s MRLG). Tambi´en hemos
abajado sob e Rddonde hemos ex endido, la de inici´on del co e y que es e
es no ac´ıo en el caso eucl´ıdeo, en el caso del juego de localizaci´on de adio
m´ınimo. Po lo an o, los juegos coope a i os, en muchos casos, p opo cionan
una soluci´on pa a es as si uaciones median e el co e.
Finalmen e, podemos conclui que el co e es una buena he amien a pa a
soluciona p oblemas de asignaci´on de cos es, aunque no siemp e exis a, o posea
m´as de una impu aci´on.
Como conclusi´on pe sonal de es e T abajo Fin de G ado, se han desc i o
si uaciones eales, de la ida co idiana, donde las ma em´a icas, de la mano de
la Teo ´ıa de Juegos, pueden esol e con lic os in e pe sonales. De ini i amen e
las ma em´a icas i en en e noso os y, como hemos desa ollado, nos ayudan
a soluciona una g an a iedad de si uaciones co idianas de o ma e ec i a.
En conc e o en es e abajo hemos mos ado si uaciones an co idianas co-
mo: asigna alumnos a un colegio; o ganiza dis in os ayun amien os pa a cons-
ui un ae opue o, con sus espec i as in aes uc u as; o, que bene icio pod ´an
86
Cap´ı ulo 7. Conclusiones
ob ene a ias emp esas al pone en com´un sus p oduc os pa a gene a de e -
minados bienes, que se pueden ende en el me cado a un p ecio ijo, pueden
se analizados cuan i a i amen e con ´ecnicas ma em´a icas.
Los cien ´ı icos, en nues o caso ma em´a icos, enemos el debe de ansmi-
i odo lo an e io y mos a al mundo de una o ma amena y a ac i a la
impo ancia de la ciencia y su g an a iedad de aplicaciones.
87
Cap´ı ulo 7. Conclusiones
88
Ap´endice A
Aplicaci´on del Juego de
P oducci´on Lineal
Hoy en d´ıa disponemos de bas an es so wa e pa a esol e p og amas linea-
les de op imizaci´on como el XP ess, Gu obi o CPLEX. Noso os hemos elegido
CPLEX, pa a implemen a lo hemos usado la p´agina web www.neos-se e .o g,
donde podemos abaja con NEOS-SERVER, aqu´ı encon amos un se icio
g a ui o o ecido po la Uni e sidad de Wisconsin. En NEOS-SERVER encon-
a emos m´as de 60 m´e odos pa a esol e dis in os p og amas de op imizaci´on
en e ellos los nomb ados an e io men e.
Pa a esol e un p og ama, como los que noso os enemos que esol e , hay
que en ia a NEOS-SERVER es a chi os.
El p ime o de ellos iene que se un a chi o con ex ensi´on ”.mod”, aqu´ı debemos
e leja nues o modelo, es e es el c´odigo de nues o modelo pa a el p og ama
p imal:
1pa am n ;
2pa am m;
3se J := {1 . . n }; #conjun o de a i a b l e s de d e c i s i´o n
4se I := {1 . .m}; #conjun o de e s i c c i o n e s
5
6pa am C {J}>= 0 ; #c o e i c i e n e s de l a u nci´on o b j e i o
7pa am A {I , J}>= 0 ; #ma iz de l o s c o e i c i e n e s de l a s
es icciones
8pa am B {I}>= 0 ; # ec o d e l lado de echo de l a s e s i c c i o n e s
89