Equilibria in Ordinal Games: A Framework based on Possibility Theory.

1 Introduction

Game theory used to be mainly a science for economic theorists, until recently when, with the expansion of internet, many practical instances have emerged. Accordingly, in the recent years there has been a growing interest in the AI community for algorithmic game theory [Nisan et al., 2007]. From a practical viewside of game theory, there are instances where the assumption of cardinal payoffs for players can be questioned. For example, in a recent paper, [Ouenniche et al., 2016] describe a realistic example of Public-Private Partnership project, which is dealt with using ordinal game theory.

Ordinal games [Cruz Jr. and Simaan, 2000; Xu, 2000] are thus a natural framework to consider as soon as no cardinal payoffs are available to players. The first analysis of equilibria in ordinal games dates back to [Barany et al., 1992], with a classification of two-person ordinal games in terms of their Pareto sets (pairs of pure strategies which are not uniformly dominated). [Xu, 2000] defines Ordinal Nash Equilibria (ONE) as the natural counterpart of Nash equilibria and proposes an algorithm that computes ordinal Nash equilibria for 2 and 3-players ordinal games, in polynomial time. From the theoretical point of view, [Durieu et al., 2008] study a few categories of ordinal games, among which ordinal best-response potential games, and show that they always admit ordinal Nash equilibria. This property is a counterpart of the one holding for cardinal potential games, which are also known to admit a pure Nash equilibrium [Monderer and Shapley, 1996]. Finally, [De Clercq et al., 2014; 2015] study "possibilistic Boolean games". These are a concise version of ordinal games, constructed from possibilistic logic preference bases. The set of alternatives of each player is given by the instantiation of a separate set of propositional variables. A pure Nash equilibrium (i.e. ONE) is defined as usual. Then, the authors focus on the ill-known ordinal game case, where players do not precisely know others' preferences. They propose an evaluation of ONE in terms of their possibility and necessity degrees to be an ONE for the true (ill-known) ordinal game.

Besides, there has been little progress, if any, in the analysis of ordinal games which do not admit pure strategy equilibria. The only proposed approach [Cruz Jr. and Simaan, 2000; Ouenniche et al., 2016] consists in listing all potential combinations of pure strategies and use the list of ranks of pure strategies of each player to analyze the game's possible pure equilibria. This kind of approach is hardly feasible in practice and, again, it is oriented toward the search of a pure equilibrium. A consequence is that there is no real solution concept for ordinal games which do not admit an ONE.

The present paper proposes the first definition of mixed equilibria for ordinal games. This definition naturally extends possibilistic (single agent) decision theory [Dubois and Prade, 1995]. Our first contribution is to show that ordinal games always admit a possibilistic mixed equilibrium, which can be seen as a qualitative counterpart to mixed probabilistic equilibria. Then, we show that a possibilistic equilibrium can be computed in polynomial time, which contrasts with mixed probabilistic equilibria in cardinal game theory. The definition we propose is thus operational in two ways: (i) it tackles the case when no ONE exists in an ordinal game and (ii) it allows an efficient computation of mixed equilibia.

2 Ordinal Games and Nash Equilibria in Possibility Theory

2.1 Normal FormGames and Nash Equilibria

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

Definition 1 (Normal form game) A normal form game is a triple G = 〈N, (Ai)i∈N , (ui)i∈N 〉, where:

• N = {1, . . . , n} is a finite set of players.
• Ai is a finite set of actions available to player i ∈ N (also called strategy space). A = ×i∈NAi is the product set of available actions. a = (ai)i∈N ∈ A is a joint action of the n players (or a strategy profile).
• (ui)i∈N is a set of utility functions. For any player i, ui : A → L is the utility function of player i, i.e. ui(a) is the utility for agent i of the joint action a ∈ A.

L = {α0, . . . , αk} is a finite totally ordered set, equipped with preorder relation ≥, which is sufficient to define pure Nash equilibria. We will use the following notation ∀a ∈ A:

• a-i = (a1, ..., ai-1, ai+1, ..., an) ∈ A-i = ×j̸=iAj
• (a′i , a-i) = (a1, ..., ai-1, a′i , ai+1, ..., an) ∈ A

Informally, a pure Nash equilibrium, for a game G = 〈N, (Ai)i∈N, (ui)i∈N〉, is a joint action a∗ ∈ A, from which no player has interest to deviate unilaterally. More formally:

Definition 2 (Pure Nash equilibrium)

Let G = 〈N, (Ai)i∈N, (ui)i∈N〉 be a normal form game. a∗ ∈ A is a pure Nash equilibrium of G, if and only if:

One known problem with normal form games is that a pure Nash equilibrium may not exist for a given game G. However, when utility functions take real values, the following has been proved (see, e.g. [Osborne and Rubinstein, 1994]). By allowing players to adopt mixed strategies in the form of probability distributions pi : Ai → [0, 1], one can ensure the existence of a mixed Nash equilibrium p∗ , verifying:

Definition 3 (Mixed Nash equilibrium)

Let G = 〈N, (Ai)i∈N, (ui)i∈N〉 be a given normal form game. Let p∗ = (p∗i )i∈N, where p∗i is a probability distribution over Ai. p∗ is a mixed Nash equilibrium of G, if and only if it verifies: ui(p∗ ) ≥ ui(pi, p∗-i ), ∀i ∈ N, ∀pi, where, ui(p) =def ∑a∈A (∏k∈N pk(ak)) ui(a) is the expected utility to player i of the joint mixed strategy p and p∗-i = {p∗j , j ∈ N, j ̸= i}.

The existence of a mixed Nash equilibrium is guaranteed for any game [Nash, 1950]. However, [Daskalakis et al., 2006] have shown that it is hard to compute one (PPAD-complete: a complexity class of problems which are not assumed to be polynomial time solvable).

2.2 Ordinal Games

There are many natural examples of games in which the utility functions of players take their values in an ordinal scale. Let us consider the following example:

Example 1 (Firms competition) An established firm (E) and a newcomer (N) to a market of fixed size have to choose the packaging of a similar product. Each firm can choose between two different packagings: X and Y. The established producer prefers the newcomers product to look like its ownwhile the newcomer prefers that the products look different (to attract customers). The option Y is more risky than X for the newcomer (in case E also plays Y), but will generate more profit if E plays X. E, however, is indifferent between X and Y. Ordinal outcomes (uE, uN), compatible with this knowledge, are listed in the following table. These outcomes are ranked from 0 (worst case) to 4 (best case):

Preferences are purely ordinal, so are not proportional to any expected profit. If we translate ordinal utilities to their corresponding real values, this problem admits a single mixed Nash equilibrium 1 , p∗E = (0.6; 0.4) and p∗N = (0.5; 0.5).

However, such a direct translation to quantitative values raises questions. If we replace the value uN(X, Y ) = 4 with uN(X, Y ) = 5, the new mixed equilibrium becomes p∗E = (0.5; 0.5) and p∗N = (0.5; 0.5). If we switch for uN(X, Y ) = 6, we get p∗E = (0.43; 0.57) and p∗N = (0.5; 0.5). The three games give identical ordinal orderings of all pure joint strategies to all players. However, with three different compatible cardinal translations of the utilities, the resulting Nash equilibria verify either p∗E (X) > p∗E (Y ), p∗E (X) = p∗E (Y ) or p∗E (X) < p∗E (Y ). Thus, a game theory that directly works on the ordinal expression of utilities would be useful. We propose such an approach, based on possibility theory, which handles ordinal games and avoids the bias linked to ordinalcardinal utility translation.

2.3 Possibilistic Mixed Strategies in Ordinal Games

In this paper, an ordinal game is a triple G = 〈N, (Ai)i∈N, (µi)i∈N〉. The utility functions, µi, take their values in a finite ordinal scale, L, contrarily to utility functions ui which can take cardinal values.

In this section, we define a notion of ordinal mixed strategy for such games, based on possibility theory [Dubois and Prade, 1988]. A possibility distribution over the alternatives of Ai of player i is a function πi : Ai → L that captures a ranking over the elements of Ai. πi can have a dual interpretation, either in terms of preference and in terms of likelihood. More precisely:

• For player i distribution πi models the ranking of alternatives in terms of preference or comitment. Under this interpretation, πi(ai) = 1L means that ai is satisfactory, fully conceivable to player i to play, while πi(ai) = 0L means that it is absolutely not an option for i 2 .
• When interpreted by other players, the ranking πi can be seen as a measure of likelihood of play. In this case, πi(ai) = 1L means that ai is a completely plausible play of player i. On the contrary, πi(ai) = 0L is interpreted as ai is an impossible play of player i.

This dual preference/likelihood interpretation is natural in game theory since, according to the other players, the most preferred alternatives of player i should be the most likely to be played. Possibilistic mixed strategies are defined as normalized possibility distributions πi : Ai →L:

1 Which was computed using http://gambit.sourceforge.net/.

2 0L and 1L are the lowest and highest elements of L.

The joint possibility distribution over joint strategies a = (a1, . . . , an), is defined as the minimum of the individual players possibilistic mixed strategies:

2.4 Evaluating Possibilistic Mixed Strategies

Let an ordinal game G = 〈N, (Ai)i∈N, (µi)i∈N〉 be given and assume that a set of mixed possibilistic strategies πi over Ai have been defined, π being the corresponding joint mixed possibilistic strategy. Now, the question is to measure the utility of π to each player, or, in other terms, the ranking of joint mixed possibilistic strategies by each player.

The two following optimistic and pessimistic criteria have been proposed and axiomatized for decision under uncertainty in the possibilistic framework [Dubois and Prade, 1995; Dubois et al., 2001].

Where n is the order-reversing map of L. For instance, if L = {α0, . . . , αK}, n(αk) = αK-k, ∀αk ∈ L.

µOP T i (π) and µPES i (π) can be readily adapted to the evaluation of joint mixed possibilistic strategies, when these are interpreted as measuring the likelihood of joint strategies. They are soft versions of the maximax and maximin criteria. When there is no knowledge about what other players will play, π(a) = 1L, ∀a ∈ A1 × . . . × An. Then:

• According to µOPT i (π), each player assumes that all other players will be benevolent to him, i.e. act for the best, since µOPT i (π) = maxa µi(a).
• On the contrary, according to µPES i (π), each player assumes that all other players will act in the worst way for him, since µPES i (π) =mina µi(a).

Note that, as for expected utility theory, possibilistice decision criteria assume a form of commensurateness between uncertainty and preference levels [Dubois et al., 2001]. In the framework of competitive game theory, µOPT is rather unnatural, so we will focus on µPES .

2.5 Possibilistic Mixed Equilibria

A possibilistic mixed equilibrium (ΠME) can be informally defined, as in the stochastic case, as a set π∗ = (π∗ 1 , . . . , π∗n ) of (normalized) preference rankings from which no player has interest to deviate unilaterally. Formally, we define:

Definition 4 (Possibilistic Mixed equilibrium)

Let G = 〈N, (Ai)i∈N, (µi)i∈N〉 be an ordinal game. π∗ = (π∗ 1 , . . . , π∗n ) is a possibilistic mixed equilibrium for G if and only if, for any possibilistic mixed strategy π, we have:

In this definition, the double nature of the joint possibility distribution π∗ appears. Indeed, while the π∗ i are obviously interpreted as likelihood rankings in Equation (1), they are defined as solutions to equations involving preference rankings only in the above definition. In this respect, as aggregations of preference rankings, they should be interpreted as preference rankings themselves.

Note that, deterministic equilibria can be interpreted in the same way in both possibilistic game theory and probabilistic game theory settings. However, in the mixed-equilibrium case, while usual mixed Nash equilibria are interpreted as random plays that give good outcomes "on average", in the possibilistic setting these should be interpreted as "commitments" in a negociation process (see Section 2.6), that is the fixed point of a negociation where players indicate which options they may consider in actual play and which they are more prone to play than others. As usual in possibility theory, this is a "one-shot game" interpretation, where games are not repeated and possible outcomes cannot be "averaged"...

Let us now look at some properties of possibilistic mixed equilibria and their computation. We are going to give a constructive proof of the existence of a ΠME for any ordinal game in the next section. But before this, let us define a leastspecific possibilistic Nash equilibrium. First, recall the usual definition of specificity relation of possibility distributions.

Definition 5 (Specificity relation)

Let πi and π′i be two (normalized) possibility distributions over Ai. We say that π′i is more specific than πi (written π′i ⪯ πi), if the following holds: π′i (ai) ≤ πi(ai), ∀ai ∈ Ai.

≺ is the corresponding strict order. By extension, for mixed strategies π = (πi)i∈N and π′ = (π′i )i∈N, we say that π′ is more specific than π when the distributions π′i are all more specific than the distributions πi, ∀i ∈ N. That is:

Assume that a possibilistic joint strategy π is given. We can show that the pessimistic utility of a player never decreases when the joint strategy of all players is made more specific, i.e. if players precise their intentions.

Proposition 1 (Improvement through specificity) Let G = 〈N, (Ai)i∈N, (µi)i∈N〉 be an ordinal game. Let π be an arbitrary possibilistic mixed strategy and let π′ ⪯ π be a more specific possibilistic mixed strategy. Then, we can show that:

Proof: Notice that

Updating a player's mixed strategy for a more specific one cannot decrease his own utility if all other players stick to their own strategy. However, changing one's strategy for a more specific one may give incentive to other players to change their own, as the following example shows.

Example 2 (ΠME and specificity) Let us consider the following ordinal game with two players, two actions and a simple binary scale {0, 1}: Since utilities are binary, possibility

distributions correspond to subsets of {X, Y }. Now, we can check that π = {πE = {X, Y }, πN = {X, Y }} has utility zero to both players. If πE is made more specific (for example π′E = {X}) and πN is left unchanged, this does not modify the utility to player E. By symmetry, no player can unilaterally improve his utility. So, π is a ΠME. Note that {π′E , πN} is no more a ΠME: If player N sees that player E has switched to π′E = {X}, he will be better of if he changes his own strategy to π′N = {X} and gets utility 1. In turn, this will give an incentive to E to switch to π′E = {Y }, etc. Indeed, the only ΠME of this game is π.

It will be useful, when interpreting and computing mixed equilibria, to focus on those which are the least-specific, i.e. put the less restrictions on players' rankings of alternatives:

Definition 6 (Least-specific ΠME)

Let G = 〈N, (Ai)i∈N, (µi)i∈N〉 be an ordinal game. π∗ = (π∗ 1 , . . . , π∗n ) is a least-specific possibilistic mixed equilibrium for G if and only if: (i) π∗ is a possibilistic mixed equilibrium for G and (ii) There exists no π′ s.t. π∗ ≺ π′ and π′ is a ΠME.

2.6 ANegotiation Interpretation of Least-Specific Possibilistic Mixed Equilibria

We will give a constructive proof of the existence of a possibilistic mixed equilibrium for any ordinal game in the following section. However, in order to introduce the proof, it is useful to recall the double nature of possibilistic mixed strategies. These are first preference rankings of alternatives expressed by each player. On the other hand, preference rankings of other players can be interpreted by a player as likelihood rankings of their available strategies.

So, when talking about the improvement and the specificity of a ΠME one is faced with a double interpretation, again:

• Interpreting other players' strategies as likelihood rankings, a given player shows a kind of aversion for uncertainty: It is more comfortable to see other players commit to a given play. This is reflected in Proposition 1 where it is shown that more specific mixed strategies lead to a better utility.
• On the other hand, as far as player i is concerned, his mixed strategy πi can be viewed as a commitment to play: The more specific πi the more constraints i puts

on himself. Thus, one can expect players to prefer to put the lightest constraints on themselves, i.e. to keep πi as less specific as possible.

According to these thoughts, one can see the search for a possibilistic mixed equilibrium as a form of negotiation where players trade, in turn, commitments on their own strategies, so as to improve their position in the joint equilibrium, until no player has interest to trade anymore. We will see that this iterative negotiation procedure leads to a (leastspecific) Nash equilibrium. Furthermore, we will show that a ΠME can be computed in time polynomial in the size of the utility tables µi, unlike "quantitative" mixed Nash equilibria.

3 A Polynomial Time Algorithm for Building Possibilistic Mixed Equilibria

The proof of the main result of this paper goes through three steps. First, we define the problem of deciding, for a given ordinal game, joint mixed possibilistic strategy and player, whether this player can improve his utility by making (unilateraly) his mixed strategy more specific. Then we propose a polynomial-time procedure which answers this question and, if the answer is positive, returns an improved strategy. Finally, we use this procedure as a building block for a polynomial-time algorithm which computes a ΠME for any arbitrary ordinal game.

3.1 Possibilistic Mixed Strategy Improvement

Assume ordinal game G = 〈N, (Ai)i∈N, (µi)i∈N〉, and mixed strategy π = (π1, . . . , πn) are given. Let us consider the point of view of player i. We want to check whether πi can be improved by making it minimally more specific.

To be more precise, we are looking for π′i ≺ πi, such that:

Furthermore, we want π′i to be a least-specific such distribution (there may exist more than one), i.e.

First, let us notice that

where µPES i (ai, π-i) is the utility player i gets when playing ai, when the other players follow the joint strategy π-i:

Note that the computation of µPES i (·, π-i), Ai → L takes polynomial time in the game expression. Now, for a given triple (G, π, i), let Di ⊆ Ai define the set of dominated actions of player i, given π:

That is, when switching from the distribution πi to the fixed action ai, player i does not improve his utility.

Intuitively, in order to improve his situation in the game, player i will make new commitments by decreasing, when possible, the plausibility of his dominated actions, ai ∈ Di, leaving the possibility of non-dominated actions unchanged. Note that the following two facts hold:

Fact (3) holds by definition of Di, while fact (4) holds since,

Thus, if we want to transform π into a more specific distribution π′ , by changing only πi(ai) for ai ∈ Di, in order to get an increased utility µPES i (π′ ) > µPES i (π), we have to ensure that:

This leads to the definition of π′ =IMPROVE(G, π, i):

• π′-i = π-i: Only player i changes his commitment.
• If (i) Π(Ai \ Di) < 1L or (ii) µPES i (π) = 1L, then π cannot be improved and π′ = π. Indeed, in the first case, we cannot decrease the possibility of all ai in Di while keeping a normalized distribution πi. In the second case, there is no hope to improve µPES i (π).
• If Π(Ai \Di) = 1L and µPES i (π) < 1L, then π′i (ai) = πi(ai), ∀ai ∈ Ai \Di and π′i (ai) = min (πi(ai), n(µPES i (π))) , ∀ai ∈ Di.

Given the above definition of the IMPROVE function, one can prove the following results:

Proposition 2 (Improvement function)

Let G = 〈N, (Ai)i∈N , (µPES i )i∈N〉 be an ordinal game. Let also π be a joint possibilistic mixed strategy and i ∈ N be a player. Then, the following facts hold:

1. IMPROVE(G, π, i) is normalized.
2. IMPROVE(G, π, i) ⪯ π.
3. If IMPROVE(G, π, i) ≺ π, µPES i (IMPROVE(G, π, i)) > µPES i (π). Else, IMPROVE(G, π, i) = π.
4. For any joint possibilistic mixed strategy π′′ such that IMPROVE(G, π, i) ≺ π′′ ⪯ π, we have:

1. If π′ = IMPROVE(G, π, i), then, ∀j ∈ N, ∀aj ∈ Aj µPES j (aj, π′-j ) ≥ µPES j (aj, π-j) and µPES j (π′ ) ≥ µPES j (π).

Proof:

1. IMPROVE(G, π, i) only changes (potentially) πi. And when it does, we have taken the caution that the corresponding π′i remains normalized.
2. The only potential change in π′ =IMPROVE(G, π, i) occurs when π′i (ai) ← min (πi(ai), n(µPES i (π))). And, obviously, π′i (ai) ≤ πi(ai). So, π′i ⪯ πi and π′ ⪯ π.
3. Note that if IMPROVE(G, π, i) = π′ ≺ π, then (i) π′-i = π-i, (ii) ∀ai ∈ Ai \ Di, π′i (ai) = πi(ai) and (iii) ∀ai ∈ Di, π′i (ai) ≤ n(µPES i (π)) and

The "else" part is trivial since (π′ ⪯ π and π′ ̸≺ π) ⇒ π′ = π.

1. We proved in 3. that ∀ai ∈ Di, π′i (ai) = n(µPES i (π)). Then, since π′-i = π-i and ∀ai ∈ Ai \ Di, π′i (ai) = πi(ai), we get: π′ ≺ π′′ ⇒ ∃ai ∈ Di,

Thus, µPES i (π′′ ) ≤ µPES i (π). The other direction µPES i (π′′ ) ≥ µPES i (π), comes from the specificity relation π′′ ⪯ π.

1. First, note that if π′ = IMPROVE(G, π, i), π′ only differs from π in its component π′i and π′i ⪯ πi. Then, note that, ∀j ∈ N \ i, aj ∈ Aj :

In addition, since µPES i (ai, π′-i ) does not need π′i to be computed, we have µPES i (ai, π′-i ) = µPES i (ai, π-i). Now, since, ∀j ∈ N,

and we have both π′ ⪯ π (implying n(π′j (aj)) ≥ n(πj(aj)), ∀j, aj) and µPES j (aj, π′-j ) ≥ µPES j (aj, π-j), then: µPES j (π′ ) ≥ µPES j (π), ∀j ∈ N. □

Properties 1, 2 and 3 in Proposition 2 show that IMPROVE(G, π, i) is at least as specific as π and strictly improves the utility of player i or leaves π unchanged. Property

5 shows that IMPROVE(G, π, i) does not decrease the utilities of other players than i. Property 5 will be especially useful for proving Proposition 3. Finally, property 4 shows that IMPROVE(G, π, i) is the least specific improvement of π to player i, when it changes π. Note that the complexity of IMPROVE is dominated by that of the computation of the set of tables {µPES i (ai, π-i)}i∈N,ai∈Ai . These can be computed in time polynomial in |G|. Therefore, IMPROVE(G, π, i) can itself be performed in polynomial time.

3.2 An Algorithm for the Construction of Possibilistic Nash Equilibria

We exploit procedure IMPROVE in an algorithm which computes a possibilistic mixed equilibrium of an ordinal game.

repeat

Algorithm 1: Algorithm which computes a possibilistic mixed equilibrium.

We have to show that Algorithm 1, which performs iterates of the IMPROVE procedure, converges. In addition, we will show that it converges towards a possibilistic mixed equilibrium of the ordinal game G and that convergence occurs within time polynomial in the expression of G.

Proposition 3 (Convergence)

Algorithm 1 converges in a finite number of steps and convergence occurs in time polynomial in the size of G.

Proof: First, note that the outer loop of the algorithm requires n calls to the function IMPROVE per iteration. Then, note that by Prop. 2, result 3, π′ =IMPROVE(G, π, i) is either more specific than π, or equal to π and that π′ can only differ from π in its component π′i . Finally, note that the number of possible strict improvements of a player i's mixed strategy πi : Ai → L is upper bounded by |L| × |Ai|: For each improvement, one of the |Ai| coordinates of the mixed strategy is decreased, and each coordinate belongs to L.

Therefore, Algorithm 1 converges after at most n × |L| × |Ai| calls to the IMPROVE procedure, which itself takes time polynomial in the size of the expression of G. □

Proposition 4 (Soundness)

If Algorithm 1 has converged towards π∗ , then π∗ is a possibilistic mixed equilibrium of G.

Proof: Since π∗ has been obtained after convergence of Algorithm 1, it verifies : π∗ = IMPROVE(G, π∗ , i), ∀i ∈ N. This implies that ∀i ∈ N, ∀πi, µPES i (π∗ ) ≥ µPES i (πi, π∗-i ), that is, π∗ is a Nash equilibrium. □

Example 3 (Illustration of Algorithm 1) L = {0, · · · , 4}. Let us consider the previous ordinal game: Let us start with N

π0E = π0N = [4; 4], that is, π0E (X) = π0N (X) = π0E (Y ) = π0N (Y ) = 4: Uncertainty is maximal. Now,

Furthermore, µPES E (π0 ) = 1, µPES N (π0 ) = 0, A∗N = {Y } and A∗E = {X, Y }. Since AE \ A∗E = ∅, IMPROVE(G, π0 ,E) = π0 . Since AN \ A∗N = {X}, we get IMPROVE(G, π0 ,N) = [π0N (X); n(µPES N (π0 ))] = [4; 3]. Another round of improvement does not give anymore changes. So, π∗ = (π∗E , π∗N ), where π∗E = [4; 4] and π∗N = [4; 3], forms a possibilistic mixed equilibrium of the ordinal game.

4 Concluding Remarks and FutureWork

In this paper, we have proposed first steps towards the definition of possibilistic mixed equilibria in ordinal game theory. Our main contribution has been to show that possibilistic mixed Nash equilibria exist for all possibilistic games and can be computed in polynomial time. This contribution offers several perspectives:

Concisely expressed games. Possibility theory can be embedded nicely in logic, to provide enhanced reasoning tools. [De Clercq et al., 2014] have studied the possibility and necessity of the existence of ONE in games expressed in possibilistic logic. Considering mixed possibilistic equilibria in possibilistic boolean games would be natural. Of course, it is likely that possibilistic mixed equilibrium computation becomes NP-hard.

Competitive Markov Decision Processes. These, also called stochastic games [Filar and Vrieze, 1997] extend both Markov Decision Processes [Puterman, 1994] and games. Possibilistic Markov Decision Processes have been defined in [Sabbadin et al., 1998; Sabbadin, 2001]. Possibilistic competitive MDP are a natural extension to possibilistic MDP.

Partial observability. Games with incomplete information [Harsanyi, 1967; Myerson, 1991] are a first way to deal with partial observability. A second way is Partially Observed Stochastic Games (POSG) [Sorin, 2002], which extend both Partially Observed MDP [Cassandra et al., 1994] and games. Such an extended framework could also be developed in the possibilistic case, by grounding it on the possibilistic POMDP framework [Sabbadin, 2001].

Acknowledgements

This work was supported by the French "Agence Nationale de la Recherche" grant ANR-13-AGRO-0001-04.