Unilateral support equilibria

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 idea1 is to introduce a new equilibrium concept, 

1This 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,(Xi)iN,(πi)iN)

where N is a non-empty, finite set of players, with |N| ≥ 2, Xi 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 : iN X R Xi is 

A strategy combination xX is called a Nash equilibrium if for every i N it holds that 

πi(xi,xi) ≤ πi(xi,xi)

for every xi Xi (Nash, 1950, [4]).2 The set of Nash equi- libria for G is denoted by NE(G). For i N and xi Xi, define the set of best reply strategies against xi, BRi(xi), 

2Note that xi = (xj)jN\{i} Xi = jN\{i} Xj in general. 

as follows: 

BRi(xi) = {xi Xi πi(xi,x i) ≤ πi(xi,xi

for every x i Xi}

Clearly, xNE(G) if and only if xi BRi(xi) for every i N

A strategy combination xX is called a Berge equilibrium if for every i N it holds that 

πi(xi,xi) ≤ πi(xi,xi)

for every xi Xi (Berge, 1957, [1]). The set of Berge equilibria for G is denoted by BE(G). For i N and xi Xi, define the set of best support strategy combinations against xi, BSi(xi), as follows (cf. Musy et al., 2012, [3]): 

BSi(xi) = {xi Xi πi(xi,x i) ≤ πi(xi,xi

for every x i Xi}

Clearly, xBE(G) if and only if xi BSi(xi) 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 xX is called unilaterally supportive with respect to σ if, for every i N

πσ(i)(xi,xi) ≤ πσ(i)(xi,xi)

for every xi Xi. 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,(Xi)iN,(πσ(i))iN)

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 USEId(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 xX be a strategy combination. Then xUSE(G) if and only if for every i N and every j N \ {i} it holds that 

πi(xj,xj) ≤ πi(xj,xj) for every xj Xj. 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

fe1 [ (1,1,0) 1 f2 (0,0,0) f1 (0,0,1) f2 (0,0,0) ] e2 (0,0,0) (0,0,1) (0,0,0) (1,1,0) 

g1 g

Here, G is represented as a trimatrix game.

3That is, in short, player 1 randomizes over e1 and e2, player 2 over 

(e(e2,f2,g2)(e2,f2,g2)2,f2,g2)g2g2g2X

X

X

X

X

e

g1 X

e

g1 X

e1 g1 (a) BS1(·) (b) BS2(·) 

X

X

(c) BS3(·) 

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 ∈ [ 12,1] can (bottom do f

f

f

strategy λe1 + (1 − λ)e2 X1 with part), then the best thing players 2 and 3 to support player 1 is the strategy combina- tion (f1,g1) ∈ 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 (e1,f1,g1) ∈ USE(G). Using the characterization provided in Theorem 1, this can be seen from the following six inequalities: 

π1(e1,x2,g1) ≤ 1 = π1(e1,f1,g1) for every x2 X2; π1(e1,f1,x3) ≤ 1 = π1(e1,f1,g1) for every x3 X3; π2(x1,f1,g1) ≤ 1 = π2(e1,f1,g1) for every x1 X1; π2(e1,f1,x3) ≤ 1 = π2(e1,f1,g1) for every x3 X3; π3(x1,f1,g1)=0= π3(e1,f1,g1) for every x1 X1; π3(e1,x2,g1)=0= π3(e1,f1,g1) for every x2 X2

Consequently, USE(G) = ∅. 

Finally, note that also NE(G) = ∅, since (e1,f1,g2) ∈ NE(G). 

△ 

f1 and f2 and player 3 randomizes over g1 and g2. The pay-off functions are the expected pay-offs. 

e2 e2 e2 f

f

f

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. 

0