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.     

Definition and properties of cooperative equilibria in a two-player game of infinite duration

A two-player multistage game, with an infinite number of stages is considered. The concepts of overtaking and weakly overtaking payoff sequences are introduced. The class of strategies considered consists of memory strategies, which are based on the past history of the control and the initial state from where the game has been played. Weak equilibria are defined in this class of strategies. It is then shown how such equilibria can be constructed by composing into a trigger strategy a nominal cooperative control sequence and two threat strategies representing the announced retaliation by each player in the case where the other player does not play according to the nominal control. When the threats consists of a feedback equilibrium pair, the resulting cooperative equilibrium is perfect. Another result shows that, if each player can use a most effective threat based on a saddle-point feedback strategy, then any weak equilibrium in the class of memory strategies is in some sense related to this particular kind of equilibrium in the class of trigger strategies.Dedicated to G. LeitmannThis research was supported by SSHRC Grant No. 410-81-0722 and FCAC Grant No. EQ-428 to the first author. This research has also been made possible by a financial support from the University of Puerto Rico.     

Games of stopping with infinite horizon

We consider two-person zero-sum games of stopping: two players sequentially observe a stochastic process with infinite time horizon. Player I selects a stopping time and player II picks the distribution of the process. The pay-off is given by the expected value of the stopped process. Results of Irle (1990) on existence of value and equivalence of randomization for such games with finite time horizon, where the set of strategies for player II is dominated in the measure-theoretical sense, are extended to the infinite time case. Furthermore we treat such games when the set of strategies for player II is not dominated. A counterexample shows that even in the finite time case such games may not have a value. Then a sufficient condition for the existence of value is given which applies to prophet-type games.     

Common-value all-pay auctions with asymmetric information

We study two-player common-value all-pay auctions in which the players have ex-ante asymmetric information represented by finite connected partitions of the set of states of nature. Our focus is on a family of such auctions in which no player has an information advantage over his opponent. We find sufficient conditions for the existence of equilibrium with monotone strategies, and show that such an equilibrium is unique. We further show that the ex-ante distribution of equilibrium effort is the same for every player (and hence the players’ expected efforts are equal), although their expected payoffs are different and they do not have the same ex-ante probability of winning.     

Uncoupled automata and pure Nash equilibria

We study the problem of reaching a pure Nash equilibrium in multi-person games that are repeatedly played, under the assumption of uncoupledness: EVERY player knows only his own payoff function. We consider strategies that can be implemented by finite-state automata, and characterize the minimal number of states needed in order to guarantee that a pure Nash equilibrium is reached in every game where such an equilibrium exists.     

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.     

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.     

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.     

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.     

Stay-in-a-set games

There exists a Nash equilibrium (ε-Nash equilibrium) for every n-person stochastic game with a finite (countable) state space and finite action sets for the players if the payoff to each player i is one when the process of states remains in a given set of states G _i and is zero otherwise. Received: December 2000     

Learning of winning strategies for terminal games with linear-size memory

We prove that if one or more players in a locally finite positional game have winning strategies, then they can find it by themselves, not losing more than a bounded number of plays and not using more than a linear-size memory, independently of the strategies applied by the other players. We design two algorithms for learning how to win. One of them can also be modified to determine a strategy that achieves a draw, provided that no winning strategy exists for the player in question but with properly chosen moves a draw can be ensured from the starting position. If a drawing- or winning strategy exists, then it is learnt after no more than a linear number of plays lost (linear in the number of edges of the game graph). Z. Tuza’s research has been supported in part by the grant OTKA T-049613.     

Player splitting in extensive form games

By a player splitting we mean a mechanism that distributes the information sets of a player among so-called agents. A player splitting is called independent if each path in the game tree contains at most one agent of every player. Following Mertens (1989), a solution is said to have the player splitting property if, roughly speaking, the solution of an extensive form game does not change by applying independent player splittings. We show that Nash equilibria, perfect equilibria, Kohlberg-Mertens stable sets and Mertens stable sets have the player splitting property. An example is given to show that the proper equilibrium concept does not satisfy the player splitting property. Next, we give a definition of invariance under (general) player splittings which is an extension of the player splitting property to the situation where we also allow for dependent player splittings. We come to the conclusion that, for any given dependent player splitting, each of the above solutions is not invariant under this player splitting. The results are used to give several characterizations of the class of independent player splittings and the class of single appearance structures by means of invariance of solution concepts under player splittings. Received: December 1996/Revised Version: January 2000     

A combinatorial proof of a fixed point property

A class of finite simplicial complexes, called pseudo cones, is developed that has a number of useful combinatorial properties. A partially ordered set is a pseudo cone if its order complex is a pseudo cone. Pseudo cones can be constructed from other pseudo cones in a number of ways. Pseudo cone ordered sets include finite dismantlable ordered sets and finite truncated noncomplemented lattices. The main result of the paper is a combinatorial proof of the fixed simplex property for finite pseudo cones in which a combinatorial structure is constructed that relates fixed simplices to one another. This gives combinatorial proofs of some well known non-constructive results in the fixed point theory of finite partially ordered sets.     

Congestion games with failures

We introduce a new class of games, congestion games with failures (CGFs), which allows for resource failures in congestion games. In a CGF, players share a common set of resources (service providers), where each service provider (SP) may fail with some known probability (that may be constant or depend on the congestion on the resource). For reliability reasons, a player may choose a subset of the SPs in order to try and perform his task. The cost of a player for utilizing any SP is a function of the total number of players using this SP. A main feature of this setting is that the cost for a player for successful completion of his task is the minimum of the costs of his successful attempts. We show that although CGFs do not, in general, admit a (generalized ordinal) potential function and the finite improvement property (and thus are not isomorphic to congestion games), they always possess a pure strategy Nash equilibrium. Moreover, every best reply dynamics converges to an equilibrium in any given CGF, and the SPs’ congestion experienced in different equilibria is (almost) unique. Furthermore, we provide an efficient procedure for computing a pure strategy equilibrium in CGFs and show that every best equilibrium (one minimizing the sum of the players’ disutilities) is semi-strong. Finally, for the subclass of symmetric CGFs we give a constructive characterization of best and worst equilibria.     

Finding all solutions of affine generalized Nash equilibrium problems with one-dimensional strategy sets

We consider a class of generalized Nash equilibrium problems with quadratic cost functions and common linear constraints for all players. Further we focus on the case where every player has a single strategy variable within a bounded set. For this problem class we present an algorithm that is able to compute all solutions and that terminates finitely. Our method is based on a representation of the solution set as a finite union of polyhedral sets using sign conditions for the derivatives of the cost and constraint functions. The effectiveness of the algorithm is shown in various examples from literature.     

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.     

A Game Related to the Number of Hides Game

In this paper, we study a discrete search game on an array of N ordered cells, with two players having opposite goals: player I (searcher) and player II (hider). Player II has to hide q objects at consecutive cells and player I can search p consecutive cells. The payoff to player I is the number of objects found by him. In some situations, the players need to adopt sophisticated strategies if they are to act optimally.     

On equilibria in finite games

We are concerned with Nash equilibrium points forn-person games. It is proved that, given any real algebraic numberα, there exists a 3-person game with rational data which has a unique equilibrium point andα is the equilibrium payoff for some player. We also present a method which allows us to reduce an arbitraryn-person game to a 3-person one, so that a number of questions about generaln-person games can be reduced to consideration of the special 3-person case. Finally, a completely mixed game, where the equilibrium set is a manifold of dimension one, is constructed.     

A unifying model for matrix-based pairing situations

We present a unifying framework for transferable utility coalitional games that are derived from a non-negative matrix in which every entry represents the value obtained by combining the corresponding row and column. We assume that every row and every column is associated with a player, and that every player is associated with at most one row and at most one column. The instances arising from this framework are called pairing games, and they encompass assignment games and permutation games as two polar cases. We show that the core of a pairing game is always non-empty by proving that the set of pairing games coincides with the set of permutation games. Then we exploit the wide range of situations comprised in our framework to investigate the relationship between pairing games that have different player sets, but are defined by the same underlying matrix. We show that the core and the set of extreme core allocations are immune to the merging of a row player with a column player. Moreover, the core is also immune to the reverse manipulation, i.e., to the splitting of a player into a row player and a column player. Other common solution concepts fail to be either merging-proof or splitting-proof in general.