Unified approach to approximate solutions in games and multiobjective programming

Using a theorem of Tijs, we derive results about approximate solutions for Nash equilibrium theory and for multiobjective problems. We describe conditions under which one can replace an infinite strategy set, an infinite alternative set, or an infinite set of criteria by a finite subset without losing all approximate solutions of the problem under consideration.This work was done during the period when the second author was Visiting Professor of the Italian National Research Council at the Mathematical Department of the University of Pavia, Pavia, Italy.     

Finding all pure strategy Nash equilibria in a planar location game

In this paper, we deal with a planar location-price game where firms first select their locations and then set delivered prices in order to maximize their profits. If firms set the equilibrium prices in the second stage, the game is reduced to a location game for which pure strategy Nash equilibria are studied assuming that the marginal delivered cost is proportional to the distance between the customer and the facility from which it is served. We present characterizations of local and global Nash equilibria. Then an algorithm is shown in order to find all possible Nash equilibrium pairs of locations. The minimization of the social cost leads to a Nash equilibrium. An example shows that there may exist multiple Nash equilibria which are not minimizers of the social cost.     

Equilibria in load balancing games

A Nash equilibrium （NE） in a multi-agent game is a strategy profile that is resilient to unilateral deviations. A strong Nash equilibrium （SE） is one that is stable against coordinated deviations of any coalition. We show that, in the load balancing games, NEs approximate SEs in the sense that the benefit of each member of any coalition from coordinated deviations is well limited. Furthermore, we show that an easily recognizable special subset of NEs exhibit even better approximation of SEs.     

Juche versus Sadae: Game-theoretic approach

We argue that to some degree Juche is represented by the concept of Nash equilibrium, and Sadae by Thompson and Faith's truly perfect information equilibrium. We characterize the latter, and show that for a Pareto optimal Nash equilibrium, Juche is as good as, or better than Sadae. This includes the game of brinkmanship.     

约束形式下广义最大元Nash均衡的存在性

运用广义最大元方法在非传递性偏好下给出了博弈均衡的存在性定理,推广了一些经典的博弈均衡存在性定理.在文中介绍策略式博弈的Nash均衡具有宽泛的条件,在微观经济理论中有广泛的应用.     

Nash refinement of equilibria

A method for choosing equilibria in strategic form games is proposed and axiomatically characterized. The method as well as the axioms are inspired by the Nash bargaining theory. The method can be applied to existing refinements of Nash equilibrium (e.g., perfect equilibrium) and also to other equilibrium concepts, like correlated equilibrium.The authors thank the reviewers for their comments, which led to an improvement of the paper.     

A silent duel over a cake

The division of a cake by two players is modelled by means of a silent game of timing. It is shown that this game has a unique Nash equilibrium. The strategies of the Nash equilibrium are explicitly given.I thank Peter Borm, Eric van Damme, Feico Drost, Harold Houba, Jos Potters, Stef Tijs and the referees for their comments.     

Logit equilibrium as an approximation of Nash equilibrium

We prove that the graph of the logit equilibrium correspondence is a smooth manifold, which is homeomorphic to the space of payoff functions and uniformly approximates the graph of the Nash equilibrium manifold.     

管理中的Nash平衡与Braess悖论现象

本给出了交通规划、经济贸易以及其它管理中的一些Nash平衡和Braess悖论实例，分析了Nash平衡和Braess悖论现象及其本质特征，指出它们在管理工作中具有普遗性和潜在应用性。     

A two-population game in observable double-ended queuing systems

In this study, the existing game theoretical framework is extended to strategic queuing in search of solutions for a two-population game in observable double-ended queuing systems with zero matching times. We show that multiple Nash equilibria and one unique subgame perfect Nash equilibrium exist in this game.     

A procedure for finding Nash equilibria in bi-matrix games

In this paper we consider the computation of Nash equilibria for noncooperative bi-matrix games. The standard method for finding a Nash equilibrium in such a game is the Lemke-Howson method. That method operates by solving a related linear complementarity problem (LCP). However, the method may fail to reach certain equilibria because it can only start from a limited number of strategy vectors. The method we propose here finds an equilibrium by solving a related stationary point problem (SPP). Contrary to the Lemke-Howson method it can start from almost any strategy vector. Besides, the path of vectors along which the equilibrium is reached has an appealing game-theoretic interpretation. An important feature of the algorithm is that it finds a perfect equilibrium when at the start all actions are played with positive probability. Furthermore, we can in principle find all Nash equilibria by repeated application of the algorithm starting from different strategy vectors.This author is financially supported by the Co-operation Centre Tilburg and Eindhoven Universities, The Netherlands.     

Homogeneous Customers Renege from Invisible Queues at Random Times under Deteriorating Waiting Conditions

We consider a memoryless first-come first-served queue in which customers' waiting costs are increasing and convex with time. Hence, customers may opt to renege if service has not commenced after waiting for some time. We assume a homogeneous population of customers and we look for their symmetric Nash equilibrium reneging strategy. Besides the model parameters, customers are aware only, if they are in service or not, and they recall for how long they are have been waiting. They are informed of nothing else. We show that under some assumptions on customers' utility function, Nash equilibrium prescribes reneging after random times. We give a closed form expression for the resulting distribution. In particular, its support is an interval (in which it has a density) and it has at most two atoms (at the edges of the interval). Moreover, this equilibrium is unique. Finally, we indicate a case in which Nash equilibrium prescribes a deterministic reneging time.     

DYNAMIC BEHAVIOURS OF AN AUTONOMOUS STAGE-STRUCTURED COMPETITIVE SYSTEMS WITH TOXIC EFFECT

It is known that somebody''s behavior (decision) in a stochastic social network may be influenced by that of his (or her) friends. In this paper, we consider two stochastic social network game models (a) and (b) which can be defined respectively by two different utility functions. Some sufficient conditions for the existence of Nash equilibrium (NE) of the two network game models are obtained by analyzing the different effort relation between a player and his (or her) neighbors.     

On differential games with a feedback nash equilibrium

This note provides a lemma on differential games which possess a feedback Nash equilibrium (FNE). In particular, it shows that (i) a class of games with a degenerate FNE can be constructucted from every game which has a nondegenerate FNE and (ii) a class of games with a nondegenerate FNE can be constructed from every game which has a degenerate FNE.The author would like to thank an anonymous referee for invaluable comments and suggestions.     

Learning Equilibrium Play: A Myopic Approach

We model repeated play of noncooperative stage games in terms of approximate gradient steps. That simple format requires little information and no optimization. Moreover, it allows players to evaluate marginal cost or profit inexactly and to move with different velocities. Uncertainty can also be accommodated. Granted some crucial stability, we show that play converges to Nash equilibrium.     

两阶段主从博弈均衡解的存在性

首先给出带参数的纳什均衡问题Γ(x),在此基础上给出了具有带参数的纳什均衡约束的两阶段主从博弈问题G.可以证明带参数的纳什均衡点是存在的,即无论领导者选择何种策略,跟随者的最佳回应集都是非空的.最后推出了关于两阶段主从博弈均衡点的存在性定理.     

Strong stability of Nash equilibria in load balancing games

We study strong stability of Nash equilibria in load balancing games of m(m 2)identical servers,in which every job chooses one of the m servers and each job wishes to minimize its cost,given by the workload of the server it chooses.A Nash equilibrium(NE)is a strategy profile that is resilient to unilateral deviations.Finding an NE in such a game is simple.However,an NE assignment is not stable against coordinated deviations of several jobs,while a strong Nash equilibrium(SNE)is.We study how well an NE approximates an SNE.Given any job assignment in a load balancing game,the improvement ratio(IR)of a deviation of a job is defined as the ratio between the pre-and post-deviation costs.An NE is said to be aρ-approximate SNE(ρ1)if there is no coalition of jobs such that each job of the coalition will have an IR more thanρfrom coordinated deviations of the coalition.While it is already known that NEs are the same as SNEs in the 2-server load balancing game,we prove that,in the m-server load balancing game for any given m 3,any NE is a(5/4)-approximate SNE,which together with the lower bound already established in the literature yields a tight approximation bound.This closes the final gap in the literature on the study of approximation of general NEs to SNEs in load balancing games.To establish our upper bound,we make a novel use of a graph-theoretic tool.     

Existence and uniqueness of a Nash equilibrium feedback for a simple nonzero-sum differential game

Existence and uniqueness of a Nash equilibrium feedback is established for a simple class nonzero-sum differential games on the line.     

A Strong Anti-Folk Theorem

We study the properties of finitely complex, symmetric, globally stable, and semi-perfect equilibria. We show that: (1) If a strategy satisfies these properties then players play a Nash equilibrium of the stage game in every period; (2) The set of finitely complex, symmetric, globally stable, semi-perfect equilibrium payoffs in the repeated game equals the set of Nash equilibria payoffs in the stage game; and (3) A strategy vector satisfies these properties in a Pareto optimal way if and only if players play some Pareto optimal Nash equilibrium of the stage game in every stage. Our second main result is a strong anti-Folk Theorem, since, in contrast to what is described by the Folk Theorem, the set of equilibrium payoffs does not expand when the game is repeated.This paper is a revised version of Chapter 3 of my Ph.D. thesis, which has circulated under the title “An Interpretation of Nash Equilibrium Based on the Notion of Social Institutions”.     

一类投资价值为变量的研究与开发项目的Nash解问题

本文考虑一类完全信息下研究与开发 (R& D)项目中的纯策略问题 .设有一个 R& D项目 ,两位风险中性的投资人竞争 .项目需要的投资量至少是 I,投资较多的一方取胜 .项目成功后的价值是确定的 ,但是其价值大小对这两位投资人不一样 (品牌知名度 ,管理水平 ,营销能力等方面的差异导致的价格和销量不同 ) ,我们使用博弈论方法对此进行研究 ,得到的结果显示 :如果他们所实现的项目价值是常量 ,则不存在均衡解 ;而当项目价值是一个关于投资总量的单增函数时 ,则在两位投资人的价值函数的差异较大时 ,存在一个同时还是社会占优的 Nash均衡解 ,在两位投资人的价值函数差异不太大时 ,不存在均衡解 ,此时的竞争会导致社会效益下降 .从而提示政府应当通过一定的方式 (如招投标法 ,审批法 )对投资活动予以控制 .