A Dijkstra-Type Algorithm for Dynamic Games

Martino Bardi () and Juan Pablo Maldonado López ()
Additional contact information
Martino Bardi: Università degli Studi di Padova
Juan Pablo Maldonado López: Sorbonne Universités

Dynamic Games and Applications, 2016, vol. 6, issue 3, No 1, 263-276

Abstract: Abstract We study zero-sum dynamic games with deterministic transitions and alternating moves of the players. Player 1 aims at reaching a terminal set and minimizing a possibly discounted running and final cost. We propose and analyze an algorithm that computes the value function of these games extending Dijkstra’s algorithm for shortest paths on graphs. We also show the connection of these games with numerical schemes for differential games of pursuit-evasion type, if the grid is adapted to the dynamical system. Under suitable conditions, we prove the convergence of the value of the discrete game to the value of the differential game as the step of approximation tends to zero.

Keywords: Zero sum dynamic games; Dijkstra algorithm; Pursuit evasion games; Discrete time games; 91A25; 65Kxx; 49N70; 91A23; 91A24; 49N75 (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s13235-015-0156-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:dyngam:v:6:y:2016:i:3:d:10.1007_s13235-015-0156-0

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/13235

DOI: 10.1007/s13235-015-0156-0

Access Statistics for this article

Dynamic Games and Applications is currently edited by Georges Zaccour

More articles in Dynamic Games and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().