Skip to Main content Skip to Navigation
Conference papers

Ordinal Polymatrix Games with Incomplete Information

Abstract : 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.
Complete list of metadatas

Cited literature [32 references]  Display  Hide  Download
Contributor : Helene Fargier <>
Submitted on : Tuesday, November 10, 2020 - 9:15:45 AM
Last modification on : Wednesday, January 20, 2021 - 3:38:30 AM


Files produced by the author(s)



Nahla 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, Sep 2020, Rhodes, Greece. pp.99-108, ⟨10.24963/kr.2020/11⟩. ⟨hal-02997292⟩



Record views


Files downloads