Strategy complexity of two-player, zero-sum games
Rasmus Ibsen-Jensen · 2013
This dissertation considers two-player, zero-sum games with a focus on how complicated they are to play; a notion I will call strategy complexity. Often, knowing good bounds on the strategy complexity indicates bounds on the run time of various algorithms. In such cases I will also derive bounds on the algorithms. I consider a wide assortment of different two-player, zero-sum game classes, e.g. matrix games, uni-chain concurrent mean-payoff games, concurrent mean-payoff games, concurrent reachability games and one-clock priced timed games. In all game classes considered, except for one-clock priced timed games and concurrent mean-payoff games, I will use the notion of patience as a measure of how complicated a game is to play. I do so since a “good” strategy in those game classes can take the form of probability distributions over some set of choices. The patience is then 1=p, where p is the smallest non-zero probability used in one of the probability distributions. In each case I provide relatively tight bounds on the patience of the “good” strategy that requires the least patience in the worst game of the game class. I will give an improved bound on the patience of concurrent reachability games, which show that they require double exponential much patience. I use this to show that two classic algorithms for concurrent reachability games run slowly. I will also present an exponential (both upper and lower) bound on patience for uni-chain concurrent mean-payoff games and for matrix games. The bound on uni-chain concurrent mean-payoff games implies a new, faster algorithm for solving such games. The bound on matrix games does not imply any new bounds on algorithms, since they can already be solved in polynomial time. In one-clock priced timed games I do not consider patience, since the strategies do not use probabilities. Instead I consider how much space is necessary to write down a “good” strategy. In this case I show that a good strategy can be written down in an exponential amount of space, in the size of the game. I also give an algorithm that pretty much runs in that much time and finds such a strategy In concurrent mean-payoff games I do not consider patience either, since as I will argue, in the worst case, the patience is infinite. Thus, instead I consider how much memory is necessary to play well after having played the game for some time. For the specific and quite well-studied concurrent mean-payoff game, the Big Match, I show on one hand that the memory usage must grow unbounded and on the other hand I give a family of strategies for which the memory usage grows arbitrarily slowly (but unbounded). Furthermore, I show that for concurrent mean-payoff games and states in such games which have value equal to the greatest reward, if an optimal strategy exists, then it is a so-called Markov strategy. If a finite-memory near-optimal strategy exists, then there exists one that uses no memory and have double exponential patience (this also gives a bound on the subclass of concurrent reachability games in which state have value 0 or 1). In each of the two cases I show these statements by giving a polynomial time algorithm that finds such states (that is, I give (1) a polynomial time algorithm that finds states which have value equal to the greatest reward and in which an optimal strategy exists; and (2) a polynomial time algorithm that finds states which have value equal to the greatest reward and in which a finite-memory near optimal strategy exists).