On the Complexity of Pareto-Optimal Nash and Strong Equilibria

We consider the computational complexity of coalitional solution concepts in scenarios related to load balancing such as anonymous and congestion games. In congestion games, Pareto-optimal Nash and strong equilibria, which are resilient to coalitional deviations, have recently been shown to yield significantly smaller inefficiency. Unfortunately, we show that several problems regarding existence, recognition, and computation of these concepts are hard, even in seemingly special classes of games. In anonymous games with constant number of strategies, we can efficiently recognize a state as Pareto-optimal Nash or strong equilibrium, but deciding existence for a game remains hard. In the case of player-specific singleton congestion games, we show that recognition and computation of both concepts can be done efficiently. In addition, in these games there are always short sequences of coalitional improvement moves to Pareto-optimal Nash and strong equilibria that can be computed efficiently.     

求解图型博弈的Nash均衡

图型博弈是一种新的博弈表示方法。求解Nash均衡是图型博弈的核心问题。论文把求解图型博弈的Nash均衡看作是离散空间中的优化问题,给出了求解图型博弈ε-Nash均衡的迭代优化算法。另外,为加快算法的收敛速度,提出了一个获得高迭代效率策略剖面的方法:基于博弈的图形结构进行多策略更新。实验结果表明算法是可行、高效的。     

Worst-Case Nash Equilibria in Restricted Routing

We study the network routing problem with restricted and related links.There are parallel links with possibly different speeds,between a source and a sink.Also there are users,and each user has a traffic of some weight to assign to one of the links from a subset of all the links,named his/her allowable set.The users choosing the same link suffer the same delay,which is equal to the total weight assigned to that link over its speed.A state of the system is called a Nash equilibrium if no user can decrease his/her delay by unilaterally changing his/her link.To measure the performance degradation of the system due to the selfish behavior of all the users,Koutsoupias and Papadimitriou proposed the notion Price of Anarchy (denoted by PoA),which is the ratio of the maximum delay in the worst-case Nash equilibrium and in an optimal solution.The PoA for this restricted related model has been studied,and a linear lower bound was obtained.However in their bad instance,some users can only use extremely slow links.This is a little artificial and unlikely to appear in a real world.So in order to better understand this model,we introduce a parameter for the system,and prove a better Price of Anarchy in terms of the parameter.We also show an important application of our result in coordination mechanism design for task scheduling game.We propose a new coordination mechanism,Group-Makespan,for unrelated selfish task scheduling game with improved price of anarchy.     

状态无关主动队列管理算法博弈的Nash均衡

状态无关的主动队列管理算法处理分组时不区分分组所在的流的信息，因此在Internet中，它易于设计和部署。文中通过数学分析和仿真方法研究AQM博弈和Nash均衡存在性。假设业务流是Poisson分布的且用户可自由修改发送速率，因而有结论：Drop Tail、RED不能获得Nash均衡，CHOKe可以获得近似Nash均衡。依据判定条件，推导出一种与状态无关且具有效率的Nash均衡AQM算法。     

状态无关主动队列管理算法博弈的Nash均衡

状态无关的主动队列管理算法处理分组时不区分分组所在的流的信息,因此在Internet中,它易于设计和部署。文中通过数学分析和仿真方法研究AQM博弈和Nash均衡存在性。假设业务流是Poisson分布的且用户可自由修改发送速率,因而有结论:Drop Tail、RED不能获得Nash均衡,CHOKe可以获得近似Nash均衡。依据判定条件,推导出一种与状态无关且具有效率的Nash均衡AQM算法。     

Nash Equilibria and the Price of Anarchy for Flows over Time

We study Nash equilibria in the context of flows over time. Many results on static routing games have been obtained over the last ten years. In flows over time (also called dynamic flows), flow travels through a network over time and, as a consequence, flow values on edges are time-dependent. This more realistic setting has not been tackled from the viewpoint of algorithmic game theory yet; but there is a rich literature on game theoretic aspects of flows over time in the traffic community.     

Nash equilibria: Complexity,symmetries, and approximation

We survey recent joint work with Christos Papadimitriou and Paul Goldberg on the computational complexity of Nash equilibria. We show that finding a Nash equilibrium in normal form games is computationally intractable, but in an unusual way. It does belong to the class NP; but Nash’s theorem, showing that a Nash equilibrium always exists, makes the possibility that it is also NP-complete rather unlikely. We show instead that the problem is as hard computationally as finding Brouwer fixed points, in a precise technical sense, giving rise to a new complexity class called PPAD. The existence of the Nash equilibrium was established via Brouwer’s fixed-point theorem; hence, we provide a computational converse to Nash’s theorem.To alleviate the negative implications of this result for the predictive power of the Nash equilibrium, it seems natural to study the complexity of approximate equilibria: an efficient approximation scheme would imply that players could in principle come arbitrarily close to a Nash equilibrium given enough time. We review recent work on computing approximate equilibria and conclude by studying how symmetries may affect the structure and approximation of Nash equilibria. Nash showed that every symmetric game has a symmetric equilibrium. We complement this theorem with a rich set of structural results for a broader, and more interesting class of games with symmetries, called anonymous games.     

一种TCP博弈模型的Nash均衡存在性分析与仿真

在当今的Internet中,远程教学、大规模传输等“不响应拥塞”应用与日剧增,使得端系统有动机更改拥塞控制方案以满足自己的需要,这加重了Internet拥塞。一般希望通过研究用户非合作博弈行为的Nash均衡来规范自私的端用户行为。阐述了TCP拥塞博弈模型,主体为采取TCP协议的端用户,策略为TCP端用户的慢启动拥塞窗口递增参数。通过数学分析方法论证了网络方对TCP流没有额外的处罚时,TCP博弈存在Nash均衡。同时,通过Ns2仿真工具验证了当路由器采用DropTail队列管理算法,端节点采取TCPTahoe和TCPReno时,TCP博弈存在Nash均衡。这意味着TCP算法对Internet的稳定起着重要作用。     

Computing Nash Equilibria for Scheduling on Restricted Parallel Links

We consider the problem of routing n users on m parallel links under the restriction that each user may only be routed on a link from a certain set of allowed links for the user. So, this problem is equivalent to the correspondingly restricted scheduling problem of assigning n jobs to m parallel machines. In a Nash equilibrium, no user may improve its own Individual Cost (latency) by unilaterally switching to another link from its set of allowed links.     

Equilibria problems on games: Complexity versus succinctness

We study the computational complexity of problems involving equilibria in strategic games and in perfect information extensive games when the number of players is large. We consider, among others, the problems of deciding the existence of a pure Nash equilibrium in strategic games or deciding the existence of a pure Nash or a subgame perfect Nash equilibrium with a given payoff in finite perfect information extensive games. We address the fundamental question of how can we represent a game with a large number of players? We propose three ways of representing a game with different degrees of succinctness for the components of the game. For perfect information extensive games we show that when the number of moves of each player is large and the input game is represented succinctly these problems are PSPACE-complete. In contraposition, when the game is described explicitly by means of its associated tree all these problems are decidable in polynomial time. For strategic games we show that the complexity of deciding the existence of a pure Nash equilibrium depends on the succinctness of the game representation and then on the size of the action sets. In particular we show that it is NP-complete, when the number of players is large and the number of actions for each player is constant, and that the problem is -complete when the number of players is a constant and the size of the action sets is exponential in the size of the game representation. Again when the game is described explicitly the problem is decidable in polynomial time.     

Computation of Multi-facility Location Nash Equilibria on a Network Under Quantity Competition

We deal with the location-quantity problem for competing firms when they locate multiple facilities and offer the same type of product. Competition is performed under delivered quantities that are sent from the facilities to the customers. This problem is reduced to a location game when the competing firms deliver the Cournot equilibrium quantities. While existence conditions for a Nash equilibrium of the location game have been discussed in many contributions in the literature, computing an equilibrium on a network when multiple facilities are to be located by each firm is a problem not previously addressed. We propose an integer linear programming formulation to fill this gap. The formulation solves the profit maximization problem for a firm, assuming that the other firms have fixed their facility locations. This allows us to compute location Nash equilibria by the best response procedure. A study with data of Spanish municipalities under different scenarios is presented and conclusions are drawn from a sensitivity analysis.

     

对等网副本散布问题纯策略纳什均衡研究

在对等网环境中为增强数据的可靠性与访问效率,需要将数据副本进行有效的散布。应用博彝论原理研究副本散布问题是一种有效的新方法。分析了当前使用博弈论方法研究所存在的问题,提出副本散布问题的基本博彝模型,首次证明了多对象且节点容量有限情况下纯策略纳什均衡的存在性,较以前的研究成果更具有实用价值,且是今后进一步研究的基础。     

The Qualitative Properties of Symmetric Open‐Loop Nash Equilibria in the State‐Control Dynamic System in Differential Games

The local stability, steady state comparative statics, and local comparative dynamics of symmetric open‐loop Nash equilibria in the state‐control dynamic system for a seemingly ubiquitous class of discounted infinite horizon differential games are investigated. It is shown that most of the useful qualitative results occur because the same small number of assumptions is being made about the mathematical structure of the integrand and/or state equations. Applications of the results to exhaustible resource extraction and capital accumulation differential games are provided.     

Deterministic calibration and Nash equilibrium

We provide a natural learning process in which the joint frequency of (time-averaged) empirical play converges into the set of convex combinations of Nash equilibria. Furthermore, the actual distribution of players' actions is close to some (approximate) Nash equilibria on most rounds (on all but a vanishing fraction of the rounds). In this process, all players rationally choose their actions using a public prediction made by a deterministic, weakly calibrated algorithm. For this to be possible, we show that such a deterministic (weakly) calibrated learning algorithm exists.     

Approximation of Nash strategies

Near-equilibrium solutions of nonzero-sum differential games are defined. It is shown that truncated series solutions of linear quadratic games are near-equilibrium.     

Cournot–Nash and Bertrand–Nash equilibria for a heterogeneous duopoly of differentiated products

Under Cournot–Nash and Bertrand–Nash equilibria, analytical expressions are found for outputs, prices, and profits in the case when all duopoly parameters of differentiated products are different. It is shown that the signs of differences between such outputs, prices, and profits depend on the complementarity or substitutability of products. The concepts of exogenous, endogenous, and asymmetric differentiated products are introduced.     

Equilibria and convex cost networks

This paper explores the relationship between equilibria and convex cost networks. It is shown that the equilibrium points of certain large-scale systems can be obtained as the solution of convex programs. The extremality conditions that relate a certain primal-dual program pair are equivalent to equilibrium conditions. An economics example is given to illustrate the theory