Value of time-bounded weighted timed games can be approximated in high complexity
Approximating the Value of Time-Bounded Weighted Timed Games
Computer Science and Game Theory
Summary
Weighted timed games are mathematical models used to decide the best moves in situations with time and cost constraints, but exactly finding their best value is impossible with today’s algorithms. The authors show that while exact solutions can't be computed, approximations become possible when the game has a fixed time limit. They prove that this approximation can be done, although it may require a very large amount of computing effort. This result opens the door to understanding these games better under time restrictions.
What this means in practice
- •For real-time system designers: Determine approximate optimal strategies in real-time systems with strict time limits by using the time-bound approximability result.
- •For automated scheduling teams: Use decidable approximate values to improve automated scheduling models constrained by both time and cost.
A theory result. No direct application yet.
Authors
Isa Vialard, Joël Ouaknine
Abstract
The Value Problem for weighted timed games, an extension of timed automata with weights and adversity, consists in determining, given a weighted timed game with a reachability objective and a rational threshold, whether or not the value of the game exceeds the threshold. This problem is known to be undecidable for weighted timed games, i.e., there is no algorithm that can compute the value exactly. A natural alternative is to approximate the value; however, the Approximation problem is also undecidable in general. In this paper, we prove that the Approximation problem is decidable in 4-ExpTime for weighted timed games whose executions are time-bounded.