Abstract
The computation of equilibria in games is a challenging task. The literature studies the problem of finding Nash equilibria with complete-information games in depth, but not enough attention is paid to searching for equilibria in Bayesian games. Customarily, these games are reduced to complete information games and standard algorithms for computing Nash equilibria are employed. However, no work studied how these algorithms perform with Bayesian games. In this paper we focus on two-player strategic-form games. We show that the most efficient algorithm for computing Nash equilibria with GAMUT data (i.e., Porter-Nudelman-Shoham) is inefficient with Bayesian games, we provide an extension, and we experimentally evaluate its performance.
Original language | English |
---|---|
Title of host publication | Web Intelligence and Intelligent Agent Technologies, 2009. WI-IAT '09. IEEE/WIC/ACM International Joint Conferences on |
Publisher | IET |
Pages | 541-548 |
Number of pages | 8 |
Volume | 2 |
ISBN (Electronic) | 978-1-4244-5331-3 |
ISBN (Print) | 978-0-7695-3801-3 |
DOIs | |
Publication status | Published - 1 Sept 2009 |
Keywords / Materials (for Non-textual outputs)
- Bayesian methods
- Conferences
- Game theory
- Intelligent agent
- Mathematical programming
- Mobile robots
- Nash equilibrium
- Security
- Uncertainty
- Algorithmic game theory
- Bayes-Nash equilibrium
- enumeration algorithm