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]

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]

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]