Strategy Machines and their Complexity


Marcus Gelderie (Informatik 7)

Title Strategy Machines and their Complexity
When 08.02.2012, 10:00
Where Room 5052
Abstract The classical objects of study in game theory are Mealy machine strategies. These machines present a global view on the strategy in the sense that they comprise information about all possible configurations of the strategy at once. This information is stored in the control states. The number of those states is the key optimization criterion. In contrast to this global perspective is the local perspective of a Turing machine implementing a winning strategy. Here the focus is on the computation of the next output based on the current configuration of the machine. The optimization criteria differ. Now we can define the latency of such a machine, its space requirement and its size. We define a model, called a strategy machine, of such controllers. We show how this model allows us to measure the quantities mentioned above. In addition we give lower and upper bounds for several classes of games.