On Discrete-Time Approximations to Infinite Horizon Differential Games

Technische Samenvatting: Discrete Benaderingen voor Differentiële Spelen met Oneindige Horizont

Probleemstelling
Het artikel behandelt de numerieke benadering van Markoviaanse Nash-evenwichten (MNE) in niet-coöperatieve differentieerspelen met $N$ spelers en een oneindige horizont. In dergelijke spelen interageren $N$ spelers strategisch in de tijd, waarbij elke speler $i$ streeft naar het maximaliseren van een objectieve functionaal $W_i$, onderworpen aan een toestandsdynamische vergelijking $\dot{x} = g(x, u_i, u_{-i})$. De auteurs richten zich op strategieën met toestandsfeedback (Markoviaans), die de voorkeur genieten vanwege hun subgame-perfectheid (tijdconsistentie) in vergelijking met open-loop-evenwichten.

De kernuitdaging is dat MNE's worden gekenmerkt door een stelsel van $N$ gekoppelde Hamilton-Jacobi-Bellman (HJB)-vergelijkingen. Vanwege de hoge niet-lineariteit en dimensionaliteit van deze vergelijkingen zijn analytische oplossingen over het algemeen niet beschikbaar, behalve voor specifieke lineair-kwadratische of lineaire-toestandsmodellen. Bijgevolg zijn numerieke methoden vereist. Het artikel onderzoekt of discrete-tijd- en volledig discrete (tijd en toestand) benaderingen van deze spelen convergeren naar de oplossing in continue tijd, en of de resulterende discrete evenwichten geldige benaderingen vormen (specifiek $\epsilon$-Nash-evenwichten) voor het oorspronkelijke continue spel.

Methodologie
De auteurs maken gebruik van een semi-Lagrangiaanse discretisatiebenadering, waarbij de discretisatie in de tijd van de dynamiek wordt gecombineerd met een overeenkomstige discretisatie van de objectieve functionaal.

1. Discrete-tijdbenadering (Semi-discreet):

   • De continue tijds horizon wordt gediscretiseerd met stapgrootte $h$.
   • De toestandsdynamiek wordt benaderd met een voorwaartse Euler-scheme: $x_{n+1} = x_n + h g(x_n, u_{i,n}, u_{-i,n})$.
   • De objectieve functionaal wordt benaderd met de rechthoekenregel, met een discrete disconteringsfactor $\beta_h = 1 - \rho h$.
   • De auteurs analyseren de convergentie van de discrete waardenfunctie naar de continue waardenfunctie en stellen vast dat een Markoviaans Nash-evenwicht van het discrete spel een $\epsilon$-Nash-evenwicht vormt voor het continue spel.

2. Volledig discrete benadering (Tijd en Toestand):

   • De toestandsruimte wordt gediscretiseerd met behulp van een triangulatie van een begrensd polyeder $\Omega$ met meshgrootte $k$.
   • Stuksgewijs affiene functies worden gebruikt om de waardenfuncties en strategieën op de gridknopen te benaderen.
   • Een hulpspel wordt gedefinieerd met behulp van interpolatie-operatoren ($I_k$) op de toestandsruimte om de discrete toestandsdynamiek te behandelen.
   • De analyse berust op het definiëren van een hulp-probleem in continue tijd met geïnterpoleerde strategieën om de fout tussen de volledig discrete oplossing en de continue oplossing te begrenzen.

Belangrijkste Bijdragen en Resultaten
Het artikel biedt rigoureuze convergentiebewijzen en foutschattingsformules voor de voorgestelde discretisatieschema's:

• Consistentie van Waardenfuncties: De auteurs bewijzen dat, naarmate de tijdstap $h \to 0$ (en vervolgens $k \to 0$ voor het volledig discrete geval), de waardenfuncties van de discrete spelen convergeren naar de waardenfunctie van het continue differentieel spel.
• $\epsilon$-Nash-evenwicht Eigenschap:
  • Stelling 3 & 6: Er wordt bewezen dat voor elke $\epsilon > 0$ er een voldoende kleine discretisatieparameter ($h$ of $h, k$) bestaat, zodat het Markoviaanse Nash-evenwicht van het discrete spel een $\epsilon$-Nash-evenwicht is voor het continue spel. Dit betekent dat geen enkele speler meer dan $\epsilon$ kan winnen door eenzijdig af te wijken van de discrete strategie in de continue setting.
  • Stelling 4 & 7: Onder sterkere hypothesen (specifiek met betrekking tot de disconteringsfactor $\rho$ ten opzichte van de Lipschitz-constanten van de dynamiek en kostenfuncties) leiden de auteurs expliciete foutgrenzen af. Zij tonen aan dat de benaderingsfout van orde $O(h)$ is voor het discrete-tijdgeval en van orde $O(h+k)$ voor het volledig discrete geval.
• Numerieke Experimenten: De theoretische resultaten worden gevalideerd met twee voorbeelden:
  1. Een grensoverschrijdend vervuilingspel (lineair-kwadratische structuur), waarbij de numerieke resultaten eerste-orde convergentie bevestigen voor zowel waardenfuncties als strategieën.
  2. Een Lanchester-type differentieel spel (niet-lineair, niet-kwadratisch), dat eveneens convergentie van de waardenfunctie en strategieën aantoont naarmate de discretisatieparameters afnemen.

Betekenis en Claims
Het artikel claimt een theoretische fundering te leggen voor het gebruik van semi-Lagrangiaanse methoden om complexe niet-coöperatieve differentieerspelen op te lossen. De primaire betekenis ligt in het bewijzen dat de computatieel hanteerbare discrete evenwichten niet louter numerieke artefacten zijn, maar wiskundig gegarandeerd de ware evenwichten in continue tijd benaderen met willekeurige precisie.

De auteurs merken op dat, hoewel de hypothesen die vereist zijn voor de expliciete foutgrenzen (zoals de voorwaarde $\rho > L$) restrictief zijn, deze vaak worden voldaan in praktische toepassingen, met name wanneer de dynamiek binnen een begrensd, positief invariant domein blijft. Het werk breidt eerdere resultaten over optimale controle voor één speler uit naar de setting van spellen met meerdere spelers, en toont aan dat de semi-Lagrangiaanse aanpak robuust blijft wanneer strategische interacties aanwezig zijn. Het artikel concludeert dat deze methoden een levensvatbare weg bieden voor het berekenen van Markoviaanse Nash-evenwichten in modellen waar analytische oplossingen onmogelijk zijn.