¿Qué es la Teoría de Juegos en programación?


La teoría de juegos es una rama de la Matemática que se encarga de estudiar el comportamiento de ciertos individuos (jugadores) y su toma de decisiones.

Esta fue creada por el matemático Von Neumann junto con Morgenstern, en la publicación “TheTheory of Games and Economic Behavior”, aunque anteriormente ya se habían tratado algunos conceptos, pero ninguno fue tan a fondo.

John Von Neumann

Fig1: John Von Neumann

La teoría de juegos abarca varios campos de la ciencia como son la sociología, la biología y la informática, entre otras. Uno de los problemas más famosos de la teoría de juegos es el Dilema del Prisionero. Este consiste en que se arrestan a dos individuos (A y B) pero no se tienen las pruebas suficientes para encarcelarlos, entonces se decide ubicarlos en celdas diferentes e interrogarlos por separado. Entonces a cada uno se le ofrece una propuesta: si ambos se niegan a declararse culpable entonces son condenados a 3 años, si ambos confiesan entonces son condenados a 4 años y si uno confiesa y el otro no entonces el que habla recibe la libertad y el que calla recibe la pena de 8 años.

DILEMA DEL PRISIONERO:

  B confiesa B calla
A confiesa Ambos son condenados a 4 años. A es liberado, B es condenado 8 años.
A calla B es liberado, A es condenado 8 años. A y B son condenados a 3 años.

 

 

¿Qué harías si estuvieras en esta situación? callas, confiesas. Pues esto y mucho más estudia la teoría de juegos, y una de las clásicas representaciones es conocida, como matriz de pago. Veamos cómo queda la matriz de pago del Dilema del Prisionero:

Matriz de Pago:

  B confiesa B calla
A confiesa -4 , -4 0 , -8
A calla -8 , 0 -3 , -3

 

Claramente se puede ver que para los dos jugadores existe una decisión que trae el mejor resultado para ambos en conjunto, que es A confiesa y B confiesa, esto es lo que se llama Equilibrio de Nash.

El equilibrio de Nash no es más que la situación donde cada jugador utiliza una estrategia para maximizar su propio beneficio y bajo ningún concepto este puede modificar su estrategia para lograr un beneficio mayor que el de los demás jugadores. Esto garantiza el mejor resultado en conjunto para todos.

Juegos Combinatorios:

Uno de los tipos de juegos que más aplicaciones tiene, son los juegos donde no interviene el azar (esto lo veremos en próximos artículos). Algunos juegos clásicos de este tipo son los juegos de Nim, Hackenbush, y otros juegos de tablero en los cuales la teoría de Sprague-Grundy juega un papel fundamental.

Imágenes de NIM, HACKENBUSH

Juego de Nim

Fig2: Juego de Nim

Juego de Hackenbush

Fig3: Juego de Hackenbush

Como vemos, la teoría de juegos es una rama de la matemática que puede sernos de mucha ayuda en diversos campos de la informática. Muchos de los problemas que estudia este campo, permiten dar soluciones óptimas a desafíos reales. Es por esto que a lo largo de una serie de artículos que se publicarán después de este, conoceremos la utilidad y la importancia que tiene para la vida, además de que veremos problemas clásicos que muchas veces por el mero desconocimiento somos incapaces de resolver. Con más, hasta la próxima y si tienen alguna duda o sugerencia, pueden reflejarla en los comentarios.