Open access peer-reviewed chapter

Pareto Optimality and Equilibria in Noncooperative Games

By Vladislav Zhukovskiy and Konstantin Kudryavtsev

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

DOI: 10.5772/intechopen.88184

Downloaded: 81

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)

Γ=NXiiNfixiN,E1

where N=12Nis the set of players’ serial numbers; each player i chooses and applies his own pure strategy xiXiRni, forming no coalition with the others, which induces a strategy profile x=x1xNX=iNXiRnn=n1++nN; for each iN, a payoff function fixis defined on the strategy profile set X, which gives the payoff of player i. In addition, denote f=f1fNand xzi=x1xi1zixi+1xN.

Definition 1. A strategy profile xe=x1exNeXis called a Nash equilibrium in the game (1) if

maxxiXifixexi=fixeiN.E2

The set of all xein game (1) will be designated by Xe.

Now, consider internal instability of Xe. A subset XRnis internally instable if there exist at least two strategy profiles xjXj=12such that

fx1<fx1fix1<fix1 iN,E3

internally stable otherwise.

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

12Xi=11i=1,2fix=xi2+2x1x2i=1,2.E4

A strategy profile xe=x1ex2e112is a Nash equilibrium in game (4) if

x12+2x1x2exie2+2x1ex2e,x22+2x1ex2xie2+2x1ex2ex1,x211,

which is equivalent to

x1x2e2x1ex2e2,x1ex22x1ex2e2.

Therefore, we have Xe=ααα11and fiXe=xeXefixe=α11α2α2in game (4). Consequently, the set Xeis internally instable in game (4); as for x1=00and x2=11, it follows that fix1=0<fix2=1i=12(see Eq. (3)).

Note 1. In the antagonistic setting of game (1) (N=12and f1x=f2x), the equality f1x1=f1x2holds for any two saddle points xjXj=12by 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=XefixiN,E5

where the set Xeof alternatives xcoincides with the set of Nash equilibrium strategy profiles xein game (1) and the ith criterion fixis the payoff function of player i.

Definition 2. An alternative xPXeis Pareto optimal (efficient) in problem (5) if xXethe system of inequalities

fixfixPiN

is infeasible, with at least one being a strict inequality. Designate by XPthe set of all xP.

According to Definition 2, the set XPsatisfies the inclusion XPXeand is internally stable.

The following statement is obvious: if for all xXewe have

iNfixiNfixP,E6

then xPgives 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 xXis called a Pareto-optimal Nash equilibrium for game (1) if xis 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=11and x=11.

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

φixz=fizxifiz iN,φN+1xz=rNfrxrNfrz,E7

where z=z1zN,ziXiiN,zX,xX. The Germeier convolution ([13], p. 43) of the scalar functions (7) has the form

φxz=maxj=1,,N+1φjxz.E8

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

XZ=Xφxz.E9

In this game, player 1 and his opponent choose their strategies xXand zXto maximize and minimize, respectively, the payoff function φxzdescribed by (7) and (8).

A saddle point xozX2of game (9) is defined by the chain of inequalities

φxzφx0zφx0zx,zX.E10

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

minzXmaxxXφxz=maxxXφxz

and the maximin strategy x0

maxxXminzXφxz=minzXφx0z.

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

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

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

φx0x0=maxj=1,,N+1φjx0x0=0.

By (10), for all xXit follows that

0φxz=maxj=1,,N+1φjxz=0.

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

0maxj=1,,N+1φjxzφjxz 
φjxz0 j=1NN+1 7
7fjzxifjz0 xiXiiN
rNfrxrNfrz0 xXe
maxxiXifjzxi=fjz iN
maxxXeiNfix=iNfiz2,6zXezXP.

This chain involves the inclusion XeX.

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

Step 1. Using the payoff functions fixiNfrom (1) and the vectors z=z1zN,ziXiand x=x1xN,xiXiiN,construct the functionφxzby formulas (7) and (8).

Step 2. Find the saddle point xozof antagonistic game (9). Then zis the Pareto equilibrium solution of game (1).

As far as the authors know, numerical calculation methods of the saddle pointxozfor the Germeier convolution

φxz=maxj=1,,N+1φjxz

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 maxjφjxproposed 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 XicompRniand fiCXiNin game (1), then the Germeier convolution φxz=maxj=1,,N+1φjxzfrom (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 Xiof the pure strategies xiare compact sets in Rni(are closed and bounded), whereas the payoff function fixof each player i iNis continuous on the set of pure strategy profiles X.

Consider the mixed strategy extension of game (1). To this end, construct the Borel σ-algebra BXion each compact set XiiNand probability measures νion BXi(i.e., nonnegative scalar functions defined on the elements of BXithat are countably additive and normalized to unity on Xi). Denote by νithe whole set of such measures; the measure νiproper is called the mixed strategy of player i iNin game (1). Next, for game (1) construct the mixed strategy profiles, that is, the multiplicative measures

νdx=ν1dx1νNdxN,

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

fiν=Xfixνdx iN.E11

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

Γ˜=NνiiNfiνiN.

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

νiνias the mixed strategy of player i.

ννas the mixed strategy profile.

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

Further exposition involves the vector z=z1zNXwith ziXiiN,and, of course, the vector x=x1xNX,as well as the mixed strategy profiles ν,μνand the mathematical expectations

fiν=Xfixνdx,fiμ=Xfizμdz,fiμνi=X1Xi1XiXi+1XNfixμNdzNμi+1dzi+1νidxiμi1dzi1μ1dz1.E12

Once again, we underline that xi,ziXiiNand x,zX.

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 xeXin pure strategies in the same game (1).

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

fiνeνifiνe νiνi iN;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 XicompRniand fiCXiN. Denote by Nthe set of such profiles νe.

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

Γ˜υ=NfiνiN.E14

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

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

fiνfiνP iN

is infeasible, with at least one inequality being strict.

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

iNfiνiNfiνP,E15

then the mixed strategy profile νPNis 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 Xiof each player i is a nonempty compact set in RniiN.

  2. The payoff function fixof player i iNis 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

φxz=maxj=1,,N+1φjxz,

where

φixz=fizxifiziN,φN+1xz=rNfrxrNfrz,

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

Define the auxiliary antagonistic game

Γa=IIIXZ=Xφxz,

where players I and II seek to maximize and minimize, respectively, the function φxzcontinuous on X×ZZ=Xby choosing their strategies xXand zX.

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=IIIXZ=XfIxz=φxzfIIxz=φxz.

In this game, player I seeks to maximize fIxz=φxzby choosing his strategy xX,whereas player II tries to maximize fIIxz=φxzThe sets Xand X=Zin game Γ2are compact, while the payoff functions fIxzand fIIxzare continuous on X×Z;hence, by the Glicksberg theorem, there exists a Nash equilibrium strategy profile νeμin the mixed extension Γ2:

Γ˜2=IIIνμfiνμ=XXfixzνdxμdzi=I,II.

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

Γ˜a=IIIνμφνμ=XXφxzνdxμdz.

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

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

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

0φνμ=XXmaxj=1,,N+1φjxzνdxμdz.E17

It was established in [3] that

maxj=1,,N+1XXφjxzνdxμdzXXmaxj=1,,N+1φjxzν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

maxj=1,,N+1XXφjxzνdxμdz0 νν,

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

XXφjxzνdxμdz0 νν.E19

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

Xνidxi=1,Xμidzi=1iN,Xνdx=1,Xμdz=1E20

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

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

XXfizxifizνdxμdz=XXifizxifizνidxiμdz==XXfizxiνidxiμdzXfizμdzXiνidxi=12,20=12,20X1Xi1XiXi+1XNfiz1zi1xizi+1zNμNdzNμi+1dzi+1νidxiμi1dzi1μ1dz1fiμ=
=fiμνifiμ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

XXφN+1xzνdxμdz =7XXiNfixνdxμdzXXiNfixνdxμdz=
=XiNfixνdxXμdzXiNfizμdzXνdx=20
=20iNXfixνdxiNXfizμdz=12iNfiνiNfiμ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 μNconclude 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.

© 2020 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Vladislav Zhukovskiy and Konstantin Kudryavtsev (November 26th 2020). Pareto Optimality and Equilibria in Noncooperative Games, Multicriteria Optimization - Pareto-Optimality and Threshold-Optimality, Nodari Vakhania and Frank Werner, IntechOpen, DOI: 10.5772/intechopen.88184. Available from:

chapter statistics

81total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Polynomial Algorithm for Constructing Pareto-Optimal Schedules for Problem 1∣rjLmax,Cmax

By Alexander A. Lazarev and Nikolay Pravdivets

Related Book

First chapter

Genetic Algorithm Optimization of an Energy Storage System Design and Fuzzy Logic Supervision for Battery Electric Vehicles

By Stefan Breban

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us