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]

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]

R.E. Axiomatization of Conditional Independence

Pavel Naumov and Brittany Nicholls

The paper investigates properties of the conditional independence relation between pieces of information. This relation is also known in the database theory as embedded multi-valued dependency. In 1980, Parker and Parsaye-Ghomi established that the properties of this relation can not be described by a finite system of inference rules. In 1995, Herrmann proved that the propositional theory of this relation is undecidable. The main result of this paper is a complete recursively enumerable axiomatization of this theory. [pdf]