Robust Multiple Objective Game Theory

In this paper, we propose a distribution-free model instead of considering a particular distribution for multiple objective games with incomplete information. We assume that each player does not know the exact value of the uncertain payoff parameters, but only knows that they belong to an uncertainty set. In our model, the players use a robust optimization approach for each of their objective to contend with payoff uncertainty. To formulate such a game, named “robust multiple objective games” here, we introduce three kinds of robust equilibrium under different preference structures. Then, by using a scalarization method and an existing result on the solutions for the generalized quasi-vector equilibrium problems, we obtain the existence of these robust equilibria. Finally, we give an example to illustrate our model and the existence theorems. Our results are new and fill the gap in the game theory literature.     

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.     

Noncooperative selection of the core

For bargaining environments given by transferable utility characteristic functions that are zero-normalized and admit a nonempty core, we find a class of random-proposer bargaining games, generalized from Okada (1993), such that there is a one-to-one mapping from these games to the core, each game realizes the corresponding core allocation as its unique (ex ante) Stationary Subgame Perfect Equilibrium (SSPE) payoff profile, and every ex post SSPE payoff profile converges to the core allocation as the discount factor goes to one. The result has a natural interpretation in terms of bargaining power. Received: December 2000/Revised: August 2002     

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.     

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.     

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.     

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.     

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.     

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.     

Monotone and bounded interval equilibria in a coordination game with information aggregation

We analyze how private learning in a class of games with common stochastic payoffs affects the form of equilibria, and how properties such as player welfare and the extent of strategic miscoordination relate across monotone and non-monotone equilibria. Researchers typically focus on monotone equilibria. We provide conditions under which non-monotone equilibria also exist, where players attempt to coordinate to obtain the stochastic payoff whenever signals are in a bounded interval. In bounded interval equilibria (BIE), an endogenous fear of miscoordination discourages players from coordinating to obtain the stochastic payoff when their signals suggest coordination is most beneficial. In contrast to monotone equilibria, expected payoffs from successful coordination in BIE are lower than the ex-ante expected payoff from ignoring signals and always trying to coordinate to obtain the stochastic payoff. We show that BIE only exist when, absent private information, the game would be a coordination game.     

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.     

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.     

On stochastic games with additive reward and transition structure

In this paper, we introduce a new class of two-person stochastic games with nice properties. For games in this class, the payoffs as well as the transitions in each state consist of a part which depends only on the action of the first player and a part dependent only on the action of the second player.For the zero-sum games in this class, we prove that the orderfield property holds in the infinite-horizon case and that there exist optimal pure stationary strategies for the discounted as well as the undiscounted payoff criterion. For both criteria also, finite algorithms are given to solve the game. An example shows that, for nonzero sum games in this class, there are not necessarily pure stationary equilibria. But, if such a game possesses a stationary equilibrium point, then there also exists a stationary equilibrium point which uses in each state at most two pure actions for each player.     

On Pareto equilibria in vector-valued extensive form games

In this paper we investigate the existence of Pareto equilibria in vector-valued extensive form games. In particular we show that every vector-valued extensive form game with perfect information has at least one subgame perfect Pareto equilibrium in pure strategies. If one tries to prove this and develop a vector-valued backward induction procedure in analogy to the real-valued one, one sees that different effects may occur which thus have to be taken into account: First, suppose the deciding player at a nonterminal node makes a choice such that the equilibrium payoff vector of the subgame he would enter is undominated under the equilibrium payoff vectors of the other subgames he might enter. Then this choice need not to lead to a Pareto equilibrium. Second, suppose at a nonterminal node a chance move may arise. The combination of the Pareto equilibria of the subgames to give a strategy combination of the entire game need not be a Pareto equilibrium of the entire 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.     

On weakly correlated and correlated equilibria in discontinuous games

This paper treats of non-zero-sum discontinuous games with compact Hausdorff strategy spaces. It is assumed that the payoff function of each player in the game is bounded, Borel measurable and is upper semicontinuous on his strategy space, for all fixed actions of the remaining players. It is shown that for each ε>0, such games possess weakly correlated ε-epuilibria introduced by Moulin and Vial as extension of correlated equilibria in the sense of Aumann. An upper semicontinuous came having weakly correlated equilibria and no correlated equilibria is discussed in details.     

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     

不确定性下的一主多从博弈及其ε-平衡稳定性分析

本文对主从博弈以及不确定性等问题进行研究,建立了不确定性下的一主多从博弈模型,并利用极大值定理证明了该模型均衡点的存在性。对于不确定性下的一主多从博弈的均衡点问题建立了有限理性模型,进而得到其均衡点的稳定性,即结构稳定以及对ε-平衡是鲁棒的。     

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.