Playing games when states have rich structure
Abstract.
Both in the classical theory of extensive-form games and in the more
recent theory of games on graphs, it is normally assumed that a state
of the game has no structure beyond the outgoing moves. In other words,
the internal structure of the states is abstracted away. This is very useful
in some cases, but can be a hindrance in others, for example when studying
games on pushdown graphs or on timed automata.
Towards a better understanding on how internal structure of the states can
influence behaviour of the players, we introduce a general model of games
with structured states. In our model, actions of the players are given by
structure rewriting rules and winning conditions by logic formulas. In case
of games with perfect information, we show that the structure of the states
can be exploited to create simple strategies, sometimes even when the number
of states in the game is infinite. A similar phenomenon arises in games on
pushdown graphs and we prove a close relationship between pushdown games
and our model when rewriting rules are of a certain simple form. For games
with incomplete information, we give a few examples of how the structure of
the states can influence the play and players' beliefs in much more
intricate ways.
To understand how such complex games can be played rationally at all, we
reach
to game playing algorithms and conclude with a presentation of one of them.
Relevant Papers.