Strategy complexity of concurrent games

Rasmus Ibsen-Jensen

Abstract

The talk will be on how complicated good strategies (ways of playing) for concurrent games can/must be.  The measure of complication chosen will try to describe how much space a good strategy will use.

The talk will first consider matrix games/normal form games, which are games like rock-paper-scissors, and then move on to concurrent games, which in essence consists of playing a matrix game but where the outcome picks the next matrix to play (repeated infinitely many times), which can model games with no prior upper bound on number of steps, like poker.

For much of the talk, the games will have good strategies that takes the form of probability distributions over a finite set of choices and will for such use the measure of strategy complexity will be patience and roundedness, which is 1/smallest positive pr. and greatest denominator resp. The talk will end with concurrent mean-payoff games where unbounded space is