Computing pure Bayesian-Nash equilibria in games with finite actions and continuous types
OA Location
Author(s)
Rabinovich, Zinovi
Naroditskiy, Victor
Gerding, Enrico H
Jennings, Nicholas R
Type
Journal Article
Abstract
We extend the well-known fictitious play (FP) algorithm to compute pure-strategy Bayesian-Nash equilibria in private-value games of incomplete information with finite actions and continuous types (G-FACTs). We prove that, if the frequency distribution of actions (fictitious play beliefs) converges, then there exists a pure-strategy equilibrium strategy that is consistent with it. We furthermore develop an algorithm to convert the converged distribution of actions into an equilibrium strategy for a wide class of games where utility functions are linear in type. This algorithm can also be used to compute pure \ensuremathε-Nash equilibria when distributions are not fully converged. We then apply our algorithm to find equilibria in an important and previously unsolved game: simultaneous sealed-bid, second-price auctions where various types of items (e.g., substitutes or complements) are sold. Finally, we provide an analytical characterization of equilibria in games with linear utilities. Specifically, we show how equilibria can be found by solving a system of polynomial equations. For a special case of simultaneous auctions, we also solve the equations confirming the results obtained numerically.
Date Issued
2013-02
Citation
Artificial Intelligence, 2013, 195, pp.106-139
Start Page
106
End Page
139
Journal / Book Title
Artificial Intelligence
Volume
195
Identifier
http://eprints.soton.ac.uk/343596/
Subjects
Science & Technology
Technology
Computer Science, Artificial Intelligence
Computer Science
COMPUTER SCIENCE, ARTIFICIAL INTELLIGENCE
Algorithmic game theory
Bayes-Nash equilibrium
Epsilon-Nash equilibrium
Fictitious play
Simultaneous auctions
SIMULTANEOUS AUCTIONS
FICTITIOUS PLAY
UPPER ENVELOPE
ALGORITHMS
SYNERGIES
SELLERS
Artificial Intelligence & Image Processing
0801 Artificial Intelligence And Image Processing
1702 Cognitive Science
Notes
keywords: algorithmic game theory, bayes-nash equilibrium, epsilon-nash equilibrium, fictitious play, simultaneous auctions