Published: 25th July 2017
DOI: 10.4204/EPTCS.251
ISSN: 2075-2180

EPTCS 251

Proceedings Sixteenth Conference on
Theoretical Aspects of Rationality and Knowledge
Liverpool, UK, 24-26 July 2017

Edited by: Jérôme Lang

Preface
Jérôme Lang
Cheryl's Birthday
Hans van Ditmarsch, Michael Ian Hartley, Barteld Kooi, Jonathan Welton and Joseph B.W. Yeo
1
Common Knowledge in a Logic of Gossips
Krzysztof R. Apt and Dominik Wojtczak
10
A Logic for Global and Local Announcements
Francesco Belardinelli, Hans van Ditmarsch and Wiebe van der Hoek
28
Relaxing Exclusive Control in Boolean Games
Francesco Belardinelli, Umberto Grandi, Andreas Herzig, Dominique Longin, Emiliano Lorini, Arianna Novaro and Laurent Perrussel
43
A New Game Equivalence and its Modal Logic
Johan van Benthem, Nick Bezhanishvili and Sebastian Enqvist
57
From Type Spaces to Probability Frames and Back, via Language
Adam Bjorndahl and Joseph Y. Halpern
75
Logic and Topology for Knowledge, Knowability, and Belief - Extended Abstract
Adam Bjorndahl and Aybüke Özgün
88
Rationalizability and Epistemic Priority Orderings
Emiliano Catonini
102
Preservation of Semantic Properties during the Aggregation of Abstract Argumentation Frameworks
Weiwei Chen and Ulle Endriss
118
Binary Voting with Delegable Proxy: An Analysis of Liquid Democracy
Zoé Christoff and Davide Grossi
134
Bisimulation in Inquisitive Modal Logic
Ivano Ciardelli and Martin Otto
151
Toward an Epistemic-Logical Theory of Categorization
Willem Conradie, Sabine Frittella, Alessandra Palmigiano, Michele Piazzai, Apostolos Tzimoulis and Nachoem M. Wijnberg
167
Choice-Theoretic Deontic Logic
Franz Dietrich and Christian List
187
Conditional Belief, Knowledge and Probability
Jan van Eijck and Kai Li
188
Coalition and Group Announcement Logic
Rustam Galimullin and Natasha Alechina
207
A Formal Approach to the Problem of Logical Non-Omniscience
Scott Garrabrant, Tsvi Benson-Tilsen, Andrew Critch, Nate Soares and Jessica Taylor
221
The Topology of Statistical Verifiability
Konstantin Genin and Kevin T. Kelly
236
Games With Tolerant Players
Arpita Ghosh and Joseph Y. Halpern
251
What Drives People's Choices in Turn-Taking Games, if not Game-Theoretic Rationality?
Sujata Ghosh, Aviad Heifetz, Rineke Verbrugge and Harmen de Weerd
265
The Topology-Free Construction of the Universal Type Structure for Conditional Probability Systems
Pierfrancesco Guarino
285
An Epistemic Foundation for Authentication Logics (Extended Abstract)
Joseph Y. Halpern, Ron van der Meyden and Riccardo Pucella
306
A Knowledge-Based Analysis of the Blockchain Protocol
Joseph Y. Halpern and Rafael Pass
324
No Trade and Yes Trade Theorems for Heterogeneous Priors
Ziv Hellman and Alia Gizatulina
336
Indicative Conditionals and Dynamic Epistemic Logic
Wesley H. Holliday and Thomas F. Icard III
337
Common Belief in Rationality in Psychological Games
Stephan Jagau and Andrés Perea
352
Categories for Dynamic Epistemic Logic
Kohei Kishida
353
Arbitrary Arrow Update Logic with Common Knowledge is neither RE nor co-RE
Louwe B. Kuijer
373
Group Recommendations: Axioms, Impossibilities, and Random Walks
Omer Lev and Moshe Tennenholtz
382
Optimizing Epistemic Model Checking Using Conditional Independence (Extended Abstract)
Ron van der Meyden
398
Bayesian Decision Theory and Stochastic Independence
Philippe Mongin
415
Endogenizing Epistemic Actions
Will Nalls and Adam Bjorndahl
426
Together We Know How to Achieve: An Epistemic Logic of Know-How (Extended Abstract)
Pavel Naumov and Jia Tao
441
Why Forward Induction Leads to the Backward Induction Outcome: A New Proof for Battigalli's Theorem
Andrés Perea
454
Condorcet's Principle and the Preference Reversal Paradox
Dominik Peters
455
Self-confirming Games: Unawareness, Discovery, and Equilibrium
Burkhard C. Schipper
470
Argument-based Belief in Topological Structures
Chenwei Shi, Sonja Smets and Fernando R. Velázquez-Quesada
489
Reconciling Bayesian Epistemology and Narration-based Approaches to Judiciary Fact-finding
Rafal Urbaniak
504
A New Modal Framework for Epistemic Logic
Yanjing Wang
515

Preface

This volume consists of papers presented at the Sixteenth Conference on Theoretical Aspects of Rationality and Knowledge (TARK) held at the University of Liverpool, UK, from July 24 to 26, 2017.

My first TARK paper was 14 years ago. I was trained as a computer scientist but never felt completely at home at computer science conferences; neither did I feel at home at logic conferences or at economics conferences. TARK allowed me to feel at home without having to apologize for being an outsider, and I consider it the utmost example of what an interdisciplinary conference should be. TARK conferences bring together researchers from a wide variety of fields, including Computer Science (especially, Artificial Intelligence, Cryptography, Distributed Computing), Economics (especially, Decision Theory, Game Theory, Social Choice Theory), Linguistics, Philosophy (especially, Philosophical Logic), and Cognitive Psychology, in order to further understand the issues involving reasoning about rationality and knowledge.

This year we had a record of 91 submissions, out of which 18 were accepted as contributed talks and 19 as posters plus short presentation.  This huge number of submissions needed a major involvment of the members of the programme committee, to which I want to express my warmest thanks: Christian Bach (University of Liverpool), Adam Bjorndahl (Carnegie Mellon University), Jan van Eijck (CWI), Nina Gierasimczuk (Danish Technical University), Andreas Herzig (CNRS),  John Horty (University of Maryland), Fenrong Liu (Tsinghua University),  Emiliano Lorini (CNRS), Michael Mandler (Royal Holloway College, University of London), Martin Meier (Institute for Advanced Studies),  Larry Moss (Indiana University),  Pavel Naumov (Vassar College), Rafael Pass (Cornell University),  Gabriella Pigozzi (Université Paris-Dauphine),  Ariel D. Procaccia (Carnegie Mellon University), Burkhard Schipper (University of California, Davis), Sunil Easaw Simon (Indian Institute of Technology),  Elias Tsakas (Maastricht University), and Rineke Verbrugge (University of Groningen). I thank them for their careful (and sometimes very long) reviews and for the interesting discussions that followed.  Given the high number of submissions and the obvious limits imposed by the program, we had to reject some papers that could otherwise have been accepted. I hope that our process was rational enough so that we did not make too many mistakes.

Not only we had a record of submissions and accepted papers  at this TARK, but we have also a record of eminent invited speakers, which I wholeheartedly thank, following their order of appearance in the program. Mike Wooldridge (University of Oxford) is a world leading researcher in multi-agent systems who contributed to shape the field. Edith Elkind (University of Oxford) is a world leading researcher in social choice theory and algorithmic game theory. Christian List (London School of Economics) is a world leading researcher at the intersection of philosophy, economics, and political science. Pierpaolo Battigalli (Università Bocconi) is a world leading researcher in epistemic game theory. Last but not least, Hans van Ditmarsch (CNRS) and Barteld Kooi (University of Groningen), world leading researchers in epistemic logic, will give an evening talk on epistemic puzzles, based on their recent book One Hundred Prisoners and a Lightbulb (we hope the attendees will find the protocol allowing them to exit the room).

This TARK will be taking place in Liverpool. I want to express my warmest thanks to Wiebe van der Hoek and Davide Grossi for their rational and knowledgeable organisation of the conference, and for the time of energy they have put in it. This TARK will be collocated with the International Workshop on Strategic Reasoning. I want to thank its organizers, Wiebe van der Hoek, Bastien Maubert, Nello Murano and Sasha Rubin, who helped us composing the program of the joint sessions.

I thank EasyChair for making the life of authors, reviewers, and conference organizers so much easier. Also, like in 2015, EPTCS kindly agreed to publish our proceedings. I want to thank Rob van Glabbeek and the EPTCS staff for their help, kindness, and responsiveness.
 
Finally, I thank Joe Halpern for being always available to provide any kind of advice and inspiration.


J. Lang
LAMSADE-CNRS, PSL Research University, Université Paris-Dauphine, France
Programme Chair, TARK 2017




Choice-Theoretic Deontic Logic

Franz Dietrich (Paris School of Economics and CNRS)
Christian List (London School of Economics)

Rational choice theorists and deontic logicians both study actions, yet they use very different approaches. This paper introduces some choice-theoretic concepts, namely those of feasible options, choice contexts, choice functions, rankings of options, and reasons structures, into deontic logic. We use these concepts to define a simple "choice-theoretic" language for deontic logic, and consider four different "choice-theoretic" semantics for that language, which we call "basic", "behavioural", "ranking-based", and "reason-based semantics". We compare these semantics in terms of the strength of their entailment relations and characterize precisely the differences in strength between weaker and stronger ones among these semantics.


No Trade and Yes Trade Theorems for Heterogeneous Priors

Ziv Hellman (Bar Ilan University)
Alia Gizatulina (University of St. Gallen)

There is a widespread belief that because a classic theorem shows that common priors imply no trade, it follows that lack of common priors is sufficient to guarantee trade. We show, however, that even under non-common priors the classical no trade theorem obtains. Speculative trade does become mutually acceptable if traders put at least slight probability on the trading partner being irrational. Our model, thus, provides a generalization of the result of Neeman (1996) for the case of heterogeneous priors. We also derive bounds on disagreements in the case of heterogeneous priors and p-common beliefs.



Common Belief in Rationality in Psychological Games

Stephan Jagau (University of Amsterdam)
Andrés Perea (Maastricht University)

Belief-dependent motivations and emotional mechanisms such as surprise, anxiety, anger, guilt, and intention-based reciprocity pervade real-life human interaction. At the same time, traditional game theory has experienced huge difficulties trying to capture them adequately. Psychological game theory, initially introduced by Geanakoplos et al. (1989), has proven to be a useful modeling framework for these and many more psychological phenomena. In this paper, we use the epistemic approach to psychological games to systematically study common belief in rationality, also known as correlated rationalizability. We show that common belief in rationality is possible in any game that preserves optimality at infinity, a mild requirement that nests all previously known existence conditions. Also, we provide an example showing that common belief in rationality might be impossible in games where optimality is not preserved at infinity. We then develop an iterative procedure that, for a given psychological game, determines all rationalizable choices. In addition, we explore classes of psychological games that allow for a simplified procedure.




Why Forward Induction Leads to the Backward Induction Outcome: A New Proof for Battigalli's Theorem

Andrés Perea (Maastricht University)

Battigalli (1997) has shown that in dynamic games with perfect information and without relevant ties, the forward induction concept of extensive-form rationalizability yields the backward induction outcome. In this paper we provide a new proof for this remarkable result, based on four steps. We first show that extensive-form rationalizability can be characterized by the iterated application of a special reduction operator, the strong belief reduction operator. We next prove that this operator satisfies a mild version of monotonicity, which we call monotonicity on reachable histories. This property is used to show that for this operator, every possible order of elimination leads to the same set of outcomes. We finally show that backward induction yields a possible order of elimination for the strong belief reduction operator. These four properties together imply Battigalli's theorem.