Logic, Rationality, and Interaction

We introduce and formally study games in which the goals of players relate to the epistemic states of players in the game. For example, one player might have a goal that another player knows a certain proposition, while another player might have as a goal that a certain player does not know some proposition. The formal model we use to study epistemic games is a variation of the increasingly popular

Boolean games

model in which each player controls a number of Boolean variables, but has limited ability to see the truth values of the overall set of formulae that hold in the game. Each player in an

epistemic Boolean game

has a goal, defined as a formula of modal epistemic logic. Using such a language for goals allows us to explicitly and compactly represent desirable epistemic states. After motivating and formally defining epistemic Boolean games as a concise representation of epistemic Kripke structures, we investigate their complexity and study their properties.

We propose a novel approach to preference change. We treat a set of preferences as a special kind of theory, and define minimal change contraction and revision operations in the spirit of minimal change as advocated by the Alchourron, Gardenfors, and Makinson (AGM) theory of belief revision. We characterise minimal contraction of preference sets by a set of postulates and prove a representation theorem. We also give a linear time algorithm which implements minimal contraction by a single preference. We also define minimal contraction by a set of preferences, and for a significant special case state postulates, prove a representation theorem, and provide an efficient algorithm implementing minimal contraction by a set of preferences.

We present a new topological semantics for doxastic logic, in which the belief modality is interpreted as the closure of the interior operator. We show that this semantics is the most general (extensional) semantics validating Stalnaker’s epistemic-doxastic axioms [22] for “strong belief”, understood as

subjective certainty

. We prove two completeness results, and we also give a topological semantics for update (dynamic conditioning), i.e. the operation of revising with “hard information” (modeled by restricting the topology to a subspace). Using this, we show that our setting fits well with the defeasibility analysis of knowledge [18]: topological knowledge coincides with undefeated true belief. Finally, we compare our semantics to the older topological interpretation of belief in terms of Cantor derivative [23].

Planning and plan recognition are arguably essential to all rational, co-operative activities, and linguistic communication is no exception. Recently, Lewis (2012) argues that recognizing the importance of plan helps settle a debate regarding the semantics and pragmatics of indefinites. More specifically, Lewis argues against the dynamic approach (e.g. Kamp (1981), Heim (1982), Groenendijk and Stokhof (1991), Kamp and Reyle (1993), and Asher and Lascarides (2003)), according to which indefinites are subject to a

semantic

“Novelty” condition; instead, she offers a neo-Gricean account and analyzes Novelty as a pragmatic, cancelable implicature. I argue that Lewis’ analysis is inadequate. Her pragmatic picture not only rests on dubious assumptions concerning plan recognition, but offers no real explanation of the alleged counterexamples against the dynamic theories. Moreover, I provide evidence that supports a more semantic analysis of the Novelty condition.

In this paper, I will develop a semantic model for interrogatives, an important sentence type expressing a special aspect of uncertainty. The model is based on the notions of generalized quantifiers and bilattices, and is used to model several aspects of interrogative semantics, including resolvedness conditions, answerhood, exhaustivity and interrogative inferences. It will be shown that the semantic model satisfies a number of adequacy criteria.

We propose a new dynamic hybrid logic to reason about social networks and their dynamics building on the work of “Logic in the Community” by Seligman, Liu and Girard. Our framework distinguishes between the purely private sphere of agents, namely their mental states, and the public sphere of their observable behavior, i.e., what they seem to believe. We then show how such a distinction allows our framework to model many social phenomena, by presenting the case of pluralistic ignorance as an example and discussing some of its dynamic properties.

In this paper, we re-explain four types of players’ rationality from the viewpoint of strategy-choosing regret, and we provide a unified logic of epistemic characterization of the four iterated elimination algorithms IESD (Iterated Elimination Strictly Dominated strategy), Rationalizablity (also called iterated elimination strategies that are never best responses), IA (Iterated Admissibility) and IERS (Iterated Elimination Regret-dominated Strategy). The unified characterization extends van Benthem’s work of linking game theory with epistemic logic and provides further insights into exploring the rationale of these iterated eliminating algorithms. In addition, to clarify the proof-theoretic principles assumed in players’ reasoning, we also develop an axiomatic presentation for our results.

In public announcement logic it is assumed that all agents pay attention (listen to/observe) to the announcement. Weaker observational conditions can be modelled in event (action) model logic. In this work, we propose a version of public announcement logic wherein it is encoded in the states of the epistemic model which agents pay attention to the announcement. This logic is called attention-based announcement logic, abbreviated

ABAL

. We give an axiomatization and prove that complexity of satisfiability is the same as that of public announcement logic, and therefore lower than that of action model logic [2]. We exploit our logic to formalize the concept of joint attention that has been widely discussed in the philosophical and cognitive science literature. Finally, we extend our logic by integrating attention change.

We study a recently introduced extension of normal form games with a phase before the actual play of the game, where each player can make binding offers for payments of utility to the other players after the play of the game, contingent on the recipient playing the strategy indicated in the offer. Such offers transform the payoff matrix of the original game and allow for some degree of cooperation between rational players while preserving the non-cooperative nature of the game. We focus on 2-player negotiations games arising in the preplay phase when offers for payments are made conditional on a suggested matching offer of the same kind being made in return by the receiver. We study and analyze such bargaining games, obtain results describing their possible solutions and discuss the degrees of efficiency and fairness that can be achieved in such negotiation process depending on whether time is valuable or not.

This paper studies Gentzen-style sequent calculi for multi-modal logics with interaction between the modalities. We prove cut elimination and some of its usual corollaries for two such logics: Standard Deontic Logic with the Ought-implies-Can principle, and a non-normal deontic logic where obligation, permissions and abilities interact in a complex way. The key insight of these results is to make rules sensitive to the shape of the formulas on either sides of the sequents. This way one can devise rules in a much more modular fashion. This feature of Hilbert-style systems is notoriously lost when one moves to sequent calculi. By partly restoring modularity the method proposed here can potentially provide a unified approach to the proof theory of multi-modal systems.

We introduce a display calculus for the logic of Epistemic Actions and Knowledge (EAK) of Baltag-Moss-Solecki. This calculus is

cut-free

and

complete

w.r.t. the standard Hilbert-style presentation of EAK, of which it is a

conservative extension

, given that—as is common to display calculi—it is defined on an expanded language in which all logical operations have adjoints. The additional dynamic operators do not have an interpretation in the standard Kripke semantics of EAK, but do have a natural interpretation in the final coalgebra. This proof-theoretic motivation revives the interest in the global semantics for dynamic epistemic logics pursued among others by Baltag [4], Cîrstea and Sadrzadeh [8].

The paper introduces a notion of cellular game that is intended to represent rationally behaving cells of a cellular automaton. The focus is made on studying properties of functional dependence between strategies of different cells in a Nash equilibrium of such games. The main result is a sound and complete axiomatization of these properties. The construction in the proof of completeness is based on the Fibonacci numbers.

We introduce

ATLEA

, a novel extension of Alternating-time Temporal Logic with explicit actions in the object language.

ATLEA

allows to reason about abilities of agents under commitments to play certain actions. Pre- and postconditions as well as availability and unavailability of actions can be expressed. We show that the multiagent extension of Reiter’s solution to the frame problem can be encoded into

ATLEA

. We also consider an epistemic extension of

ATLEA

. We demonstrate that the resulting logic is sufficiently expressive to reason about uniform choices of actions. Complexity results for the satisfiability problem of

ATLEA

and its epistemic extension are given in the paper.

We aim to present a deontic logic with updates as an extension of Boolean Modal Logic. The features of this logic include the following: (a) deontic relations are defined on sets of finite sequences of states, called histories, and consequently, formulas are evaluated at histories, not states; and (b) it has two dynamic operators, which tend to update the obligation states of agents in different ways. This logic reflects the distinction between the descriptive and prescriptive use of norm sentences.

In order to deal with ambiguity in statements made in a natural language I introduce nondeterministic semantics for propositional logic with an arbitrary set

C

of connectives. The semantics are based on the idea that Γ entails

$\varDelta$

if and only if every possible deterministic disambiguation of Γ entails every possible deterministic disambiguation of

$\varDelta$

. I also introduce a cut-free sequent style proof system

S

C

that is sound and complete for the given semantics. Finally I show that while the semantics and proof system do not satisfy reflexivity they do allow certain kinds of substitution of equivalents.

This paper studies two ways of updating neighborhood models: update by taking the intersection of the neighborhoods with the announced proposition, and update by selecting all the neighborhoods that can entail the announced proposition. For each of these two ways, we establish reduction axioms and some basic model-theoretic results on public announcement logic and dynamic epistemic logic of product update. We also study various notions of group knowledge such as common and distributed knowledge over neighborhood models.

We propose a logic for describing the interaction between knowledge, preference, and the freedom to act, and their interactions with the norms of

Priori

and a

Posteriori

rationality, which we have argued for in previous work [3]. We then apply it to strategic games to characterise weak dominance and Nash equilibrium.

This paper reports correspondence results between input/ output logic and the theory of joining-systems. The results have the form: every norm (

a

,

x

) is logically derivable from a set of norms

G

if and only if it is in the space of norms algebraically generated by

G

.

Under relational models, epistemic logic agents are logically omniscient. A common strategy to avoid this has been to distinguish between

implicit

and

explicit

knowledge, and approaches based on relational models have used implicit knowledge as a primitive, defining explicit knowledge as implicit knowledge that satisfies some additional requirement. In this work we follow the opposite direction: using neighbourhood models, we take explicit knowledge as a primitive, then defining implicit knowledge as what the agent will know explicitly in an ‘ideal’ state. This approach, though natural, does not satisfy two ‘intuitive’ properties: explicit knowledge does not need to be implicit, and the consequent of an explicitly known implication with explicitly known antecedent does not need to be implicitly known; we discuss why this is the case. Then a modus ponens operation is defined, and it is shown how it satisfies a third ‘intuitive’ property: if the agent knows explicitly an implication and its antecedent, then after a modus ponens step she will know explicitly the consequent.

We study the expressivity hierarchy of languages for epistemic awareness models based on the operators for implicit and explicit knowledge, implicit and explicit possibility and awareness, providing in each case an expressivity characterisation in terms of bisimulation.

In this paper we take the S5 definition of knowledge, and have a new look at logics combining modalities for public announcements, action models, common knowledge and relativized common knowledge. In particular, we prove two expressivity results which previously have only been shown for the case where knowledge is represented using arbitrary Kripke models but have remained open for the case of S5 models: public announcement logic with relativized common knowledge is strictly more expressive than public announcement logic with common knowledge, and action model logic with common knowledge is strictly more expressive than public announcement logic with common knowledge. We also propose and study a definition of relativized common knowledge for action model logic.

We study the possibility and impossibility of aggregating logics, which may come from different sources (individuals, agents, groups, societies, cultures). A logic is treated as a binary relation between sets of formulas and formulas (or a set of accepted arguments). Logic aggregation is treated as argument-wise. We prove that certain logical properties can be preserved by some desired aggregation functions, while some other logical properties cannot be preserved together under non-degenerate aggregation functions, as long as some natural conditions for the aggregation function are satisfied. We compare our framework of logic aggregation with other aggregation frameworks, including preference aggregation and judgment aggregation.

To develop a court argumentation system of three agents: a plaintiff, a defendant, and a judge, this paper constructs task models of courtroom investigation. More specifically, we develop the algorithms of evidence questioning and evaluation, and establish a mechanism for fact finding, which consists of

evidence-claim

networks and evidence aggregation. Finally, we illustrate our system with a real legal scenario.

Here we choose an object-oriented approach to model a deontic action logic. The interpretation of an action, related to its execution circumstance, is a set of events charactered by a structure, named event-base, which satisfies some algebra properties. Different from Modal Action Logic (MAL), this structure is not a Boolean one, but reflects the algebra properties of sequent actions and true concurrent actions. At last, our work includes an axiomatic system for deontic complex actions as well as its completeness.

A growing community investigates planning using dynamic epistemic logic. Another framework based on similar ideas is knowledge-based programs as plans. Here we show how actions correspond in the two frameworks. We finally discuss fragments of DEL planning obtained by the restriction of event models. Fragments are separated by virtue of their computational complexity.

This paper presents a quasi-lexicographic judgment aggregation rule based on the hierarchy of judges. We do not assume completeness at both individual and collective levels, which means that a judge can abstain from a proposition and the collective judgment on a proposition can be undetermined. We prove that the proposed rule is (weakly) oligarchic. This is by no means a negative result. In fact, our result demonstrates that with abstentions, oligarchic aggregation is not necessarily a single level determination but can be a multiple-level democracy, which partially explains its pervasiveness in the real world.

This paper tackles some conceptual problems in the epistemic foundations of classical game theory. Focus is placed on the discussions of the asymmetry of different epistemic standpoints in modeling a game and the thesis of no subjective probability for self-action in games.

To characterize the structures and reason about strategies of extensivegames,much work has been done to provide the logical systems for such games. These logic systems focus on various perspectives of extensive games: (Harrenstein

et al.

, 2003) concentrated on describing equilibrium concepts and strategic reasoning. (van Benthem, 2002) used dynamic logic to describe games as well as strategies.

In the 1992 paper [1] Bikchandani et al. show how it may be rational for Bayesian agents in a sequential decision making scenario to ignore their private information and conform to the choices made by previous agents. If this occurs, an agent ignoring her private information is said to be

in a cascade

.

According to the principle of minimal change, an agent should not change her belief state more than is strictly required to accomodate new information. We propose a novel approach to the issue by considering a notion of optimality of belief revision policies that is sensitive to the

target of revision

.

This paper presents logics for reasoning about

sound enough evidence

and its relation to evidence and knowledge. The logic of sound enough evidence is based on van Benthem and Pacuit’s evidence logic and Holliday’s formalization of Nozick’s tracking theory. And the newly defined knowledge based on

sound enough evidence

does not imply the evidence-based belief but respects the epistemic closure. The related philosophical issues are also discussed.

We prove that the computational problem of finding backward induction outcome is PTIME-complete.

Pan pointed out that there are three kinds of different negations: contradictory negation, opposite negation and medium negation. He also proposed the novel fuzzy set FScom with the above three kinds of negations, followed by one improved fuzzy set IFScom that is established based on FScom. In this paper, a novel fuzzy propositional logic calculus system that equipped with three kinds of negations is set up to correspond to the FScom and IFScom. The soundness theorem and completeness theorem of the system is proved.