On the Non-Existence of Nash Equilibrium in Games with Resource-Bounded Players

preprint2015arXivOpen access

Abstract

We consider sequences of games G={G1,G2,…}\mathcal{G}=\{G_1,G_2,\ldots\} where, for all nn, GnG_n has the same set of players. Such sequences arise in the analysis of running time of players in games, in electronic money systems such as Bitcoin and in cryptographic protocols. Assuming that one-way functions exist, we prove that there is a sequence of 2-player zero-sum Bayesian games G\mathcal{G} such that, for all nn, the size of every action in GnG_n is polynomial in nn, the utility function is polynomial computable in nn, and yet there is no polynomial-time Nash equilibrium, where we use a notion of Nash equilibrium that is tailored to sequences of games. We also demonstrate that Nash equilibrium may not exist when considering players that are constrained to perform at most TT computational steps in each of the games {Gi}i=1∞\{G_i\}_{i=1}^{\infty}. These examples may shed light on competitive settings where the availability of more running time or faster algorithms lead to a "computational arms race", precluding the existence of equilibrium. They also point to inherent limitations of concepts such "best response" and Nash equilibrium in games with resource-bounded players.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.