VSL 2014: VIENNA SUMMER OF LOGIC 2014
LG ON TUESDAY, JULY 15TH, 2014

View: session overviewtalk overviewside by side with other conferences

09:00-10:15 Session 45: Logic and games from cognitive, social, and abstract perspectives (1/2)
Location: MB, Hörsaal 12
09:00
Ludics and interactive completeness
09:45
Forward and backward induction in dynamic games: Distilling the axiomatic differences on common ground
SPEAKER: Sujata Ghosh

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

10:15-10:45Coffee Break
10:45-13:00 Session 47E: Logic and games from cognitive, social, and abstract perspectives (2/2)
Location: MB, Hörsaal 12
10:45
Signaling in independence-friendly logic
SPEAKER: Gabriel Sandu
11:30
Game Reductions

ABSTRACT. One recurring pattern in strategic reasoning consists in constructing a strategy for one game while playing another, auxiliary game on the side. Ehrenfeucht-Fraisse games can be seen as an instance of this technique. Although close to the concept of reduction in computation, transferring strategies between games is typically used as a proof artifice, without explicit formalisation. In this talk, we set out with a construction that underlies recent results about infinite games with imperfect monitoring. On basis of this, we illustrate more general features of a strategy transfer mechanism and outline a formal approach via meta-games.

 

12:00
Game Semantics from a Cognitive Modeling Standpoint
SPEAKER: unknown

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

12:30
Emulating Diffusion and Best Response Dynamics in Social Networks using Action Models

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

13:00-14:30Lunch Break
14:30-16:15 Session 50E: Games for belief revision and non-classical logic (1/2)
Location: MB, Hörsaal 12
14:30
Semantic games for Łukasiewicz logic
SPEAKER: Ondrej Majer
15:15
Game Semantics for Conditional Logic

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

15:45
Multi-Agent Dialogical Games for Modal Logic
SPEAKER: Martin Sticht

ABSTRACT. 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 new approach works in a more deterministic way and thereby provides a plan to parallelize the reasoning process.

16:00-16:30Coffee Break
16:30-17:45 Session 52D: Games for belief revision and non-classical logic (2/2)
Location: MB, Hörsaal 12
16:30
Non-characterizability in belief revision: an application of finite model theory
SPEAKER: Jon Yaggie

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

17:00
Game Semantics for Some Non-Classical Logics
SPEAKER: Can Baskent

ABSTRACT. Our main 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.

19:00-20:00 Session 56A: VSL Public Lecture 1
Location: MB, Kuppelsaal
19:00
VSL Public Lecture: Gödel in Vienna
SPEAKER: Karl Sigmund