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]
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]
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]
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]
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]