Published: 23rd June 2016
DOI: 10.4204/EPTCS.215
ISSN: 2075-2180

EPTCS 215

Proceedings Fifteenth Conference on
Theoretical Aspects of Rationality and Knowledge
Carnegie Mellon University, Pittsburgh, USA, June 4-6, 2015

Edited by: R Ramanujam

Preface
Invited Presentation: The Problem of Analogical Inference in Inductive Logic
Simon M. Huttegger
1
Invited Presentation: Human-Agent Decision-making: Combining Theory and Practice
Sarit Kraus
13
Invited Presentation: Rationality and Beliefs in Dynamic Games: Revealed-Preference Foundations
Marciano Siniscalchi
28
Resolving Distributed Knowledge
Thomas Ågotnes and Yì N. Wáng
31
Epistemic Protocols for Distributed Gossiping
Krzysztof R. Apt, Davide Grossi and Wiebe van der Hoek
51
Coordination Games on Directed Graphs
Krzysztof R. Apt, Sunil Simon and Dominik Wojtczak
67
On the Solvability of Inductive Problems: A Study in Epistemic Topology
Alexandru Baltag, Nina Gierasimczuk and Sonja Smets
81
Bayesian Games with Intentions
Adam Bjorndahl, Joseph Y. Halpern and Rafael Pass
99
Translucent Players: Explaining Cooperative Behavior in Social Dilemmas
Valerio Capraro and Joseph Y. Halpern
114
Single-Peaked Consistency for Weak Orders Is Easy
Zack Fitzsimmons
127
Standard State Space Models of Unawareness (Extended Abstract)
Peter Fritz and Harvey Lederman
141
Do players reason by forward induction in dynamic perfect information games?
Sujata Ghosh, Aviad Heifetz and Rineke Verbrugge
159
Ceteris paribus logic in counterfactual reasoning
Patrick Girard and Marcus Anthony Triplett
176
An Axiomatic Approach to Routing
Omer Lev, Moshe Tennenholtz and Aviv Zohar
194
Preference at First Sight
Chanjuan Liu
207
The optimality of coarse categories in decision-making and information storage
Michael Mandler
227
Relating Knowledge and Coordinated Action: The Knowledge of Preconditions Principle
Yoram Moses
231
Parameterized Complexity Results for a Model of Theory of Mind Based on Dynamic Epistemic Logic
Iris van de Pol, Iris van Rooij and Jakub Szymanik
246
Undecidable Cases of Model Checking Probabilistic Temporal-Epistemic Logic (Extended Abstract)
R van der Meyden and M K Patra
264
Announcement as effort on topological spaces
Hans van Ditmarsch, Sophia Knight and Aybüke Özgün
283
A Dynamic Epistemic Framework for Conformant Planning
Quan Yu, Yanjun Li and Yanjing Wang
298

Preface

This volume consists of papers presented at the Fifteenth conference on Theoretical Aspects of Rationality and Knowledge (TARK) held at Carnegie Mellon University, Pittsburgh, USA from June 4 to 6, 2015.

It has been my pleasure to be part of the TARK community since the first conference at Asilomar, California, in 1986, principally due to the encouragement of Rohit Parikh, one of the founders of TARK. This conference is uniquely situated as one that brings together researchers from a wide variety of fields, including Artificial Intelligence, Cryptography, Distributed Computing, Economics and Game Theory, Linguistics, Philosophy, and Psychology. It has played an important role in our understanding of interdisciplinary issues involving reasoning about rationality and knowledge.

TARK 2015 had 63 submissions out of which 18 were accepted as contributed talks and 9 as poster presentations for the programme. I am very grateful for having the cooperation and advice of 17 other members of the multidisciplinary program committee: Eleonora Cresto (CONICET, University of Buenos Aires, Argentina), Clare Dixon (University of Liverpool, UK), Edith Elkind (Oxford University, UK), Amanda Friedenberg (Arizona State University, USA), Sujata Ghosh (Indian Statistical Institute, India), Andreas Herzig (IRIT, Toulouse, France), Bettina Klaus (University of Lausanne, Switerland), Kevin Kelly (Carnegie Mellon University, USA), Yoram Moses (Technion, Tel Aviv, Israel), Andrés Perea (Maastricht University, The Netherlands), Sophie Pinchinat (IRISA, Rennes, France), Francesca Rossi (University of Padova, Italy), Olivier Roy (Bayreuth University, Germany), Burkhard Schipper (University of California at Davis, USA), Hans van Ditmarsch (LORIA, France), Yanjing Wang (Peking University, China) and Michael Wooldridge (Oxford, UK). I thank them for their hard work in providing careful reviews and for the detailed discussions about the submissions. When papers are read across disciplines, there can be keen differences in what is considered good and important; I thank the committee members for trying their best to listen to other viewpoints.

We had four eminent invited speakers in this edition of TARK: Robin Clark of the University of Pennsylvania, USA, bringing a viewpoint from Psychology and Cognition to epistemic reasoning; Simon Huttegger, of the University of California, Irvine, USA, a philosopher's look at observational process and inductive logic; Sarit Kraus of Bar-Ilan University, Israel, on desiging computational agents for interacting with people, based on insights from game theory and logic; Marciano Siniscalchi, Northwestern University, USA, on foundations of rationality in sequential games. In addition, we had a tutorial on causal inference and causal discovery, jointly by Peter Spirtes of Carnegie Mellon University, USA, and Kun Zhang of Max Planck Institute for Intelligent Systems, Tübingen, Germany. I thank these speakers for insightful presentations, some of which have been included as abstracts / papers here.

The organizing team at Carnegie Mellon University, led by Kevin Kelly, did an excellent job of running the conference, and Joe Halpern provided advice and inspiration when needed, I thank them all.

Though the conference proceedings were prepared at the time of the meeting and made available from the conference page (http://www.imsc.res.in/tark/tark15.html), it could not be indexed by DBLP and other scholarly services. Hence the need for a Post-Proceedings that could be indexed and accessed in the Web. EPTCS kindly agreed to provide a venue for this, and I sincerely thank Krzysztof Apt for suggesting this avenue, and Rob van Glabbeek for patiently guiding this process. I thank Anantha Padmanabha, my colleague at IMSc, for tremendous help with preparing this volume.

R. Ramanujam
Institute of Mathematical Sciences, Chennai, India
Programme Chair, TARK 2015


Rationality and Beliefs in Dynamic Games: Revealed-Preference Foundations

Marciano Siniscalchi (Northwestern University,IL, USA)

Sequential rationality is the prevalent notion of best response for dynamic games; it is an essential part of the definition of sequential equilibrium [9], perfect Bayesian equilibrium [6], and extensive-form rationalizability [11]. Abstracting from notational and other minor differences, a strategy si of player i is sequentially rational if, beginning at any information set where i moves, si specifies a sequence of actions that is optimal given the beliefs that i holds at that information set about the play of her opponents.
While this notion is central to the theory of dynamic games, it raises both practical and methodological concerns. From a practical standpoint, it is not obvious how to reliably ascertain which strategy a player follows in a given dynamic game, and a fortiori whether it is or isn't sequentially rational. Consider a three-stage Centipede game [13], played by Ann (who moves at the first and third nodes) and Bob. Suppose that, as predicted by backward induction, Ann ends the game at the first node by moving Down. Then, we are unable to observe Bob's intended choice at the second node. Furthermore, to determine whether such a choice would have been optimal, had Ann chosen Across instead, we need to consider Bob's beliefs conditional upon an event that Bob does not expect to occur-a zero-probability event. While formally we can represent such beliefs, it is not clear how an experimenter might elicit them in practice.

Reinhard Selten's strategy method [16] is a widely used experimental procedure that is intended to elicit players' intended strategy choices in dynamic games. There is evidence that the strategy method is an effective elicitation procedure: see, e.g., [3]. But this finding actually raises further questions. The strategy method essentially asks players to simultaneously commit to a strategy, which is then implemented by the experimenter without possibility of subsequent intervention by the subjects. This reduces the original dynamic game to one in which players face non-trivial moves only in the initial stage; furthermore, such moves are simultaneous. Standard solution concepts such as sequential or perfect Bayesian equilibrium predict that players will maximize ex-ante expected payoffs when the strategy method is employed; therefore, such solution concepts do allow subjects to commit to strategies that are not sequentially rational in the original game. Refinements that incorporate the notion of invariance [8] do imply that subjects will only commit to strategies that are sequentially rational in the original game. However, there is ample experimental evidence that contradicts the invariance hypothesis [5, 15, 4, 7]. Thus, the received theory cannot at the same time explain the effectiveness of the strategy method, and account for violations of the invariance hypothesis.

These practical issues hint at a deeper methodological concern. Economics has long embraced the revealed-preference approach: assumptions about agents' tastes and beliefs should be testable, or elicitable, on the basis of observable choices in suitably designed problems. To date, rationality and beliefs in dynamic games have not been subject to analysis from the revealed-preference perspective. Formal definitions of sequential rationality build upon expected-utility maximization. However, the revealed preference foundations for expected utility [14, 1] concern atemporal, or one-shot choices. Furthermore, extensions of expected-utility theory to dynamic choice problems are wholly silent about behavior conditional upon ex-ante zero probability events. Of course, the analysis of intended choices following unexpected moves is at the heart of dynamic game theory. Thus, the received decision theory is insufficient to provide foundations to the analysis of dynamic games.

The objective of this project is to provide such a foundation. This entails two contributions. The first is to define a novel choice criterion for dynamic decision problems and games, sequential preference, so as to satify two criteria. First, the proposed criterion implies sequential rationality. Second, it allows preferences over strategies to be elicited from ex-ante choices, using a version of the strategy method. In particular, sequential preferences provide a theoretical rationale for the use of this common experimental procedure, as well as a method to elicit conditional beliefs following zero-probability events.
Building on the finding that sequential preferences are indeed elicitable, the second contribution of this project is to provide a behavioral, or axiomatic, characterization of the proposed choice criterion. This is based on a suitable adaptation of the Anscombe-Aumann [1] axioms.

Finally, in the analysis of sequential preferences, there are natural connections to conditional probability systems [12,10] and lexicographic probability systems [2]. These are explored, and their implications for game-theoretic analysis are discussed. The project is carried out in two papers. The first, [18], introduces sequential preferences, and analyzes elicitation and the strategy method. The second, [17], provides behavioral foundations.

References

  1. F. J. Anscombe and R. J. Aumann. A definition of subjective probability. In: Annals of Mathematical Statistics, 34: 199-205, 1963.
  2. L. Blume, A. Branderburger, and E. Dekel. Lexicographic probabilities and choice under uncertainty. In: Econometrica, 59:61-79, 1991.
  3. J. Brandts and G. Charness. The strategy versus the direct-response method: a first survey of experimental comparisons. In: Experimental Economics, 14(3):375-398, 2011.
  4. D. J. Cooper and J. B. Van Huyck. Evidence on the equivalence of the strategic and extensive form representation of games. In: Journal of Economic Theory, 110(2):290-308, 2003.
  5. R. Cooper, D. V. DeJong, R. Forsythe, and T. W. Ross. Forward induction in the battle-of-the-sexes games. In: American Economic Review, 83(5):1303-1316, 1993.
  6. D. Fudenberg and J. Tirole. Perfect Bayesian equilibrium and sequential equilibrium* 1. In: Journal of Economic Theory, 53(2):236-260, 1991.
  7. S. Huck and W. Müller. Burning money and (pseudo) first-mover advantages: an experimental study on forward induction. In: Games and Economic Behavior, 51(1):109-127, 2005.
  8. E. Kohlberg and J. Mertens. On the strategic stability of equilibria. In: Econometrica: Journal of the Econometric Society, 54(5):1003-1037, 1986.
  9. D. Kreps and R. Wilson. Sequential equilibria. In: Econometrica: Journal of the Econometric Society, 50(4):863-894, 1982.
  10. R. B. Myerson. Axiomatic foundations of bayesian decision theory. In: Discussion Paper 671, The Center for Mathematical Studies in Economics and Management Science, Northwestern University, January 1986.
  11. D. G. Pearce. Rationalizable strategic behavior and the problem of perfection. In: Econometrica, 52:1029-1050, 1984.
  12. A. Rènyi. On a new axiomatic theory of probability. In: Acta Mathematica Hungarica, 6(3):285-335, 1955.
  13. R. Rosenthal. Games of Perfect Information, Predatory Pricing and the Chain-Store Paradox. In: Journal of Economic Theory, 25(1):92-100, 1981.
  14. L. Savage. The foundations of statistics. In: Dover Pubns, 1972.
  15. A. Schotter, K. Weigelt, and C. Wilson. A laboratory investigation of multiperson rationality and presentation effects. In: Games and Economic behavior, 6(3):445-468, 1994.
  16. R. Selten. Ein oligopolexperiment mit preisvariation und investition. In: Beitrage zur experimentellen "Wirtschaftsforschung, ed. by H. Sauermann, JCB Mohr (Paul Siebeck), Tubingen" , pages 103-135, 1967.
  17. M. Siniscalchi. Foundations for sequential preferences. In: mimeo, Northwestern University, 2015.
  18. M. Siniscalchi. Sequential preferences and sequential rationality. In: Northwestern University, 2015.