Correlated equilibria in some classes of two-person games

A correlated equilibrium in a two-person game is “good” if for everyNash equilibrium there is a player who prefers the correlated equilibrium to theNash equilibrium. If a game is “best-response equivalent” to a two-person zero-sum game, then it has no good correlated equilibria. But games which are “almost strictly competitive” or “order equivalent” to a two-person zero-sum game may have good correlated equilibria.     

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.     

Perturbation theory for games in normal form and stochastic games

In this paper, the effect on values and optimal strategies of perturbations of game parameters (payoff function, transition probability function, and discount factor) is studied for the class of zero-sum games in normal form and for the class of stationary, discounted, two-person, zero-sum stochastic games.A main result is that, under certain conditions, the value depends on these parameters in a pointwise Lipschitz continuous way and that the sets of -optimal strategies for both players are upper semicontinuous multifunctions of the game parameters.Extensions to general-sum games and nonstationary stochastic games are also indicated.     

Numerical solution of special matrix games

A method is proposed for solving large-sized matrix games (zero-sum games) of special form for which there is a fast algorithm of searching for the best pure strategy of a player given any mixed strategy of the opponent. Examples of problems leading to such games are given. The method proposed is numerically compared with the Brown-Robinson iterative method.     

Discrete Colonel Blotto and General Lotto games

A class of integer-valued allocation games—“General Lotto games”—is introduced and solved. The results are then applied to analyze the classical discrete “Colonel Blotto games”; in particular, optimal strategies are obtained for all symmetric Colonel Blotto games.     

Stationary,completely mixed and symmetric optimal and equilibrium strategies in stochastic games

In this paper, we address various types of two-person stochastic games—both zero-sum and nonzero-sum, discounted and undiscounted. In particular, we address different aspects of stochastic games, namely: (1) When is a two-person stochastic game completely mixed? (2) Can we identify classes of undiscounted zero-sum stochastic games that have stationary optimal strategies? (3) When does a two-person stochastic game possess symmetric optimal/equilibrium strategies? Firstly, we provide some necessary and some sufficient conditions under which certain classes of discounted and undiscounted stochastic games are completely mixed. In particular, we show that, if a discounted zero-sum switching control stochastic game with symmetric payoff matrices has a completely mixed stationary optimal strategy, then the stochastic game is completely mixed if and only if the matrix games restricted to states are all completely mixed. Secondly, we identify certain classes of undiscounted zero-sum stochastic games that have stationary optima under specific conditions for individual payoff matrices and transition probabilities. Thirdly, we provide sufficient conditions for discounted as well as certain classes of undiscounted stochastic games to have symmetric optimal/equilibrium strategies—namely, transitions are symmetric and the payoff matrices of one player are the transpose of those of the other. We also provide a sufficient condition for the stochastic game to have a symmetric pure strategy equilibrium. We also provide examples to show the sharpness of our results.     

Non-cooperative monopolistic games and monopolistic market games

A class of non-cooperative games is discussed in which one player (“the monopolist”) by choosing his strategy restricts the other players to subsets of their strategy sets. Examples of such games in various fields are given. In particular it is shown that some very important economic situations fall within this class of games. A solution concept is defined and sufficient conditions for its existence are derived. The question of the advantages a player derives from being a monopolist is raised and conditions are derived for him to benefit from being a monopolist.     

Infinitely repeated games of incomplete information: Symmetric case with random signals

We consider infinitely repeated two-person zero-sum games of incomplete information in which the signals are the same for both players and consist of probability distributions on a given alphabet. We show that such games have a value.     

Two-person zero-sum stochastic games

Two-person zero-sum stochastic games with finite state and action spaces are considered. The expected average payoff criterion is introduced. In the special case of single controller games it is shown that the optimal stationary policies and the value of the game can be obtained from the optimal solutions to a pair of dual programs. For multichain structures, a decomposition algorithm is given which produces such optimal stationary policies for both players. In the case of both players controlling the transitions, a generalized game is obtained, the solution of which gives the optimal policies.     

Mixed strategy solutions for quadratic games

Mixed strategy solutions are given for two-person, zero-sum games with payoff functions consisting of quadratic, bilinear, and linear terms, and strategy spaces consisting of closed balls in a Hilbert space. The results are applied to linear-quadratic differential games with no information, and with quadratic integral constraints on the control functions.     

Take-and-guess games

This paper studies two classes of two-person zero-sum games in which the strategies of both players are of a special type. Each strategy can be split into two parts, a taking and a guessing part. In these games two types of asymmetry between the players can occur. In the first place, the number of objects available for taking does not need to be the same for both players. In the second place, the players can be guessing sequentially instead of simultaneously; the result is asymmetric information. The paper studies the value and equilibria of these games, for all possible numbers of objects available to the players, for the case with simultaneous guessing as well as for the variant with sequential guessing.      

Reduction of Silverman-like games to games on bounded sets

A two person zero sum game is regarded as Silverman-like if the strategy sets are sets of real numbers bounded below, the payoff function is bounded, the maximum payoff is achieved whenever the second player's numbery exceeds the first player's numberx by “too much”, and the minimum is achieved wheneverx exceedsy by “too much”. Explicit upper bounds are obtained for pure strategies to be included in an optimal mixed strategy in such games. In particular, if the strategy sets are discrete, the games may be reduced to games on specified finite sets.     

Global games

Global games are real-valued functions defined on partitions (rather than subsets) of the set of players. They capture “public good” aspects of cooperation, i.e., situations where the payoff is naturally defined for all players (“the globe”) together, as is the case with issues of environmental clean-up, medical research, and so forth. We analyze the more general concept of lattice functions and apply it to partition functions, set functions and the interrelation between the two. We then use this analysis to define and characterize the Shapley value and the core of global games.     

An operator solution of stochastic games

A class of zero-sum, two-person stochastic games is shown to have a value which can be calculated by transfinite iteration of an operator. The games considered have a countable state space, finite action spaces for each player, and a payoff sufficiently general to include classical stochastic games as well as Blackwell’s infiniteG _δ games of imperfect information. Research supported by National Science Foundation Grants DMS-8801085 and DMS-8911548.     

Characterizing properties of the value function of stochastic games

In the present note, the axiomatic characterization of the value function of two-person, zero-sum games in normal form by Vilkas and Tijs is extended to the value function of discounted, two-person, zero-sum stochastic games. The characterizing axioms can be indicated by the following terms: objectivity, monotony, and sufficiency for both players; or sufficiency for one of the players and symmetry. Also, a characterization without using the monotony axiom is given.     

Strategy-indifferent games of best choice

The game of best choice (or “secretary problem”) is a model for making an irrevocable decision among a fixed number of candidate choices that are presented sequentially in random order, one at a time. Because the classically optimal solution is known to reject an initial sequence of candidates, a paradox emerges from the fact that candidates have an incentive to position themselves immediately after this cutoff which challenges the assumption that candidates arrive in uniformly random order.One way to resolve this is to consider games for which every (reasonable) strategy results in the same probability of success. In this work, we classify these “strategy-indifferent” games of best choice. It turns out that the probability of winning such a game is essentially the reciprocal of the expected number of left-to-right maxima in the full collection of candidate rank orderings. We present some examples of these games based on avoiding permutation patterns of size 3, which involves computing the distribution of left-to-right maxima in each of these pattern classes.     

Sufficient conditions for optimality in two-person zero-sum differential games with state and strategy constraints

A sufficiency theorem for optimal feedback strategies in two-person zero-sum differential games is given. The theorem is applicable to a wide class of such games for which strategies are Borel measurable functions on a subset of the state space. The theorem generalizes those of [1, 2, and 5].