Papers for

automated scheduling teams

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Value of time-bounded weighted timed games can be approximated in high complexity

Approximating the Value of Time-Bounded Weighted Timed Games

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.

Thu 15 OctComputer Science and Game Theory

The gist

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.

Open → 2610.21487v1