An Alternating Direction Method for Nash Equilibrium of Two-Person Games with Alternating Offers
- PDF / 631,922 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 80 Downloads / 210 Views
An Alternating Direction Method for Nash Equilibrium of Two-Person Games with Alternating Offers Zheng Peng · Wenxing Zhu
Received: 14 July 2011 / Accepted: 23 August 2012 / Published online: 6 September 2012 © Springer Science+Business Media, LLC 2012
Abstract In this paper, we propose a method for finding a Nash equilibrium of twoperson games with alternating offers. The proposed method is referred to as the inexact proximal alternating direction method. In this method, the idea of alternating direction method simulates alternating offers in the game, while the inexact solutions of subproblems can be matched to the assumptions of incomplete information and bounded individual rationality in practice. The convergence of the proposed method is proved under some suitable conditions. Numerical tests show that the proposed method is competitive to the state-of-the-art algorithms. Keywords Computational game theory · Nash equilibrium · Inexact proximal point method · Alternating direction method 1 Introduction The analysis of economic behavior and noncooperative games are a modeling tool having the Nash equilibrium as the central solution concept. However, the equilibrium has to be found at first, which often takes a substantial amount of the analysis. To find a Nash equilibrium, one can convert the equilibrium problem to a suitable optimization problem and then design a computer program to solve the resulting optimization problem. Communicated by Liqun Qi. Z. Peng () College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China e-mail: [email protected] W. Zhu Center of Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fuzhou 350108, China e-mail: [email protected]
534
J Optim Theory Appl (2013) 157:533–551
Two-person games are the foundations for describing the basic concepts and properties of game theory and for analyzing the algorithm used to compute a Nash equilibrium. Almost all classical courses of game theory have mentioned some theory on two-person games, e.g., the Prisoner’s Dilemma and classical bargaining games (with two players): for examples, see [1, 2]. Researches on algorithms for finding a Nash equilibrium of a two-person game can be dated back to the 1960s. Two comprehensive survey papers were presented by Mckelvey [3] and Stengel [4]. Recently, Antipin [5] proposed an extra-proximal method for the solution of the two-person nonzerosum game problem and proved its convergence. Orbay [6] presented a characterization of internal Cournot equilibrium basing on the first-order conditions corresponding to profit maximization over prices. This characterization may yield significant computational advantage, since demand functions need not to be inverted and simple first-order conditions are obtained. Yuan [7] considered the application of trust-region methods to Nash equilibrium problems. The proposed method includes different trust regions for each player, and the trial step is computed and accepted (or rejected) based on each individual utility function. Unde
Data Loading...
