A Characterization of Nash Equilibrium for the Games with Random Payoffs

We consider a two-player random bimatrix game where each player is interested in the payoffs which can be obtained with certain confidence. The payoff function of each player is defined using a chance constraint. We consider the case where the entries of the random payoff matrix of each player jointly follow a multivariate elliptically symmetric distribution. We show an equivalence between the Nash equilibrium problem and the global maximization of a certain mathematical program. The case where the entries of the payoff matrices are independent normal/Cauchy random variables is also considered. The case of independent normally distributed random payoffs can be viewed as a special case of a multivariate elliptically symmetric distributed random payoffs. As for Cauchy distribution, we show that the Nash equilibrium problem is equivalent to the global maximization of a certain quadratic program. Our theoretical results are illustrated by considering randomly generated instances of the game.     

Distributionally robust chance-constrained games: existence and characterization of Nash equilibrium

We consider an n-player finite strategic game. The payoff vector of each player is a random vector whose distribution is not completely known. We assume that the distribution of a random payoff vector of each player belongs to a distributional uncertainty set. We define a distributionally robust chance-constrained game using worst-case chance constraint. We consider two types of distributional uncertainty sets. We show the existence of a mixed strategy Nash equilibrium of a distributionally robust chance-constrained game corresponding to both types of distributional uncertainty sets. For each case, we show a one-to-one correspondence between a Nash equilibrium of a game and a global maximum of a certain mathematical program.     

General sum games with joint chance constraints

We consider an $n$-player non-cooperative game with continuous strategy sets. The strategy set of each player contains a set of stochastic linear constraints. We model the stochastic linear constraints of each player as a joint chance constraint. We assume that the row vectors of a matrix defining the stochastic constraints of each player are independent and each row vector follows a multivariate normal distribution. Under certain conditions, we show the existence of a Nash equilibrium for this game.     

Random Games Under Elliptically Distributed Dependent Joint Chance Constraints

Journal of Optimization Theory and Applications - We study an n-player game with random payoffs and continuous strategy sets. The payoff function of each player is defined by its expected value and...     

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.     

When “Better” is better than “Best”

We consider two-player normal form games where each player has the same finite strategy set. The payoffs of each player are assumed to be i.i.d. random variables with a continuous distribution. We show that, with high probability, the better-response dynamics converges to pure Nash equilibrium whenever there is one, whereas best-response dynamics fails to converge, as it is trapped.     

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”.     

Probabilities of Pure Nash Equilibria in Matrix Games when the Payoff Entries of One Player Are Randomly Selected

The Nash equilibrium in pure strategies represents an important solution concept in nonzero sum matrix games. Existence of Nash equilibria in games with known and with randomly selected payoff entries have been studied extensively. In many real games, however, a player may know his own payoff entries but not the payoff entries of the other player. In this paper, we consider nonzero sum matrix games where the payoff entries of one player are known, but the payoff entries of the other player are assumed to be randomly selected. We are interested in determining the probabilities of existence of pure Nash equilibria in such games. We characterize these probabilities by first determining the finite space of ordinal matrix games that corresponds to the infinite space of matrix games with random entries for only one player. We then partition this space into mutually exclusive spaces that correspond to games with no Nash equilibria and with r Nash equilibria. In order to effectively compute the sizes of these spaces, we introduce the concept of top-rated preferences minimal ordinal games. We then present a theorem which provides a mechanism for computing the number of games in each of these mutually exclusive spaces, which then can be used to determine the probabilities. Finally, we summarize the results by deriving the probabilities of existence of unique, nonunique, and no Nash equilibria, and we present an illustrative example.     

A note on correlated equilibrium

The set of correlated equilibria for a bimatrix game is a closed, bounded, convex set containing the set of Nash equilibria. We show that every extreme point of a maximal Nash set is an extreme point of the above convex set. We also give an example to show that this result is not true in the payoff space, i.e. there are games where no Nash equilibrium payoff is an extreme point of the set of correlated equilibrium payoffs.     

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.     

Nondominated Nash points: application of biobjective mixed integer programming

We study the connection between biobjective mixed integer linear programming and normal form games with two players. We first investigate computing Nash equilibria of normal form games with two players using single-objective mixed integer linear programming. Then, we define the concept of efficient (Pareto optimal) Nash equilibria. This concept is precisely equivalent to the concept of efficient solutions in multi-objective optimization, where the solutions are Nash equilibria. We prove that the set of all points in the payoff (or objective) space of a normal form game with two players corresponding to the utilities of players in an efficient Nash equilibrium, the so-called nondominated Nash points, is finite. We demonstrate that biobjective mixed integer linear programming, where the utility of each player is an objective function, can be used to compute the set of nondominated Nash points. Finally, we illustrate how the nondominated Nash points can be used to determine the disagreement point of a bargaining problem.     

Separable and low-rank continuous games

In this paper, we study nonzero-sum separable games, which are continuous games whose payoffs take a sum-of-products form. Included in this subclass are all finite games and polynomial games. We investigate the structure of equilibria in separable games. We show that these games admit finitely supported Nash equilibria. Motivated by the bounds on the supports of mixed equilibria in two-player finite games in terms of the ranks of the payoff matrices, we define the notion of the rank of an n-player continuous game and use this to provide bounds on the cardinality of the support of equilibrium strategies. We present a general characterization theorem that states that a continuous game has finite rank if and only if it is separable. Using our rank results, we present an efficient algorithm for computing approximate equilibria of two-player separable games with fixed strategy spaces in time polynomial in the rank of the game. This research was funded in part by National Science Foundation grants DMI-0545910 and ECCS-0621922 and AFOSR MURI subaward 2003-07688-1.     

On solving generalized Nash equilibrium problems via optimization

This paper deals with the generalized Nash equilibrium problem (GNEP), i.e. a noncooperative game in which the strategy set of each player, as well as his payoff function, depends on the strategies of all players. We consider an equivalent optimization reformulation of GNEP using a regularized Nikaido–Isoda function so that solutions of GNEP coincide with global minima of the optimization problem. We then propose a derivative-free descent type method with inexact line search to solve the equivalent optimization problem and we prove that our algorithm is globally convergent. The convergence analysis is not based on conditions guaranteeing that every stationary point of the optimization problem is a solution of GNEP. Finally, we present the performance of our algorithm on some examples.     

Monotone and bounded interval equilibria in a coordination game with information aggregation

We analyze how private learning in a class of games with common stochastic payoffs affects the form of equilibria, and how properties such as player welfare and the extent of strategic miscoordination relate across monotone and non-monotone equilibria. Researchers typically focus on monotone equilibria. We provide conditions under which non-monotone equilibria also exist, where players attempt to coordinate to obtain the stochastic payoff whenever signals are in a bounded interval. In bounded interval equilibria (BIE), an endogenous fear of miscoordination discourages players from coordinating to obtain the stochastic payoff when their signals suggest coordination is most beneficial. In contrast to monotone equilibria, expected payoffs from successful coordination in BIE are lower than the ex-ante expected payoff from ignoring signals and always trying to coordinate to obtain the stochastic payoff. We show that BIE only exist when, absent private information, the game would be a coordination game.     

Pure strategy Nash equilibria and the probabilistic prospects of Stackelberg players

We consider the set of all m×n bimatrix games with ordinal payoffs. We show that on the subset E of such games possessing at least one pure strategy Nash equilibrium, both players prefer the role of leader to that of follower in the corresponding Stackelberg games. This preference is in the sense of first-degree stochastic dominance by leader payoffs of follower payoffs. It follows easily that on the complement of E, the follower’s role is preferred in the same sense. Thus we see a tendency for leadership preference to obtain in the presence of multiple pure strategy Nash equilibria in the underlying game.     

Single-payoff farsighted stable sets in strategic games with dominant punishment strategies

We investigate farsighted stable sets in a class of strategic games with dominant punishment strategies. In this class of games, each player has a strategy that uniformly minimizes the other players’ payoffs for any given strategies chosen by these other players. We particularly investigate a special class of farsighted stable sets, each of which consists of strategy profiles yielding a single payoff vector. We call such a farsighted stable set as a single-payoff farsighted stable set. We propose a concept called an inclusive set that completely characterizes single-payoff farsighted stable sets in strategic games with dominant punishment strategies. We also show that the set of payoff vectors yielded by single-payoff farsighted stable sets is closely related to the strict \(\alpha \)-core in a strategic game. Furthermore, we apply the results to strategic games where each player has two strategies and strategic games associated with some market models.     

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.     

Formulating an <Emphasis Type="Italic">n</Emphasis>-person noncooperative game as a tensor complementarity problem

In this paper, we consider a class of n-person noncooperative games, where the utility function of every player is given by a homogeneous polynomial defined by the payoff tensor of that player, which is a natural extension of the bimatrix game where the utility function of every player is given by a quadratic form defined by the payoff matrix of that player. We will call such a problem the multilinear game. We reformulate the multilinear game as a tensor complementarity problem, a generalization of the linear complementarity problem; and show that finding a Nash equilibrium point of the multilinear game is equivalent to finding a solution of the resulted tensor complementarity problem. Especially, we present an explicit relationship between the solutions of the multilinear game and the tensor complementarity problem, which builds a bridge between these two classes of problems. We also apply a smoothing-type algorithm to solve the resulted tensor complementarity problem and give some preliminary numerical results for solving the multilinear games.     

Bounded rationality, strategy simplification, and equilibrium

It is frequently suggested that predictions made by game theory could be improved by considering computational restrictions when modeling agents. Under the supposition that players in a game may desire to balance maximization of payoff with minimization of strategy complexity, Rubinstein and co-authors studied forms of Nash equilibrium where strategies are maximally simplified in that no strategy can be further simplified without sacrificing payoff. Inspired by this line of work, we introduce a notion of equilibrium whereby strategies are also maximally simplified, but with respect to a simplification procedure that is more careful in that a player will not simplify if the simplification incents other players to deviate. We study such equilibria in two-player machine games in which players choose finite automata that succinctly represent strategies for repeated games; in this context, we present techniques for establishing that an outcome is at equilibrium and present results on the structure of equilibria.     

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