Inducció cap a arrere

La Inducció cap a arrere és el procés de raonar arrere en el temps, des del final d'un problema o situació, per a determinar una seqüència d'accions òptimes. Es procedix, en primer lloc prenent en conte l'última volta que es va portar a terme una decisió i s'elegix qué fer en eixe moment. En esta informació, es pot llavors determinar lo que deuria fer en la penúltima decisió. Este procés continua arrere fins que s'ha determinat la millor acció per a cada situació possible (és dir, per a cada possible conjunt d'informació) en cada punt en el temps.

En el método matemàtic d'optimisació programació dinàmica, l'inducció arrere és un dels principals métodos per a resoldre l'equació de Bellman. En la teoria de jocs, l'inducció arrere és un método utilisat per a calcular l'equilibri perfecte en subjuegos en els jocs seqüencials. L'única diferència és que l'optimisació implica un sol prenedor de decisions , que elegix lo que deu fer en cada moment del temps, mentres que la teoria de jocs analisa cóm les decisions de varis jugadors interactuen. És dir, per mig de la previsió de lo que l'últim jugador que elegix va a fer en eixa situació, és possible determinar que va a fer el penúltim jugador en elegir, i aixina successivament. En els camps relacionats en la planificació automàtica i la programació automatizado i demostració automàtica de teoremes, el método es diu busca arrere o encadenament cap a arrere . En l'escacs es diu escacs retrospectiu.

L'inducció arrere s'ha utilisat per a resoldre jocs des de que la teoria de jocs ha existit. John von Neumann i Oskar Morgenstern sugerixen la solució d'un joc de suma zero, jocs de dos persones per inducció arrere en el seu llibre Teoria de Jocs i Comportament Econòmic (1944), el llibre que va establir la teoria de jocs com un camp d'estudi. El concepte d'inducció cap a arrere també està relacionat en el Premi Nobel d'Economia Reinhard Selten, un dels creadors del concepte d'equilibri perfecte en subjuegos, la noció d'equilibri de referència per a jocs seqüencials.

Eixemples

Problema de decisió individual

Partim d'un individu desocupat en capacitat per a treballar 10 anys més (T=10). Imaginem que cada any que es troba sense ocupació, pot aplegar-li una bona oferta de treball remunerat en 100 euros, o una mala oferta de treball remunerada en 44 euros, exactament en la mateixa provabilitat (50%). Si decidix acceptar una de les 2 ofertes, permaneixerà en eixe treball durant 10 anys. "¿Deuria este individu acceptar males ofertes de treball?" Podem respondre a esta pregunta a través de la inducció cap a arrere. En l'any 10 (t=10), el valor d'acceptar una bona oferta de treball és de 100 euros, i el d'acceptar una mala oferta de treball és de 44 euros, si rebugem les ofertes rebem 0 euros. Per lo que si l'individu en l'últim periodo seguix sense ocupació deu acceptar qualsevol treball.

En l'any 9 (t=9), el valor d'acceptar una bona oferta de treball és de 200 euros, i el d'acceptar una mala oferta de treball és de 88 euros (44*2). Si rebugem una oferta de treball rebem 0 euros, més el valor d'esperar la pròxima oferta de treball, 100 euros o 44 euros en 50% de provabilitat, valor esperat = 72 euros (0,5*(100+44)). Per lo que, independentment de si l'oferta és bona o mala deu acceptar eixa oferta en lloc d'esperar una atra millor.

En l'any 8 (t=8),el valor d'acceptar una bona oferta de treball és de 300 euros, i el d'acceptar una mala oferta de treball és de 132 euros (44*3). Si rebugem una oferta de treball rebem 0 euros, més el valor esperat d'esperar una oferta de treball en l'any 9. Com sabem que les ofertes en l'any 9 deuen acceptar-se, el valor esperat d'esperar una oferta de treball en l'any 9 serà = 144 euros (0,5*(200+88)). Per lo que, en l'any 8, és preferible esperar una nova oferta de treball que acceptar una mala.

Com a conclusió obtenim que les ofertes males solament es deurien acceptar si no es té ocupació en els anys 9 o 10, rebujant-se fins a l'any 8. Si pensem que anem a ocupar un lloc de treball durant varis anys, deuríem ser exigents en les distintes ofertes.

Inducció cap a arrere en un problema de decisió seqüencial

Eixemple per a entendre l'Equilibri de Nash Perfecte en Subjuegos.

En l'image anterior es mostra un eixemple per a un joc que posseïx un Equilibri de Nash no perfecte i un equilibri perfecte en subjuegos. Les estratègies per al jugador 1 vénen donades per {L,R} mentres que el jugador 2 té l'opció entre {K,O}.

Matriu de pagaments que nos permet trobar els equilibris del joc

Matriu de pagaments que permet identificar un eixemple de ENPS.

Equilibri perfecte en subjuegos {R(U1,K2)} Equilibri de Nash no perfecte {L(U1,U2)} Per a aplicar l'algoritme de inducció cap a arrere, comencem l'anàlisis pels nodos finals (aquelles decisions a on el joc acabaria). Els corresponents al jugador 2. Si 2 tinguera que moure en el nodo esquerre elegiria U1, ya que (3 és major que 1). S i tinguera que moure en el nodo de la dreta elegiria K2 (1 és major que 0). Considerant ara l'únic nodo "penúltim" el del jugador 1, com este jugador sap anticipar lo que farà el jugador 2 racional, 1 elegirà R ( 2 és major que 1).

Tenint llavors 2 equilibris, {R(U1,K2)} Equilibri de Nash Perfecte en Subjuegos i {L(U1,U2)}Equilibri de Nash no Perfecte.

Joc de l'Ultimàtum

Considere el joc de l'ultimàtum , a on un jugador propon dividir certa cantitat de diners en un atre (suponem que abdós jugadors són egoistes). El primer jugador (el proponente) sugerix una divisió entre els dos jugadors. El segon jugador té l'opció d'acceptar la divisió o rebujar-la. Si el segon jugador accepta, abdós obtenen la cantitat sugerida pel proponente. Si és rebujat, cap rep res. Considere les accions del segon jugador donada qualsevol proposta arbitrària del primer jugador (que li dona al segon jugador més de zero). Com l'única opció que té el segon jugador en cada u d'estos punts del joc és elegir entre alguna cosa i res, un pot esperar que el segon accepte. Ya que el segon acceptarà totes les propostes oferides pel primer (que li donen al segon res), el primer deu propondre donar el segon lo menys possible. Est és l'únic equilibri perfecte en subjuegos del joc de l'ultimàtum. (No obstant, el joc de l'ultimàtum té molts uns atres equilibris de Nash que no són perfectes per al subjuego).

Joc del Ciempiés (versió reduïda)

Representa una situació en la que és beneficiós per a abdós jugadors continuar el joc, aun cuando un dels jugadors vullga terminar hui, si sabera que l'atre està dispost a terminar-ho matí. El nostre joc es desenrolla en 3 fases, en les quals els jugadors decidixen Continuar (C) o Terminar (T).

Mini joc del ciempiés

En primer lloc, situem-nos en el final del joc a on el jugador 1 deu elegir entre Continuar en un (pagament =2), o Terminar en (pagament =3). Clarament elegirà Terminar. En segon lloc, el jugador 2( que sap que el jugador 1 és racional) té que decidir entre Terminar en un (pagament=4), o Continuar en (pagament=3). Evidentment elegirà Terminar. I per últim, el jugador 1 deu elegir Terminar en un (pagament=1), o Continuar en un (pagament=0).Elegirà Terminar. Equilibri de Nash (T,T,T)

Els pagaments del nodo final del joc, (3,3) i (2,5), són abdós estrictament millors que la solució d'equilibri (1,1). Pero eixos resultats no es poden alcançar, ya que el jugador 2 no continuarà, per lo que el jugador 1 anticipant-se decidix Terminar el joc.

Aplicacions

Aplicació de l'inducció cap a arrere als jocs de taula

Hi ha jocs com les dames i l'escacs que es caracterisen per ser jocs finitos en informació perfecta. El poder aplicar-los la inducció cap a arrere permet trobar els resultats perfectes en subjuegos, açò té gran rellevància respecte a la busca de bones estratègies de joc. Si enfrontàrem a un jugador qualsevol, contra un ordenador capaç d'aplicar l'algoritme de inducció cap a arrere a jocs tan complexos com l'escacs o les dames, el nostre jugador eixiria sempre perdedor. ya que, l'ordenador sabria que estratègia jugar en cada moment del joc per a alcançar la victòria.

Inducció cap a arrere i entrada econòmica

Considere un joc dinàmic en el qual els jugadors són 2 empreses, una empresa establida en una indústria i una atra en possibilitat d'ingressar en eixa indústria. L'empresa establida té el monopoli de l'indústria i no vol perdre participació en el mercat. Si l'atra empresa decidix no ingressar, l'empresa ya establida rep un pagament elevat (manté el seu monopoli) i la nova ni pert ni gana (el seu pagament és zero). Si la nova empresa decidix ingressar, l'empresa ya establida pugues "barallar" o "acomodar" a la nova. Lluitarà baixant el seu preu, fent que la nova empresa ixca del negoci (i incórrega en costs d'eixida, un benefici negatiu) i danye els seus propis beneficis. Si decidix acomodar, perdrà algunes de les seues vendes, pero mantindrà un preu elevat i rebrà majors guanys que baixant el seu preu (pero menor que els guanys del monopoli). Considere si la millor resposta de l'monopolista és adaptar-se si la nova empresa decidix ingressar. Si el monopoliste s'acomoda, la millor resposta de la nova empresa és ingressar (i obtindre guanys). Per lo tant, el perfil d'estratègies en el que entra la nova i el monopoliste s'acomoda és un equilibri de Nash consistent en la inducció cap a arrere. No obstant, si el monopoliste baralla, la millor resposta de la nova és no ingressar, i si la nova no ingressa, no importa lo que el monopoliste decidixca fer. Per lo tant, el perfil d'estratègies en el que baralla el monopoliste si entra la nova, pero la nova no entra també és un equilibri de Nash. No obstant, si la nova ingressara, la millor resposta de l'monopolista és acomodar-se: l'amenaça d'enfrontaments no és creible. Este segon equilibri de Nash pugues per lo tant ser eliminat per inducció cap a arrere.