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

Markov games with incomplete information

We consider zero-sum Markov games with incomplete information. Here, the second player is never informed about the current state of the underlying Markov chain. The existence of a value and of optimal strategies for both players is shown. In particular, we present finite algorithms for computing optimal strategies for the informed and uninformed player. The algorithms are based on linear programming results.     

The information revealed in infinitely-repeated games of incomplete information

Zero-sum two-person games with incomplete information on one side are considered. It is shown that the information revealed by the informed player in an infinitely-repeated game with simultaneous moves is essentially the same as the information revealed by him in a one-stage game in which he must move first.     

Statistically varyingN-person games with incomplete information

The paper provides a functional relationship between the amount of information available to the players and an equilibrium payoff in a game with statistically varying states of nature. Moreover, it is shown that for a supergame consisting of independent repetitions of a common matrix game equilibrium strategies are available which provide only few sequences of actions with positive probability.

---

Zusammenfassung Es werdenN-Personenspiele betrachtet, in denen die Auszahlungen sowohl von den Aktionen der Spieler, als auch von einem im Zeitablauf variierenden, a priori unbekannten, Zustandsparameter beeinflußt werden. Im vorliegenden Ansatz wird die erhaltbare Information in expliziter Weise als strategischer Parameter der Spieler aufgefaßt. Die Spieler sind bei der Beschaffung von Information informationstheoretisch modellierten Beschränkungen and die Menge verfügbarer Information unterworfen. Es gelingt in dem Modell, asymptotisch den funktionalen Zusammenhang zwischen der Menge verfügbarer Information und den erreichbaren Gleichgewichtsauszahlungen inT-fach replizierten Spielen zu bestimmen.

     

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.     

Selection of a correlated equilibrium in Markov stopping games

This paper deals with an extension of the concept of correlated strategies to Markov stopping games. The Nash equilibrium approach to solving nonzero-sum stopping games may give multiple solutions. An arbitrator can suggest to each player the decision to be applied at each stage based on a joint distribution over the players’ decisions according to some optimality criterion. This is a form of equilibrium selection. Examples of correlated equilibria in nonzero-sum games related to the best choice problem are given. Several concepts of criteria for selecting a correlated equilibrium are used.     

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.     

Optimal strategies in repeated games with incomplete information

The paper is concerned with zero-sum two-person repeated games with lack of information on one side. The main result in the construction of an optimal strategy for the uninformed player in the infinitely repeated game.     

Repeated games with incomplete information and transportation problems

We consider two person zero-sum repeated games with lack of information on one side and with payoffs of special "separable" form. The solutions for these games are reduced to the solutions for families of special transportation type problems with recursive structure. We illustrate our approach applying it to the game introduced by Mertens/Zamir [1976] and later studied by several authors. The "symmetric" subclass of games under consideration was studied in Domansky, Kreps [1995].     

Minmax and maxmin of repeated games with incomplete information

For a class of 2-Person 0-sum repeated games with incomplete information,Aumann/Masch1er [1967] andStearns [1967] have given a necessary and sufficient condition for the existence of v_∞ (the value of the infinitely repeated game).Mertens/Zamir [1971] andMertens [1971/72] have given the formula (and thus proved the existence) of \(\mathop {\lim }\limits_{n \to \infty } \) v _n , the limit of the values of the games withn repetitions, for a much larger class of games than that treated byAumann/Maschler andSteams. In this paper we extend the Aumann-Maschler-Stearns results to the larger family of games studied byMertens [1971/72].     

Asymptotically optimal strategies in repeated games with incomplete information

It is known that for repeated zero-sum games with incomplete information the limit of the values of theN-stage game exists asN tends to infinity. In this paper strategies are constructed that guarantee in theN-stage game the limit of values up to an error term \(\frac{K}{{\sqrt N }}.\)      

Infinite sequential games with perfect but incomplete information

Infinite sequential games, in which Nature chooses a Borel winning set and reveals it to one of the players, do not necessarily have a value if Nature has 3 or more choices. The value does exist if Nature has 2 choices. The value also does not necessarily exist if Nature chooses from 2 Borel payoff functions. Similarly, if Player 1 chooses the Borel winning set and does not reveal his selection to Player 2, then the game does not necessarily have a value if there are 3 or more choices; it does have a value if there are only 2 choices. If Player 1 chooses from 2 Borel payoff functions and does not reveal his choice, the game need not have a value either.     

Experimental results on ultimatum games with incomplete information

This paper is about experiments on two versions of ultimatum games with incomplete information, called the offer game and the demand game. We apply the strategy method, that is, each subject had to design a complete strategy in advance instead of reacting spontaneously to a situation which occurs in the game. Game theory predicts very similar outcomes for the offer and the demand games. Our experiments, however, show significant differences in behavior between both games. Using the strategy method, allows us to explore the motivations leading to those differences. Since each subject played the same version of the game eight rounds against changing anonymous opponents we can also study subjects' learning behavior. We propose a theory of boundedly rational behavior, called the “anticipation philosophy”, which is well supported by the experimental data.     

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.     

The mixed expansion of differential games with incomplete information

Kuhn's theorem [1953] about behavioral strategies is proved for the mixed expansion of a differential game.     

Formulation of Bayesian analysis for games with incomplete information

A formal model is given of Harsanyi's infinite hierarchies of beliefs. It is shown that the model closes with some Bayesian game with incomplete information, and that any such game can be approximated by one with a finite number of states of world.     

Adaptive expectations and dynamic adjustment in noncooperative games with incomplete information

This paper is concerned with the analysis of a Nash equilibrium of a noncooperative game. It can be shown that, without complete information about the other players' objectives or interests, the group of players, as a whole, can reach a Nash equilibrium by adopting a class of adaptive expectation and dynamic adjustment processes. It is shown that, if the expectation and adjustment processes are made continuously, the stability of the overall dynamic process is independent of the specific mechanisms of the expectation and the adjustment, but depends on the properties of each player's objective or payoff function. If, however, expectation and adjustment processes are made at discrete time intervals, the stability of the discrete process depends on the speed of adjustment chosen by each player.This research was supported by ONR Contract No. N00014-75-C-0738. The authors are indebted to the referee for several valuable comments and suggestions for improvement.