Pavel Naumov

The article studies the interplay between obligations, knowledge, and abilities. It introduces the notion of norm-dependent abilities–something that an agent knows how to achieve using a knowingly allowed action and assuming that the other agents also use only knowingly allowed actions. The main technical contribution is a sound and complete logical system that describes the interplay between the modalities representing knowledge, obligations, and norm-dependent abilities in the presence of information walls between the agents.

The article introduces two modalities representing knowledge about the subjective and objective current moment of time. It provides formal semantics of these modalities, shows that the modalities are not definable through each other, and gives a sound and complete axiomatisation of their interplay. The axiomatisation contains an unusual Insertion inference rule generalising the Necessitation rule. The article proves that the Insertion rule is not derivable from the other axioms and inference rules.

Two different forms of responsibility, counterfactual and seeing-to-it, have been extensively discussed in philosophy in the context of a single agent or multiple agents acting simultaneously. Although the generalisation of counterfactual responsibility to a setting where multiple agents act in some order is relatively straightforward, the same cannot be said about seeing-to-it responsibility. Two versions of seeing-to-it modality applicable to such settings have been proposed in the literature. Neither of them perfectly captures the intuition of responsibility. This paper proposes a definition of seeing-to-it responsibility for such settings that amalgamate the two modalities. This paper shows that counterfactual responsibility and the newly proposed notion of responsibility are not definable via each other. It also studies the higher-order responsibility and the responsibility gap for these two forms of responsibility. It shows that although these two forms of responsibility are not enough to ascribe responsibility in each possible situation, this gap does not exist if higher-order responsibility is taken into account.

There are two distinct forms of responsibility that can be found in literature: counterfactual responsibility and responsibility for “seeing to it that.” It has been previously observed that, in the case of strategic games, the counterfactual form of responsibility can be defined through responsibility for “seeing to it that,” but not the other way around. We consider these two forms of responsibility in the case of infinite extensive form games. The main technical result is that, in this new setting, neither of the two forms of responsibility can be defined through the other. Some preliminary results for finite extensive form games are also given.

With agents relying more and more on information from central servers rather than their own sensors, knowledge becomes property not of a specific agent but of the data that the agents can access. The article proposes a dynamic logic of data-informed knowledge that describes an interplay between three modalities and one relation capturing the properties of this form of knowledge. The main technical results are the undefinability of two dynamic operators through each other, a sound and complete axiomatisation, and a model checking algorithm.

Traditionally, the formulae in modal logic express properties of possible worlds. Prior introduced “egocentric” logics that capture properties of agents rather than of possible worlds. In such a setting, the article proposes the modality “know how to tell apart” and gives a complete logical system describing the interplay between this modality and the knowledge modality. An important contribution of this work is a new matrix-based technique for proving completeness theorems in an egocentric setting.

The paper considers a commonly used axiomatization of the classical propositional logic and studies how different axiom schemata in this system contribute to proof complexity of the logic. The existence of a polynomial bound on proof complexity of every statement provable in this logic is a well-known open question.The axiomatization consists of three schemata. We show that any statement provable using unrestricted number of axioms from the first of the three schemata and polynomially-bounded in size set of axioms from the other schemata, has a polynomially-bounded proof complexity. In addition, it is also established, that any statement, provable using unrestricted number of axioms from the remaining two schemata and polynomially-bounded in size set of axioms from the first scheme, also has a polynomially-bounded proof complexity

The classical propositional logic is known to be sound and complete with respect to the set semantics that interprets connectives as set operations. The paper extends propositional language by a new binary modality that corresponds to partial recursive function type constructor under the above interpretation. The cases of deterministic and non-deterministic functions are considered and for both of them semantically complete modal logics are described and decidability of these logics is established.

The article studies preferences of agents in a setting with imperfect information. For such a setting, the authors propose a new class of preferences. It is said that an agent prefers one statement over another if, among all indistinguishable worlds, the agent prefers the worlds where the first statement is true to those where the second one is true. The main technical result is a sound and complete logical system describing the interplay between a binary modality capturing preferences and the knowledge modality. The proof of completeness is using a newly proposed “tumbled pairs” technique.

Modal logic S5 is commonly viewed as an epistemic logic that captures the most basic properties of knowledge. Kripke proved a completeness theorem for the first-order modal logic S5 with respect to a possible worlds semantics. A multiagent version of the propositional S5 as well as a version of the propositional S5 that describes properties of distributed knowledge in multiagent systems has also been previously studied. This article proposes a version of S5-like epistemic logic of distributed knowledge with quantifiers ranging over the set of agents, and proves its soundness and completeness with respect to a Kripke semantics.

Diffusion in social networks is a result of agents’ natural desires to conform to the behavioral patterns of their peers. In this article we show that the recently proposed “propositional opinion diffusion model” could be used to model an agent’s conformity to different social groups that the same agent might belong to, rather than conformity to the society as whole. The main technical contribution of this article is a sound and complete logical system describing the properties of the influence relation in this model. The logical system is an extension of Armstrong’s axioms from database theory by one new axiom that captures the topological structure of the network.