Induzione all'indietro - Backward induction

L'induzione a ritroso è il processo di ragionamento a ritroso nel tempo, dalla fine di un problema o di una situazione, per determinare una sequenza di azioni ottimali. Procede esaminando l'ultimo punto in cui deve essere presa una decisione e quindi identificando quale azione sarebbe più ottimale in quel momento. Utilizzando queste informazioni, si può quindi determinare cosa fare nel penultimo momento della decisione. Questo processo continua a ritroso finché non si è determinata l'azione migliore per ogni possibile situazione (cioè per ogni possibile insieme di informazioni ) in ogni momento. L'induzione all'indietro fu usata per la prima volta nel 1875 da Arthur Cayley , che scoprì il metodo mentre cercava di risolvere il famigerato problema del segretario.

Nel metodo di ottimizzazione matematica della programmazione dinamica , l'induzione all'indietro è uno dei metodi principali per risolvere l' equazione di Bellman . Nella teoria dei giochi , l'induzione all'indietro è un metodo utilizzato per calcolare gli equilibri perfetti dei sottogiochi nei giochi sequenziali . L'unica differenza è che l'ottimizzazione coinvolge un solo decisore , che sceglie cosa fare in ogni momento, mentre la teoria dei giochi analizza come interagiscono le decisioni di più giocatori . Cioè, anticipando cosa farà l'ultimo giocatore in ogni situazione, è possibile determinare cosa farà il penultimo giocatore, e così via. Nei campi correlati di pianificazione e schedulazione automatizzata e dimostrazione automatizzata di teoremi , il metodo è chiamato ricerca all'indietro o concatenamento all'indietro . Negli scacchi si chiama analisi retrograda .

L'induzione a ritroso è stata utilizzata per risolvere i giochi finché esiste il campo della teoria dei giochi. John von Neumann e Oskar Morgenstern suggerirono di risolvere giochi a due persone a somma zero per induzione all'indietro nel loro Theory of Games and Economic Behaviour (1944), il libro che ha stabilito la teoria dei giochi come campo di studio.

Induzione a ritroso nel processo decisionale: un problema di arresto ottimale

Si consideri un disoccupato che potrà lavorare per altri dieci anni t = 1,2,...,10. Supponiamo che ogni anno in cui rimangono disoccupati, gli venga offerto un lavoro "buono" che paga $ 100, o un lavoro "cattivo" che paga $ 44, con uguale probabilità (50/50). Una volta accettato un lavoro, rimarranno in quel lavoro per il resto dei dieci anni. (Supponiamo per semplicità che si preoccupino solo dei loro guadagni monetari e che valutino allo stesso modo i guadagni in momenti diversi, cioè il tasso di sconto è uno.)

Questa persona dovrebbe accettare lavori scadenti? Per rispondere a questa domanda, possiamo ragionare a ritroso dal tempo t = 10.

• Al tempo 10, il valore di accettare un buon lavoro è di $100; il valore di accettare un cattivo lavoro è $44; il valore del rifiuto del lavoro disponibile è zero. Pertanto, se sono ancora disoccupati nell'ultimo periodo, dovrebbero accettare qualunque lavoro gli venga offerto in quel momento.
• Al momento 9, il valore di accettare un buon lavoro è $200 (perché quel lavoro durerà per due anni); il valore di accettare un cattivo lavoro è 2*$44 = $88. Il valore del rifiuto di un'offerta di lavoro ora è $ 0, più il valore dell'attesa per la prossima offerta di lavoro, che sarà di $ 44 con il 50% di probabilità o di $ 100 con il 50% di probabilità, per un valore medio ("previsto") di 0,5* ($ 100 + $ 44) = $ 72. Pertanto, indipendentemente dal fatto che il lavoro disponibile al momento 9 sia buono o cattivo, è meglio accettare quell'offerta piuttosto che aspettarne una migliore.
• Al momento 8, il valore dell'accettazione di un buon lavoro è di 300 dollari (durerà per tre anni); il valore di accettare un cattivo lavoro è 3*$44 = $132. Il valore del rifiuto di un'offerta di lavoro ora è $ 0, più il valore dell'attesa di un'offerta di lavoro al momento 9. Poiché abbiamo già concluso che le offerte al momento 9 dovrebbero essere accettate, il valore atteso dell'attesa di un'offerta di lavoro al momento 9 è 0,5*($200+$88) = $144. Pertanto, al momento 8, è più prezioso aspettare la prossima offerta che accettare un cattivo lavoro.

Si può verificare continuando a lavorare a ritroso che le cattive offerte vanno accettate solo se si è ancora disoccupati alle ore 9 o 10; dovrebbero essere rifiutati in ogni momento fino a t = 8. L'intuizione è che se ci si aspetta di lavorare in un lavoro per molto tempo, questo rende più prezioso essere pignoli su quale lavoro accettare.

Un problema di ottimizzazione dinamica di questo tipo è chiamato problema di arresto ottimale , perché il problema è quando smettere di aspettare un'offerta migliore. La teoria della ricerca è il campo della microeconomia che applica problemi di questo tipo a contesti come lo shopping, la ricerca di lavoro e il matrimonio.

Induzione a ritroso nella teoria dei giochi

Nella teoria dei giochi, l'induzione all'indietro è un concetto di soluzione. È un affinamento del concetto di razionalità che sono sensibili agli insiemi di informazioni individuali nella rappresentazione in forma estensiva di un gioco. L'idea di induzione all'indietro utilizza la razionalità sequenziale identificando un'azione ottimale per ogni informazione in un dato albero di gioco .

In “Strategy: An Introduction to Game Theory” di Joel Watson, la procedura di Backward induction è definita come: “Il processo di analisi di un gioco dalla fine all'inizio. Ad ogni nodo decisionale, si prendono in considerazione le azioni che sono dominate, dati i nodi terminali che possono essere raggiunti attraverso il gioco delle azioni individuate nei nodi successori.”.

Uno svantaggio della procedura di induzione all'indietro è che può essere applicata solo a classi limitate di giochi. La procedura è ben definita per qualsiasi gioco di informazione perfetta senza vincoli di utilità. È anche ben definito e significativo per il gioco dell'informazione perfetta con i legami. Tuttavia, porta a più di un profilo strategico. La procedura può essere applicata ad alcuni giochi con set di informazioni non banali ma in generale non è affidabile. La procedura è più adatta per risolvere giochi con informazioni perfette. Pertanto, se tutti i giocatori non sono consapevoli delle azioni e dei guadagni degli altri giocatori in ogni nodo decisionale, l'induzione all'indietro non è così facile da applicare. (Watson pag.188)

La procedura di induzione all'indietro può essere dimostrata con un semplice esempio.

Induzione a ritroso nella teoria dei giochi: gioco a più stadi

Il gioco proposto è un gioco a più fasi che coinvolge 2 giocatori. I giocatori stanno pianificando di andare al cinema. Attualmente, ci sono 2 film molto popolari, Joker e Terminator. Il giocatore 1 vuole guardare Terminator e il giocatore 2 vuole guardare Joker. Il giocatore 1 acquisterà prima un biglietto e comunicherà al giocatore 2 la sua scelta. Quindi, il giocatore 2 acquisterà il suo biglietto. Una volta che entrambi avranno osservato le scelte, decideranno se andare al cinema o restare a casa. Proprio come nella prima fase, il giocatore 1 sceglie per primo. Il giocatore 2 fa quindi la sua scelta dopo aver osservato la scelta del giocatore 1.

Per questo esempio, supponiamo che i payoff vengano aggiunti in diverse fasi. Il gioco è un perfetto gioco di informazioni.

Matrice in forma normale :

Fase 1

Giocatore 2 Giocatore 1	Burlone	Terminatore
Burlone	3, 5	0, 0
Terminatore	1, 1	5, 3

Fase 2

Giocatore 2 Giocatore 1	Vai al film	Stare a casa
Vai al film	6, 6	4, -2
Stare a casa	-2, 4	-2, -2

Rappresentazione in forma estesa :

Passaggi per risolvere questo gioco a più fasi, con il modulo esteso come mostrato a destra:

1. L'induzione a ritroso inizia a risolvere il gioco dai nodi finali.
2. Il giocatore 2 osserverà 8 sottogiochi dai nodi finali per scegliere "Vai al film" o "Resta a casa"
   1. Il giocatore 2 effettuerà 4 confronti in totale. Sceglierà un'opzione con il payoff più alto.
   2. Ad esempio, considerando il primo sottogioco, il payoff di 11 è superiore a 7. Pertanto, il giocatore 2 sceglie "Vai al film".
   3. Il metodo continua per ogni sottogioco.
3. Una volta che il giocatore 2 ha completato le sue scelte, il giocatore 1 farà la sua scelta in base ai sottogiochi selezionati.
   1. Il processo è simile al passaggio 2. Il giocatore 1 confronta i suoi guadagni per fare le sue scelte.
   2. I sottogiochi non selezionati dal giocatore 2 nel passaggio precedente non vengono più considerati da entrambi i giocatori perché non ottimali.
   3. Ad esempio, la scelta di "Vai al film" offre un payoff di 9 (9,11) e la scelta di "Resta a casa" offre un payoff di 1 (1, 9). Il giocatore 1 sceglierà "Vai al film".
4. Il processo si ripete per ogni giocatore fino al raggiungimento del nodo iniziale.
   1. Ad esempio, il giocatore 2 sceglierà "Joker" perché il payoff di 11 (9, 11) è maggiore di "Terminator" con il payoff di 6 (6, 6).
   2. Ad esempio, il giocatore 1, al nodo iniziale, selezionerà "Terminator" perché offre un payoff maggiore di 11. Terminator: (11, 9) > Joker: (9, 11)
5. Per identificare l' equilibrio perfetto del sottogioco , dobbiamo identificare un percorso che seleziona il sottogioco ottimale in corrispondenza di ogni insieme di informazioni.
   1. In questo esempio, il giocatore 1 sceglie "Terminator" e anche il giocatore 2 sceglie "Terminator". Quindi, entrambi scelgono di "Vai al film".
   2. L'equilibrio perfetto del sottogioco porta al payoff di (11,9)

Induzione a ritroso nella teoria dei giochi: il gioco dell'ultimatum

L'induzione a ritroso è "il processo di analisi di un gioco dalla fine all'inizio". Come per la risoluzione di altri equilibri di Nash , si presume la razionalità dei giocatori e la conoscenza completa. Il concetto di induzione all'indietro corrisponde a questo presupposto che è risaputo che ogni giocatore agirà razionalmente con ciascun nodo decisionale quando sceglie un'opzione, anche se la sua razionalità implica che tale nodo non sarà raggiunto.' Sotto l'assunzione reciproca della razionalità, quindi, l'induzione all'indietro consente a ciascun giocatore di prevedere esattamente cosa farà il suo avversario in ogni fase del gioco.

Per risolvere un Sottogioco Perfetto Equilibrio con induzione all'indietro, il gioco dovrebbe essere scritto in forma estesa e poi diviso in sottogiochi . A partire dal sottogioco più lontano dal nodo iniziale, o punto di partenza, vengono pesati i payoff previsti elencati per questo sottogioco e il giocatore razionale selezionerà per sé l'opzione con il payoff più alto. Viene selezionato e contrassegnato il vettore di payoff più elevato. Risolvi per il perfetto equilibrio del sottogioco lavorando continuamente a ritroso da un sottogioco all'altro fino ad arrivare al punto di partenza. Con l'avanzare di questo processo, il tuo gioco di forma estensiva iniziale diventerà sempre più breve. Il percorso segnato dei vettori è l'equilibrio perfetto del sottogioco.

Induzione all'indietro applicata al gioco Ultimatum

Pensa a un gioco tra due giocatori in cui il giocatore 1 propone di dividere un dollaro con il giocatore 2. Questo è un famoso gioco asimmetrico che viene giocato in sequenza chiamato gioco dell'ultimatum . il giocatore uno agisce per primo dividendo il dollaro come meglio crede. Ora, il giocatore due può accettare la parte che gli è stata data dal giocatore uno o rifiutare la divisione. Se il giocatore 2 accetta la divisione, sia il giocatore 1 che il giocatore 2 ottengono il pagamento in base a quella divisione. Se il giocatore 2 decide di rifiutare l'offerta del giocatore 1, entrambi i giocatori non ottengono nulla. In altre parole, il giocatore 2 ha potere di veto sull'allocazione proposta del giocatore 1, ma l'applicazione del veto elimina qualsiasi ricompensa per entrambi i giocatori. Il profilo di strategia per questo gioco quindi può essere scritto come coppie (x, f(x)) per tutti gli x compresi tra 0 e 1, dove f(x)) è una funzione a due valori che esprime se x è accettato o meno.

Considera la scelta e la risposta del giocatore 2 a qualsiasi proposta arbitraria del giocatore 1, supponendo che l'offerta sia maggiore di $ 0. Usando l'induzione all'indietro, sicuramente ci aspetteremmo che il giocatore 2 accetti qualsiasi vincita maggiore o uguale a $ 0. Di conseguenza, il giocatore 1 dovrebbe proporre di dare al giocatore 2 il meno possibile per ottenere la maggior parte della divisione. giocatore 1 dare al giocatore 2 la più piccola unità di denaro e tenere il resto per sé è l'unico sottogioco perfetto equilibrio. Il gioco dell'ultimatum ha molti altri equilibri di Nash che non sono perfetti per i sottogiochi e quindi non richiedono l'induzione all'indietro.

Il gioco dell'ultimatum è un'illustrazione dell'utilità dell'induzione all'indietro quando si considerano giochi infiniti; tuttavia, i risultati teoricamente previsti del gioco del gioco sono criticati. L'evidenza empirica e sperimentale ha dimostrato che il proponente offre molto raramente $ 0 e il giocatore 2 a volte rifiuta anche offerte superiori a $ 0, presumibilmente per motivi di equità. Ciò che è ritenuto giusto dal giocatore 2 varia in base al contesto e la pressione o la presenza di altri giocatori può significare che il modello teorico del gioco non può necessariamente prevedere ciò che le persone reali sceglieranno.

In pratica, l'equilibrio perfetto del sottogioco non è sempre raggiunto. Secondo Camerer, un economista comportamentale americano, il giocatore 2 "rifiuta offerte inferiori al 20 percento di X circa la metà delle volte, anche se alla fine non ottengono nulla". Sebbene l'induzione a ritroso preveda che il rispondente accetti qualsiasi offerta uguale o maggiore di zero, i rispondenti in realtà non sono giocatori razionali e quindi sembrano preoccuparsi più dell'"equità" dell'offerta piuttosto che dei potenziali guadagni monetari.

Vedi anche il gioco del millepiedi .

Induzione a ritroso in economia: il problema della decisione di ingresso

Considera un gioco dinamico in cui i giocatori sono un'impresa storica in un settore e un potenziale concorrente in quel settore. Allo stato attuale, l'operatore storico ha il monopolio del settore e non vuole perdere parte della sua quota di mercato a favore del nuovo operatore. Se il concorrente sceglie di non partecipare, il guadagno per l'operatore storico è elevato (mantiene il suo monopolio) e il concorrente non perde né guadagna (il suo profitto è zero). Se il concorrente entra, l'operatore storico può "combattere" o "accomodare" il concorrente. Combatterà abbassando il suo prezzo, facendo chiudere l'impresa (e incorrendo in costi di uscita - un profitto negativo) e danneggiando i propri profitti. Se accoglie il concorrente perderà parte delle sue vendite, ma verrà mantenuto un prezzo elevato e riceverà maggiori profitti rispetto alla riduzione del prezzo (ma inferiore ai profitti del monopolio).

Considera se la migliore risposta dell'operatore storico è quella di accogliere se il concorrente entra. Se l'operatore storico si accomoda, la migliore risposta del concorrente è entrare (e ottenere profitto). Quindi il profilo della strategia in cui il concorrente entra e l'operatore storico si accomoda se il concorrente entra è un equilibrio di Nash coerente con l'induzione all'indietro. Tuttavia, se l'operatore storico sta per combattere, la migliore risposta del concorrente è di non entrare, e se il concorrente non entra, non importa ciò che l'operatore storico sceglie di fare nell'ipotetico caso in cui il concorrente entra. Quindi il profilo della strategia in cui l'operatore storico combatte se il concorrente entra, ma il concorrente non entra è anch'esso un equilibrio di Nash. Tuttavia, se il concorrente dovesse deviare ed entrare, la migliore risposta dell'operatore storico è quella di adattarsi: la minaccia di combattere non è credibile. Questo secondo equilibrio di Nash può quindi essere eliminato per induzione all'indietro.

Trovare un equilibrio di Nash in ogni processo decisionale (sottogioco) costituisce un perfetto equilibrio di sottogioco. Pertanto, questi profili di strategia che descrivono equilibri perfetti di sottogioco escludono la possibilità di azioni come minacce incredibili che vengono utilizzate per "spaventare" un concorrente. Se l'operatore storico minaccia di avviare una guerra dei prezzi Guerra dei prezzi con un concorrente, minaccia di abbassare i prezzi da un prezzo di monopolio a leggermente inferiore a quello del concorrente, il che sarebbe poco pratico e incredibile, se il concorrente sapesse che una guerra dei prezzi non sarebbe effettivamente accadere poiché comporterebbe perdite per entrambe le parti. A differenza di un'ottimizzazione ad agente singolo che include equilibri non fattibili o ottimali, un equilibrio perfetto di sottogioco tiene conto delle azioni di un altro giocatore, assicurando così che nessun giocatore raggiunga un sottogioco per errore. In questo caso, l'induzione all'indietro che produce equilibri di sottogioco perfetti assicura che il concorrente non sarà convinto della minaccia dell'operatore storico sapendo che non era una risposta migliore nel profilo della strategia.

Paradosso dell'induzione all'indietro: l'impiccagione inaspettata

L' inaspettato paradosso dell'impiccagione è un paradosso legato all'induzione all'indietro. Supponiamo che a un prigioniero venga detto che verrà impiccata tra il lunedì e il venerdì della prossima settimana. Tuttavia, il giorno esatto sarà una sorpresa (cioè non saprà la sera prima che verrà giustiziata il giorno successivo). Il prigioniero, interessato a superare in astuzia il suo carnefice, tenta di determinare in quale giorno avverrà l'esecuzione.

Ragiona che non può avvenire venerdì, poiché se non fosse avvenuto entro la fine di giovedì, saprebbe che l'esecuzione sarebbe avvenuta venerdì. Pertanto, può eliminare il venerdì come possibilità. Eliminato il venerdì, decide che non può avvenire giovedì, poiché se non fosse accaduto mercoledì, saprebbe che doveva essere giovedì. Pertanto, può eliminare giovedì. Questo ragionamento procede finché non ha eliminato tutte le possibilità. Conclude che non sarà impiccata la prossima settimana.

Con sua sorpresa, mercoledì viene impiccata. Ha commesso l'errore di presumere di sapere definitivamente se il fattore futuro sconosciuto che avrebbe causato la sua esecuzione fosse uno su cui potesse ragionare.

Qui il prigioniero ragiona per induzione a ritroso, ma sembra giungere a una falsa conclusione. Si noti, tuttavia, che la descrizione del problema presuppone che sia possibile sorprendere qualcuno che sta eseguendo l'induzione all'indietro. La teoria matematica dell'induzione a ritroso non fa questa ipotesi, quindi il paradosso non mette in discussione i risultati di questa teoria. Tuttavia, questo paradosso ha ricevuto alcune discussioni sostanziali da parte dei filosofi.

Induzione a ritroso e conoscenza comune della razionalità

L'induzione all'indietro funziona solo se entrambi i giocatori sono razionali , cioè selezionano sempre un'azione che massimizza il loro profitto. Tuttavia, la razionalità non basta: ogni giocatore dovrebbe anche credere che tutti gli altri giocatori siano razionali. Anche questo non basta: ogni giocatore dovrebbe credere che tutti gli altri giocatori sappiano che tutti gli altri giocatori sono razionali. E così via all'infinito. In altre parole, la razionalità dovrebbe essere conoscenza comune .

Induzione all'indietro limitata

L'induzione all'indietro limitata è una deviazione dall'induzione all'indietro completamente razionale. Si tratta di mettere in atto il regolare processo di induzione all'indietro senza una perfetta previsione. In teoria, ciò si verifica quando uno o più giocatori hanno una previsione limitata e non possono eseguire l'induzione all'indietro attraverso tutti i nodi terminali. L'induzione all'indietro limitata gioca un ruolo molto più importante nei giochi più lunghi poiché gli effetti dell'induzione all'indietro limitata sono più potenti nei periodi successivi dei giochi.

Gli esperimenti hanno dimostrato che nei giochi di contrattazione sequenziale, come il gioco del millepiedi , i soggetti si discostano dalle previsioni teoriche e si impegnano invece in un'induzione all'indietro limitata. Questa deviazione si verifica a causa della razionalità limitata , in cui i giocatori possono vedere perfettamente solo alcune fasi avanti. Ciò consente l'imprevedibilità nelle decisioni e l'inefficienza nella ricerca e nel raggiungimento di equilibri di Nash perfetti nei sottogiochi .

Ci sono tre grandi ipotesi per questo fenomeno;

1. La presenza di fattori sociali (es. equità)
2. La presenza di fattori non sociali (es. limitata induzione a ritroso)
3. Differenza culturale

Le violazioni dell'induzione all'indietro sono principalmente attribuite alla presenza di fattori sociali. Tuttavia, le previsioni dei modelli basati sui dati per i giochi di contrattazione sequenziali (utilizzando il modello della gerarchia cognitiva ) hanno evidenziato che in alcuni giochi la presenza di una limitata induzione all'indietro può svolgere un ruolo dominante.

All'interno di ripetuti giochi di beni pubblici, il comportamento della squadra è influenzato da una limitata induzione all'indietro; dove è evidente che i contributi iniziali dei membri del team sono superiori ai contributi verso la fine. L'induzione all'indietro limitata influenza anche il modo in cui si verifica regolarmente il free-riding all'interno del gioco dei beni pubblici di una squadra. All'inizio, quando gli effetti della limitata induzione all'indietro sono bassi, il free riding è meno frequente, mentre verso la fine, quando gli effetti sono alti, il free riding diventa più frequente.

Anche l'induzione all'indietro limitata è stata testata all'interno di una variante del gioco di corse. Nel gioco, i giocatori sceglierebbero in sequenza numeri interi all'interno di un intervallo e sommerebbero le loro scelte fino a raggiungere un numero target. Colpire il bersaglio fa guadagnare a quel giocatore un premio; l'altro perde. Durante una serie di giochi, è stato introdotto un piccolo premio. La maggior parte dei giocatori ha quindi eseguito un'induzione all'indietro limitata, poiché ha risolto per il piccolo premio piuttosto che per il premio originale. Solo una piccola parte dei giocatori ha considerato entrambi i premi all'inizio.

Appunti