All talks will take place in Hörsaal (lecture room) 12, main building (Karlsplatz), Stiege (staircase) 6, 2nd floor.
Ludics and interactive completeness
Forward and backward induction in dynamic games: Distilling the axiomatic differences on common ground
Backward Induction (BI) is the basic solution concept for finite games with perfect information. It is the procedure to find out all the subgame-perfect equilibria in such games, i.e. the Nash equilibria in which incredible threats are precluded. An alternative approach to solving games with perfect information is to employ Forward Induction (FI), with which players do assess their opponents’ future behavior on the basis of these opponents’ past moves. A prominent solution concept embodying FI is Extensive-Form Rationalizability (EFR), in which the active player at each node reacts optimally to a best rationalization of her opponents’ past behavior.
Both BI and EFR are, strictly speaking, distinct iterative heuristics of strategy sieving, whose technical definitions do not directly disclose their epistemic motivation. This calls for exposing the different axiomatic assumptions underlying the two solution concepts, in a way that will enable an explicit comparison between them. This (ongoing) work aims at setting up an appropriate epistemic logic syntax, and at formulating directly comparable axiom systems characterizing BI and EFR.
Signaling in independence-friendly logic
IF logic is an extension of first-order logic with quantifiers of the form
(∃x/X) , (∀y/Y)
where X and Y are sets of individual variables. The intended interpretation of, e.g., (∃x/X) is: the choice of a value for x is independent of the choices of values for the variables in X. The notion of “independence” is a game-theoretical one. When X and Y are empty, we recover the standard quantifiers ∃x and ∀y. There are basically two kinds of prefixes of IF quantifiers that lead to a greater expressive power over ordinary first-order logic: Henkin prefixes and signaling prefixes. An example of a Henkin prefix is
∀x∀y(∃z/{y})(∃w/{x,z})
and an example of a signaling prefix is
∀x∃y(∃z/{x}).
Henkin prefixes have been introduced (in a different context) by Henkin (1961) and signaling prefixes by Hodges (1997).
The present paper surveys recent results on Henkin and signaling prefixes which are relevant for expressive power and computational complexity. We shall also consider IF sentences with signaling prefixes which are indeterminate and a way to overcome their indeterminacy by applying von Neumann's Minimax Theorem.
Emulating diffusion and best response dynamics in social networks using action models
Threshold models and their dynamics may be used to model the spread of behaviors, fashions or language use in social networks. Regarding such as Kripke models, it is shown how standard update mechanisms may be emulated using action models. The suitable class of action models is specified and shown to include models characterizing best response dynamics of both coordination and anti-coordination games played on graphs. Hereby, new links between social network theory, game theory and dynamic ‘epistemic’ logic are drawn.
Game semantics from a cognitive modeling standpoint
Wittgenstein has suggested an analogy between having a proof and winning a game. Two research programs that have undertaken to make this analogy formally precise: game-theoretic semantics (GTS) and dialogical logic (DL) but have so come up only with a partial reduction of logic to language games. Specifically, they have failed to specify preferences for the players, and inference mechanisms by which dominated strategies are eliminated, and by which strategic profiles that realize proofs are selected. Instead, they introduce ad hoc restrictions on strategies by means of game rules that guarantee the games to realize model-checking (GTS) and proofs (DL) procedures. We show how these restrictions can be derived from preference profiles of bounded-rational players, and specify inference mechanisms for strategy selection, based on some assumptions that select the player types. Our model does not answer a foundational agenda but should be viewed as an exercise in cognitive modeling, which bridges the watershed between formal and cognitive semantics, and may yield some insights into how logical reasoning could have emerged from natural language argumentation.
Game reduction
We propose a notion of reduction between games to capture that one game is not harder to play than another one. Our definition corresponds to a model-comparison game between dynamic models.
Semantic games for Łukasiewicz logic
The aim of the presentation is to give an overview of various approaches to game-theoretical semantics for one of the most prominent members of the family of fuzzy logics and compare it to some other game-theoretical frameworks for many-valued logics, in particular to equilibrium semantics for Independence-friendly (IF) logics.
Łukasiewicz logic is one of the background systems of the family of fuzzy logics and captures some basic intuitions about principles of reasoning with vague information. Game-theoretical semantics among other things provides alternative ways to derive these principles and thus gives an interesting insight in the foundations of fuzzy logics.
The story of game-theoretical approach to Łukasiewicz logic goes back to 1970s when Robin Giles proposed a Lorenzen style game interpreted in terms of betting on the results of a physical experiment, the aim of which was to propose a non-classical logic for physics. His proposal was then further developed and generalized by C. Fermüller (Fermüller 2009). P. Cintula and O. Majer (Cintula and Majer 2009) proposed an alternative approach—a Hintikka-Sandu-style evaluation game that can be interpreted as a certain kind of bargaining game.
Independence-friendly logic with equilibrium semantics (Mann, Sandu and Sevenster 2011) is a recent contribution to the family of many-valued logics. There are similarities between both formalisms on a technical level (the ‘slash-free’ fragment of IF logic is equivalent to the weak fragment of Łukasiewicz logic) but from the point of view of foundations each of them deals with a different kind of uncertainty. We will discuss the possibility of combining both frameworks into a hybrid system incorporating both vagueness and probability, which could be interesting both technically and from the point of view of foundations of uncertainty.
Multi-agent dialogical games for modal logic
Dialogical Logic as a game-theoretic approach was introduced by Lorenzen and Lorenz and can be used to check validity of formulae for different kinds of logics. The system has been extended by Rahman and Rückert to cope with modal logic. Dialogues are very flexible as one can simply exchange their underlying rules to obtain decision procedures for other kinds of logic. A problem that occurs with the dialogues is that the amount of possible moves the players can perform in the game often cause a very high branching which makes the implementation inefficient when one wants to show or refute validity of formulae. We modify the system by introducing further players who all try to show validity of a formula together. This approach works in a more deterministic way and thereby provides a plan to parallelize the reasoning process.
Game semantics for conditional logic
In this talk we introduce a game semantics for conditional logic. We define a game for every inference between conditionals. A winning strategy for the first player can be transformed into a proof of the inference in system P, which is the standard inference system for conditional logic. Conversely a proof in system P yields a winning strategy for the first player. A winning strategy for the second player can be transformed into a countermodel to the inference in the standard order semantics of conditional logic. Conversely a countermodel in the order semantics yields a winning strategy for the second player. Combining these results we obtain a new, more constructive, proof of strong completeness for conditional logic with respect to its order semantics.
Game semantics for some non-classical logics
Game-theoretical semantics has a very intuitive approach to formal semantics. A semantic verification game is played by two players, Abelard and Heloise. The goal of Heloise in the game is to verify the truth of a given formula in a given model, whereas for Abelard it is to falsify it. The rules of the semantic verification game are specified syntactically based on the form of the formula. The major result of this approach states that Heloise has a winning strategy if and only if the given formula is true in the given model.
Our goal in this paper is to give game semantics for various non-classical logics, and observe how non-classical logical elements change the verification game. Therefore, we follow the “from logic to game” direction. The logics we consider are Graham Priest’s Logic of Paradox, Dunn’s First-Degree Entailment, Routley and Routley’s Relevance Logic and finally Belnap’s four-valued logic.
While giving a game-theoretical semantics for Logic of Paradox, we introduce an additional player. For First-Degree Entailment, we allow simultaneous plays. For Relevance Logic, we follow the traditional modal direction in handling possible worlds. In Belnap’s four-valued logic, we observe why game semantics, in its intuitive sense, does not work. Furthermore, we also observe how the biconditional classical correctness theorem fails in non-classical logics.
Non-classical game semantics introduce various finer game-theoretical notions. For instance, paraconsistent logics distinguish different “trues”: trues that are only true, and trues that are also false (similarly for falsehood). In the semantic verification game for paraconsistent logic of paradox, we can distinguish the cases where having a winning strategy for one player does imply the lack of a winning strategy for the opponent, and where having a winning strategy for one player does not imply the lack of winning strategy for the opponent. This is one of the strengths of non-classical game semantics.
Finally, we conclude with some remarks on the connection between designated truth values, which is a very central concept to non-classical logics, and game semantics.
Non-characterizability in belief revision: An application of finite model theory
A formal framework is given for the characterizability of a class of belief revision operators, defined using minimization over a class of partial preorders, by postulates. It is shown that for partial orders characterizability implies a definability property of the class of partial orders in monadic second-order logic. Based on a non-definability result for a class of partial orders, an example is given of a non-characterizable class of revision operators. This appears to be the first non-characterizability result in belief revision.