delete

Contattaci

back to resources

Teoria dei Grafi

data
14/5/2021
data progetto
autore
Monica Mura, Carla Melia
cliente
partnership
url
No items found.

Introduzione alla teoria dei grafi per la teoria dei giochi

Nell’articolo precedente abbiamo illustrato i principi base della teoria dei giochi e, tramite qualche esempio, abbiamo scoperto come può essere utilizzata per attuare la strategia più conveniente in una situazione in cui il guadagno finale dipende dalle mosse effettuate dagli altri giocatori.

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 detti vertici o nodi ed E è un sottoinsieme 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)}.

Una digrafo è un grafo che possiede almeno un arco orientato, cioè un arco caratterizzato da un verso che non può essere percorso nel verso opposto.

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]

Consideriamo una situazione in cui sono presenti due giocatori e il primo di essi, A, sceglie un numero tra 1,2 e 3. Il secondo partecipante, B, somma al numero detto 1, 2 o 3. A farà lo stesso nel turno successivo e così via finché uno dei due arriverà ad esclamare 31 vincendo.

Tale gioco può essere rappresentato tramite il seguente digrafo:

I vertici sono i numeri naturali dall’1 al 31 e gli archi che 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 riesce a dire 27 ha vinto perché il giocatore successivo potrà selezionare solo i vertici 28, 29, o 30 e, in ognuno di questi casi, il primo riuscirà a posizionarsi sul 31.

Possiamo quindi porci come obiettivo di arrivare al 27 e non al 31. Ma a questo punto chi dirà23 riuscirà a vincere 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:

  • Se un giocatore dice un numero non appartenente a X allora l’avversario ha sempre la possibilità di farlo e dunque di vincere.
  • Se un giocatore dice un numero appartenente a X allora l’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 decida di partecipare alla protesta solo se sa che almeno un numero sufficiente di cittadini vi aderirà.

Supponiamo di avere 4 cittadini e rappresentiamo il fatto che il cittadino w conosca il comportamento di quello u e viceversa con la presenza del lato (w,u). La cifra accanto a un nodo indica il numero minimo di manifestanti totali affinché il nodo in questione si unisca all’impresa.

Consideriamo le seguenti situazioni:

Notiamo che nel caso A la rivolta non avrà luogo in quanto ognuno dei partecipanti non ha 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 per strategie miste

Esistono dei giochi in cui non sono presenti gli equilibri di Nash che abbiamo introdotto nell’articolo precedente, ovvero quelli basati su strategie pure. Una strategia pura infatti fornisce una descrizione completa del modo in cui un individuo gioca una partita. In particolare, essa determina quale scelta farà il giocatore in qualsiasi situazione che potrebbe affrontare.

Una strategia mista 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 caso particolare 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: quelli per le strategie pure, analizzati finora, si hanno quando tutti i giocatori hanno a disposizione solo strategie pure, altrimenti si parla di equilibri di Nash per strategie miste.

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

Introduciamo un esempio.

Esempio dell’attaccante/difensore

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

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

Supponiamo che:

  • 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 scegliesse a2, A otterrebbe un guadagno di 5 e D una perdita pari;
  • seD scegliesse d2 mentre A scegliesse a1, A ricaverebbe un guadagno di 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 le strategie 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 potremmo concludere che in questo genere di giochi (detti strettamente competitivi) non esistano equilibri di Nash.

Se uno dei due giocatori sapesse il comportamento dell’altro allora potrebbe scegliere la strategia atta a massimizzare il suo profitto e inevitabilmente a minimizzare quello dell’avversario. Ognuno dei giocatori cercherà perciò di rendere imprevedibile la propria strategia.

Sia p la probabilità che A scelga a1 e q la probabilità che D scelga d1.Per ora sappiamo solo che esiste almeno un equilibrio per le strategie miste ma non quali debbano essere i valori effettivi di p e q.

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

Se supponiamo che D abbia una probabilità q di giocare d1 allora abbiamo 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.

Ora supponiamo che A abbia una probabilità 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 se scegliesse d2

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

Quindi abbiamo che gli unici possibili valori di probabilità che possono apparire nell’equilibrio perla strategia mista sono p = 1/3 per l’attaccante e q = 2/3 per il difensore.

Si noti inoltre che il guadagno atteso di A nel caso in cui scelga a1e D scelga d1 è di 10/3 e quello di 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, potremmo immaginare che solo per un terzo del tempo A provi ad attaccare con a1.

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

La risposta è che se A provasse sempre ad attaccare con a1 allora D sarebbe persuaso a 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 preferenza una 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 divengono rispettivamente le nuove strategie strettamente dominate per F2 e F1 e quindi possono essere a loro volta eliminate. Arriviamo alla conclusione che F1 sceglierà C e F2 D.

Questo modo di procedere è chiamato cancellazione iterativa delle strategie strettamente dominate. Notiamo inoltre che la coppia (C,D) costituisce l’unico equilibrio di Nash del gioco ed infatti questa metodologia di studio è anche utile a trovare gli equilibri di Nash. Generalizziamo di seguito il processo appena presentato.

Dato un numero arbitrario di n giocatori abbiamo che la cancellazione iterativa delle strategie strettamente dominate procede come segue:

  1. Si parte da un giocatore, si trovano tutte le sue strategie strettamente dominate e le si eliminano;
  2. Si considera il gioco semplificato ottenuto. Si eliminano eventuali 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 della versione originale del gioco coincide con quello della versione finale così ottenuta.

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

In questo caso a è una strategia debolmente dominata poiché in ogni caso ogni giocatore può solo migliorare il suo guadagno scegliendo b. Inoltre si noti che (b,b) è un equilibrio di Nash.

Quando abbiamo delle strategie debolmente dominate non è consigliabile procedere con il metodo della cancellazione, poiché questa operazione potrebbe distruggere degli equilibri.

D’altro canto è intuitivo pensare che nessun giocatore 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 inficia il  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 Connected 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 algunos juegos 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’indirizzo http://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 Monica Mura e Carla Melia, Data Scientist in Orbyta Tech, 01.05.2021

Risultati

resources

Le nuove linee guida per la sicurezza delle password aziendali

Le nuove linee guida per la sicurezza delle password aziendali

Password aziendali

Linee guida Garante Privacy

Garante Privacy

GDPR

6 motivi per scegliere Flutter nel 2024

6 motivi per scegliere Flutter nel 2024

App Development

Google

React Native

AI, sistemi esperti e rappresentazione della conoscenza

AI, sistemi esperti e rappresentazione della conoscenza

Sistemi esperti

Rappresentazione della conoscenza

Tradurre la Lingua Italiana dei Segni - il Progetto LIS2Speech

Tradurre la Lingua Italiana dei Segni - il Progetto LIS2Speech

LIS2SPEECH

Traduzione LIS

User Experience Design tra accessibilità e inclusività

User Experience Design tra accessibilità e inclusività

User Experience

Accessibilità

Inclusività

Assitech.Net entra nella galassia Orbyta Technologies

Assitech.Net entra nella galassia Orbyta Technologies

Orbyta Technologies

Orbyta Group

Acquisizione

News

Programmazione Funzionale Java

Programmazione Funzionale Java

Functional Programming

Java

Software Development

Reactive Programming: parallelizzare con Project Reactor

Reactive Programming: parallelizzare con Project Reactor

Programmazione Reattiva

Reactive Programming

Project Reactor

Piattaforme E-commerce Wholesale per il settore B2B

Piattaforme E-commerce Wholesale per il settore B2B

Wholesale

B2B

Antipattern nello sviluppo software: altri errori da evitare

Antipattern nello sviluppo software: altri errori da evitare

Software Development

Antipattern nello sviluppo software: definizione, ambiti di applicazione ed esempi

Antipattern nello sviluppo software: definizione, ambiti di applicazione ed esempi

Software Development

App tattiche di supporto alla gestione dei progetti reiterativi

App tattiche di supporto alla gestione dei progetti reiterativi

App Development

Power Platform

Low Code

DevOps

Introduzione a Power Pages, il servizio Microsoft per siti web low-code

Introduzione a Power Pages, il servizio Microsoft per siti web low-code

Microsoft

Low-code

Power Platform

Introduzione a Jupyter e Seaborn per Data Analysis e Visualization

Introduzione a Jupyter e Seaborn per Data Analysis e Visualization

Jupiter

Python

Data Analysis

Data Visualization

Come utilizzare Matplotlib per la Data Visualization in Python

Come utilizzare Matplotlib per la Data Visualization in Python

Python

Data Visualization

Data Science

Data Analysis

Introduzione alla libreria Dash per Python

Introduzione alla libreria Dash per Python

Python

Data Science

Data Visualization

Data Analysis

Prime Video passa al monolite: ma allora serverless è inutile? 

Prime Video passa al monolite: ma allora serverless è inutile? 

Tableau per la Business Intelligence: introduzione, tutorial e confronto

Tableau per la Business Intelligence: introduzione, tutorial e confronto

Introduzione a Qlik Sense, piattaforma di Business Intelligence avanzata

Introduzione a Qlik Sense, piattaforma di Business Intelligence avanzata

Applicazioni Cloud Native: definizione, vantaggi e tecnologie

Applicazioni Cloud Native: definizione, vantaggi e tecnologie

Power Apps Tutorial – Case Study: come costruire una business app da zero

Power Apps Tutorial – Case Study: come costruire una business app da zero

Il futuro del gaming tra F2P, GaaS, Crypto e Play to Earn

Il futuro del gaming tra F2P, GaaS, Crypto e Play to Earn

Power Apps Basics: interfacce, implementazione & vantaggi

Power Apps Basics: interfacce, implementazione & vantaggi

Strumenti di Business Intelligence: QlikSense & Power BI a confronto

Strumenti di Business Intelligence: QlikSense & Power BI a confronto

Introduzione a Serverless: non solo Lambda Function

Introduzione a Serverless: non solo Lambda Function

Metaverso: siamo pronti a cogliere l’opportunità?

Metaverso: siamo pronti a cogliere l’opportunità?

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

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

Let's Redux React to a Game

Let's Redux React to a Game

Introduzione a PowerShell

Introduzione a PowerShell

Pago con carta: i trend dei pagamenti digitali e il futuro delle carte di credito

Pago con carta: i trend dei pagamenti digitali e il futuro delle carte di credito

NFT World: il fenomeno NFT tra metaverso, business e GameFi

NFT World: il fenomeno NFT tra metaverso, business e GameFi

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: i 4 ruoli più richiesti nel settore

Data Science Job Roles: i 4 ruoli più richiesti nel settore

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