El dilema del estudiante~ o (teoria de juegos)

La teoría de juegos es un área de la matemática aplicada que utiliza modelos para estudiar interacciones en estructuras formalizadas de incentivos (los llamados juegos) y llevar a cabo procesos de decisión. Sus investigadores estudian las estrategias óptimas así como el comportamiento previsto y observado de individuos en juegos.

La forma normal (o forma estratégica) de un juego es una Matriz que muestra los jugadores, las estrategias, y las recompensas.

Cuando un juego se presenta en forma normal, se presupone que todos los jugadores actúan simultáneamente o, al menos, sin saber la elección que toma el otro.

La representación de juegos en forma extensiva modela juegos con algún orden que se debe considerar. Los juegos se presentan como árboles. Cada vértice o nodo representa un punto donde el jugador toma decisiones. El jugador se especifica por un número situado junto al vértice. Las líneas que parten del vértice representan acciones posibles para el jugador. Las recompensas se especifican en las hojas del árbol.

Tipos de juegos:

Juegos simétricos y asimétricos

Un juego simétrico es un juego en el que las recompensas por jugar una estrategia en particular dependen sólo de las estrategias que empleen los otros jugadores y no de quién las juegue. Si las identidades de los jugadores pueden cambiarse sin que cambien las recompensas de las estrategias, entonces el juego es simétrico. Muchos de los juegos 2×2 más estudiados son simétricos. Las representaciones estándar del juego de la gallina, el dilema del prisionero y la caza del ciervo son juegos simétricos.

Los juegos asimétricos más estudiados son los juegos donde no hay conjuntos de estrategias idénticas para ambos jugadores. Por ejemplo, el juego del ultimátum y el juego del dictador tienen diferentes estrategias para cada jugador; no obstante, puede haber juegos asimétricos con estrategias idénticas para cada jugador.

Juegos de suma cero y de suma no cero

En los juegos de suma cero el beneficio total para todos los jugadores del juego, en cada combinación de estrategias, siempre suma cero (en otras palabras, un jugador se beneficia solamente a expensas de otros). El go, el ajedrez, el póker y el juego del oso son ejemplos de juegos de suma cero, porque se gana exactamente la cantidad que pierde el oponente. Como curiosidad, el fútbol dejó hace unos años de ser de suma cero, pues las victorias reportaban 2 puntos y el empate 1 (considérese que ambos equipos parten inicialmente con 1 punto), mientras que en la actualidad las victorias reportan 3 puntos y el empate 1.

La mayoría de los ejemplos reales en negocios y política, al igual que el dilema del prisionero, son juegos de suma no cero, porque algunos desenlaces tienen resultados netos mayores o menores que cero. Es decir, la ganancia de un jugador no necesariamente se corresponde con la pérdida de otro. Por ejemplo, un contrato de negocios involucra idealmente un desenlace de suma positiva, donde cada oponente termina en una posición mejor que la que tendría si no se hubiera dado la negociación.

Se puede analizar más fácilmente un juego de suma cero, y cualquier juego se puede transformar en un juego de suma cero añadiendo un jugador "ficticio" adicional ("el tablero" o "la banca"), cuyas pérdidas compensen las ganancias netas de los jugadores.

Juegos cooperativos

Un juego con situacion cooperativa se caracteriza por un contrato que puede hacerse cumplir. La teoría de los juegos cooperativos da justificaciones de contratos plausibles. La plausibilidad de un contrato está muy relacionada con la estabilidad.

Dos jugadores negocian qué tanto quieren invertir en un contrato. La teoría de la negociación axiomática nos muestra cuánta inversión es conveniente para nosotros. Por ejemplo, la solución de Nash para la negociación demanda que la inversión sea justa y eficiente.

De cualquier forma, podríamos no estar interesados en la justicia y exigir más. De hecho, existe un juego no-cooperativo creado por Ariel Rubinstein consistente en alternar ofertas, que apoya la solución de Nash considerándola la mejor, mediante el llamado equilibrio de Nash.

Simultáneos y secuenciales

Los juegos simultáneos son juegos en los que los jugadores mueven simultáneamente o en los que éstos desconocen los movimientos anteriores de otros jugadores. Los juegos secuenciales (o dinámicos) son juegos en los que los jugadores posteriores tienen algún conocimiento de las acciones previas. Este conocimiento no necesariamente tiene que ser perfecto; sólo debe consistir en algo de información. Por ejemplo, un jugador1 puede conocer que un jugador2 no realizó una acción determinada, pero no saber cuál de las otras acciones disponibles eligió.

Juegos de información perfecta

Un juego es de información perfecta si todos los jugadores conocen los movimientos que han efectuado previamente todos los otros jugadores; así que sólo los juegos secuenciales pueden ser juegos de información perfecta, pues en los juegos simultáneos no todos los jugadores (a menudo ninguno) conocen las acciones del resto. La mayoría de los juegos estudiados en la teoría de juegos son juegos de información imperfecta, aunque algunos juegos interesantes son de información perfecta, incluyendo el juego del ultimátum y el juego del ciempiés.

La información perfecta se confunde a menudo con la información completa, que es un concepto similar. La información completa requiere que cada jugador conozca las estrategias y recompensas del resto pero no necesariamente las acciones.

En los juegos de información completa cada jugador tiene la misma "información relevante al juego" que los demás jugadores. El ajedrez y el dilema del prisionero ejemplifican juegos de información completa.

Tipos de estrategias

Estrategia dominante

Se dice que un jugador posee una estrategia dominante si una estrategia particular es preferida a cualquier otra estrategia a disposición de el. Es posible que cada uno de los dos jugadores tenga estrategia dominante.

OJO POR OJO (en inglés TIT FOR TAT).

Supongamos que dos jugadores repiten de forma indefinida una situación con pagos de forma del Dilema del Prisionero:

En esta situación la estrategia OJO POR OJO puede quedar definida de la forma siguiente: "En la primera jugada elegiré la estrategia COOPERAR. En las jugadas siguientes elegiré la misma estrategia que haya elegido mi oponente en la jugada anterior". En otras palabras, si el otro coopera, yo cooperaré con él. Si el otro es un traidor, yo seré un traidor".

Estrategía TORITO (en inglés "BULLY").

Esta estrategia consiste en hacer lo contrario que haga el oponente: "Si el otro jugador es leal en una jugada, yo le traicionaré en la siguiente; si el otro jugador me ha traicionado, yo le seré leal a la siguiente oportunidad".

Equilibrio de Nash

El equilibrio de Nash fue formulado por John Nash, que es un matemático norteamericano, en 1951. Un par de estrategias es un equilibrio de Nash si la elección de A es óptima dada la de B y la de B es óptima, dada la de A. El equilibrio de Nash se diferencia del equilibrio de las estrategias dominantes en que, en el equilibrio de las estrategias dominantes, se exige que la estrategia de A sea óptima en el caso de todas las elecciones óptimas de B, y viceversa. El equilibrio de Nash es menos restrictivo que el equilibrio de estrategias óptimas.



*Extra*

Seguramente todos conoceran el juego de piedra, papel o tijera~
Este juego puede verse desde el enfoque de la teoria de juegos =O
Aqui los jugadores son tu y tu amigo/rival/etc, sus diferentes estrategias a seguir seria el elegir piedra, papel o tijera!

La matriz de pagos quedaria algo asi:

....................oponente
....................papel.......tijera.......piedra
.....papel........0,0..........-1,1...........1,1
Tu.tijera........1,-1..........0,0...........-1,1
.....piedra......-1,1.........1,-1...........0,0

¿Que tipo de juego es?
Asi es, un juego de informacion perfecta de suma cero, ademas de simetrico

Debido a que este juego no tiene ninguna estrategia dominante, ni ningun tipo de equilibrio no es muy interesante de analizar para la teoria de juegos.

Pero como hemos tratado en clases anteriores sobre inteligencia artificial, pues hice un programa con "inteligencia" que juega piedra, papel o tijera.

Se anexa el codigo:
https://docs.google.com/Doc?docid=0AbozH-ZdB4BqZGY3em13d21fNWZqdjk4emM2&hl=en

El programa es muy sencillo y su unico fin es para ilustrar un concepto, claro que mis habilidades para programar no facilitan su entendimiento, aun asi el programa es muy intuitivo.

Nota: por falta de tiempo se quedo un pequeño bug al comienzo =p y solo sigan las instrucciones y hagan lo que el programa pregunta porque si no explota =)

El programa hace uso del concepto de machine lerning para jugar.

La idea es que el programa tiene una funcion de evaluacion (toma en cuenta los 4 anteriores movimientos del rival ademas del resultado del cada uno de esos juegos (victoria, derrota, empate)) y en base a estos resultados predice el movimiento que hara el rival y hace el movimiento ganador.

Dependiendo del resultado, si gana, empata o pierde, la funcion se altera un poco.

No esta muy bien pensado pero bueno.