2012/01/17 by Thomas Dueholm Hansen, Hansen, Thomas Dueholm, Rasmus Ibsen-Jensen +3
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computational Geometry (cs.CG) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1201.3498
openalex publication_date 2012/01/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
One-clock priced timed games is a class of two-player, zero-sum, continuous-time games that was defined and thoroughly studied in previous works. We show that one-clock priced timed games can be solved in time m 12n n^(O(1)), where n is the number of states and m is the number of actions. The best previously known time bound for solving one-clock priced timed games was 2^(O(n2+m)), due to Rutkowski. For our improvement, we introduce and study a new algorithm for solving one-clock priced timed games, based on the sweep-line technique from computational geometry and the strategy iteration paradigm from the algorithmic theory of Markov decision processes. As a corollary, we also improve the analysis of previous algorithms due to Bouyer, Cassez, Fleury, and Larsen; and Alur, Bernadsky, and Madhusudan.