How to Select a Solution in Generalized Nash Equilibrium Problems

We propose a new solution concept for generalized Nash equilibrium problems. This concept leads, under suitable assumptions, to unique solutions, which are generalized Nash equilibria and the result of a mathematical procedure modeling the process of finding a compromise. We first compute the favorite strategy for each player, if he could dictate the game, and use the best response on the others’ favorite strategies as starting point. Then, we perform a tracing procedure, where we solve parametrized generalized Nash equilibrium problems, in which the players reduce the weight on the best possible and increase the weight on the current strategies of the others. Finally, we define the limiting points of this tracing procedure as solutions. Under our assumptions, the new concept selects one reasonable out of typically infinitely many generalized Nash equilibria.     

Cournot tâtonnement and dominance solvability in finite games

If a finite strategic game is strictly dominance solvable, then every simultaneous best response adjustment path, as well as every non-discriminatory individual best response improvement path, ends at a Nash equilibrium after a finite number of steps. If a game is weakly dominance solvable, then every strategy profile can be connected to a Nash equilibrium with a simultaneous best response path and with an individual best response path (if there are more than two players, switches from one best response to another may be needed). Both statements remain valid if dominance solvability in the usual sense is replaced with “BR-dominance solvability”, where a strategy can be eliminated if it is not among the best responses to anything, or if it is not indispensable for providing the best responses to all contingencies. For a two person game, some implications in the opposite direction are obtained.     

Best response dynamics for role games

In a role game, players can condition their strategies on their player position in the base game. If the base game is strategically equivalent to a zero-sum game, the set of Nash equilibria of the role game is globally asymptotically stable under the best response dynamics. If the base game is 2 ×2, then in the cyclic case the set of role game equilibria is a continuum. We identify a single equilibrium in this continuum that attracts all best response paths outside the continuum. Received: June 2001     

Absolutely expedient algorithms for learning Nash equilibria

This paper considers a multi-person discrete game with random payoffs. The distribution of the random payoff is unknown to the players and further none of the players know the strategies or the actual moves of other players. A class of absolutely expedient learning algorithms for the game based on a decentralised team of Learning Automata is presented. These algorithms correspond, in some sense, to rational behaviour on the part of the players. All stable stationary points of the algorithm are shown to be Nash equilibria for the game. It is also shown that under some additional constraints on the game, the team will always converge to a Nash equilibrium. Dedicated to the memory of Professor K G Ramanathan     

On a class of nonzero-sum,linear-quadratic differential games

A class of two-player, nonzero-sum, linear-quadratic differential games is investigated for Nash equilibrium solutions when both players use closed-loop control and when one or both of the players are required to use open-loop control. For three formulations of the game, necessary and sufficient conditions are obtained for a particular strategy set to be a Nash equilibrium strategy set. For a fourth formulation of the game, where both players use open-loop control, necessary and sufficient conditions for the existence of a Nash equilibrium strategy set are developed. Several examples are presented in order to illustrate the differences between this class of differential games and its zero-sum analog.This research was supported by the National Science Foundation under Grant No. GK-3341.     

Structure of equilibria inN-person non-cooperative games

Here we study the structure of Nash equilibrium points forN-person games. For two-person games we observe that exchangeability and convexity of the set of equilibrium points are synonymous. This is shown to be false even for three-person games. For completely mixed games we get the necessary inequality constraints on the number of pure strategies for the players. Whereas the equilibrium point is unique for completely mixed two-person games, we show that it is not true for three-person completely mixed game without some side conditions such as convexity on the equilibrium set. It is a curious fact that for the special three-person completely mixed game with two pure strategies for each player, the equilibrium point is unique; the proof of this involves some combinatorial arguments.     

Do we detect and exploit mixed strategy play by opponents?

We conducted an experiment in which each subject repeatedly played a game with a unique Nash equilibrium in mixed strategies against some computer-implemented mixed strategy. The results indicate subjects are successful at detecting and exploiting deviations from Nash equilibrium. However, there is heterogeneity in subject behavior and performance. We present a one variable model of dynamic random belief formation which rationalizes observed heterogeneity and other features of the data.The minimax and Nash equilibrium solutions coincide in this setting, and we could proceed only referring to the minimax solution and strategies. However, we proceed using the Nash equilibrium framework because we wish to focus on the concept of best response.     

Two noncooperative games between a coalition and its surrounding in a class of n-person games with constant sum

A cooperative game engendered by a noncooperative n-person game (the master game) in which any subset of n players may form a coalition playing an antagonistic game against the residual players (the surrounding) that has a (Nash equilibrium) solution, is considered, along with another noncooperative game in which both a coalition and its surrounding try to maximize their gains that also possesses a Nash equilibrium solution. It is shown that if the master game is the one with constant sum, the sets of Nash equilibrium strategies in both above-mentioned noncooperative games (in which a coalition plays with (against) its surrounding) coincide.     

Internal correlation in repeated games

This paper characterizes the set of all the Nash equilibrium payoffs in two player repeated games where the signal that the players get after each stage is either trivial (does not reveal any information) or standard (the signal is the pair of actions played). It turns out that if the information is not always trivial then the set of all the Nash equilibrium payoffs coincides with the set of the correlated equilibrium payoffs. In particular, any correlated equilibrium payoff of the one shot game is also a Nash equilibrium payoff of the repeated game.For the proof we develop a scheme by which two players can generate any correlation device, using the signaling structure of the game. We present strategies with which the players internally correlate their actions without the need of an exogenous mediator.     

Distributed consensus in noncooperative inventory games

This paper deals with repeated nonsymmetric congestion games in which the players cannot observe their payoffs at each stage. Examples of applications come from sharing facilities by multiple users. We show that these games present a unique Pareto optimal Nash equilibrium that dominates all other Nash equilibria and consequently it is also the social optimum among all equilibria, as it minimizes the sum of all the players’ costs. We assume that the players adopt a best response strategy. At each stage, they construct their belief concerning others probable behavior, and then, simultaneously make a decision by optimizing their payoff based on their beliefs. Within this context, we provide a consensus protocol that allows the convergence of the players’ strategies to the Pareto optimal Nash equilibrium. The protocol allows each player to construct its belief by exchanging only some aggregate but sufficient information with a restricted number of neighbor players. Such a networked information structure has the advantages of being scalable to systems with a large number of players and of reducing each player’s data exposure to the competitors.     

Limiting distributions of the number of pure strategy Nash equilibria in n-person games

We study the number of pure strategy Nash equilibria in a “random” n-person non-cooperative game in which all players have a countable number of strategies. We consider both the cases where all players have strictly and weakly ordinal preferences over their outcomes. For both cases, we show that the distribution of the number of pure strategy Nash equilibria approaches the Poisson distribution with mean 1 as the numbers of strategies of two or more players go to infinity. We also find, for each case, the distribution of the number of pure strategy Nash equilibria when the number of strategies of one player goes to infinity, while those of the other players remain finite.     

A non-zero-zum War of Attrition

The division of a cake by two players is modelled by means of a game of timing in which the players have a probability of learning when their opponent acts. It is shown that the game has a unique Nash equilibrium when both players are non-noisy but that there are many Nash equilibria including pure ones when at least one of the players is noisy. Explicit expressions for the strategies used in these Nash equilibria are obtained.This work was carried out while Dr. Garnaev was visiting the University of Southampton on a Postdoctoral Fellowship of The Royal Society of London.     

Non-additive anonymous games

This paper introduces a class of non-additive anonymous games where agents are assumed to be uncertain (in the sense of Knight) about opponents’ strategies and about the initial distribution over players’ characteristics in the game. We model uncertainty by non-additive measures or capacities and prove the Cournot–Nash equilibrium existence theorem for this class of games. Equilibrium distribution can be symmetrized under milder conditions than in the case of additive games. In particular, it is not required for the space characteristics to be atomless under capacities. The set-valued map of the Cournot–Nash equilibria is upper-semicontinuous as a function of initial beliefs of the players for non-additive anonymous games.     

Forward-backward stochastic differential equation games with delay and noisy memory

Abstract

The goal of this paper is to study a stochastic game connected to a system of forward-backward stochastic differential equations (FBSDEs) involving delay and noisy memory. We derive sufficient and necessary maximum principles for a set of controls for the players to be a Nash equilibrium in the game. Furthermore, we study a corresponding FBSDE involving Malliavin derivatives. This kind of equation has not been studied before. The maximum principles give conditions for determining the Nash equilibrium of the game. We use this to derive a closed form Nash equilibrium for an economic model where the players maximize their consumption with respect to recursive utility.     

A two-person non-zero-sum game model of the world oil market

The world oil market is modelled as a two-person non-zero-sum game in normal form with each player having a continuum of strategies. The two players are the oil importing nations (OPIC) and the oil exporting nations (OPEC). The game is solved in the noncooperative sense using the equilibrium point solution concept due to Nash. The Nash equilibrium point solution yields an analytic expression for the optimal price per barrel of oil for OPEC and the optimal level of imports of oil for OPIC assuming noncooperation between the players. The cooperative solution to the game is also investigated using the von Neumann-Morgenstern negotiation set solution and Nash's bargaining point solution. Again, we give analytic expressions for the optimal price of a barrel of oil and the optimal level of imports of oil assuming that the players cooperate (negotiate, bargain, etc., for a binding agreement) in arriving at a solution.     

Learning algorithms for repeated bimatrix Nash games with incomplete information

The purpose of this paper is to study a particular recursive scheme for updating the actions of two players involved in a Nash game, who do not know the parameters of the game, so that the resulting costs and strategies converge to (or approach a neighborhood of) those that could be calculated in the known parameter case. We study this problem in the context of a matrix Nash game, where the elements of the matrices are unknown to both players. The essence of the contribution of this paper is twofold. On the one hand, it shows that learning algorithms which are known to work for zero-sum games or team problems can also perform well for Nash games. On the other hand, it shows that, if two players act without even knowing that they are involved in a game, but merely thinking that they try to maximize their output using the learning algorithm proposed, they end up being in Nash equilibrium.This research was supported in part by NSF Grant No. ECS-87-14777.     

Game theoretic approach for fertilizer application: looking for the propensity to cooperate

This paper continues the research implemented in previous work of (Schreider et al. in Environ. Model. Assess. 15(4):223–238, 2010) where a game theoretic model for optimal fertilizer application in the Hopkins River catchment was formulated, implemented and solved for its optimal strategies. In that work, the authors considered farmers from this catchment as individual players whose objective is to maximize their objective functions which are constituted from two components: economic gain associated with the application of fertilizers which contain phosphorus to the soil and environmental harms associated with this application. The environmental losses are associated with the blue-green algae blooming of the coastal waterways due to phosphorus exported from upstream areas of the catchment. In the previous paper, all agents are considered as rational players and two types of equilibria were considered: fully non-cooperative Nash equilibrium and cooperative Pareto optimum solutions. Among the plethora of Pareto optima, the solution corresponding to the equally weighted individual objective functions were selected. In this paper, the cooperative game approach involving the formation of coalitions and modeling of characteristic value function will be applied and Shapley values for the players obtained. A significant contribution of this approach is the construction of a characteristic function which incorporates both the Nash and Pareto equilibria, showing that it is superadditive. It will be shown that this approach will allow each players to obtain payoffs which strictly dominate their payoffs obtained from their Nash equilibria.     

Variational inequality formulation for the games with random payoffs

We consider an n-player non-cooperative game with random payoffs and continuous strategy set for each player. The random payoffs of each player are defined using a finite dimensional random vector. We formulate this problem as a chance-constrained game by defining the payoff function of each player using a chance constraint. We first consider the case where the continuous strategy set of each player does not depend on the strategies of other players. If a random vector defining the payoffs of each player follows a multivariate elliptically symmetric distribution, we show that there exists a Nash equilibrium. We characterize the set of Nash equilibria using the solution set of a variational inequality (VI) problem. Next, we consider the case where the continuous strategy set of each player is defined by a shared constraint set. In this case, we show that there exists a generalized Nash equilibrium for elliptically symmetric distributed payoffs. Under certain conditions, we characterize the set of a generalized Nash equilibria using the solution set of a VI problem. As an application, the random payoff games arising from electricity market are studied under chance-constrained game framework.     

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.     

Relaxation Methods for Generalized Nash Equilibrium Problems with Inexact Line Search

The generalized Nash equilibrium problem (GNEP) is an extension of the standard Nash game where, in addition to the cost functions, also the strategy spaces of each player depend on the strategies chosen by all other players. This problem is rather difficult to solve and there are only a few methods available in the literature. One of the most popular ones is the so-called relaxation method, which is known to be globally convergent under a set of assumptions. Some of these assumptions, however, are rather strong or somewhat difficult to understand. Here, we present a modified relaxation method for the solution of a certain class of GNEPs. The convergence analysis uses completely different arguments based on a certain descent property and avoids some of the technical conditions for the original relaxation method. Moreover, numerical experiments indicate that the modified relaxation method performs quite well on a number of different examples taken from the literature.