Room 327
Complexity Measures for Distributed Games
Dietmar Berwanger
CNRS, ENS Paris-Saclay
Strategic coordination is a key task in distributed computing
an in infinitely repeated games. Intriguingly, this task cannot be solved algorithmically in general, and we have little understanding of the particular classes where it is solvable.
In this talk, I will describe some entropy-like parameters that measure how close a coordination game is from a being a regular zero-sum game. This yields a parametrised reduction to one-player decision problems representable and solvable with automata.
Done