Teoria dei giochi e calcoli strategici: dalla guerra ... · PDF fileTeoria dei giochi e...

Teoria dei giochi e calcoli strategici:dalla guerra fredda alle aste on-line

Vincenzo BonifaciIstituto di Analisi dei Sistemi ed InformaticaConsiglio Nazionale delle Ricerche, Roma

martedì 6 maggio 2014

Cos’è la “Teoria dei Giochi”?

• Teoria delle decisioni interattive

• Più entità - giocatori - che si ritrovano a competere, cooperare, coordinarsi...

• Ciascun giocatore può intraprendere azioni, o mosse

• Le azioni determinano l’esito del gioco

Esempio: la morra cinese

• 2 giocatori

• ogni giocatore ha 3 azioni: Sasso, Forbice, Carta

• esiti possibili:vittoria (+1), pareggio (0), sconfitta (-1)

• +1, 0, -1 : profitto

S 0 0 +1 -1 -1 +1

F -1 +1 0 0 +1 -1

C +1 -1 -1 +1 0 0

Esempi di “giochi”

• Giochi veri e propri:

• tris, scacchi...

• Politica estera

• Mercati finanziari

• Interazioni in Internet e nel Web

• ...

• Politica estera

• ...

Teoria deigiochi

• Politica estera

• ...

Teoria deigiochi

Scienzapolitica

• Politica estera

• ...

Teoria deigiochi

Scienzapolitica

• Politica estera

• ...

Teoria deigiochi

EconomiaScienzapolitica

• Politica estera

• ...

Teoria deigiochi

EconomiaScienzapolitica

• Politica estera

• ...

Teoria deigiochi

Economia

Informatica

Scienzapolitica

• Politica estera

• ...

Teoria deigiochi

Economia

Informatica

Scienzapolitica

Cosa significa analizzare un gioco?

• Identificazione dei punti di equilibrio...

• scelta di azioni “stabili”, che si confermano a vicenda

• ...e dei punti di non equilibrio

• scelta irrazionale da parte di almeno un giocatore

• Non si cerca di spiegare perché le preferenze dei giocatori sono quelle che sono; ma di capire cosa ne consegue

“La ragione è schiava delle passioni” (D. Hume)

Il gioco del “coniglio”

Film: Gioventù bruciata (1955)martedì 6 maggio 2014

• 2 giocatori

• azioni: sterzare (S)o andare dritti (D)

S 0 0 -1 1

D 1 -1 -100 -100

• 2 giocatori

S 0 0 -1 1

D 1 -1 -100 -100

• 2 giocatori

S 0 0 -1 1

D 1 -1 -100 -100

• 2 giocatori

S 0 0 -1 1

D 1 -1 -100 -100

• 2 giocatori

S 0 0 -1 1

D 1 -1 -100 -100

• 2 giocatori

S 0 0 -1 1

D 1 -1 -100 -100

• 2 giocatori

S 0 0 -1 1

D 1 -1 -100 -100

Equilibri

S 0 0 +1 -1 -1 +1

F -1 +1 0 0 +1 -1

C +1 -1 -1 +1 0 0

Equilibri

• Esiste sempre almeno un punto di equilibrio?

S 0 0 +1 -1 -1 +1

F -1 +1 0 0 +1 -1

C +1 -1 -1 +1 0 0

Equilibri

• Morra cinese: no?

S 0 0 +1 -1 -1 +1

F -1 +1 0 0 +1 -1

C +1 -1 -1 +1 0 0

Equilibri

S 0 0 +1 -1 -1 +1

F -1 +1 0 0 +1 -1

C +1 -1 -1 +1 0 0

Equilibri

S 0 0 +1 -1 -1 +1

F -1 +1 0 0 +1 -1

C +1 -1 -1 +1 0 0

Equilibri

S 0 0 +1 -1 -1 +1

F -1 +1 0 0 +1 -1

C +1 -1 -1 +1 0 0

Equilibri

S 0 0 +1 -1 -1 +1

F -1 +1 0 0 +1 -1

C +1 -1 -1 +1 0 0

Equilibri

S 0 0 +1 -1 -1 +1

F -1 +1 0 0 +1 -1

C +1 -1 -1 +1 0 0

Equilibri

S 0 0 +1 -1 -1 +1

F -1 +1 0 0 +1 -1

C +1 -1 -1 +1 0 0

Equilibri

• Idea: permettere strategiemiste (aleatorie)

• Esempio:

• Sasso 33,3...%

• Forbici 33,3...%

• Carta 33,3...%

S 0 0 +1 -1 -1 +1

F -1 +1 0 0 +1 -1

C +1 -1 -1 +1 0 0

Giochi di pura competizione

• Giochi a somma zero:la somma dei profitti dei giocatori è la stessa in tutti gli esiti del gioco

• Esempi:

• Morra cinese

• Spartizione di una torta tra 2 persone

• Una persona divide, l’altra sceglie

Un contributo fondamentale

• John von Neumann (1903–1957)

• Uno dei padri del calcolatore...

• ...e della teoria dei giochi

• Ha dimostrato che ogni gioco a somma zero ammette un equilibrio (nel 1928 per 2 giocatori; nel 1944 per più giocatori)

• ...e della teoria dei giochi

• Ha dimostrato che ogni gioco a somma zero ammette un equilibrio (nel 1928 per 2 giocatori; nel 1944 per più giocatori)

• Fautore della deterrenza nucleare:fu presidente del comitato USA per i missili balistici intercontinentali

Giochi pericolosi: la guerra fredda

• Teoria della deterrenzanucleare

• Ordigno “fine di mondo”

Film: Il dottor Stranamore (1964)martedì 6 maggio 2014

1962: La crisi dei missili di Cuba

• Presidente USA - John F. KennedyPremier URSS - Nikita Krusciov

• Missili nucleari USA in Turchia e Italia

• Missili nucleari URSS a Cuba

• Embargo e crisi diplomatica

• 2 giocatori USA, URSS

• azioni:smantellare i missili(S) o mantenerli (M)

• analogo al giocodel “coniglio”!

S 0 0 -1 1

M 1 -1 -100 -100

S 0 0 -1 1

M 1 -1 -100 -100

S 0 0 -1 1

M 1 -1 -100 -100

S 0 0 -1 1

M 1 -1 -100 -100

S 0 0 -1 1

M 1 -1 -100 -100

S 0 0 -1 1

M 1 -1 -100 -100

Il dilemma del prigionieroM. Flood, M. Drescher, A. Tucker (1950)

Il dilemma del prigioniero

• Classico esempio di gioco non a somma zero

M. Flood, M. Drescher, A. Tucker (1950)

• 2 colpevoli, interrogati separatamente dalla polizia

• Collaborare con la polizia (facendo il nome del proprio complice), o mantenere il silenzio?

• collaborare comporta uno sconto di pena

• se entrambi collaborano, la pena sarà maggiore

• se non si collabora ma si viene “traditi”, la pena sarà massima

Il dilemma del prigioniero: analisi

• 2 giocatori

• azioni: non confessare (N),confessare (C)

N -1 -1 -10 0

C 0 -10 -5 -5

• 2 giocatori

N -1 -1 -10 0

C 0 -10 -5 -5

• 2 giocatori

N -1 -1 -10 0

C 0 -10 -5 -5

• 2 giocatori

N -1 -1 -10 0

C 0 -10 -5 -5

• 2 giocatori

N -1 -1 -10 0

C 0 -10 -5 -5

• 2 giocatori

N -1 -1 -10 0

C 0 -10 -5 -5

A Beautiful Mind

• Un equilibrio esiste sempre anche per i giochi non a somma zero?

• John Nash (1928–)

• 1949: dimostra il suo famoso teorema: ogni gioco (finito) ammette un equilibrio

• 1961-1970: ricovero su diagnosi di schizofrenia

• 1994: premio Nobel per l’economia

• 2002: esce il film A Beautiful Mind

Teoremi del punto fisso

• Il Teorema di Nash si basa a sua volta sul Teorema di Brouwer (1910)

Ogni funzione continua F da un disco chiuso a se stesso ammette un punto fisso

• Un punto fisso è un vettore x tale che F(x) = x

• Esempio: Mescolare il caffé

• x = posizione di una particella di caffé prima del mescolamento

• F(x) = posizione dopo il mescolamento

Calcolo degli equilibri

• Purtroppo il teorema di Nash – come quello di Brouwer – è essenzialmente non costruttivo

• Assicura l’esistenza di un equilibrio, ma non aiuta a determinarlo “algoritmicamente”

• L’area del calcolo degli equilibri è oggetto di attiva ricerca in informatica teorica

Il progetto dei “meccanismi” di gioco

• Analisi di un gioco:

• Gioco ! analisi ! esiti previsti

• Progetto di meccanismi:

• Esiti desiderati ! sintesi ! gioco

• Obiettivi:

• Semplicità delle strategie di equilibrio

• Efficienza nell’allocazione delle risorse

• Equità

• Profitti (per l’autorità che “legifera” il gioco)

• Come aggiudicare un oggetto in vendita tramite un’asta per corrispondenza?

• Asta “del primo prezzo”:

• offerte in busta chiusa

• la più alta vince e paga quanto offerto

• Asta “del secondo prezzo” (asta di Vickrey):

• offerte in busta chiusa

• la più alta vince, ma paga quanto offerto dalla seconda offerta più alta

• In uso dal 500 A.C. e dal 1893 D.C., rispettivamente

L’asta del secondo prezzo

• Valutazione G1 = 10 !Valutazione G2 = 20 !

• Se parità, assegna a G1

• Profitto =valutazione - prezzo

• L’asta del secondo prezzo induce comportamenti efficienti e prevedibili

!"10 !"20

!"10 0 0 0 10

!"20 0 0 0 0

!"10 !"20

!"10 0 0 0 10

!"20 0 0 0 0

!"10 !"20

!"10 0 0 0 10

!"20 0 0 0 0

!"10 !"20

!"10 0 0 0 10

!"20 0 0 0 0

!"10 !"20

!"10 0 0 0 10

!"20 0 0 0 0

!"10 !"20

!"10 0 0 0 10

!"20 0 0 0 0

!"10 !"20

!"10 0 0 0 10

!"20 0 0 0 0

Applicazioni delle aste

• eBay: aste on-line per compravendita di oggetti

• Offerte per delega da parte del software (rialzi automatici fino al limite prefissato)

• fatturato: 16 miliardi di $ (nel 2013)

• Google: aste on-line per compravendita di inserzioni pubblicitarie

• fatturato: 42 miliardi di $ (nel 2012)

• Aste statali per l’assegnazione delle frequenze di trasmissione

Conclusioni

• Collegamenti con molte discipline: in particolare, con l’algoritmica e con l’analisi matematica

• Numerosi scenari applicativi

• Molti problemi aperti

• Come calcolare gli equilibri?

• Come progettare meccanismi per indurre comportamenti virtuosi?

Per approfondire

• Laszlo MeroCalcoli morali. Teoria dei giochi, logica e fragilità umanaEdizioni Dedalo, 2000

Teoria dei giochi e calcoli strategici: dalla guerra ... · PDF fileTeoria dei giochi e...

Documents

Transcript of Teoria dei giochi e calcoli strategici: dalla guerra ... · PDF fileTeoria dei giochi e...