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 |
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
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.
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.
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.
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.