𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the computability of Nash equilibria

✍ Scribed by Kislaya Prasad

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
763 KB
Volume
21
Category
Article
ISSN
0165-1889

No coin nor oath required. For personal study only.

✦ Synopsis

We present some algorithmic unsolvability and incompleteness results in game theory and discuss their significance.

The main theorem presents a class of n-person games, where each player's strategy set is the real line and payoffs are continuous functions, for which there could not possibly exist an algorithm to compute either a Nash equilibrium or an E-equilibrium. Conditions sufficient to ensure solvability are also discussed.

πŸ“œ SIMILAR VOLUMES

Computing Nash equilibria by iterated po
Computing Nash equilibria by iterated polymatrix approximation
✍ Srihari Govindan; Robert Wilson πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 249 KB

This article develops a new algorithm for computing Nash equilibria of N -player games. The algorithm approximates a game by a sequence of polymatrix games in which the players interact bilaterally. We provide su cient conditions for local convergence to an equilibrium and report computational exper

On the relationship between Nashβ€”Cournot
On the relationship between Nashβ€”Cournot and Wardrop equilibria
✍ A. Haurie; P. Marcotte πŸ“‚ Article πŸ“… 1985 πŸ› John Wiley and Sons 🌐 English βš– 568 KB

A noncooperative game is formulated on a transportation network with congestion. The players are associated with origin-destination pairs, and are facing demand functions at their respective destination nodes. A Nash-Cournot equilibrium is defined and conditions for existence and uniqueness of this