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.     

Some interesting properties of maximin strategies

Since the seminal paper of Nash (1950) game theoretic literature has focused mostly on equilibrium and not on maximin (minimax) strategies. We study the properties of these strategies in non-zero-sum strategic games that possess (completely) mixed Nash equilibria. We find that under certain conditions maximin strategies have several interesting properties, some of which extend beyond 2-person strategic games. In particular, for n-person games we specify necessary and sufficient conditions for maximin strategies to yield the same expected payoffs as Nash equilibrium strategies. We also show how maximin strategies may facilitate payoff comparison across Nash equilibria as well as refine some Nash equilibrium strategies.     

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.     

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

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

Conditional Markov equilibria in discounted dynamic games

This paper introduces conditional Markov strategies in discrete-time discounted dynamic games with perfect monitoring. These are strategies in which players follow Markov policies after all histories. Policies induced by conditional Markov equilibria can be supported with the threat of reverting to the policy that yields the smallest expected equilibrium payoff for the deviator. This leads to a set-valued fixed-point characterization of equilibrium payoff functions. The result can be used for the computation of equilibria and for showing the existence in behavior strategies.     

On the existence of almost-pure-strategy Nash equilibrium in <Emphasis Type="Italic">n</Emphasis>-person finite games

This paper gives wide characterization of n-person non-coalitional games with finite players’ strategy spaces and payoff functions having some concavity or convexity properties. The characterization is done in terms of the existence of two-point-strategy Nash equilibria, that is equilibria consisting only of mixed strategies with supports being one or two-point sets of players’ pure strategy spaces. The structure of such simple equilibria is discussed in different cases. The results obtained in the paper can be seen as a discrete counterpart of Glicksberg’s theorem and other known results about the existence of pure (or “almost pure”) Nash equilibria in continuous concave (convex) games with compact convex spaces of players’ pure strategies.     

Existence of pure Nash equilibria in discontinuous and non quasiconcave games

In a recent but well known paper, Reny has proved the existence of Nash equilibria for compact and quasiconcave games, with possibly discontinuous payoff functions. In this paper, we prove that the quasiconcavity assumption in Reny’s theorem can be weakened: we introduce a measure allowing to localize the lack of quasiconcavity, which allows to refine the analysis of equilibrium existence (I wish to thank P. J. Reny, two anonymous referees and the associated editor for corrections, suggestions and remarks which led to improvements in the paper).     

Finitely additive and epsilon Nash equilibria

We prove the existence of a mixed strategy Nash equilibrium in normal form games when the space of mixed strategies consists of finitely additive probability measures. It is then proved that from this result an existence result for epsilon equilibria with countably additive mixed strategies can be obtained. These results are applied to the classic Cournot game.     

大博弈中Nash均衡的存在性

研究了具有任意多个局中人的非合作博弈(大博弈)中Nash均衡的存在性.将1969年Ma的截口定理推广得到新的截口定理.用这个新的截口定理进一步证明了:1)大博弈中Nash均衡的存在性;2)纯策略集为紧度量空间而且支付函数为连续函数时,连续大博弈中混合策略Nash均衡的存在性.并且存在性定理推出了2010年Salonen的结果,即此研究结果较Salonen的结论更具普遍意义.     

Structure of extreme correlated equilibria: a zero-sum example and its implications

We exhibit the rich structure of the set of correlated equilibria by analyzing the simplest of polynomial games: the mixed extension of matching pennies. We show that while the correlated equilibrium set is convex and compact, the structure of its extreme points can be quite complicated. In finite games the ratio of extreme correlated to extreme Nash equilibria can be greater than exponential in the size of the strategy spaces. In polynomial games there can exist extreme correlated equilibria which are not finitely supported; we construct a large family of examples using techniques from ergodic theory. We show that in general the set of correlated equilibrium distributions of a polynomial game cannot be described by conditions on finitely many moments (means, covariances, etc.), in marked contrast to the set of Nash equilibria which is always expressible in terms of finitely many moments.     

Sensitive equilibria for ergodic stochastic games with countable state spaces

We consider stochastic games with countable state spaces and unbounded immediate payoff functions. Our assumptions on the transition structure of the game are based on a recent work by Meyn and Tweedie [19] on computable bounds for geometric convergence rates of Markov chains. The main results in this paper concern the existence of sensitive optimal strategies in some classes of zero-sum stochastic games. By sensitive optimality we mean overtaking or 1-optimality. We also provide a new Nash equilibrium theorem for a class of ergodic nonzero-sum stochastic games with denumerable state spaces.     

Paréto equilibria in multicriteria metagames

Summary In this paper we study the existence of Paréto equilibria of a multicriteria metagame. A theorem on existence of a Paréto equilibrium and a theorem on existence of a Nash equilibrium with weights are presented, which improve and extend some known results in the theory of games with multiple payoffs. Also relations between a Paréto equilibrium and other solution concepts of an optimization problem with multiple criteria are discussed. Partially supported by NSFC, NSFIMTF and MADIS. The authors are grateful to the referee's valuable comments and suggestions.     

Characterization of optimal strategies in matrix games with convexity properties

This paper gives a full characterization of matrices with rows and columns having properties closely related to the (quasi-) convexity-concavity of functions. The matrix games described by such payoff matrices well approximate continuous games on the unit square with payoff functions F (x, y) concave in x for each y, and convex in y for each x. It is shown that the optimal strategies in such matrix games have a very simple structure and a search-procedure is given. The results have a very close relationship with the known theorem of Debreu and Glicksberg about the existence of a pure Nash equilibrium in n-person games. Received: May 1997/Final version: August 1999     

On the existence of Nash equilibria in large games

We study the existence of Nash equilibria in games with an infinite number of players. We show that there exists a Nash equilibrium in mixed strategies in all normal form games such that pure strategy sets are compact metric spaces and utility functions are continuous. The player set can be any nonempty set.     

On stochastic games in economics

In this paper we show that many results on equilibria in stochastic games arising from economic theory can be deduced from the theorem on the existence of a correlated equilibrium due to Nowak and Raghavan. Some new classes of nonzero-sum Borel state space discounted stochastic games having stationary Nash equilibria are also presented. Three nontrivial examples of dynamic stochastic games arising from economic theory are given closed form solutions. Research partially supported by MNSW grant 1 P03A 01030.     

The Folk theorem for dominance solutions

The known variants of the Folk theorem characterize the sets of equilibria for repeated games. The present paper considers dominance solutions of finitely repeated games and discounted supergames with perturbed payoff functions. The paper shows that for a normal form game the set of dominance solution payoff vectors of the T-fold repetitions converges to the set of feasible and individually rational payoffs as T tends to infinity and the perturbation value tends to 0. A similar theorem is proved for supergames as the discount factor tends to 1. Received: May 1994/final version: September 1997     

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.     

Robust game theory

We present a distribution-free model of incomplete-information games, both with and without private information, in which the players use a robust optimization approach to contend with payoff uncertainty. Our ``robust game' model relaxes the assumptions of Harsanyi's Bayesian game model, and provides an alternative distribution-free equilibrium concept, which we call ``robust-optimization equilibrium,' to that of the ex post equilibrium. We prove that the robust-optimization equilibria of an incomplete-information game subsume the ex post equilibria of the game and are, unlike the latter, guaranteed to exist when the game is finite and has bounded payoff uncertainty set. For arbitrary robust finite games with bounded polyhedral payoff uncertainty sets, we show that we can compute a robust-optimization equilibrium by methods analogous to those for identifying a Nash equilibrium of a finite game with complete information. In addition, we present computational results. The research of the author was partially supported by a National Science Foundation Graduate Research Fellowship and by the Singapore-MIT Alliance. The research of the author was partially supported by the Singapore-MIT Alliance.     

Split equilibrium problems for related games and applications to economic theory

ABSTRACT

In this paper we introduce the concept of split Nash equilibrium problems associated with two related noncooperative strategic games. Then we apply the Fan-KKM theorem to prove the existence of solutions to split Nash equilibrium problems of related noncooperative strategic games, in which the strategy sets of the players are nonempty closed and convex subsets in Banach spaces. As an application of this existence to economics, an example is provided that studies the existence of split Nash equilibrium of utilities of two related economies. As applications, we study the existence of split Nash equilibrium in the dual (playing twice) extended Bertrand duopoly model of price competition.     

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.