Skip to content
Torna ai risultati

Equilibrio di Nash

Introdotto da
John Nash
Anno
1950
Tipo
algorithm
Famiglia
Game-theoretic

Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese

Dimensione del carattere

A cosa serve?

L'Equilibrio di Nash è un concetto di soluzione della teoria dei giochi in cui nessun giocatore può deviare unilateralmente per migliorare il proprio payoff.

Formalizzato da John Nash nel 1950, l'algoritmo di Lemke-Howson trova computazionalmente gli equilibri nei giochi bimatrice identificando coppie di vertici completamente etichettati nei politopi delle strategie.

L’intuizione alla base del metodo

In un Equilibrio di Nash, la strategia di ciascun giocatore è la migliore risposta a ogni altra strategia degli altri giocatori. Immaginate una situazione in cui entrambi i giocatori conoscono la strategia dell'altro: nessuno dei due vorrebbe cambiare, poiché farlo peggiorerebbe solo la propria situazione. L'algoritmo di Lemke-Howson sfrutta la geometria dei poliedri di gioco, tracciando etichette (vincoli insoddisfatti) e pivotando attraverso i vertici fino a trovare una coppia completamente etichettata, una configurazione in cui entrambi i giocatori non hanno deviazioni profittevoli.

Storia

John Nash dimostrò nella sua tesi del 1950 che ogni gioco finito possiede almeno un Equilibrio di Nash a strategie miste. Nel 1964, Lemke e Howson pubblicarono il primo algoritmo costruttivo per trovare questi equilibri, trasformando la prova di esistenza di Nash in un metodo computazionale pratico. Il loro lavoro divenne fondamentale per la teoria dei giochi computazionale e l'economia algoritmica.

Quando usarlo

Utilizzare l'analisi dell'Equilibrio di Nash quando si studiano giochi con due giocatori e spazi di strategie discreti, o quando si cercano equilibri completamente misti. Adatto per modellare problemi di competizione, negoziazione e coordinamento in cui l'interazione strategica è fondamentale. Il metodo di Lemke-Howson funziona al meglio per giochi bimatrice non degeneri; casi degeneri possono richiedere calcolo simbolico o perturbazione.

Limiti e considerazioni

  • Limitato a giochi bimatrice (a due giocatori); l'estensione a giochi a n giocatori è NP-hard
  • Fallisce o diventa inefficiente su giochi degeneri dove sono possibili pivot multipli in entrata
  • Può trovare un solo equilibrio; spesso esistono equilibri multipli in giochi non a somma zero
  • Non gestisce direttamente giochi dinamici o in forma estesa senza riformulazione

Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.

Punti di forza

  • Computazionalmente efficiente per trovare equilibri di Nash in giochi bimatrice finiti
  • Garantisce la convergenza a una coppia di vertici completamente etichettata per giochi non degeneri
  • Fornisce una base teorica che collega la geometria combinatoria alla teoria dei giochi
  • Applicabile agli equilibri di strategie miste, che sono spesso più realistici dei risultati di strategie pure

Applicazioni

  • Economia: modellazione della competizione oligopolistica e del comportamento di definizione dei prezzi nei mercati
  • Aste e progettazione di meccanismi: analisi delle strategie di offerta nelle aste al primo prezzo e a busta chiusa
  • Sicurezza informatica: previsione degli equilibri tra attaccante e difensore nei giochi di sicurezza di rete
  • Biologia della fauna selvatica: analisi delle strategie evolutivamente stabili nelle interazioni predatore-preda

Come funziona

Come funziona

1

Convertire il gioco bimatrice in due problemi di complementarità lineare (LCP), uno per ciascun giocatore, che rappresentano le loro condizioni di migliore risposta.

2

Assegnare etichette agli spigoli e ai vertici dei politopi delle strategie in base a quali vincoli di incentivo del giocatore sono violati.

3

Partendo dal vertice di tutti uni (completamente etichettato), eseguire pivot simili al simplesso per navigare nel politopo, rimuovendo e aggiungendo etichette fino a scoprire una coppia completamente etichettata.

4

Confermare che le strategie di entrambi i giocatori formano migliori risposte reciproche verificando che nessuno possa migliorare il proprio payoff data la strategia dell'altro.

Errori comuni

  • Assumendo l'esistenza di un equilibrio unico; molti giochi hanno equilibri di Nash multipli con diverse implicazioni di payoff
  • Confondere equilibri di strategie miste (gioco probabilistico) con equilibri di strategie pure, portando a un'interpretazione errata del comportamento degli agenti
  • Trascurare la distinzione tra condizioni necessarie e sufficienti per l'equilibrio; una coppia completamente etichettata soddisfa l'ottimalità ma potrebbe non essere realizzata se i giocatori non riescono a coordinarsi

Domande frequenti

Un gioco può non avere un Equilibrio di Nash?

Gli equilibri di Nash a strategie pure potrebbero non esistere (ad es. Sasso-Carta-Forbici), ma ogni gioco finito ha almeno un equilibrio a strategie miste in cui i giocatori randomizzano sulle azioni con probabilità specifiche.

In che modo un equilibrio a strategie miste differisce da un equilibrio a strategie pure?

In un equilibrio a strategie pure, ogni giocatore si impegna in un'azione specifica con certezza. In un equilibrio a strategie miste, ogni giocatore utilizza una distribuzione di probabilità sulle azioni. Gli equilibri misti sono spesso più generali e esistono quando quelli puri non lo fanno.

Perché l'algoritmo di Lemke-Howson è preferito alla ricerca esaustiva?

L'algoritmo sfrutta la struttura poliedrica degli spazi delle strategie, riducendo lo spazio di ricerca esponenzialmente e raggiungendo la convergenza in tempo polinomiale per giochi non degeneri, mentre l'enumerazione esaustiva diventa infattibile all'aumentare dello spazio delle strategie.

Metodi correlati

Fonti

  1. Nash, J. F. (1950). Equilibrium points in N-person games. Proceedings of the National Academy of Sciences, 36(1), 48-49.

    Apri il riferimento DOI
    Copiato.
  2. Lemke, C. E., & Howson Jr, J. T. (1964). Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12(2), 413-423.

    Apri il riferimento DOI
    Copiato.