Possibilistic Games with Incomplete Information

1 Introduction

Game theory proposes a very simple but powerful framework to capture decision problems involving several agents: in a game with complete information, each agent (each "player") chooses an action among a set of possible actions, and the final outcome depends on the actions chosen by all the agents.

The preferences of the agents among the outcomes are captured by utility functions. The term "payoff" is often used to designate their utility - this suits to problems where the satisfaction can be expressed on a cardinal scale, typically a monetary scale. But there are instances where the assumption of cardinality can be questioned (see, e.g., [Ouenniche et al., 2016; Cruz and Simaan, 2000]). Moreover, several fundamental notions of game theory, e.g., Nash Equilibrium and Dominance, do not require such an assumption - they are basically ordinal notions. A cardinal notion is called in two cases at least: (i) when the game is repeated (and outcomes are "collected" and assumed to be additive), and (ii) when the outcomes depend on a probabilistic event (e.g., in the prisoner dilemma, if the verdict does not only depend on the confession of the prisoners, but also on the result of the trial). To capture such incomplete information situations, Bayesian games have been proposed by Harsanyi [1967]. This approach does nevertheless not apply to ordinal games, where the utility degrees capture no more than a ranking, nor to situations of a decision under qualitative uncertainty.

Following the seminal work of [De Clercq et al., 2018] on possibilistic Boolean games, we propose to use possibility theory to model qualitative uncertainty in ordinal games. Unlike [De Clercq et al., 2018], we do not develop a complex language. We stay at the semantic level and work out the idea of possibilistic games, extending the notion of Nash Equilibrium [Nash, 1950] to such games and showing how to transform them into classical games.

Section 2 presents the notions on which the paper relies. Section 3 and 4 propose a possibilistic model for ordinal games with incomplete information and generalizes the notion of a Nash Equilibrium (NE) to this framework. Section 5 states the complexity of the problem of the existence of a NE and proposes a Mixed Integer Linear Programming encoding of the problem. Experiments are reported in Section 6. The proofs are omitted for the sake of brevity; they can be found at [Ben Amor et al., 2019].

2 Background

2.1 Normal FormGames

A strategic game or normal form game is classically defined as follows [Morgenstern and Von Neumann, 1944]:

Definition 1 (Normal FormGame) A normal form game is a triple G = 〈N, A, µ〉, where:

• N = {1, . . . , n} is a finite set of players;
• A = ×i∈NAi, where Ai is a finite set of actions available to player i ∈ N;
• µ = {(µi)i∈N} is a set of utility functions µi : A ↦→∆.

A joint (or "pure") strategy is a vector a ∈ A which specifies an action for each player and µi(a) is the utility of agent i for the joint strategy a; it takes values in a finite totally ordered scale ∆ (the higher µi(a), the more satisfied agent i). Typically ∆ = [0, 1], but any ordered scale may be used.

A joint strategy is a Nash Equilibrium (NE) if no player can improve her utility by unilaterally changing her strategy:

Definition 2 (Nash Equilibrium) A strategy profile a ∈ A is a NE, iff ∀i ∈ N, ∀a′i ∈ Ai: µi(ai.a-i) ≥ µi(a′i .a-i). where ∀a ∈ A, ai is the action of i in a, a-i = (a1, . . . , ai-1, ai+1, . . . , an) ∈ A-i = ×j̸=iAj is its restriction to all the players but i and "." denotes the concatenation (e.g., ∀(a′i , a-i), a′i .a-i = (a1, . . . , ai-1, a′i , ai+1, . . . , an)).

2.2 Possibility Theory

The basic building block in possibility theory [Dubois and Prade, 1988] is the notion of possibility distribution. A possibility distribution π is a mapping from a set of states S to an ordered scale ∆ (here to ∆ = [0, 1]). π(s) = 1 means that s is totally plausible, π(s) = 0 means that s is impossible and π(s) > π(s′ ) means that s is more plausible than s′ . π is assumed to be normalized: there is at least one totally possible state (a s such that π(s) = 1). From π, one can compute the possibility Π(E) and the necessity N(E) of any event E ⊆ S: Π(E) = sups∈E π(s) evaluates to what extent E is consistent with the knowledge represented by π while N(E) = 1 -Π( ¯E) = 1 - sups/∈E π(s) corresponds to the extent to which ¬E is inconsistent and thus evaluates at which level E is certainly implied by the knowledge.

Considering qualitative (possibilistic) problems of decision under uncertainty, where each consequence is evaluated by a utility function µ : S ↦→ ∆, [Dubois and Prade, 1995; Dubois et al., 2001] have proposed qualitative utilities, called pessimistic and optimistic utility degrees, as counterparts to von Neumann and Morgenstern's [1944] expected utility:

U pes generalizes the Wald criterion and estimates to what extent it is certain (i.e., necessary according to measure N) that µ reaches a good utility. U opt estimates to what extent it is possible that µ reaches a good utility. In the framework of competitive game theory, U opt is rather unnatural (too adventurous), while U pes conveniently models the cautious decision makers. As many other models this models makes a commensurability assumption between the utility levels and the levels of likelihood. This assumption is common to all the models which considers that the agent's preference relation is complete and transitive (this is the case in many models, be they qualititative or quantitative: expected utility [Savage, 1954; Morgenstern and Von Neumann, 1944], multi-prior non expected utility [Gilboa and Schmeidler, 1989], Sugeno integrals [Dubois et al., 1998], etc. ).

In the following, we shall finally use the notion of conditional possibility measure proposed by [Hisdal, 1978] in order to stay in the pure ordinal framework (for a discussion about the alternative definitions of conditional possibilities, see [Walley and De Cooman, 1999]). For any events E and F ⊆ S the possibility of E given F is:

3 Possibilistic Games with Incomplete Information

The classical framework of games under perfect information assumes that each player knows everything about the game: the players, the actions available to every player, all their utilities, etc. What is not known by a player is the decision of the other ones, but the game itself is assumed to be perfectly known by everyone (hence the name "perfect information").

This assumption cannot always be satisfied. In the real world indeed, players are not so well informed, and the knowledge about the game is often incomplete. For instance, a landlord may ignore if a potential tenant is honest and has a moral incentive to pay his loan or not, if we consider the classical battle of sexes example, a person who has doubts about the faithfulness of his/her partner has some uncertainty about his/her priorities (being together or missing the appointment).

Bayesian games [Harsanyi, 1967] offer a suitable framework for cardinal games under incomplete knowledge; they assume that the utility degrees are additive in essence and that the knowledge of the players can be quantified in a probabilistic way. This kind of approach does not apply to ordinal games, where the utility degrees do not capture more than a ranking, nor to situations of a decision under qualitative uncertainty. We propose in the following a model for (ordinal) games under possibilistic information.

A game with incomplete information can be first understood as a set S of states of nature, each state corresponding to a classical game. The utility µi of an agent i depends not only on the actions of the other players but also on the real world. Originally, none of the players know which is the real world, but all of them share a common knowledge about the game. Just before playing, each agent i will receive from Nature some information τi(s) about the real world - τi maps any s ∈ S to an element θi of a set Θi called the set of "types" of i. After having observed τi(s), agent i knows more about the real game, but several games may still be plausible. The agent, thus, conditions her knowledge on τi(s). The use of a space type is classic in game theory - it is the basis of Bayesian games. The set of possible types of i, Θi, can be considered as the local state space for the player i and Θ = Θ1 × · · · × Θn as the effective global state space. The idea of Harsanyi when defining types was that a player's local state can encapsulate all the information to which the player has access: it contains not only the status of the external world that the player has observed but also his introspective mental states (see [Brandenburger, 1993] [J. Aumann and Brandenburger, 1995] [Battigalli and Bonanno, 1999], [Brandenburger, 2008], [Dekel and Siniscalchi, 2015] for the links between belief states and types, and more generally for further developments about epistemic game theory.

In the present paper we follow Harsanyi's approach, based on types, extending it to qualitative games with possibilistic uncertainty. Thus, the action of an agent i depends only on the information θi ∈ Θi she receives. A joint strategy σ = (σ1, . . . , σn) is thus a tuple of functions σi that map each possible information (each "type" θi in Θi) to action in Ai 1 .

Definition 3 A strategy is a vector σ = (σ1, . . . , σn) of functions σi : Θi →Ai.

σi(θi) specifies the action that player i will execute when receiving the private information θi. Given a strategy σ and a configuration of the players types θ ∈ Θ = Θ1 × · · · × Θn, σ(θ) = (σ1(θ1), . . . , σn(θn)) denotes the joint action (the element of A) prescribed by strategy σ when θ occurs. In the following, Σi denotes the set of all functions from Θi to Ai and Σ = Σ1 × · · · × Σn the set of all joint strategies.

1 In this paper, we consider pure strategies only: in our qualitative context, the notion of a mixed (Bayesian) strategy, which relies on additive probabilities, is not pertinent.

In the Bayesian framework, the game under incomplete information is most of the time described on the space of types (underlying worlds are omitted). In the present work, we proceed in the same way and define a possibilistic game with incomplete information as follows:

Definition 4 (Π-game) A possibilistic game with incomplete information (Π-game) G is a tuple 〈N, A, Θ, π, µ〉 where:

• N is a finite set of n players {1, ..., n};
• A = ×i∈NAi where Ai is the set of actions of player i;
• Θ = ×i∈NΘi, where Θi is the set of types of player i gathers all the configurations of types, i.e. vectors θ = (θ1, . . . , θn). θi denotes the type of i in θ and θ-i = (θ1, . . . , θi-1, θi+1, . . . , θn) . Likewise Θ-i = ×j̸=iΘj;
• π: Θ → ∆ is a joint possibility distribution over the combinations of types;
• µ = {(µi)i∈N} where µi : A × Θ → ∆ is the utility function of player i.

Possibility distribution π captures the common knowledge of the players. The information that the players have about the real world corresponds to a θ ∈ Θ but is not common: i does not know θ, but only θi (θi is the private knowledge of agent i). π(.|θi) represents the knowledge that agent i has when learning θi. On the other hand, utility µi(a, θ) (utility of joint action a for player i when learning θ) will be obtained once all players have played their action and revealed their type (thus µi depends on the whole θ and not only on θi).

A Π-game can be equivalently defined as a set of |Θ| normal form games with the same set of players N and the same set of actions A. More precisely, for each θ ∈ Θ, there is a game Gθ = 〈N, A, {{µθi }i∈N}〉 where:

Example 1 (A landlord and a tenant) A landlord L can rent a house to a tenant T. She can Accept (A) or Refuse (R), i.e., AL = {A,R} and the tenant can Pay the landlord (P) or not (P), i.e., AT = {P, P}. The tenant can be honest (H) or dishonest (D), i.e., ΘT = {H,D}. The landlord does not know the type of the tenant but she receives information indicating that the tenant is honest (IH) or dishonest (ID), i.e., ΘL = {IH, ID}. Generally, the tenant is honest and the landlord is informed that the tenant is honest. But the tenant may be dishonest and the landlord well informed. There is a low possibility that the landlord is informed that the tenant is honest while it is not the case. Finally, it cannot be excluded that the landlord is informed that the tenant is dishonest while she is honest. This is captured by the following common π: π(H, IH) = 1 π(D, ID) = 0.75 π(D, IH) = 0.5 π(H, ID) = 0.25 The projections of π on ΘT and ΘL yield: π(H) = 1, π(D) = 0.75, π(IH) = 1 π(ID) = 0.75. For each strategy, each player has a utility in {0, 0.25, 0.5, 0.75, 1} (from 0 meaning "completely dissatisfied" to 1 meaning "completely satisfied", 0.5 meaning "neutral", etc.) When the landlord refuses to rent, the utility of the tenant is equal to 0 if honest and equal to 0.25 if dishonest. When the landlord accepts, the tenant's utility of P (resp. P) is equal to 1 (resp. 0.25) when she is dishonest and equal to 0.25 (resp. 1) when she is honest. The utility of the landlord is neutral (0.5) when refusing. When accepting, the landlord's utility is high (1) when the tenant pays, low when she does not pay (0 if the landlord believes that the tenant is honest, 0.25 otherwise). There are four combinations of types, and thus four possible games (see Table 1) the possibility degrees of which are: π(GH,IH ) = π(H, IH) = 1 π(GH,ID ) = π(H, ID) = 0.25 π(GD,IH ) = π(D, IH) = 0.5 π(GD,ID ) = π(D, ID) = 0.75

Clearly, Π-games properly generalize classical games (with complete information) since:

Proposition 1 Any classical normal form game is a Π-game with |Θi| = 1, ∀i ∈ N.

Π-games can be related to the framework proposed by [De Clercq et al., 2018] as a semantics for possibilistic Boolean games. In possibilistic Boolean games, the knowledge of each player can be captured by a distinct possibility distribution πi (the knowledge is not common) and the players do not receive any private information (there is no type). [De Clercq et al., 2018] propose to compute the possibility and the necessity of a given profile of actions being a NE in the usual sense (Definition 2): each agent computes these indices according to her own knowledge. The authors then consider the problem from the external point of view of an observer who proceeds to a fusion of these distributions and deduces a unique π = mini∈N πi over types of players.

Adapting these notions to Π-games, where the prior knowledge is common, we can compute, for any profile a of actions:

Contrarily to the framework of [De Clercq et al., 2018], ours can handle the knowledge that each agent i has when receiving some private information θi. Then, the posterior necessity (resp. possibility) that a is a NE can be different from one agent to another:

4 Nash Equilibrium

One problem with the concepts proposed in [De Clercq et al., 2018] above is that they are based on the definition of strategies as profiles of actions, as usual in a classical normal form game. This definition does not take uncertainty about the types of the players into account: it supposes that the full θ is eventually known by all the players, and thus that the utility of each agent is known by each other before the actions are played. In other words, the definition of the above necessity and possibility indices only suits games which are presently incomplete but will eventually become completely known.

In the present work, an agent i only knows π(.|θi) when receiving θi and deciding what to play. As in any incomplete information game, strategy σ specifies an action for each θi. σ is a NE when i has no incentive to change her choice of action for θi, given π(.|θi) and σ. Using possibilistic qualitative decision theory, the utility of σ(θi) is evaluated, using Equation (1) (we suppose that the agent is cautious).

Definition 5 (Utility of an action Utility of joint strategy)

The utility of ai for player i of type θi in the context of σ-i is

The utility of strategy σ to agent i of type θi is:

Of course U pes i (σi(θi), σ-i, θi) is independent of the choices of player i when her type is different from θi.

A best response for player i of type θi is computed knowing the provisional strategies of the other players, i.e., knowing σ-i. This is the action ai which maximizes U pes i (ai, σ-i, θi) (again, when considering a joint strategy σ, the uncertainty of i only bears on the types of the other players. What they plan to do depending on their type is known, prescribed by σ).

Definition 6 (Best Response in a Π-game)

A (Nash) Equilibrium (NE) is a joint strategy from which no player i will deviate unilaterally knowing σ-i. In the possibilistic context, we thus set the following definition:

Definition 7 (Nash Equilibrium in a Π-game) σ is a ΠNash equilibrium (Π-NE) iff ∀i ∈ N, ∀θi ∈ Θi, ∀a′i ∈ Ai,

This definition generalizes Definition 2, which is recovered when |Θ| = 1 (only one possible type per player). As a consequence, a pure equilibrium may not exist for a Π-game (a classical normal form game does not always admit a NE).

Example 2 (cont' Example 1) Let us first compute the conditional possibility distribution (Equation (3)):

• π(H|IH) = π(IH|H) = 1 π(D|IH) = π(IH|D) = 0.5

π(H|ID) = π(ID|H) = 0.25 π(D|ID) = π(ID|D) = 1

For instance, when the landlord learns that the tenant is honest, i.e., when the landlord is of type IH, the most plausible type for the tenant is H (π(H|IH) = 1) but it can not be excluded that is not the case (π(D|IH) = 0.5).

Consider the joint strategy where the tenant pays if she is honest, and does not pay otherwise, and the landlord accepts iff learning that the tenant is honest: σ∗T (H) = P, σ∗T (D) = P σ∗L(IH) = A, σ∗L(ID) = R. The pessimistic utility of the honest tenant is: U pes T (σ∗ ,H)

U pes L (σ∗ , IH) = 0.5; U pes L (σ∗ , ID) = 0.5.

The best response to σ∗L for the tenant of type H is P; indeed: U pes T (P, σ∗L,H) = 0.75, U pes T (P, σ∗L,H) = 0.25.

The two responses P and P are equally interesting for tenant of typeD: U pes T (P, σ∗L,D) = 0.25, and U pes T (P, σ∗L,D) = 0.25.

It can also be checked that strategy σ∗ is a Π-NE; the pessimistic utility of the H tenant playing P (resp. P) is equal to 0.75 (resp. 0.25). So, in this case, the tenant prefers P to P. The dishonest tenant is indifferent between P and P (UT (P, σ∗L,D) = UT (P, σ∗L,D) = 0.25). Also, an IH landlord prefers A to R (UL(A, σ∗T , IH) ≥ UL(R, σ∗T , IH)). Unlike the IH landlord, the ID landlord prefers R to A (utility 0.5 instead of 0.25).

We finally show that any incomplete game can be transformed into an equivalent normal form game with complete information, the pure equilibria of which are in bijection with the pure equilibria of the Π-game. This representation result is a qualitative counterpart of Harsyani's about the representation of Bayesian games by normal form games under complete information. The idea is to consider as many players as the number of pairs (i, θi), each (i, θi) having Ai as a set of available actions. A joint strategy in this (classical) normal form game then corresponds to a strategy σ of the Π-game.

Definition 8 (Transformed Game) Given a Π-game G = 〈N,A,Θ, µ〉 ˜G = 〈 ˜N, ˜ A, ˜µ〉 is the normal form game where:

• ˜N = {(i, θi), i ∈ N, θi ∈ Θi};
• ˜ A(i,θi) = Ai for all (i, θi) ∈ ˜N;
• ˜µ(i,θi)(a) = U pes i (σa , θi) ∀a, i, θi, where σa is the strategy of the original game defined by: σa i (θi) = a(i,θi).

Example 3 (Cont' Example 1) The transformed game ˜G has 4 players: ˜N = {(T,H), (T,D), (L, IH), (L, ID)}, with ˜ A(T,H) = ˜ A(T,D) = {P, P}, ˜ A(L,IH) = ˜ A(L,ID) = {A,R}. The joint action a = (P, P,A,R) of ˜G corresponds to σ∗ in G. The utilities of a in ˜G are:

Let us check that a is a NE in ˜G; the utility of player (T, H) playing P (resp. P) is equal to 0.75 (resp. 0.25): she prefers to play P than P. For player (T,D), ˜µ(T,D)(a) = U pes T (σ,D) = 0.25 and ˜µ(T,D)(P.a-i) = U pes T (P, σ-i,D) = 0.25. So, she is indifferent between P and P, etc.

The following proposition holds.

Proposition 2 a is a pure NE in ˜G = 〈 ˜N, ˜ A, ˜U〉 iff σa is a Π-NE in G = 〈N, A, Θ, µ〉.

As to the complexity of the transformation, consider that the games are extensively represented, by tables. The transformed game contains Σi=1,n|Θi| utility functions of size Πi=1,n|Ai||Θi| . If we write for simplification purpose that |Ai| = a and |Θi| = d ∀i ∈ N (same number of types and the same number of actions for all players), this means that a game containing n utility functions of a size (a · d)n is transformed into a game containing n · d utility functions of size (an )d . Except when the number of types is very small, the transformation does not provide a convenient way to solve the game. Proposition 2 is, as in the Bayesian case, more a representation result than the premise of a solving tool.

5 Solving the Possibilistic NE Problem

Finding a Π-NE in a Π-game is a difficult problem. Indeed:

Definition 9 (Π-NE problem) Given a Π-game G = 〈N,A,Θ, π, µ〉, the Π-NE problem consists in etermining whether there exists a Π-Nash equilibrium.

Proposition 3 Π-NE is NP-Hard, even in symmetric 2player games where π corresponds to total ignorance , i.e., ∀θ1 ∈ Θ1 and ∀θ2 ∈ Θ2, π(θ1, θ2) = 1.

Taking advantage of the efficiency of modern solvers, we propose a Mixed Integer Linear Programming (MILP) formulation for finding Π-NE in Π-game (we follow in this the line opened by [Ceppi et al., 2009] for solving Bayesian games). The main decision variables are Boolean variables encoding the strategy searched for: each σi,ai,θi is a Boolean variable indicating whether action ai is prescribed for type θi of player i: ∀i = 1, n, ∀ai ∈ Ai, ∀θi ∈ Θi : σi,ai,θi ∈ {0, 1}. The utilities are encoded by continuous variables: Ui,ai,θi is the utility (according to σ-i) of agent i if action ai is chosen for type θi (i.e., if σi(θi) = ai):

We will also use the following to constrain the Ui,ai,θi to be equal to the minθ-i∈Θ-i of max(1-π(θ-i|θi), µi(a, θ)) (and not only lower than the min):

Let MAXi,a,θ = max(1 - π(θ-i|θi), µi(a, θ)), the constraints are the following:

∀i = 1, n, ∀ai, a′i ∈ Ai s.t ai ̸= a′i , ∀θi ∈ Θi,

∀i = 1, n, ∀a ∈ A, ∀θ ∈ Θ,

Constraints (8) ensure that the strategy σ searched for specifies exactly one action per type, for each player i.

Constraints (9) require that σ is a Π-NE: when σi,ai,θi = 1, this constraint requires Ui,ai,θi ≥ Ui,a′i ,θi , i.e., that player i has no incentive to deviate from ai. When actions ai is not chosen for θi, (σi,ai,θi = 0) the constraint is always satisfied (Ui,ai,θi -Ui,a′i ,θi is always greater than -1).

Constraints (10) implement Definition (5). They ensure that the utility of player i playing σ(θi) = ai is lower than all, i.e., the minimum over the θ-i of the MAXi,ai.σ(θ-i),θ. Indeed, for any profile of action a that does not correspond to what is prescribed by σ, Σj̸=i(1 - σj,aj,θj ) ≥ 1 and the constraint is always satisfied (Ui,ai,θi ≤ 1). If a-i is chosen for θ-i, then σj,aj,θj = 1 ∀j ̸= i and Σj̸=i(1 - σj,aj,θj ) = 0: the constraint becomes Ui,ai,θi ≤MAXi,a,θ.

Constraints (11) and (12) ensure that Ui,ai,θi is equal to the min of the MAXi,a,θ: when a-i does not correspond to σ-i, Σj̸=i(1 - σj,aj,θj ) is at least equal to 1 and the constraint is always satisfied. When a-i does correspond to σ-i, the sum is equal to 0 and does not annihilate the constraint. The min is reached if Ui,ai,θi =MAXi,a,θ. Mi,ai,θi.θ-i is another way to annihilate the constraint, and reaching the min means not annihilating the constraint for one θ-i - hence Equation (12).

The above problem is linear (the max operator which appears in constraints (10) and (11) deals with constants only). The above formulation does not lead no a combinatorial explosion of the space required. Recall that the size of the original problem is size = n · |Θ| · |A|+|Θ|. Let us denote a (resp. d) the number of actions (resp. types) of each player. The MILP formulation contains:

• n·d·a continuous variables Up,ap,θp , n·d·a Boolean variables σp,ap,θp and n · a · |Θ| Boolean variables Mp,ap,θ;
• n · d constraints (8), each involving a variables;
• n·d·a·(a-1) constraints (9), each involving 3 variables;
• n · |Θ| · |A| constraints (10) each involving n variables;
• n·|Θ|·|A| constraints (11) each involving n+1 variables;
• n · a · d constraints (12) each involving |Θ| d variables.

The size of the MILP encoding is thus in O(n2 · |Θ| · |A|) (polynomial in the size of the original size).

6 Experimental Study

To conduct our experimental study, we developed a novel Πgame generator based on GAMUT [Nudelman et al., 2004], a suite of classical normal form games (with complete information) generators (following the approach of [Ceppi et al., 2009] for the generation of Bayesian games). More precisely, to generate a Π-game version of a GAMUT problem (e.g., the Covariant game), we need as inputs: the number of degrees in ∆, the number n of players, the class of game and if necessary the number of actions |Ai| and of types |Θi| for each player i. Then, we ask GAMUT to generate |Θ| normal form games of the class given in input, the range of utility of which is ∆ and we generate a normalized distribution π : Θ ↦→ ∆ (a randomly selected θ receives degree 1; the degrees of the other elements of Θ are selected in ∆ following a uniform distribution). The utilities µi(a, θ) is simply the utility of a for player i in game Gθ . In our experiments, we vary the number of players from 2 to 6, the number of types from 2 to 8 and the number of actions from 2 to 15. For each combination of parameters, we have generated 50 instances and measured the time necessary to get a Π-NE (or a negative result). We present in the following results of 3 game classes: Covariant games, Dispersion games and Travelers Dilemma game. All experiments were conducted on an Intel Xeon E5540 processor and 64GB RAM workstation. We used CPLEX [CPLEX, 2009] as a MILP solver. We also implemented the transformation of the Π-game as a normal form game (T ˜G) in Java 8. This method, which is exponential in time and space, cannot be considered as a solving method, and this is supported by the experimental results. The implementation of the T ˜G and MILP solver are available online [Ben Amor et al., 2019]. In our evaluation, we bounded the execution time to 10 minutes as in [Sandholm et al., 2005; Porter et al., 2008] experiments.

Table 2 and Table 3 present, respectively, the average memory (in MB) required to decide whether the problem admits a Π-NE or not and the average of execution time (in milliseconds) needed to find one Π-NE (best results are in bold). We vary the |Ai| from 2 to 10 and |Θi| from 2 to 4 for player i while fixing n = 2. "-" mentions that the execution time exceeds 10 minutes. Table 2 confirms that T ˜G is a very naive (exponential) way and that cannot scale up contrarily to MILP which requires less memory, e.g., T ˜G requires more than 3, 4MB when MILP needs just 23MB to solve Travelers Dilemma game with 2 players, 10 actions and 4 types per player. The non-scalability of T ˜G is also observable in Table 3 showing that this latter cannot be used in practice. We also deepened our study of MILP by varying its complexity parameters. More precisely, we first vary the number of actions from 2 to 15 and the number of types from 2 to 8 with two players (n = 2) (see Figure 1). Then, we vary n from 2 to 7 and the number of types from 2 to 5 while fixing the number of actions to 2 (see Table 4). Globally MILP results confirm the feasibility of the qualitative approach of incomplete game advocated by this paper. Results show that MILP has almost the same behavior with different games and that the number of players highly impacts the execution time which is consistent with the theoretical complexity since adding a player directly increases |Θ| and |A|.

7 Conclusion

The main contributions of this paper are threefold: first, it proposes possibilistic games as new representation framework for (ordinal) games under possibilistic incomplete information and extends the standard notion of Nash Equilibrium to such games. Second, it proposes a transformation from possibilistic games to normal form games with complete information and shows the equivalence between pure Nash Equilibria in both frameworks. Third, it proves that finding a pure Nash Equilibrium in a Π-game is a NP-hard problem and proposes a Mixed-integer linear constraints system model to find a possibilistic Nash Equilibrium if any. The experimental study we led shows that, except when the number of types and actions are very small, the MILP approach outperforms the transformation to normal form game approach. As future work, we first plan to define possibilistic mixed NE in possibilistic games and design polynomial time solution algorithms to find them, in the line of [Ben Amor et al., 2017]. Another interesting line of research is to explore concisely expressed possibilistic games, in the line of Bayesian actiongraph games [Jiang and Leyton-Brown, 2010], for example.