La inducción hacia atrás es el proceso de determinar una secuencia de elecciones óptimas razonando desde el punto final de un problema o situación hasta su comienzo a través de eventos o acciones individuales (punto por punto). [1] La inducción hacia atrás implica examinar el punto final de una serie de decisiones e identificar el proceso o acción más óptima necesaria para llegar a ese punto. Este proceso continúa hacia atrás hasta que se determina la mejor acción para cada punto posible a lo largo de la secuencia (es decir, para cada conjunto de información posible). La inducción hacia atrás fue utilizada por primera vez en 1875 por Arthur Cayley , quien descubrió el método mientras intentaba resolver el problema de la secretaria . [2]
En programación dinámica , un método de optimización matemática , la inducción hacia atrás es un método para resolver la ecuación de Bellman . [3] [4] En los campos relacionados de la planificación y programación automatizadas y la demostración automatizada de teoremas , el método se denomina búsqueda hacia atrás o encadenamiento hacia atrás . En ajedrez, se llama análisis retrógrado .
En teoría de juegos , una variante de la inducción hacia atrás es un método utilizado para calcular equilibrios perfectos en subjuegos en juegos secuenciales . [5] La diferencia es que los problemas de optimización involucran a un tomador de decisiones que elige qué hacer en cada momento, mientras que los problemas de teoría de juegos involucran las decisiones de varios jugadores que interactúan. En esta situación todavía puede ser posible aplicar una generalización de la inducción hacia atrás, ya que al anticipar lo que hará el último jugador en cada situación, puede ser posible determinar lo que hará el penúltimo jugador, y así sucesivamente. Esta variante de inducción hacia atrás se ha utilizado para resolver juegos formales desde los inicios de la teoría de juegos. John von Neumann y Oskar Morgenstern sugirieron resolver juegos formales de dos personas de suma cero mediante este método en su Teoría de los juegos y el comportamiento económico (1944), el libro que estableció la teoría de juegos como un campo de estudio. [6] [7]
Una persona que se enfrenta a diez años de posibles oportunidades de empleo (indicadas como multiplicadas por 1, 2,... 10) puede tener que elegir entre dos opciones laborales: un trabajo "bueno" que ofrece un salario de 100 dólares o un trabajo "malo" que ofrece un salario de $44. Cada tipo de trabajo tiene la misma probabilidad de ser ofrecido. Al aceptar un trabajo, la persona permanecerá en ese trabajo en particular durante el resto de los diez años.
Este escenario se simplifica suponiendo que la única preocupación del individuo son sus ingresos monetarios totales esperados, sin ninguna preferencia variable por los ingresos en diferentes períodos. En términos económicos, este es un escenario con una tasa de interés implícita de cero y una utilidad marginal constante del dinero.
Si la persona en cuestión debería aceptar un "mal" trabajo se puede decidir razonando hacia atrás desde el momento 10.
Se puede comprobar, trabajando hacia atrás, que una "mala" oferta sólo debe aceptarse si la persona todavía está desempleada en el momento 9 o 10; una mala oferta debe ser rechazada en cualquier momento hasta el 8. Generalizando este ejemplo intuitivamente, corresponde al principio de que si uno espera trabajar en un empleo durante mucho tiempo, vale la pena elegirlo con cuidado.
Un problema de optimización dinámica de este tipo se denomina problema de detención óptima porque la cuestión en cuestión es cuándo dejar de esperar una oferta mejor. La teoría de la búsqueda es un campo de la microeconomía que aplica modelos de este tipo a cuestiones como las compras, la búsqueda de empleo y el matrimonio.
En teoría de juegos , la inducción hacia atrás es un concepto de solución que se deriva de la aplicación de la racionalidad secuencial para identificar una acción óptima para cada conjunto de información en un árbol de juego determinado . Desarrolla las implicaciones de la racionalidad a través de conjuntos de información individuales en la representación extensiva de un juego. [8]
Para resolver un equilibrio perfecto en subjuegos con inducción hacia atrás, el juego debe escribirse en forma extensiva y luego dividirse en subjuegos . Comenzando con el subjuego más alejado del nodo inicial, o punto de partida, se pesan los pagos esperados enumerados para este subjuego, y un jugador racional seleccionará la opción con el mayor pago para sí mismo. Se selecciona y marca el vector de pago más alto. Para resolver el equilibrio perfecto en subjuegos, se debe trabajar continuamente hacia atrás de un subjuego a otro hasta llegar al punto de partida. A medida que avanza este proceso, el juego inicial en forma extensiva se hará cada vez más corto. El camino marcado de los vectores es el equilibrio perfecto en subjuegos. [9]
Esta idea de inducción hacia atrás en la teoría de juegos se puede demostrar con un ejemplo sencillo.
Un primer ejemplo natural es un juego de varias etapas en el que participan dos jugadores. Los jugadores planean ir al cine. Actualmente, 2 películas son muy populares, Joker y Terminator. El jugador 1 quiere ver Terminator y el jugador 2 quiere ver Joker. El jugador 1 comprará un boleto primero y le informará al jugador 2 sobre su elección. Luego, el jugador 2 comprará su billete. Una vez que ambos observan las elecciones, en la segunda etapa, eligen si ir al cine o quedarse en casa. Al igual que en la primera etapa, el jugador 1 elige primero, luego el jugador 2 hace su elección después de observar la elección del jugador 1.
En este ejemplo, los pagos se suman en diferentes etapas. El juego es un juego de información perfecto .
Representación en forma extensiva :
Pasos para resolver este juego de varias etapas, en formato extenso como se ve a la derecha:
La inducción hacia atrás sólo se puede aplicar a clases limitadas de juegos. El procedimiento está bien definido para cualquier juego de información perfecta y sin ataduras de utilidad. También está bien definido y es significativo para juegos de información perfecta con vínculos. Sin embargo, en tales casos conduce a más de una estrategia perfecta. El procedimiento se puede aplicar a algunos juegos con conjuntos de información no trivial, pero no es aplicable en general. Es más adecuado para resolver juegos con información perfecta. Si todos los jugadores no son conscientes de las acciones y pagos de los demás jugadores en cada nodo de decisión, entonces la inducción hacia atrás no se aplica tan fácilmente. [10]
Además, incluso en juegos que formalmente permiten la inducción hacia atrás en teoría, es posible que no prediga con precisión el juego empírico en la práctica. Esto se puede demostrar con un segundo ejemplo.
Un segundo ejemplo, más famoso, de juego asimétrico consiste en dos jugadores: el jugador 1 propone dividir un dólar con el jugador 2, lo que el jugador 2 luego acepta o rechaza. Esto se llama el juego del ultimátum . El jugador 1 actúa primero dividiendo el dólar como mejor le parezca. A continuación, el jugador 2 acepta la parte que le ha ofrecido el jugador 1 o rechaza la división. Si el jugador 2 acepta la división, tanto el jugador 1 como el jugador 2 obtienen los pagos correspondientes a esa división. Si el jugador 2 decide rechazar la oferta del jugador 1, ambos jugadores no recibirán nada. En otras palabras, el Jugador 2 tiene poder de veto sobre la asignación propuesta por el Jugador 1, pero aplicar el veto elimina cualquier recompensa para ambos jugadores. [11]
Considerando la elección y respuesta del Jugador 2 ante cualquier propuesta arbitraria del Jugador 1, la racionalidad formal prescribe que el Jugador 2 aceptaría cualquier pago mayor o igual a $0. En consecuencia, mediante inducción hacia atrás, el jugador 1 debería proponer darle al jugador 2 lo menos posible para ganar la mayor parte de la división. El jugador 1 que le da al jugador 2 la unidad de dinero más pequeña y se queda con el resto es el único equilibrio perfecto en subjuegos. El juego del ultimátum tiene varios otros equilibrios de Nash que no son perfectos en subjuegos y, por lo tanto, no surgen mediante inducción hacia atrás.
El juego del ultimátum es una ilustración teórica de la utilidad de la inducción hacia atrás cuando se consideran juegos infinitos, pero los resultados teóricamente predichos del juego del ultimátum no coinciden con la observación empírica. La evidencia experimental ha demostrado que un proponente, el Jugador 1, rara vez ofrece $0 y el respondedor, el Jugador 2, a veces rechaza ofertas superiores a $0. Lo que el Jugador 2 considera aceptable varía según el contexto. La presión o presencia de otros jugadores y las implicaciones externas pueden significar que el modelo formal del juego no necesariamente puede predecir lo que elegirá una persona real. Según Colin Camerer , un economista conductual estadounidense, el jugador 2 "rechaza ofertas inferiores al 20 por ciento de X aproximadamente la mitad de las veces, aunque terminan sin nada". [12]
Si bien la inducción hacia atrás, asumiendo la racionalidad formal, predeciría que un respondedor aceptaría cualquier oferta mayor que cero, los respondedores en realidad no son jugadores formalmente racionales y, por lo tanto, a menudo parecen preocuparse más por la "justicia" de la oferta o quizás por otras anticipaciones de efectos indirectos o externos que por la racionalidad formal. ganancias monetarias potenciales inmediatas.
Se debe considerar un juego dinámico en el que los jugadores son una empresa establecida en una industria y un entrante potencial en esa industria. Tal como están las cosas, el operador actual tiene el monopolio de la industria y no quiere perder parte de su participación de mercado en favor del entrante. Si el entrante decide no ingresar, la recompensa para el titular es alta (mantiene su monopolio) y el entrante no pierde ni gana (su recompensa es cero). Si el entrante ingresa, el titular puede "luchar" o "acomodar" al entrante. Luchará bajando su precio, sacando del negocio al entrante (e incurriendo en costos de salida, una recompensa negativa) y dañando sus propias ganancias. Si se adapta al entrante perderá algunas de sus ventas, pero mantendrá un precio alto y recibirá mayores ganancias que si bajara su precio (pero menores que las ganancias del monopolio).
Si el titular se adapta, dado el caso de que el entrante ingrese, la mejor respuesta para el entrante es ingresar (y obtener ganancias). Por lo tanto, el perfil de estrategia en el que entra el entrante y el establecido se acomoda si el entrante entra es un equilibrio de Nash consistente con la inducción hacia atrás. Sin embargo, si el titular va a pelear, la mejor respuesta para el entrante es no ingresar, y si el entrante no ingresa, no importa lo que el titular decida hacer en el caso hipotético de que el entrante ingrese. Por lo tanto, el perfil de estrategia en el que el titular lucha si el entrante entra, pero el entrante no entra, también es un equilibrio de Nash. Sin embargo, si el entrante se desvía y entra, la mejor respuesta del titular es adaptarse: la amenaza de pelear no es creíble. Por tanto, este segundo equilibrio de Nash puede eliminarse mediante inducción hacia atrás.
Encontrar un equilibrio de Nash en cada proceso de toma de decisiones (subjuego) constituye un equilibrio perfecto en subjuego. Por lo tanto, estos perfiles estratégicos que representan equilibrios perfectos en subjuegos excluyen la posibilidad de acciones como amenazas increíbles que se utilizan para "asustar" a un participante. Si el operador actual amenaza con iniciar una guerra de precios con un entrante, está amenazando con bajar sus precios desde un precio de monopolio a un precio ligeramente inferior al del entrante, lo que sería poco práctico e increíble si el entrante supiera que en realidad no se produciría una guerra de precios. ya que resultaría en pérdidas para ambas partes. A diferencia de una optimización de agente único que incluye equilibrios que no son factibles u óptimos, un equilibrio perfecto en subjuegos tiene en cuenta las acciones de otro jugador, asegurando así que ningún jugador llegue a un subjuego por error. En este caso, la inducción hacia atrás que produce equilibrios perfectos en subjuegos garantiza que el entrante no estará convencido de la amenaza del titular sabiendo que no fue la mejor respuesta en el perfil de estrategia. [13]
La inesperada paradoja del ahorcamiento es una paradoja relacionada con la inducción hacia atrás. El prisionero descrito en la paradoja utiliza la inducción hacia atrás para llegar a una conclusión falsa. 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 parte de esta suposición, por lo que la paradoja no pone en duda los resultados de esta teoría.
La inducción hacia atrás funciona sólo si ambos jugadores son racionales , es decir, siempre seleccionan una acción que maximice su recompensa. Sin embargo, la racionalidad no es suficiente: cada jugador también debería creer que todos los demás jugadores son racionales. Incluso esto no es suficiente: cada jugador debe creer que todos los demás jugadores saben que todos los demás jugadores son racionales, y así sucesivamente, hasta el infinito. En otras palabras, la racionalidad debería ser de conocimiento común . [14]
La inducción hacia atrás limitada es una desviación de la inducción hacia atrás totalmente racional. Implica poner en práctica el proceso regular de inducción hacia atrás sin una previsión perfecta. En teoría, esto ocurre cuando uno o más jugadores tienen una previsión limitada y no pueden realizar una inducción hacia atrás a través de todos los nodos terminales. [15] La inducción hacia atrás limitada juega un papel mucho más importante en juegos más largos, ya que los efectos de la inducción hacia atrás limitada son más potentes en períodos posteriores de los juegos.
Los experimentos han demostrado que en los juegos de negociación secuencial, como el juego del ciempiés , los sujetos se desvían de las predicciones teóricas y, en cambio, participan en una inducción regresiva limitada. Esta desviación se produce como consecuencia de una racionalidad limitada , donde los jugadores sólo pueden ver perfectamente unas pocas etapas por delante. [16] Esto permite la imprevisibilidad en las decisiones y la ineficiencia a la hora de encontrar y lograr equilibrios de Nash perfectos en subjuegos .
Hay tres hipótesis generales para este fenómeno:
Las violaciones de la inducción hacia atrás se atribuyen predominantemente a la presencia de factores sociales. Sin embargo, las predicciones de modelos basados en datos para juegos de negociación secuencial (utilizando el modelo de jerarquía cognitiva ) han puesto de relieve que en algunos juegos la presencia de una inducción hacia atrás limitada puede desempeñar un papel dominante. [17]
En juegos repetidos de bienes públicos, el comportamiento del equipo se ve afectado por una inducción regresiva limitada; donde es evidente que las contribuciones iniciales de los miembros del equipo son mayores que las contribuciones hacia el final. La inducción regresiva limitada también influye en la regularidad con la que se produce el aprovechamiento gratuito dentro del juego de bienes públicos de un equipo. Al principio, cuando los efectos de la inducción hacia atrás limitada son bajos, el parasitismo es menos frecuente, mientras que hacia el final, cuando los efectos son altos, el parasitismo se vuelve más frecuente. [18]
También se ha probado la inducción hacia atrás limitada dentro de una variante del juego de carreras. En el juego, los jugadores elegirían secuencialmente números enteros dentro de un rango y sumarían sus elecciones hasta alcanzar un número objetivo. Alcanzar el objetivo le otorga al jugador un premio; el otro pierde. A mitad de una serie de juegos, se introdujo un pequeño premio. Luego, la mayoría de los jugadores realizaron una inducción regresiva limitada, ya que resolvieron el premio pequeño en lugar del premio original. Sólo una pequeña fracción de jugadores consideró ambos premios al principio. [19]
La mayoría de las pruebas de inducción hacia atrás se basan en experimentos, en los que los participantes son incentivados sólo en pequeña medida para realizar bien la tarea, si es que lo hacen. Sin embargo, las violaciones de la inducción hacia atrás también parecen ser comunes en entornos de alto riesgo. Un análisis a gran escala del programa de televisión estadounidense The Price Is Right , por ejemplo, proporciona evidencia de una previsión limitada. En cada episodio, los concursantes juegan Showcase Showdown, un juego secuencial de información perfecta para el cual se puede encontrar la estrategia óptima mediante inducción hacia atrás. Las desviaciones frecuentes y sistemáticas del comportamiento óptimo sugieren que una proporción considerable de los concursantes no logran realizar una inducción retrospectiva adecuada y consideran miopemente sólo la siguiente etapa del juego. [20]