delete

Contattaci

back to resources

Teoria dei Giochi

data
16/4/2021
data progetto
autore
simone
cliente
partnership
url
No items found.

Introduzione alla teoria dei giochi: equilibri di Nash ed equilibri multipli

La teoria dei giochi è quella scienza matematica sviluppata al fine di capire quale sia la strategia migliore che un soggetto possa attuare in situazioni che mutano non solo al variare delle sue decisioni ma anche di quelle dei soggetti a esso connessi. Tale teoria, com’è facilmente intuibile, viene applicata a molti ambiti, per esempio quelli in cui ci si prefigge di studiare un piano di marketing o una politica proficua.

Un esempio che consigliamo si può trovare al seguente link: 

https://www.youtube.com/watch?v=jILgxeNBK_8

Definiamo gioco una qualsiasi situazione in cui:

  • Esiste un insieme di partecipati che chiameremo giocatori;
  • Ogni giocatore ha a disposizione una serie di possibili opzioni di comportamento che chiameremo strategie;
  • Per ogni scelta di strategie ogni giocatore riceve un guadagno, detto anche payoff, generalmente rappresentato da un numero.

Ogni giocatore in generale cercherà di massimizzare il suo profitto ma non è detto che il suo unico interesse sia questo, infatti, potrebbe anche cercare si massimizzare il tornaconto di altri giocatori e, in tal caso, il concetto di guadagno andrà rivisto affinché esso descriva con completezza il grado di soddisfazione del soggetto. 

Nella teoria dei giochi è fondamentale il concetto dell’equilibrio di Nash sviluppato da John F. Nash, economista e matematico statunitense, i cui studi all’interno di questo ambito hanno portato allo sviluppo di quello che viene chiamato, il “dilemma del prigioniero”. Di seguito vediamo una sua rappresentazione schematica.

How to win at game theory | New Scientist

Rimandiamo al seguente video per una spiegazione più estesa di questo Dilemma:

https://www.youtube.com/watch?v=NdITTDl5coE

Ora introduciamo qualche nuova definizione.

Una scelta di strategie, una per ogni giocatore, è socialmente ottimale se massimizza la somma dei guadagni di tutti i giocatori, mentre è Pareto-ottimale se non esiste un’altra combinazione di mosse tale che migliori i payoff di almeno un giocatore senza diminuire quello degli altri. Non lo dimostreremo qua per motivi di brevità ma se una soluzione è socialmente ottimale allora è anche Pareto-ottimale

Supporremo che ogni giocatore conosca integralmente la struttura del gioco (cioè che il gioco sia completo) e quindi che sia a conoscenza di tutte le possibili strategie e guadagni di ogni partecipante. Inoltre, assumeremo che ogni partecipante sia intelligente (cioè in grado di capire, senza commettere errori, dato un insieme di strategie possibili quale sia la più conveniente) e razionale (cioè tale che, una volta riconosciuta la/le strategia/e a massimo profitto la/le preferisca alle altre [14]).

Modelli in cui tali assunzioni non vengono fatte possono divenire estremamente complicati e non li approfondiremo nel corso di questa trattazione. 

Si consideri il seguente esempio tratto dal sesto capitolo di [2].

Esempio degli studenti

Helpful Study Partner | Funny dog memes, Dog quotes funny, Funny animals

Uno studente deve affrontare un esame e una presentazione per il giorno seguente ma non può prepararsi adeguatamente per entrambe. Per semplicità supponiamo che egli sia in grado stimare con ottima precisione quale sarà il voto ottenuto (calcolato in centesimi) da entrambe le prove al variare della sua preparazione. 

In particolare, per quel che riguarda l’esame lo studente si aspetta una votazione pari a 92 se studia e di 80 altrimenti. La presentazione, invece, deve essere fatta con un compagno e nel caso in cui entrambi lavorino su di essa la votazione relativa sarà di 100, se solo uno dei due (indipendentemente da chi) ci lavorasse di 92 e se non lo facesse nessuno di 84. Anche il compagno deve scegliere se studiare per l’esame o concentrarsi sulla preparazione e le sue previsioni sui voti sono le stesse.

Si presuma infine che i due compagni non possano comunicare e quindi mettersi d’accordo sul da farsi. L’obiettivo per entrambi è quello di massimizzare il valore medio delle due votazioni che poi andrà a costituire il voto definitivo. Schematizziamo di seguito i possibili risultati:

  • Se entrambi preparassero la presentazione prenderebbero 100 in essa e 80 nell’esame ottenendo quindi una votazione finale di 90;
  • Se entrambi studiassero per l’esame prenderebbero 92 in esso e 84 nella presentazione per una media di 88;
  • Se uno studiasse per l’esame e l’altro preparasse la presentazione avremmo che quest’ultimo prenderebbe 92 in essa ma 80 nell’esame arrivando a una media di 86, mentre l’altro prenderebbe anch’esso 92 per la presentazione (poiché ci avrebbe lavorato l’altro) e 92 all’esame ottenendo una media di 92.

Cos’è meglio fare quindi? Possiamo ragionare in questo modo:

  1. Se si sapesse che il compagno studierà per l’esame, lo studente dovrebbe scegliere di fare lo stesso in quanto ciò gli permetterebbe di ottenere una votazione media di 88, mentre focalizzarsi sulla presentazione di 86;
  2. Se si sapesse che il compagno preparerà la presentazione, lo studente dovrebbe scegliere di studiare perché così otterrebbe una media finale di 92 mentre in caso contrario di 90.

Possiamo dunque concludere che la miglior cosa da fare sarebbe, in ogni caso, studiare per l’esame.

What advice do you have for someone studying for the bar exam?

Quando, come nell’esempio presentato, un giocatore ha una strategia strettamente più conveniente delle altre, indipendentemente dal comportamento degli altri giocatori, chiameremo tale scelta strategia strettamente dominante e, supponendo la razionalità del soggetto, daremo per scontato che la adotti. 

Nell’esempio precedente, per la stessa natura del problema, ci aspettiamo un comportamento simmetrico da parte dei due giocatori che dunque sceglieranno entrambi di studiare ottenendo la votazione complessiva di 88.

È interessante però notare che se gli studenti avessero potuto accordarsi sul preparare entrambi la presentazione il risultato finale non sarebbe variato, infatti, in tal caso, lo studente si sarebbe aspettato un voto medio di 90 e dunque avrebbe deciso di studiare per l’esame sapendo che l’altro avrebbe preparato la presentazione, infatti ciò gli permetterebbe di raggiungere il 92. 

In realtà, tale piano non avrebbe funzionato perché, a una più attenta analisi, ci si accorge che anche il compagno, in un’ottica meccanicamente razionalistica incentrata sulla massimizzazione del proprio profitto, avrebbe attuato allo stesso modo e dunque entrambi avrebbero ottenuto un punteggio medio di 88, mentre, non giocando razionalmente, avrebbero potuto raggiungere la votazione di 90.

Un’ultima “definizione” prima di spiegare un tema centrale della teoria dei giochi: senza entrare in tecnicismi diremo che in pratica la miglior risposta è la scelta più conveniente che un giocatore, che crede in un dato comportamento degli altri giocatori, possa fare. 

Equilibrio di Nash

Consigliamo vivamente di guardare questo video tratto dal celeberrimo film “A Beautiful Mind” prima di proseguire. 

https://www.youtube.com/watch?v=jAUlrWJtjVY

Dato un gioco, se nessuno dei partecipanti ha una strategia strettamente dominante, per predire l’evolversi della situazione, introduciamo il concetto di equilibrio di Nash secondo cui, in una situazione del genere, dobbiamo aspettarci che i giocatori usino le strategie che danno le migliori risposte le une alle altre. 

Si rimanda a [13] per una definizione più precisa, ma in pratica, se un gioco ammette almeno un equilibrio di Nash, ogni partecipante ha a disposizione almeno una strategia S1 alla quale non ha alcun interesse ad allontanarsi se tutti gli altri giocatori hanno giocato la propria strategia Sn. Questo perché se il giocatore i giocasse una qualsiasi altra strategia a sua disposizione, mentre tutti gli altri hanno giocato la propria strategia se, potrebbe solo peggiorare il proprio guadagno o, al più, lasciarlo invariato. Poiché questo vale per tutti i giocatori se esiste uno e un solo equilibrio di Nash, esso costituisce la soluzione del gioco in quanto nessuno dei giocatori ha interesse a cambiare strategia.

In altre parole si definisce equilibrio di Nash un profilo di strategie (una per ciascun giocatore) rispetto al quale nessun giocatore ha interesse ad essere l'unico a cambiare.

The Value of Coordination - 80,000 Hours

Esistono però giochi che presentano più equilibri di Nash.

Equilibri multipli: giochi di coordinazione

Si supponga, riprendendo l’esempio precedente, che gli studenti debbano preparare, una volta essersi divisi il lavoro, le slide della presentazione. Lo studente, senza possibilità di comunicare col compagno, deve decidere se creare le slide col programma A o col programma B considerando che sarebbe molto più facile unirle a quelle del compagno se fossero fatte con lo stesso software.

Un gioco di questo tipo è detto di coordinazione perché l’obiettivo dei due giocatori è quello di coordinarsi. In questo caso notiamo che ci sono più equilibri di Nash, cioè (A,A) e (B,B). Cosa bisogna aspettarsi?

La teoria dei punti focali (detti anche punti di Schelling) ci dice che possiamo usare caratteristiche intrinseche del gioco per prevedere quale equilibrio sarà quello scelto, cioè quello in grado di dare a tutti i giocatori un guadagno maggiore. Thomas Schelling ne “La strategia del conflitto” descrive un punto focale come: "l’aspettativa di ogni giocatore su quello che gli altri si aspettano che lui si aspetti di fare[7]. 

Premium Vector | People with question marks. man and woman with question,  thinking guy

Per esempio, ritornando al gioco degli studenti, se lo studente S1 sapesse che il compagno S2 predilige A, allora sceglierà A, infatti sapendo che S2 a sua volta sa che lui è a conoscenza di questo fatto assumerà che quest’ultimo sceglierà effettivamente A sapendo che S1 si conformerà di conseguenza.

Schelling illustra questo concetto tramite il seguente esempio: “domani devi incontrare un estraneo a New York, che luogo e ora sceglieresti?”

Che cosa fare a New York, Stati Uniti d'America - Eventi ed attività |  Eventbrite

Questo è un gioco di coordinamento, dove tutti gli orari e tutti i luoghi della città possono essere una soluzione di equilibrio. Proponendo il quesito a un gruppo di studenti constatò che la risposta più comune era: "alla Grand Central Station a mezzogiorno". La GCS non è un luogo che porterebbe a un guadagno maggiore (il giocatore potrebbe facilmente incontrare qualcuno al bar, o in un parco), ma la sua tradizione come luogo di incontro la rende speciale e costituisce, perciò, un punto di Schelling. Nella teoria dei giochi un punto di Schelling è una soluzione che i giocatori tendono ad adottare in assenza di comunicazione, poiché esso appare naturale, speciale o rilevante per loro.

La teoria dei giochi ben si combina con quella dei grafi e la introdurremo nei prossimi articoli per vedere altri esempi di come possa esistere un possibile conflitto tra razionalità individuale, nel senso di massimizzazione dell’interesse personale, ed efficienza, ovvero la ricerca del miglior risultato possibile, sia individuale sia collettivo.

Abbiamo anche visto che applicando una strategia individualistica si ottiene a volte un esito inferiore rispetto a quanto ottenibile nel caso in cui si possa raggiungere un accordo e che se esiste un equilibrio di Nash ed è unico, esso rappresenta la soluzione del gioco poiché nessuno dei giocatori ha interesse a cambiare strategia. 

Bibliografia e sitografia

[1] R. Dawkins, Il gene egoista, I edizione collana Oscar saggi, Arnoldo Mondadori Editore, 1995.

[2] D. Easley e J. Kleinberg, Networks, Crowds, and Markets: Reasoning about a Highly Con- nected World, Cambridge University Press, 2010.

[3] R. Gibbons, Teoria dei giochi, Bologna, Il Mulino, 2005.

[4] S. Rizzello e A. Spada, Economia cognitiva e interdisciplinarità, Giappichelli Editore, 2011.

[5] G. Romp,Game Theory: Introduction and Applications, Mishawaka, Oxford University Press, 1997

[6] T. C. Schelling, The Strategy of Conflict, Cambridge, Massachusetts: Harvard, University Press, 1960.

[7] P. Serafini, Teoria dei Grafi e dei Giochi, a.a. 2014-15 (revisione: 28 novembre 2014).

[8] http://it.wikipedia.org/wiki/Equilibrio_di_Nash consultato il 12/05/2015.

[9] http://www.oilproject.org/lezione/teoria-dei-giochi-equilibrio-di-nash-e-altri-concetti-introduttivi-2471.html consultato il 13/05/2015.

[10] https://www.youtube.com/watch?v=jILgxeNBK_8 consultato il 19/01/2021.

[11] https://it.wikipedia.org/wiki/Teoria_dei_giochi

[12] https://fiscomania.com/teoria-dei-giochi-prigioniero-nash/ 

Articolo a cura di Carla Melia e Lucia Campomaggiore, Data Scientist in Orbyta Tech, 25.03.2021

Risultati

resources

Recap Flutter Forward 2023: le 7 novità più interessanti

Recap Flutter Forward 2023: le 7 novità più interessanti

Quick Escape Room

Quick Escape Room

Orbyta Invaders Ignition

Orbyta Invaders Ignition

Il lancio della nuova Identity di Orbyta parte dal Metaverso!

Il lancio della nuova Identity di Orbyta parte dal Metaverso!

development

design

metaverse

brand identity

Database a grafo in SQL Server

Database a grafo in SQL Server

Data Science Job Roles

Data Science Job Roles

Teoria dei giochi: Propagazione delle strategie

Teoria dei giochi: Propagazione delle strategie

The chosen one: .NET 5

The chosen one: .NET 5

Network Science e Social Network Analysis

Network Science e Social Network Analysis

Isolation levels on SSMS

Isolation levels on SSMS

Teoria dei Grafi

Teoria dei Grafi

Creare un podcast in automatico a partire da audio vocali e musica

Creare un podcast in automatico a partire da audio vocali e musica

Teoria dei Giochi

Teoria dei Giochi

Recommender systems: principali metodologie degli algoritmi di suggerimento

Recommender systems: principali metodologie degli algoritmi di suggerimento

Introduction to Quantum Computing and Qiskit

Introduction to Quantum Computing and Qiskit

System Versioned Tables

System Versioned Tables

Vim o non Vim

Vim o non Vim

I vantaggi di un Message Broker

I vantaggi di un Message Broker

PlayStation 5 e l'accesso ai dati: un cambio architetturale?

PlayStation 5 e l'accesso ai dati: un cambio architetturale?

Protezione dei Web Services

Protezione dei Web Services

need more info?

contattaci