## Unilateral support equilibria

**The concept of Nash equilibria is the most well-known concept within non-cooperative game theory and is widely used in many other fields. In a Nash equilibrium, every player maximizes his or her own pay-off with respect to the Nash equilibrium strategy combination of the other players. On the other hand, in a Berge equilibrium, every player’s pay-off is maximized by the group of all other players and this player is thus supported by them. We introduce a new equilibrium concept based on individual support rather than the group support underlying a Berge equilibirum. In a unilateral support equilibrium, every player is supported by every other player individually. **

**Introduction **Non-cooperative game theory deals with situations of interac- tion and conflict between individuals (or players). Within the field of non-cooperative game theory, special attention goes to providing equilibrium concepts to somehow solve these con- flicts. Such a concept should answer the question how to determine a good strategy if you do not know the strategies of the other players beforehand.

The standard Nash equilibrium concept is defined by Nash (1951, [5]) and is based on the fact that no player should have an incentive to unilaterally deviate from an equilibrium strategy.

The idea of Berge (1957, [1]) yields an equilibrium concept in which players are not maximizing their own pay-offs, but maximize the other players’ pay-off instead. This follows the motto of The Three Musketeers: ‘one for all, and all for one’: every player supports (as part of a larger group) every other player and all other players support every single player.

However, the support relation in a Berge equilibrium is re- stricted to group support as the group of all players except for one single player supports the single player in the best way possible. To do so, they have to coordinate their actions, which can cause coordination issues for the players. To avoid these rather complex coordination issues, we consider individ- ual support rather than group support.

Our main idea^{1 }is to introduce a new equilibrium concept,

1_{This Triangle is a short version of our paper ‘Unilateral support }equilibria’, Schouten, Borm, Hendrickx (2019), [6].

which is based on support relations between the individual players. We model these support relations by bijections and in particular, by using derangements, in which there are no fixed points. The interpretation of such a derangement is that every player supports exactly one other player and every player is supported by exactly one other player. Then, a uni- lateral support equilibrium is a strategy combination that is unilaterally supportive with respect to every possible derange- ment.

**Preliminaries **First, we provide the preliminaries on non-cooperative game theory and the two equilibrium concepts. A *non-cooperative (strategic) game *is a triple

*G *= (*N,*(*X*_{i}_{)}_{i}_{∈}_{N}_{,}_{(}_{π}_{i}_{)}_{i}_{∈}_{N}_{)}_{, }

where *N *is a non-empty, finite set of players, with |*N*| ≥ 2, *X*_{i }_{the set of strategies for player }_{i }_{∈ }* _{N }*the pay-off function of player

*i*∈

*N*. Here, called the

*set of strategy combinations*.

_{and }*X *= _{π}_{i }^{∏}_{: }*i*∈*N *_{X }_{→ }_{R }^{X}*i *is

A strategy combination *x*^{∗ }∈ *X *is called a *Nash equilibrium *if for every *i *∈ *N *it holds that

*π*_{i}_{(}* _{x}*∗

_{−}

_{i}*,x*

_{i}_{) ≤ }

_{π}

_{i}_{(}

*∗*

_{x}_{−}

_{i}*,x*

^{∗}

*i*

^{)}

^{, }for every *x*_{i }_{∈ }_{X}_{i }_{(Nash, 1950, [4]).}2 _{The set of Nash equi- }libria for *G *is denoted by *NE*(*G*). For *i *∈ *N *and *x*_{−}_{i }_{∈ }_{X}_{−}_{i}_{, }define the *set of best reply strategies against x*_{−}_{i}_{, }_{BR}_{i}_{(}_{x}_{−}_{i}_{), }

2_{Note that }_{x}_{−}* _{i }*= (

*x*

*)*

_{j}

_{j}_{∈}

_{N}_{\{}

_{i}_{} }∈

*X*

_{−}

*=*

_{i }^{∏}

*j*∈

*N*\{

*i*}

^{X}*j*

^{in general. }

as follows:

*BR*_{i}_{(}_{x}_{−}_{i}_{) = }{_{x}_{i }_{∈ }_{X}* _{i }*∣

_{∣ }

_{π}

_{i}_{(}

_{x}_{−}

_{i}

_{,x }*) ≤*

_{i}*π*

_{i}_{(}

_{x}_{−}

_{i}

_{,x}

_{i}_{) }

for every *x ** _{i }*∈

*X*

*}*

_{i}

_{. }Clearly, *x*^{∗ }∈ *NE*(*G*) if and only if *x*^{∗}*i *^{∈ }^{BR}*i*(*x*^{∗}−*i*^{) for every }*i *∈ *N*.

A strategy combination *x*^{∗ }∈ *X *is called a *Berge equilibrium *if for every *i *∈ *N *it holds that

*π*_{i}_{(}* _{x}*∗

_{i}*,x*

_{−}

_{i}_{) ≤ }

_{π}

_{i}_{(}

*∗*

_{x}

_{i}*,x*

^{∗}−

*i*

^{)}

^{, }for every *x*_{−}_{i }_{∈ }_{X}_{−}_{i }_{(Berge, 1957, [1]). The set of Berge }equilibria for *G *is denoted by *BE*(*G*). For *i *∈ *N *and *x*_{i }_{∈ }_{X}_{i}_{, }define the *set of best support strategy combinations against x*_{i}_{, }_{BS}_{i}_{(}_{x}_{i}_{), as follows (cf. Musy et al., 2012, [3]): }

*BS*_{i}_{(}_{x}_{i}_{) = }{_{x}_{−}_{i }_{∈ }_{X}_{−}* _{i }*∣

_{∣ }

_{π}

_{i}_{(}

_{x}

_{i}

_{,x }_{−}

*) ≤*

_{i}*π*

_{i}_{(}

_{x}

_{i}

_{,x}_{−}

_{i}_{) }

for every *x *_{−}* _{i }*∈

*X*

_{−}

*}*

_{i}

_{. }Clearly, *x*^{∗ }∈ *BE*(*G*) if and only if *x*^{∗}−*i *^{∈ }^{BS}*i*(*x*^{∗}*i*^{) for every }*i *∈ *N*.

Set *N *= {1*,*2*,…,n*}. A *bijection σ *: *N *→ *N *is a map that is both surjective (onto) and injective (one-to-one) and is denoted by *σ *= (*σ*(1)*,σ*(2)*,…,σ*(*n*)). The set of all such bijections is denoted by Π(*N*). The identity bijection is de- noted by *Id*, i.e. *Id *= (1*,*2*,…,n*). In the context of sup- portive behavior, a bijection *σ *∈ Π(*N*) should be interpreted as follows: player *i *∈ *N *supports player *σ*(*i*) ∈ *N*. Finally, we introduce the set of all *derangements*, given by

*D*(*N*) = {*δ *∈ Π(*N*) | *δ*(*i*) = *i *for every *i *∈ *N*}*. *

**Unilateral support equilibria **We start by introducing unilaterally supportive strategy com- binations with respect to a bijection. Afterwards, this is gen- eralized to the definition of a unilateral support equilibrium, where the dependence on a certain bijection is removed.

**Definition 1 **Let *G *be a non-cooperative game and let *σ *∈ Π(*N*) be a bijection. A strategy combination *x*^{∗ }∈ *X *is called *unilaterally supportive with respect to σ *if, for every *i *∈ *N*,

*π*_{σ}_{(}_{i}_{)}_{(}* _{x}*∗

_{−}

_{i}*,x*

_{i}_{) ≤ }

_{π}

_{σ}_{(}

_{i}_{)}

_{(}

*∗*

_{x}_{−}

_{i}*,x*

^{∗}

*i*

^{)}

^{, }for every *x*_{i }_{∈ }_{X}_{i}_{. The set of such strategy combinations is }denoted by *USE*_{σ}_{(}_{G}_{). }* _{⊲ }*In a unilaterally supportive strategy combination with respect to a bijection

*σ*, player

*i*∈

*N*supports player

*σ*(

*i*) ∈

*N*in the best way possible. This means that player

*i*is going to maximize the pay-off of player

*σ*(

*i*), given the unilaterally sup- portive strategy combination of the other players. This implies that every set of unilaterally supportive strategy combinations with respect to a bijection

*σ*of a game

*G*coincides with the set of Nash equilibria of the game

*G*

_{σ }_{with twisted pay-off }functions, in which player

*i*’s pay-off function is replaced by the pay-off function of player

*σ*(

*i*), i.e.,

*G*_{σ }_{= }(_{N,}_{(}_{X}_{i}_{)}_{i}_{∈}_{N}_{,}_{(}_{π}_{σ}_{(}_{i}_{)}_{)}_{i}_{∈}* _{N}*)

_{. }**Proposition 1 ***Let G be a non-cooperative game and let σ *∈ Π(*N*) *be a bijection. Then it holds that *

*USE*_{σ}_{(}_{G}_{) = }_{NE}_{(}_{G}_{σ}_{)}_{. }

**Remark **Note that if one applies Proposition 1 to the iden- tity bijection, it follows that *USE*_{Id}_{(}_{G}_{) = }_{NE}_{(}_{G}_{). }For every bijection, the corresponding set of unilaterally sup- portive strategy combination with respect to that bijection can be defined. However, only derangements really reflect the idea of supportive behavior. If a player is mapped to himself, then this player does not support another player. The set of unilaterally supportive strategy combinations with respect to a derangement has the disadvantage that it is not anonymous in the sense that it relies on the predetermined support rela- tions given by the derangement. For this reason, in order to define the set of unilateral support equilibria, we will consider the set of unilaterally supportive strategy combinations with respect to all derangements.

**Definition 2 **Let *G *be a non-cooperative game. Then the set of *unilateral support equilibria *is defined as *USE*(*G*) = ^{⋂ }

*δ*∈*D*(*N*)^{USE}*δ*(*G*)*. ⊲ *

The following theorem provides an alternative formulation of the set of unilateral support equilibria in terms of the pay-off functions. This contrasts the definition, which is formulated as the intersection of sets of unilaterally supportive strategy

combinations. The theorem clearly highlights the underlying feature of unilaterally supportive behavior.

**Theorem 1 ***Let G be a non-cooperative game and let x*^{∗ }∈ *X be a strategy combination. Then x*^{∗ }∈ *USE*(*G*) *if and only if for every i *∈ *N and every j *∈ *N *\ {*i*} *it holds that *

*π*_{i}_{(}* _{x}*∗

_{−}

_{j}*,x*

_{j}_{) ≤ }

_{π}

_{i}_{(}

*∗*

_{x}_{−}

_{j}*,x*

^{∗}

*j*

^{) }

^{for every x}*j*∈

*X*

_{j}

_{. }**Unilateral support, Berge and Nash equilibria**Theorem 1 shows that in a unilateral support equilibrium, ev- ery player is supported by every other player individually. In a Berge equilibrium, every player is supported by the group of all other players together. Subsequently, every Berge equilibrium is in fact a unilateral support equilibrium. This result is based on the fact that a Berge equilibrium is unilaterally supportive with respect to any derangement.

**Theorem 2 ***Let G be a non-cooperative game. Then it holds that BE*(*G*) ⊆ *USE*(*G*)*. *

For a two-person game, however, the group of all other players together consists of only one other player. This implies that the set of Berge equilibria consists of those strategy combi- nations in which every player is supported by the other player in the best way possible. Hence, the set of Berge equilibria coincides with the set of unilateral support equilibria.

**Proposition 2 ***Let G be a non-cooperative game with *|*N*| = 2*. Then it holds that *

*BE*(*G*) = *USE*(*G*) = *NE*(*G*_{(2}_{,}_{1)}_{)}_{. }

To conclude, we give an example of a game in which there is a unilateral support equilibrium, while there is no Berge equilibrium. This shows that the inclusion of Theorem 2 is a strict inclusion.

**Example 1 **Consider the following game, proposed by Corley (2015, [2]):

*G *=

*f*_{e}_{1 }_{[ (1}_{,}_{1}_{,}_{0) }_{1 }_{f}_{2 }_{(0}_{,}_{0}_{,}_{0) }_{f}_{1 }_{(0}_{,}_{0}_{,}_{1) }_{f}_{2 }_{(0}_{,}_{0}_{,}_{0) ] }*e*_{2 }_{(0}_{,}_{0}_{,}_{0) (0}_{,}_{0}_{,}_{1) (0}_{,}_{0}_{,}_{0) (1}_{,}_{1}_{,}_{0) }

*g*_{1 }_{g}_{2 }

*. *

Here, *G *is represented as a trimatrix game.^{3 }

3_{That is, in short, player 1 randomizes over }_{e}_{1 }_{and }_{e}_{2}_{, player 2 over }

(e(e_{2},f_{2},g_{2})(e_{2},f_{2},g_{2})_{2},f_{2},g_{2})g_{2}g_{2}g_{2}X_{3 }

X_{3 }

X_{2 }

X_{2 }

_{X}_{1 }

e_{1 }

_{g}_{1 }_{X}_{1 }

e_{1 }

_{g}_{1 }_{X}_{1 }

e_{1 }_{g}_{1 }**(a) ***BS*_{1}_{(·) }**(b) ***BS*_{2}_{(·) }

X_{3 }

X_{2 }

**(c) ***BS*_{3}_{(·) }

**Figure 1 ***– The three sets of best support strategy combinations corresponding to BE*(*G*)

First, we show that there are no Berge equilibria by using the sets of best support strategy combinations, which are presented in Figure 1. For example, Figure 1a shows that, if player 1 chooses a *λ *together ∈ [ ^{1}2^{,}^{1] }can ^{(bottom }do f_{2 }

f_{2 }

f_{2 }

strategy *λe*_{1 }_{+ (1 − }_{λ}_{)}_{e}_{2 }_{∈ }_{X}_{1 }_{with }^{part), then the best thing players 2 and 3 }to support player 1 is the strategy combina- tion (*f*_{1}_{,g}_{1}_{) ∈ }_{X}_{−1}_{. }

Using Figure 1, it can be readily seen that the intersection between the three sets of best support strategy combinations is empty. Hence, *BE*(*G*) = ∅.

Secondly, we show that (*e*_{1}_{,f}_{1}_{,g}_{1}_{) ∈ }_{USE}_{(}_{G}_{). Using the }characterization provided in Theorem 1, this can be seen from the following six inequalities:

*π*_{1}_{(}_{e}_{1}_{,x}_{2}_{,g}_{1}_{) ≤ 1 = }_{π}_{1}_{(}_{e}_{1}_{,f}_{1}_{,g}_{1}_{) for every }_{x}_{2 }_{∈ }_{X}_{2}_{; }*π*_{1}_{(}_{e}_{1}_{,f}_{1}_{,x}_{3}_{) ≤ 1 = }_{π}_{1}_{(}_{e}_{1}_{,f}_{1}_{,g}_{1}_{) for every }_{x}_{3 }_{∈ }_{X}_{3}_{; }*π*_{2}_{(}_{x}_{1}_{,f}_{1}_{,g}_{1}_{) ≤ 1 = }_{π}_{2}_{(}_{e}_{1}_{,f}_{1}_{,g}_{1}_{) for every }_{x}_{1 }_{∈ }_{X}_{1}_{; }*π*_{2}_{(}_{e}_{1}_{,f}_{1}_{,x}_{3}_{) ≤ 1 = }_{π}_{2}_{(}_{e}_{1}_{,f}_{1}_{,g}_{1}_{) for every }_{x}_{3 }_{∈ }_{X}_{3}_{; }*π*_{3}_{(}_{x}_{1}_{,f}_{1}_{,g}_{1}_{)=0= }_{π}_{3}_{(}_{e}_{1}_{,f}_{1}_{,g}_{1}_{) for every }_{x}_{1 }_{∈ }_{X}_{1}_{; }*π*_{3}_{(}_{e}_{1}_{,x}_{2}_{,g}_{1}_{)=0= }_{π}_{3}_{(}_{e}_{1}_{,f}_{1}_{,g}_{1}_{) for every }_{x}_{2 }_{∈ }_{X}_{2}_{. }

Consequently, *USE*(*G*) = ∅.

Finally, note that also *NE*(*G*) = ∅, since (*e*_{1}_{,f}_{1}_{,g}_{2}_{) ∈ }_{NE}_{(}_{G}_{). }

△

*f*1 and *f*2 and player 3 randomizes over *g*1 and *g*2. The pay-off functions are the expected pay-offs.

e_{2 }e_{2 }e_{2 }f_{1 }

f_{1 }

f_{1 }

Dit omhoog zetten misschien, in plaats van halverwege de pagina

**References **

[1] Berge, C. (1957). *Théorie générale des jeux à n personnes. *

Gauthier-Villars, Paris. [2] Corley, H. (2015). A mixed cooperative dual to the Nash equi-

librium. *Game Theory*, **2015**, article ID 647246. [3] Musy, O., A. Pottier, and T. Tazdaït (2012).A new theorem to find Berge equilibria. *International Game Theory Review, ***14**, article ID 1250005. [4] Nash, J. (1950). Equilibrium points in n-person games. *Pro- ceedings of the National Academy of Sciences of the USA*, **36**, 48–49 [5] Nash, J. (1951). Non-cooperative games. *Annals of Mathe- *

*matics, ***54**, 286–295. [6] Schouten, J., P. Borm and R. Hendrickx (2019). Unilateral support equilibria. *Journal of Mathematical Psychology*, **93**, 102295.