Repeated Games with Bonuses

This paper deals with 2-player zero-sum repeated games in which player 1 receives a bonus at stage t if he repeats the action he played at stage t−1. We investigate the optimality of simple strategies for player 1. A simple strategy for player 1 consists of playing the same mixed action at every stage, irrespective of past play. Furthermore, for games in which player 1 has a simple optimal strategy, we characterize the set of stationary optimal strategies for player 2.     

On the existence of good stationary strategies for nonleavable stochastic games

This paper discusses the problem regarding the existence of optimal or nearly optimal stationary strategies for a player engaged in a nonleavable stochastic game. It is known that, for these games, player I need not have an -optimal stationary strategy even when the state space of the game is finite. On the contrary, we show that uniformly -optimal stationary strategies are available to player II for nonleavable stochastic games with finite state space. Our methods will also yield sufficient conditions for the existence of optimal and -optimal stationary strategies for player II for games with countably infinite state space. With the purpose of introducing and explaining the main results of the paper, special consideration is given to a particular class of nonleavable games whose utility is equal to the indicator of a subset of the state space of the 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.     

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.     

Zero-sum stochastic games with unbounded costs: Discounted and average cost cases

Zero-sum stochastic games with countable state space and with finitely many moves available to each player in a given state are treated. As a function of the current state and the moves chosen, player I incurs a nonnegative cost and player II receives this as a reward. For both the discounted and average cost cases, assumptions are given for the game to have a finite value and for the existence of an optimal randomized stationary strategy pair. In the average cost case, the assumptions generalize those given in Sennott (1993) for the case of a Markov decision chain. Theorems of Hoffman and Karp (1966) and Nowak (1992) are obtained as corollaries. Sufficient conditions are given for the assumptions to hold. A flow control example illustrates the results.     

Convex semi-infinite games

This paper introduces a generalization of semi-infinite games. The pure strategies for player I involve choosing one function from an infinite family of convex functions, while the set of mixed strategies for player II is a closed convex setC inR ⁿ. The minimax theorem applies under a condition which limits the directions of recession ofC. Player II always has optimal strategies. These are shown to exist for player I also if a certain infinite system verifies the property of Farkas-Minkowski. The paper also studies certain conditions that guarantee the finiteness of the value of the game and the existence of optimal pure strategies for player I.Many thanks are due to the referees for their detailed comments.     

Static search games played over graphs and general metric spaces

We define a general game which forms a basis for modelling situations of static search and concealment over regions with spatial structure. The game involves two players, the searching player and the concealing player, and is played over a metric space. Each player simultaneously chooses to deploy at a point in the space; the searching player receiving a payoff of 1 if his opponent lies within a predetermined radius r of his position, the concealing player receiving a payoff of 1 otherwise. The concepts of dominance and equivalence of strategies are examined in the context of this game, before focusing on the more specific case of the game played over a graph. Methods are presented to simplify the analysis of such games, both by means of the iterated elimination of dominated strategies and through consideration of automorphisms of the graph. Lower and upper bounds on the value of the game are presented and optimal mixed strategies are calculated for games played over a particular family of graphs.     

Stationary equilibria in cyclic games: Search and structure

The existence of optimal stationary strategies for a cyclic game played on the vertices of a bipartite graph up to the first cycle with the payoff of one player to the other equaling the sum of the maximal and minimal local payoffs on this cycle is proved. This result implies that the problem belongs to the class NP ∩ co-NP; -a polynomial algorithm that yields optimal strategies for ergodic extensions of matrix games is given. Translated fromMatematicheskie Zametki, Vol. 67, No. 6, pp. 913–921, June, 2000.     

A Game Related to the Number of Hides Game

In this paper, we study a discrete search game on an array of N ordered cells, with two players having opposite goals: player I (searcher) and player II (hider). Player II has to hide q objects at consecutive cells and player I can search p consecutive cells. The payoff to player I is the number of objects found by him. In some situations, the players need to adopt sophisticated strategies if they are to act optimally.     

Stochastic Discrete-Time Nash Games with Constrained State Estimators

In this paper, we consider stochastic linear-quadratic discrete-time Nash games in which two players have access only to noise-corrupted output measurements. We assume that each player is constrained to use a linear Kalman filter-like state estimator to implement his optimal strategies. Two information structures available to the players in their state estimators are investigated. The first has access to one-step delayed output and a one-step delayed control input of the player. The second has access to the current output and a one-step delayed control input of the player. In both cases, statistics of the process and statistics of the measurements of each player are known to both players. A simple example of a two-zone energy trading system is considered to illustrate the developed Nash strategies. In this example, the Nash strategies are calculated for the two cases of unlimited and limited transmission capacity constraints.     

Weak topology and infinite matrix games

This paper approaches infinite matrix games through the weak topology on the players' sets of strategies. A new class of semi-infinite and infinite matrix games is defined, and it is proved that these games always have a value and optimal strategies for each player. Using these games it is proved that some other important classes of infinite matrix game also have values. Received April 1996/Revised version June 1997/Final version September 1997     

A class of stochastic games with ordered field property

It is shown that discounted general-sum stochastic games with two players, two states, and one player controlling the rewards have the ordered field property. For the zero-sum case, this result implies that, when starting with rational data, also the value is rational and that the extreme optimal stationary strategies are composed of rational components.     

Stackelberg strategies in linear-quadratic stochastic differential games

This paper obtains the Stackelberg solution to a class of two-player stochastic differential games described by linear state dynamics and quadratic objective functionals. The information structure of the problem is such that the players make independent noisy measurements of the initial state and are permitted to utilize only this information in constructing their controls. Furthermore, by the very nature of the Stackelberg solution concept, one of the players is assumed to know, in advance, the strategy of the other player (the leader). For this class of problems, we first establish existence and uniqueness of the Stackelberg solution and then relate the derivation of the leader's Stackelberg solution to the optimal solution of a nonstandard stochastic control problem. This stochastic control problem is solved in a more general context, and its solution is utilized in constructing the Stackelberg strategy of the leader. For the special case Gaussian statistics, it is shown that this optimal strategy is affine in observation of the leader. The paper also discusses numerical aspects of the Stackelberg solution under general statistics and develops algorithms which converge to the unique Stackelberg solution.This work was performed while the second author was on sabbatical leave at the Department of Applied Mathematics, Twente University of Technology, Enschede, Holland.     

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.     

Pure subgame-perfect equilibria in free transition games

We consider a class of stochastic games, where each state is identified with a player. At any moment during play, one of the players is called active. The active player can terminate the game, or he can announce any player, who then becomes the active player. There is a non-negative payoff for each player upon termination of the game, which depends only on the player who decided to terminate. We give a combinatorial proof of the existence of subgame-perfect equilibria in pure strategies for the games in our class.     

Proper belief revision and rationalizability in dynamic games

In this paper we develop an epistemic model for dynamic games in which players may revise their beliefs about the opponents’ utility functions as the game proceeds. Within this framework, we propose a rationalizability concept that is based upon the following three principles: (1) at every instance of the game, a player should believe that his opponents are carrying out optimal strategies, (2) a player, at information set h, should not change his belief about an opponent’s relative ranking of two strategies s and s′ if both s and s′ could have led to h, and (3) the players’ initial beliefs about the opponents’ utility functions should agree on a given profile u of utility functions. Common belief in these events leads to the concept of persistent rationalizability for the profile u of utility functions. It is shown that for a given game tree with observable deviators and a given profile u of utility functions, every properly point-rationalizable strategy is a persistently rationalizable strategy for u. This result implies that persistently rationalizable strategies always exist for all game trees with observable deviators and all profiles of utility functions. We provide an algorithm that can be used to compute the set of persistently rationalizable strategies for a given profile u of utility functions. For generic games with perfect information, persistent rationalizability uniquely selects the backward induction strategy for every player.     

Duality and markovian strategies

We introduce the dual of a stochastic game with incomplete information on one side, and we deduce some properties of optimal strategies of the uninformed player. Received December 1996/Revised version December 1997     

An orderfield property for stochastic games when one player controls transition probabilities

When the transition probabilities of a two-person stochastic game do not depend on the actions of a fixed player at all states, the value exists in stationary strategies. Further, the data of the stochastic game, the values at each state, and the components of a pair of optimal stationary strategies all lie in the same Archimedean ordered field. This orderfield property holds also for the nonzero sum case in Nash equilibrium stationary strategies. A finite-step algorithm for the discounted case is given via linear programming.This research was partially supported by the Air Force Office of Scientific Research, Grant No. 78-3495. The authors are indebted to Mr. J. Filar for some helpful suggestions in redrafting an earlier version of the paper, especially toward clarifying some obscurities in the proofs of Theorems 3.1 and 4.2 that existed in the earlier versions. This paper is dedicated to Professor C. R. Rao on his 60th birthday.     

Avoiding unfairness of Owen allocations in linear production processes

This paper deals with cooperation situations in linear production problems in which a set of goods are to be produced from a set of resources so that a certain benefit function is maximized, assuming that resources not used in the production plan have no value by themselves. The Owen set is a well-known solution rule for the class of linear production processes. Despite their stability properties, Owen allocations might give null payoff to players that are necessary for optimal production plans. This paper shows that, in general, the aforementioned drawback cannot be avoided allowing only allocations within the core of the cooperative game associated to the original linear production process, and therefore a new solution set named EOwen is introduced. For any player whose resources are needed in at least one optimal production plan, the EOwen set contains at least one allocation that assigns a strictly positive payoff to such player.