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]

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]

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]

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]

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]