Computer Laboratory Home Page Search A-Z Directory Help
University of Cambridge Home Logic and Semantics Seminar
29th October 2004: Dietmar Berwanger
Computer Laboratory > Research > TSG > Logic and Semantics Seminar > 29th October 2004: Dietmar Berwanger

Speaker: Dietmar Berwanger, RWTH Aachen
Title: Hope and Trust in Infinite Games
Time: 29th October 2004, 14:00
Venue: William Gates Building, room FW11
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.