On equilibrium in pure strategies in games with many players

We demonstrate that, if there are sufficiently many players, any Bayesian equilibrium of an incomplete information game can be “ε-purified” . That is, close to any Bayesian equilibrium there is an approximate Bayesian equilibrium in pure strategies. Our main contribution is obtaining this result for games with a countable set of pure strategies. In order to do so we derive a mathematical result, in the spirit of the Shapley–Folkman Theorem, permitting countable strategy sets. Our main assumption is a “large game property,” dictating that the actions of relatively small subsets of players cannot have large affects on the payoffs of other players. E. Cartwright and M. Wooders are indebted to Phillip Reny, Frank Page and two anonymous referees for helpful comments.     

When is the value of public information positive in a game?

The value of public information is studied by considering the equilibrium selections that maximize the weighted sum of players' payoffs. We show that the value of information can be deduced from the deterministic games where the uncertain parameters have given values. If the maximal weighted sum of equilibrium payoffs in deterministic games is convex then the value of information in any Bayesian game derived from the deterministic games is positive with respect to the selection. We also show the converse result that positive value of information implies convexity. Hence, the convexity of maximal weighted sum of payoffs in deterministic games fully characterizes the value of information with respect to considered selections. We also discuss the implications of our results when positive value of information means that for any equilibrium in a game with less information there is a Pareto dominant equilibrium in any game with more information.     

On the role of chance moves and information in two-person games

The value of information has been the subject of many studies in a strategic context. The central question in these studies is how valuable the information hidden in the chance moves of a game is for one or more of the players. Generally speaking, only the extra possibilities that are beneficial for the players have been considered so far. In this note we study the value of information for a special class of two-person games. For these games we also investigate how “badly” the players can do, both with and without knowing the result of the chance move. In this way one can determine to what extent the players are restricted in their possibilities by the fact that some information is hidden in the chance moves of the games. This allows for a comparison of the influence of the chance move to the control that the players have over the game result.     

Dynamic consistency in incomplete information games under ambiguity

We develop a general framework of incomplete information games under ambiguity which extends the traditional framework of Bayesian games to the context of Ellsberg-type ambiguity. We then propose new solution concepts called ex ante and interim Γ-maximin equilibrium for solving such games. We show that, unlike the standard notion of Bayesian Nash equilibrium, these concepts may lead to rather different recommendations for the same game under ambiguity. This phenomenon is often referred to as dynamic inconsistency. Moreover, we characterize the sufficient condition under which dynamic consistency is assured in this generalized framework.     

A survey of static and dynamic potential games

Potential games are noncooperative games for which there exist auxiliary functions, called potentials, such that the maximizers of the potential are also Nash equilibria of the corresponding game. Some properties of Nash equilibria, such as existence or stability, can be derived from the potential, whenever it exists. We survey different classes of potential games in the static and dynamic cases, with a finite number of players, as well as in population games where a continuum of players is allowed. Likewise, theoretical concepts and applications are discussed by means of illustrative examples.     

A PGM framework for recursive modeling of players in simple sequential Bayesian games

We consider the situation where two agents try to solve each their own task in a common environment. In particular, we study simple sequential Bayesian games with unlimited time horizon where two players share a visible scene, but where the tasks (termed assignments) of the players are private information. We present an influence diagram framework for representing simple type of games, where each player holds private information. The framework is used to model the analysis depth and time horizon of the opponent and to determine an optimal policy under various assumptions on analysis depth of the opponent. Not surprisingly, the framework turns out to have severe complexity problems even in simple scenarios due to the size of the relevant past. We propose two approaches for approximation. One approach is to use Limited Memory Influence Diagrams (LIMIDs) in which we convert the influence diagram into a set of Bayesian networks and perform single policy update. The other approach is information enhancement, where it is assumed that the opponent in a few moves will know your assignment. Empirical results are presented using a simple board game.     

Redefinition of Belief Distorted Nash Equilibria for the Environment of Dynamic Games with Probabilistic Beliefs

In this paper, a new concept of equilibrium in dynamic games with incomplete or distorted information is introduced. In the games considered, players have incomplete information about crucial aspects of the game and formulate beliefs about the probabilities of various future scenarios. The concept of belief distorted Nash equilibrium combines optimization based on given beliefs and self-verification of those beliefs. Existence and equivalence theorems are proven, and this concept is compared to existing ones. Theoretical results are illustrated using several examples: extracting a common renewable resource, a large minority game, and a repeated Prisoner’s Dilemma.     

连续区间策略下二人零和对策问题研究

考虑连续区间策略下的二人零和对策问题,研究其均衡策略的存在性。首先分析了完全信息下的二人零和对策问题,证明了该问题均衡策略的存在性并给出求解方法。然后进一步研究了收益函数不确定的不完全信息二人零和对策问题,在各局中人都认为对方是风险厌恶型的假设下,分析该类对策纯策略均衡的存在性,并通过研究纯策略均衡存在的充要条件给出判断并寻找纯策略均衡解的方法。最后给出一个数值算例,验证本文所提出方法的可行性。     

Implementability of correlated and communication equilibrium outcomes in incomplete information games

In a correlated equilibrium, the players’ choice of actions is directed by correlated random messages received from an outside source, or mechanism. These messages allow for more equilibrium outcomes than without any messages (pure-strategy equilibrium) or with statistically independent ones (mixed-strategy equilibrium). In an incomplete information game, the messages may also reflect the types of the players, either because they are affected by extraneous factors that also affect the types (correlated equilibrium) or because the players themselves report their types to the mechanism (communication equilibrium). Mechanisms may be further differentiated by the connections between the messages that the players receive and their own and the other players’ types, by whether the messages are statistically dependent or independent, and by whether they are random or deterministic. Consequently, whereas for complete information games there are only three classes of equilibrium outcomes, with incomplete information the corresponding number is 14 or 15 for correlated equilibria and even larger—15, 16 or 17—for communication equilibria. For both solution concepts, the implication relations between the different kinds of equilibria form a two-dimensional lattice, which is considerably more intricate than the single-dimensional one of the complete information case.     

On repeated games with incomplete information played by non-Bayesian players

Unlike in the traditional theory of games of incomplete information, the players here arenot Bayesian, i.e. a player does not necessarily have any prior probability distribution as to what game is being played. The game is infinitely repeated. A player may be absolutely uninformed, i.e. he may know only how many strategies he has. However, after each play the player is informed about his payoff and, moreover, he has perfect recall. A strategy is described, that with probability unity guarantees (in the sense of the liminf of the average payoff) in any game, whatever the player could guarantee if he had complete knowledge of the game.     

Continuity of the value and optimal strategies when common priors change

We show that the value of a zero-sum Bayesian game is a Lipschitz continuous function of the players?? common prior belief with respect to the total variation metric on beliefs. This is unlike the case of general Bayesian games where lower semi-continuity of Bayesian equilibrium (BE) payoffs rests on the ??almost uniform?? convergence of conditional beliefs. We also show upper semi-continuity (USC) and approximate lower semi-continuity (ALSC) of the optimal strategy correspondence, and discuss ALSC of the BE correspondence in the context of zero-sum games. In particular, the interim BE correspondence is shown to be ALSC for some classes of information structures with highly non-uniform convergence of beliefs, that would not give rise to ALSC of BE in non-zero-sum games.     

n人可信策略博弈

本文研究模糊支付n人策略博弈,由于支付信息的不完全性,模糊支付可视为模糊变量。基于可信性理论,在不同的决策环境中引入模糊排序方法表征支付者行为。因此,本文定义四种可信均衡,等价于纳什均衡。其次证明了可信均衡存在性定理。除此之外,在现实策略博弈中用算例说明四种可信均衡的现实意义。最后讨论四种可信均衡之间可能存在的关系。     

Performance versus informativeness in linear-quadratic Gaussian noncooperative games

In this paper, we study the impact of informativeness on the performance of linear quadratic Gaussian Nash and Stackelberg games. We first show that, in two-person static Nash games, if one of the players acquires more information, then this extra information is beneficial to him, provided that it is orthogonal to both players' information. A special case is that when one of the players is informationally stronger than the other, then any new information is beneficial to him. We then show that a similar result holds for dynamic Nash games. In the dynamic games, the players use strategies that are linear functions of the current estimates of the state, generated by two Kalman filters. The same properties are proved to hold in static and feedback Stackelberg games as well.This work was partially supported by the US Air Force Office of Scientific Research under Grant No. AFOSR-82-0174.     

Zero-sum sequential games with incomplete information

Repeated zero-sum two-person games of incomplete information on one side are considered. If the one-shot game is played sequentially, the informed player moving first, it is proved that the value of then-shot game is constant inn and is equal to the concavification of the game in which the informed player disregards his extra information. This is a strengthening ofAumann andMaschler's results for simultaneous games. Optimal strategies for both players are constructed explicitly.     

An evolutionary game theoretic perspective on e-collaboration: The collaboration effort and media relativeness

Studies of e-collaboration from a game-theoretical perspective are practically nonexistent. This article contributes to filling this gap by focusing on the strategic interaction between players as they decide whether and how much to collaborate with each other. We use evolutionary game theory to make predictions about a two-person e-collaboration game. More specifically, we extend the traditional Prisoners’ Dilemma and Snowdrift game theory notions to discrete-strategy e-collaboration games, by explicitly including social punishments into the players’ payoff functions. We also introduce continuous-strategy e-collaboration games with both complete and incomplete information. Finally, we provide two generic dynamic programming models for e-collaboration games with media selection.     

Two Game Models for Cooperation with Implicit Noncooperation

We propose two flexible game models to represent and analyze cases that cannot be modeled by current game models. One is called sharing creditability game (SCG) and the other is called bottomline game (BLG). The new models transform cooperative games into new games that incorporate auxiliary information (noncooperative in nature) usually neglected in previous theories. The new games will be solved only by traditional noncooperative game theory. When the new solutions are applied to the original games, the solutions can reflect the auxiliary information in addition to the original objectives of the decision makers or players. Generally, the new solutions are different from the cooperative and the noncooperative solutions of the original games. Existing transferable utility (TU) games and noncooperative games will coincide with special cases of the two new game models. Using SCG and BLG, the prisoner’s dilemma can be reformulated and a richer set of decisions can be considered for the players. The two new game models have potential applications in military and socioeconomic situations.This research was partly funded by the College Engineering, Ohio State University.     

Learning algorithms for repeated bimatrix Nash games with incomplete information

The purpose of this paper is to study a particular recursive scheme for updating the actions of two players involved in a Nash game, who do not know the parameters of the game, so that the resulting costs and strategies converge to (or approach a neighborhood of) those that could be calculated in the known parameter case. We study this problem in the context of a matrix Nash game, where the elements of the matrices are unknown to both players. The essence of the contribution of this paper is twofold. On the one hand, it shows that learning algorithms which are known to work for zero-sum games or team problems can also perform well for Nash games. On the other hand, it shows that, if two players act without even knowing that they are involved in a game, but merely thinking that they try to maximize their output using the learning algorithm proposed, they end up being in Nash equilibrium.This research was supported in part by NSF Grant No. ECS-87-14777.     

Dynamic programming approach to discrete time dynamic feedback Stackelberg games with independent and dependent followers

Stackelberg games play an extremely important role in such fields as economics, management, politics and behavioral sciences. Stackelberg game can be modelled as a bilevel optimization problem. There exists extensive literature about static bilevel optimization problems. However, the studies on dynamic bilevel optimization problems are relatively scarce in spite of the importance in explaining and predicting some phenomena rationally. In this paper, we consider discrete time dynamic Stackelberg games with feedback information. Dynamic programming algorithms are presented for the solution of discrete time dynamic feedback Stackelberg games with multiple players both for independent followers and for dependent followers. When the followers act dependently, the game in this paper is a combination of Stackelberg game and Nash game.     

Existence of optimal strategies in Markov games with incomplete information

The existence of a value and optimal strategies is proved for the class of two-person repeated games where the state follows a Markov chain independently of players’ actions and at the beginning of each stage only Player 1 is informed about the state. The results apply to the case of standard signaling where players’ stage actions are observable, as well as to the model with general signals provided that Player 1 has a nonrevealing repeated game strategy. The proofs reduce the analysis of these repeated games to that of classical repeated games with incomplete information on one side. This research was supported in part by Israeli Science Foundation grants 382/98, 263/03, and 1123/06, and by the Zvi Hermann Shapira Research Fund.     

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.