Speaker |
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. |
Slides |
Event calendar
- Subscribe to the ics feed.
Upcoming Events
- No Events