Alternating (In)Dependence-Friendly Logic ‡
Informational independence is a phenomenon that emerges quite naturally in game theory, as players in a game make moves based on what they know about the state of the current play [8]. In games such as Chess or Go, both players have perfect information about the current state of the play and the moves they and their adversary have previously made. For other games, like Poker and Bridge, the players have to make decisions based only on imperfect information on the state of the play. Given the tight connection between games and logics, think for instance at game-theoretic semantics [5, 4, 1], a number of proposals have been put forward to reason with or about informational independence, most notably, Independence-Friendly Logic [2], Dependence Logic [7], and logics derived thereof.
Independence-Friendly Logic (IF) was originally introduced by Hintikka and Sandu [2], and later extensively studied, emphe.g., in [6], as an extension of First-Order Logic (FOL) with informational independence as first-class notion. Unlike in FOL, where quantified variables always functionally depend on all the previously quantified ones, the values for quantified variables in IF can be chosen independently of the values of specific variables quantified before in the formula. From a general game-theoretic viewpoint, however, the IF semantics exhibits some limitations. It treats the players asymmetrically, truly allowing only one of the two players to have imperfect information. In addition, sentences of the logic can only encode the existence of a uniform winning strategy for one of the two players and, as a consequence, IF does admit undetermined sentences, which are neither true nor false.
In this talk I will present an extension of IF, called Alternating (In)Dependence Friendly Logic (ADIF), tailored to overcome these limitations and that appears more adequate when reasoning about games with full imperfect information is the main concern. To this end, we introduce a novel compositional semantics, generalising Hodges’ semantics for IF based on trumps/teams [3, 7, 6], which
- allows for restricting the two players, aiming at describing both symmetric and asymmetric imperfect information games,
- recovers the law of excluded middle for sentences, and
- grants ADIF the full descriptive power of Second Order Logic.
We also provide both an equivalent Herbrand-Skolem semantics and a game-theoretic semantics for the prenex fragment of ADIF, the latter being defined in terms of a determined infinite-duration game that precisely captures the compositional semantics on finite structures.
References
- [1]
- J. Hintikka. Logic, Language-Games and Information: Kantian Themes in the Philosophy of Logic. Oxford University Press, 1973.
- [2]
- J. Hintikka and G. Sandu. Informational Independence as a Semantical Phenomenon. In ICLMPS’89, pages 571–589. Elsevier, 1989.
- [3]
- W. Hodges. Compositional Semantics for a Language of Imperfect Information. LJIGPL, 5(4):539–563, 1997.
- [4]
- K. Lorenz. Dialogspiele als Semantische Grundlage von Logikkalkülen. AMLG, 11:32–55, 1968.
- [5]
- P. Lorenzen. Ein Dialogisches Konstruktivitätskriterium. In SFM’59, pages 193–200. PWN, 1961.
- [6]
- A.L. Mann, G. Sandu, and M. Sevenster. Independence-Friendly Logic - A Game-Theoretic Approach. CUP, 2011.
- [7]
- J.A. Väänänen. Dependence Logic: A New Approach to Independence Friendly Logic., volume 70 of London Mathematical Society Student Texts. CUP, 2007.
- [8]
- J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, 1944.
‡ Joint work with Dylan Bellier, Massimo Benerecetti, and Dario Della Monica.
This document was translated from LATEX by HEVEA.