Ordinal Graph-Based Games

The graphical, hypergraphical and polymatrix games frameworks provide concise representations of non-cooperative normal-form games involving many agents. In these graph-based games, agents interact in simultaneous local subgames with the agents which are their neighbors in a graph. Recently, ordinal normal form games have been proposed as a framework for game theory where agents’ utilities are ordinal. This paper presents the first definition of Ordinal Graphical Games (OGG), Ordinal Hypergraphical Games (OHG), and Ordinal Polymatrix Games (OPG). We show that, as for classical graph-based games, determining whether a pure NE exists is also NP-hard. We propose an original CSP model to decide their existence and compute them. Then, a polynomial-time algorithm to compute possibilistic mixed equilibria for graph-based games is proposed. Finally, the experimental study is dedicated to test our proposed solution concepts for ordinal graph-based games.