-
1
BENEMÉRITA UNIVERSIDAD
AUTÓNOMA DE PUEBLA
FACULTAD DE CIENCIAS FÍSICO MATEMÁTICAS
LICENCIATURA EN ACTUARÍA
TÍTULO DE LA TESIS
“ESTUDIO Y APLICACIÓN DE LA TEORÍA DE JUEGOS
PARA LA ASIGNACIÓN DE COSTOS”
QUE PARA OBTENER EL TÍTULO DE
LICENCIADA EN ACTUARÍA
PRESENTA
EVELYN MORANCHEL GARCÍA
DIRECTOR DE TESIS
JOSÉ DIONICIO ZACARÍAS FLORES
PUEBLA, PUE. DICIEMBRE 2017
-
2
Agradecimientos
Dedico este trabajo de tesis a mis padres Juan José Moranchel Dávila, Ma. Aurora
García Andrade y a mi hermana Marlene Moranchel García quienes siempre me han
apoyado incondicionalmente en el transcurso de mi vida y de mi carrera universitaria; a
ustedes que han estado presentes siempre, son mi mano derecha, los adoro.
A José Manuel Márquez Camarillo, porque tu ayuda a sido fundamental. Siempre
has estado conmigo en los momentos más difíciles. La realización de este trabajo no fue
fácil pero siempre estuviste motivándome y brindándome tú ayuda. Te lo agradezco
muchísimo. Te quiero.
A mi profesor y director de tesis José Dionicio Zacarías Flores, por haberme tenido
paciencia y haberme guiado durante todo el desarrollo de esta tesis; por su aportación, sus
consejos y sus observaciones a lo largo mi carrera. Sin su apoyo esto no hubiera sido
posible. Gracias.
A todos mis profesores de la Lic. en Actuaría, quienes se han tomado el arduo
trabajo de transmitirme sus conocimientos en el campo y demás temas correspondientes a
mi profesión. Gracias.
Finalmente, gracias a la vida por este triunfo y gracias a todas las personas que me
conocen, me apoyaron y creyeron en mí y en la realización de esta tesis. Gracias a todos
por ser parte de mi enseñanza y aprendizaje.
¡Muchas Gracias!
-
3
Introducción
Durante siglos, el hombre se ha interesado por los juegos, el juego es una de las
principales actividades que realizamos todos y cada uno de nosotros desde nuestra infancia.
La Teoría de Juegos ha demostrado una gran versatilidad para la resolución de problemas
actuales. Partió de la Teoría Económica y la Teoría Matemática para estudiar la interacción
entre los agentes económicos y analizar el resultado que tendrían sobre los participantes.
En los últimos 30 años, la Teoría de Juegos ha experimentado una expansión muy
significativa en la investigación y en diversas áreas de estudio, como en la Economía, la
Psicología, la Política, o la Computación. En términos generales, podemos decir que la
Teoría de Juegos estudia los dilemas que se le presentan al hombre en la vida cotidiana.
Este trabajo tiene como objetivos principales, servir como una ayuda de inducción a
la Teoría de Juegos Cooperativos y en particular, a su aplicación para la resolución de
problemas de asignación de costos, consolidar ciertos conceptos que son de gran
importancia para entender la Teoría de Juegos Cooperativos; mostrar un ejemplo práctico
de interés personal y hacer ver que la Teoría de Juegos nos ayuda a generar soluciones
factibles y justas que brindan una mejor asignación que los métodos de solución clásicos,
que son a los que generalmente estamos acostumbrados, además de reforzar esta idea
desarrollando un programa en VBA Excel.
A continuación, se describirá brevemente el contenido de este trabajo: el Capítulo 1
tiene un carácter meramente introductorio; en él, se presentan de forma extensiva los
antecedentes históricos de la Teoría de Juegos, brindando un espacio para narrar la historia
y vida de uno de los personajes más importantes que contribuyeron al nacimiento de la
Teoría de Juegos al publicar el libro “Theory of Games and Economic Behavior” en el año
de 1944, el matemático John von Neumann (1903-1957); de igual manera se hace hincapié
en mostrar mediante el “dilema del prisionero” el concepto clave creado por von Neumann
conocido como el Teorema Minimax y finalmente se hace referencia de aquellos conceptos
básicos e imprescindibles para la comprensión de este trabajo.
En el Capítulo 2 y el Capitulo 3 se presentan la introducción y el desarrollo de los
juegos cooperativos. El primero de ellos introduce a esta idea trabajando los juegos de
-
4
suma cero entre dos personas con y sin punto de equilibrio, dando paso a la utilización de
diversas estrategias y la definición y aplicación del teorema Minimax de von Neumann. El
siguiente capítulo brinda los conceptos más importantes de la Teoría de Juegos de manera
coalicional o cooperativa y en particular, se estudiarán los conceptos más significativos: el
Core, el Nucleolus y el Valor de Shapley.
El Capítulo 4 introduce al concepto de asignación de costos que es la idea principal
de este trabajo, comenzando por saber qué es un costo desde el punto de vista económico,
su clasificación y los métodos de costeo contables y económicos tradicionales. Al final se
hace referencia a la utilización del método de Teoría de Juegos.
En el Capítulo 5 se analiza el artículo “AN APPLICATION OF GAME THEORY:
COST ALLOCATION” de Jean Lemaire (Harry J. Loman) [16] profesor en seguros y
gestión de riesgos en la Universidad Wharton; ya que el problema de la asignación de
costos es uno de los más difíciles en las economías pequeñas y de gran escala, este artículo
ejemplifica esta situación de manera intuitiva, además de estudiar dos variaciones
adicionales al concepto de Nucleolus como son el Nucleolus Proporcional y el Nucleolus
Disruptivo.
En el Capítulo 6 se da paso a la generación de un problema de asignación de costos
de interés personal denominado “Seguro de Vida Grupo”. En él, se estudia cómo un
empresario puede llegar a sufrir pérdidas mayores por comisión al momento de asegurar a
sus empleados y cómo la Teoría de Juegos brinda una solución más factible que la
utilización de los métodos de asignación de costos tradicionales. Además, se pretende
mostrar la solución al mismo problema mediante la realización de un programa creado en
VBA Excel.
Con respecto a la presentación de conceptos y de ideas en este trabajo, cada uno de
ellos se elaboró de la manera más minuciosa posible, además de brindar una serie de
ejemplos para mejorar su comprensión.
-
5
ÍNDICE GENERAL
Introducción 3
CAPÍTULO 1. TEORÍA DE JUEGOS ........................................................................................... 8
1.1 Introducción .................................................................................................................................. 8
1.2 Antecedentes históricos ............................................................................................................... 10
1.3 Utilidad del teorema Minimax de von Neumann ........................................................................ 13
CAPÍTULO 2. JUEGOS DE SUMA CERO ................................................................................. 22
2.1 Introducción ................................................................................................................................ 22
2.2 Juegos de suma cero entre dos personas con punto de equilibrio ............................................... 22
2.3 Estrategias mixtas para juegos de suma cero entre dos personas sin punto de equilibrio ........... 25
2.4 Estrategias dominadas ................................................................................................................. 35
2.5 La mejor estrategia de respuesta ................................................................................................. 39
CAPÍTULO 3. JUEGOS COOPERATIVOS ............................................................................... 41
3.1 Introducción ................................................................................................................................ 41
3.2 Juegos cooperativos..................................................................................................................... 42
3.3 Conjunto de imputaciones ........................................................................................................... 49
3.4 El Core......................................................................................................................................... 53
3.5 El Nucleolus ................................................................................................................................ 57
CAPÍTULO 4. ASIGNACIÓN DE COSTOS ............................................................................... 69
4.1 Introducción ................................................................................................................................ 69
4.2 ¿Qué es el costo? ......................................................................................................................... 70
4.3 Clasificación de costos ................................................................................................................ 71
4.4 Métodos de costeo ....................................................................................................................... 74
4.5 Métodos para el cálculo de costos ............................................................................................... 81
CAPÍTULO 5. “AN APPLICATION OF GAME THEORY: COST ALLOCATION” .......... 94
5.1 Introducción ................................................................................................................................ 94
5.2 Aplicación de la Teoría de Juegos: Asignación de costos ........................................................... 95
5.3 Estudio de un problema de asignación de interés ...................................................................... 109
CAPÍTULO 6. SEGURO DE VIDA GRUPO ............................................................................. 117
6.1 Introducción .............................................................................................................................. 117
-
6
6.2 Problema de asignación de interés “Seguro de Vida Grupo” .................................................... 118
6.3 “Seguro de Vida Grupo” Resultados ......................................................................................... 128
6.4 CSG Programa .......................................................................................................................... 132
6.4.1 Implementación ...................................................................................................................... 133
6.4.2 Ejecución ................................................................................................................................ 139
CONCLUSIÓN .............................................................................................................................. 150
ANEXOS………………………………………………………………………………………..…152
BIBLIOGRAFÍA ........................................................................................................................... 154
-
7
“ESTUDIO Y APLICACIÓN DE LA TEORÍA DE JUEGOS
PARA LA ASIGNACIÓN DE COSTOS”
EVELYN MORANCHEL GARCÍA
Diciembre 2017
-
CAPÍTULO 1 1.1 Introducción
8
CAPÍTULO 1. TEORÍA DE JUEGOS
1.1 Introducción
El juego es una de las principales actividades que realiza el ser humano desde su
niñez; como lo indica la psicología, activa procesos físicos, educativos, sociales o
emocionales que permiten que el hombre se desarrolle en su entorno y adopte una conducta
que le permita responder ante situaciones conflictivas que se le presenten en la vida real [2].
Un juego es una situación en la que compiten dos o más jugadores que emplean su
imaginación o ciertas herramientas y que además, siguen un determinado número de reglas
con el fin proporcionar entretenimiento, diversión o cumplir algún objetivo, tomando en
cuenta que se puede ganar como se puede perder. Dentro de un juego, se supone que todos
los participantes son racionales. Algunos ejemplos de ello son: el ajedrez, el póker, los
juegos de mesa, los juegos deportivos o incluso en el ámbito de los negocios, lanzar un
producto al mercado.
Como es de esperarse, cada jugador intentará maximizar su utilidad o ganancia,
pero hay que tomar en cuenta que el resultado no sólo dependerá de lo que un solo jugador
elija, sino que también, dependerá de las estrategias que utilicen los demás jugadores.
Durante siglos, el hombre se ha interesado por los juegos, Luca Paccioli (siglo XV),
Tartaglia (siglo XVI) y Cardano (siglo XVI) comenzaron a resolver problemas de juegos de
azar abordando juegos con apuestas, mientras que Pierre Fermat y Blaise Pascal (siglo
XVII) por mencionar algunos, se interesaron por resolver situaciones que involucraban
juegos de azar matemáticamente, dando así el inicio a la Teoría de la Probabilidad [14]. La
Teoría de la Probabilidad estuvo limitada algún tiempo a los juegos de azar. Durante el
siglo XVIII comenzó un auge en la Estadística (aunque surgió desde los inicios de la
humanidad) que complementó las bases teóricas de las probabilidades de juegos de azar,
permitiendo el estudio de los datos obtenidos probabilísticamente e interpretando esa
información para tomar decisiones y afrontar riesgos ante situaciones impredecibles [13].
-
CAPÍTULO 1 1.1 Introducción
9
Sin embargo, la Teoría de Juegos no se basa en estudiar la probabilidad de un juego
ni estudiar los datos obtenidos de él, sino que su objetivo principal, es estudiar el
comportamiento estratégico entre los contrincantes dentro de un mismo juego.
Un comportamiento estratégico comienza por la formulación de un juego que, cómo
ya se sabe, consta de un número de jugadores, de acciones posibles para cada jugador y un
conjunto de reglas. Más aún, el comportamiento estratégico nació como un concepto
económico que representa a un conjunto de estrategias que toma una empresa en torno al
mercado con la única finalidad de maximizar sus beneficios [1].
En la actualidad, la Teoría de Juegos tiene bastantes aplicaciones, por ejemplo: en la
Economía, ayuda a la distribución de recursos entre oferentes y demandantes para que
exista una competencia perfecta; en la política, se puede ver reflejada en las campañas que
utilizan los diferentes partidos políticos para llegar al poder en las elecciones; en la
Biología, se ha utilizado para comprender y predecir algunos resultados evolutivos; en la
Sociología, se utiliza para estudiar el comportamiento de grupos delincuentes y ejemplificar
el modo en el que pueden llegar a operar, etc. Todas las aplicaciones mencionadas
anteriormente tienen algo común, el resultado de estas situaciones dependerá de las
decisiones que tomen los jugadores.
La Teoría de Juegos ha demostrado una gran versatilidad para la resolución de
problemas actuales. Partió de la Teoría Económica y la Matemática para estudiar la
interacción entre los agentes económicos y analizar el resultado que tendrían sobre los
participantes. De manera general, brinda a la Teoría Económica una nueva visión sobre el
análisis de diversas situaciones a nivel teórico y práctico.
“Pero sin duda, su principal aplicación la encontramos en las ciencias económicas
porque intenta encontrar estrategias racionales en situaciones donde el resultado
depende no solamente de la estrategia de un participante y de las condiciones del
mercado, sino también de las estrategias elegidas por otros jugadores, con objetivos
distintos o coincidentes” [2].
-
CAPÍTULO 1 1.2 Antecedentes históricos
10
1.2 Antecedentes históricos
La Teoría de Juegos tiene sus inicios comenzando por James Waldegrave en el año
de 1713. Waldegrave escribió en una carta una solución mínima de estrategias mixtas de un
juego de cartas entre dos personas muy importante de la época conocido como “Le Her”;
sin embargo, no tuvo el análisis teórico necesario hasta el trabajo que presentaría Cournot
más adelante [20].
Antoine Augustin Cournot, matemático, filósofo y economista francés (1801-1877),
fue el primero en estudiar los aspectos estratégicos al momento en que interactuaban los
agentes económicos, en su obra “Investigaciones acerca de los principios matemáticos de la
Teoría de las riquezas” publicada en el año de 1838. En ésta, se analizan las diferentes
formas de competencia en el mercado entre vendedores y productores, es decir, entre la
oferta y la demanda [18].
Posteriormente, el economista y abogado ingles Francis Ysidro Edgeworth (1845-
1926) se apoyó en la idea de Cournot para desarrollar el mismo concepto basado en una
economía sin producción dentro de su publicación “Matemáticas psíquicas: Un ensayo
sobre la aplicación de las matemáticas a las ciencias morales” en el año de 1881.
Edgeworth introdujo una herramienta de representación de interacción entre agentes
sin producción llamada “la caja de Edgeworth” que permite analizar todas las posibilidades
de asignación de recursos entre entidades y observar si esa asignación es una asignación
óptima [18].
El matemático alemán Ernest Friedrich Ferdinand Zermelo (1871-1953) brindó el
primer teorema formal de la Teoría de Juegos. El teorema consiste en determinar las
estrategias óptimas de los jugadores desde la última jugada retrocediendo hasta la primera,
siendo un teorema que sería recuperado por varios autores posteriormente. Su teorema
recoge a la vez varios enunciados importantes que afirman que:
-
CAPÍTULO 1 1.2 Antecedentes históricos
11
“En todo juego finalizado –cuyo número de partidas sea conocido de antemano-
con la información perfecta –cada jugador conoce, además de las suyas todas
las estrategias y las funciones de ganancia del resto de los jugadores- existe un
equilibrio” [18].
Las contribuciones anteriores permiten resolver juegos con estrategias puras. Más
adelante, el matemático francés Emile Borel (1871-1956) en el volumen IV de su obra
titulada “Tratado del cálculo de sus probabilidades y aplicaciones” publicada en 1924, en
donde introduce probabilidades en los juegos de azar y enuncia un teorema para juegos de
suma cero en donde se expresa que en un juego la ganancia de un jugador corresponde a la
pérdida de otro. También clasificó a los juegos de azar en dos: los juegos donde la
personalidad y habilidad de un jugador no intervienen y los juegos donde la personalidad y
habilidad del jugador sí intervienen [18].
La Teoría de Juegos nace propiamente en el año de 1944 con el matemático
estadounidense John von Neumann (1903-1957) y el economista alemán Oskar
Morgenstern (1902-1977) con la publicación de su libro “Theory of Games and Economic
Behavior” en el año de 1944, en donde se muestra la importancia de esta disciplina aplicada
a las relaciones humanas [18]; ambos proponen una relación de equilibrio en un juego de
suma cero mediante el famoso teorema Minimax introduciendo dos conceptos clave de la
Teoría de Juegos: los juegos cooperativos y los juegos no cooperativos.
Prácticamente, en el primer tipo, los jugadores no tienen comunicación, no hay
acuerdo y cada uno elige independientemente su estrategia sin importarle lo que suceda; en
los juegos cooperativos ocurre todo lo contrario, siempre se asume que los jugadores son
personas razonables que pueden establecer acuerdos entre sí acerca de las estrategias más
apropiadas para obtener un beneficio conjunto [10].
Para el año de 1950, aparecieron las primeras discusiones acerca del “dilema del
prisionero”. Éste, es uno de los ejemplos más representativos del teorema de equilibrio
entre dos jugadores y en él, se analizan los incentivos que tienen dos presos encarcelados
por un delito para delatar al otro a la policía y así, poder acceder a sus beneficios
penitenciarios.
http://es.wikipedia.org/wiki/1950http://es.wikipedia.org/wiki/Dilema_del_prisionerohttp://es.wikipedia.org/wiki/Dilema_del_prisionero
-
CAPÍTULO 1 1.2 Antecedentes históricos
12
Este experimento se realizó en la corporación RAND dedicada a la formación de
fuerzas armadas en Estados Unidos. Enfatizaremos en él un poco más adelante.
El economista y matemático estadounidense John Forbes Nash (1928-2015) fue
quién consolidó las bases de la Teoría de Juegos. Se basó en los trabajos del economista
Cournot proponiendo una Teoría de Equilibrio no cooperativo para juegos de suma variable
denominado “Equilibrio de Nash”, generalizando la propuesta hecha anteriormente por von
Neumann y Morgenstern y mostrando que, la elección de la estrategia de cada jugador es
una respuesta óptima a las elecciones de las estrategias de otros jugadores. Nash quizá es el
apellido más conocido en el tema de la Teoría de Juegos [18].
Curiosamente, la obra de Antoine Augustin Cournot fue ignorada hasta que salió a
la luz gracias a los trabajos de Forbes. En años posteriores, Nash publicó escritos con
originales soluciones para algunos problemas de la Teoría de Juegos, para juegos
bipersonales cooperativos y para la reducción de juegos cooperativos a un marco no
cooperativo [2].
Reinhard Selten (1930-2016) en el año de 1965 aportó a la teoría de Nash
introduciendo el concepto de equilibrio perfecto en subjuegos, aportando al teorema de
equilibrio de Nash. En 1967 John Harsanyi (1920-2000) desarrolló los conceptos de
información completa en donde los jugadores conocen perfectamente la estructura de un
juego, logrando junto con Nash y Selten, ganar el Premio Nobel de Economía en el año
de 1994 [3].
Una de las últimas aportaciones importantes a la Teoría de Juegos fue de Robert J.
Aumann y Thomas C. Schelling (1921-2016), por la que obtuvieron el Premio Nobel de
Economía en el año 2005 con la publicación “The Strategy of Conflict” aplicada a la Teoría
de Juegos en las ciencias sociales mediante el análisis de juegos con sucesos repetidos [2].
http://es.wikipedia.org/wiki/RANDhttp://es.wikipedia.org/wiki/1967http://es.wikipedia.org/wiki/Premio_Nobel_de_Econom%C3%ADahttp://es.wikipedia.org/wiki/1994
-
CAPÍTULO 2 1.3 Utilidad del Teorema Minimax de von Neumann
13
1.3 Utilidad del Teorema Minimax de von Neumann
En muchos ámbitos, el hombre está sujeto a resolver dilemas. Como lo indica la
Filosofía, un dilema es una situación problemática que se puede resolver mediante
alternativas distintas y que, además, ninguna de éllas es completamente aceptable. Los
dilemas reales son aquellos que vivimos en nuestra vida cotidiana y surgen de situaciones
propias, de nuestros intereses o de la sociedad [11].
Todo el tiempo debemos tomar una decisión, difícil o no, pero sin duda con
resultados diferentes a los que teníamos pensado. Una pregunta surge muy claramente,
¿Realmente, el ser humano se comporta de manera racional cuando se le presenta alguna
situación?
Uno de los ejemplos más representativos de cómo el ser humano responde a estos
dilemas de la vida cotidiana es “El dilema del prisionero”. Este dilema en un claro ejemplo
de la Teoría de Juegos que supone que cada uno de los jugadores de manera independiente
intenta maximizar su ganancia sin que le importe lo que sucede con el otro jugador. Su
enunciado dice lo siguiente:
“La policía arresta a dos sospechosos, pero no existen suficientes pruebas para
condenarlos. Se cree que han participado en el robo de un banco, delito penado con
diez años de cárcel. Tan sólo puede culparles de un cargo menor, tenencia ilícita de
armas, cuyo castigo es de solo un año. Detenidos y encerrados en celdas separadas
de forma que no pueden comunicarse entre sí, la policía les visita de forma
independiente ofreciéndoles el mismo trato:
Si uno confiesa y su cómplice no, el cómplice será condenado a la pena total, diez
años, y el que confiesa será liberado. Si uno calla y el cómplice confiesa, éste será
quien salga libre y el primero recibirá una pena de diez años. Si ambos confiesan,
los dos serán condenados a seis años. Si ambos lo niegan, tan solo podrán
encerrarlos durante un año por un cargo menor” [9].
-
CAPÍTULO 2 1.3 Utilidad del Teorema Minimax de von Neumann
14
Figura 1. Diagrama “El dilema del prisionero”.
Cada preso puede optar por colaborar con el otro diciendo que el compañero no
tendría por qué estar en la cárcel o acusarlo de haber cometido el delito. Podemos ver una
matriz que representa las opciones de este problema y sus posibles soluciones en la Figura
1 y 2.
Sospechoso B niega Sospechoso B confiesa
Sospechoso A niega Ambos se condenan por
1 año
A es condenado a 10
años y B queda libre
Sospechoso A confiesa B es condenado a 10
años y A queda libre
Ambos se condenan por
6 años
Figura 2. Matriz “El dilema del prisionero”.
-
CAPÍTULO 2 1.3 Utilidad del Teorema Minimax de von Neumann
15
Ahora, analizando lo anterior, supongamos que la única meta entre ambos
sospechosos es minimizar su condena. Cada uno tiene dos opciones, callar o confesar. El
resultado final dependerá de la elección del cómplice, por lo que no puede esperar a ver
qué contesta el otro acusado, es decir, cada uno contestará sin saber que elegirá el otro
cómplice [6].
Si uno de ellos confía en que el otro cooperará y se queda callado, la opción más
egoísta podría ser confesar, porque entonces el sospechoso que confesó saldría libre
mientras que el cómplice tendría que cumplir la pena máxima. Pero si espera que el
cómplice confiese, su mejor opción es confesar para que ambos eviten la pena máxima y
paguen una pena por 6 años. Por otro lado, si ambos cooperaran, cumplirían una pena
mínima [6].
Como se observa, confesar es una estrategia que domina para ambos acusados
porque cualquiera que sea la elección del otro cómplice se reducirá la pena al momento de
que confiesen, pero no sería la mejor opción porque ambos recibirían una condena larga.
Allí radica el punto cumbre de éste [6].
Viéndolo como un interés en conjunto de ambos sospechosos, la elección más
racional es que ambos cooperen quedándose callados y así, ambos cumplan una pena
mínima; esto sería un resultado óptimo para ellos como equipo y cualquier otra elección
que hubiesen tomado empeoraría este resultado en conjunto. Y esto es claro dado que, si
ambos cómplices tuvieran intereses individuales o egoístas recibirían una condena larga
[6].
Otro ejemplo basado en el “dilema del prisionero” puede ser ubicado en la
docencia.
-
CAPÍTULO 2 1.3 Utilidad del Teorema Minimax de von Neumann
16
Figura 3. “El dilema del prisionero” aplicado a la docencia.
Supongamos que un maestro, al iniciar su curso, propone hacer la realización de
una evaluación continua mediante la entrega de ejercicios en grupos; si la mayoría de los
ejercicios que entregue cada grupo están bien hechos y muestran interés al momento de
trabajar, entonces no habrá examen final, pero si los alumnos no muestran interés y los
ejercicios están mal hechos tendrán que hacer un examen final para acreditar la materia [6].
Los alumnos deben entregar los ejercicios semanalmente y se considera que han
estado trabajando continuamente; además supongamos que la cantidad de alumnos que
debe realizar los ejercicios con interés para evitar presentar el examen debe ser mayor o
igual al 80%. La matriz que representa las posibles opciones de los alumnos se ven
representadas en la Figura 4.
-
CAPÍTULO 2 1.3 Utilidad del Teorema Minimax de von Neumann
17
80% trabaja con interés
los ejercicios
80% no trabaja con
interés los ejercicios
20% trabaja con interés
los ejercicios
Nadie hace examen final
habiendo mostrado
interés todos
Todos presentan examen
final habiendo mostrado
interés en su minoría
20% no trabaja con
interés los ejercicios
Nadie hace examen final
habiendo mostrado
interés la mayoría
Todos presentan examen
final sin haber mostrado
interés en su mayoría
Figura 4. Matriz de la “forma de evaluación del maestro”.
Los alumnos tienen dos opciones para esta forma de evaluación del profesor: que
todos se esfuercen y no presenten examen final o que no se esfuercen y dependan de lo que
hagan sus compañeros de grupo. En general, los alumnos intentan pasar una materia
haciendo el mínimo esfuerzo y pensando que los demás se esforzarían por ellos
(beneficiándose de esa acción). El dilema aquí es que no se sabe si todos piensan igual [6].
Para ver qué sucede, tomaremos un grupo de entre todos al que llamaremos grupo
A. Este grupo A podría pensar que los demás grupos se van a esforzar con los ejercicios
para no hacer examen y por tanto para este grupo, la mejor opción sería no hacer ningún
esfuerzo. Serían los “únicos” en no entregar bien sus ejercicios, pero aun así pasarían la
materia sin hacer examen mientras que el resto de sus compañeros se esforzaron durante
todo el periodo escolar [6].
Pero si el grupo A piensa que los demás no se van a esforzar, lo mejor sería que se
esforzaran lo mínimo posible porque tendrían que hacer el examen final, pero al menos se
habrían esforzado menos en el periodo. Sin embargo, si todos los grupos se deciden
esforzar, todos habrán trabajado y no presentarían el examen final [6].
La estrategia que domina aquí para todos los grupos es no esforzarse, sea la
estrategia que sea para los demás, siempre conseguirían no trabajar durante el curso. El
problema es que esa estrategia no lleva a un resultado óptimo, porque si ninguno se
esfuerza demasiado, tendrán que hacer examen final. Si todos los grupos pensaran en el
-
CAPÍTULO 2 1.3 Utilidad del Teorema Minimax de von Neumann
18
beneficio general, lo mejor sería que todos se esforzaran al realizar sus ejercicios para no
hacer el examen final.
Por tanto, al igual que en el “dilema del prisionero”, la estrategia dominante no
conlleva a una solución óptima y si los estudiantes buscan el interés propio, pueden llegar a
un resultado que sea perjudicial para ellos [6].
El dilema del prisionero es complicado porque desafía el sentido común; es un
dilema con el que todos hemos de convivir. La parte esencial, como ya se vio en los
ejemplos anteriores, radica en mejorar los intereses propios, de forma que, si todas las
personas hicieran esto, la toma de decisiones nos llevaría al caos total; por eso, muchos han
interpretado este problema como un problema fundamental que ocurre en nuestra sociedad;
ciertamente, muchas de las más grandes tragedias sufridas por la humanidad fueron
causadas por el ser humano.
Von Neumann adquirió una alta reputación en su carrera por el gran dominio que
mostró hacia la matemática pura y la física matemática. Cabe señalar que fue un hombre al
que le gustaba el juego; el póker en particular, y se interesaba por los diferentes aspectos al
momento de jugar, el engaño, los movimientos falsos que hacían los jugadores para distraer
al oponente y no violar las reglas del juego, entre otros.
Desde mediados de 1920, von Neumann se dedicó a estudiar la estructura
matemática de juegos como naipes, dados o el póker. A medida en que fue avanzando, se
dio cuenta de que sus estudios podían aplicarse a diversos ámbitos en donde se ve reflejado
el juego, como fue la Economía y la Política, lo que lo llevó junto con el apoyo de Oskar
Morgenstern a publicar “Theory of Games and Economic Behavior”.
“En palabras de los autores el objetivo de la obra es mostrar adecuadamente que
los problemas típicos de comportamiento económico son rigurosamente idénticos a
las soluciones matemáticas de determinados juegos de estrategias” [12].
La publicación de John von Neumann no se refiere a jugar, sino que nos enseña
cómo la Teoría de Juegos estudia los dilemas o conflictos entre personas racionales; von
Neumann presenta esto de manera teórica y matemática desde un punto de vista
razonable.
-
CAPÍTULO 2 1.3 Utilidad del Teorema Minimax de von Neumann
19
Básicamente, la Teoría de Juegos estudia la rivalidad entre jugadores que piensan y
que pueden ser capaces de engañar al otro, y como se supone que los jugadores son
racionales, se puede llevar a cabo un análisis preciso de las estrategias.
Aunque la publicación presentó la teoría enfocada a problemas económicos, más
tarde, su contenido y terminología resultó de uso común para investigadores en ciencias,
economistas, filósofos, militares, etc. y se fue adaptando a diversas necesidades.
Sabemos a ciencia cierta que algunos juegos son simples de analizar, pero otros no.
Lo que von Neumann buscó fue encontrar siempre una respuesta racional al momento de
jugar, sobre todo, en aquellos casos en donde existen inconformidades.
La idea clave de la Teoría de Juegos es aquella que indique una solución óptima de
un conflicto estableciendo un equilibrio entre los jugadores; en el año de 1926, von
Neumann formuló el “Teorema Minimax”. Este principio estableció una solución racional
para una competencia, definido de tal manera que ambas partes no podrían hacer nada
mejor, en otras palabras, el resultado “Minimax” minimiza el daño máximo para los
jugadores [17].
Además, para quienes tienen escasa formación en esta disciplina, la idea de la
Teoría de Juegos y del “teorema Minimax” de von Neumann es fácil de entender. A
grandes rasgos, dicho teorema nos dice que, para todos los juegos finitos, entre dos
jugadores y de suma cero, siempre existirá un valor V que representará la cantidad media
que espera ganar el jugador 1 de parte del jugador 2 [17].
“Von Neumann, intuyó que este resultado era plausible por tres motivos
fundamentales:
1. La existencia de una estrategia para el primer jugador que es la mejor para sus
intereses, que le permitirá obtener unas ganancias determinadas, el valor medio del
juego, y contra la cual nada puede hacer el segundo jugador.
2. La existencia de una estrategia para el segundo jugador que es la mejor para
sus intereses, es decir, que le garantiza que no perderá como media más de un valor
determinado, el valor medio del juego, y contra la cual nada puede hacer el primer
jugador.
-
CAPÍTULO 2 1.3 Utilidad del Teorema Minimax de von Neumann
20
3. El hecho de que el juego sea de suma cero, esto es, lo que gana el primer
jugador debe perderlo el segundo, o que implica que existe un valor medio del
juego tanto el primer jugador como el segundo aceptan esa ganancia o pérdida
respectivamente, ya que cualquier otra estrategia les aleja de este valor en
detrimento de sus intereses” [17].
Un ejemplo que puede ilustrar la idea que fundamenta el teorema Minimax puede
ser el momento de cortar un pastel. No importa que tan cuidadoso sea uno, al momento de
cortarlo, uno, dos o más niños, se quejará de que su pedazo fue más pequeño que el de otro.
Figura 5. Ejemplo para ilustrar el “Teorema Minimax” al momento de cortar un pastel.
La solución para este problema consiste en que el primero de ellos corte el pastel, y
que todos los demás escojan el pedazo que quieran. Sería una repartición justa. El primer
niño no podría quejarse de que la partición está mal hecha porque él la hizo. Los demás no
podrían protestar, porque cada uno de ellos eligió el pedazo que quería. El problema del
pastel es un conflicto de intereses (un dilema) y la solución pasa por ser un resultado
óptimo [12].
-
CAPÍTULO 2 1.3 Utilidad del Teorema Minimax de von Neumann
21
Mediante ejemplos de aplicación del “dilema del prisionero” se puede observar
cómo influye el teorema Minimax y cómo influye la Teoría de Juegos en la vida diaria, por
este motivo es tan estudiado. En particular, hemos visto en los ejemplos anteriores cómo se
presentan situaciones en donde siempre se obtendría una estrategia óptima si los jugadores
buscan un beneficio en grupo y no beneficio propio. Sin embargo, como ocurre en la
sociedad y en la mayoría de las situaciones, los participantes de un juego actúan de manera
egoísta y se perjudican a ellos mismos y a sus contrincantes [6].
-
CAPÍTULO 2 2.1 Introducción
22
CAPÍTULO 2. JUEGOS DE SUMA CERO
2.1 Introducción
Como ya se mencionó anteriormente el enfoque de la Teoría de Juegos es analizar
las posibilidades de que algunos o todos los jugadores, lleguen a un acuerdo sobre las
decisiones que va a tomar cada uno de éllos. Es decir, el juego se vuelve una competición
entre jugadores que no sólo buscan sus intereses individuales. Los jugadores escogerán
estrategias mediante un proceso en donde la mayoría de los participantes, si no es que
todos, alcancen un beneficio satisfactorio. Los casos que se analizarán a continuación son
los juegos de suma cero entre dos personas con punto de equilibrio y sin punto de
equilibrio.
2.2 Juegos de suma cero entre dos personas con punto de
equilibrio
En un juego entre dos personas se considerarán sólo a dos jugadores a los cuales los
llamaremos jugador I y jugador II (racionales, claro está). Cada jugador tendrá un número
finito de elecciones llamadas estrategias. Es decir, el jugador I, tendrá n estrategias en
total, así que él decidirá con qué estrategia jugará, con y el jugador II tendrá
m estrategias en total, así que él decidirá con qué estrategia j jugará, con . Por
notación, cada pago o recompensa que puede recibir el jugador I por parte del jugador II
cuando el jugador I eligió la estrategia mientras que el jugador II eligió la estrategia , se
representará mediante un valor , por tanto, un valor representará que el jugador II
obtuvo una recompensa del jugador I cuando el jugador I eligió la estrategia mientras que
el jugador II eligió la estrategia .
En este juego, consideraremos que la ganancia de cualquiera de los dos jugadores
representará la pérdida del otro; a esto le llamaremos juego de suma cero entre dos
personas [5]. Generalmente para representar este tipo de juegos, podemos expresar los
-
CAPÍTULO 2 2.2 Juegos de suma cero entre dos personas con punto de equilibrio
23
resultados mediante una matriz de juego ( ) con como se muestra a
continuación.
Figura 6. Matriz suma cero entre dos personas
Como se puede observar, las filas representan las estrategias de jugador I y las
columnas, las estrategias del jugador II. Por notación, para una matriz de juego :
( )
(
) .
Es fácil notar que, cualquiera de los dos jugadores intentará maximizar sus
beneficios individuales. Si todo el tiempo las personas jugaran de la misma manera, es
decir, usando las mismas estrategias, se volvería un juego predecible. Por tanto, debemos
suponer que los juegos serán jugados usando estrategias al azar.
Entonces, lo que desea hacer el jugador I es elegir una fila que maximice su
ganancia sobre las estrategias del jugador II. A este concepto se le conoce como el más
bajo valor de juego y se denota como sigue: .
Por otro lado, el jugador II, suponiendo que juegue de la mejor manera, intentará
elegir una columna que minimice su pérdida sobre las estrategias del jugador I. A esto se
le llama el más alto valor de juego y se denota como: .
ESTRATEGIA 1 ESTRATEGIA 2 … ESTRATEGIA m
ESTRATEGIA1 …
ESTRATEGIA 2 …
… … … … …
ESTRATEGIA n …
JUGADOR II
JUG
AD
OR
I
-
CAPÍTULO 2 2.2 Juegos de suma cero entre dos personas con punto de equilibrio
24
En una matriz de juego, como lo muestra la Figura 7, podemos ver representado al
más alto y más bajo valor de juego.
Figura 7. Representación del más bajo valor de juego y el más alto valor de juego en una matriz de suma cero
entre dos personas.
Note que representa la cantidad minima que podría obtener el jugador I mientras
que representa la cantidad máxima que podría llegar a perder el jugador II. Esta
descripción deja en claro que .
Si se tiene una matriz de suma cero entre dos jugadores y además se cumple la
condición de que entonces se dice que el juego tiene un punto silla. Un punto
silla es una condición necesaria y suficiente para encontrar un equilibrio entre las
estrategias puras de cada jugador, es decir, una estrategia óptima para cada uno de ellos y se
representa:
( ) ( ) .
Además, a ese punto silla obtenido se le conoce como ( ) o valor de juego. Por
tanto, ( ) es un pago determinado que se obtiene al tomar simultáneamente una estrategia
minima y una estrategia máxima entre los dos jugadores.
Definición 2.2.1. En particular, si se considera a una fila y una columna cualesquiera
tal que existe , un punto silla de estrategias puras en un juego ocurre si:
ESTRATEGIA 1 ESTRATEGIA 2 … ESTRATEGIA m
ESTRATEGIA1 …
ESTRATEGIA 2 …
… … … … … …
ESTRATEGIA n …
…
…
JUGADOR II
JUG
AD
OR
I
-
CAPÍTULO 2 2.3 Estrategias mixtas para juegos de suma cero entre dos personas sin
punto de equilibrio
25
Es claro que, si existe un punto silla o un valor de juego óptimo para los dos
jugadores y alguno de ellos decide jugar otra estrategia, el otro jugador puede tomar ventaja
de ello y mejorar su ganancia.
Ejemplo 2.2.1
Considere el siguiente juego: hay dos jugadores (I y II) y cada uno decide mostrar 1, 2 o 3
dedos al mismo tiempo. Si el número total de dedos mostrados suma un numero par el
jugador II pierde -$1 y el jugador I gana +$1, si el número de dedos mostrados suma un
número impar ocurre lo contrario. La matriz de juego está representada en la Figura 8.
Figura 8. Matriz que representa las posibles estrategias de los jugadores I y II.
Si calculamos el valor más bajo y más alto de juego se obtiene:
Ahora, si no existe una estrategia óptima pura, ¿de qué manera se tendría que jugar
un juego? Existe una forma que permite hallar un valor óptimo ( ) mediante estrategias
mixtas.
2.3 Estrategias mixtas para juegos de suma cero entre dos
personas sin punto de equilibrio
Ahora, supongamos que cada jugador elige una estrategia al azar con cierto nivel de
probabilidad que especifica la posibilidad de que cada estrategia sea jugada. A estas
posibles estrategias se les conoce como estrategias mixtas y se representan mediante
vectores de probabilidad.
ESTRATEGIA 1 ESTRATEGIA 2 ESTRATEGIA 3
ESTRATEGIA1 1 -1 1
ESTRATEGIA 2 -1 1 -1
ESTRATEGIA 3 1 -1 1JUG
AD
OR
I
JUGADOR II
-
CAPÍTULO 2 2.3 Estrategias mixtas para juegos de suma cero entre dos personas sin
punto de equilibrio
26
Es decir, una estrategia mixta es aquella en la que el jugador asigna una
probabilidad estrictamente positiva a cada estrategia pura (aquella que tiene probabilidad de
1 de ser elegida) y es una generalización del tema anterior.
El jugador I tendrá un vector de estrategias mixtas denotado por: mientras que el
vector de estrategias del jugador II se denotará por . Al ser vectores de probabilidad deben
cumplir que:
( ) ∑
(
) ∑
Los componentes representan la probabilidad de que la fila sea utilizada por el
jugador I mientras que los componentes representan la probabilidad de que la columna
sea utilizada por el jugador II. Además, al conjunto de las estrategias mixtas con k
componentes se le denotará como:
( ) ∑ .
Ahora, si suponemos que los jugadores juegan varias veces este mismo juego, en
promedio, existirá una recompensa media que esperan recibir, a esto se reconoce como el
pago esperado [5].
Los jugadores I y II elegirán sus estrategias al azar y de manera independiente, lo
que nos lleva a la siguiente definición.
Definición 2.3.1 Dado que los jugadores I y II eligen estrategias independientemente, el
pago esperado para ambos jugadores se denota como:
( ) ∑∑
( )
∑∑
( ) ( )
-
CAPÍTULO 2 2.3 Estrategias mixtas para juegos de suma cero entre dos personas sin
punto de equilibrio
27
∑∑
∑∑
( ) (
)
Entonces, el más bajo valor de juego y el más alto valor de juego en estrategias
mixtas se denota como sigue:
Definición 2.3.2 Un punto silla de estrategias mixtas ( ), es un par de vectores de
probabilidad y que satisfacen:
( ) ( ) ( ) ( ), para cada y
En esta terminología, una estrategia mixta para el jugador I es cualquier elemento
y una estrategia mixta para el jugador II es cualquier elemento . Por tanto,
una estrategia pura para el jugador I, es un elemento de la forma
( ) que indica que el jugador I siempre jugará la fila correspondiente a la
posición de 1 en el vector ocurre lo mismo para el jugador II en el vector
Imaginando el caso en que el jugador I decide usar una estrategia pura, es decir,
una estrategia que jugará todo el tiempo, y el jugador II decide jugar con una estrategia
mixta, entonces, el pago esperado se simplificará como:
( ) ∑ ( )
(
)
-
CAPÍTULO 2 2.3 Estrategias mixtas para juegos de suma cero entre dos personas sin
punto de equilibrio
28
En el caso que ocurra lo contrario:
E( ) ∑ ( ) (
).
Existe una lista de propiedades que nos ayudan a encontrar el valor de un juego de
estrategias mixtas y se describirán a continuación.
Propiedades para estrategias mixtas
Teorema 2.3.1 Dada una matriz de juego ( ) con un valor de juego
( ) un número real c y respectivamente.
a) ( ) ( )
b) ( ) ( )
c) ( ) ( )
( ) ( ) .
d) ( ) ( )
( ) ( )
e) ( )
( )
( )
( ).
Demostración
a) Supongamos que:
( ) ∑ para
Sea ( ) una estrategia mixta óptima para el jugador II. Si
multiplicamos ambos lados de la ecuación anterior por y se suma sobre todas las
se obtiene:
-
CAPÍTULO 2 2.3 Estrategias mixtas para juegos de suma cero entre dos personas sin
punto de equilibrio
29
∑
∑∑
( ) ( )
Y ∑ entonces ( ) ( ) para cualquier . □
b) Para probar esta parte se utiliza lo mismo que en a). □
c) Si ∑ ∑
se tiene que:
( ) ∑∑
∑
∑
( ) ∑ ∑
∑
( ).
Esto dice que ( ).Y nosotros tenemos que por la definición 2.3.2
( ) ( ) ( ) Con y , entonces
( ) ( ) Y es un punto silla con ( ). □
d) Sea ( ) una estrategia mixta óptima para el jugador II. Si:
( ) ( ) ( )
Para todas las columnas y filas , donde la primera parte de la inecuación viene
de la definición de un óptimo para el jugador II. Usando la parte c) podemos notar
que es un óptimo para el jugador I. La segunda parte para d) se hace de manera
análoga. □
e) Comenzamos por establecer la definición como sigue:
( )
( )
Para cualquier estrategia mixta Esto es, desde que cada estrategia pura se
convierte en una estrategia mixta ocurre que:
( )
( )
Ahora definimos
( ). Entonces:
∑ ( ( ) )
( ) .
-
CAPÍTULO 2 2.3 Estrategias mixtas para juegos de suma cero entre dos personas sin
punto de equilibrio
30
Con ( ) para cada En consecuencia,
( ) , y
juntando las inecuaciones, se concluye que ( )
( )
Usando la definición de ( ) sabemos que:
( )
( )
( )
De manera similar podemos ver que:
( ) ( ) ( )
En consecuencia
( )
( )
( )
Y si es un punto óptimo para el jugador I, entonces:
( )
( )
( )
( )
Por otro lado, si ( ) ( ) entonces, ( ) (
) para todas las
columnas y ( ) ( ) para toda , lo cual implica que , es una estrategia
mixta para el jugador I. □
Ejemplo 2.3.1
Sea A una matriz de juego representada por (
).
El primer paso es verificar si existe o no un punto silla de estrategias puras. Se tiene que:
Como , se debe encontrar una estrategia óptima para el jugador I mientras
el jugador II utiliza una estrategia , entonces, I tendrá un vector de estrategias mixtas
denotado por ( ) y un valor de juego ( ) . Entonces:
E( ) ( ) (
) y E( ) ( ) (
),
Volvemos las inecuaciones igualdades y resolviendo para y para se obtiene:
-
CAPÍTULO 2 2.3 Estrategias mixtas para juegos de suma cero entre dos personas sin
punto de equilibrio
31
( )
.
Similarmente, para encontrar una estrategia óptima para el jugador II mientras I
utiliza una estrategia , suponemos que utilizará un vector de estrategias mixtas denotado
por ( ) y un valor de juego ( ) . Entonces:
E( ) ( ) (
) y E( )
( ) (
),
Y resolviendo para y para se obtiene:
( )
.
Entonces, (
) es una estrategia óptima para I y (
) es una estrategia
óptima para II, ambos con un valor de juego ( )
.
Lema 2.3.1 Si es una estrategia mixta para el jugador I y existe un número ( ) tal
que E( ) ( ) , entonces para cualquier estrategia , E( ) ( ).
Lo anterior nos indica básicamente que si la estrategia que eligió el jugador I, es
una buena estrategia aun cuando el jugador II utilizó cualquier otra estrategia pura,
entonces, seguirá siendo una buena estrategia para el jugador I y viceversa.
Ejemplo 2.3.2
Continuando con el ejemplo 2.3.1, se verifica el Lema anterior.
Para el jugador 1:
E( )
y E( ) = (
) (
)(
) =
.
Para el jugador 2:
-
CAPÍTULO 2 2.3 Estrategias mixtas para juegos de suma cero entre dos personas sin
punto de equilibrio
32
E( )
y E( ) = (
) (
)(
) =
.
Como podemos observar, existe un valor de juego ( )
, de tal manera que el
jugador I obtendrá un pago esperado mayor o igual a
suponiendo que él juega de la
mejor manera posible sin importar que estrategia utilice el jugador II. De manera similar, el
jugador II obtendrá un pago esperado menor o igual a
, suponiendo que él juega de la
mejor manera posible sin importar que estrategia utilice el jugador I.
Observación 2.3.1
Los supuestos de existencia de un valor mínimo y un máximo son justificables ya que en:
( )
,
( )
.
Las expresiones que se muestran arriba, se desarrollan de manera lineal y por lo
tanto de manera continua, además los valores sobre los cuales se trata de encontrar un valor
optimo, ya sea o son conjuntos cerrados y acotados.
Teorema 2.3.2 En cualquier matriz de juego ( ), a cualquiera de los jugadores se les
permite usar estrategias mixtas que cumplan con las siguientes propiedades:
1. El valor de juego para cada jugador es único
2. Existe al menos una estrategia pura para cada jugador
3. El valor de juego para cada jugador de estrategias puras y mixtas satisfacen:
( ) ( )
( ) ( ) (1)
Demostración
Para 1. La unicidad de deriva directamente de su definición:
-
CAPÍTULO 2 2.3 Estrategias mixtas para juegos de suma cero entre dos personas sin
punto de equilibrio
33
Por tanto, son únicos. □
Para 2. La cantidad es una función continua de . Pero Y es
vector con valores finitos y el mínimo de esa función se alcanza en , demostrando que
existe una estrategia segura para el jugador I. Para el jugador II se comprueba
análogamente. □
Para 3. El valor de juego se deduce al razonar que el máximo valor que se puede perder en
un juego no puede ser menor que lo mínimo que se puede ganar en un juego. Las
desigualdades se siguen, ya que el valor más bajo y el valor más alto de juego de
estrategias puras están incluidas en el espacio de estrategias mixtas, lo que denota que en
una matriz de juego , el valor más bajo y el valor más alto de estrategias mixtas se denota
como:
( )
(2)
( )
(3)
Y además sabiendo por una de las definiciones más importantes de la Teoría de Juegos de
suma cero es que el valor más bajo y más alto de juego son iguales . □
Lema 2.3.2 Dada una matriz de juego ( ), ocurre que:
i) Exista un vector tal que
ii) Exista un vector tal que
Teorema 2.3.3 (Teorema Minimax de von Neumann)
Dada una matriz de juego ( ) existen vectores de probabilidad de estrategias
, en promedio, después de jugar repetidamente, los niveles más bajo y
más alto de juego coinciden, es decir:
-
CAPÍTULO 2 2.3 Estrategias mixtas para juegos de suma cero entre dos personas sin
punto de equilibrio
34
Demostración.
Aplicando la alternativa i) del Lema 2.3.2, dada una matriz de juego A, al menos una de
las desigualdades siguientes se cumple:
)
)
Asumiendo que la primera alternativa del Lema 2.3.2 es válida, entonces existe otro vector
por ejemplo lo cual equivale a para toda x
en vector . Esto equivale a decir que . Lo cual implica por (2) en el
Teorema 2.3.2 que
.
Ahora, Tomando la alternativa ii) del Lema 2.3.2, supongamos que existe otro vector por
ejemplo lo cual equivale a para toda y en
vector . Esto equivale a decir que . Lo cual implica por (3) en el
Teorema 2.3.2 que
.
Así, bajo la alternativa i) del Lema 2.3.2, la desigualdad se mantiene y bajo la alternativa
ii) del Lema 2.3.2, la segunda desigualdad se satisface.
Ahora, considere una nueva matriz , tal que de tal manera que desplaza todas
las entradas de la matriz con una constante de tal manera que: = , lo que
afecta a ambas desigualdades de
, siendo ahora:
( )
( ) (I)
( )
( ) (II)
Y como la matriz es arbitraria en ( ) ( ), si reemplazamos con , para una matriz
de juego y una constante c, al menos una de estas desigualdades se cumple:
( ) (III)
( ) (IV)
-
CAPÍTULO 2.4 Estrategias dominadas
35
Ahora, para que se cumpla esta condición para algún valor , es necesario que ( )
( ); Por contradicción, la única posibilidad es que ( ) ( ) en vista de la
desigualdad media de (I) en el Teorema 2.3.2 con y tomando ( )
. Se
deduce que ni (III) ni (IV) se cumplen, lo que concluye la demostración del Teorema. □
2.4 Estrategias dominadas
Normalmente trabajar con matrices pequeñas es mejor y menos tardado que con
matrices muy grandes. En particular, se puede reducir el tamaño de una matriz de juego
( ) eliminando filas o columnas que quizá nunca se utilicen porque en el caso de cada
jugador, siempre habrá alguna estrategia mejor que utilizar, a esto se le conoce como
eliminación por dominancia.
Así que antes de comenzar a resolver un juego de suma cero, primero debemos
verificar si se puede reducir la matriz ( ) a una de tamaño ( ) ( ) o
( ) Para poder utilizar el método de eliminación por dominancia se deben cumplir
alguna o todas las condiciones de la siguiente definición. Recordemos que las estrategias
para el jugador I se representan por las filas y las estrategias del jugador II se representan
por las columnas de la matriz de juego ( ).
Definición 2.4.1 Si una fila domina a una fila , entonces podemos remover la fila para
. Si una columna domina a una columna podemos remover la columna
para . Si una fila o una columna son redundantes, podemos eliminarlas y
así reducir el tamaño de la matriz.
Formalmente, el proceso de reducir el tamaño de una matriz de juego se realiza
mediante la combinación convexa de filas o columnas.
Definición 2.4.2 Si una fila es dominada por una combinación convexa de otras dos filas
se puede eliminar si se cumple lo siguiente:
( ) ( ).
-
CAPÍTULO 2.4 Estrategias dominadas
36
Si una columna es dominada por una combinación convexa de otras dos columnas
se puede eliminar si se cumple lo siguiente:
( ) ( ).
Al aplicar el concepto de estrategias mixtas podemos apoyarnos utilizando un
gráfico; este gráfico puede incluso revelarnos conceptos acerca de cómo mira cada jugador
sus jugadas.
En general se pueden eliminar filas o columnas que gráficamente no se intersecten
en un punto óptimo al que llamamos valor de juego; a menudo se cumple, pero no siempre
es cierto. Por eso es más recomendable realizar el análisis matemático además de apoyarnos
del gráfico, veamos los dos ejemplos siguientes.
Ejemplo 2.4.2 Sea A una matriz de juego representada por (
).
Se calcula el valor más bajo de juego ( ) y el valor más alto de juego ( ). En efecto, se
tiene que , así que no existe un punto silla de estrategias puras. Ahora,
procedemos a hacer su análisis gráfico para el jugador II como se muestra en la Figura 9.
Figura 9. Grafo de estrategias para el jugador II.
-
CAPÍTULO 2.4 Estrategias dominadas
37
Ahora, mediante el método gráfico se quiere visualizar las estrategias que tiene el
jugador II con respecto al otro jugador (jugador I). Se trazan dos ejes paralelos a una
distancia no tan pequeña. Cada uno de los ejes trazados ahora representará las estrategias
del jugador I.
Localizamos dentro de la matriz cada una de las n estrategias del jugador I que, para
el ejemplo dado son 4, definidas por (-1, 2), (3, -4), (-5, 6) y (7, -8). Finalmente se trazan
las rectas formadas por la unión de los puntos dados.
Como el jugador II busca minimizar su posible pérdida, la zona factible de
soluciones está en la parte inferior de las líneas trazadas y su solución óptima es el vértice
máximo.
En ocasiones, los gráficos suelen ser complicados de analizar a simple vista.
Sabemos que el punto óptimo se encuentra en el vértice máximo de las rectas formadas por
las estrategias, pero no queda suficientemente claro, además, a simple vista no podemos
descartar alguna estrategia que no se llegará a usar en el juego. Entonces para resolver este
juego, se reducirá el tamaño de la matriz por medio de estrategias dominadas.
Primero se tomará la fila 2 y se verificará si es una combinación convexa de las filas 4 y 1:
( ) ( ).
Resolviendo para encontramos un intervalo donde se encuentra con
, por tanto,
podemos eliminar la fila 2 obteniendo la siguiente matriz: (
).
Se tomará la fila 2 de la nueva matriz y se verificará si es una combinación convexa de las
filas 3 y 1:
( ) ( ).
Resolviendo para encontramos un intervalo donde se encuentra con
, por
tanto, podemos eliminar la fila 2 obteniendo la siguiente matriz: (
).
-
CAPÍTULO 2.4 Estrategias dominadas
38
Y resolvemos para el jugador I, con un vector de estrategias mixtas denotado por
( ) y un valor de juego ( ) . Entonces:
E( ) ( ) y E( ) ( ).
Volvemos las inecuaciones igualdades y resolviendo para y para se obtiene:
( )
.
Similarmente, resolvemos para el jugador II con un vector de estrategias mixtas denotado
por ( ) y un valor de juego ( ) . Entonces:
E( ) ( ) y E( )
( ).
Volvemos las inecuaciones igualdades y resolviendo para y para se obtiene:
( )
.
Entonces, (
) es una estrategia óptima para I en el juego original y
(
) es una estrategia óptima para II, ambos con un valor de juego ( )
.
Podemos verificar que en realidad se encontró la mejor estrategia para ambos
jugadores si se cumple: ( ) ( ) ( ) ( ). Calculando:
( ) (
)(
) = (
)
( ) (
) (
)
(
)
Se puede verificar que al realizar el producto matricial de ( ) y de
( ) ambos obtienen un valor de juego ( )
, por tanto, se obtuvo una estrategia
óptima para ambos jugadores.
-
CAPÍTULO 2.5 La mejor estrategia de respuesta
39
2.5 La mejor estrategia de respuesta
Supongamos que el jugador I sabe o supone que el jugador II usará una estrategia
pura en ese caso, el jugador I debe jugar una estrategia mixta para que maximice su
pago esperado ( ). A este concepto se le conoce como la mejor estrategia de
respuesta de I ante el jugador II.
Definición 2.5.1 Una estrategia mixta para el jugador I es la mejor estrategia de
respuesta ante la estrategia del jugador II si satisface:
( ) ( )
De igual forma, una estrategia mixta para el jugador II es la mejor estrategia de
respuesta ante la estrategia del jugador I si satisface:
( ) ( )
Es decir, si la estrategia y la estrategia son un punto silla en el juego es decir,
( ) ( ) entonces son la mejor estrategia de respuesta.
En general, si la estrategia es conocida entonces:
( )
( )
Si la estrategia es conocida entonces:
( )
( )
Ejemplo 2.5.1
Consideremos una matriz de juego (
). Además, si se resuelve mediante
estrategias mixtas y eliminación por dominancia obtenemos que existe un punto silla de
estrategias en (
) y además un valor de juego ( ) . Ahora,
-
CAPÍTULO 2.5 La mejor estrategia de respuesta
40
suponga que el jugador II por alguna razón piensa que la mejor estrategia que puede usar es
(
) Cuál es la mejor estrategia de respuesta para el jugador I?
Entonces, para encontrar una estrategia óptima para el jugador I mientras el jugador
II utiliza la estrategia , I tendrá que utilizar un vector de estrategias mixtas denotado por:
( ).
Calculando: ( ) ( )
.
Pero, lo que queremos es tomar la estrategia que maximice, así que para obtener el
máximo valor objetivo de esa función resultante en términos de de acuerdo a la
noción de optimización, se debe de tomar a cada valor de la función resultante e
igualarlos a 0. Este paso permite obtener el valor máximo de la función que es
y
representa el valor del juego.
Por otro lado al hacer , sustituyendo los valores en el vector de
estrategias mixtas se obtiene ( ) ( ).
Entonces, la mejor estrategia de respuesta para el jugador I cuando en jugador II usa
(
) es ( ). Además, el pago esperado para el jugador I después de
maximizar la función es ( )
.
En otras palabras, en un juego con dos jugadores, si se conoce una estrategia para
algún jugador, existirán expectativas bajo las cuales se puede actuar con una mejor
respuesta. La correspondencia de mejor respuesta es, como su nombre lo indica,
una regla que asocia un perfil de estrategias mixtas a un perfil de estrategias o
viceversa.
Hay que tomar en cuenta que no siempre se cuenta con un solo perfil de posibles
estrategias, sino que pueden existir varias, la cuestión es ¿Cuál de ellas se tomará?, la que
maximice el beneficio.
-
CAPÍTULO 3 3.1 Introducción
41
CAPÍTULO 3. JUEGOS COOPERATIVOS
3.1 Introducción
En esta parte se estudiará cómo hacer una distribución de pagos entre los jugadores
que forman una coalición y han obtenido una ganancia jugando de manera cooperativa. En
particular se estudiarán tres conceptos muy importantes; el Core, el Nucleolus y el Valor
de Shapley [7].
El Core es un concepto de solución de tipo conjunto, es decir, limita a un conjunto
de posibles valores exigiéndole cumplir ciertas propiedades. El Core es un conjunto de
distribuciones de pagos que ofrece a cada coalición un beneficio mayor o igual que el que
esta coalición puede conseguir por sí misma. Por tanto, lo convierte en un reparto de pagos
que satisface a todos los jugadores y a todas las posibles coaliciones. Esta idea fue
introducida por Gillies (1953); por otro lado, puede darse el caso de que en un juego el
Core sea vacío, por lo tanto, no se podría obtener un vector de pagos con el que todos los
jugadores se viesen beneficiados, lo que puede causar descontentos o inconformidades
entre ellos.
El concepto de Nucleolus fue introducido por Schneider (1969) y lo que busca es
minimizar esos descontentos generados en todas las coaliciones, es decir, lo que se busca es
un reparto socialmente más justo en el sentido de que la coalición que resulte más
desfavorecida en el reparto de los beneficios, esté lo menos perjudicada posible.
Más adelante surgió el concepto del Valor de Shapley. Fue nombrado en honor de
Lloyd Shapley (1967); este método de distribución, asigna un reparto único del beneficio
total generado por la coalición a todos los jugadores. La importancia de este concepto es su
conFiguración. Imaginemos una coalición de jugadores que coopera y obtiene una cierta
ganancia general de la cooperación. Dado que algunos jugadores pueden contribuir más a la
coalición que otros, ¿Qué importancia tiene cada jugador para la cooperación y qué
recompensa puede esperar de élla? El Valor de Shapley ofrece una posible respuesta a esta
pregunta mediante la aplicación de ciertos axiomas como se mostrará más adelante, donde
la repartición de los beneficios siempre existe y es óptima.
-
CAPÍTULO 3 3.2 Juegos cooperativos
42
3.2 Juegos cooperativos
Comenzaremos por definir un juego en forma coalicional o también llamado en
forma de función característica con utilidades transferibles, éste consiste de:
1. Un conjunto finito de jugadores denotado por .
2. Subconjuntos de
3. Una función característica que asocie a cada subconjunto un número real o valor de
la coalición ( ), siendo ( )
Así, ( ) es un juego en forma coalicional en forma de función característica
con utilidades transferibles con y ( ) especificados.
Si el beneficio que obtiene un jugador estando en una coalición es menor o igual
al beneficio que obtendría al unirse con otra coalición ; es decir con con ,
entonces ocurre que ( ) ( ) y a esto se le conoce como un juego cooperativo
monótono.
Si se tiene un juego en forma coalicional donde ocurre que la suma de los beneficios
al jugar dos coaliciones y por separado es menor que el pago que obtendrian si se
unieran para trabajar en conjunto , entonces ( )
( ) ( ); a esto se le llama juego cooperativo superaditivo.
Pero generalizando aún más el concepto anterior, si se tienen dos coaliciones con
una intersección no necesariamente vacía y se unen, entonces, la suma de los beneficios de
la unión e intersección es al menos igual que la suma de los beneficios de las coaliciones
que se unieron, es decir, si , y ocurre que ( ) ( ) ( ) ( ) a
esto se le conoce como un juego convexo. Si ocurre lo contrario en la desigualdad,
entonces, el juego es cóncavo.
-
CAPÍTULO 3 3.2 Juegos cooperativos
43
Ejemplo 3.2.1
Figura 10. Representación del juego en forma estratégica para los tres jugadores.
Una finca está valorada por su actual propietario en $350,000.00. Un empresario
ofrece acondicionarla como un polígono industrial con lo que su valor de mercado podría
alcanzar los $700,000.00. Una empresa constructora le ofrece urbanizar la finca para
subdividirla y destinarla a viviendas, con esta urbanización el valor de la finca sería de
$775,000.00.
Iniciamos representando el juego de manera coalicional ( ).
Sea , en donde 1 representa al empresario que ofrece adecuar la finca
como polígono industrial, 2 representa a la empresa constructora y 3 representa al actual
propietario de la finca.
Notemos que, tanto el jugador 1 como el 2 necesitan llegar a un acuerdo con el
jugador 3 para utilizar la finca. Sin la participación del jugador 3 no podrían hacer nada, por
tanto:
-
CAPÍTULO 3 3.2 Juegos cooperativos
44
( ) ( ) ( )
Por otro lado, Si el jugador 3 no coopera con ninguno de los otros dos jugadores, la
finca se mantiene con un valor de $350,000.00, lo que es: ( ) = 350,000.
Si el jugador 3 llega a un acuerdo con el jugador 1, entre los dos obtendrían
$700,000.00, lo que es: ( ) = 700,000.
Si el jugador 3 solo llega a un acuerdo con el jugador 2, entre los dos obtendrían
$775,000.00, lo que es: ( ) = 775,000.
Si cooperaran los tres jugadores y realizaran conjuntamente el proyecto que les
brindara mayor beneficio, entonces entre los tres obtendrían: ( ) = 775,000.
Y la representación en forma coalicional del juego se vería como:
( ) ( ) ( ) ( ) ( ) = 350,000, ( ) = 700,000,
( ) = 775,000, ( ) = 775,000
En donde los valores están expresados en pesos.
Podemos verificar que todas las inecuaciones formadas por la combinación de las
coaliciones cumplen que este juego es monótono:
( ) ( ), ( ) ( ), ( ) ( ),
( ) ( ), ( ) ( ) ( ) ( ),
( ) ( ), ( ) ( ), ( ) ( ).
Superaditivo y convexo:
( ) ( ) ( ), ( ) ( ) ( ),
( ) ( ) ( ), ( ) ( ) ( ),
( ) ( ) ( ), ( ) ( ) ( ).
-
CAPÍTULO 3 3.2 Juegos cooperativos
45
Ejemplo 3.2.2
Consideremos tres empresas que producen un mismo bien. Dadas las tecnologías aplicadas
por cada empresa, la empresa 1 puede producir 0, 8 o 16 unidades al coste unitario de
$2.00, la empresa 2 puede producir 0, 4 o 12 unidades al coste unitario de $2.00 y la
empresa 3 puede producir 0, 8 o 12 unidades al coste unitario de $2.00. La función de
demanda del bien es conocida por las tres empresas y tiene la siguiente forma:
( ) .
En donde x representa la cantidad total de producto en el mercado. Representemos
el juego de forma coalicional ( ).
Sea , en donde 1 representa la empresa 1, 2 representa a la empresa 2 y 3
representa la empresa 3.
Ahora , y son los respectivos
subconjuntos de las estrategias para las empresas jugadoras.
La cantidad total de producto que llega al mercado es y el pago
que obtiene cada empresa está determinado por la función de beneficio definida por:
( ) ( )
La representación del juego en forma estratégica para cada jugador se ve en la Figura 11.
-
CAPÍTULO 3 3.2 Juegos cooperativos
46
Cuando la Empresa 3 utiliza la estrategia 0
Empresa 2
Em
pre
sa 1
0 4 12
0 0,0,0 0,120,0 0,288,0
8 216,0,0 192,96,0 144,216,0
16 336,0,0 288,72,0 192,144,0
Cuando la Empresa 3 utiliza la estrategia 8
Empresa 2 E
mp
resa
1 0 4 12
0 0,0,216 0,96,192 0,216,144
8 168,0,168 144,72,144 96,144,96
16 240,0,120 192,48,96 96,72,48
Cuando la Empresa 3 utiliza la estrategia 12
Empresa 2
Em
pre
sa 1
0 4 12
0 0,0,288 0,84,252 0,180,180
8 144,0,216 120,60,180 72,108,108
16 192,0,144 144,36,108 48,36,36
Figura 11. Representación del juego en forma estratégica para los tres jugadores.
Ahora se calculará el valor de cada coalición ( ).
Empezando por la empresa 1: Si elige la estrategia 0, no importa que jueguen las
demás empresas, su pago será de 0. Si elige la estrategia 8, puede obtener alguna de las
siguientes cantidades dependiendo de las combinaciones de estrategias de las otras dos
empresas: 216, 192, 144, 168, 144, 96, 144, 120, 72. Entonces:
Si elige la estrategia 16 obtendrá un pago dependiendo de las combinaciones de
estrategias de las otras dos empresas y calculando el mínimo se obtiene:
.
Por tanto, la empresa 1 debe elegir aquella estrategia que le asegure el máximo de
los posibles beneficios, así el . Finalmente ( ) .
-
CAPÍTULO 3 3.2 Juegos cooperativos
47
Para la empresa 2 y para la empresa 3 los cálculos se realizan de manera análoga
obteniendo ( ) y ( ) respectivamente. Ahora, para la coalición {1,2},
se obtendría un pago resultante del pago de la suma de ambas empresas. Y de igual manera,
lo que busca la coalición es asegurar un beneficio máximo así que:
y ( ) como se observa
en la Figura 12.
x1 x2 Pago para la coalición {1, 2}
0 0 min {0, 0, 0} = 0
0 4 min {120, 96, 84} = 84
0 12 min {288, 216, 180} = 180
8 0 min {216, 168, 144} = 144
8 4 min {288, 216, 180} = 180
8 12 min {360, 240, 180} = 180
16 0 min {336, 240, 192} = 192
16 4 min {360, 240, 180} = 180
16 12 min {336, 184, 84} = 84
x1 x2 Pago para la coalición {1, 3}
0 0 min {0, 0, 0} = 0
0 8 min {216, 192, 144} = 144
0 12 min {288, 252, 180} = 180
8 0 min {216, 192, 144} = 144
8 8 min {336, 288, 192} = 192
8 12 min {360, 300, 180} = 180
16 0 min {336, 288, 192} = 192
16 8 min {360, 288, 144} = 144
16 12 min {336, 252, 84} = 84
x1 x2 Pago para la coalición {2, 3}
0 0 min {0, 0, 0} = 0
0 8 min {216, 168, 120} = 120
0 12 min {288, 216, 144} = 144
4 0 min {120, 96, 72} = 72
4 8 min {288, 216, 144} = 144
4 12 min {336, 240, 144} = 144
12 0 min {288, 216, 144} = 144
12 8 min {360, 240, 120} = 120
12 12 min {360, 216, 72} = 72
Figura 12. Representación del juego en forma estratégica para las coaliciones {1, 2}, {1, 3} y {2, 3}.
-
CAPÍTULO 3 3.2 Juegos cooperativos
48
Para la coalición {1,3} y {2,3} se trabajó de manera análoga y se obtuvieron los
valores ( ) ( ) respectivamente.
Por último, se calcula el valor de la coalición formada por las 3 empresas calculando
la suma de los pagos como se observa en la Figura 13.
Cuando la Empresa 3 utiliza la estrategia 0
Empresa 2 E
mp
resa
1
0 4 12
0 0 120 288
8 216 288 360
16 336 360 336
Cuando la Empresa 3 utiliza la estrategia 8
Empresa 2
Em
pre
sa 1
0 4 12
0 216 288 360
8 336 360 336
16 360 336 216
Cuando la Empresa 3 utiliza la estrategia 12
Empresa 2
Em
pre
sa 1
0 4 12
0 288 336 360
8 360 360 288
16 336 288 120
Figura 13. Representación del juego en forma estratégica para la coalición {1, 2, 3}.
Y como se quiere maximizar el beneficio se obtiene:
{
}
. Con ( )
Por tanto, la representación del juego de manera coalicional es:
( )
( ) ( ) ( ) ( ) ( ) = 48, ( ) = 192,
( ) = 144, ( ) = 360.
De igual manera, este juego es monótono, superaditivo y convexo.
-
CAPÍTULO 3 3.3 Conjunto de imputaciones
49
Definición 3.2.1 Un juego de manera coalicional se dice que es 0-normalizado si cumple
( ) . Si no es normalizado, para obtener la 0-normalización de un
juego se debe definir la función característica:
( ) ( ) ∑ ( ) , para toda .
Definición 3.2.2 Un juego de manera coalicional se dice que es (0,1)-normalizado si
cumple que ( ) y además ( )
Ejemplo 3.2.3 Si analizamos el juego del Ejemplo 3.2.1, resulta que no es 0-normalizado
ya que ( ) . Por consiguiente, tampoco es un juego (0,1)-normalizado.
Para 0-normalización tenemos que:
( ) ( ) ∑ ( )
Por ejemplo, para ( ) ( ) ( ) , y haciendo este
proceso para todas las coaliciones, el juego normalizado queda de la siguiente manera:
( ) ( ) ( ) ( ) ( ) = 0, ( ) = 350,000,
( ) = 425,000, ( ) = 425,000.
3.3 Conjunto de imputaciones
Ahora, ya sabemos que ( ) es un juego en su forma coalicional o de función
característica en donde es el conjunto de jugadores que deciden trabajar
conjuntamente para ganar el mayor beneficio. Pero el problema se presenta al no saber
cómo repartir el valor ( ) entre todos los jugadores.
-
CAPÍTULO 3 3.3 Conjunto de imputaciones