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.