Open access peer-reviewed chapter

# Pareto Optimality and Equilibria in Noncooperative Games

Written By

Vladislav Zhukovskiy and Konstantin Kudryavtsev

Submitted: November 17th, 2018 Reviewed: June 22nd, 2019 Published: November 26th, 2020

DOI: 10.5772/intechopen.88184

From the Edited Volume

## Multicriteria Optimization

Edited by Nodari Vakhania and Frank Werner

Chapter metrics overview

View Full Metrics

## Abstract

This chapter considers the Nash equilibrium strategy profiles that are Pareto optimal with respect to the rest of the Nash equilibrium strategy profiles. The sufficient conditions for the existence of such pure strategy profiles are established. These conditions employ the Germeier convolutions of the payoff functions. For the noncooperative games with compact strategy sets and continuous payoff functions, the existence of the Pareto-optimal Nash equilibria (PoNE) in mixed strategies is proven.

### Keywords

• Pareto optimality
• Nash equilibrium
• Pareto-optimal Nash equilibrium
• noncooperative game
• Germeier convolution

## 1. Introduction

In 1949, J. Nash, a Princeton University graduate at that time and a famous American mathematician and economist as we know him today, suggested the notion of an equilibrium solution for a noncooperative game [1] lately called “the Nash equilibrium strategy profile.” Since then, this equilibrium is widely used in economics, sociology, military sciences, and other spheres of human activity. Moreover, 45 years later J. Nash, J. Harshanyi, and R. Selten were awarded the Nobel Prize “for the pioneering analysis of equilibria in the theory of noncooperative games.”

However, as shown by Example 1, the set of the Nash equilibrium strategy profiles has a negative property: there may exist two Nash equilibrium strategy profiles such that the payoffs of each player in the first strategy profile are strictly greater than the corresponding payoffs in the second one. In 2013, the authors emphasized this fact in a series of papers [2, 3] while exploring the existence of a guaranteed equilibrium solution for a noncooperative game under uncertainty. Particularly, these papers were focused on the Nash equilibrium strategy profile that is Pareto optimal with respect to the rest of the Nash equilibrium strategy profiles, thereby eliminating the above shortcoming. And the following question arises immediately. How can such an equilibrium (the so-called Pareto equilibrium strategy profile) be found? Our idea is to use the sufficient conditions (Theorem 1) reducing Nash equilibrium strategy profile design to saddle point calculation in a special Germeier convolution of the payoff functions. As an application, this chapter establishes the existence of the Pareto-optimal Nash equilibrium (PoNE) strategy profile in the class of mixed strategies (see Assertion 1). Similar results were obtained by the authors for the Pareto-optimal Berge equilibrium in [4].

Note that two approaches can be adopted to perform formalization of the Pareto unimprovable Nash equilibrium. According to the first approach, Pareto optimality is required on the set of all strategy profiles in the game. The second approach dictates to find the Pareto-optimal equilibrium on the set of all Nash equilibria. Generally, the first approach implies construction of all Nash equilibrium strategy profiles with subsequent check belonging to the Pareto boundary of the strategy profile set of the game (see [5]). Numerical algorithms realizing this approach were suggested for the bimatrix games in [5], for some two-player normal-form games in [6] and the monograph ([7], pp. 92–93), as well as for the linear two-player positional games with cylindrical terminal payoff functions in [8]. In the case of nonlinear differential games with convex terminal payoff functions, the publication [9] obtained the sufficient conditions under which the unimprovable equilibrium strategy profile on the set of Nash equilibria (the second approach) is Pareto optimal on the whole strategy profile set of the game.

This chapter adheres to the second approach, suggesting an algorithm that yields the Pareto-optimal strategy profile among all Nash equilibria.

## 2. Internally instable set of Nash equilibrium strategy profiles

As is well known, the game theory is used in modeling interactions in economics, sociology, political science, and many other areas. Game theory is the mathematical study of conflict, in which a decision-maker’s success in making choices depends on the choice of others. In contrast to the decision-making theory, in game theory, several decision-makers act simultaneously. These decision-makers are called players. Their actions are called pure strategies. Each of the players seeks to achieve their own goals that do not coincide with the goals of other players. A measure of a player’s approach of a goal is estimated by his payoff function. The realized value of the player’s payoff function is called his payoff. At the same time, the player’s payoff function depends not only on his choice but also on the choice of all other players. Therefore, when making a decision, the player is forced to focus not only on his own interests but also on the possible actions of the other players. If the players cannot coordinate their actions, the game is called a noncooperative game. The basic concept of a solution in a noncooperative game theory is the Nash equilibrium.

Consider a noncooperative game (NG) of N players in the class of pure strategies (a non-antagonistic game)

Γ = N X i i N f i x i N , E1

where N = 1 2 N is the set of players’ serial numbers; each player i chooses and applies his own pure strategy x i X i R n i , forming no coalition with the others, which induces a strategy profile x = x 1 x N X = i N X i R n n = n 1 + + n N ; for each i N , a payoff function f i x is defined on the strategy profile set X , which gives the payoff of player i. In addition, denote f = f 1 f N and x z i = x 1 x i 1 z i x i + 1 x N .

Definition 1. A strategy profile x e = x 1 e x N e X is called a Nash equilibrium in the game (1) if

max x i X i f i x e x i = f i x e i N . E2

The set of all x e in game (1) will be designated by X e .

Now, consider internal instability of X e . A subset X R n is internally instable if there exist at least two strategy profiles x j X j = 1 2 such that

f x 1 < f x 1 f i x 1 < f i x 1   i N , E3

internally stable otherwise.

Example 1. Consider a two-player NG of the form

1 2 X i = 1 1 i = 1 , 2 f i x = x i 2 + 2 x 1 x 2 i = 1 , 2 . E4

A strategy profile x e = x 1 e x 2 e 1 1 2 is a Nash equilibrium in game (4) if

x 1 2 + 2 x 1 x 2 e x i e 2 + 2 x 1 e x 2 e , x 2 2 + 2 x 1 e x 2 x i e 2 + 2 x 1 e x 2 e x 1 , x 2 1 1 ,

which is equivalent to

x 1 x 2 e 2 x 1 e x 2 e 2 , x 1 e x 2 2 x 1 e x 2 e 2 .

Therefore, we have X e = α α α 1 1 and f i X e = x e X e f i x e = α 1 1 α 2 α 2 in game (4). Consequently, the set X e is internally instable in game (4); as for x 1 = 0 0 and x 2 = 1 1 , it follows that f i x 1 = 0 < f i x 2 = 1 i = 1 2 (see Eq. (3)).

Note 1. In the antagonistic setting of game (1) ( N = 1 2 and f 1 x = f 2 x ), the equality f 1 x 1 = f 1 x 2 holds for any two saddle points x j X j = 1 2 by the saddle point equivalence. Hence, the saddle point set is always internally stable in the antagonistic game. Note that a saddle point is a Nash equilibrium strategy profile in the antagonistic setting of game (1).

Note 2. In the non-antagonistic setting of game (1), the internal instability effect vanishes if there exist a unique Nash equilibrium strategy profile in (1).

Associate the following auxiliary N-criterion problem with game (1):

Γ v = X e f i x i N , E5

where the set X e of alternatives x coincides with the set of Nash equilibrium strategy profiles x e in game (1) and the ith criterion f i x is the payoff function of player i.

Definition 2. An alternative x P X e is Pareto optimal (efficient) in problem (5) if x X e the system of inequalities

f i x f i x P i N

is infeasible, with at least one being a strict inequality. Designate by X P the set of all x P .

According to Definition 2, the set X P satisfies the inclusion X P X e and is internally stable.

The following statement is obvious: if for all x X e we have

i N f i x i N f i x P , E6

then x P gives the Pareto-optimal alternative in problem (5).

## 3. Sufficient conditions of Pareto-optimal equilibrium

Get back to game (1), associating it with the N-criterion problem (5).

Definition 3. A strategy profile x X is called a Pareto-optimal Nash equilibrium for game (1) if x is a Nash equilibrium in (1) (Definition 1) and a Pareto optimum in (5) (Definition 2).

Note 3. Two classes of games where the Pareto equilibrium strategy profiles exist in pure strategies were presented in ([7], pp. 91–92) and, in the case of differential games, in [9, 10, 11, 12].

Note 4. Within Example 1, we have two Pareto equilibrium strategy profiles, namely, x = 1 1 and x = 1 1 .

Based on (2) and (5), introduce N + 1 scalar functions defined by

φ i x z = f i z x i f i z   i N , φ N + 1 x z = r N f r x r N f r z , E7

where z = z 1 z N , z i X i i N , z X , x X . The Germeier convolution ([13], p. 43) of the scalar functions (7) has the form

φ x z = max j = 1 , , N + 1 φ j x z . E8

In addition, associate the following antagonistic game with game (1) and the N-criterion problem (5):

X Z = X φ x z . E9

In this game, player 1 and his opponent choose their strategies x X and z X to maximize and minimize, respectively, the payoff function φ x z described by (7) and (8).

A saddle point x o z X 2 of game (9) is defined by the chain of inequalities

φ x z φ x 0 z φ x 0 z x , z X . E10

In game (9), the saddle points are given by the minimax strategy z

min z X max x X φ x z = max x X φ x z

and the maximin strategy x 0

max x X min z X φ x z = min z X φ x 0 z .

The following statement defines a sufficient condition for the existence of a PoNE strategy profile in game (1).

Theorem 1. If a saddle point x o z exists in the antagonistic game (9) (i.e., the condition (10) holds), then the minimax strategy z is a PoNE strategy profile for game (1) [14].

Proof. Let z = x 0 for the right-hand inequality in (10). Using (7) and (8), we have

φ x 0 x 0 = max j = 1 , , N + 1 φ j x 0 x 0 = 0 .

By (10), for all x X it follows that

0 φ x z = max j = 1 , , N + 1 φ j x z = 0 .

Therefore, for all x X , the following chain of implications is true:

0 max j = 1 , , N + 1 φ j x z φ j x z
φ j x z 0   j = 1 N N + 1   7
7 f j z x i f j z 0   x i X i i N
r N f r x r N f r z 0   x X e
max x i X i f j z x i = f j z   i N
max x X e i N f i x = i N f i z 2 , 6 z X e z X P .

This chain involves the inclusion X e X .

Remark 1. Theorem 1 substantiates the following design method of the PoNE strategy profile x in game (1).

Step 1. Using the payoff functions f i x i N from (1) and the vectors z = z 1 z N , z i X i and x = x 1 x N , x i X i i N , construct the function φ x z by formulas (7) and (8).

Step 2. Find the saddle point x o z of antagonistic game (9). Then z is the Pareto equilibrium solution of game (1).

As far as the authors know, numerical calculation methods of the saddle point x o z for the Germeier convolution

φ x z = max j = 1 , , N + 1 φ j x z

have not been developed yet. However, they are vital to construct the Nash equilibrium strategy profiles that are Pareto optimal (see Theorem 1). This is a new trend in equilibrium programming; in the authors’ opinion, it can be developed using the mathematical apparatus of Germeier convolution optimization max j φ j x proposed by Dem’yanov [15].

Remark 2. The results of operations research ([16], p. 54) yield the following statement that is crucial to prove the existence of a PoNE strategy profile in the class of mixed strategies in game (1) (see the forthcoming section). If X i comp R n i and f i C X i N in game (1), then the Germeier convolution φ x z = max j = 1 , , N + 1 φ j x z from (7) and (8) is continuous on X × X .

## 4. Existence of PoNE strategy profile in mixed strategies

That game (1) admits a PoNE strategy profile in the class of pure strategies (see Definition 3) is rather a miracle. This equilibrium may exist only for special payoff functions, strategy sets, and numbers of players. Therefore, adhering to the approach associated with E. Borel [17], J. von Neumann [18], Nash [1], and their followers, we establish the existence of the PoNE strategy profile of game (1) in the class of mixed strategies under standard game theory restrictions (i.e., compact strategy sets and continuous payoff functions).

And so, suppose that in game (1) the sets X i of the pure strategies x i are compact sets in R n i (are closed and bounded), whereas the payoff function f i x of each player i i N is continuous on the set of pure strategy profiles X .

Consider the mixed strategy extension of game (1). To this end, construct the Borel σ-algebra B X i on each compact set X i i N and probability measures ν i on B X i (i.e., nonnegative scalar functions defined on the elements of B X i that are countably additive and normalized to unity on X i ). Denote by ν i the whole set of such measures; the measure ν i proper is called the mixed strategy of player i i N in game (1). Next, for game (1) construct the mixed strategy profiles, that is, the multiplicative measures

ν dx = ν 1 dx 1 ν N dx N ,

and designate by ν the set of such strategy profiles. And finally, find the mathematical expectations

f i ν = X f i x ν dx   i N . E11

As a result, the game Γ from (1) is associated with its mixed strategy extension

Γ ˜ = N ν i i N f i ν i N .

In the noncooperative game Γ ˜ , we have the following elements:

ν i ν i as the mixed strategy of player i.

ν ν as the mixed strategy profile.

f i ν as the payoff function of player i defined by (11).

Further exposition involves the vector z = z 1 z N X with z i X i i N , and, of course, the vector x = x 1 x N X , as well as the mixed strategy profiles ν , μ ν and the mathematical expectations

f i ν = X f i x ν dx , f i μ = X f i z μ dz , f i μ ν i = X 1 X i 1 X i X i + 1 X N f i x μ N dz N μ i + 1 dz i + 1 ν i dx i μ i 1 dz i 1 μ 1 dz 1 . E12

Once again, we underline that x i , z i X i i N and x , z X .

The following notion of the Nash equilibrium strategy profile ν e ν in mixed strategies in original game (1) answers to Definition 1 of the Nash equilibrium strategy profile x e X in pure strategies in the same game (1).

Definition 4. A strategy profile ν e ν is called a Nash equilibrium for the game Γ ˜ if

f i ν e ν i f i ν e   ν i ν i   i N ; E13

throughout the paper, ν e ν will be also called the Nash equilibrium strategy profile in mixed strategies for game (1).

By the Glicksberg theorem [19], there exists a Nash equilibrium strategy profile in mixed strategies in game (1) under X i comp R n i and f i C X i N . Denote by N the set of such profiles ν e .

Associate the following N-criterion problem with the game Γ ˜

Γ ˜ υ = N f i ν i N . E14

In (14), a decision-maker chooses a strategy profile ν N to simultaneously maximize all components of the vector criterion f ν = f 1 ν f N ν . The notion of the Pareto optimal strategy profile is conventional (see below).

Definition 5. A strategy profile ν P N is called Pareto optimal for the N-criterion problem Γ ˜ υ from (14) if for any ν N the system of inequalities

f i ν f i ν P   i N

is infeasible, with at least one inequality being strict.

The following statement represents an analog of (6): if for all ν N we have

i N f i ν i N f i ν P , E15

then the mixed strategy profile ν P N is Pareto optimal in the problem Γ ˜ υ from (14).

Combining Definition 4 with Definition 5 leads to.

Definition 6. A strategy profile ν ν is called a Pareto-optimal Nash equilibrium strategy profile in mixed strategies for game (1) if ν is a Nash equilibrium in Γ ˜ (according to Definition 4), and ν is Pareto optimal in the multicriterion problem Γ ˜ υ (according to Definition 5).

Now, we prove the existence of a Nash equilibrium strategy profile in mixed strategies that is Pareto optimal with respect to the rest Nash equilibrium strategy profiles.

Assertion 1. Consider the noncooperative game (1) where:

1. The pure strategy set X i of each player i is a nonempty compact set in R n i i N .

2. The payoff function f i x of player i i N is continuous on the strategy profile set X .

Then there exists a PoNE strategy profile in mixed strategies in game (1).

Proof. Using formulas (7) and (8), construct the scalar function

φ x z = max j = 1 , , N + 1 φ j x z ,

where

φ i x z = f i z x i f i z i N , φ N + 1 x z = r N f r x r N f r z ,

According to the construction procedure and Remark 2, the function φ x z is defined and continuous on the product of compact sets X × X .

Define the auxiliary antagonistic game

Γ a = I II X Z = X φ x z ,

where players I and II seek to maximize and minimize, respectively, the function φ x z continuous on X × Z Z = X by choosing their strategies x X and z X .

Now, apply a special case of the Glicksberg theorem [19] to the game Γ a , as the saddle point in this game coincides with the Nash equilibrium strategy profile in the two-player noncooperative game

Γ 2 = I II X Z = X f I x z = φ x z f II x z = φ x z .

In this game, player I seeks to maximize f I x z = φ x z by choosing his strategy x X , whereas player II tries to maximize f II x z = φ x z The sets X and X = Z in game Γ 2 are compact, while the payoff functions f I x z and f II x z are continuous on X × Z ; hence, by the Glicksberg theorem, there exists a Nash equilibrium strategy profile ν e μ in the mixed extension Γ 2 :

Γ ˜ 2 = I II ν μ f i ν μ = X X f i x z ν dx μ dz i = I , II .

In addition, ν e μ is simultaneously a saddle point of the mixed extension of the game Γ a :

Γ ˜ a = I II ν μ φ ν μ = X X φ x z ν dx μ dz .

Thus, according to the Glicksberg theorem, there exists a pair ν e μ representing a saddle point of φ ν μ , that is,

φ ν μ φ ν e μ φ ν e μ , ν , μ ν . E16

Letting μ = ν e in the right inequality of (16) gives φ ν e ν e = 0 and so, ν ν formula (16) implies

0 φ ν μ = X X max j = 1 , , N + 1 φ j x z ν dx μ dz . E17

It was established in [3] that

max j = 1 , , N + 1 X X φ j x z ν dx μ dz X X max j = 1 , , N + 1 φ j x z ν dx μ dz . E18

Note that this property has an analog: the maximum of the sum of functions does not exceed the sum of their maxima. It follows from (17) and (18) that

max j = 1 , , N + 1 X X φ j x z ν dx μ dz 0   ν ν ,

and then surely for each j = 1 , , N , N + 1 , we have

X X φ j x z ν dx μ dz 0   ν ν . E19

Next, taking into account the normalized mixed strategies and the normalized mixed strategy profiles, that is, the conditions

X ν i dx i = 1 , X μ i dz i = 1 i N , X ν dx = 1 , X μ dz = 1 E20

that hold ν i ν i , μ i μ i , ν ν , μ μ , we distinguish between two cases, namely, j N and j = N + 1 . For each of these cases, it is necessary to refine inequalities (19).

Case 1: j N . Using (7) and (20) for each i N , inequality (19) is reduced to the form

X X f i z x i f i z ν dx μ dz = X X i f i z x i f i z ν i dx i μ dz = = X X f i z x i ν i dx i μ dz X f i z μ dz X i ν i dx i = 12 , 20 = 12 , 20 X 1 X i 1 X i X i + 1 X N f i z 1 z i 1 x i z i + 1 z N μ N dz N μ i + 1 dz i + 1 ν i dx i μ i 1 dz i 1 μ 1 dz 1 f i μ =
= f i μ ν i f i μ 0   ν i ν i .

In combination with (13), this result gives the inclusion μ N , that is, the mixed strategy profile μ is a Nash equilibrium for the game (1) by Definition 4.

Case 2: j = N + 1 . Here inequality (19) acquires the form

X X φ N + 1 x z ν dx μ dz   = 7 X X i N f i x ν dx μ dz X X i N f i x ν dx μ dz =
= X i N f i x ν dx X μ dz X i N f i z μ dz X ν dx = 20
= 20 i N X f i x ν dx i N X f i z μ dz = 12 i N f i ν i N f i μ 0   ν N ,

in as much as N ν . This immediately yields (15) for ν P = μ , that is, the strategy profile μ is Pareto optimal for the N-criterion problem Γ ˜ υ from (14) by Definition 5.

This outcome and the inclusion μ N conclude the proof.

Note 5. Another proof of Assertion 1 can be found in ([3], pp. 13–15).

## 5. Conclusions

Vorob’ev, the founder of game theory in Russia, believed that its subject [20] is answering the following three questions:

1. What is the optimality of a given game?

2. Does an optimal solution exist?

3. How can it be found?

For the many-player noncooperative games, the answer to the first question is the PoNE strategy profile.

The answer to the second question is given by Assertion 1: if the strategy sets are compact and the payoff functions are continuous, then a Pareto equilibrium strategy profile exists in the class of mixed strategies.

As turned out, the answer to the third question is not so simple. At first glance, one should just construct the Germeier convolution of the payoff functions using formulas (7) and (8) and find the saddle point (10); then the minimax strategy entering the saddle point is the PoNE strategy profile. This equilibrium design method is dictated by Theorem 1, actually being the basic result of the present paper. However, the issues of saddle point construction for the Germeier convolutions have not been developed so far. The usage of specific numerical algorithms and their complexity still remain under investigated. Further research by the authors and, hopefully, by the readers will endeavor to improve the situation.

## References

1. 1. Nash JF. Equilibrium points in N-Person games. Proceedings of the National Academy of Sciences of the United States of America. 1950;36:48-49
2. 2. Zhukovskiy VI, Kudryavtsev KN. Equilibrating conflicts under uncertainty. I. Analogue of a saddle-point. Matematicheskaya Teoriya Igr i Ee Prilozheniya. 2013;5(1):27-44
3. 3. Zhukovskiy VI, Kudryavtsev KN. Equilibrating Conflicts under Uncertainty. II. Analogue of a Maximin. Matematicheskaya Teoriya Igr i Ee Prilozheniya. 2013;5(2):3-45
4. 4. Zhukovskiy VI, Kudryavtsev KN. Mathematical foundations of the Golden Rule. I. Static case. Automation and Remote Control. 2017;78(10):1920-1940. DOI: 10.1134/S0005117917100149
5. 5. Gatti N, Rocco M, Sandhom T. On the verification and computation of strong Nash equilibrium. In: Proceedings of the ACM International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS); 6–10 May 2013; Saint Paul, USA. 2013. pp. 723-730
6. 6. Gasko N, Suciu M, Lung RI, Dumitrescu D. Pareto-optimal Nash equilibrium detection using an evolutionary approach. Acta Universitatis Sapientiae. 2012;4(2):237-246
7. 7. Podinovskii VV, Nogin BD. Pareto Optimal Solutions of Multicriteria Problems. Moscow: Fizmatlit; 2007
8. 8. Kleimenov AF, Kuvshinov DR, Osipov SI. Nash and Stackelberg solutions numerical construction in a two-person nonantagonistic linear positional differential game. Trudy Instituta Matematiki i Mekhaniki UrO RAN. 2009;15(4):120-133
9. 9. Mamedov MB. Investigation of unimprovable equilibrium situations in nonlinear conflict-controlled dynamical systems. Zhurnal Vychislitel′noy Matematiki i Matematicheskoy Fiziki. 2004;44(2):308-317
10. 10. Kononenko AF, Konurbaev EM. Existence of equilibrium profiles in the class of positional strategies that are pareto optimal for certain differential games. In: Game Theory and Its Applications. Kemerovo: Kemerovo State University; 1983. pp. 105-115
11. 11. Mamedov MB. On a Nash Equilibrium Profile Being Pareto Optimal. Izvestiya Akademii Nauk Azerbaĭdzhana: Seriya Fiziko-Tekhnicheskikh. 1983;4(2):11-17
12. 12. Starr AW, Ho YC. Further properties of nonzero-sum differential games. The Journal of Optimization Theory and Applications. 1969;3(4):207-219
13. 13. Germeier YB. Introduction to the Theory of Operations Research. Moscow: Nauka; 1971
14. 14. Kudryavtsev K, Zhukovskiy V, Stabulit I. One method for computing the Pareto-optimal Nash equilibrium in bimatrix game. In: 2017 Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of VF Demyanov)(CNSA). IEEE; 2017. pp. 1-3. DOI: 10.1109/CNSA.2017.7973978
15. 15. Dem’yanov VF, Malozemov VN. Introduction to Minimax. Moscow: Nauka; 1972
16. 16. Morozov VV, Sukharev AG, Fedorov VV. Operations Research in Problems and Exercises. Moscow: Nauka; 1986
17. 17. Borel E. La th’eorie du jeu et les equations int’engrales a noyau sym’etrique. Comptes rendus de l'Académie des Sciences. 1921;173:1304-1308
18. 18. von Neumann J. Zur Theorie der Gesellschaftspiele. Mathematische Annalen. 1928;100(1):295-320
19. 19. Glicksberg IL. A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points. Proceedings of American Mathematical Society. 1952;3(1):170-174
20. 20. Vorob’ev NN. The present state of the theory of games. Russian Mathematical Surveys. 1970;25(2):77-136

Written By

Vladislav Zhukovskiy and Konstantin Kudryavtsev

Submitted: November 17th, 2018 Reviewed: June 22nd, 2019 Published: November 26th, 2020