Fall 2009
Seminar in Computational Logic
Tuesday, 2:00pm – 4:00pm, room 3309 (Graduate Center)
December 1 meeting
Speaker: Sergei Artemov, CUNY Graduate Center
Title: Beyond Nash
The knowledge-based rational decision model (KBR-model) suggests following a strategy yielding the highest payoff which the agent can secure to the best of his knowledge. Special (extreme) cases of KBR in perfect information (PI) games are the backward induction solution which assumes common knowledge of rationality, and the pure maximin solution which assumes ignorance of each other rationality. In this talk, we prove a conjecture by A. Brandenburger that in PI games each KBR-path is a Nash path. Therefore, Nash equilibria capture KBR-solutions for all epistemic states of rational players, but cannot distinguish between them. Time permitting, we discuss epistemic means to win games against a rational opponent and outline corresponding research directions. Suggested reading: https://tr.cs.gc.cuny.edu/tr/techreport.php?id=386
November 24 meeting
Speaker: Walter Dean, CUNY Graduate Center/ U of Warwick, UK
Title: Epistemic Paradox and Explicit Modal Logic (Ph.D. dissertation defense)
The dissertation concerns the reconstruction of two well-known puzzles about knowledge in the context of explicit modal logic (aka Justification Logic) as developed by Artemov and Fitting. The Knower Paradox (which is due to Montague and Kaplan [1960]) threatens to show that plausible epistemic principles are incompatible with the existence of self-referential statements involving knowledge (e.g. “This sentence is true if I do not know it is true”). The Knowability Paradox (which is due to Fitch [1963]) threatens to show that the verificationist credo “If P is true, then P is knowable” is inconsistent with the existence of unknown truths.
In this presentation, I will first present the original derivations of the paradoxes. I will then present a variant of Fitting’s [2008] Quantified Logic of Proofs [QLP] in which to reconstruct these derivations. I will argue that the reconstructions offer additional insight into the original puzzles themselves and also shed light on a number of technical and conceptual questions about QLP and its potential epistemic interpretation.
November 19, 2:00-3:30 PM.
Room: 4422 – MIND THE ROOM CHANGE!
Speaker: Evan Goris, CUNY Graduate Center
Title: Logical Analysis of Cryptographic Protocols.
This talk contains an overview on some selected topics on formal analysis of security protocols: BAN Logic, Systems and Runs Framework, and Dynamic Epistemic Logic. This is the second PhD exam for the speaker.
November 10 meeting
Speaker: Antonis Achilleos, CUNY Graduate Center
Title: Justification Logic: Complexity Bounds for One or More Agents.
In this talk, the known bounds for the complexity of a variety of justification logics will be presented, together with the techniques needed to prove these bounds. Perhaps surprisingly, these techniques can be extended in a natural way to prove similar bounds for multi-agent variations of these logics.
November 3 meeting
1. Speaker: Alexander Gavryushkin, Novosibirsk/Notre Dame
Title: Spectra of Decidable Models of Ehrenfeucht Theories
The talk is an introduction to problems, connecting with spectra of decidable (computable) models of Ehrenfeucht theories. We will present essential definitions and preliminaries. We also construct several new examples of different spectra as for decidable as for computable case.
2. Speaker: Alexandra Gavryushkina, Novosibirsk/Notre Dame
Title: On Automatic Linear and Partial Orders
I will talk about the problem of existence of a computable isomorphism between any two automatic presentations of an automatic scattered linear order. Also the complexity of isomorphism types of automatic partial orders will be mentioned.
October 27 meeting
Speaker: Loes Olde Loohuis, CUNY Graduate Center
Title: Obligations in a Responsible World.
In this talk we propose an extension of Horty’s framework of deontic logic. We suggest defining obligations under the assumption that agents are responsible, and we will see how this assumption solves some objections raised to Horty’s system. Also, we discuss how the assumption of a responsible world can (not easily) be incorporated into the framework of knowledge based obligations introduced by Pacuit, Parikh and Cogan.
October 20 meeting
Speaker: Sergei Artemov, CUNY Graduate Center
Title: Rational decisions in non-probabilistic settings.
The knowledge-based rational decision model KBR-model is built on explicit epistemic reading of standard game-theoretical assumptions, e.g., Harsanyi’s Maximin Postulate, in a non-probabilistic setting. This model suggests following maximin strategy over all scenarios which the agent considers possible to the best of his knowledge.
In this talk, we show that KBR is the only non-probabilistic decision making method which is definitive, rational, and based exclusively on knowledge. We analyze other decision methods: Nash equilibrium and subgame perfect equilibrium, backward induction solution, pure maximin, eliminating dominated strategies, and for each of these cases indicate which of three properties definitive, rational, or based exclusively on knowledge fails.
October 13 meeting
Speaker: Bakhadyr Khoussainov, Cornell/University of Auckland, NZ
Title: Infinite games played on finite graphs: decidability and complexity
In this talk we will study infinite games on finite graphs played between two players, Player 0 and Player 1. The winning conditions for these games are defined through the acceptance conditions used in automata theory. To solve a given game means to find out which player is the winner of the game. The games we discuss are natural objects of study in complexity theory. The games are also used to model reactive systems, communication and update networks, and processes of infinite duration. Through these games one can address issues on realizability of specifications, correct program synthesis and optimization of control programs. Our goal will be to provide several decidability and complexity results in solving the games.
October 6 meeting
Speaker: Can Baskent, CUNY Graduate Center
Title: Meditations on Subset Space Logic
In this talk, after providing a brief overview of the subject, I will discuss subset spaces from dynamic epistemic and game theoretical perspectives. First, I will show that subset space logic is complete for public announcement logic. Second, I will provide an extension of game logic with epistemic modalities interpreted in subsets. Our aim is to provide a geometric touch to dynamic epistemology and game logic.
September 22 meeting
Speaker: Sergei Artemov, CUNY Graduate Center
Title: Belief-Based Rational Decisions
We extend a mathematical model of rational decision making from a case of knowledge to one of beliefs. The existence and uniqueness of the game solution theorem holds, as does Aumann’s Theorem on rationality of perfect information games and its stronger forms. Our “no cross-knowledge of rationality” solution of the Centipede game also has a belief counterpart with better epistemic assumptions than those of Aumann’s Theorem. The same holds for all strictly competitive games.
September 15 meeting
Speaker: Melvin Fitting, CUNY Graduate Center
Title: Intensions Axiomatized
This is work that was published in 2005, but I haven’t talked about it at CUNY yet. In a first-order modal logic I introduced, called FOIL (first-order intensional logic), there are quantifiers over both objects and intensions, where intensions are modeled Carnap style as functions from possible worlds to objects. Partial functions are actually more natural than total functions for modeling intensions because something like “the present King of France” doesn’t designate in the current world, for instance. There is a “predicate abstraction” operator in FOIL, whose origins can be traced back to Russell (though he probably wouldn’t recognize this). The semantics for all this, and tableau rules, are rather natural and simple. The problem is axiomatization.
Normal modal logics are well-known. Regular modal logics less so. It turns out that an axiomatization for FOIL with predicate abstraction, but without quantifiers, can be based on the idea that each predicate abstraction operator is a regular modal operator. Requiring normality amounts to assuming intensions always designate. Soundness and completeness can then be proved, though the arguments almost certainly do not extend all the way to S5. It is interesting to see why not.
I’ll fill in the necessary background, so general familiarity with modal logic should be sufficient. The completeness argument will not be presented in detail, but the central ideas will be discussed.
The paper on which the talk is based is available on my web site, “FOIL axiomatized.” There is also a short correction available, though it is technical in nature.
September 1 meeting
Speaker: Sergei Artemov, CUNY Graduate Center
Title: Knowledge-Based Rational Decisions
We outline a mathematical model of rational decision-making based on standard game-theoretical assumptions:
1) rationality yields a payoff maximization given the player’s knowledge;
2) the standard logic of knowledge for Game Theory is the modal logic S5.
Within this model, each game has a solution and rational players know which moves to make at each node. We demonstrate that uncertainty in games of perfect information results exclusively from players’ different perceptions of the game. In strictly competitive perfect information games, any level of players’ knowledge leads to the backward induction solution which coincides with the maximin solution. The same result holds for the well-known centipede game: its standard `backward induction solution’ does not require any mutual knowledge of rationality.