Addendum to “Generalized Nash equilibrium problem,variational inequality and quasiconvexity” [Oper. Res. Lett. 36 (4) (2008) 461–464]

In this paper we correct an error which appeared in Theorem 4.1 in Aussel and Dutta (2008). We also provide an example to illustrate our point.     

Generalized Nash equilibrium problem, variational inequality and quasiconvexity

It is well known that the generalized Nash equilibrium problem, a model for multi-leader–follower games, can be reformulated as a quasivariational inequality. We show that, in fact, a reformulation in terms of a variational inequality can be obtained in the general setting of quasiconvex nondifferentiable decision functions. An existence result is deduced.     

On generalized Nash games and variational inequalities

We show that for a large class of problems a generalized Nash equilibrium can be calculated by solving a variational inequality. We analyze what solutions are found by this reduction procedure and hint at possible applications.     

Inequalities and Nash equilibria

This paper concentrates on the problem of the existence of equilibrium points for non-cooperative generalized N-person games, N-person games of normal form and their related inequalities. We utilize the K-K-M lemma to obtain a theorem and then use it to obtain a new Fan-type inequality and minimax theorems. Various new equilibrium point theorems are derived, with the necessary and sufficient conditions and with strategy spaces with no fixed point property. Examples are given to demonstrate that these existence theorems cover areas where other existence theorems break down.     

Generalized Nash equilibrium problems

The Generalized Nash equilibrium problem is an important model that has its roots in the economic sciences but is being fruitfully used in many different fields. In this survey paper we aim at discussing its main properties and solution algorithms, pointing out what could be useful topics for future research in the field. The work of Christain Kanzow has been partially supported by the program “Identification, Optimization and Control with Applications in Modern Technologies” of the Elite Network of Bavaria, Germany.     

双寡头电信市场中SP的定价模型

信息产业部对SP市场的整治,为未来无线服务提供商的发展提供了更加健康的生长空间。本文重点讨论了未来SP如何赁借自身的实力在双寡头电信市场中得以生存,发展的问题。文中分析了三人博弈的均衡问题,给出了纳什均衡解的取值空间及存在条件,为运营商和SP的发展提供了借鉴。     

Nash equilibrium in a pay-as-bid electricity market: Part 1 – existence and characterization

We consider a model of a pay-as-bid electricity market based on a multi-leader-common-follower approach where the producers as leaders are at the upper level and the regulator as a common follower is at the lower level. We fully characterize Nash equilibria for this model by describing necessary and sufficient conditions for their existence as well as providing explicit formulas of such equilibria in the market.     

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.     

Strategic bidding in continuous electricity auctions: an application to the Spanish electricity market

In this paper we introduce an asymmetric model of continuous electricity auctions with limited production capacity and bounded supply functions. The strategic bidding is studied with this model by means of an electricity market game. We prove that for every electricity market game with continuous cost functions a mixed-strategy Nash equilibrium always exists. In particular, we focus on the behavior of producers in the Spanish electricity market. We consider a very simple form for the Spanish electricity market: an oligopoly consisting just of independent hydro-electric power production units in a single wet period. We show that a pure-strategy Nash equilibrium for the Spanish electricity market game always exists.     

A variational inequality approach for the determination of oligopolistic market equilibrium

This paper presents an alternative approach to that by Murphy, Sherali and Soyster [13] for computing market equilibria with mathematical programming methods. This approach is based upon a variational inequality representation of the problem and the use of a diagonalization/relaxation algorithm.     

寡头市场的一类动态博弈模型

首先讨论了寡头垄断市场中n批厂商分批(每批至少有两个以上的厂商)先后进入某行业各批厂商依次且每批同时选择其产量的动态博弈模型的子博弈精练解及其相关结论,探讨了此结论与有关问题的比较分析,并给出此问题的几种特殊情况,说明了此模型的广泛性和实用性.     

Utilitarian resource assignment

This paper studies a resource allocation problem introduced by Koutsoupias and Papadimitriou. The scenario is modelled as a multiple-player game in which each player selects one of a finite number of known resources. The cost to the player is the total weight of all players who choose that resource, multiplied by the “delay” of that resource. Recent papers have studied the Nash equilibria and social optima of this game in terms of the L_∞ cost metric, in which the social cost is taken to be the maximum cost to any player. We study the L₁ variant of this game, in which the social cost is taken to be the sum of the costs to the individual players, rather than the maximum of these costs. We give bounds on the size of the coordination ratio, which is the ratio between the social cost incurred by selfish behavior and the optimal social cost; we also study the algorithmic problem of finding optimal (lowest-cost) assignments and Nash Equilibria. Additionally, we obtain bounds on the ratio between alternative Nash equilibria for some special cases of the problem.     

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.     

Infinite horizon noncooperative differential games with nonsmooth costs

For a noncooperative differential game, the value functions of the various players satisfy a system of Hamilton-Jacobi equations. In the present paper, we study a class of infinite-horizon scalar games with either piecewise linear or piecewise smooth costs, exponentially discounted in time. By the analysis of the value functions, we find that results about existence and uniqueness of admissible solutions to the HJ system, and therefore of Nash equilibrium solutions in feedback form, can be recovered as in the smooth costs case, provided the costs are globally monotone. On the other hand, we present examples of costs such that the corresponding HJ system has infinitely many admissible solutions or no admissible solutions at all, suggesting that new concepts of equilibria may be needed to study games with general nonlinear costs.     

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.     

Market power analysis in electricity markets using supply function equilibrium model

This paper presents a surveillance method based on the gametheory which is used by the ISO to find whether a power supplierin an electricity market has market power. The paper uses thesupply function equilibrium model to analyse the generationsuppliers’ bidding behaviour and models the ISO's marketpower monitoring problem as a bi-level multi-objective problem.The outer sub-problem is a multi-objective problem which maximizessuppliers’ payoffs, while the inner one is the ISO's marketclearing problem based on the locational marginal pricing mechanism.A discrete method is adopted to find ‘good enough’solutions, in a continuous bidding strategy space, which arethe intersection of all suppliers’ optimal response spacesaccording to Nash equilibrium. The paper utilizes the IEEE 118-bussystem to illustrate the application of the proposed methodwith three suppliers as price setters in the energy market andthe other generators as price takers. The numerical resultsshow that the transmission congestion may enhance the suppliers’ability to exercise market power. Likewise, suppliers’gaming behaviour could relieve the transmission congestion.It is shown that applying price caps is an efficient way ofmitigating market power.     

效用函数与纳什均衡

本文引入效用函数将博弈问题描述为收入形式和效用形式两种模型,使得纳什均衡与参与人效用函数联系起来,并得到结论(1)效用函数的变化对纯策略纳什均衡不产生影响,却改变真混合策略纳什均衡;(2)效用函数严格拟凹时,真混合策略蚋什均衡是稳定的;(3)效用函数严格拟凸时,真混合策略纳什均衡不存在.