key: cord-0044732-f3w0qz4h
authors: Azzabi, Arij; Ben Amor, Nahla; Fargier, Hélène; Sabbadin, Régis
title: Ordinal Graph-Based Games
date: 2020-05-18
journal: Information Processing and Management of Uncertainty in Knowledge-Based Systems
DOI: 10.1007/978-3-030-50146-4_21
sha: e66048d84d725b3afe1e8fa3655abc4bb0d029aa
doc_id: 44732
cord_uid: f3w0qz4h

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.

Game theory is a natural framework to consider when modeling complex multi-agent systems. The larger the number of agents in these systems, the more computational issues arise. However, there exist situations where the utility of players only depends on a small subset of other players' strategies. Accordingly, researchers in AI proposed compact representations for games, pursuing the seminal work on graphical games [11] . Polymatrix games [20] , graphical games [11] and hypergraphical games [16] have been proposed as a convenient way to represent games with multiple players and local interactions. These models offer the possibility to exploit local interactions among players and can require exponentially less space than usual normal-form games to represent. In hypergraphical games, agents' interactions are represented by a hypergraph where each agent (vertex) can be involved in several normal-form subgames (hyperedges). If the utility of each agent depends on exactly one subgame, then the game is a graphical game. If all subgames involve only two players then the game is a polymatrix game. In this work, we are interested in these three classes of games.

As for standard representations, the overall aim for players with compact representations of games is to compute a Nash equilibrium (NE) [13] . Significant work has been devoted to finding pure or mixed NE for polymatrix, graphical and hypergraphical games. [11] proposed a message passing type algorithm (TreeNash) for computing NE on tree structured graphical games. [10, 15] extended the TreeNash algorithm to arbitrary graphical games, by defining NashProp, a heuristic Loopy Belief Propagationtype algorithm. Concerning polymatrix games, [12] have demonstrated that a mixed NE could be found by a reduction to a Linear Complementarity Problem (LCP) . In a different line of works, [17] have studied constrained pure NE in different subclasses of polymatrix games. They have shown that the problem of finding pure NE is tractable in these subclasses. [2] proposed Valued Nash Propagation (VNP), an algorithm for finding a pure NE in hypergraphical games and showed that VNP works efficiently when the hypertree-width is bounded. [19] proposed an algorithm for solving Asymmetric Distributed Constraint Satisfaction problems (ADisCSP), in order to find approximate NE for hypergraphical games. When it comes to reflecting realistic games situations, local interactions between players is only one aspect. Another important feature of games is that preferences of players may not always be easily quantified. Sometimes, only an ordinal ranking of joint strategies can be reasonably expressed by "players". Pure NE are hopefully invariant to the quantitative embedding of ordinal preference scales. However, mixed-equilibria are sensitive to non-linear transformations of the preference scales of players, which makes usual game theory unable to easily tackle ordinal preferences over joint strategies. Therefore, Ordinal games [3] have been studied as a framework to tackle games with ordinal preferences. However, until recently there has been little advancement in the analysis of equilibria in ordinal games. [3] studied only pure strategies in ordinal games. Then, a definition of mixed strategies has been recently proposed in the possibility theory framework [1] . In the same line, [8] have proposed the definition of randomization over actions using possibilistic approaches to study and compare both qualitative and quantitative equilibrium concepts based on the Sugeno integral and Choquet integral [7] . However, to our knowledge, all works dedicated to the study of ordinal games are limited to normal-form games, while the two aspects of compactness and ordinal preferences occur naturally in human elicited games situations. Our goal is to overcome the lack of solution concepts and algorithms for compactly represented ordinal games.

The contributions of the present paper are fourfold: (i) We give the first definition of Ordinal Graphical Games (OGG), Ordinal Hypergraphical Games (OHG) and Ordinal Polymatrix Games (OPG). These definitions allow, in some cases, an exponentially more compact representation of ordinal games than in [1] , for example. We also study both pure and possibilistic mixed NE in these games. (ii) We show that, as for cardinal graph-based games, deciding whether a pure NE exists is NP-complete. (iii) We propose and implement solution approaches for finding pure and mixed NE for graphbased ordinal games, the algorithm computing mixed-NE being polytime in the game description. (iv) We end the paper with an experimental study.

A normal form game represents strategic interactions between players with conflicting objectives. Extensive normal form games representations are exploited to compute equilibrium strategies between players. A normal form game is defined as follows [18] :

is a set of strategies available to player i. a = (a 1 , . . . , a n ) denotes a joint strategy.

The classical definition of pure NE in a normal-form game is the following:

. Extensive normal form games expressions are unable to model games with more than dozen of players (utility tables representations are exponential in the number of players). Fortunately, in realistic games situations with many players, interactions are often only "local". The utility of players only depends on the strategies chosen by few other players. Compact representations of games have thus been largely studied.

In this paper, we are particularly interested in three models of compactlyrepresented normal-form games, based on graph theory: graphical games [11] , polymatrix games [20] and hypergraphical games [16] .

These three frameworks represent normal form games N, A,Ū , where the utility functions of playersŪ = {ū i : A → R} i∈N have some particular structure:

-In a graphical game the local utility functions of players are defined by:

These local utility functions concisely represent (when |M i | < n) the utility functions of players in the corresponding normal form game. These are defined by

-In hypergraphical games the utility function of any player is a sum of local utility functions over subgames involving only few players. There are K subgames and N k ⊆ N, ∀k = 1..K, is the set of players involved in subgame k. The local utility functions of player i are defined as:

In the corresponding normal form game, global utility functions are defined as

-In a polymatrix game, the local utility functions of players are defined by:Ū = ūij : A {i,j} → R (i,j)∈E⊆N 2 where E is a set of pairs of players involved in 2player games. In the corresponding normal form game, global utility functions are defined as

(3) [1] have introduced the definition of possibilistic mixed strategies in ordinal games. These definitions are based on the possibilistic decision theory framework. First, we give an overview of the possibility theory framework. Possibility theory [4] can be seen as a qualitative counterpart to probability theory. The basic concept in possibility theory is the notion of possibility distribution π. It is a mapping from a set of states S to a finite ordered scale L = {0 L < . . . < 1 L }, equipped with the order-reversing function ν : L → L. π gives some knowledge about state s ∈ S: π(s) = 1 L indicates that s is totally plausible, π(s) = 0 L means that s is impossible and π(s) > π(s ) implies that s is more plausible than s . π is assumed to be normalized: there is at least one completely possible state (s * such that π(s * ) = 1 L ). Assuming π, the possibility Π(E) and the necessity N (E) of any event E ⊆ S can be computed:

In light of qualitative (possibilistic) decision problems under uncertainty, where each result is assessed by an ordinal utility function μ : S → Δ, [4, 5] have introduced qualitative pessimistic utility (U pes ), which is a counterpart to von Neumann and Morgenstern's [18] expected utility:

U pes generalizes the Wald criterion and determines to what degree it is certain (i.e., according to measure N ) that μ achieves a good utility. While pure NEs are similar in ordinal and cardinal games, ordinal games do not admit stochastic mixed strategies, since one cannot compute the mathematical expectation of a probability distribution over ordinal rewards. However, possibilistic mixed strategies can be considered as a qualitative counterpart to probabilistic mixed strategies in cardinal games and have been justified in terms of equilibria in ordinal games, in [1] . Since the concept of pure NE is ordinal in nature, its definition is the same in the possibilistic framework as in the classical framework:

N, (A i ) i∈N , (μ i ) i∈N : -N = {1, ..., n} is a set of n players. -A = A 1 × ... × A n : A i is a set of actions available to player i. -L is a finite ordinal scale. -μ = {μ i : A → L} i∈N

Note that, in the qualitative case, a pure NE verifies:

. One can check that the ordinal game has two pure NEs: (W,W) and (OW,OW). In these NE, both farmers are somehow satisfied (levels 3 and 4 ∈ L) and have no incentive to deviate.

The concept of mixed strategy in the possibility theory framework [1] is described as a possibility distribution over the alternatives of player i, i.e., π i : A i → L. Hence, π i is a ranking over the options included in A i , showing a player's preferences. π i can also be usefully interpreted by other players as a likelihood of play of player i, i.e., a ranking of the options that player i is likely to play. As usual, π i is normalized, i.e., max ai∈Ai π i (a i ) = 1 L . A joint possibilistic mixed strategy verifies:

The pessimistic possibilistic decision criterion [4] is used to evaluate the utility of π to player i:

where ν : L → L is the order-reversing function of L. A (least specific) Possibilistic Mixed Equilibrium (ΠME) is defined as a set π * = (π * 1 , . . . , π * n ) of normalized possibility distributions expressing individual preferences, where no player has incentive to deviate unilaterally from her strategy.

is a ΠME iff it satisfies, for any possibilistic mixed strategy π, μ P ES

Example 3 (Cont. Example 1). Let us consider possibilistic mixed strategy (π * 1 , π * 2 ), where π * 1 (W ) = π * 2 (W ) = 4 and π * 1 (OW ) = π * 2 (OW ) = 1. One can check that μ P ES 1 (π * ) = μ P ES 2 (π * ) = 3 and that this is a possibilistic equilibrium in the sense of [1] . No player can improve her pessimistic utility by changing her mixed strategy.

Mixed strategies in cardinal games are evaluated by their expected utility, reflecting the assumption that games are repeated and that utility compensate. In the ordinal framework, mixed strategies can be seen as refining "worst-case" strategies (i.e. minimax strategies). [1] have proposed a different interpretation of these: A player's own strategy is a form of "commitment to play" she announces to other players (I will preferably play actions with highest possibility degree but I may play different actions as well). Then an equilibrium results from different rounds of discussions during which players successively lower the plausibility of playing actions, until no one feels better of changing her current strategy.

A ΠME is generally not unique. A least specific ΠME is one where the utility of any player can only decrease when it unilaterally transforms its possibility distribution into a less specific one. The interest of a least specific ΠME is that it sets only the lightest possible constraints on every players' strategies. One can check that in the previous example, π * is a least specific ΠME. By replacing π * 1 with π 1 (W ) = 4, π 1 (OW ) = 2, we get μ P ES

. [1] have proved that a least specific ΠME for an ordinal game could be computed in polynomial time, and have provided a polynomial time algorithm to compute a ΠME through successive improvement of strategies.

In the previous section, we have recalled the framework of possibilistic ordinal game theory, which has been proposed to model, in particular, human elicited game situations, where preferences between strategies are usually best modelled in "ordinal" ways. Another important features of human-elicited games is a need for compactness of expression. One cannot easily rank joint strategies where actions of many players are involved. In particular, the notion of local interactions is worth exploring in the context of ordinal games as well. This section introduces the ordinal counterparts to graphical, hypergraphical and polymatrix games.

We briefly present a toy problem which illustrates both ordinal and graphical aspects of the game. Let assume that we have n farmers each with a unique field arranged in the form of a grid. 

In this section, we provide definitions of three new ordinal games classes: graphical (OGG), hypergraphical (OHG) and polymatrix (OPG). These are defined in the framework of possibilistic game theory, by considering local ordinal utility functionsμ i .

In an OGG the local utility functions of players are defined as:μ In the case of ordinal graphical games, the analogy with cardinal games is direct, since utility functions μ i require no aggregations of local utilities.

In an OHG, local utilities are combined using an ordinal aggregator. In the following, the local utilities are aggregated through a minimum operator, which is coherent with preference aggregation in an adversarial framework. 

Note that a given OHG can be easily cast as an OGG, by defining M i = ∪ k,i∈N k N k , ∀i ∈ N and

Finally, OPG can be defined as specific cases of OHG where each agent is involved in simultaneous 2-player games. Formally, once again we consider a specific ordinal utility function:

In an OHG, the local utility functions of players are defined as:μ

where E is a set of edges defining the 2-player games.

In 

Informally, a pure NE in a graph-based ordinal game is a joint action a * ∈ A from which no player has an incentive to deviate unilaterally.

In the case of OGG, the definition of pure NE may exploit the locality of possibilistic utility functions:

Proof sketch. The proposition results from Definition 4 and Definition 6.

Recall that an OHG can be cast as an OGG. According to Proposition 1 and Eq. 8, we can prove the following corollary:

In the same way, an OPG is an OHG where all subgames contain exactly two players.

We now show that deciding the existence of a pure NE in ordinal graphical games is a difficult problem, even in a very restricted setting.

Proof sketch. Membership. We can decide the membership by guessing a joint action a and verifying that a is a NE. Clearly the latter task takes time polynomial in the size of the game.

Hardness. [6] have shown that deciding the existence of a pure NE in (usual) graphical games is NP-complete even for 3-bounded neighborhood games, i.e., where each player has 3 neighbors at most. Now, just note that pure NE in ordinal and cardinal graphical games are the same notion when no utility functions aggregations are performed (i.e. when there is a single ordinal utility function for each player). Thus, if one is given a graphical game as input, it can be transformed (in polynomial time) into an ordinal graphical game, by plunging the utilities into an ordinal scale. The pure NE are then equal in both cardinal and ordinal problems.

We then prove that deciding the existence of pure NE in OPG and OHG is also NP-complete, which is less obvious at first glance:

Proof sketch. The membership part is easy for both OPG and OHG. The hardness part, for OPG, relies on a reduction of the K-INDEPENDENT SET problem 1 . Hardness for OHG results from the hardness result for OPG.

A Constraint Satisfaction Problem (CSP) is a triple (X ; D; C) where X is a set of variables, D is the set of domains of these variables and C is a set of constraints over variables values. Modeling a graph-based ordinal game as a CSP is useful in the sense that we can take advantage of existing CSP solvers in order to find pure NE(s) within reasonable time. In this section, we show how to model Ordinal Graphical Games (and OHG and OPG) as a CSP and show that the solutions of the induced CSP are pure NE for the original game. Note that [6] proposed a CSP modeling of (cardinal) graphical games in order to find pure NE. The concepts of pure NE are identical in cardinal and ordinal graphical games since utilities in each games are not combined, unlike in polymatrix and hypergraphical games. Still, our CSP 2 model is different from that of [6] . Indeed, the fact that local utilities are aggregated by a minimum operator and not a sum leads to a different reduction (a simpler one, in fact), to a different problem. This different form allows it to be extended to OHG and OPG. 

Note that there are

is satisfied if and only if a i is a non-dominated action of player i. So, obviously, the following proposition holds:

Proof sketch. The proof directly results from the definition of the constraints in terms of non-dominated strategies.

Since ordinal hypergraphical and polymatrix games can be represented as ordinal graphical games, they can also be modelled as CSP. However, note that in the conversion to a graphical game, conciseness may be lost. In the extreme case of a polymatrix game with relations between every pairs of players, the representation of the resulting ordinal graphical game is exponentially larger than that of the original game. Fortunately, in the case of ordinal hypergraphical/polymatrix games, each constraint C i,a i of the corresponding ordinal graphical game can be equivalently replaced in the CSP with an equivalent set of constraints (of reasonable sizes):

Then it directly follows that:

Thus, for both hypergraphical and polymatrix games, the search for pure NE can be performed through modelling as a CSP of similar size as that of the original problem.

In this section, we show that computing a possibilistic mixed equilibrium in OGG (and OPG and OHG) takes polynomial time in the size of the game. To start with, let an OGG G = N, A, {M i } i∈N ,μ be given. Let us assume that π = {π i } i=1..n is a mixed possibilistic strategy over A = A 1 × . . . × A n . As for ordinal games [1] , the utility of π in an OGG is measured using the pessimistic criterion μ pes . It can be shown that the expression of μ pes decomposes according to the structure of the graphical game.

Proof sketch: The proposition results from the expression of μ i (a) =μ i (a Mi ), ∀i ∈ N, ∀a ∈ A as well as from the decomposability of π(a Mi ) = min j∈Mi π j (a j ), through elementary computations.

The subset of dominated actions for player i, D i ⊆ A i can be defined as follows:

Now, we can prove that,

Proof. First, note that μ pes i (π) in Proposition 7 takes polynomial time to compute for OGG, OHG and OPG, given that the expression ofμ i (a Mi ) decomposes in OHG and OPG. The computation of a possibilistic mixed equilibrium in an ordinal game requires iterative calls to an IMPROVE procedure (Algorithm 1), as shown in [1] . Basically, the solution algorithm proposed in [1] in order to compute a mixed equilibrium consists in starting with uniform possibilistic strategies for every players (π i (a i ) = 1 L , ∀i, a i ) and then "improving" the current mixed strategy of a single player of the game, by applying Algorithm 1. At every time steps, a new player is chosen, which strategy is improved. The algorithm stops when no player can see her strategy improved. It is shown in [1] that the algorithm converges to a possibilistic mixed strategy in time polynomial in the expression of the ordinal game. Let us show that the same result holds in the case of ordinal graph-based games, First, note that one call to the IMPROVE procedure takes polynomial time, since μ pes i (π) takes polynomial time to compute 3 . Now, we need to Algorithm 1. IMPROVE procedure 1: Input: (G, π loc , i) 2: Output: π loc 3: π ← π loc 4: if (Πi(Ai \ Di) = 1L) and μ pes i (π) < 1L then 5: for ai ∈ Di 6: πi(ai) ← min πi(ai), ν(μ pes i (π)) 7:

end for 8: end if 9: π loc ← π prove that a possibilistic mixed equilibrium is reached within a polynomial number of calls to IMPROVE. This results directly from the observation made in [1] , that each improvement reduces strictly the possibility π i (a i ) of one alternative of one player i. Since at least one alternative for each player should keep possibility 1 L , the number of iterations of the algorithm is bounded by:

We empirically evaluated the time execution of pure and mixed NE computation in various ordinal games. To this end, we built and solved CSP models using the CHOCO solver [9] , providing a single pure NE or a proof of non-existence. The mixed NE computation algorithm (PME) was implemented in MATLAB. All experiments were performed on an Intel(R) Core(TM) i5-7200U CPU, 2.5 Ghz processor, with 8 Gb RAM memory, 64 bits architecture and under Windows 10 OS. Both algorithms were tested on a dataset of problems, including randomly generated problems and "Farmers games":

-Randomly generated Games. The structure of OHGs were generated randomly, by controlling the number of players n, the number of actions per player, m, the size of hyperedges, s (s = 2 in the case of OPG). The number of local games, K, was computed from a connectivity parameter, c = K NP G , where NP G = n! s!(n−s)! is the maximal number of distinct subgames. The local games correspond to four types of games included in the Gamut suite [14] : "Chicken Games (CG)", "Compound Games (COG)", "Random Games (RG)" and "Dispersion Games (DG)". Local games where generated using Gamut, then their utilities were made ordinal. From Figs. 1 and 2, we notice that, for all games, the CSP algorithm is able to return a proof of existence or non existence of pure NE. Besides, the PME algorithm always returns a possibilistic mixed equilibrium efficiently. As theoretically expected, pure NE existence is experimentally harder to prove than mixed NE computation, especially for "difficult" games (more players, more actions per player). Another result of the experimental study is that ordinal polymatrix games seem easier to solve than ordinal hypergraphical games. In addition, the connectivity of games seems to have only a second-order impact on experimental time-complexity. Figure 3 shows that the number of actions impacts the execution time for both algorithms. This conclusion holds for all tested games. For the most difficult games we considered (Farmers games), the "exponential vs polynomial complexity" phenomenon really shows up (Fig. 4) .

In this paper, we have introduced and defined Ordinal Graphical Games (OGG) Ordinal Hypergraphical Games (OHG) and Ordinal Polymatrix Games (OPG). These frameworks are embedded in possibilistic game theory and inspired by the classical graphical, hypergraphical and polymatrix games models. First, we have studied pure NE in OGG, OHG and OPG and shown that, as for graphical (normal-form) games, deciding their existence is NP-complete. Second, we have shown that the problem of finding a pure NE in ordinal graph-based games could be modelled as a Constraint Satisfaction problem (CSP). Finally, we focused our attention on the problem of finding possibilistic mixed equilibria. We have shown that, as for ordinal normal-form games, a ΠME can be computed in polynomial time (in the size of the game). For this purpose, we have proposed an adapted version of the current algorithm for ordinal games and we have shown that it runs in polynomial time. This result is surprising at first glance, since OGG, OHG and OPG admit exponentially more compact representations than normal form ordinal games. However, this result is due to the nice properties of the "minimum" aggregator used to combine local utilities.

The choice of a CSP modelling to compute pure NE was natural, in particular since it provides a natural and easy way to model the search for pure NE in possibilistic games. It is even more natural than in the cardinal case, due to the use of the minimum operator to aggregate utilities in local games. Furthermore, the CSP approach allows to make use of existing efficient solvers and do not require to develop specific solution algorithms. However, in the context of (cardinal) graphical games, the family of TreeNash/Nashprop algorithms [10] has been advocated to compute exact/approximate mixed NE, in particular for graphical games where the underlying graphical structure is a tree. These algorithms require, from a conceptual point of view, to propagate messages between players in the form of continuous multivariate functions T : [0, 1] k → {0, 1}, expressing "best responses" to mixed strategies. Since this is not possible in practice, approximate (discretized) or exact (exponential size) representations of these functions are propagated to compute equilibria. In ordinal graphical games, since the set of possibility distributions is a finite set, we may define similar message propagation algorithms where the messages are finite tables. This is an interesting avenue for further research. However, it remains to compare the efficiency of these message-passing algorithms to that of the ones we propose.

Equilibria in ordinal games: a framework based on possibility theory

A distributed algorithm for optimising over pure strategy Nash equilibria

Ordinal games and generalized Nash and Stackelberg solutions

Possibility theory and its applications: a retrospective and prospective view

Decision-theoretic foundations of qualitative possibility theory

Pure Nash equilibria: hard and easy games

A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid

Possibilistic randomisation in strategic-form games

Choco: an open source Java constraint programming library

Algorithmic game theory

Graphical models for game theory

Copositive-plus Lemke algorithm solves polymatrix games

Non-cooperative games

Run the GAMUT: a comprehensive approach to evaluating game-theoretic algorithms

Nash propagation for loopy graphical games

Computing correlated equilibria in multi-player games

Constrained pure Nash equilibria in polymatrix games

Theory of Games and Economic Behavior

A distributed asynchronous solver for Nash equilibria in hypergraphical games

Equilibrium points in polymatrix games