∙ ∙ ∙∙TL T L G G 3 Texts in Logic and Games Volume 3 Texts in Logic and Games | 3 Logic and the This volume in the Texts in Logic and Games series grew out of the seventh conference on Logic and the Founda­ B o tions of the Theory of Games and Decisions (LOFT 7), n a Foundations of which took place in Liverpool, in July 2006. The LOFT n n conferences are interdisciplinary events that bring o | together researchers from a variety of fields: compu­ V Game and Decision a ter science, economics, game theory, linguistics, logic, n d multi­agent systems, psychology, philosophy, social e r choice and statistics. Topics that fall under the LOFT H Theory (LOFT 7) o umbrella include epistemic and temporal logic, theories e k of information processing and belief revision, models of | W bounded rationality, non­monotonic reasoning, theories o of learning and evolution, mental models, etc. The papers o l EditEd by d collected in this volume reflect the variety of interests r i giacomo bonanno, wiEbE van dEr hoEk and d and the interdisciplinary composition of the LOFT com­ ge michaEl wooldridgE munity. ( e d s .) TOL hFO isbn 978 90 8964 026 0 e gg O i ac rm y a amsTerdam universiTy press en ( www.aup.nL Lad On T Fd h T de 7e 9 789089 640260 )cF O i su in O d n a T i O n s amstErdam univErsity prEss 3_def_v2.indd 1 5-6-2008 17:40:26 Logic and the Foundations oF game and decision theory (LoFt 7) TLG_3_voorwerk.indd 1 10-6-2008 13:43:51 ∙ ∙ T L G Texts in Logic and Games Volume 3 General Series Editor Advisory Board Johan van Benthem Samson Abramsky Krzysztof Apt Managing Editors Robert Aumann Wiebe van der Hoek Pierpaolo Battigalli (Computer Science) Ken Binmore Bernhard von Stengel Oliver Board (Economics & Game Theory) Giacomo Bonanno Robert van Rooij Steve Brams (Linguistics & Philosophy) Adam Brandenburger Benedikt Löwe Yossi Feinberg (Mathematical Logic) Erich Grädel Joe Halpern Editorial Assistant Wilfrid Hodges Cédric Dégremont Gerhard Jäger Rohit Parikh Technical Assistant Ariel Rubinstein Joel Uckelman Dov Samet Gabriel Sandu Reinhard Selten Robert Stalnaker Jouko Väänänen TLG_3_voorwerk.indd 2 10-6-2008 13:43:51 Logic and the Foundations of Game and Decision Theory (LOFT 7) EditEd by GiACOMO bONANNO WiEbE VAN d ER HOEK MiCHAEL WOOLdRidGE Texts in Logic and Games Volume 3 AMstER dAM uNi VERsity pRE ss TLG_3_voorwerk.indd 3 10-6-2008 13:43:51 Cover design: Maedium, Utrecht isbn 978 90 8964 026 0 nur 918 © Giacomo Bonanno, Wiebe van der Hoek, Michael Wooldridge / Amsterdam University Press, 2008 All rights reserved. Without limiting the rights under copyright reserved above, no part of this book may be reproduced, stored in or introduced into a retrieval system, or transmitted, in any form or by any means (electronic, mechanical, photocopying, recording or otherwise) without the written permission of both the copyright owner and the author of the book. TLG_3_voorwerk.indd 4 10-6-2008 13:43:51 Table of Contents Preface .................................................................7 A Qualitative Theory of Dynamic Interactive Belief Revision Alexandru Baltag, Sonja Smets ........................................11 A Syntactic Approach to Rationality in Games with Ordinal Payoffs Giacomo Bonanno ....................................................59 Semantic Results for Ontic and Epistemic Change Hans van Ditmarsch, Barteld Kooi ....................................87 Social Laws and Anti-Social Behaviour Wiebe van der Hoek, Mark Roberts, Michael Wooldridge ..............119 AMethodforReasoningaboutOtherAgents’BeliefsfromObservations Alexander Nittka, Richard Booth .....................................153 A Logical Structure for Strategies R. Ramanujam, Sunil Simon .........................................183 Models of Awareness Giacomo Sillari ......................................................209 Preface This volume in the Texts in Logic and Games series was conceived as a ramification of the seventh conference on Logic and the Foundations of the Theory of Games and Decisions (LOFT7), which took place in Liverpool, in July 2006.1 The LOFT conferences have been a regular biannual event since 1994. The first conference was hosted by the Centre International de Recherches Mathematiques in Marseille (France), the next four took place at the Inter- national Centre for Economic Research in Torino (Italy), the sixth confer- ence was hosted by the Graduate School of Management in Leipzig (Ger- many) and the most recent one took place at the University of Liverpool (United Kingdom).2 The LOFT conferences are interdisciplinary events that bring together researchersfromavarietyoffields: computerscience,economics,gamethe- ory, linguistics, logic, multi-agent systems, psychology, philosophy, social choice and statistics. In its original conception, LOFT had as its central theme the application of logic, in particular modal epistemic logic, to foun- dationalissuesinthetheoryofgamesandindividualdecision-making. Epis- temicconsiderationshavebeencentraltogametheoryforalongtime. The 1 The conference was organized by the editors of this volume with the assistance of a programcommitteeconsistingofThomas˚Agotnes,JohanvanBenthem,AdamBran- denburger, Hans van Ditmarsch, Jelle Gerbrandy, Wojtek Jamroga, Hannes Leitgeb, Benedikt L¨owe, Marc Pauly, Andr´es Perea, Gabriella Pigozzi, Wlodek Rabinowicz, HansRott,andKristerSegerberg. 2 CollectionsofpapersfrompreviousLOFTconferencescanbefoundinaspecialissueof TheoryandDecision (Vol.37,1994,editedbyM.BacharachandP.Mongin),thevol- umeEpistemiclogicandthetheoryofgamesanddecisions (editedbyM.Bacharach, L.-A.G´erard-Varet,P.MonginandH.ShinandpublishedbyKluwerAcademic,1997), two special issues of Mathematical Social Sciences (Vols. 36 and 38, 1998, edited by G. Bonanno, M. Kaneko and P. Mongin), two special issues of Bulletin of Economic Research (Vol. 53, 2001 and Vol. 54, 2002, edited by G. Bonanno and W. van der Hoek), a special issue of Research in Economics, (Vol. 57, 2003, edited by G. Bo- nanno and W. van der Hoek), a special issue of Knowledge, Rationality and Action (partofSynthese,Vol.147,2005,editedbyG.Bonanno)andthevolumeProceedings of the 7th Conference on Logic and the Foundations of Game and Decision Theory (editedbyG.Bonanno,W.vanderHoekandM.Wooldridge,UniversityofLiverpool, 2006). 8 Preface expression“interactiveepistemology”hasbeenusedinthegame-theorylit- erature to refer to the analysis of decision making by agents involved in a strategic interaction, when these agents recognize each other’s intelligence and rationality. What is relatively new is the realization that the tools and methodologiesthatwereusedingametheoryarecloselyrelatedtothoseal- readyusedinotherfields,notablycomputerscienceandphilosophy. Modal logic turned out to be the common language that made it possible to bring together different professional communities. It became apparent that the insights gained and the methodologies employed in one field could benefit researchers in other fields. Indeed, new and active areas of research have sprung from the interdisciplinary exposure provided by the LOFT confer- ences.3 Over time the scope of the LOFT conference has broadened to encom- pass a wider range of topics, while maintaining its focus on the general issue of rationality and agency. Topics that have fallen within the LOFT umbrella include epistemic and temporal logic, theories of information pro- cessing and belief revision, models of bounded rationality, non-monotonic reasoning, theories of learning and evolution, mental models, etc. The papers collected in this volume reflect the general interests and interdisciplinary scope of the LOFT conferences. The paper by Alexandru Baltag and Sonja Smets falls within the recent literature that deals with belief revision and update within the Dynamic EpistemicLogicparadigm. Theauthorsdevelopanotionofdoxasticaction general enough to cover many examples of multi-agent communication ac- tionsencounteredintheliterature,butalsoflexibleenoughtodealwithboth static and dynamic belief revision. They discuss several epistemic notions: knowledge, belief and conditional belief. For the latter they distinguish between the statement ‘if informed that P, the agent would believe that Q was the case (before the learning)’ and the statement ‘if informed that P, the agent would come to believe that Q is the case (in the world after the learning)’. They also study a “safe belief” operator meant to express a weak notion of “defeasible knowledge”: it is belief that is persistent under revision with any true information. Baltag and Smets provide a complete axiomatization of the logic of conditional belief, knowledge and safe belief. In the second part of the paper the authors discuss dynamic belief revision in the context of action models. ThepaperbyGiacomoBonannodealswiththequestionofwhatchoices are compatible with rationality of the players and common belief of ratio- nality. He takes a syntactic approach and defines rationality axiomatically. 3 There is substantial overlap between the LOFT community and the community of researcherswhoareactiveinanotherregular,biannualevent,namelytheconferences onTheoreticalAspectsofRationalityandKnowledge(TARK). Preface 9 Furthermore, he does not assume von Neumann-Morgenstern payoffs but merely ordinal payoffs, thus aiming for a more general theory of rationality in games. The author considers two axioms. The first says that a player is irrational if she chooses a particular strategy while believing that another strategyofhersisbetter. Heshowsthatcommonbelief ofthisweaknotion of rationality characterizes the iterated deletion of pure strategies that are strictly dominated by another pure strategy. The second axiom says that a player is irrational if she chooses a particular strategy while believing that a different strategy is at least as good and she considers it possible that this alternative strategy is actually better than the chosen one. The author shows that common knowledge of this stronger notion of rationality char- acterizes the iterated deletion procedure introduced by Stalnaker (1994), restricted—once again—to pure strategies. The paper by Hans van Ditmarsch and Barteld Kooi investigates a dy- namiclogicdescribing“epistemicevents”thatmaychangeboththeagents’ information (or beliefs) and what the authors call “the ontic facts” of the world (that is, objective, non-epistemic statements about the world). A sound and complete axiomatization is provided. Some original and inter- estingsemanticresultsarealsoproved,inparticularthefactthatanymodel changecanbesimulatedby“epistemicevents”,andthusanyconsistentgoal canbeachievedbyperformingsomesuchevent. Theauthorsillustratetheir results in several examples, including card games and logical puzzles. The paper by Wiebe van der Hoek, Mark Roberts and Michael Wool- dridge extends the authors’ previous work on Alternating-time Temporal Logic and its ramifications. They extend it by introducing the notion of a legally possible strategy, that they oppose to a physically possible strat- egy, and define social belief as truth in all states that are (1) possible for the agent, and (2) are obtained from the initial state by a legally possible strategy. They use this framework to reason about social laws. In a system withsocial laws, everyagent is supposedto refrainfrom performing certain forbidden actions. Rather than assuming that all agents abide by the law, the authors consider what happens if certain agents act socially, while oth- ers do not. In particular, they focus on the agents’ strategic abilities under such mixed conditions. The paper by Alexander Nittka and Richard Booth deals with the tra- ditional “static” belief revision setting, but with a different twist: rather than answering the question of how an agent should rationally change his beliefs in the light of new information, they address the question of what one can say about an agent who is observed in a belief change process. That is, the authors study the problem of how to make inferences about an agent’s beliefs based on observation of how that agent responded to a