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

Sofia Ceppi; Nicola Gatti; N. Basilico

doi:10.1109/WI-IAT.2009.209

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

Sofia Ceppi, Nicola Gatti, N. Basilico

School of Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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	https://doi.org/10.1109/WI-IAT.2009.209
Publication status	Published - 1 Sep 2009

Keywords

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

Access to Document

10.1109/WI-IAT.2009.209

http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5285123

Cite this

@inproceedings{69f22e9d82ce4c19b4b94a3e1eead9c5,

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

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.",

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

author = "Sofia Ceppi and Nicola Gatti and N. Basilico",

year = "2009",

month = sep,

day = "1",

doi = "10.1109/WI-IAT.2009.209",

language = "English",

isbn = "978-0-7695-3801-3",

volume = "2",

pages = "541--548",

booktitle = "Web Intelligence and Intelligent Agent Technologies, 2009. WI-IAT '09. IEEE/WIC/ACM International Joint Conferences on",

publisher = "IET",

}

Computing Bayes-Nash Equilibria through Support Enumeration Methods in Bayesian Two-Player Strategic-Form Games. / Ceppi, Sofia; Gatti, Nicola; Basilico, N.

Web Intelligence and Intelligent Agent Technologies, 2009. WI-IAT '09. IEEE/WIC/ACM International Joint Conferences on. Vol. 2 IET, 2009. p. 541-548.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Ceppi, Sofia

AU - Gatti, Nicola

AU - Basilico, N.

PY - 2009/9/1

Y1 - 2009/9/1

N2 - 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.

AB - 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.

KW - Bayesian methods

KW - Conferences

KW - Game theory

KW - Intelligent agent

KW - Mathematical programming

KW - Mobile robots

KW - Nash equilibrium

KW - Security

KW - Uncertainty

KW - Algorithmic game theory

KW - Bayes-Nash equilibrium

KW - enumeration algorithm

U2 - 10.1109/WI-IAT.2009.209

DO - 10.1109/WI-IAT.2009.209

M3 - Conference contribution

SN - 978-0-7695-3801-3

VL - 2

SP - 541

EP - 548

BT - Web Intelligence and Intelligent Agent Technologies, 2009. WI-IAT '09. IEEE/WIC/ACM International Joint Conferences on

PB - IET

ER -