LIPIcs.CSL.2016.30.pdf
- Filesize: 0.61 MB
- 17 pages
Document
Minimizing Regret in Discounted-Sum Games
Authors
-
Part of:
Volume:
25th EACSL Annual Conference on Computer Science Logic (CSL 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Computer Science Logic (CSL) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-08-29
Cite AsGet BibTex
Paul Hunter, Guillermo A. Pérez, and Jean-François Raskin. Minimizing Regret in Discounted-Sum Games. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.CSL.2016.30
https://doi.org/10.4230/LIPIcs.CSL.2016.30
Abstract
In this paper, we study the problem of minimizing regret in discounted-sum games played on weighted game graphs. We give algorithms for the general problem of computing the minimal regret of the controller (Eve) as well as several variants depending on which strategies the environment (Adam) is permitted to use. We also consider the problem of synthesizing regret-free strategies for Eve in each of these scenarios.
Keywords
- Quantitative games
- Regret
- Verification
- Synthesis
- Game theory
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Benjamin Aminof, Orna Kupferman, and Robby Lampert. Reasoning about online algorithms with weighted automata. ACM Transactions on Algorithms, 2010. URL: http://dx.doi.org/10.1145/1721837.1721844.
-
Krzysztof R. Apt and Erich Grädel. Lectures in game theory for computer scientists. Cambridge University Press, 2011.
- David E. Bell. Regret in decision making under uncertainty. Operations Research, 30(5):961-981, 1982. URL: http://dx.doi.org/10.1287/opre.30.5.961.
- Udi Boker and Thomas A. Henzinger. Exact and approximate determinization of discounted-sum automata. LMCS, 10(1), 2014. URL: http://dx.doi.org/10.2168/LMCS-10(1:10)2014.
- Ashok K. Chandra, Dexter Kozen, and Larry J. Stockmeyer. Alternation. J. ACM, 28(1):114-133, 1981. URL: http://dx.doi.org/10.1145/322234.322243.
- Krishnendu Chatterjee, Laurent Doyen, and Thomas A. Henzinger. Quantitative languages. ACM Transactions on Computational Logic, 11(4), 2010. URL: http://dx.doi.org/10.1145/1805950.1805953.
- Werner Damm and Bernd Finkbeiner. Does it pay to extend the perimeter of a world model? In FM, volume 6664 of LNCS, pages 12-26. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-21437-0_4.
-
Emmanuel Filiot, Tristan Le Gall, and Jean-François Raskin. Iterated regret minimization in game graphs. In MFCS, volume 6281 of LNCS, pages 342-354. Springer, 2010.
-
Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.
- Thomas A. Henzinger and Nir Piterman. Solving games without determinization. In CSL, pages 395-410, 2006. URL: http://dx.doi.org/10.1007/11874683_26.
- Paul Hunter, Guillermo A. Pérez, and Jean-François Raskin. Mean-payoff games with partial-observation - (extended abstract). In RP, pages 163-175, 2014. URL: http://dx.doi.org/10.1007/978-3-319-11439-2_13.
- Paul Hunter, Guillermo A. Pérez, and Jean-François Raskin. Minimizing regret in discounted-sum games. CoRR, abs/1511.00523, 2015. URL: http://arxiv.org/abs/1511.00523.
-
Paul Hunter, Guillermo A Pérez, and Jean-François Raskin. Reactive synthesis without regret. Acta Informatica, pages 1-37, 2015.
-
Daniel Dominic Sleator and Robert Endre Tarjan. Amortized efficiency of list update rules. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA, pages 488-492. ACM, 1984.
-
Uri Zwick and Mike Paterson. The complexity of mean payoff games on graphs. TCS, 158(1):343-359, 1996.