Ordinal Polymatrix Games with Incomplete Information - Argumentation, Décision, Raisonnement, Incertitude et Apprentissage Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

Ordinal Polymatrix Games with Incomplete Information

Résumé

Possibilistic games with incomplete information (Π-games) constitute a suitable framework for the representation of ordinal games under incomplete knowledge. However, representing a Π-game in standard normal form requires an extensive expression of the utility functions and the possibility distribution, namely, on the product spaces of actions and types. In the present work, we propose a less costly view of Π-games, namely min-based polymatrix Π-games, which allows to concisely specify Π-games with local interactions. This framework allows, for instance, the compact representation of coordination games under uncertainty where the satisfaction of an agent is high if and only if her strategy is coherent with all of her neighbors, the game being possibly only incompletely known to the agents. Then, an important result of this paper is to show that a min-based polymatrix Π-game can be transformed, in polynomial time, into a (complete information) min-based polymatrix game with identical pure Nash equilibria. Finally, we show that the latter family of games can be solved through a MILP formulation. Experiments on variants of the GAMUT problems confirm the feasibility of this approach.
Fichier principal
Vignette du fichier
KR_20___Meriem.pdf (1.42 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02997292 , version 1 (10-11-2020)

Identifiants

Citer

Nahla Ben Amor, Hélène Fargier, Régis Sabbadin, Meriem Trabelsi. Ordinal Polymatrix Games with Incomplete Information. 17th International Conference on Principles of Knowledge Representation and Reasoning (KR 2020), Principles of Knowledge Representation and Reasoning, Incorporated (KR, Inc.), Sep 2020, Rhodes, Greece. pp.99-108, ⟨10.24963/kr.2020/11⟩. ⟨hal-02997292⟩
94 Consultations
101 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More