KR2020Proceedings of the 17th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning

Rhodes, Greece. September 12-18, 2020.

Edited by

ISSN: 2334-1033
ISBN: 978-0-9992411-7-2

Sponsored by
Published by

Copyright © 2020 International Joint Conferences on Artificial Intelligence Organization

Ordinal Polymatrix Games with Incomplete Information

  1. Nahla Ben Amor(Institut Supérieur de Gestion de Tunis)
  2. Hélène Fargier(IRIT-CNRS)
  3. Régis Sabbadin(INRAE-MIAT)
  4. Meriem Trabelsi(LARODEC, Institut Supérieur de Gestion de Tunis, Université de Tunis,, IRIT, Université de Toulouse)


  1. KR and game theory-General
  2. Qualitative reasoning, reasoning about physical systems-General
  3. Uncertainty, vagueness, many-valued and fuzzy logics-General


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.