LIPIcs.STACS.2016.11.pdf
- Filesize: 0.69 MB
- 14 pages
Document
Entropy Games and Matrix Multiplication Games
Authors
-
Part of:
Volume:
33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-02-16
Cite As Get BibTex
Eugene Asarin, Julien Cervelle, Aldric Degorre, Catalin Dima, Florian Horn, and Victor Kozyakin. Entropy Games and Matrix Multiplication Games. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.STACS.2016.11
Abstract
Two intimately related new classes of games are introduced and studied: entropy games (EGs) and matrix multiplication games (MMGs). An EG is played on a finite arena by two-and-a-half players: Despot, Tribune and the non-deterministic People. Despot wants to make the set of possible People's behaviors as small as possible, while Tribune wants to make it as large as possible. An MMG is played by two players that alternately write matrices from some predefined finite sets. One wants to maximize the growth rate of the product, and the other to minimize it. We show that in general MMGs are undecidable in quite a strong sense. On the positive side, EGs correspond to a subclass of MMGs, and we prove that such MMGs and EGs are determined, and that the optimal strategies are simple. The complexity of solving such games is in NP cap coNP.
Subject Classification
Keywords
- game theory
- entropy
- joint spectral radius
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Eugene Asarin, Nicolas Basset, and Aldric Degorre. Entropy of regular timed languages. Inform. Comput., 241:142-176, 2015. URL: http://dx.doi.org/10.1016/j.ic.2015.03.003.
- Eugene Asarin, Michel Blockelet, Aldric Degorre, Cătălin Dima, and Chunyan Mu. Asymptotic behaviour in temporal logic. In Proc. CSL-LICS, pages 10:1-10:9. ACM, 2014. URL: http://dx.doi.org/10.1145/2603088.2603158.
- Eugene Asarin, Julien Cervelle, Aldric Degorre, Cătălin Dima, Florian Horn, and Victor Kozyakin. Entropy Games and Matrix Multiplication Games. https://hal.archives-ouvertes.fr/hal-01164086, 2015.
- Marc A. Berger and Yang Wang. Bounded semigroups of matrices. Linear Algebra Appl., 166:21-27, 1992. URL: http://dx.doi.org/10.1016/0024-3795(92)90267-E.
- Vincent D. Blondel and Yurii Nesterov. Polynomial-time computation of the joint spectral radius for some sets of nonnegative matrices. SIAM J. Matrix Anal. A., 31(3):865-876, 2009. URL: http://dx.doi.org/10.1137/080723764.
- Vincent D. Blondel and John N. Tsitsiklis. The boundedness of all products of a pair of matrices is undecidable. Syst. Control Lett., 41(2):135-140, 2000. URL: http://dx.doi.org/10.1016/S0167-6911(00)00049-9.
- Noam Chomsky and George A. Miller. Finite state languages. Inform. Control, 1(2):91-112, 1958. URL: http://dx.doi.org/10.1016/S0019-9958(58)90082-2.
- Adam Czornik. On the generalized spectral subradius. Linear Algebra Appl., 407:242-248, 2005. URL: http://dx.doi.org/10.1016/j.laa.2005.05.006.
- Ingrid Daubechies and Jeffrey C. Lagarias. Sets of matrices all infinite products of which converge. Linear Algebra Appl., 161:227-263, 1992. URL: http://dx.doi.org/10.1016/0024-3795(92)90012-Y.
- Ingrid Daubechies and Jeffrey C. Lagarias. Corrigendum/addendum to [9]. Linear Algebra Appl., 327(1-3):69-83, 2001. URL: http://dx.doi.org/10.1016/S0024-3795(00)00314-1.
- Aldric Degorre, Laurent Doyen, Raffaella Gentilini, Jean-François Raskin, and Szymon Torunczyk. Energy and mean-payoff games with imperfect information. In Proc. CSL, LNCS 6247, pages 260-274. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-15205-4_22.
-
Andrzej Ehrenfeucht and Jan Mycielski. Positional strategies for mean payoff games. International Journal of Game Theory, 8(2):109-113, 1979.
- Leonid Gurvits. Stability of discrete linear inclusion. Linear Algebra Appl., 231:47-85, 1995. URL: http://dx.doi.org/10.1016/0024-3795(95)90006-3.
-
Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, 2013.
- Raphaël Jungers. The Joint Spectral Radius: Theory and Applications. LNCIS 385. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-540-95980-9.
- Victor Kozyakin. An annotated bibliography on convergence of matrix products and the theory of joint/generalized spectral radius. Preprint, Institute for Information Transmission Problems, Moscow, 2013. URL: http://dx.doi.org/10.13140/2.1.4257.5040.
- Yurii Nesterov and Vladimir Yu. Protasov. Optimizing the spectral radius. SIAM J. Matrix Anal. A., 34(3):999-1013, 2013. URL: http://dx.doi.org/10.1137/110850967.
- Vladimir Yu. Protasov. Spectral simplex method. Math. Program., pages 1-27, 2015. URL: http://dx.doi.org/10.1007/s10107-015-0905-2.
-
Gian-Carlo Rota and Gilbert Strang. A note on the joint spectral radius. Nederl. Akad. Wetensch. Proc. Ser. A 63 = Indag. Math., 22:379-381, 1960.
-
Ludwig Staiger. Entropy of finite-state omega-languages. Probl. Control Inform., 14(5):383-392, 1985.
-
Jacques Theys. Joint Spectral Radius: Theory and Approximations. PhD thesis, Université Catholique de Louvain, 2005.
- John N. Tsitsiklis and Vincent D. Blondel. The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate. Math. Control Signals Systems, 10(1):31-40, 1997. URL: http://dx.doi.org/10.1007/BF01219774.
-
John von Neumann and Oskar Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, 1947.
-
Klaus Weihrauch. Computable Analysis. Springer, 2000.
- Uri Zwick and Mike Paterson. The complexity of mean payoff games on graphs. Theor. Comput. Sci., 158(1-2):343-359, 1996. URL: http://dx.doi.org/http://dx.doi.org/10.1016/0304-3975(95)00188-3.