Azimipour, Sanaz and Pavel Naumov. “Lighthouse Principle for Diffusion in Social Networks.” Journal of Applied Logics-IfCoLoG Journal of Logics and Their Applications, vol. 5, issue 1, 2018, pp. 97-120.
Abstract: The article investigates an influence relation between two sets of agents in a social network. It proposes a logical system that captures propositional properties of this relation valid in all threshold models of social networks with the same structure. The logical system consists of Armstrong axioms for functional dependence and an additional Lighthouse axiom. The main results are soundness, completeness, and decidability theorems for this logical system.
Deuser, Kaya and Pavel Naumov. “Armstrong’s Axioms and Navigation Strategies.” Proceedings of 32nd AAAI Conference on Artificial Intelligence, AAAI-18, 2018, pp. 6343-6350.
Abstract: The paper investigates navigability with imperfect information. It shows that the properties of navigability with perfect recall are exactly those captured by Armstrong's axioms from database theory. If the assumption of perfect recall is omitted, then Armstrong's transitivity axiom is not valid, but it can be replaced by a weaker principle. The main technical results are soundness and completeness theorems for the logical systems describing properties of navigability with and without perfect recall.
Deuser, Kaya and Pavel Naumov. “Navigability with Bounded Recall.” Proceedings of the Sixteenth International Conference on Principles of Knowledge Representation and Reasoning, KR-18, 2018, pp. 635-636.
Abstract: The paper studies navigability by machines with bounded recall in mazes with imperfect information. The main result is a sound and complete logical system for the relation “there is a machine with at most n states that can navigate from a set of classes of indistinguishable rooms X to a set of classes of indistinguishable rooms Y ”. The axioms of the system generalize Armstrong’s axioms of functional dependency from database theory.
Deuser, Kaya and Pavel Naumov. “Navigability with Intermediate Constraints.” Journal of Logic and Computation, vol. 28, issue 7, 2018, pp. 1647-1670.
Abstract: The article studies navigability of an autonomous agent in a maze where some rooms may be indistinguishable. In a previous work the authors have shown that the properties of navigability in such a setting depend on whether an agent has perfect recall. Navigability by strategies with perfect recall is a transitive relation and navigability by memoryless strategies is not. Independently, Li and Wang proposed a notion of navigability with intermediate constraints for linear navigation strategies. Linear strategies are different from both perfect recall and memoryless strategies. This article shows that a certain form of transitivity, expressible in the language with intermediate constraints, holds for memoryless strategies. The main technical result is a sound and complete logical system describing the properties of memoryless strategies in the language with intermediate constraints.
Naumov, Pavel and Kevin Ros. “Strategic Coalitions in Systems with Catastrophic Failures.” Proceedings of the Sixteenth International Conference on Principles of Knowledge Representation and Reasoning, KR-18, 2018, pp. 659-660.
Abstract: The paper introduces a notion of a transition system with catastrophic failures where in each state and under each action profile of the agents the system might either transition to a next state or fail with a given probability. The main technical result is a sound and complete axiomatization of modality “coalition has a strategy to survive with a given probability while achieving a given goal.”
Naumov, Pavel and Jia Tao. “Second-Order Know-How Strategies.” Proceedings of the Seventeenth International Conference on Autonomous Agents and Multiagent Systems, AAMAS-18, 2018, pp. 390-398.
Abstract: The fact that a coalition has a strategy does not mean that the coalition knows what the strategy is. If the coalition knows the strategy, then such a strategy is called a know-how strategy of the coalition. The paper proposes the notion of a second-order know-how strategy for the case when one coalition knows what the strategy of another coalition is. The main technical result is a sound and complete logical system describing the interplay between the distributed knowledge modality and the second-order coalition know-how modality.
Naumov, Pavel and Jia Tao. “Strategic Coalitions with Perfect Recall.” Proceedings of the 32nd AAAI Conference on Artificial Intelligence, AAAI-18, 2018, pp. 4702-4709.
Abstract: The paper proposes a bimodal logic that describes an interplay between distributed knowledge modality and coalition know-how modality. Unlike other similar systems, the one proposed here assumes perfect recall by all agents. Perfect recall is captured in the system by a single axiom. The main technical results are the soundness and the completeness theorems for the proposed logical system.
Naumov, Pavel and Jia Tao. “Together We Know How to Achieve: An Epistemic Logic of Know-How.” Artificial Intelligence, vol. 262, 2018, pp. 279-300.
Abstract: The existence of a coalition strategy to achieve a goal does not necessarily mean that the coalition has enough information to know how to follow the strategy. Neither does it mean that the coalition knows that such a strategy exists. The article studies an interplay between the distributed knowledge, coalition strategies, and coalition “know-how” strategies. The main technical result is a sound and complete trimodal logical system that describes the properties of this interplay.