检索结果-内蒙古大学图书馆

TROPICAL COMPLEMENTARITY PROBLEMS AND NASH EQUILIBRIA

SIAM JOURNAL ON DISCRETE MATHEMATICS 2023年第3期37卷 1645-1665页

作者： Allamigeon, Xavier Gaubert, Stephane Meunier, Frederic Inst Polytech Paris INRIA Paris France Inst Polytech Paris CNRS Ecole Polytech CMAP Paris France Ecole Ponts CERMICS Paris France

Linear complementarity programming is a generalization of linear programming which encompasses the computation of Nash equilibria for bimatrix games. While the latter problem is PPAD-complete, we show that the tropical analogue of the complementarity problem associated with Nash equilibria can be solved in polynomial time. Moreover, we prove that the lemke-howson algorithm carries over the tropical setting and performs a linear number of pivots in the worst case. A consequence of this result is a new class of (classical) bimatrix games for which Nash equilibria computation can be done in polynomial time.

关键词： Nash equilibria bimatrix games linear complementarity problems lemke-howson algorithm tropical geometry

来源：评论

学校读者我要写书评

暂无评论

Unit vector games

引用

INTERNATIONAL JOURNAL OF ECONOMIC THEORY 2016年第1期12卷 7-27页

作者： Savani, Rahul von Stengel, Bernhard Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England London Sch Econ Dept Math London England

McLennan and Tourky showed that imitation games provide a new view of the computation of Nash equilibria of bimatrix games with the lemke-howson algorithm. In an imitation game, the payoff matrix of one of the players is the identity matrix. We study the more general unit vector games, which are already known, where the payoff matrix of one player is composed of unit vectors. Our main application is a simplification of the construction by Savani and von Stengel of bimatrix games where two basic equilibrium-finding algorithms take exponentially many steps: the lemke-howson algorithm, and support enumeration.

关键词： bimatrix game Nash equilibrium computation imitation game lemke-howson algorithm unit vector game

来源：评论

学校读者我要写书评

暂无评论

The Complexity of the Homotopy Method, Equilibrium Selection, and lemke-howson Solutions

引用

ACM Transactions on Economics and Computation 2013年第2期1卷 1–25页

作者： Paul W. Goldberg Christos H. Papadimitriou Rahul Savani University of Liverpool University of California at Berkeley

We show that the widely used homotopy method for solving fixpoint problems, as well as the Harsanyi-Selten equilibrium selection process for games, are PSPACE-complete to implement. Extending our result for the Harsanyi-Selten process, we show that several other homotopy-based algorithms for finding equilibria of games are also PSPACE-complete to implement. A further application of our techniques yields the result that it is PSPACE-complete to compute any of the equilibria that could be found via the classical lemke-howson algorithm, a complexity-theoretic strengthening of the result in Savani and von Stengel [2006]. These results show that our techniques can be widely applied and suggest that the PSPACE-completeness of implementing homotopy methods is a general principle.

关键词： Fixpoint problems lemke-howson algorithm equilibria game theory homotopy methods

来源：评论

学校读者我要写书评

暂无评论

Smoothed analysis in Nash equilibria and the Price of Anarchy

Smoothed analysis in Nash equilibria and the Price of Anarch...

引用

作者： Rodrigues, Félix Carvalho

This thesis analyzes problems in game theory with respect to perturbation. It uses smoothed analysis to accomplish such task and focuses on two kind of games, bimatrix games and the traffic assignment problem. The lemke-howson algorithm is a widely used algorithm to compute a Nash equilibrium of a bimatrix game. This problem is PPAD-complete (Polynomial Parity Arguments on Directed graphs), and there exists an instance which takes exponential time (with any starting pivot.) It has been proven that even with a smoothed analysis it is still exponential. However, no experimental study has been done to verify and evaluate in practice how the algorithm behaves in such cases. This thesis shows in detail how the current known worst-case instances are generated and shows that the performance of the algorithm on these instances, when perturbed, differs from the expected behavior proven in theory. The Traffic Assignment Problem models a situation in a road network where users want to travel from an origin to a destination. It can be modeled as a game using game theory, with a Nash equilibrium happening when users behave selfishly and an optimal social welfare being the best possible flow from a global perspective. We provide a new measure, which we call the Smoothed Price of Anarchy, based on the smoothed analysis of algorithms in order to analyze the effects of perturbation on the Price of Anarchy. Using this measure, we analyze the effects that perturbation has on the Price of Anarchy for real and theoretical instances for the Traffic Assignment Problem. We demonstrate that the Smoothed Price of Anarchy remains in the same order as the original Price of Anarchy for polynomial latency functions. Finally, we study benchmark instances in relation to perturbation. ...

关键词： Inteligência artificial algorithmic game theory Smoothed analysis Algoritmos lemke-howson algorithm Teoria : Jogos Bimatrix games Frank-Wolfe algorithm Network games Traffic assignment problem Price of anarchy Dissertação

来源：评论

学校读者我要写书评

暂无评论

Imitation games and computation

引用

GAMES AND ECONOMIC BEHAVIOR 2010年第1期70卷 4-11页

作者： McLennan, Andrew Tourky, Rabee Univ Queensland Sch Econ St Lucia Qld 4072 Australia

An imitation game is a finite two person normal form game in which the two players have the same set of pure strategies and the goal of the second player is to choose the same pure strategy as the first player. We explain how, in two different settings, observations obtained from imitation games complete a circle of ideas, showing that phenomena that had for many years seemed to be distinct are actually superficially different manifestations of a single structure. First, one can pass from a given two person finite game to an imitation game whose Nash equilibria are in one-to-one correspondence with the Nash equilibria of the given game. Second, each of the paths of the procedure described in lemke (1965) for solving a linear complementarity problem is the projection of the path of the lemke-howson algorithm applied to an imitation game. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Computational economics Symmetric games Nash equilibrium Computational complexity Two person games 2-Nash Imitation games lemke-howson algorithm lemke paths

来源：评论

学校读者我要写书评

暂无评论

Sperner Oiks

引用

Electronic Notes in Discrete Mathematics 2010年第C期36卷 1273-1280页

作者： Edmonds, Jack Gaubert, Stéphane Gurvich, Vladimir INRIA and École Polytechnique France RUTCOR Rutgers University Piscataway NJ 08854 640 Bartholomew Road United States

The idea of "lemke pivoting in a family of oiks (Euler complexes)" generalizes, and abstracts to pure combinatorics, the lemke-howson exchange algorithm for finding a Nash equilibrium in bimatrix games, as well as the classical algorithm for finding the properly colored room in Sperner's Lemma. Given a "room-partitioning", this algorithm finds another (distinct) room-partitioning by traversing the exchange graph. In this paper we show that each family of k oiks O={O1, ... ,Ok} can be reduced to a pair of oiks O'={O1+ ... +Ok,O0} (one of which, O0, is a Sperner oik) such that the exchange graphs for O and O' are isomorphic. Numerous applications of Sperner's Lemma in combinatorial topology are well known. © 2010 Elsevier B.V.

关键词： Brouwer Theorem Euler complex (oik) Exchange algorithm KKM-Theorem lemke-howson algorithm Manifold Pivot Room Sperner Lemma Wall

来源：评论

学校读者我要写书评

暂无评论

Euler Complexes (Oiks)

引用

Electronic Notes in Discrete Mathematics 2010年第C期36卷 1289-1293页

作者： Edmonds, Jack Canada and Paris

We present a class of instances of the existence of a second object of a specified type, in fact, of an even number of objects of a specified type, which generalizes the existence of an equilibrium for bimatrix games. The proof is an abstract generalization of the lemke-howson algorithm for finding an equilibrium of a bimatrix *** of this note, with various examples, were presented at a Dagstuhl conference in 2007, the Dubrovnik ECCO XXI conference in 2008, the Paris TGGT conference in 2008, and the Bonn conference, "Recent trends in Combinatorial Optimization", proceedings: Springer, 2009. The version here is meant to be updated convenience for the session on Oiks, ISCO, 2010. © 2010.

关键词： 05C85 68R10 68W40 91A05 Binary matroid Euler binary matroid Euler complex Euler graph Exchange algorithm lemke-howson algorithm Matching algorithm Matroid partition algorithm Nash equilibrium Room family Room partition Simplicial pseudo-manifold

来源：评论

学校读者我要写书评

暂无评论

Settling the Complexity of Computing Two-Player Nash Equilibria

引用

JOURNAL OF THE ACM 2009年第3期56卷 14:1-14:57页

作者： Chen, Xi Deng, Xiaotie Teng, Shang-Hua Princeton Univ Dept Comp Sci Princeton NJ 08540 USA City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Boston Univ Dept Comp Sci Boston MA 02215 USA Akamai Technol Inc Cambridge MA USA

We prove that BIMATRIX, the problem of finding a Nash equilibrium in a two-player game, is complete for the complexity class PPAD (Polynomial Parity Argument, Directed version) introduced by Papadimitriou in 1991. Our result, building upon the work of Daskalakis et al. [2006a] on the complexity of four-player Nash equilibria, settles a long standing open problem in algorithmic game theory. It also serves as a starting point for a series of results concerning the complexity of two-player Nash equilibria. In particular, we prove the following theorems: - BIMATRIX does not have a fully polynomial-time approximation scheme unless every problem in PPAD is solvable in polynomial time. - The smoothed complexity of the classic lemke-howson algorithm and, in fact, of any algorithm for BIMATRIX is not polynomial unless every problem in PPAD is solvable in randomized polynomial time. Our results also have a complexity implication in mathematical economics: - Arrow-Debreu market equilibria are PPAD-hard to compute.

关键词： algorithms Economics Theory Two-player game Nash equilibrium Brouwer's fixed point PPAD-completeness smoothed analysis lemke-howson algorithm Sperner's lemma Arrow-Debreu market

来源：评论

学校读者我要写书评

暂无评论

Games in oriented matroids

引用

JOURNAL OF MATHEMATICAL ECONOMICS 2008年第7-8期44卷 807-821页

作者： McLennan, Andrew Tourky, Rabee Univ Queensland Sch Econ Brisbane Qld 4010 Australia

We introduce a combinatorial abstraction of two person finite games in an oriented matroid. We also define a combinatorial version of Nash equilibrium and prove that an odd number of equilibria exists. The proof is a ... 详细信息

关键词： two person games oriented matroids lemke-howson algorithm

来源：评论

学校读者我要写书评

暂无评论

Hard-to-solve bimatrix games

引用

ECONOMETRICA 2006年第2期74卷 397-429页

作者： Savani, R von Stengel, B Univ London London Sch Econ & Polit Sci Dept Math London WC2A 2AE England

The lemke-howson algorithm is the classical method for finding one Nash equilibrium of a bimatrix game. This paper presents a class of square bimatrix games for which this algorithm takes, even in the best case, an exponential number of steps in the dimension d of the game. Using polytope theory, the games are constructed using pairs of dual cyclic polytopes with 2d suitably labeled facets in d-space. The construction is extended to nonsquare games where, in addition to exponentially long lemke-howson computations, finding an equilibrium by support enumeration takes on average exponential time.

关键词： bimatrix game computational complexity lemke-howson algorithm Nash equilibrium support enumeration

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：