Skip to Main content Skip to Navigation
Conference papers

Jeux bayésiens hypergraphiques

Abstract : This paper defines the framework of hypergraphical Bayesian games, which allows to concisely specify Bayesian games with local interactions. This framework generalizes both normal-form Bayesian games and hypergraphical games (including polymatrix games). Establishing a generalization of Howson and Rosenthal’s Theorem, we show that hypergraphical (resp. polymatrix) Bayesian games can be transformed, in polynomial time, into equivalent complete-information hypergraphical (resp. polymatrix) games. This result has several consequences. It involves that finding a mixed Nash equilibrium in a hyper-graphical or polymatrix Bayesian game is a PPAD-completeproblem while the existence of a pure Nash equilibrium defines an NP-complete problem. It also implies that computing a mixed Nash-equilibrium in a standard normal-form, Bayesian game is PPAD-complete.
Document type :
Conference papers
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03298713
Contributor : Abir B. Karami <>
Submitted on : Friday, July 23, 2021 - 6:44:04 PM
Last modification on : Wednesday, September 8, 2021 - 2:28:33 PM

File

RJCIA_2021_paper_2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03298713, version 1

Citation

Hélène Fargier, Paul Jourdan, Régis Sabbadin. Jeux bayésiens hypergraphiques. Rencontres des Jeunes Chercheurs en Intelligence Artificielle (RJCIA 2021) @ Plate-Forme Intelligence Artificielle (PFIA 2021), Jul 2021, Bordeaux, France. pp.38-45. ⟨hal-03298713⟩

Share

Metrics

Record views

35

Files downloads

32