Qual è la teoria dei giochi algoritmici? Spiegato con esempi

Nel 1999, quando Nisan e Ronen hanno contribuito con le loro idee a un documento, il mondo ha assistito a un nuovo concetto di progettazione del meccanismo algoritmico. Tenta di negare The Price of Anarchy, dove l'interesse personale si traduce sempre in un sistema degradato.

Il loro articolo ha dimostrato che più parti interessate potrebbero stabilire un sistema produttivo in equilibrio. Quindi, invece di guardare a un'economia in degrado, guarderemmo al benessere sociale e alla massimizzazione delle entrate.

La teoria dei giochi algoritmici (AGT) si basa sulla comprensione di Algorithmic Mechanism Design (AMD) .

Mentre AMD descrive che l'interesse personale potrebbe portare a un buon sistema, AGT mira ad analizzare e progettare una configurazione strategica che descriva le azioni dei partecipanti interessati.

Prima di vedere come funziona AGT nell'ambiente strategico, diamo un'occhiata a come funziona la Teoria dei giochi!

Comprendiamo la teoria dei giochi con l'aiuto di un esempio

In un mondo perfetto, in cui ogni mossa è uno sforzo calcolato, Game Theory non avrebbe molto senso come oggi.

L'idea di calcolare la prossima mossa di cittadini intelligenti e razionali è sia elettrizzante che spaventosa.

La teoria dei giochi impone che in una data situazione sociale, le parti in competizione possano prendere decisioni razionali valutando la validità delle possibilità e stimando la mossa netta del concorrente.

Anche se può sembrare una scommessa, i teorici hanno ripristinato una strategia spiegabile che sradica la convinzione che sia una scommessa.

L'esempio più comunemente citato è il dilemma del prigioniero.

Scopri: gli 8 migliori progetti che ogni sviluppatore dovrebbe provare a colpo sicuro

Spiegazione del dilemma del prigioniero

La premessa è semplice: quando la polizia ha catturato due detenuti e li ha interrogati sul crimine, nessuno dei due avrebbe rotto il loro silenzio.

Quindi, il procuratore distrettuale ha deciso di semplificare la cosa stabilendo tre condizioni davanti a loro, poiché si trovano adiacenti.

• Condizione 1: se nessuno dei due confessa il crimine, va in prigione per sei anni.
• Condizione 2: se uno dei due denuncia l'altro, l'informatore può vagare liberamente mentre l'altro resta per dieci anni.
• Condizione 3: se entrambi confessano, vanno in prigione per un anno.

Immediatamente dopo aver ascoltato le condizioni, vengono portati in una stanza separata per prendere le loro decisioni.

Possiamo trasferire questi dati sotto forma di una matrice, in quanto tale;

Fonte

La soluzione a questo problema è semplice;

Ogni prigioniero prenderà in considerazione la possibilità di dire la verità sul crimine. Nessuno dei due può dire rigorosamente che l'altro starà zitto. Così, cedendo alla probabilità, entrambi decidono di confessare il delitto e di andare in prigione solo per un anno.

La teoria dei giochi è un'arma potente nelle mani di chi la brandisce. Possiamo decifrare anche le situazioni più complesse comprendendo la natura dei numeri e la collocazione dell'assetto sociale.

Teoria dei giochi algoritmici

Consideriamo ora un diagramma di Venn della teoria dei giochi e dell'informatica. Immagina un aumento drastico del livello di accuratezza perché tracciare la probabilità di ottenere risposte.

E questo è ciò che fa la teoria dei giochi algoritmici (AGT) !

Tenta di risolvere i problemi dei giorni nostri trovando un perfetto equilibrio tra algoritmi informatici e teoria dei giochi.

In altre parole più semplici, la teoria dei giochi algoritmici tenta di definire l'equilibrio socio-economico tra l'esecuzione di un compito. Utilizza anche i principi dell'Equilibrio di Nash; afferma che una volta che i partecipanti trovano una strategia che funziona per loro, non vorranno deviare da essa finché non smette di funzionare a loro vantaggio.

Facciamo un piccolo esempio per comprendere il funzionamento della teoria dei giochi algoritmici.

Torniamo a scuola quando giocavamo a giochi come Kho-Kho, Ice & Water, Chain-Cut, ecc. Ognuno di questi giochi ha un bel design e un meccanismo per giocare.

Prendiamo ad esempio Ice & Water;

• Ci sono diversi giocatori e un ricevitore. Il ricevitore dovrebbe trasformare tutti in ghiaccio.
• Gli altri giocatori hanno il potere di riportare qualcuno in acqua al tocco.
• Ci sono zone libere dove i giocatori possono riposare per 30 secondi.

Ora, se guardi attentamente, vedrai che ognuna di queste regole costituisce il meccanismo del gioco e ne definisce il design.

• I giocatori possono giocare a questo gioco fintanto che lo trovano interessante. Qui, The Nash Equilibria descrive che finché i giocatori trovano la loro strategia funzionante e il gioco interessante, giocheranno.
• La razione di un giocatore è di non farsi prendere. E lei agisce su quella razione comprendendo l'impostazione. Implementa un approccio oggettivo, in cui vince la partita non facendosi beccare. E questo è popolarmente noto come Mechanism Design o Reverse Game Theory.
• Ora, nel caso in cui ogni giocatore consideri solo un motivo – “Di non farsi prendere” – e non consideri la seconda parte – “di salvare gli altri giocatori”, allora questo concetto è chiamato Prezzo dell'Anarchia. Spiega come l'efficienza di qualsiasi sistema si degraderà a causa dei comportamenti egoistici dei giocatori.

Ora, una pletora di più concetti emergono dai tre concetti sopra menzionati. Sebbene siano tutti interamente o moderatamente correlati alla teoria dei giochi, creano una base funzionale per la teoria dei giochi algoritmica.

Checkout: 42 entusiasmanti idee e argomenti per progetti Python per principianti

Ora sorge la domanda: "Come rappresentiamo un ambiente strategico in termini di algoritmi?"

Diamo ora un'occhiata a come possiamo usare Python per definire un ambiente strategico e comprendere l'implementazione di Nashpy per una determinata situazione.

Immagina di giocare a sasso-carta-forbici con uno dei tuoi amici. Ognuno di voi ha una delle tre opzioni;

• Roccia
• Carta
• Forbici

E la rubrica per vincere la partita è

• La roccia schiaccia le forbici
• Le forbici tagliano le carte
• La carta copre la roccia

E questo significa che se entrambi i giocatori presentano rock, questo spiega le ripetizioni.

Possiamo rappresentarlo sotto forma di una matrice 3×3 dove si trova Aij;

Fonte

Nota: qui i e j sono i turni giocati dai due giocatori.

Qui,

• Zero rappresenta che entrambi avete giocato lo stesso oggetto (roccia-roccia; o carta-carta)
• Uno rappresenta che uno di voi ha battuto l'altro (come forbici da roccia)
• Meno Uno rappresenta che uno di voi due ha perso perché l'altro vi ha prevalso (come carta da sasso)

Ora, per rappresentare questo su Nashpy, scriverai un codice simile a questo;

Fonte

Pensieri finali

La teoria dei giochi algoritmici è un principio perfetto nel mondo attuale in cui la competizione nasce dall'interesse personale e la vittoria è il raggiungimento dell'interesse personale.

Quindi, come manager, insegnanti, CXO o uomini d'affari moderni, se capisci il predominio della teoria dei giochi algoritmici, allora mi permette di modificare la citazione di Severus Snape di Harry Potter;

"La teoria dei giochi algoritmici può insegnarti come imbottigliare la fama, produrre gloria e persino mettere un freno alle perdite."

Comprendere la teoria dei giochi algoritmici può aiutarti a gestire i numeri in modo più deciso che mai. Nell'era attuale, in cui decidiamo le cose nei minimi dettagli per sviluppare un piano sostenibile, AGT si rivela un aspetto di trasformazione.

Sappiamo già che la scienza dei dati può trasformare le aziende in un'arena redditizia, ma AGT ha il potere di alzare la soglia.

Supponiamo che tu sia ancora scettico sulla teoria dei giochi e su come la scienza dei dati sia la professione più redditizia e competitiva oggi.

Se sei curioso di conoscere la scienza dei dati, dai un'occhiata al Diploma PG in Data Science di IIIT-B e upGrad, creato per i professionisti che lavorano e offre oltre 10 casi di studio e progetti, workshop pratici pratici, tutoraggio con esperti del settore, 1- on-1 con mentori del settore, oltre 400 ore di apprendimento e assistenza al lavoro con le migliori aziende.