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.     

Stochastic games with non-observable actions

We examine n-player stochastic games. These are dynamic games where a play evolves in stages along a finite set of states; at each stage players independently have to choose actions in the present state and these choices determine a stage payoff to each player as well as a transition to a new state where actions have to be chosen at the next stage. For each player the infinite sequence of his stage payoffs is evaluated by taking the limiting average. Normally stochastic games are examined under the condition of full monitoring, i.e. at any stage each player observes the present state and the actions chosen by all players. This paper is a first attempt towards understanding under what circumstances equilibria could exist in n-player stochastic games without full monitoring. We demonstrate the non-existence of -equilibria in n-player stochastic games, with respect to the average reward, when at each stage each player is able to observe the present state, his own action, his own payoff, and the payoffs of the other players, but is unable to observe the actions of them. For this purpose, we present and examine a counterexample with 3 players. If we further drop the assumption that the players can observe the payoffs of the others, then counterexamples already exist in games with only 2 players.     

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.     

Fictitious play in coordination games

We study the Fictitious Play process with bounded and unbounded recall in pure coordination games for which failing to coordinate yields a payoff of zero for both players. It is shown that every Fictitious Play player with bounded recall may fail to coordinate against his own type. On the other hand, players with unbounded recall are shown to coordinate (almost surely) against their own type as well as against players with bounded recall. In particular, this implies that a FP player's realized average utility is (almost surely) at least as large as his minmax payoff in 2×2 coordination games. Received: December 1997/Final version: November 1998     

Value and perfection in stochastic games

A stochastic game isvalued if for every playerk there is a functionr ^k:S→R from the state spaceS to the real numbers such that for every ε>0 there is an ε equilibrium such that with probability at least 1−ε no states is reached where the future expected payoff for any playerk differs fromr ^k(s) by more than ε. We call a stochastic gamenormal if the state space is at most countable, there are finitely many players, at every state every player has only finitely many actions, and the payoffs are uniformly bounded and Borel measurable as functions on the histories of play. We demonstrate an example of a recursive two-person non-zero-sum normal stochastic game with only three non-absorbing states and limit average payoffs that is not valued (but does have ε equilibria for every positive ε). In this respect two-person non-zero-sum stochastic games are very different from their zero-sum varieties. N. Vieille proved that all such non-zero-sum games with finitely many states have an ε equilibrium for every positive ε, and our example shows that any proof of this result must be qualitatively different from the existence proofs for zero-sum games. To show that our example is not valued we need that the existence of ε equilibria for all positive ε implies a “perfection” property. Should there exist a normal stochastic game without an ε equilibrium for some ε>0, this perfection property may be useful for demonstrating this fact. Furthermore, our example sews some doubt concerning the existence of ε equilibria for two-person non-zero-sum recursive normal stochastic games with countably many states. This research was supported financially by the German Science Foundation (Deutsche Forschungsgemeinschaft) and the Center for High Performance Computing (Technical University, Dresden). The author thanks Ulrich Krengel and Heinrich Hering for their support of his habilitation at the University of Goettingen, of which this paper is a part.     

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.     

Bias and Overtaking Equilibria for Zero-Sum Stochastic Differential Games

This paper deals with zero-sum stochastic differential games with long-run average payoffs. Our main objective is to give conditions for existence and characterization of bias and overtaking optimal equilibria. To this end, first we characterize the family of optimal average payoff strategies. Then, within this family, we impose suitable conditions to determine the subfamilies of bias and overtaking equilibria. A key step to obtain these facts is to show the existence of solutions to the average payoff optimality equations. This is done by the usual “vanishing discount” approach. Finally, a zero-sum game associated to a certain manufacturing process illustrates our results.     

Absolutely expedient algorithms for learning Nash equilibria

This paper considers a multi-person discrete game with random payoffs. The distribution of the random payoff is unknown to the players and further none of the players know the strategies or the actual moves of other players. A class of absolutely expedient learning algorithms for the game based on a decentralised team of Learning Automata is presented. These algorithms correspond, in some sense, to rational behaviour on the part of the players. All stable stationary points of the algorithm are shown to be Nash equilibria for the game. It is also shown that under some additional constraints on the game, the team will always converge to a Nash equilibrium. Dedicated to the memory of Professor K G Ramanathan     

带策略约束的区间数双矩阵博弈的双线性规划求解方法

传统区间数双矩阵博弈理论研究局中人支付值为区间数的策略选择问题,但没有考虑局中人策略选择可能受到各种约束.创建一种求解局中人策略选择受约束且支付值为区间数的双矩阵博弈（简称带策略约束的区间数双矩阵博弈）的简单、有效的双线性规划求解方法.首先,将局中人的博弈支付看作支付值区间中数值的函数.通过证明这种函数具有单调性,据此利用支付值区间的上、下界,构造了一对辅助双线性规划模型,可分别用于显式地计算任意带策略约束的区间数双矩阵博弈中局中人区间数博弈支付的上、下界及其相应的最优策略.最后,利用考虑策略约束条件下企业和政府针对发展低碳经济策略问题的算例,通过比较其与不考虑策略约束情形下的结果,说明了提出的模型和方法的有效性、优越性及可应用性.     

Pursuit–Evasion Games with incomplete information in discrete time

Pursuit–Evasion Games (in discrete time) are stochastic games with nonnegative daily payoffs, with the final payoff being the cumulative sum of payoffs during the game. We show that such games admit a value even in the presence of incomplete information and that this value is uniform, i.e. there are e{\epsilon}-optimal strategies for both players that are e{\epsilon}-optimal in any long enough prefix of the game. We give an example to demonstrate that nonnegativity is essential and expand the results to Leavable Games.     

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.     

Internal correlation in repeated games

This paper characterizes the set of all the Nash equilibrium payoffs in two player repeated games where the signal that the players get after each stage is either trivial (does not reveal any information) or standard (the signal is the pair of actions played). It turns out that if the information is not always trivial then the set of all the Nash equilibrium payoffs coincides with the set of the correlated equilibrium payoffs. In particular, any correlated equilibrium payoff of the one shot game is also a Nash equilibrium payoff of the repeated game.For the proof we develop a scheme by which two players can generate any correlation device, using the signaling structure of the game. We present strategies with which the players internally correlate their actions without the need of an exogenous mediator.     

A BSDE approach to stochastic differential games with incomplete information

We consider a two-player zero-sum stochastic differential game in which one of the players has a private information on the game. Both players observe each other, so that the non-informed player can try to guess his missing information. Our aim is to quantify the amount of information the informed player has to reveal in order to play optimally: to do so, we show that the value function of this zero-sum game can be rewritten as a minimization problem over some martingale measures with a payoff given by the solution of a backward stochastic differential equation.     

Pure strategy Nash equilibria and the probabilistic prospects of Stackelberg players

We consider the set of all m×n bimatrix games with ordinal payoffs. We show that on the subset E of such games possessing at least one pure strategy Nash equilibrium, both players prefer the role of leader to that of follower in the corresponding Stackelberg games. This preference is in the sense of first-degree stochastic dominance by leader payoffs of follower payoffs. It follows easily that on the complement of E, the follower’s role is preferred in the same sense. Thus we see a tendency for leadership preference to obtain in the presence of multiple pure strategy Nash equilibria in the underlying game.     

Independent mistakes in large games

Economic models usually assume that agents play precise best responses to others' actions. It is sometimes argued that this is a good approximation when there are many agents in the game, because if their mistakes are independent, aggregate uncertainty is small. We study a class of games in which players' payoffs depend solely on their individual actions and on the aggregate of all players' actions. We investigate whether their equilibria are affected by mistakes when the number of players becomes large. Indeed, in generic games with continuous payoff functions, independent mistakes wash out in the limit. This may not be the case if payoffs are discontinuous. As a counter-example we present the n players Nash bargaining game, as well as a large class of “free-rider games.” Received: November 1997/Final version: December 1999     

A link between sequential semi-anonymous nonatomic games and their large finite counterparts

We show that obtainable equilibria of a multi-period nonatomic game can be used by players in its large finite counterparts to achieve near-equilibrium payoffs. Such equilibria in the form of random state-to-action rules are parsimonious in form and easy to execute, as they are both oblivious of past history and blind to other players’ present states. Our transient results can be extended to a stationary case, where the finite multi-period games are special discounted stochastic games. In both nonatomic and finite games, players’ states influence their payoffs along with actions they take; also, the random evolution of one particular player’s state is driven by all players’ states as well as actions. The finite games can model diverse situations such as dynamic price competition. But they are notoriously difficult to analyze. Our results thus suggest ways to tackle these problems approximately.     

Optimal strategic reasoning with McNaughton functions

The aim of the paper is to explore strategic reasoning in strategic games of two players with an uncountably infinite space of strategies the payoff of which is given by McNaughton functions—functions on the unit interval which are piecewise linear with integer coefficients. McNaughton functions are of a special interest for approximate reasoning as they correspond to formulas of infinitely valued Lukasiewicz logic. The paper is focused on existence and structure of Nash equilibria and algorithms for their computation. Although the existence of mixed strategy equilibria follows from a general theorem (Glicksberg, 1952) [5], nothing is known about their structure neither the theorem provides any method for computing them. The central problem of the article is to characterize the class of strategic games with McNaughton payoffs which have a finitely supported Nash equilibrium. We give a sufficient condition for finite equilibria and we propose an algorithm for recovering the corresponding equilibrium strategies. Our result easily generalizes to n-player strategic games which don't need to be strictly competitive with a payoff functions represented by piecewise linear functions with real coefficients. Our conjecture is that every game with McNaughton payoff allows for finitely supported equilibrium strategies, however we leave proving/disproving of this conjecture for future investigations.     

The Compromise Value for Cooperative Games with Random Payoffs

This paper introduces and studies the compromise value for cooperative games with random payoffs, that is, for cooperative games where the payoff to a coalition of players is a random variable. This value is a compromise between utopia payoffs and minimal rights and its definition is based on the compromise value for NTU games and the τ-value for TU games. It is shown that the nonempty core of a cooperative game with random payoffs is bounded by the utopia payoffs and the minimal rights. Consequently, for such games the compromise value exists. Further, we show that the compromise value of a cooperative game with random payoffs coincides with the τ-value of a related TU game if the players have a certain type of preferences. Finally, the compromise value and the marginal value, which is defined as the average of the marginal vectors, coincide on the class of two-person games. This results in a characterization of the compromise value for two-person games.I thank Peter Borm, Ruud Hendrickx and two anonymous referees for their valuable comments.     

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.     

Subgame Consistent Cooperative Solutions in Stochastic Differential Games

Subgame consistency is a fundamental element in the solution of cooperative stochastic differential games. In particular, it ensures that: (i) the extension of the solution policy to a later starting time and to any possible state brought about by the prior optimal behavior of the players would remain optimal; (ii) all players do not have incentive to deviate from the initial plan. In this paper, we develop a mechanism for the derivation of the payoff distribution procedures of subgame consistent solutions in stochastic differential games with transferable payoffs. The payoff distribution procedure of the subgame consistent solution can be identified analytically under different optimality principles. Demonstration of the use of the technique for specific optimality principles is shown with an explicitly solvable game. For the first time, analytically tractable solutions of cooperative stochastic differential games with subgame consistency are derived.