Non-cooperative n-person game with a stopped set

A continuous time non-cooperative n-person Markov game with a stopped set is studied in this paper. We prove that, in the game process with or without discount factor, there exists an optimal stationary point of strategies, called the equilibrium point, and each player has his equilibrium stationary strategy, such that the total expected discounted or non-discounted gain are maximums.     

A note on two-person zero-sum communicating stochastic games

For undiscounted two-person zero-sum communicating stochastic games with finite state and action spaces, a solution procedure is proposed that exploits the communication property, i.e., working with irreducible games over restricted strategy spaces. The proposed procedure gives the value of the communicating game with an arbitrarily small error when the value is independent of the initial state.     

A general solution concept for two-person,zero-sum games

In this paper, finitely additive mixed extensions of two-person zero-sum games are studied, where the players use probability contents as mixed strategies. It is well-known that symmetric finitely additive mixed extensions always have a saddle point, a finitely additive solution. We generalize this solution concept and assign a finitely additive solution to every bounded two-person, zero-sum game.     

Perfect information two-person zero-sum markov games with imprecise transition probabilities

Based on an extension of the controlled Markov set-chain model by Kurano et al. (in J Appl Prob 35:293–302, 1998) into competitive two-player game setting, we provide a model of perfect information two-person zero-sum Markov games with imprecise transition probabilities. We define an equilibrium value for the games formulated with the model in terms of a partial order and then establish the existence of an equilibrium policy pair that achieves the equilibrium value. We further analyze finite-approximation error bounds obtained from a value iteration-type algorithm and discuss some applications of the model.     

A two-person game of timing with random termination

We consider a marksmanship contest in which the first contestant to hit his target wins and the contest is to be terminated at a random timeT with cdfH(t). The model is evidently an extension of the classical discrete fire duel to the timing problem under an uncertain environment. It is shown that the uncertainty on the termination of the contest has influence on the equilibrium strategies and the equilibrium values.     

Necessary and sufficient conditions for multistage two-person zero-sum games

After previously obtained necessary conditions for optimal strategies in multistage two-person zero-sum games are summarized, necessary and sufficient conditions are derived. The utilization of these conditions is illustrated by means of a simple example.This research was supported by the Office of Naval Research under Grant No. Nonr 3656-31.     

Finite approximations to a zero-sum game with incomplete information

In this paper, we investigate a scheme for approximating a two-person zero-sum gameG of incomplete information by means of a natural systemG _mn of its finite subgames. The main question is: For largem andn, is an optimal strategy forG _mn necessarily anε-optimal strategy forG?     

A zero-sum stochastic game model of duopoly

We consider a discrete time zero-sum stochastic game model of duopoly and give a partial characterization of each firm's optimal pricing strategy. An extension to a continuous time model is also discussed.     

An algorithm for solving a two-person game with information transfer

An algorithm for solving a two-person game with information transfer is proposed. The algorithm is based on a special linear programming problem. An example is given.     

On saddlepoints of two-person zero-sum games with applications to data verification tests

A set of sufficient conditions for the existence of saddlepoint strategies of two-person zero-sum games is given which may be described as follows: The set of pure strategies for one of the two players is a compact metric space. His opponent has a best answer to each randomized strategy. The payoff function satisfies a continuity condition concerning the weak convergence of probability measures. These conditions are neither covered by those of well known existence theorems for saddlepoints nor do they generalize them. They are applied to treat important practical problems that have not been solved before. Received November 1995/Revised version August 1998     

Continuous-time zero-sum stochastic game with stopping and control

We consider a zero-sum stochastic game for continuous-time Markov chain with countable state space and unbounded transition and pay-off rates. The additional feature of the game is that the controllers together with taking actions are also allowed to stop the process. Under suitable hypothesis we show that the game has a value and it is the unique solution of certain dynamic programming inequalities with bilateral constraints. In the process we also prescribe a saddle point equilibrium.     

A Neo2 bayesian foundation of the maxmin value for two-person zero-sum games

A joint derivation of utility and value for two-person zero-sum games is obtained using a decision theoretic approach. Acts map states to consequences. The latter are lotteries over prizes, and the set of states is a product of two finite sets (m rows andn columns). Preferences over acts are complete, transitive, continuous, monotonie and certainty-independent (Gilboa and Schmeidler (1989)), and satisfy a new axiom which we introduce. These axioms are shown to characterize preferences such that (i) the induced preferences on consequences are represented by a von Neumann-Morgenstern utility function, and (ii) each act is ranked according to the maxmin value of the correspondingm × n utility matrix (viewed as a two-person zero-sum game). An alternative statement of the result deals simultaneously with all finite two-person zero-sum games in the framework of conditional acts and preferences.We are indebted to Jacques Drèze, Andreu Mas-Colell, Roger Myerson and Reinhard Selten for helpful comments.     

An improved algorithm for finding saddlepoints of two-person zero-sum games

It is well-known that one can sort (order)n real numbers in at mostF ₀(n) =nl – 2 ^l + 1 steps (comparisons), wherel = [log₂ n]. We snow how to find the strict saddlepoint or prove its absence in anm byn matrix,m n, in at mostF ₀(m)+F ₀(m+1)+n+m – 3 + (n–m) [log₂(m+1)] steps.     

A policy-improvement type algorithm for solving zero-sum two-person stochastic games of perfect information

 We give a policy-improvement type algorithm to locate an optimal pure stationary strategy for discounted stochastic games with perfect information. A graph theoretic motivation for our algorithm is presented as well. Received: January 1998 / Accepted: May 2002 Published online: February 14, 2003 Key words. stochastic games – MDP – perfect information – policy iteration Partially Funded by NSF Grant DMS 930-1052 and DMS 970-4951     

The value of two-person zero-sum repeated games with incomplete information and uncertain duration

Fix a zero-sum repeated game Γ with incomplete information on both sides. It is known that the value of the infinitely repeated game Γ_∞ need not exist (Aumann and Maschler 1995). It is proved that any number between the minmax and the maxmin of Γ_∞ is the value of a long finitely repeated game Γ _n where players’ information about the uncertain number of repetitions n is asymmetric.