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.     

Nash equilibria of Cauchy-random zero-sum and coordination matrix games

We consider zero-sum games (A,  − A) and coordination games (A,A), where A is an m-by-n matrix with entries chosen independently with respect to the Cauchy distribution. In each case, we give an exact formula for the expected number of Nash equilibria with a given support size and payoffs in a given range, and also asymptotic simplications for matrices of a fixed shape and increasing size. We carefully compare our results with recent results of McLennan and Berg on Gaussian random bimatrix games (A,B), and describe how the three situations together shed light on random bimatrix games in general.     

Nash equilibria in random games

We consider Nash equilibria in 2‐player random games and analyze a simple Las Vegas algorithm for finding an equilibrium. The algorithm is combinatorial and always finds a Nash equilibrium; on m × n payoff matrices, it runs in time O(m²nloglog n + n²mloglog m) with high probability. Our result follows from showing that a 2‐player random game has a Nash equilibrium with supports of size two with high probability, at least 1 − O(1/log n). Our main tool is a polytope formulation of equilibria. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Generic stability of Nash equilibria for noncooperative differential games

The stability of Nash equilibria against the perturbation of the right-hand side functions of state equations for noncooperative differential games is investigated. By employing the set-valued analysis theory, we show that the differential games whose equilibria are all stable form a dense residual set, and every differential game can be approximated arbitrarily by a sequence of stable differential games, that is, in the sense of Baire’s category most of the differential games are stable.     

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.     

On existence of undominated pure strategy Nash equilibria in anonymous nonatomic games: a generalization

In this paper, we generalize the exitence result for pure strategy Nash equilibria in anonymous nonatomic games. By working directly on integrals of pure strategies, we also generalize, for the same class of games, the existence result for undominated pure strategy Nash equilibria even though, in general, the set of pure strategy Nash equilibria may fail to be weakly compact. Received August 2001     

Information patterns and Nash equilibria in extensive games — II

In Part I of this paper we introduced extensive games with a non-atomic continuum of players. It was shown that the Nash plays (outcomes) are invariant of the information patterns on the game, provided that no player's unilateral change in moves can be observed by others. This led to an enormous reduction in the Nash plays of the these games, as exemplified in the anti-folk theorem. Our concern in this sequel is to develop a finite version of these results.     

On the existence of strong Nash equilibria

This paper investigates the existence of strong Nash equilibria (SNE) in continuous and concave games. It is shown that the coalition consistency property introduced in the paper, together with concavity and continuity of payoffs, permits the existence of SNE in games with compact and convex strategy spaces. We also characterize the existence of SNE by providing necessary and sufficient conditions. We suggest an algorithm for computing SNE. The results are illustrated with applications to economies with multilateral environmental externalities and to the static oligopoly model.     

Computing approximate Nash equilibria in general network revenue management games

Computing optimal capacity allocations in network revenue management is computationally hard. The problem of computing exact Nash equilibria in non-zero-sum games is computationally hard, too. We present a fast heuristic that, in case it cannot converge to an exact Nash equilibrium, computes an approximation to it in general network revenue management problems under competition. We also investigate the question whether it is worth taking competition into account when making (network) capacity allocation decisions. Computational results show that the payoffs in the approximate equilibria are very close to those in exact ones. Taking competition into account never leads to a lower revenue than ignoring competition, no matter what the competitor does. Since we apply linear continuous models, computation time is very short.     

Information patterns and Nash equilibria in extensive games: 1

In this paper we explore the relation between information patterns and Nash Equilibria in extensive games. By information we mean what players know about moves made by others, as well as by chance. For the most part we confine ourselves to pure strategies. But in Section 2 behavioral strategies are also examined. It turns out that they can be modeled as pure strategies of an appropriately enlarged game. Our results, applied to the enlarged game, can then be reinterpreted in terms of the behavioral strategies of the original game.     

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.     

Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games

The noncooperative multi-leader-follower game can be formulated as a generalized Nash equilibrium problem where each player solves a nonconvex mathematical program with equilibrium constraints. Two major deficiencies exist with such a formulation: One is that the resulting Nash equilibrium may not exist, due to the nonconvexity in each players problem; the other is that such a nonconvex Nash game is computationally intractable. In order to obtain a viable formulation that is amenable to practical solution, we introduce a class of remedial models for the multi-leader-follower game that can be formulated as generalized Nash games with convexified strategy sets. In turn, a game of the latter kind can be formulated as a quasi-variational inequality for whose solution we develop an iterative penalty method. We establish the convergence of the method, which involves solving a sequence of penalized variational inequalities, under a set of modest assumptions. We also discuss some oligopolistic competition models in electric power markets that lead to multi-leader-follower games.Jong-Shi Pang: The work of this authors research was partially supported by the National Science Foundation under grant CCR-0098013 and ECS-0080577 and by the Office of Naval Research under grant N00014-02-1-0286.Masao Fukushima: The work of this authors research was partially supported by a Grant-in-Aid for Scientific Research from the Ministry of Education, Science, Culture and Sports of Japan.     

Finding a Nash equilibrium in noncooperativeN-person games by solving a sequence of linear stationary point problems

In this paper we present an algorithm for finding a Nash equilibrium in a noncooperative normal formN-person game. More generally, the algorithm can be applied for solving a nonlinear stationary point problem on a simplotope, being the Cartesian product of several simplices. The algorithm solves the problem by solving a sequence of linear stationary point problems. Each problem in the sequence is solved in a finite number of iterations. Although the overall convergence cannot be proved, the method performs rather well. Computational results suggest that this algorithm performs at least as good as simplicial algorithms do.For the special case of a bi-matrix game (N=2), the algorithm has an appealing game-theoretic interpretation. In that case, the problem is linear and the algorithm always finds a solution. Furthermore, the equilibrium found in a bi-matrix game is perfect whenever the algorithm starts from a strategy vector at which all actions are played with positive probability.This research is part of the VF-program Co-operation and Competition, which has been approved by the Netherlands Ministery of Education and Sciences.     

Algorithms for computing Nash equilibria in deterministic LQ games

In this paper we review a number of algorithms to compute Nash equilibria in deterministic linear quadratic differential games. We will review the open-loop and feedback information case. In both cases we address both the finite and the infinite-planning horizon.     

Nash equilibria in competitive project scheduling

We consider the problem of scheduling activities of a project by a firm that competes with another firm that has to perform the same project. The profit that a firm gets from each activity depends on whether the firm finishes the activity before or after its competitor. It is required to find a Nash equilibrium solution or show that no such solutions exist. We present a structural characterization of Nash equilibrium solutions, and a low order polynomial algorithm for the problem.     

Sufficient conditions for Nash equilibria inN-person games over reflexive Banach spaces

Sufficient conditions are obtained for the existence of Nash equilibrium points inN-person games when the strategy sets are closed, convex subsets of reflexive Banach spaces. These conditions require that each player's cost functional is convex in that player's strategy, weakly continuous in the strategies of the other players, weakly lower semicontinuous in all strategies, and furthermore satisfies a coercivity condition if any of the strategy sets is unbounded. The result is applied to a class of linear-quadratic differential games with no information, to prove that equilibrium points exist when the duration of these games is sufficiently small.This work was supported by a Commonwealth of Australia, Postgraduate Research Award.     

On Nash equilibria inN-person games over reflexive Banach spaces

In this note, an extended version of the Ky Fan inequality is obtained for reflexive Banach spaces. As an application of the result, it is proved that Nash equilibrium points exist under weaker conditions than those of Williams (Ref. 1).     

Nash equilibria in optimal reinsurance bargaining

We introduce a strategic behavior in reinsurance bilateral transactions, where agents choose the risk preferences they will appear to have in the transaction. Within a wide class of risk measures, we identify agents’ strategic choices to a range of risk aversion coefficients. It is shown that at the strictly beneficial Nash equilibria, agents appear homogeneous with respect to their risk preferences. While the game does not cause any loss of total welfare gain, its allocation between agents is heavily affected by the agents’ strategic behavior. This allocation is reflected in the reinsurance premium, while the insurance indemnity remains the same in all strictly beneficial Nash equilibria. Furthermore, the effect of agents’ bargaining power vanishes through the game procedure and the agent who gets more welfare gain is the one who has an advantage in choosing the common risk aversion at the equilibrium.