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.     

A Shared-Constraint Approach to Multi-Leader Multi-Follower Games

Multi-leader multi-follower games are a class of hierarchical games in which a collection of leaders compete in a Nash game constrained by the equilibrium conditions of another Nash game amongst the followers. The resulting equilibrium problem with equilibrium constraints is complicated by nonconvex agent problems and therefore providing tractable conditions for existence of global or even local equilibria has proved challenging. Consequently, much of the extant research on this topic is either model specific or relies on weaker notions of equilibria. We consider a modified formulation in which every leader is cognizant of the equilibrium constraints of all leaders. Equilibria of this modified game contain the equilibria, if any, of the original game. The new formulation has a constraint structure called shared constraints, and our main result shows that if the leader objectives admit a potential function, the global minimizers of the potential function over this shared constraint are equilibria of the modified formulation. We provide another existence result using fixed point theory that does not require potentiality. Additionally, local minima, B-stationary, and strong-stationary points of this minimization problem are shown to be local Nash equilibria, Nash B-stationary, and Nash strong-stationary points of the corresponding multi-leader multi-follower game. We demonstrate the relationship between variational equilibria associated with this modified shared-constraint game and equilibria of the original game from the standpoint of the multiplier sets and show how equilibria of the original formulation may be recovered. We note through several examples that such potential multi-leader multi-follower games capture a breadth of application problems of interest and demonstrate our findings on a multi-leader multi-follower Cournot game.     

Generalized correlated equilibrium for two-person games in extensive form with perfect information

A correlation scheme (leading to a special equilibrium called “soft” correlated equilibrium) is applied for two-person finite games in extensive form with perfect information. Randomization by an umpire takes place over the leaves of the game tree. At every decision point players have the choice either to follow the recommendation of the umpire blindly or freely choose any other action except the one suggested. This scheme can lead to Pareto-improved outcomes of other correlated equilibria. Computational issues of maximizing a linear function over the set of soft correlated equilibria are considered and a linear-time algorithm in terms of the number of edges in the game tree is given for a special procedure called “subgame perfect optimization”.     

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

A procedure for finding Nash equilibria in bi-matrix games

In this paper we consider the computation of Nash equilibria for noncooperative bi-matrix games. The standard method for finding a Nash equilibrium in such a game is the Lemke-Howson method. That method operates by solving a related linear complementarity problem (LCP). However, the method may fail to reach certain equilibria because it can only start from a limited number of strategy vectors. The method we propose here finds an equilibrium by solving a related stationary point problem (SPP). Contrary to the Lemke-Howson method it can start from almost any strategy vector. Besides, the path of vectors along which the equilibrium is reached has an appealing game-theoretic interpretation. An important feature of the algorithm is that it finds a perfect equilibrium when at the start all actions are played with positive probability. Furthermore, we can in principle find all Nash equilibria by repeated application of the algorithm starting from different strategy vectors.This author is financially supported by the Co-operation Centre Tilburg and Eindhoven Universities, The Netherlands.     

Monitoring cooperative equilibria in a stochastic differential game

This paper deals with a class of equilibria which are based on the use of memory strategies in the context of continuous-time stochastic differential games. In order to get interpretable results, we will focus the study on a stochastic differential game model of the exploitation of one species of fish by two competing fisheries. We explore the possibility of defining a so-called cooperative equilibrium, which will implement a fishing agreement. In order to obtain that equilibrium, one defines a monitoring variable and an associated retaliation scheme. Depending on the value of the monitoring variable, which provides some evidence of a deviation from the agreement, the probability increases that the mode of a game will change from a cooperative to a punitive one. Both the monitoring variable and the parameters of this jump process are design elements of the cooperative equilibrium. A cooperative equilibrium designed in this way is a solution concept for a switching diffusion game. We solve that game using the sufficient conditions for a feedback equilibrium which are given by a set of coupled HJB equations. A numerical analysis, approximating the solution of the HJB equations through an associated Markov game, enables us to show that there exist cooperative equilibria which dominate the classical feedback Nash equilibrium of the original diffusion game model.This research was supported by FNRS-Switzerland, NSERC-Canada, FCAR-Quebec.     

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.     

Cheap play with no regret

This paper studies a special class of differential information games with pre-play communication —games with “cheap play”. We consider problems in which there are several rounds of payoff-irrelevant publicly observable choice (or discussion) of actions, followed by a final round in which actions are binding and payoff relevant. A natural focal subset of equilibria of such games in one that consists of equilibria involvingno regret. Such games were first studied by Green and Laffont (1987), where a criterion calledposterior implementability is introduced with the intention of identifying regret-free equilibria in games with cheap play. This is simply a restriction on the Bayesian equilibrium of the underlying one-shot game. If indeed such a restriction does characterize regret-freeness, then the analytics of such situations would be enormously simplified since one can ignore the messy extended-form of the cheap play game; merely examining the one-shot game is sufficient. We argue that regret-freeness of an equilibrium has a subtle distinction: regret-freeness in moves and regret-freeness in assessments. We show that the former causes the extended-form to be irrelevant; posterior implementability completely characterizes equilibria with regret-freeness in moves. The latter, on the other hand, does not yield a similar principle: the extended-form cannot be ignored.     

Finding all pure strategy Nash equilibria in a planar location game

In this paper, we deal with a planar location-price game where firms first select their locations and then set delivered prices in order to maximize their profits. If firms set the equilibrium prices in the second stage, the game is reduced to a location game for which pure strategy Nash equilibria are studied assuming that the marginal delivered cost is proportional to the distance between the customer and the facility from which it is served. We present characterizations of local and global Nash equilibria. Then an algorithm is shown in order to find all possible Nash equilibrium pairs of locations. The minimization of the social cost leads to a Nash equilibrium. An example shows that there may exist multiple Nash equilibria which are not minimizers of the social cost.     

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.     

Coalition-proof equilibria in a voluntary participation game

We examine the coalition-proof equilibria of a participation game in the provision of a (pure) public good. We study which Nash equilibria are achieved through cooperation, and we investigate coalition-proof equilibria under strict and weak domination. We show that under some incentive condition, (i) a profile of strategies is a coalition-proof equilibrium under strict domination if and only if it is a Nash equilibrium that is not strictly Pareto-dominated by any other Nash equilibrium and (ii) every strict Nash equilibrium for non-participants is a coalition-proof equilibrium under weak domination.     

Discounted and finitely repeated minority games with public signals

We consider a repeated game where at each stage players simultaneously choose one of the two rooms. The players who choose the less crowded room are rewarded with one euro. The players in the same room do not recognize each other, and between the stages only the current majority room is publicly announced, hence the game has imperfect public monitoring. An undiscounted version of this game was considered by Renault et al. [Renault, J., Scarlatti, S., Scarsini, M., 2005. A folk theorem for minority games. Games Econom. Behav. 53 (2), 208–230], who proved a folk theorem. Here we consider a discounted version and a finitely repeated version of the game, and we strengthen our previous result by showing that the set of equilibrium payoffs Hausdorff-converges to the feasible set as either the discount factor goes to one or the number of repetition goes to infinity. We show that the set of public equilibria for this game is strictly smaller than the set of private equilibria.     

A Bayesian Game without ∈-equilibria

We present a three-player Bayesian game for which there are no ∈-equilibria in Borel measurable strategies for small enough positive ∈, however there are non-measurable equilibria. The structure of the game employs a nonamenable semi-group action corresponding to the knowledge of the players. The equilibrium property is related to the proper colouring of graphs and the Borel chromatic number; but rather than keeping adjacent vertices coloured differently there are algebraic conditions relating to the topology of the space and some ergodic operators.     

Unit-sphere games

This paper introduces a class of games, called unit-sphere games, in which strategies are real vectors with unit 2-norms (or, on a unit-sphere). As a result, they should no longer be interpreted as probability distributions over actions, but rather be thought of as allocations of one unit of resource to actions and the payoff effect on each action is proportional to the square root of the amount of resource allocated to that action. The new definition generates a number of interesting consequences. We first characterize the sufficient and necessary condition under which a two-player unit-sphere game has a Nash equilibrium. The characterization reduces solving a unit-sphere game to finding all eigenvalues and eigenvectors of the product matrix of individual payoff matrices. For any unit-sphere game with non-negative payoff matrices, there always exists a unique Nash equilibrium; furthermore, the unique equilibrium is efficiently reachable via Cournot adjustment. In addition, we show that any equilibrium in positive unit-sphere games corresponds to approximate equilibria in the corresponding normal-form games. Analogous but weaker results are obtained in n-player unit-sphere games.     

Algorithms for generalized potential games with mixed-integer variables

We consider generalized potential games, that constitute a fundamental subclass of generalized Nash equilibrium problems. We propose different methods to compute solutions of generalized potential games with mixed-integer variables, i.e., games in which some variables are continuous while the others are discrete. We investigate which types of equilibria of the game can be computed by minimizing a potential function over the common feasible set. In particular, for a wide class of generalized potential games, we characterize those equilibria that can be computed by minimizing potential functions as Pareto solutions of a particular multi-objective problem, and we show how different potential functions can be used to select equilibria. We propose a new Gauss–Southwell algorithm to compute approximate equilibria of any generalized potential game with mixed-integer variables. We show that this method converges in a finite number of steps and we also give an upper bound on this number of steps. Moreover, we make a thorough analysis on the behaviour of approximate equilibria with respect to exact ones. Finally, we make many numerical experiments to show the viability of the proposed approaches.     

The multiple-partners assignment game with heterogeneous sales and multi-unit demands: competitive equilibria

A multiple-partners assignment game with heterogeneous sales and multi-unit demands consists of a set of sellers that own a given number of indivisible units of potentially many different goods and a set of buyers who value those units and want to buy at most an exogenously fixed number of units. We define a competitive equilibrium for this generalized assignment game and prove its existence by using only linear programming. In particular, we show how to compute equilibrium price vectors from the solutions of the dual linear program associated to the primal linear program defined to find optimal assignments. Using only linear programming tools, we also show (i) that the set of competitive equilibria (pairs of price vectors and assignments) has a Cartesian product structure: each equilibrium price vector is part of a competitive equilibrium with all optimal assignments, and vice versa; (ii) that the set of (restricted) equilibrium price vectors has a natural lattice structure; and (iii) how this structure is translated into the set of agents?? utilities that are attainable at equilibrium.     

A note on the strategic adoption of a new technology

This note reports an application of two-person, nonzero-sum game theory to a problem in the economics of technology adoption. It extends the analysis of a previous paper to consider differentiable mixed-strategy equilibria. In this case, the mixed-strategy equilibrium has a natural interpretation as a pure strategy equilibrium in an appropriately defined differential game.     

Adjustment patterns and equilibrium selection in experimental signaling games

This paper examines the relation between adjustment patterns and equilibrium selection in laboratory experiments with two types of simple signaling games. One type of game has two Nash equilibria, of which only one is sequential. The other type has two sequential equilibria, only one of them satisfying equilibrium dominance. For each type of game, the results show that variations in the payoff structure, which do not change the equilibrium configuration, generate different adjustment patterns. As a consequence, the less refined equilibrium is more frequently observed for some payoff structures, while the more refined equilibrium is more frequently observed in others.     

A predator–prey–disease model with immune response in infected prey

In this paper, a predator–prey–disease model with immune response in the infected prey is formulated. The basic reproduction number of the within-host model is defined and it is found that there are three equilibria: extinction equilibrium, infection-free equilibrium and infection-persistent equilibrium. The stabilities of these equilibria are completely determined by the reproduction number of the within-host model. Furthermore, we define a basic reproduction number of the between-host model and two predator invasion numbers: predator invasion number in the absence of disease and predator invasion number in the presence of disease. We have predator and infection-free equilibrium, infection-free equilibrium, predator-free equilibrium and a co-existence equilibrium. We determine the local stabilities of these equilibria with conditions on the reproduction and invasion reproduction numbers. Finally, we show that the predator-free equilibrium is globally stable.