On Discrete-Time Approximations to Infinite Horizon Differential Games

Sintesi Tecnica: Approssimazioni Discrete per Giochi Differenziali a Orizzonte Infinito

Enunciato del Problema
Il lavoro affronta l'approssimazione numerica degli Equilibri di Nash Markoviani (MNE) in giochi differenziali non cooperativi a $N$ giocatori con orizzonte infinito. In tali giochi, $N$ giocatori interagiscono strategicamente nel tempo, dove ogni giocatore $i$ mira a massimizzare un funzionale obiettivo $W_i$ soggetto a un'equazione di dinamica dello stato $\dot{x} = g(x, u_i, u_{-i})$. Gli autori si concentrano su strategie di feedback sullo stato (markoviane), che sono preferite per la loro perfezione nei sottogiochi (consistenza temporale) rispetto agli equilibri a ciclo aperto.

La sfida principale è che gli MNE sono caratterizzati da un sistema di $N$ equazioni di Hamilton-Jacobi-Bellman (HJB) accoppiate. A causa dell'alta non linearità e dimensionalità di queste equazioni, le soluzioni analitiche sono generalmente non disponibili, tranne che per modelli specifici lineari-quadratici o lineari nello stato. Di conseguenza, sono necessari metodi numerici. Il lavoro indaga se le approssimazioni in tempo discreto e completamente discrete (tempo e stato) di questi giochi convergano alla soluzione a tempo continuo e se gli equilibri discreti risultanti servano come approssimazioni valide (specificamente equilibri $\epsilon$-Nash) per il gioco continuo originale.

Metodologia
Gli autori adottano un approccio di discretizzazione semi-Lagrangiana, combinando la discretizzazione temporale della dinamica con una corrispondente discretizzazione del funzionale obiettivo.

1. Approssimazione in Tempo Discreto (Semi-discreta):

   • L'orizzonte temporale continuo è discretizzato con passo temporale $h$.
   • La dinamica dello stato è approssimata utilizzando uno schema di Eulero in avanti: $x_{n+1} = x_n + h g(x_n, u_{i,n}, u_{-i,n})$.
   • Il funzionale obiettivo è approssimato utilizzando la regola del rettangolo con un fattore di sconto discreto $\beta_h = 1 - \rho h$.
   • Gli autori analizzano la convergenza della funzione di valore discreta alla funzione di valore continua e stabiliscono che un Equilibrio di Nash Markoviano del gioco discreto costituisce un equilibrio $\epsilon$-Nash per il gioco continuo.

2. Approssimazione Completamente Discreta (Tempo e Stato):

   • Lo spazio degli stati è discretizzato utilizzando una triangolazione di un poliedro limitato $\Omega$ con dimensione della mesh $k$.
   • Vengono utilizzate funzioni affini a tratti per approssimare le funzioni di valore e le strategie sui nodi della griglia.
   • Viene definito un gioco ausiliario utilizzando operatori di interpolazione ($I_k$) sullo spazio degli stati per gestire la dinamica dello stato discreta.
   • L'analisi si basa sulla definizione di un problema a tempo continuo ausiliario con strategie interpolate per limitare l'errore tra la soluzione completamente discreta e la soluzione continua.

Contributi e Risultati Chiave
Il lavoro fornisce dimostrazioni rigorose di convergenza e stime di errore per gli schemi di discretizzazione proposti:

• Coerenza delle Funzioni di Valore: Gli autori dimostrano che, al tendere del passo temporale $h \to 0$ (e successivamente $k \to 0$ per il caso completamente discreto), le funzioni di valore dei giochi discreti convergono alla funzione di valore del gioco differenziale continuo.
• Proprietà di Equilibrio $\epsilon$-Nash:
  • Teoremi 3 e 6: È dimostrato che per ogni $\epsilon > 0$, esiste un parametro di discretizzazione sufficientemente piccolo ($h$ o $h, k$) tale che l'Equilibrio di Nash Markoviano del gioco discreto sia un equilibrio $\epsilon$-Nash per il gioco continuo. Ciò significa che nessun giocatore può ottenere un guadagno superiore a $\epsilon$ deviando unilateralmente dalla strategia discreta nel contesto continuo.
  • Teoremi 4 e 7: Sotto ipotesi più forti (in particolare riguardo al tasso di sconto $\rho$ rispetto alle costanti di Lipschitz della dinamica e delle funzioni di costo), gli autori derivano limiti di errore espliciti. Dimostrano che l'errore di approssimazione è dell'ordine $O(h)$ per il caso in tempo discreto e $O(h+k)$ per il caso completamente discreto.
• Esperimenti Numerici: I risultati teorici sono validati utilizzando due esempi:
  1. Un gioco di inquinamento transfrontaliero (struttura lineare-quadratica), dove i risultati numerici confermano la convergenza del primo ordine sia per le funzioni di valore che per le strategie.
  2. Un gioco differenziale di tipo Lanchester (non lineare, non quadratico), che dimostra anch'esso la convergenza della funzione di valore e delle strategie al diminuire dei parametri di discretizzazione.

Significato e Affermazioni
Il lavoro afferma di stabilire una base teorica per l'uso di metodi semi-Lagrangiani per risolvere complessi giochi differenziali non cooperativi. Il significato principale risiede nella dimostrazione che gli equilibri discreti computazionalmente gestibili non sono semplici artefatti numerici, ma sono matematicamente garantiti come approssimazioni degli equilibri continui veri con precisione arbitraria.

Gli autori notano che, sebbene le ipotesi richieste per i limiti di errore espliciti (come la condizione $\rho > L$) siano restrittive, sono spesso soddisfatte nelle applicazioni pratiche, in particolare quando la dinamica rimane all'interno di un dominio limitato e positivamente invariante. Il lavoro estende i risultati precedenti sul controllo ottimo a singolo giocatore all'ambito dei giochi a più giocatori, dimostrando che l'approccio semi-Lagrangiano rimane robusto quando sono presenti interazioni strategiche. Il lavoro conclude che questi metodi forniscono una via praticabile per il calcolo degli equilibri di Nash markoviani in modelli in cui le soluzioni analitiche sono impossibili.