Computing Bayes-Nash Equilibria through Support Enumeration Methods in Bayesian Two-Player Strategic-Form Games

Sofia Ceppi, Nicola Gatti, N. Basilico

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 languageEnglish
Title of host publicationWeb Intelligence and Intelligent Agent Technologies, 2009. WI-IAT '09. IEEE/WIC/ACM International Joint Conferences on
Number of pages8
ISBN (Electronic)978-1-4244-5331-3
ISBN (Print)978-0-7695-3801-3
Publication statusPublished - 1 Sep 2009


  • Bayesian methods
  • Conferences
  • Game theory
  • Intelligent agent
  • Mathematical programming
  • Mobile robots
  • Nash equilibrium
  • Security
  • Uncertainty
  • Algorithmic game theory
  • Bayes-Nash equilibrium
  • enumeration algorithm

Cite this