A global Newton method to compute Nash equilibria

被引：102

作者：

Govindan, S

Wilson, R ^{[1
]}

机构：

[1] Stanford Univ, Sch Business, Stanford, CA 94305 USA

[2] Univ Western Ontario, Dept Econ, London, ON N6A 5C2, Canada

来源：

JOURNAL OF ECONOMIC THEORY | 2003年 / 110卷 / 01期

基金：

美国国家科学基金会;

关键词：

noncooperative game; Nash equilibrium; algorithm; global Newton method; homotopy;

D O I：

10.1016/S0022-0531(03)00005-X

中图分类号：

F [经济];

学科分类号：

02 ;

摘要：

A new algorithm is presented for computing Nash equilibria of finite games. Using Kohlberg and Mertens' structure theorem we show that a homotopy method can be represented as a dynamical system and implemented by Smale's global Newton method. The algorithm is outlined and computational experience is reported. (C) 2003 Elsevier Science (USA). All rights reserved.

引用

页码：65 / 86

页数：22

共 34 条

[21] BIMATRIX EQUILIBRIUM POINTS AND MATHEMATICAL-PROGRAMMING
LEMKE, CE
[J]. MANAGEMENT SCIENCE, 1965, 11 (07) : 681 - 689
[22] LEMKE CE, 1964, SIAM J APPL MATH, V12, P413
[23] STABLE EQUILIBRIA - A REFORMULATION .1. DEFINITION AND BASIC PROPERTIES
MERTENS, JF
[J]. MATHEMATICS OF OPERATIONS RESEARCH, 1989, 14 (04) : 575 - 625
[24] GENERALIZATION OF LEMKE-HOWSON ALGORITHM TO NONCOOPERATIVE N-PERSON GAMES
ROSENMULLER, J
[J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1971, 21 (01) : 73 - +
[25] SHAPLEY LS, 1974, MATH PROGRAMMING STU, V1, P175, DOI DOI 10.1007/BFB0121248
[26] Smale S., 1976, J Math Econ, V3, P107, DOI [DOI 10.1016/0304-4068(76)90019-7, 10.1016/0304-4068(76)90019-7]
[27] TOMLIN JA, 1978, MATH PROGRAM STUD, V7, P55
[28] von Stengel B., 2002, HDB GAME THEORY, P1723
[29] VONSTENGEL B, 1997, 264 EIDG TH I THEOR
[30] COMPUTING EQUILIBRIA OF N-PERSON GAMES
WILSON, R
[J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1971, 21 (01) : 80 - &

← 1 2 3 4 →