Inducción hacia atrás
La Inducción hacia atrás es el proceso de razonar atrás en el tiempo, desde el final de un problema o situación, para determinar una secuencia de acciones óptimas. Se procede, en primer lugar tomando en cuenta la última vez que se llevó a cabo una decisión y se elige qué hacer en ese momento. Con esta información, se puede entonces determinar lo que debería hacer en la penúltima decisión. Este proceso continúa atrás hasta que se ha determinado la mejor acción para cada situación posible (es decir, para cada posible conjunto de información) en cada punto en el tiempo.
En el método matemático de optimización programación dinámica, la inducción atrás es uno de los principales métodos para resolver la ecuación de Bellman.[1][2] En la teoría de juegos, la inducción atrás es un método utilizado para calcular el equilibrio perfecto en subjuegos en los juegos secuenciales.[3] La única diferencia es que la optimización implica un solo tomador de decisiones , que elige lo que debe hacer en cada momento del tiempo, mientras que la teoría de juegos analiza cómo las decisiones de varios jugadores interactúan. Es decir, mediante la previsión de lo que el último jugador que elige va a hacer en esa situación, es posible determinar que va a hacer el penúltimo jugador en elegir, y así sucesivamente. En los campos relacionados con la planificación automática y la programación automatizada y demostración automática de teoremas, el método se llama búsqueda atrás o encadenamiento hacia atrás . En el ajedrez se llama ajedrez retrospectivo.
La inducción atrás se ha utilizado para resolver juegos desde que la teoría de juegos ha existido. John von Neumann y Oskar Morgenstern sugieren la solución de un juego de suma cero, juegos de dos personas por inducción atrás en su libro Teoría de Juegos y Comportamiento Económico (1944), el libro que estableció la teoría de juegos como un campo de estudio.[4][5] El concepto de inducción hacia atrás también está relacionado con el Premio Nobel de Economía Reinhard Selten, uno de los creadores del concepto de equilibrio perfecto en subjuegos, la noción de equilibrio de referencia para juegos secuenciales.
Ejemplos
editarProblema de decisión individual
editarPartimos de un individuo desempleado con capacidad para trabajar 10 años más (T=10). Imaginemos que cada año que se encuentra sin empleo, puede llegarle una buena oferta de trabajo remunerado con 100 euros, o una mala oferta de trabajo remunerada con 44 euros, exactamente con la misma probabilidad (50%). Si decide aceptar una de las 2 ofertas, permanecerá en ese trabajo durante 10 años. "¿Debería este individuo aceptar malas ofertas de trabajo?" Podemos responder a esta pregunta a través de la inducción hacia atrás.
- En el año 10 (t=10), el valor de aceptar una buena oferta de trabajo es de 100 euros, y el de aceptar una mala oferta de trabajo es de 44 euros, si rechazamos las ofertas recibimos 0 euros. Por lo que si el individuo en el último período sigue sin empleo debe aceptar cualquier trabajo.
- En el año 9 (t=9), el valor de aceptar una buena oferta de trabajo es de 200 euros, y el de aceptar una mala oferta de trabajo es de 88 euros (44*2). Si rechazamos una oferta de trabajo recibimos 0 euros, más el valor de esperar la próxima oferta de trabajo, 100 euros o 44 euros con 50% de probabilidad, valor esperado = 72 euros (0,5*(100+44)). Por lo que, independientemente de si la oferta es buena o mala debe aceptar esa oferta en vez de esperar otra mejor.
- En el año 8 (t=8),el valor de aceptar una buena oferta de trabajo es de 300 euros, y el de aceptar una mala oferta de trabajo es de 132 euros (44*3). Si rechazamos una oferta de trabajo recibimos 0 euros, más el valor esperado de esperar una oferta de trabajo en el año 9. Como sabemos que las ofertas en el año 9 deben aceptarse, el valor esperado de esperar una oferta de trabajo en el año 9 será = 144 euros (0,5*(200+88)). Por lo que, en el año 8, es preferible esperar una nueva oferta de trabajo que aceptar una mala.
Como conclusión obtenemos que las ofertas malas solo se deberían aceptar si no se tiene empleo en los años 9 o 10, rechazándose hasta el año 8. Si pensamos que vamos a ocupar un puesto de trabajo durante varios años, deberíamos ser exigentes con las distintas ofertas.
Inducción hacia atrás en un problema de decisión secuencial
editar
En la imagen anterior se muestra un ejemplo para un juego que posee un Equilibrio de Nash no perfecto y un equilibrio perfecto en subjuegos. Las estrategias para el jugador 1 vienen dadas por {L,R} mientras que el jugador 2 tiene la opción entre {K,U}.
Matriz de pagos que nos permite hallar los equilibrios del juego
editar
Equilibrio perfecto en subjuegos {R(U1,K2)} Equilibrio de Nash no perfecto {L(U1,U2)} Para aplicar el algoritmo de inducción hacia atrás, comenzamos el análisis por los nodos finales (aquellas decisiones donde el juego acabaría). Los correspondientes al jugador 2. Si 2 tuviera que mover en el nodo izquierdo elegiría U1, puesto que (3 es mayor que 1). S i tuviese que mover en el nodo de la derecha elegiría K2 (1 es mayor que 0). Considerando ahora el único nodo "penúltimo" el del jugador 1, como este jugador sabe anticipar lo que hará el jugador 2 racional, 1 elegirá R ( 2 es mayor que 1).
Teniendo entonces 2 equilibrios, {R(U1,K2)} Equilibrio de Nash Perfecto en Subjuegos y {L(U1,U2)}Equilibrio de Nash no Perfecto.
Juego del Ultimátum
editarConsidere el juego del ultimátum , donde un jugador propone dividir cierta cantidad de dinero con otro (suponemos que ambos jugadores son egoístas). El primer jugador (el proponente) sugiere una división entre los dos jugadores. El segundo jugador tiene la opción de aceptar la división o rechazarla. Si el segundo jugador acepta, ambos obtienen la cantidad sugerida por el proponente. Si es rechazado, ninguno recibe nada. Considere las acciones del segundo jugador dada cualquier propuesta arbitraria del primer jugador (que le da al segundo jugador más de cero). Como la única opción que tiene el segundo jugador en cada uno de estos puntos del juego es elegir entre algo y nada, uno puede esperar que el segundo acepte. Dado que el segundo aceptará todas las propuestas ofrecidas por el primero (que le dan al segundo nada), el primero debe proponer dar el segundo lo menos posible. Este es el único equilibrio perfecto en subjuegos del juego del ultimátum. (Sin embargo, el juego del ultimátum tiene muchos otros equilibrios de Nash que no son perfectos para el subjuego).
Juego del Ciempiés (versión reducida)
editarRepresenta una situación en la que es beneficioso para ambos jugadores continuar el juego, aun cuando uno de los jugadores quiera terminar hoy, si supiese que el otro está dispuesto a terminarlo mañana. Nuestro juego se desarrolla en 3 fases, en las cuales los jugadores deciden Continuar (C) o Terminar (T).
- En primer lugar, situémonos en el final del juego donde el jugador 1 debe elegir entre Continuar con un (pago =2), o Terminar con (pago =3). Claramente elegirá Terminar.
- En segundo lugar, el jugador 2( que sabe que el jugador 1 es racional) tiene que decidir entre Terminar con un (pago=4), o Continuar con (pago=3). Evidentemente elegirá Terminar.
- Y por último, el jugador 1 debe elegir Terminar con un (pago=1), o Continuar con un (pago=0).Elegirá Terminar.
Equilibrio de Nash (T,T,T) Los pagos del nodo final del juego, (3,3) y (2,5), son ambos estrictamente mejores que la solución de equilibrio (1,1). Pero esos resultados no se pueden alcanzar, dado que el jugador 2 no continuará, por lo que el jugador 1 anticipándose decide Terminar el juego.
Aplicaciones
editarAplicación de la inducción hacia atrás a los juegos de mesa
editarHay juegos como las damas y el ajedrez que se caracterizan por ser juegos finitos con información perfecta. El poder aplicarles la inducción hacia atrás permite encontrar los resultados perfectos en subjuegos, esto tiene gran relevancia respecto a la búsqueda de buenas estrategias de juego. Si enfrentásemos a un jugador cualquiera, contra un ordenador capaz de aplicar el algoritmo de inducción hacia atrás a juegos tan complejos como el ajedrez o las damas, nuestro jugador saldría siempre perdedor. Puesto que, el ordenador sabría que estrategia jugar en cada momento del juego para alcanzar la victoria.
Inducción hacia atrás y entrada económica
editarConsidere un juego dinámico en el cual los jugadores son 2 empresas, una empresa establecida en una industria y otra con posibilidad de ingresar en esa industria. La empresa establecida tiene el monopolio de la industria y no quiere perder participación en el mercado. Si la otra empresa decide no ingresar, la empresa ya establecida recibe un pago elevado (mantiene su monopolio) y la nueva ni pierde ni gana (su pago es cero). Si la nueva empresa decide ingresar, la empresa ya establecida puede "pelear" o "acomodar" a la nueva. Luchará bajando su precio, haciendo que la nueva empresa salga del negocio (e incurra en costes de salida, un beneficio negativo) y dañe sus propios beneficios. Si decide acomodar, perderá algunas de sus ventas, pero mantendrá un precio elevado y recibirá mayores ganancias que bajando su precio (pero menor que las ganancias del monopolio). Considere si la mejor respuesta del monopolista es adaptarse si la nueva empresa decide ingresar. Si el monopolista se acomoda, la mejor respuesta de la nueva empresa es ingresar (y obtener ganancias). Por lo tanto, el perfil de estrategias en el que entra la nueva y el monopolista se acomoda es un equilibrio de Nash consistente con la inducción hacia atrás. Sin embargo, si el monopolista pelea, la mejor respuesta de la nueva es no ingresar, y si la nueva no ingresa, no importa lo que el monopolista decida hacer. Por lo tanto, el perfil de estrategias en el que pelea el monopolista si entra la nueva, pero la nueva no entra también es un equilibrio de Nash. Sin embargo, si la nueva ingresara, la mejor respuesta del monopolista es acomodarse: la amenaza de enfrentamientos no es creíble. Este segundo equilibrio de Nash puede por lo tanto ser eliminado por inducción hacia atrás.
Paradoja del Ahorcado
editarSupongamos que a un prisionero se le dice que será ahorcado en algún momento entre el lunes y el viernes de la próxima semana. Sin embargo, el día exacto será una sorpresa (es decir, no sabrá la noche anterior que será ejecutado al día siguiente). El prisionero, interesado en burlar a su verdugo, intenta determinar qué día ocurrirá la ejecución. El razona que no puede ocurrir el viernes, ya que si no hubiera ocurrido antes del final del jueves, sabría que la ejecución sería el viernes. Por lo tanto, el puede eliminar el viernes como una posibilidad. Con el viernes eliminado, decide que no puede ocurrir el jueves, ya que si no hubiera ocurrido el miércoles, el sabría que tenía que ser el jueves. Por lo tanto, el puede eliminar el jueves. Este razonamiento continúa hasta que haya eliminado todas las posibilidades. El concluye que no será ahorcado la próxima semana. Para su sorpresa, le cuelgan el miércoles. Cometió el error de suponer que sabía de manera definitiva si el factor futuro desconocido que podría causar su ejecución podía razonar. Aquí el prisionero razona por inducción hacia atrás, pero parece llegar a una conclusión falsa. Sin embargo, tenga en cuenta que la descripción del problema supone que es posible sorprender a alguien que está realizando una inducción hacia atrás. La teoría matemática de la inducción hacia atrás no hace esta suposición, por lo que la paradoja no cuestiona los resultados de esta teoría.
Referencias
editar- ↑ Jerome Adda and Russell Cooper, "Dynamic Economics: Quantitative Methods and Applications", Section 3.2.1, page 28. MIT Press, 2003.
- ↑ Mario Miranda and Paul Fackler, "Applied Computational Economics and Finance", Section 7.3.1, page 164. MIT Press, 2002.
- ↑ Drew Fudenberg and Jean Tirole, "Game Theory", Section 3.5, page 92. MIT Press, 1991.
- ↑ John von Neumann and Oskar Morgenstern, "Theory of Games and Economic Behavior", Section 15.3.1. Princeton University Press. Third edition, 1953. (First edition, 1944.)
- ↑ Mathematics of Chess Archivado el 12 de noviembre de 2017 en Wayback Machine., webpage by John MacQuarrie.
Datos: Q968642
Multimedia: Category:Backward induction / Q968642
