Kaya Deuser, Pavel Naumov
The article proposes a trimodal logical system that can express the strategic ability of coalitions to learn from their experience. The main technical result is the completeness of the proposed system. [PDF]
Price of Privacy
Pavel Naumov and Jia Tao
The paper proposes a logical framework for reasoning about agents' ability to protect their privacy by hiding certain information from a privacy intruder. It is assumed that the knowledge of the intruder is derived from the observation of pieces of evidence and that there is a cost associated with the elimination of the evidence.
The logical framework contains a modal operator labeled by a group of agents and a total budget available to this group. The key contribution of this work is the proposed incorporation of the cost factor into privacy protection reasoning within the standard modal logic framework. The main technical result are the soundness and completeness theorems for the introduced logical system with respect to a formally defined semantics. [pdf]
Marketing Impact on Diffusion in Social Networks
Pavel Naumov and Jia Tao
The paper proposes a way to add marketing into the standard threshold model of social networks. Within this framework, the paper studies logical properties of the influence relation between sets of agents in social networks. Two different forms of this relation are considered: one for promotional marketing and the other for preventive marketing. In each case a sound and complete logical system describing properties of the influence relation is proposed. Both systems could be viewed as extensions of Armstrong's axioms of functional dependency from the database theory. [pdf]
Lighthouse Principle for Diffusion in Social Networks
Sanaz Azimipour and Pavel Naumov
The article investigates 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 topological 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. [pdf]
Knowledge in Communication Networks
Pavel Naumov and Jia Tao
The paper investigates epistemic properties of information flow under communication protocols with a given topological structure of the communication network. The main result is a sound and complete logical system that describes all such properties. The system consists of a variation of the multi-agent epistemic logic S5 extended by a new network-specific Gateway axiom. [pdf]
The Budget-Constrained Functional Dependency
Pavel Naumov and Jia Tao
Armstrong's axioms of functional dependency form a well-known logical system that captures properties of functional dependencies between sets of database attributes. This article assumes that there are costs associated with attributes and proposes an extension of Armstrong's system for reasoning about budget-constrained functional dependencies in such a setting.
The main technical result of this article is the completeness theorem for the proposed logical system. Although the proposed axioms are obtained by just adding cost subscript to the original Armstrong's axioms, the proof of the completeness for the proposed system is significantly more complicated than that for the Armstrong's system. [pdf]
A Modal Logic for Reasoning about Economic Policies
Pavel Naumov and Jia Tao
The article introduces a modal logic for reasoning about combined effect of economic policies imposed on a group of rational agents. Modalities in this language are labeled by policies applied to the players in a strategic game. The resulting logical system allows to reason about properties that are true in all Nash equilibria of the game modified by a specific policy. The main technical result is the completeness theorem for the proposed logical system. [pdf]
Budget-Constrained Knowledge in Multiagent Systems
Pavel Naumov and Jia Tao
The paper introduces a modal logical system for reasoning about knowledge in which information available to agents might be constrained by the available budget. Although the system lacks an equivalent of the standard Negative Introspection axiom from epistemic logic S5, it is proven to be sound and complete with respect to an S5-like Kripke semantics. [pdf]
Logic of Confidence
Pavel Naumov and Jia Tao
The article studies knowledge in multiagent systems where data available to the agents may have small errors. To reason about such uncertain knowledge, a formal semantics is introduced in which indistinguishability relations, commonly used in the semantics for epistemic logic S5, are replaced with metrics to capture how much two epistemic worlds are different from an agent’s point of view. The main result is a logical system sound and complete with respect to the proposed semantics. [pdf]
Equilibria Interchangeability in Cellular Games
Pavel Naumov and Margaret Protzman
The notion of interchangeability has been introduced by John Nash in one of his original papers on equilibria. This article studies properties of Nash equilibria interchangeability in cellular games that model behavior of in nite chain of homogeneous economic agents. The article shows that there are games in the which strategy of any given player is interchangeable with strategies of players in an arbitrary large neighborhood of the given player, but is not interchangeable with the strategy of a remote player outside of the neighborhood. The main technical result is a sound and complete logical system describing universal properties of interchangeability common to all cellular games. [pdf]
Common Knowledge Semantics of Armstrong’s Axioms
Zachary Heckle and Pavel Naumov
Armstrong's axioms were originally proposed to describe functional dependency between sets of attributes in relational databases. The database semantics of these axioms can be easily rephrased in terms of distributed knowledge in multi-agent systems. The paper proposes alternative semantics of the same axioms in terms of common knowledge. The main technical result of this work is soundness and completeness of Armstrong's axioms with respect to the proposed semantics. An important implication of this result is an unexpected duality between notions of distributed and common knowledge. [pdf]
Conditional Interchangeability of Nash Equilibria
Pavel Naumov Margaret Protzman
The notion of interchangeability was introduced by Nash in one of his original papers on equilibria in strategic games. It has been recently shown that propositional theory of this relation is the same as propositional theories of the nondeducibility relation in the information ow theory, the independence relation in probability theory, and the noninterference relation in concurrency theory.
Propositional theories of conditional nondeducibility and conditional independence have been studied before. This article introduces a notion of conditional interchangeability and gives complete axiomatization of this relation with conditioning by a single player. [pdf]
The Ryoan-ji Axiom for Common Knowledge on Hypergraphs
Jeffrey Kane and Pavel Naumov
The article studies common knowledge in communication networks with a fi xed topological structure. It introduces a non-trivial principle, called the Ryoan-ji axiom, which captures logical properties of common knowledge of all protocols with a given network topology. A logical system, consisting of the Ryoan-ji axiom and two additional axioms, is proven to be sound and complete. [pdf]
Functional Dependence in Strategic Games
Kristine Harjes and Pavel Naumov
The article studies properties of functional dependencies between strategies of players in Nash equilibria of multi-player strategic games. The main focus is on the properties of functional dependencies in the context of a fi xed dependency graph for pay-off functions. A logical system describing properties of functional dependence for any given graph is proposed and is proven to be complete. [pdf]
Symmetry in Information Flow
Jeffrey Kane and Pavel Naumov
The article investigates information flow properties of symmetric multi-party protocols. It gives a sound and complete axiomatic system for properties of the functional dependence predicate that are common to all protocols with the same group of symmetries. [pdf]
Strict Equilibria Interchangeability in Multi-Player Zero-Sum Games
Pavel Naumov and Italo Simonelli
The interchangeability property of Nash equilibria in two-player zero- sum games is well-known. This paper studies possible generalizations of this property to multi-player zero-sum games. A form of interchangeability property for strict Nash equilibria in such games is established. It is also shown, by proving a completeness theorem, that strict Nash equilibria do not satisfy any other non-trivial properties. [pdf]
Rationally Functional Dependence
Pavel Naumov and Brittany Nicholls
Two different types of functional dependencies are compared: dependencies that are functional due to the laws of nature and dependencies that are functional if all involved agents behave rationally. The first type of dependencies was axiomatized by Armstrong. This article gives a formal definition of the second type of functional dependencies in terms of strategic games and describes a sound and complete axiomatization of their properties. The axiomatization is significantly different from the Armstrong’s axioms. [pdf]
Cellular Games, Nash Equilibria, and Fibonacci Numbers
Kristine Harjes and Pavel Naumov
The paper introduces a notion of cellular game that is in- tended 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. [pdf]
Symmetries and Epistemic Reasoning
Jeffrey Kane and Pavel Naumov
The paper studies epistemic properties of symmetric communication protocols. It proposes a logical system describing properties common to all protocols with the same group of symmetries. This system is an extension of the standard epistemic logic S5 by a new axiom, capturing properties of symmetry in the modal language. The main results are soundness and completeness theorems for this logical system. [pdf]
On Interchangeability of Nash Equilibria in Multi-Player Strategic Games
Pavel Naumov and Brittany Nicholls
The article studies properties of interchangeability of pure, mixed, strict, and strict mixed Nash equilibria. The main result is a sound and complete axiomatic system that describes properties of interchangeability in all four settings. It has been previously shown that the same axiomatic system also describes properties of independence in probability theory, nondeducibility in information flow, and non-interference in concurrency theory. [pdf]