Pure strategy equilibria in symmetric two-player zero-sum games

We observe that a symmetric two-player zero-sum game has a pure strategy equilibrium if and only if it is not a generalized rock-paper-scissors matrix. Moreover, we show that every finite symmetric quasiconcave two-player zero-sum game has a pure equilibrium. Further sufficient conditions for existence are provided. Our findings extend to general two-player zero-sum games using the symmetrization of zero-sum games due to von Neumann. We point out that the class of symmetric two-player zero-sum games coincides with the class of relative payoff games associated with symmetric two-player games. This allows us to derive results on the existence of finite population evolutionary stable 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.     

Minimal and locally minimal games and game forms

By Shapley’s (1964) theorem, a matrix game has a saddle point whenever each of its 2×2 subgames has one. In other words, all minimal saddle point free (SP-free) matrices are of size 2×2. We strengthen this result and show that all locally minimal SP-free matrices also are of size 2×2. In other words, if A is a SP-free matrix in which a saddle point appears after deleting an arbitrary row or column then A is of size 2×2. Furthermore, we generalize this result and characterize the locally minimal Nash equilibrium free (NE-free) bimatrix games.Let us recall that a two-person game form is Nash-solvable if and only if it is tight [V. Gurvich, Solution of positional games in pure strategies, USSR Comput. Math. and Math. Phys. 15 (2) (1975) 74-87]. We show that all (locally) minimal non-tight game forms are of size 2×2. In contrast, it seems difficult to characterize the locally minimal tight game forms (while all minimal ones are just trivial); we only obtain some necessary and some sufficient conditions. We also recall an example from cooperative game theory: a maximal stable effectivity function that is not self-dual and not convex.     

Effectivity functions and simple games

The rather new notion of effectivity function is related to the notion of simple game. Every effectivity function is associated with a simple game. So theory about simple games may be applicable to effectivity functions. E.g. if the effectivity function is additive, then the associated simple game is weighted. Via a characterization of weighted simple games it is possible to characterize maximal additive effectivity functions.Finally we characterize additive effectivity functions and their associated simple games.I thank G.J. Otten for useful comments and stimulating conversations.     

Open Loop Saddle Point on Linear Quadratic Stochastic Differential Games

In this paper, we deal with one kind of two-player zero-sum linear quadratic stochastic differential game problem. We give the existence of an open loop saddle point if and only if the lower and upper values exist.     

Balancedness conditions for exact games

We provide two new characterizations of exact games. First, a game is exact if and only if it is exactly balanced; and second, a game is exact if and only if it is totally balanced and overbalanced. The condition of exact balancedness is identical to the one of balancedness, except that one of the balancing weights may be negative, while for overbalancedness one of the balancing weights is required to be non-positive and no weight is put on the grand coalition. Exact balancedness and overbalancedness are both easy to formulate conditions with a natural game-theoretic interpretation and are shown to be useful in applications. Using exact balancedness we show that exact games are convex for the grand coalition and we provide an alternative proof that the classes of convex and totally exact games coincide. We provide an example of a game that is totally balanced and convex for the grand coalition, but not exact. Finally we relate classes of balanced, totally balanced, convex for the grand coalition, exact, totally exact, and convex games to one another.     

Op en Lo op Saddle Point on Linear Quadratic Sto chastic Differential Games

In this paper, we deal with one kind of two-player zero-sum linear quadratic stochastic differential game problem. We give the existence of an open loop saddle point if and only if the lower and upper values exist.     

Dynamic competition over social networks

We propose an analytical approach to the problem of influence maximization in a social network where two players compete by means of dynamic targeting strategies. We formulate the problem as a two-player zero-sum stochastic game. We prove the existence of the uniform value: if the players are sufficiently patient, both can guarantee the same mean-average opinion without knowing the exact length of the game. Furthermore, we put forward some elements for the characterization of equilibrium strategies. In general, players must implement a trade-off between a forward-looking perspective, according to which they aim to maximize the future spread of their opinion in the network, and a backward-looking perspective, according to which they aim to counteract their opponent’s previous actions. When the influence potential of players is small, we describe an equilibrium through a one-shot game based on eigenvector centrality.     

A game-theoretic formulation of joint implementation of environmental projects

The aim of this paper is to provide a game-theoretic interpretation of joint implementation in environmental projects and to assess the merit of such a strategy. More specifically, we consider a two-player game and solve it under three different cases. In the first case, countries play a non-cooperative game and optimize their welfare under an environmental constraint without having access to joint implementation. In the second case, we assume countries do have access to JI, which allows us to assess its merits by comparing the players’ welfare levels achieved with and without JI. In the last case, the players jointly optimize their welfare under a collective environmental constraint. Comparing welfare levels in this case to those in the second case allows us to assess the merits of cooperation.     

Equilibrium Investment Strategies in Foreign Environmental Projects

This paper proposes a two-player, finite-horizon differential game model to analyze joint implementation in environmental projects, one of the flexible mechanisms considered in the Kyoto Protocol. Using a nonlinear specification for the damage costs, we show that, if joint implementation is available, both players will invest in environmental projects in their own location and one of the players will invest abroad, the identity of that player changing at most once during the planning horizon.Communicated by G. LeitmannResearch supported by FQRSC, Quéebec and NSERC, Canada. The second author’s research was partially supported by MEC under Project SEJ2005-03858 and by JCYL under Project VA045A06, confinanced by FEDER funds.     

Constitutional implementation of social choice correspondences

A game form constitutionally implements a social choice correspondence if it implements it in Nash equilibrium and, moreover, the associated effectivity functions coincide. This paper presents necessary and sufficient conditions for a unanimous social choice correspondence to be constitutionally implementable, and sufficient and almost necessary conditions for an arbitrary (but surjective) social choice correspondence to be constitutionally implementable. It is shown that the results apply to interesting classes of scoring and veto social choice correspondences.     

Min-Max payoffs in a two-player location game

We consider a two-player, sequential location game with arbitrarily distributed consumer demand. Players alternately select locations from a feasible set so as to maximize the consumer mass in their vicinity. Our main result is a complete characterization of feasible market shares, when locations form a finite set in R^d.     

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.     

Representation of finite games as network congestion games

Weighted network congestion games are a natural model for interactions involving finitely many non-identical users of network resources, such as road segments or communication links. However, in spite of their special form, these games are not fundamentally special: every finite game can be represented as a weighted network congestion game. The same is true for the class of (unweighted) network congestion games with player-specific costs, in which the players differ in their cost functions rather than their weights. The intersection of the two classes consists of the unweighted network congestion games. These games are special: a finite game can be represented in this form if and only if it is an exact potential game.     

Fictitious play with incomplete learning

In this paper, we consider a case that a game is played repeatedly in an incomplete learning process where each player updates his belief only in the learning periods rather than all the stages. For fictitious play process with incomplete learning, we discuss the absorbability of Nash equilibriums and the consistency of utilities in a finite game and discuss the convergence in a 2×2 game with an identical learning-period set. The main results for incomplete learning models are that, if it is uniformly played, a strict Nash equilibrium is absorbing in a fictitious play process; a fictitious play has the property of utility consistency if it exhibits infrequent switches and players learn frequently enough; a 2×2 game with an identical learning-period set has fictitious play property that any fictitious process for the game converges to equilibrium provided that players learn frequently enough.     

Necessary and sufficient conditions forl-stability of games in constitutional form

This paper is devoted to the notion of game in constitutional form. For this game, we define three notions of cores: theo-core, thei-core and thej-core. For each core, we give a necessary and sufficient condition for a game to be stable. We finally prove that these theorems generalize Nakamura's theorems for stability of a simple game and Keiding's theorems for stability of an effectivity function.     

On the probability of existence of pure equilibria in matrix games

We examine the probability that a randomly chosen matrix game admits pure equilibria and its behavior as the number of actions of the players or the number of players increases. We show that, for zero-sum games, the probability of having pure equilibria goes to zero as the number of actions goes to infinity, but it goes to a nonzero constant for a two-player game. For many-player games, if the number of players goes to infinity, the probability of existence of pure equilibria goes to zero even if the number of actions does not go to infinity.This research was supported in part by NSF Grant CCR-92-22734.     

Randomized strategy equilibrium in the action commitment game with costs of leading

We investigate a two-player action commitment game where one simultaneous-move and two sequential-move pure strategy equilibria exist when the cost of leading is zero, while the simultaneous-move outcome is not an equilibrium when the leading cost is small positive. We show that this discontinuity disappears if we consider randomized strategy equilibria. We investigate a price competition model and show that randomized strategy equilibria exist and any of them converges to the Bertrand equilibrium when the leading cost converges to zero.     

Equilibrium in a war of attrition with an option to fight decisively

We develop a symmetric incomplete-information continuous-time two-player war-of-attrition game with an option to fight decisively. We show that there exists an essentially unique symmetric Bayesian Nash equilibrium. Under equilibrium, the game does not end immediately, and a costly delay persists even with the availability of the fighting option that ends the game if chosen. In addition, there exists a critical time in which a fight occurs unless a player resigns before that time.