Entropy Games and Matrix Multiplication Games
arXiv:1506.04885
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\&coNP.
Accepted to STACS 2016
Cited by in corpus (7)
- The operator approach to entropy games
- Log-sum-exp neural networks and posynomial models for convex and log-log-convex data
- Hourglass alternative and the finiteness conjecture for the spectral characteristics of sets of non-negative matrices
- Minimax joint spectral radius and stabilizability of discrete-time linear switching control systems
- Spectral inequalities for nonnegative tensors and their tropical analogues
- Minimax theorem for the spectral radius of the product of non-negative matrices
- On convergence of infinite matrix products with alternating factors from two sets of matrices