=Paper=
{{Paper
|id=Vol-2098/paper25
|storemode=property
|title=Search of Nash Equilibrium in Quadratic
Nonconvex Game with Weighted Potential
|pdfUrl=https://ceur-ws.org/Vol-2098/paper25.pdf
|volume=Vol-2098
|authors=Ilya Minarchenko
}}
==Search of Nash Equilibrium in Quadratic
Nonconvex Game with Weighted Potential==
https://ceur-ws.org/Vol-2098/paper25.pdf
Search of Nash Equilibrium in Quadratic
Nonconvex Game with Weighted Potential?
Ilya Minarchenko
Melentiev Energy Systems Institute
of Siberian Branch of the Russian Academy of Sciences,
130 Lermontov Str., 664033, Irkutsk, Russia
eq.progr@gmail.com
Abstract. We consider an n-player nonconvex continuous game with
quadratic payoffs, multi-dimensional strategy spaces, and possibly shared
constraints on strategies, and investigate conditions when this game ad-
mits a weighted potential. Since a potential is generally nonconvex in this
case, we propose local and global search procedures for maximizing it over
the set of admissible game profiles. The local search uses nonlinear sup-
port functions that are constructed through a d.c.-decomposition of the
potential. The global search is based on reducing of a certain nonconvex
quadratic programming problem to a mixed-integer linear programming
problem.
Keywords: Nash equilibrium · Weighted potential · Nonconvex opti-
mization · D.C decomposition
1 Introduction
One of the main features of potential games in the sense of computing Nash
equilibria is a possibility of reducing the game to an optimization problem. More
exactly, in a potential game the set of maxima of a certain function is a subset
of the set of Nash equilibria. This function is called potential. Generally a po-
tential is a nonconvex function. In this case the set of local non-global maxima
may contain equilibrium points as well. For the games with differentiable pay-
offs, even a stationary point could be suspected to be an equilibrium. Thus two
crucially important questions arise in practice: how to determine the existence
of a potential, and how to specify this function. Both of these issues are solved
for the differentiable case of exact potential games with scalar strategies [15].
Weighted potential games generalize exact potential games by introducing a
positive weight for every player. The class of weighted potential games turns out
to have properties, which are very similar to those of exact potential games.
?
This research was supported by RFBR grant 18-07-01432.
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org
292 I. Minarchenko
The class of exact potential games was introduced in [15], along with weighted,
ordinal, and generalized ordinal potential games. Later even more general classes
were investigated, such as best-response potential games [19], and pseudo-potential
games [4]. A common property of all these classes stays the same: they admit
an optimization problem statement that noticeably makes easier an analysis of
the game. A survey on different classes of potential games, on relations between
them, as well as examples of applications one can find in [12, 7, 13] (see also
the references therein). In this study we are interested in continuous games,
i.e. games with continuous sets of strategies. For games with twice continuously
differentiable payoffs and interval strategy sets, a useful characteristic for iden-
tifying the existence of a potential was established [15]. Such a characteristic
can be easily extended for weighted potential games with interval strategy sets.
For ordinal and generalized ordinal potential games with the payoffs of the same
class and with multi-dimensional strategies, necessary conditions were formu-
lated in [5].
For the cases in which either a game is non-potential or an identification
whether a potential exists is complicated, there are methods of variety of types
that do not exploit potential optimization for computing Nash equilibria. For
instance, the methods among them are gradient-type algorithms [17, 21, 1], re-
laxation algorithms [20, 8], Newton-type method [9, 3], nonlinear support func-
tion method [10, 14], KKT-conditions-based method [2], and many others. It is
worth to note that convexity-type assumptions usually play significant role for
the convergence properties of equilibrium computation algorithms. The standard
assumption widely used is player-concavity of payoffs, i.e. every player’s payoff
function must be concave with respect to this player’s strategic variable. Games
with this assumption being violated we call nonconvex games, in contrast to
convex games [16]. Also there exists a rather general approach to reducing an
equilibrium problem to a global optimization problem [10] using the so-called
Nikaido-Isoda function [16]. It is noticable that this approach in general does not
employ any of convexity presumptions. The underlying method in [10] is based
on the concept of nonlinear support function. Later such a technique was applied
to quadratic nonconvex non-potential games [14]. As we see further, existence of
a weighted potential can also be guaranteed without convexity-type conditions
on payoffs.
The present paper focuses on n-player nonconvex games with quadratic pay-
offs and convex compact set of game profiles. A strategy of every player is as-
sumed to be a multi-dimensional value. We admit that the strategy set of every
player depends on chosen strategies of rival players through shared constraints.
These constraints restrain the set of admissible profiles. Recall, the problem of
finding Nash equilibrium in non-cooperative game with coupled strategy sets is
called generalized Nash equilibrium problem (GNEP). In contrast, if the strat-
egy sets are independent, the problem is referred to as Nash equilibrium prob-
lem (NEP); see [17] for details. We discuss a differentiable characterization of
weighted potential games with vector strategies, and provide explicit expression
of potential function. Then we formulate these results specifically for quadratic
Nash Equilibrium in Quadratic Weighted Potential Game 293
games. The potential turns out to be nonconvex in this statement. Hence we
propose a local search and a global search methods for maximizing a potential
function over the set of game profiles.
2 Weighted Potential Games
Consider a non-cooperative n-person game. The set of players is N = {1, 2, . . . , n},
a strategy of ith player represents mi -dimensional vector, so as the set of ad-
missible game profiles is X ⊂ Rm , where m = m1 + · · · + mn , and R denotes
the set of real numbers. Payoff function of ith player is fi : X → R. We suppose
that X is a convex compact set, and fi is twice continuously differentiable for
every i ∈ N . The problem is to find generalized Nash equilibrium (or, shortly,
Nash equilibrium) for the given game, i.e. to find a profile x∗ ∈ X meeting the
following conditions:
fi (xi , x∗−i ) 6 fi (x∗ ) ∀xi : (xi , x∗−i ) ∈ X , ∀i ∈ N , (1)
where (xi , x∗−i ) = (x∗1 , . . . , x∗i−1 , xi , x∗i+1 , . . . , x∗n ). Let us denote the game by
Γ = hN, X, {fi }i∈N i.
Recall that the game Γ is called a weighted potential game if positive weights
w1 , . . . , wn and weighted potential function P : X → R exist such that for all
i ∈ N and for all yi , zi , x−i : (yi , x−i ) ∈ X, (zi , x−i ) ∈ X the following relation
holds [15]:
fi (yi , x−i ) − fi (zi , x−i ) = wi (P (yi , x−i ) − P (zi , x−i )) . (2)
If w1 = w2 = · · · = wn , then Γ is called an exact potential game and P is
called an exact potential. In order to specify certain values of weights in (2)
we will say that the game is w-potential game, and P is w-potential, where
w = (w1 , . . . , wn ). The next useful results are well known for differentiable games
with scalar strategies. Let m1 = m2 = · · · = mn = 1. If payoffs are continuously
differentiable on X, then condition (2) can be replaced by
∂fi (x) ∂P (x)
= wi . (3)
∂xi ∂xi
Moreover, if payoffs are twice continuously differentiable then Γ is a weighted
potential game if and only if positive numbers v1 , . . . , vn exist such that for all
i ∈ N , j ∈ N (i 6= j), x ∈ X:
∂ 2 fi (x) ∂ 2 fj (x)
vi = vj , (4)
∂xi ∂xj ∂xj ∂xi
If Γ is a weighted potential game, then a weighted potential function is expressed
by Z 1X
∂fi (tx)
P (x) = vi xi dt . (5)
0 ∂xi
i∈N
294 I. Minarchenko
More exactly, due to definition (2) the game Γ is (1/v1 , . . . , 1/vn )-potential in
the latter case. Relation (3) at w1 = w2 = · · · = wn = 1, and relations (4), (5)
at v1 = v2 = · · · = vn = 1 (for exact potential games) were provided in [15].
Extension of these results for weighted potential games with scalar strategies
follows in a straightforward way.
In order to generalize the differentiable characterization (3–5) for multi-
dimensional strategy spaces, let us introduce a game Γ 0 by replacing ith player
in Γ by mi players, each of them maximizing the same function fi with respect
to one of scalar variables from mi -dimensional strategy of the ith player of Γ .
Then the set of players in Γ 0 is N 0 = {1, . . . , m1 , m1 + 1, . . . , m1 + m2 , . . . , m}.
The first m1 players try to maximize independently f1 as their payoff, whereas
the next m2 players treat f2 as a payoff, etc. The profile set in Γ 0 is X, and
every player of Γ 0 operates one scalar variable.
Recall a definition from potential game theory useful for the present study.
A path in X [15] with respect to Γ is a sequence of game profiles (p1 , p2 , . . . )
such that pk ∈ X, k = 1, 2, . . . , and for every k > 1 there exists a unique
deviating player of Γ , say ith player, such that pk = (xi , pk−i ) for some xi 6= pk−1 i ,
(i)
(xi , pk−i ) ∈ X. In the further discussion xk denotes the kth component of vector
strategy xi . Besides, w0 ∈ Rm is a vector of weights, where w1 = w10 = w20 =
0 0 0 0
· · · = wm 1
, w2 = wm 1 +1
= wm 1 +2
= · · · = wm 1 +m2
, etc.
The next result holds without continuity assumption on payoffs.
Theorem 1. Let there exist a path (p1 , p2 , . . . , pK ) in X with respect to Γ 0 con-
necting the profiles p1 = (yi , x−i ) and pK = (zi , x−i ) for every yi , zi , x−i such
that p1 ∈ X, pK ∈ X, and for every i ∈ N . Then the game Γ is a w-potential
game if and only if the game Γ 0 is a w0 -potential. If Γ and Γ 0 are a w-potential
and a w0 -potential games respectively, their weighted potentials coincide up to
constant.
Proof. If Γ is a w-potential game then (2) holds for some function P : X → R.
(i) (i)
For every i ∈ N and for every k ∈ {1, 2, . . . , mi } fix arbitrarily y−k = z−k =
(i) (i) (i) (i)
x−k such that there exists a scalar value ak : (ak , x−k , x−i ) ∈ X. Then the
condition (2) yields
(i) (i) (i) (i)
fi yk , x−k , x−i − fi zk , x−k , x−i =
(i) (i) (i) (i)
wi P yk , x−k , x−i − P zk , x−k , x−i .
The latter relation provides that Γ 0 is a w0 -potential game with potential P .
Conversely, let Γ 0 be a w0 -potential game. For every i ∈ N choose arbitrary
vectors yi , zi , x−i such that (yi , x−i ) ∈ X and (zi , x−i ) ∈ X. Define a finite path
(p1 , p2 , . . . , pK ) in X with respect to Γ 0 connecting the profiles p1 = (yi , x−i )
and pK = (zi , x−i ), where the unique deviators are the mi players of Γ 0 with fi
as their payoff. In other words, pk = (pki , x−i ), k = 2, 3, . . . , K − 1. Then due
Nash Equilibrium in Quadratic Weighted Potential Game 295
to (2) the following relations take place:
fi (yi , x−i ) − f (p2 ) = wi P (yi , x−i ) − P (p2 ) ,
fi (p2 ) − f (p3 ) = wi P (p2 ) − P (p3 ) ,
...
K−2 K−1
) = wi P (pK−2 ) − P (pK−1 ) ,
fi (p ) − f (p
fi (pK−1 ) − f (zi , x−i ) = wi P (pK−1 ) − P (zi , x−i ) .
Summing up these equalities we at once obtain that Γ is a w-potential game
with P as a w-potential function. t
u
In particular, the assumption in Theorem 1 holds for games with independent
strategy sets (for NEP). If this assumption is violated let us define an open
convex neighborhood Ω of the set X, and suppose that payoffs and a potential
are defined on Ω. Replace in Γ and Γ 0 the profile set X by Ω. Denote the derived
games by ΓΩ and ΓΩ0 respectively. It is obvious that if ΓΩ is a weighted potential
game, then Γ is also a weighted potential game with the same potential function,
since X ⊂ Ω. Moreover, the assumption of Theorem 1 holds for a game with
the profile set Ω, as for every x ∈ Ω there exists a neighborhood B(x) such that
B(x) ⊂ Ω.
Corollary 1. If ΓΩ0 is a w0 -potential game then Γ is a w-potential game with
the same potential function as in ΓΩ0 .
In what follows, we suppose that the assumption of Theorem 1 holds.
With Theorem 1 relations (3) and (4) are easily extended for games with
vector strategies. Since payoffs in Γ are continuously differentiable, due to The-
orem 1 the condition (3) for multi-dimensional strategies can be replaced by the
following one:
∇xi fi (x) = wi ∇xi P (x) . (6)
Using the assumption that payoffs are twice continuously differentiable, Theo-
rem 1 and (4) imply that Γ is a weighted potential game if and only if positive
numbers v1 , . . . , vn exist such that for all i ∈ N , j ∈ N (i 6= j), k ∈ {1, . . . , mi },
and l ∈ {1, . . . , mj }, and for every feasible x:
∂ 2 fi (x) ∂ 2 fj (x)
vi (i) (j)
= v j (j) (i)
. (7)
∂xk ∂xl ∂xl ∂xk
Condition (7) is equivalent to
vi ∇2xi ,xj fi (x) = vj [∇2xi ,xj fj (x)]> .
If we define a multi-valued function
gv (x) = (v1 ∇x1 f1 (x), . . . , vn ∇xn fn (x)) ,
then relation (7) is also equivalent to that the Jacobian Gv (x) of gv (x) is sym-
metric for every feasible x.
296 I. Minarchenko
Proposition 1. If payoffs are twice continuously differentiable then the game
Γ is a weighted potential game if and only if positive numbers v1 , . . . , vn exists
such that the Jacobian Gv (x) of the function gv (x) is a symmetric matrix for
every x ∈ X.
Formula (5) of a potential function is also adopted for multi-dimensional strate-
gies through Theorem 1.
Proposition 2. If Γ is a (1/v1 , . . . , 1/vn )-potential game then a weighted po-
tential for Γ is given by
mi
Z 1XX
∂fi (tx) (i)
P (x) = vi (i)
xk dt . (8)
0 i∈N k=1 ∂xk
Note that existence of a continuous potential function implies existence of a Nash
equilibrium in the game if the profile set X is compact.
3 Quadratic Games
Let ith player’s payoff function in the game Γ be defined as
j6=i
1 X
fi (x) = x>
i Bi xi + di + x>
i Cij xj . (9)
2
j∈N
Without loss of generality matrices Bi are supposed to be symmetric. For pay-
offs (9) necessary and sufficient condition (7) for Γ to be a weighted potential
game is presented by the following one:
>
vi Cij = vj Cji (10)
for some positive v1 , . . . , vn and for every i ∈ N and j ∈ N (i 6= j). As player-
concavity of (9) is not used in the condition (10), weighted potential quadratic
games include nonconvex games. Moreover, even the term in payoff, which does
not depend on rival players variables, has no impact on the existence of a poten-
tial function. Indeed, the equality (10) plays the role of necessary and sufficient
condition also for the game with the following payoffs:
j6=i
X
fi (x) = fbi (xi ) + x>
i Cij xj , (11)
j∈N
where fbi generally is non-quadratic.
Proposition 3. The game Γ with payoffs (11) is a weighted potential game if
and only if positive numbers v1 , . . . , vn exist such that for every i ∈ N and j ∈ N
(i 6= j) condition (10) holds.
Nash Equilibrium in Quadratic Weighted Potential Game 297
For instance, consider a 2-player game with payoffs (11) and with scalar strate-
gies:
f1 (x) = fb1 (x1 ) + c1 x1 x2 ,
f2 (x) = fb2 (x2 ) + c2 x1 x2 .
Generally c1 6= c2 , therefore existence of an exact potential is not guaranteed.
However we can always choose positive numbers v1 , v2 such that v1 c1 = v2 c2
being true, if c1 and c2 are nonzero and have the same sign:
c1 c2 > 0 .
In particular, v1 = 1, v2 = c1 /c2 would be appropriate. For an n-player game
with multi-dimensional strategy sets, in order to ensure existence of a weighted
potential in accordance with Proposition 1 we should provide v > 0 such that
the Jacobian
v1 ∇2 fb1 (x1 ) v1 C1,2 . . .
v1 C1,n
v2 C2,1 v2 ∇2 fb2 (x2 ) . . . v2 C2,n
Gv (x) =
. . . . . . . . . . . . . . . . . . .
vn Cn,1 vn Cn,2 . . . vn ∇2 fbn (xn )
be symmetric.
If (10) holds, by Proposition 2 a (1/v1 , . . . , 1/vn )-potential for Γ with pay-
offs (9) is given by
j6=i
X
> 1 1X >
P (x) = vi x i Bi xi + di + xi Cij xj . (12)
2 2
i∈N j∈N
The validity of (12) one can examine directly through the verifying the equal-
ity (6).
Example 1 (quadratic payoffs [14]). Consider a 2-player nonconvex game with
quadratic payoffs and scalar strategies:
1
f1 (x) = x21 + x1 x2 , f2 (x) = −x22 + x1 x2 , X = [−1, 1] × [−1, 1] .
2
Obviously the game does not admit exact potential. However with v1 = 1, v2 = 2
in (12) (1, 1/2)-potential is
P (x) = x21 − 2x22 + x1 x2 .
There are two Nash equilibria in the game: x0 = (1, 1/4) and x00 = (−1, −1/4).
Both of them provide maximal value to P on X. The vector field (∂f1 (x)/∂x1 ,
∂f2 (x)/∂x2 ) and the plot of the weighted potential are presented at Fig. 1. Due
to (6) the vector field coincides with (∂P (x)/∂x1 , ∂P (x)/∂x2 ).
298 I. Minarchenko
1
0.5
x2 0 0
−0.5 1
−2
0
−1 −0.5
−1 0 x2
−1 −0.5 0 0.5 1 0.5 1 −1
x1 x1
Fig. 1. Vector field (∂f1 (x)/∂x1 , ∂f2 (x)/∂x2 ) (left) and plot of the weighted potential
(right) in Example 1
To illustrate Proposition 3 consider an example with non-quadratic payoffs.
Example 2 (qubic payoffs). Define a 2-player game with payoffs (11), where
fb1 (x1 ) and fb2 (x2 ) are qubic polynoms:
f1 (x) = x31 + 5x21 − 10x1 + 10x1 x2 ,
f2 (x) = x32 − 7x22 + 13x2 + 15x1 x2 ,
X = [−10, 5] × [−10, 5] .
As in the previous example, the given game is not an exact potential. Setting
v1 = 1, v2 = 2/3 at (8) we obtain (1, 3/2)-potential function:
2 14 26
P (x) = x31 + 5x21 − 10x1 + x32 − x22 + x2 + 10x1 x2 .
3 3 3
Potential P attains its maximum on X at x0 = (5, 5), P (x0 ) ≈ 460. Besides
local non-global maximum exists: x00 ≈ (−5.73, −3.12), P (x00 ) ≈ 119.39. One
can easily verify by (1) that x00 is also a Nash equilibrium in the game. The
vector field (∂f1 (x)/∂x1 , ∂f2 (x)/∂x2 ) = (∂P (x)/∂x1 , ∂P (x)/∂x2 ) and the plot
of the weighted potential are depicted at Fig. 2.
The next example shows that locally non-optimal stationary point of a potential
may be a Nash equilibrium.
Example 3. Consider an exact potential game with X ⊆ R2 such that (0, 0) is
an interior point of X, and payoffs are defined as follows:
f1 (x) = x2 x31 − x21 + x32 x1 + 3x1 x2 ,
f2 (x) = x1 x32 − x22 + x31 x2 + 3x1 x2 .
A potential is given by
P (x) = x31 x2 − x21 + 3x1 x2 + x1 x32 − x22 .
Nash Equilibrium in Quadratic Weighted Potential Game 299
5
0
0
x2
−5
−1,000
5
0
−10 −10 −5 −5
−10 −8 −6 −4 −2 0 2 4 0 5 −10
x2
x1 x1
Fig. 2. Vector field (∂f1 (x)/∂x1 , ∂f2 (x)/∂x2 ) (left) and plot of the weighted potential
(right) in Example 2
The profile x0 = (0, 0) is an equilibrium since f1 (x1 , 0) = −x21 and f2 (0, x2 ) =
−x22 . Besides ∇P (x0 ) = 0. However P increases along directions d1 = (−1, −1)
and d2 = (1, 1) from x0 . Indeed,
P (x0 + td1 ) = P (x0 + td2 ) = 2t4 + t2 > P (x0 ) for every t>0.
Hence x0 is not locally optimal.
Therefore we are interested in maximizing P (x) subject to x ∈ X, possibly
locally, or at least finding a stationary point of the potential over X. To this
end, a local search and a global search procedures will be examined further.
4 Local Search
As we discussed before, equilibria of a potential game should be searched among
stationary points of a potential function. Hence it is reasonable to use a local
ascending method in addition to a global search technique due to much less
computational costs of the former one.
For a weighted potential quadratic game with weights (1/v1 , . . . , 1/vn ) define
a vector dv = (v1 d1 , . . . , vn dn ) and the following matrices:
v1 B 1 0 . . . 0 0 v1 C1,2 . . . v1 C1,n
0 v2 B 2 . . . 0 v2 C2,1 0 . . . v2 C2,n
Bw = . . . . . . . . . . , Cw = . . . . . . . . . . . . ,
0 0 . . . vn Bn vn Cn,1 vn Cn,2 . . . 0
and Qv = Bv + Cv , where Qv is symmetric since the game is potential. Then
represent the potential (12) as follows:
1 >
P (x) = x Qv x + x> dv .
2
300 I. Minarchenko
Consider the general case when the matrix Qv is indefinite, and represent Qv as
follows:
Qv = D1 + D2 , D1 = Qv − αI , D2 = αI , (13)
where α > 0 is the largest eigenvalue of Qv . The matrix D1 is negative semidef-
inite, whereas the matrix D2 is positive definite. Using (13) we represent P as
the sum of concave and convex functions ϕ and ψ respectively:
1 > 1 >
P (x) = ϕ(x) + ψ(x) , ϕ(x) = x D1 x + x> dv , ψ(x) = x D2 x .
2 2
In other words, one can say that P is presented as a difference of two convex
functions. Such a representation is referred to as a d.c. decomposition. Define an
iterative local search process for the problem
P (x) → max, x∈X, (14)
as follows. Let an initial profile x0 ∈ X and the current iteration point xk ∈ X
be given. Then the next point xk+1 is obtained as a solution of a maximization
problem with concave objective:
xk+1 ∈ Arg max ρ(x, xk ) | x ∈ X ,
k = 0, 1, . . . , (15)
ρ(x, xk ) = ϕ(x) + ∇ψ(xk )> (x − xk ) + ψ(xk ) . (16)
The function ρ(x, xk ) may be considered as a nonlinear support minorant func-
tion for P , since
ρ(x, xk ) 6 P (x) ∀(x, xk ) ∈ X × X ,
ρ(xk , xk ) = P (xk ) ∀xk ∈ X .
An investigation on the algorithm (15), (16), including its convergence proper-
ties, one can find in [18]. It had been shown that the process (15), (16) converges
to a stationary point of the nonconcave optimization problem (14).
5 Global Search
It is possible to point out two cases when a using of a global search is essential.
The first one is a verification of a stationary point obtained by a local search
whether this point is an equilibrium. Such a verification consists of n nonconvex
programming problems that we need to solve in global sense (see (1)). In order
to obtain various stationary points it is supposed to start local ascending from
different, say randomly chosen, initial points (multistart). Secondly, we need
to use a global search method if after the verification of considerable number
of stationary points we failed to find an equilibrium. In this case we have to
solve globally initial problem of maximizing a potential. In both cases we face
a quadratic nonconvex programming problem with a convex feasible set. One of
Nash Equilibrium in Quadratic Weighted Potential Game 301
existing methods for solving such a problem consists in its reduction to a mixed-
integer linear programming problem [11]. In what follows we recall an approach
from [11].
To this moment, we have not yet specified the profile set X. From now we
assume that X is defined by linear constraints:
X = {x ∈ Rm | Ax 6 b} , (17)
where A ∈ Rs×m and b ∈ Rs . Write out the KKT conditions for (14), (17):
s
X
∇P (x) − λi ai = 0 , (18)
i=1
λi (x> ai − bi ) = 0 , 16i6s, (19)
Ax 6 b , λ>0, (20)
where
∇P (x) = Qv x + dv , (21)
i
and a denotes the ith row of the matrix A. The relation (21) implies
x> ∇P (x) = x> Qv x + x> dv = 2P (x) − x> dv . (22)
From (18), (19), and (22) we have
s
X s
X
x> ∇P (x) − λi x> ai = 2P (x) − x> dv − λi bi = 0 .
i=1 i=1
Hence every solution of the system (18)–(20) satisfies the equality
1 >
x dv + λ> b .
P (x) =
2
For convenience define auxiliary variables yi = bi − x> ai for 1 6 i 6 s. The
problem (14), (17) is equivalent to the following one:
x> dv + λ> b → max , (23)
(x,λ,y)
Qv x + dv − λ> A = 0 , (24)
λi yi = 0 , 16i6s, (25)
Ax + y = b , (26)
λ>0, y>0. (27)
With respect to the sensible assumptions [11] we can suppose that a constant M
exists such that λ < M and y < M . Let us introduce binary variables zi ,
1 6 i 6 s. Then complementarity slackness (25) can be replaced by the following
equivalent constraints:
λi − M zi 6 0 , yi − M (1 − zi ) 6 0 , 16i6s. (28)
302 I. Minarchenko
Thus we derive the mixed-integer linear programming (MILP) problem (23),
(24), (26)–(28) with binary variables. Although the original quadratic nonconvex
problem (14), (17) is rather difficult, we believe that the derived MILP one would
be more tractable due to highly developed MILP solvers (such as CPLEX, for
example).
If we want to verify a stationary point x of the problem (14), (17) whether
x is an equilibrium, we can maximize the payoffs (9) in accordance with the
definition (1) by the same way as it was just described. Note that in this case we
need to solve n nonconvex quadratic problems of dimensions m1 , m2 , . . . , mn ,
in contrast to one large problem (14), (17) of the dimension m. Hence it may be
reasonable first to search equilibria through the local ascending, since the large
dimension plays crucial role in global search procedures.
6 Conclusion
In this study we generalize the differentiable characterization for weighted poten-
tial games with multi-dimensional strategy spaces, and specify the correspond-
ing conditions for an n-player quadratic nonconvex game with continuous set of
game profiles. The set of profiles is defined by shared constraints. It is shown
that the fulfilment of these conditions does not depend on convexity-type as-
sumptions on payoffs. A weighted potential for the given game turns out to be
a nonconcave function. Since every global maximum of a potential is a Nash
equilibrium, and moreover even a stationary point may be an equilibrium, we
propose a local and a global search procedures for maximizing a potential func-
tion of quadratic weighted potential game. The local search process represents
the sequence of convex optimization problems, and it converges to a stationary
point of a potential. The global search is based on the reduction to an MILP
problem.
References
1. Antipin, A.S.: Gradient and Extragradient Approaches in Bilinear Equilibrium
Programming. Dorodnitsyn Computing Center RAS, Moscow (2002), (in Russian)
2. Dreves, A., Facchinei, F., Kanzow, C., Sagratella, S.: On the solution of the KKT
conditions of generalized Nash equilibrium problems. SIAM J. Optim. 21(3), 1082–
1108 (2011)
3. Dreves, A., von Heusinger, A., Kanzow, C., Fukushima, M.: A globalized Newton
method for the computation of normalized Nash equilibria. J. Glob. Optim. 56(2),
327–340 (2013)
4. Dubey, P., Haimanko, O., Zapechelnyuk, A.: Strategic complements and substi-
tutes, and potential games. Games Econ. Behav. 54(1), 77–94 (2006)
5. Ewerhart, C.: Ordinal potentials in smooth games. University of Zurich, Depart-
ment of Economics, Working Paper Series, Working Paper No. 265 (2017)
6. González-Sánchez, D., Hernández-Lerma, O.: A survey of static and dynamic po-
tential games. Sci. China Math. 59(11), 2075–2102 (2016)
Nash Equilibrium in Quadratic Weighted Potential Game 303
7. González-Sánchez, D., Hernández-Lerma, O.: A survey of static and dynamic po-
tential games. Sci. China Math. 59(11), 2075–2102 (2016)
8. von Heusinger, A., Kanzow, C.: Relaxation methods for generalized nash equi-
librium problems with inexact line search. J. Optim. Theory Appl. 143, 159–183
(2009)
9. von Heusinger, A., Kanzow, C., Fukushima, M.: Newton’s method for comput-
ing a normalized equilibrium in the generalized Nash game through fixed point
formulation. Math. Program. 132, 99–123 (2012)
10. Khamisov, O.: A global optimization approach to solving equilibrium programming
problems. In: Pardalos, P.M., Tseveendorj, I., Enkhbat, R. (eds.) Optimization and
Optimal Control. pp. 155–164. World Scientific (2003)
11. Khamisov, O.V.: Numerical Solution for Special Quadratic Nonconvex Program-
ming Problems. Discrete Analysis and Operations Research 12, 81–91 (2005), (in
Russian)
12. Lã, Q.D., Chew, Y.H., Soong, B.-H.: Potential Game Theory. Springer, Cham
(2016)
13. Mallozzi, L.: An application of optimization theory to the study of equilibria for
games: a survey. Cent. Eur. J. Oper. Res. 21(3), 523–539 (2013)
14. Minarchenko, I.: Search of Nash equilibrium in quadratic n-person game. In: Ko-
chetov, Y., Khachay, M., Beresnev, V., Nurminski, E., Pardalos, P. (eds.) Discrete
Optimization and Operations Research. DOOR 2016. LNCS, vol. 9869, pp. 509–
521. Springer, Cham (2016)
15. Monderer, D., Shapley, L.S.: Potential games. Games Econ. Behav. 14(1), 124–143
(1996)
16. Nikaido, H., Isoda, K.: Note on noncooperative convex games. Pac. J. Math. 5(5),
807-815 (1955)
17. Rosen, J.B.: Existence and uniqueness of equilibrium points for concave n-person
games. Econometrica 33(3), 520–534 (1965)
18. Strekalovsky, A.S.: On local search in D.C. optimization problems. Applied Math-
ematics and Computation 255, 73–83 (2015)
19. Voorneveld, M.: Best-response potential games. Econ. Lett. 66(3), 289–295 (2000)
20. Uryas’ev, S., Rubinstein, R.Y.: On Relaxation Algorithms in Computation of Non-
cooperative Equilibria. IEEE Trans. Autom. Control 39(6), 1263–1267 (1994)
21. Zukhovitskiy, S.I., Polyak, R.A., Primak, M.E.: Many-person convex games. Eco-
nomics and Math. Methods 7(6), 888–900 (1971), (in Russian)