La inducción regresiva es el proceso de determinar una secuencia de opciones óptimas razonando desde el punto final de un problema o situación hasta su inicio utilizando eventos o acciones individuales. [1] La inducción regresiva implica examinar el punto final en una serie de decisiones e identificar el proceso o la acción óptima requerida 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. La inducción regresiva 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, se utiliza para resolver la ecuación de Bellman . [3] [4] En los campos relacionados con 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 denomina análisis retrógrado .
En teoría de juegos , se utiliza una variante de la inducción hacia atrás 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 punto del tiempo. Por el contrario, los problemas de teoría de juegos involucran la decisión interactuante de varios jugadores . En esta situación, todavía puede ser posible aplicar una generalización de la inducción hacia atrás, ya que puede ser posible determinar lo que hará el penúltimo jugador al predecir lo que hará el último jugador en cada situación, y así sucesivamente. Esta variante de la inducción hacia atrás se ha utilizado para resolver juegos formales desde el comienzo de la teoría de juegos. John von Neumann y Oskar Morgenstern sugirieron resolver juegos formales de suma cero y dos personas a través de este método en su Teoría de juegos y comportamiento económico (1944), el libro que estableció la teoría de juegos como un campo de estudio. [6] [7]
Consideremos a una persona que evalúa posibles oportunidades de empleo para los próximos diez años, indicados como tiempos . En cada , puede encontrarse con una elección entre dos opciones laborales: un "buen" trabajo que ofrece un salario de o un "mal" trabajo que ofrece un salario de . Cada tipo de trabajo tiene la misma probabilidad de ser ofrecido. Al aceptar un trabajo, el individuo mantendrá ese trabajo en particular durante todo el resto de la duración de diez años.
Este escenario se simplifica suponiendo que la única preocupación del individuo es su ingreso monetario total esperado, sin preferencias variables por 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 del dinero constante.
Si la persona en cuestión debe aceptar un trabajo "malo" se puede decidir razonando hacia atrás desde el tiempo .
Si seguimos trabajando a la inversa, se puede verificar que una oferta "mala" solo debería aceptarse si la persona sigue desempleada en o ; una oferta mala debería rechazarse en cualquier momento hasta inclusive . Generalizando este ejemplo intuitivamente, corresponde al principio de que si uno espera trabajar en un empleo durante mucho tiempo, vale la pena elegir con cuidado.
Un problema de optimización dinámica de este tipo se denomina problema de parada óptima porque la cuestión en cuestión es cuándo dejar de esperar a que aparezca 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 una metodología 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 en forma 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 ponderan los pagos esperados enumerados para este subjuego, y un jugador racional seleccionará la opción con el pago más alto para sí mismo. Se selecciona y marca el vector de pago más alto . Para resolver el equilibrio perfecto en subjuegos, uno debe trabajar continuamente hacia atrás de subjuego a subjuego hasta que se alcance el 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 vectores es el equilibrio perfecto en subjuegos. [9]
La aplicación de la inducción hacia atrás en la teoría de juegos se puede demostrar con un ejemplo sencillo. Consideremos un juego de varias etapas en el que dos jugadores planean ir al cine.
Una vez que ambos observan las opciones, comienza la segunda etapa, en la que los jugadores eligen si ir al cine o quedarse en casa.
En este ejemplo, se suman los pagos en distintas etapas. El juego es un juego de información perfecta . Las matrices de forma normal para estos juegos son:
La forma extensiva de este juego de varias etapas se puede ver a la derecha. Los pasos para resolver este juego con inducción hacia atrás son los siguientes:
La inducción hacia atrás se puede aplicar sólo a clases limitadas de juegos. El procedimiento está bien definido para cualquier juego de información perfecta sin vínculos 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 triviales, pero no es aplicable en general. Es más adecuado para resolver juegos con información perfecta. Si todos los jugadores no están al tanto de las acciones y los pagos de los otros jugadores en cada nodo de decisión, entonces la inducción hacia atrás no se aplica tan fácilmente. [10]
Un segundo ejemplo demuestra que incluso en juegos que formalmente permiten la inducción hacia atrás en teoría, puede que no prediga con precisión el juego empírico en la práctica. Este ejemplo de un juego asimétrico consta de dos jugadores: el jugador 1 propone dividir un dólar con el jugador 2, que luego el jugador 2 acepta o rechaza. Esto se llama el juego del ultimátum . El jugador 1 actúa primero dividiendo el dólar como le parezca mejor. 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, entonces tanto el jugador 1 como el jugador 2 obtienen los pagos que coinciden con esa división. Si el jugador 2 decide rechazar la oferta del jugador 1, entonces ambos jugadores no obtienen nada. En otras palabras, el jugador 2 tiene poder de veto sobre la asignación propuesta por el jugador 1, pero la aplicación del veto elimina cualquier recompensa para ambos jugadores. [11]
Teniendo en cuenta la elección y la respuesta del Jugador 2 ante cualquier propuesta arbitraria del Jugador 1, la racionalidad formal prescribe que el Jugador 2 aceptaría cualquier pago que fuera mayor o igual a $0. En consecuencia, por inducción hacia atrás, el Jugador 1 debería proponer darle al Jugador 2 la menor cantidad posible para obtener 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 por 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 predichos teóricamente en los juegos del ultimátum no coinciden con la observación empírica. La evidencia experimental ha demostrado que un proponente, el Jugador 1, muy rara vez ofrece $0 y el que responde, el Jugador 2, a veces rechaza ofertas mayores a $0. Lo que el Jugador 2 considera aceptable varía según el contexto. La presión o la presencia de otros jugadores y las implicaciones externas pueden significar que el modelo formal del juego no necesariamente puede predecir lo que una persona real elegirá. Según Colin Camerer , un economista conductual estadounidense, el Jugador 2 "rechaza ofertas de menos del 20 por ciento de X aproximadamente la mitad de las veces, aunque termina sin nada". [12]
Aunque la inducción retrógrada suponiendo una 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 tal vez otras anticipaciones de efectos indirectos o externos en lugar de 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 potencial nuevo competidor en esa industria. En la situación actual, la empresa establecida tiene un monopolio sobre la industria y no quiere perder parte de su participación de mercado a manos del nuevo competidor. Si el nuevo competidor decide no entrar, la recompensa para la empresa establecida es alta (mantiene su monopolio) y el nuevo competidor no pierde ni gana (su recompensa es cero). Si el nuevo competidor entra, la empresa establecida puede "luchar" o "acomodarse" al nuevo competidor. Luchará bajando su precio, sacando al nuevo competidor del negocio (e incurriendo en costos de salida, una recompensa negativa) y perjudicando sus propias ganancias. Si se acomoda al nuevo competidor, perderá parte de sus ventas, pero se mantendrá un precio alto y obtendrá mayores ganancias que si bajara su precio (pero menores que las ganancias del monopolio).
Si el incumbente se acomoda en el caso de que el nuevo competidor entre, la mejor respuesta para el nuevo competidor es entrar (y obtener ganancias). Por lo tanto, el perfil de estrategia en el que el nuevo competidor entra y el incumbente se acomoda si el nuevo competidor entra es un equilibrio de Nash consistente con la inducción hacia atrás. Sin embargo, si el incumbente va a luchar, la mejor respuesta para el nuevo competidor es no entrar, y si el nuevo competidor no entra, no importa lo que el incumbente elija hacer en el caso hipotético de que el nuevo competidor entre. Por lo tanto, el perfil de estrategia en el que el incumbente lucha si el nuevo competidor entra, pero el nuevo competidor no entra es también un equilibrio de Nash. Sin embargo, si el nuevo competidor se desvía y entra, la mejor respuesta del incumbente es acomodarse: la amenaza de luchar no es creíble. Por lo tanto, este segundo equilibrio de Nash puede eliminarse mediante la inducción hacia atrás.
Encontrar un equilibrio de Nash en cada proceso de toma de decisiones (subjuego) constituye un equilibrio perfecto en subjuegos. Por lo tanto, estos perfiles de estrategia que representan equilibrios perfectos en subjuegos excluyen la posibilidad de acciones como amenazas increíbles que se utilizan para "asustar" a un nuevo competidor. Si el competidor actual amenaza con iniciar una guerra de precios con un nuevo competidor, está amenazando con reducir sus precios desde un precio de monopolio a un precio ligeramente inferior al del nuevo competidor, lo que sería poco práctico e increíble si el nuevo competidor supiera que una guerra de precios en realidad no sucedería, ya que resultaría en pérdidas para ambas partes. A diferencia de una optimización de un solo agente que podría incluir equilibrios subóptimos o inviables, un equilibrio perfecto en subjuegos tiene en cuenta las acciones de otro jugador, lo que garantiza que ningún jugador alcance un subjuego por error. En este caso, la inducción hacia atrás que produce equilibrios perfectos en subjuegos garantiza que el nuevo competidor no se convencerá de la amenaza del competidor actual sabiendo que no era la mejor respuesta en el perfil de estrategia. [13]
La paradoja del ahorcado inesperado es una paradoja relacionada con la inducción regresiva. El prisionero descrito en la paradoja utiliza la inducción regresiva para llegar a una conclusión falsa. La descripción del problema supone que es posible sorprender a alguien que está realizando la inducción regresiva. La teoría matemática de la inducción regresiva no hace esta suposición, por lo que la paradoja no pone en tela de juicio los resultados de esta teoría.
La inducción hacia atrás funciona solo si ambos jugadores son racionales , es decir, siempre eligen una acción que maximice su recompensa. Sin embargo, la racionalidad no es suficiente: cada jugador también debe 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, ad infinitum. En otras palabras, la racionalidad debe ser de conocimiento común . [14]
La inducción regresiva limitada es una desviación de la inducción regresiva completamente racional. Implica la realización del proceso regular de inducción regresiva 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 la inducción regresiva a través de todos los nodos terminales. [15] La inducción regresiva limitada desempeña un papel mucho más importante en los juegos más largos, ya que los efectos de la inducción regresiva limitada son más potentes en los 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 su lugar, participan en una inducción regresiva limitada. Esta desviación se produce como resultado de la racionalidad limitada , donde los jugadores solo 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 grandes hipótesis para este fenómeno:
Las violaciones de la inducción regresiva 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 destacado que en algunos juegos la presencia de una inducción regresiva limitada puede desempeñar un papel dominante. [17]
En los juegos de bienes públicos repetidos, el comportamiento del equipo se ve afectado por una inducción regresiva limitada, en la que 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 frecuencia con la que se produce el parasitismo en el juego de bienes públicos de un equipo. Al principio, cuando los efectos de la inducción regresiva 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 regresiva limitada en 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 que se alcanzara un número objetivo. Si acertaba el objetivo, ese jugador ganaría un premio; el otro perdería. A mitad de una serie de juegos, se introdujo un pequeño premio. La mayoría de los jugadores realizaron entonces una inducción regresiva limitada, ya que resolvieron el pequeño premio en lugar del premio original. Solo una pequeña fracción de los jugadores consideraron ambos premios al principio. [19]
La mayoría de las pruebas de inducción regresiva se basan en experimentos en los que los participantes reciben incentivos muy limitados para realizar bien la tarea, si es que lo hacen. Sin embargo, las violaciones de la inducción regresiva también parecen ser comunes en entornos de alto riesgo. Un análisis a gran escala del concurso televisivo estadounidense The Price Is Right , por ejemplo, proporciona evidencia de una previsión limitada. En cada episodio, los participantes juegan al Showcase Showdown , un juego secuencial de información perfecta para el cual se puede encontrar la estrategia óptima mediante inducción regresiva. Las desviaciones frecuentes y sistemáticas del comportamiento óptimo sugieren que una proporción considerable de los participantes no logran realizar una inducción regresiva adecuada y consideran miopemente solo la siguiente etapa del juego. [20]
