Seventh Workshop on Games in Logic, Languages & Computation

Games in Logic, Language and Computation

Thursday November 28, 2002

Euclides Building, Room P.017
Plantage Muidergracht 24, Amsterdam

Last Update : 2002/11/29

The seventh edition of the workshop on Games in Logic, Language and Computation (GLLC7) will be held on Thursday November 28, 2002. The workshop is organized by the research group Logic, Games and Computation and is hosted by the Institute for Logic, Language and Computation. For any further information, email Sjoerd Druiven or Merlijn Sevenster.

The informal workshop series "Games in Logic, Language and Computation" focuses on the application of game theory in linguistics, logic and computer science, as well as on the (logical) foundations of game theory. Earlier meetings have taken place in Utrecht, Amsterdam, Nunspeet and Groningen.

The workshop is open to all interested.

Evert Willem Beth Stichting
10:30 - 11:15 Balder ten Cate Natural deduction for epistemic actions
11:15 - 12:00 Denis Bonnay Independence, games and proofs
12:00 - 13:30 Lunch
13:30 - 14:10 Marc Pauly Programming and Verifying Subgame Perfect Mechanisms
14:10 - 14:50 Manuel Rebuschi 'Slashing' Dynamic Logics
14:50 - 15:30 Mikaël Cozic Logical Monotony and Bounded Rationality
15:30 - 16:00 Coffee & Cake
16:00 - 16:40 Ian Hodkinson Games in relation algebras
16:40 - 17:20 Tero Tulenheimo IF Modal Logic and its Expressive Power
17:20 - 18:00 Alexandru Baltag Reasoning about Epistemic Programs
18:00 - Drinks

The abstracts are at the end of this page, or follow this link.

Previous GLLC's
GLLC 6 June 20 2002, Utrecht, NL
GLLC 5 December 12 2001, Amsterdam, NL
GLLC 4 November 21 2000, Groningen, NL.
GLLC 3 October 26 2000, Nunspeet, NL
GLLC 2 June 23 2000, Amsterdam, NL
GLLC/ILLC Workshop on Logic and Games November 19-20 1999, Amsterdam, NL
Researchgroup Logic, Games and Computation
Institute for Logic, Language and Computation
University of Amsterdam
Titles and Abstracts.
Alexandru Baltag (Oxford University)
Reasoning about Epistemic Programs

Epistemic programs are programs for jointly updating all the agents' states of knowledge (or "belief") in a distributed system. They can be intuitively understood as computing the effect of exchanges of information ("communication") between agents. Such programs are recursively built from basic epistemic actions (e.g. public broadcasting, or various more "opaque" forms of communication), using standard program constructors. I introduce a (complete and decidable) Hoare logic for epistemic programs, which can be used to reason about informational changes, and in particular to prove the partial correctness of communication strategies with respect to given epistemic goals (and given epistemic preconditions). I apply this to some well-known epistemic games and puzzles. Finally, I present an extension of the Hoare logic to a much more expressive dynamic logic of epistemic programs, which turns out to be undecidable, although still useful in some contexts.

Denis Bonnay (University Paris I)
Independence, games and proofs

The claim that IF logic is the classical logic is grounded in the idea that, once one has adopted a game semantics, this liberalisation is very natural, corresponding to the shift from perfect to imperfect information games. But one could as well use Henkin quantifiers to give a recursive semantic for independence, so that the question cannot be settled on the level of pure expressivity, and arguments are likely to boil down to the fact that IF approach is more natural, elegant, or intuitive. We would like to give some precise content to this feeling. Namely, we will discuss three points : the claim of generality, the idea that IF gives a true analysis of independence, the links between truth-seeking and truth-establishing games. We will make thus some technical points about the use of slash, links with modal logic, and connections with classical proof theory.

Balder ten Cate (ILLC, University of Amsterdam)
Natural deduction for epistemic actions

This talk is about epistemic effects of actions such as public announcements (e.g., X shows his cards to everybody), private communication (e.g., X shows his cards to Y without Z noticing anything), semi-private communication (e.g., X shows his cards to Y in Z's presence; Z cannot see which cards are shown). Baltag, Moss and Solecki have proposed a convincing framework for reasoning about such "epistemic actions".

We will discuss a natural deduction calculus for reasoning about epistemic actions, based on hybrid logic. Hybrid logic is an extension of modal logic with nominals. These are special proposition letters that are true at exactly one world. Hybrid logic offers various advantages over orthodox modal logic, including nice proof systems.

Mikaël Cozic (University of Paris IV-Sorbonne)
Logical Monotony and Bounded Rationality
The starting point of my talk is the problem of logical omniscience and other similar idealizations that one can find in epistemic and doxastic models like epistemic logic, probability theory or belief revision; I call the existence of such idealizations the phenomenon of logical monotony. One disputed question is whether or not logical monotony is an innocuous idealization; I will argue that the weakening of logical monotony is relevant in the case of rational choice theory; and that such a weakening is nothing else that a fundamental aspect of the research program known as "bounded rationality", which goes back to the work of H.Simon in the fifties and is very dynamic today. I call this methodological thesis the pragmatic relevance of logical monotony. But once the pragmatic relevance of logical monotony is accepted, the main question is: what could and what should we expect from a weakening of logical standards ? I won't give any general answer to this question, but in the second part of my talk, I would like to give some insight into different ways of fulfilling this program by considering two examples in game theory: the Bayesian-cognitive justification of solution concept, as pioneered by Tan & Werlang, and the game-theoretic justification of cooperation in Repeated Prisoner's Dilemma and the introduction of finite automata to reach the cooperation's payoff.

Extended abstract

Ian Hodkinson (Imperial College London)
Games in relation algebras

It is an old problem of Henkin, Monk, and Tarski to find a `simple intrinsic characterisation' of the `representable' algebras of relations.

Games have been found useful in constructing representations of relation algebras The ideas go back to Lyndon's work in the 1950s, but the presentation can arguably be made more transparent by using games. First-order axioms characterising representability can be extracted from the process; but I claim that the games themselves form a simple, intrinsic characterisation of representability. This claim is strengthened by the fact that one may go on to use games to analyse relation algebras in some detail, and prove many hierarchy results.

Marc Pauly (University of Liverpool)
Programming and Verifying Subgame Perfect Mechanisms

An extension of the WHILE-language is developed for programming game-theoretic mechanisms involving multiple agents. Examples of such mechanisms include auctions, voting procedures, and negotiation protocols. A structured operational semantics is provided in terms of extensive games of almost perfect information. Hoare-style partial correctness assertions are proposed to reason about the correctness of these mechanisms, where correctness is interpreted as the existence of a subgame perfect equilibrium. Using an extensional approach to pre- and postconditions, we show that an extension of Hoare's original calculus is sound and complete for reasoning about subgame perfect equilibria in game-theoretic mechanisms.

Manuel Rebuschi (Université Nancy 2)
'Slashing' Dynamic Logics

Thanks to Hintikka's slash notation, informational independence can be imported into various logics and especially into dynamic languages. A natural interpretation of the resulting IF dynamic logics is then provided by usual evaluation games. We will consider two IF extensions of dynamic logics:

  1. Van Benthem's Epistemic Action Logic;
  2. Groenendijk and Stokhof's Dynamic Predicate Logic.
Both logics can account for the semantics of IF first-order languages. Their account is undoubtedly unusual, but it is still a game-theoretical one.
Tero Tulenheimo (University of Helsinki)
IF Modal Logic and its Expressive Power

The aims of my talk are:

  1. to define a language IFML[k] for IF modal logic interpreted in terms of k accessibility relations;
  2. to provide a game-theoretical interpretation to it, where the independence-indicator essentially becomes a device for forming 'information sets' on which the relevant player's winning strategies need be uniform;
  3. to compare the expressive power of IFML[k] with that of the corresponding basic modallogic ML[k].

Results are obtained already with one accessibility relation, k := 1. We show that for arbitrary unary modal structures, IFML is strictly more expressive than ML. On the other hand, over unary modal structures with arbitrary linear frames, the expressive powers of IFML and ML indeed coincide. The same holds even for the corresponding temporal logics (with operators capable of speaking both of the accessibility relation and its converse), provided that there be operators available in the respective languages that can speak of immediate successors and immediate predecessors.

When a question arises as to the translatability of IF modal logic to first-order logic, the answer is that not only can the language IFML[k] considered here be translated to IF first-order logic, but in fact it can be translated to its traditional, perfect-information fragment, i.e. to FO.

Webmaster Sjoerd Druiven

43 hits in February 2005