Department of Applied Mathematics & Physics, Kyoto University
Technical Report 2010-010 (May 07, 2010)
Semidefinite complementarity reformulation for robust Nash equilibrium problems with Euclidean uncertainty sets
by Ryoichi Nishimura, Shunsuke Hayashi and Masao Fukushima
Consider the N-person non-cooperative game in which each player's
cost function and the opponents' strategies are uncertain.
For such an incomplete information game, the new solution concept
called a robust Nash equilibrium has attracted much attention over
the past several years. The robust Nash equilibrium results
from each player's decision-making based on the robust optimization policy.
In this paper, we focus on the robust Nash equilibrium problem in which
each player's cost function is quadratic, and the uncertainty sets
for the opponents' strategies and the cost matrices are represented
by means of Euclidean and Frobenius norms, respectively.
Then, we show that the robust Nash equilibrium problem can be
reformulated as a semidefinite complementarity problem (SDCP),
by utilizing the semidefinite programming (SDP) reformulation
technique in robust optimization. We also give some numerical
example to illustrate the behavior of robust Nash equilibria.