Abstract: |
Infinite path-forming games stand as an important paradigm at the
interface between logic and computer science. Typically, they arise as
natural models for computations of reactive systems and provide
semantics for modal logics, which, in turn, are appropriate to
describe such systems.
Specifically, this framework relies on two player zero-sum games for
which the theory of omega automata supplies a solid algorithmic
basis. However, when modelling interaction among many agents, the
zero-sum assumption becomes rather inappropriate. This brings into
play new notions of rationality.
In our presentation, we consider a generalisation of path-forming
games to a multiplayer, not necessarily competitive, setting, and
propose some elementary solution concepts related to the notion of
dominance. For games on unravellings of finite graphs, we show that
equilibria obtained through iterated elimination of dominated
strategies can be algorithmically captured in terms of omega-automata.
|