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]

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]