12 December 2001, Workshop on Games and Logic

Program

Abstracts

Marc Pauly - In praise of ignorance and individualism

Coalitional power in multistage processes is modeled using effectivity frames, which are general enough to capture what groups of agents can bring about in extensive games of perfect and almost perfect information. Coalition Logic is used to describe effectivity frames, and the question of generating a mechanism satisfying a given specification is formulated as a satisfiability problem in Coalition Logic. Using this logical reformulation, we show that the complexity of this implementation problem depends (a) on whether the mechanism to be generated allows for imperfect information, and (b) on whether we are interested in individual or group ability.

Johan van Benthem - Games over Time

We propose a model for infinite extensive games in a branching temporal logic, assessing its merits for analyzing game-theoretic reasoning. The model also supports expectations and uncertainty.

Peter van Emde Boas - Imperfect Information Games; looking for the right model

The theory relating the endgame analysis of "reasonable games" with the complexity class PSPACE, which was developed 25 years ago breakes down for imperfect information games. The forthcoming InIGMA project which will start in 2002 is an attempt to extend the existing theory to include imperfect information games as well.

In the talk I will indicate the few results available in the literature, what we know about this problem, and how we hope to solve it.

Rohit Parikh - Levels of Knowledge in Distributed Computing (joint work with Pawel Krasucki)

When a group of people know some proposition, it can be known at various level. The highest level is when it is common knowledge. The lowest when it is true but known to no one. We show that there are exactly coutably many possible levels of knowledge which are regular sets of strings on the obvious alphabet and show how different kinds of protocols can be used to achieve these levels.

Joe Halpern - A Computer Scientist Looks at Game Theory

I consider issues in distributed computation that should be of relevance to game theory. In particular, I focus on (a) representing knowledge and uncertainty, (b) dealing with failures, and (c) specification of mechanisms.

Valentin Goranko: - Completeness of Extended Coalition Logics

I will discuss a variety of extended coalition logics, some of which were introduced in Marc Pauly's disertation. They can be regarded as multi-modal versions of fragments of CTL, with modalities indexed by subsets (coalitions) of a set of players, and neighbourhood, rather than Kripke, semantics. I will present axiomatizations for these logics and will outline proofs of finite model property and completeness. The proof methods are adaptation of the well-known canonical model and filtration methods, but it is reassuring that the old techniques still work here.

For more information, please contact Paul Harrenstein (paulh at cs.uu.nl).