# Blog Archives

# Topic Archive: epistemic logic

# Bi-simulation of epistemic structures: a semantic proof of completeness for Muddy Children Puzzle.

In this talk we discuss truth preserving bi-simulations of multi-agent Kripke models. As an application, we present a semantic proof of the completeness of the syntactic formulation of Muddy Children Puzzle with respect to its standard model.

# Reasoning about reasoning about games

A mixture of propositional dynamic logic and epistemic logic that we call PDL + E is used to give a formalization of Artemov’s knowledge based reasoning approach to game theory. Epistemic states of players are represented explicitly and reasoned about formally. We give a detailed analysis of the Centipede game using both syntactic proofs and semantical arguments. Formal proofs are used establish what is the case and what is needed to show this. Semantical machinery is used to establish what cannot be the case. All this makes a case that PDL + E can be a useful basis for the logical investigation of game theory.

# Syntactic Epistemic Logic and Games IV

In this talk we consider knowledge structures used to model epistemic components of extensive-form games. We show that the traditional semantic mode of specification by a single model cannot capture some natural epistemic notions, e.g., mutual knowledge of rationality, used in Epistemic Game Theory. In contrast, Syntactic Epistemic Logic handles this and many other conditions that lie outside the scope of the semantic tradition. We outline general principles of Syntactic Epistemic Logic in connection to Game Theory.

# First-order justification logic JT45

Among the different propositional justification logics, JT45 is the justification counterpart of the modal logic S5. Although there is a growing literature about propositional justification logic, there are only a few papers about the first-order version of justification logic. And most of those papers focus on the first-order version of LP. The goal of this talk is to present a first approach to first-order JT45 (FOJT45). Using Fitting models we will present a possible worlds semantics for FOJT45 and with that establish a Completeness Theorem. We will also discuss some topics related to first-order modal logic such as the Barcan Formula and the failure of the Interpolation Theorem.

# Syntactic Epistemic Logic and Games I

We argue that the traditional way to specify an epistemic situation via a single model is unnecessarily restrictive: there are numerous scenarios which do not have conventional single-model characterizations: less-than-common knowledge (e.g., mutual knowledge), partial, asymmetric knowledge, etc. Syntactic Epistemic Logic, SEL, suggests a way out of this predicament by viewing an epistemic scenario as specified syntactically by a set of formulas which corresponds to the characterization via a class of models rather than a single model. In addition, in Game Theory, SEL helps to seal the conceptual and technical gap, identified by R.Aumann, between the syntactic character of game descriptions and the predominantly semantical way of analyzing games.

This will be the first in the series of talks on SEL. We will consider natural examples of epistemic or game theoretic scenarios which have manageable syntactic description but do not have acceptable single model characterizations.

# Modeling Intuitionistic Epistemic Logic via Provability and Verification (joint work with S. Artemov)

In 1933, Goedel offered a provability semantics for intuitionsitic logic IPC by means of a syntactical embedding of IPC into the modal logic S4 which Goedel considered a calculus for classical provability. Goedel’s embedding later became a key ingredient of the BHK-style semantics of classical proofs for intuitionsitic logic via the Logic of Proofs. We will establish the embedding/interpretation of Intuitionistic Epistemic Logic IEL into a natural extension (which we suggest calling S4V) of Goedel’s provability logic S4 by a verification modality. Basically, we will explain IEL via classical provability and verification coded in S4V the way Goedel explained intuitionistic logic via classical provability by interpreting it in S4.

# From Intuitionistic Epistemic Logic to a constructive resolution of the Knowability Paradox (joint work with S. Artemov)

We outline an intuitionistic view of knowledge which maintains the Brouwer-Heyting-Kolmogorov semantics and is consistent with Williamson’s suggestion that intuitionistic knowledge be regarded as the result of verification. We argue that on this view A -> KA is valid and KA -> A is not. We show the latter is a distinctly classical principle, too strong as the intuitionistic truth condition for knowledge which can be more adequately expressed by other modal means, e.g. ~(KA & ~A) “false is not known.” We construct a system of intuitionistic epistemic logic, IEL, codifying this view of knowledge and prove the standard meta-theorems for it. From this it follows that previous outlines of intuitionistic knowledge, responding to the knowability paradox, are insufficiently intuitionistic; by endorsing KA -> A they implicitly adopt a classical view of knowledge, by rejecting A -> KA they reject the constructivity of truth. Within the framework of IEL, the knowability paradox is resolved in a constructive manner which, as we hope, reflects its intrinsic meaning.

# Models of Justification Logic III

In this lecture we will review topological models of modal and justification logics.

# On Models of Justification Logic II.

We will introduce a new, slightly more general class of models for Justification Logic and compare them with Mkrtychev, Fitting, and modular models. Completeness Theorem will be established, examples will be given and plausible areas of applications outlined.

# On models of Justification Logic

This will be a mostly survey talk in which we discuss a variety of models for Justification Logic: arithmetical models (Goedel, Artemov), Mkrtychev models, Fitting models, topological models (Artemov, Nogina), modular models (Artemov), Sedlar’s group models, and some others. We will continue discussing applications.

# Some new directions in Epistemic Logic.

We will review research avenues on which we will focus this semester.

1. Applications of Justification Logic: general theory of logical omniscience, new format of handling inconsistent information, argumentation theory, truth maintenance systems, tracking evidence and belief revision.

2. Syntactic Epistemic Logic. There is some well-known tension between a syntactic description of an epistemic scenario and its semantical analysis based on a specific model. Such analysis requires common knowledge of the model which does not usually follow from the assumptions. Syntactic Epistemic Logic offers an approach to epistemic situations which does not rely on the common knowledge of a model.

3. Generic Common Knowledge.The notion of common knowledge of F, as introduced by Lewis in 1969, refers to any situation in which each finite iteration of `agent 1 knows that agent 2 knows that … F’ holds. A similar approach has been offered by McCarthy and others. This situatuion is now called Generic Common Knowledge, GCK, of F. Now dominant notion of Common Knowledge CK was coined by Aumann in 1976 as the least of all GCK’s of F. Now there is a growing number of specific epistemic scenarios which require GCK rather than CK. We are developing the theory of GCK and applying GCK to CK in appropriate situations.

# On the Complexity of Multi-agent Justification Logic Under Interacting Justifications II

We introduce a family of multi-agent justification logics with interactions between the agents’ justifications, by extending and generalizing the two-agent versions of LP introduced by Yavorskaya in 2008. Known concepts and tools from the single-agent justification setting are adjusted for this multiple agent case. We present tableau rules and some preliminary complexity results: in several important cases, the satisfiability problem for these logics remains in the second level of the polynomial hierarchy, while for others it is PSPACE or EXP-hard.

This week we will present the general tableau rules for the family. We look more closely at particular examples and complexity bounds and we identify common sources of jumps in their complexity.

# On the Complexity of Multi-agent Justification Logic Under Interacting Justifications

We introduce a family of multi-agent justification logics with interactions between the agents’ justifications, by extending and generalizing the two-agent versions of LP introduced by Yavorskaya in 2008. Known concepts and tools from the single-agent justification setting are adjusted for this multiple agent case. We present tableau rules and some preliminary complexity results: in several important cases, the satisfiability problem for these logics remains in the second level of the polynomial hierarchy, while for others it is PSPACE or EXP-hard.

# Towards Syntactic Epistemic Game Theory

The traditional semantic approach to consider a game as an Aumann structure, though flexible and convenient, is not foundationally satisfactory due to assumptions that a given Aumann structure adequately represents the game and that this structure itself is common knowledge for the players.

These assumptions leave a gap between the officially syntactic character of the game description that often admits multiple models and studying a game as a specific model that is somehow assumed to be commonly known. This gap has been largely ignored or covered up by using as examples simple epistemic scenarios with natural models that were tacitly used as definitions of the game instead of declared syntactic game descriptions. Among others, Aumman found this foundationally unsatisfactory and argued for using what he called ‘Syntactic epistemic logic’ for reasoning about games.

In this talk, we outline a systematic approach to epistemic game theory which we suggest calling ‘Syntactic Epistemic Game Theory’, SEGT, consistent with Aumann’s suggestions, that studies games as they are normally described, in their syntactic form. In SEGT, semantic methods should be properly justified from the original game description. As a case study, we offer a SEGT theory of definitive solutions of strategic games with ordinal payoffs.

# Lost in translation: a critical view of epistemic puzzles solutions.

There are two basic ways to specify an epistemic scenario:

1. Syntactic: a verbal description with some epistemic logic on the background and some additional formalizable assumptions; think of the Muddy Children puzzle.

2. Semantic: providing an epistemic model; think of Aumann structures – a typical way to define epistemic components of games.

Such classical examples as Muddy Children, Wise Men, Wise Girls, etc., are given by syntactic descriptions (type 1), each of which is “automatically” replaced by a simple finite model (type 2). Validity of such translations from (1) to (2) will be the subject of our study.

We argue that in reducing (1) to (2), it is imperative to check whether (1) is complete with respect to (2) without which solutions of puzzles by model reasoning in (2) are not complete, at best. We have already shown that such reductions can be justified in the Muddy Children puzzle MC due to its model categoricity: we have proved that MC has the unique “cube” model Q_n for each n. This fixes an obvious gap in the “textbook” solution of Muddy Children which did not provide a sufficient justification for using Q_n.

We also show that an adequate reduction of (1) to (2) is rather a lucky exception, which makes the requirement to check the completeness of (1) w.r.t. (2) necessary. To make this point, we provide a simplified version of Muddy Children (by dropping the assumption “no kid knows whether he is muddy”) which admits the usual deductive solution by reasoning from the syntactic description, but which cannot be reduced to any finite model.

# Geodesic Semantics for Belief Change

Any logical system that models human reasoning needs to address the possibility of error and the subsequent belief change once this error is recognized. The need to deal with error-prone reasoning has only been widely acknowledged in the last thirty years or so; witnesses the popularity of the AGM postulates for Belief Revision. Despite the variety of syntactical and semantical offerings, all seem to agree that we need to model a concept of minimal change by choosing the most similar epistemic state to the present one. The favorite choice mechanisms are preferential orderings and, their generalization, distance maps. Preferential orderings provide satisfactory representation results but fail to model iteration. Distance maps model iteration but fail to provide satisfactory completeness results. In this talk, I will introduce a third semantical approach using geodesic distance (length of shortest path on a graph) that lies between the two and combines their best features: geodesic semantics provide satisfactory completeness results like preferential orderings do and deal with iteration, as distance maps do. Further, and perhaps more important, geodesic semantics offer a novel, more natural representation of similarity using distinguishability.