delete

Contattaci

back to resources

Teoria dei Grafi

data
14/5/2021
data progetto
autore
simone
cliente
partnership
url
No items found.

Introduzione alla teoria dei grafi per la teoria dei giochi

Nell’articoloprecedente (https://orbyta.it/teoria-dei-giochi/) abbiamo illustrato i principibase della teoria dei giochi e, tramite qualche esempio, abbiamo scoperto comepuò essere utilizzata per attuare la strategia più conveniente in unasituazione in cui il guadagno finale dipende dalle mosse effettuate dagli altrigiocatori.

In questo secondo articolo scopriremo cos’è la teoria dei grafi e come può essere integrata nella teoria dei giochi. Inoltre, introdurremo un altro tipo di equilibrio di Nash, ovvero gli equilibri di Nash per strategie miste.

La teoria dei grafi

I grafi possono essere utilizzati per schematizzare delle situazioni o processi e ne consentono l’analisi in termini quantitativi e algoritmici.

Tecnicamente,un grafo(o rete) G è una coppia (V, E) dove Vè un insieme finito i cui elementi sono dettivertici o nodi ed E è unsottoinsieme i cui elementi, detti archi o lati, sono coppie di oggetti inV.

Per esempio, nella seguente immagine vediamo un grafo con vertici V={A,B,C,D} ed archi E={(A,B), (B,A), (B,D), (D,B), (D,C), (C,D), (B,C), (C,B)}.

Unadigrafo è un grafo che possiedealmeno un arco orientato, cioè un arco caratterizzato da un verso che non può essere percorso nel versoopposto.

Per esempio modificando il grafo precedente come segue otteniamo un digrafo con archi E={(B,A), (B,D), (D,B), (D,C), (C,D), (B,C), (C,B)}.

Introduciamo ora qualche esempio pratico per capire come i grafi possono essere utilizzati nella teoria dei giochi.

Esempio numerico [4]

Consideriamouna situazione in cui sono presenti due giocatori e il primo di essi, A,sceglie un numero tra 1,2 e 3. Ilsecondo partecipante, B, somma al numero detto1,2 o 3. A farà lo stesso nel turno successivoe così via finché uno dei due arriverà ad esclamare 31 vincendo.
Talegioco può essererappresentato tramite il seguente digrafo:

I vertici sono i numerinaturali dall’1 al 31 e gli archiche partono dal vertice n entrano in quelli n+1, n+2 e n+3 se 1 ≤ n ≤ 28. Dal 29 escono degli archi entranti in 30 e 31, dal 30 in 31 e dal 31 nessuno.

Dunque, il giocatore che riescea dire 27 ha vinto perché il giocatore successivo potràselezionare solo i vertici 28, 29, o 30 e, in ognuno di questi casi, il primoriuscirà a posizionarsi sul 31.

Possiamo quindi porcicome obiettivo di arrivare al 27 e nonal 31. Ma a questopunto chi dirà23 riuscirà avincere e, applicando il ragionamento iterativamente, concludiamo che i nodi da toccare per vincere sono X = {3, 7, 11,15, 19, 23,27, 31}.

Osserviamo che:

  • Seun giocatore dice un numero nonappartenente a X allora l’avversario ha sempre la possibilità di farlo e dunque di vincere.
  • Se un giocatore diceun numero appartenente a X alloral’avversario non potràche scegliere un numero adesso non appartenente.

In conclusione, analizzando il grafo, scopriamo che l’obiettivo è quello di occupare sempre le posizioni di X.

Esempio della protesta

Supponiamo di voler manifestare contro una data azione di un governo dittatoriale. Tale evento risulterà vantaggioso solo se il numero di manifestanti sarà sufficientemente elevato, d’altro canto se ciò non dovesse accadere andremmo in contro ad un payoff assai negativo in quanto potremmo supporre che, in tal caso, lo stato sederà la manifestazione in modo violento.

Supponiamo che ogni persona decidadi partecipare alla protesta solose sa che almeno un numero sufficiente di cittadini vi aderirà.

Supponiamo di avere 4 cittadinie rappresentiamo il fatto che ilcittadino w conosca il comportamentodi quello u e viceversa con la presenza del lato (w,u). La cifra accanto a unnodo indica il numero minimodi manifestanti totaliaffinché il nodoin questione si unisca all’impresa.

Consideriamo le seguenti situazioni:

Notiamoche nel caso A la rivolta non avrà luogo in quanto ognuno dei partecipanti nonha modo di sapere il comportamento che adotterà il nodo ad esso non collegato.

Nel caso B invece ognuno tra u, v e w saprà che esistono almeno altri due nodi che richiedono almeno tre partecipanti totali e che a loro volta hanno questa informazione. Dunque la protesta si svolgerà, in particolare u, v e w saranno i manifestanti.

Equilibrio di Nash perstrategie miste

Esistono dei giochi in cui non sono presenti gli equilibri di Nash che abbiamo introdotto nell’articoloprecedente, ovvero quelli basati su strategiapure. Una strategia pura infatti fornisce una descrizione completadel modo in cui un individuo gioca una partita.In particolare, essa determina quale scelta farà il giocatore in qualsiasi situazione che potrebbeaffrontare.

Una strategiamista per un giocatore è una distribuzione di probabilità sull’insieme delle strategie pure che ha a disposizione. Ogni strategia pura P può essere vista come un casoparticolare di strategia mista che assegna probabilità pari a 1 a P e pari a 0a tutte le altre strategie pure.

Abbiamo quindi due tipi di equilibri di Nash: quelliper le strategie pure, analizzati finora, si hanno quando tutti i giocatorihanno a disposizione solo strategie pure, altrimenti si parla di equilibri diNash per strategie miste.

Limitandoci ad un gioco a due partecipanti, un equilibriodi Nash per le strategie miste è una coppia di scelte (che ora sonoprobabilità) tale che ognuna sia la miglior risposta all’altra.

Introduciamo un esempio.

Esempiodell’attaccante/difensore

Si consideri un gioco in cui c’è un attaccante A e un difensore D.

L’attaccantepuò scegliere tra le strategie di attacco a1o a2 mentre il difensore può difendersi da a1, equindi applicare la strategia d1, o viceversa difendersi da a2, equindi applicare la strategia d2.

Supponiamoche:

  • se D scegliesse la giusta strategia di difesa, cioè di contro ai (i = 1, 2),avremmo per A un guadagno di 0;
  • seD scegliesse d1 e A scegliessea2, A otterrebbe unguadagno di 5 e D una perdita pari;
  • seD scegliesse d2 mentre A scegliesse a1, A ricaverebbe un guadagnodi 10 e D una perdita pari.


Riassumiamo la situazione del gioco nella seguente tabella indicando in ogni riquadro: a sinistra della virgola il guadagno ottenuto da A e a destra della virgola quello ottenuto da D.

Nel nostro esempio a1 e a2 sono lestrategie pure a disposizione dell’attaccante, mentre difendere da a1 e difendere da a2 quelle del difensore.

Dato che i due giocatori otterrebbero dei guadagni nettamente contrastanti potremmoconcludere che in questogenere di giochi (detti strettamente competitivi) non esistano equilibri diNash.

Seuno dei due giocatori sapesse il comportamento dell’altro allora potrebbe scegliere la strategia atta a massimizzare il suo profitto e inevitabilmente a minimizzarequello dell’avversario. Ognuno dei giocatori cercheràperciò di rendereimprevedibile la propria strategia.

Siap la probabilità che A scelga a1 e q la probabilità che D scelga d1.Per ora sappiamo solo che esistealmeno un equilibrio per le strategie miste ma non quali debbanoessere i valorieffettivi di p e q.

Usiamo il principio secondocui un equilibrio misto sorge quando le probabilitàutilizzate da ciascun giocatore fanno sì che il suo avversario non abbia motivodi preferire una delle due opzioni disponibili all’altra.

Se supponiamo che D abbiauna probabilità q di giocared1 alloraabbiamo che i possibili guadagni per A sono:

  • (0)(q) + (10)(1 − q) = 10 − 10q se scegliesse a1;
  •  (5)(q) + (0)(1 − q) = 5q se scegliesse a2.

Per far in modo che per A sia indifferente scegliere tra a1 e a2 imponiamo 10−10q = 5q da cui q = 2/3.

Orasupponiamo che A abbia unaprobabilità p di mettere in atto a1. I possibili guadagni per D allora sono:

  • (0)(p) + (−5)(1 − p) = 5p − 5 se scegliesse d1
  • (−10)(p) + (0)(1 − p) = −10p sescegliesse d2

Imponendo5p − 5 = −10p otteniamo p = 1/3.

Quindi abbiamoche gli unici possibilivalori di probabilità che possonoapparire nell’equilibrio perla strategia mista sono p = 1/3 per l’attaccante e q = 2/3 per il difensore.

Sinoti inoltre che il guadagno attesodi A nel caso in cui scelga a1e D scelga d1 è di 10/3 e quellodi D è di -10/3.

Ciòci suggerisce un’analisi controintuitiva:la probabilità di A di sferrare l’attacco più forte è di un terzo, ovvero, in un modello continuo, potremmoimmaginare che solo per un terzodel tempo A provi ad attaccarecon a1.

Perché usare così poco la strategia più potente?

La rispostaè che se A provasse sempre ad attaccare con a1 allora D sarebbe persuasoa rispondere spesso con d1,il che ridurrebbe il payoff atteso da A. D’altro canto si consideri che poiché p = 1/3 fa sì che D scelga senza preferenzauna delle due strategie e abbiamo che, quando A usa tale valore di probabilità, allora, indipendentemente dalle scelte diD, esso si assicura un payoff di 10/3.

Esempio delle imprese

Consideriamo ora il fatto che anche se un giocatore non ha una strategia dominante, esso potrebbe avere strategie che sono dominate da altre. Si consideri il seguente esempio.

Supponiamo che due imprese, F1 e F2, stiano progettando di aprire un negozio in una delle sei città situate lungo sei uscite consecutive su una strada. Possiamo rappresentare la disposizione di queste città utilizzando un grafo a sei nodi come quello nella figura sottostante [2].

Supponiamo che F1 possa aprire il suo negozio in A, C o E mentre F2 in B, D o F. Una volta che i negozi apriranno, i clienti delle varie città faranno compere nel centro a loro più vicino. Si assuma che ogni città abbia lo stesso numero di clienti e che i guadagni dei negozi siano direttamente proporzionali al numero di clienti attirati. Otteniamo facilmente la tabella di guadagni sottostante.

Si può verificare che nessuno dei giocatori ha una strategia dominante: per esempio se F1 scegliesse la locazione A allora la risposta strettamente migliore di F2 sarebbe B, mentre se F1 scegliesse E la risposta strettamente migliore di F2 sarebbe D. Nonostante ciò notiamo che A è una strategia strettamente dominata per F1, infatti in ogni situazione in cui F1 ha l’opzione di scegliere A, esso riceverà un guadagno strettamente migliore scegliendo C. Analogamente F è una strategia strettamente dominata per F2. Abbiamo dunque che F1 non sceglierà A e F2 non sceglierà F. Possiamo a questo punto non considerare i nodi F e A, e da ciò ricaviamo la seguente tabella di payoff:

B ed E divengonorispettivamente le nuove strategie strettamente dominate per F2 e F1 e quindipossono essere a loro volta eliminate. Arriviamo alla conclusione che F1 sceglierà C e F2 D.

Questomodo di procedere è chiamato cancellazioneiterativa delle strategie strettamentedominate. Notiamo inoltreche la coppia (C,D)costituisce l’unico equilibrio di Nash del gioco ed infattiquesta metodologia di studio è anche utile a trovare gli equilibridi Nash. Generalizziamo di seguito il processoappena presentato.

Datoun numero arbitrario di n giocatori abbiamo che la cancellazione iterativadelle strategie strettamente dominate procede come segue:

  1. Siparte da un giocatore, si trovano tuttele sue strategie strettamente dominate e le si eliminano;
  2. Si considerail gioco semplificato ottenuto. Si eliminanoeventuali nuove strategie strettamente dominate;
  3. Si itera il processo finché non si trovano più strategie strettamente dominate.

Si può dimostrare che l’insieme degli equilibri di Nash dellaversione originale del gioco coincide con quello della versione finalecosì ottenuta.

Consideriamo un problema in cui due giocatori A e B possano optare per la strategia a o b con i seguenti guadagni simmetrici:

Inquesto caso a è una strategia debolmentedominata poiché in ogni caso ogni giocatore può solo migliorare il suoguadagno scegliendo b. Inoltre si noti che (b,b) è un equilibrio di Nash.

Quando abbiamo delle strategie debolmente dominate non è consigliabile procederecon il metodo della cancellazione, poiché questa operazione potrebbe distruggere degliequilibri.

D’altro cantoè intuitivo pensare che nessungiocatore scelga di assecondare l’equilibrio (a,a) composto da strategie debolmente dominate se non ha modo di prevedere il comportamento dell’altro giocatore: perché non usare la strategia (b,b) che nel peggiore dei casi comunque non inficiail  guadagno?

In questo articolo abbiamo visto come la teoria dei grafi può essere usata in quella dei giochi andando a risolvere giochi che hanno dato risultati controintuitivi. Nel prossimo articolo, approfondiremo le reti andando a studiare situazioni più complesse che ci permetteranno di analizzare la propagazione delle strategie all’interno di una rete.

Bibliografia e sitografia

[2] D. Easley e J. Kleinberg, Networks, Crowds, andMarkets: Reasoning about a Highly Con- nected World, Cambridge UniversityPress, 2010.

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

[4] E.Martìn Novo e A. Mendez Alonso, Aplicaciones de la teoría de grafos a algunosjuegos de estrategia, numero 64 di Suma, Universidad Politécnica de Madrid,2004.

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

[9] I. S.Stievano e M. Biey, Cascading behavior in networks, DET, Politecnico di Torino,2015.

[10] I. S.Stievano e M. Biey, Interactions within a network, DET, Politecnico di Torino,2015.

[11] I. S.Stievano, M. Biey e F. Corinto, Reti e sistemi complessi, DET, Politecnico diTorino, 2015.

[12] A.Ziggioto e A. Piana, Modello di Lotka-Volterra, reperibile all’indirizzohttp://www.itismajo.it/matematica/Lezioni/Vecchi%20Documenti%20a.s.%202011-12/Modello

%20di%20Lotka-Volterra.pdf,consultato il 15/05/2015.

 [15]http://web.econ.unito.it/vannoni/docs/thgiochi.pdf consultato il 14/05/2015.

Articolo a cura di MonicaMura e Carla Melia, Data Scientist in Orbyta Tech, 01.05.2021

Risultati

resources

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