July 19 (Tuesday), 1600, IITP RAS, room 307
Eugene Asarin (IITP, Universite Paris-Diderot)
Entropy games
An entropy game is played on a finite arena by two-and-a-half players: Despot, Tribune and non-deterministic People. Whenever Despot and Tribune decide on their actions, it leaves a set L of possible behaviors of People. Despot wants the entropy (growth rate) of L to be as small as possible, while Tribune wants to make it as large as possible. The main result is that the entropy game is determined, and that the optimal strategies for Despot and Tribune are positional. The analysis is based on that of matrix multiplication games, which are novel and generalizing the theory of joint spectral radius. Complexity and decidability issues are also addressed.
Joint work with Julien Cervelle, Aldric Degorre, Catalin Dima, Florian Horn and Victor Kozyakin.
| 16.07.2016 | |