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.     

Equilibria in repeated games of incomplete information: The general symmetric case

Every two person repeated game of symmetric incomplete information, in which the signals sent at each stage to both players are identical and generated by a state and moves dependent probability distribution on a given finite alphabet, has an equilibrium payoff. Received March 1996/Revised version January 1997/Final version May 1997     

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.     

A note on repeated games with non-monotonie value

We show that even when the information structure is independent of the state of nature, the value of then-stage zero-sum game with incomplete information is not necessarily monotonie with respect to the length of the game. More precisely, we give an example of such ann-stage game in whichV ₁ >V ₂ <V ₃.I am very grateful to Ehud Lehrer who introduced this question to me.     

Statistical linear differential games: A treatment of incomplete information

A zero-sum, two-player linear differential game of fixed duration is considered in the case when the information is incomplete but a statistical structure gives both players the possibility tospy the value of an unknown parameter in the payoff. Considerations of topological vector spaces and functional analysis allow one to demonstrate, via a classical Sion's theorem, sufficient conditions for the existence of a value.The author is indebted to Professor J. Fichefet for his helpful remarks and indications.     

Note Equilibrium payoffs in stochastic games of incomplete information: the general symmetric case

We prove that the existence of equilibrium payoffs for stochastic games of incomplete symmetric information follows from the same result for stochastic games with complete information. Received January 1999/Revised October 2001     

Algorithms for uniform optimal strategies in two-player zero-sum stochastic games with perfect information

We deal with zero-sum two-player stochastic games with perfect information. We propose two algorithms to find the uniform optimal strategies and one method to compute the optimality range of discount factors. We prove the convergence in finite time for one algorithm. The uniform optimal strategies are also optimal for the long run average criterion and, in transient games, for the undiscounted criterion as well.     

Randomized stopping games and Markov market games

We study nonzero-sum stopping games with randomized stopping strategies. The existence of Nash equilibrium and ɛ-equilibrium strategies are discussed under various assumptions on players random payoffs and utility functions dependent on the observed discrete time Markov process. Then we will present a model of a market game in which randomized stopping times are involved. The model is a mixture of a stochastic game and stopping game. Research supported by grant PBZ-KBN-016/P03/99.     

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 }}.\)      

Informational aspects of a class of subjective games of incomplete information: Static case

Subjective games of incomplete information are formulated where some of the key assumptions of Bayesian games of incomplete information are relaxed. The issues arising because of the new formulation are studied in the context of a class of nonzero-sum, two-person games, where each player has a different model of the game. The static game is investigated in this note. It is shown that the properties of the static subjective game are different from those of the corresponding Bayesian game. Counterintuitive outcomes of the game can occur because of the different beliefs of the players. These outcomes may lead the players to realize the differences in their models.This work was sponsored by the Office of Naval Research under Contract No. N00014-84-C-0485.     

A differential game of incomplete information

In this paper, we study a differential game of incomplete information. In such a game, the cost function depends on parameter . At the start of the game, only one of the players knows the value of this parameter, while the other player has only a (subjective) probability distribution for the parameter. We obtain explicit expressions for both the value of the game and the two players' optimal strategies.     

Repeated games with asymmetric information and random price fluctuations at finance markets

This paper is concerned with multistage bidding models introduced in De Meyer and Moussa Saley (Int J Game Theory 31:285–319, 2002) to analyze the evolution of the price system at finance markets with asymmetric information. The repeated games are considered modelling the biddings with the admissible bids k/m, unlike the above mentioned paper, where arbitrary bids are allowed. It is shown that the sequence of values of n-step games is bounded from above and converges to the value of the game with infinite number of steps. The optimal strategies of infinite game generate a symmetric random walk of transaction prices over admissible bids with absorbing extreme points. The value of infinite game is equal to the expected duration of this random walk multiplied by the constant one-step gain of informed Player 1. This study was supported by the grant 04-06-80430 of Russian Foundation of Basic Research which is gratefully acknowledged. I am thankful to anonymous referees and to William Thomson for instructive and helpful remarks and comments.     

A multistage game with incomplete information requiring an infinite memory

This paper describes a zero-sum, discrete, multistage, time-lag game in which, for one player, there is no integerk such that an optimal strategy, for a new move during play, can always be determined as a function of the pastk state positions; that is, the player requires an infinite memory. The game is a pursuit-evasion game with the payoff to the maximizing player being the time to capture.This paper is the result of work carried out at the University of Adelaide, Adelaide, Australia, under an Australian Commonwealth Postgraduate Award.The author should like to thank the referee for his valued suggestions.     

Existence of minmax points in discontinuous strategic games

In this note we prove the existence of minmax points for strategic form games where the sets of strategies are topological spaces and the payoff functions satisfy conditions weaker than continuity. The employed tools are the class of transfer weakly upper continuous functions and the class of weakly lower pseudocontinuous functions. An example shows that our result is of minimal character.     

On the stability of evolutionary dynamics in games with incomplete information

In an interaction it is possible that one agent has features it is aware of but the opponent is not. These features (e.g. cost, valuation or fighting ability) are referred to as the agent’s type. The paper compares two models of evolution in symmetric situations of this kind. In one model the type of an agent is fixed and evolution works on strategies of types. In the other model every agent adopts with fixed probabilities both types, and type-contingent strategies are exposed to evolution. It is shown that the dynamic stability properties of equilibria may differ even when there are only two types and two strategies. However, in this case the dynamic stability properties are generically the same when the payoff of a player does not depend directly on the type of the opponent. Examples illustrating these results are provided.     

A markov chain game with dynamic information

Two players, not knowing each other's position, move in a domain and can flash a searchlight. The game terminates when one player is caught within the area illuminated by the flash of the other. However, if this first player is not in this area, then the other player has disclosed his position to the former one, who may be able to exploit this information. The game is considered on a finite state space and in discrete time.The work of the second author was supported by ZWO, The Netherlands Organization for the Advancement of Pure Research, Contract No. B62-239, by the US Air Force Office of Scientific Research, Grant No. AFOSR-85-0245, and by the National Science Foundation, Grant No. NSF-INT-8504097.Visiting Professor at Delft University of Technology during 1986.     

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.     

Solutions for some bargaining games under the Harsanyi-Selten solution theory,part II: Analysis of specific bargaining games

Part II of the paper (for Part I see Harsanyi (1982)) describes the actual solutions the Harsanyi-Selten solution theory provides for some important classes of bargaining games, such as unanimity games; trade between one seller and several potential buyers; and two-person bargaining games with incomplete information on one side or on both sides. It also discusses some concepts and theorems useful in computing the solution; and explains how our concept of risk dominance enables us to analyze game situations in terms of some intuitively very compelling probabilistic (subjective-probability) considerations disallowed by classical game theory.     

On differential games with Markov perfect triggering

This paper is an attempt to throw some light on the issue of whether defining history-dependent state variables in a differential game does allow for a dynamic play of precommitment equilibria. We suggest the application of trigger strategies in a state-feedback context. Based on a punishment mode in Markov perfect strategies and being able to detect even past deviations followed by histories returning to equilibrium, these subgame-perfect strategies lead to the enforcement of certain outcomes by means of dynamic rules of strategic interaction. The last part of our exposition is devoted to specific game structures under which a trigger equilibrium can be used as well as a punishment mode.