Cooperation under interval uncertainty

In this paper, the classical theory of two-person cooperative games is extended to two-person cooperative games with interval uncertainty. The core, balancedness, superadditivity and related topics are studied. Solutions called ψ ^α-values are introduced and characterizations are given.     

Switching surfaces inN-person differential games

Switching surfaces inN-person differential games are essentially similar to those encountered in optimal control and two-person, zero-sum differential games. The differences between the Nash noncooperative solution and the saddle-point solution are reflected in the dispersal surfaces. These are discussed through classification and construction procedures for switching surfaces. A simple example of a two-person, nonzero-sum game is considered. A complete solution of this game will be presented in a companion paper (Ref. 1).     

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.     

Stochastic differential games: Occupation measure based approach

A new approach based on occupation measures is introduced for studying stochastic differential games. For two-person zero-sum games, the existence of values and optimal strategies for both players is established for various payoff criteria. ForN-person games, the existence of equilibria in Markov strategies is established for various cases.     

Separable and low-rank continuous games

In this paper, we study nonzero-sum separable games, which are continuous games whose payoffs take a sum-of-products form. Included in this subclass are all finite games and polynomial games. We investigate the structure of equilibria in separable games. We show that these games admit finitely supported Nash equilibria. Motivated by the bounds on the supports of mixed equilibria in two-player finite games in terms of the ranks of the payoff matrices, we define the notion of the rank of an n-player continuous game and use this to provide bounds on the cardinality of the support of equilibrium strategies. We present a general characterization theorem that states that a continuous game has finite rank if and only if it is separable. Using our rank results, we present an efficient algorithm for computing approximate equilibria of two-player separable games with fixed strategy spaces in time polynomial in the rank of the game. This research was funded in part by National Science Foundation grants DMI-0545910 and ECCS-0621922 and AFOSR MURI subaward 2003-07688-1.     

An operator solution of stochastic games

A class of zero-sum, two-person stochastic games is shown to have a value which can be calculated by transfinite iteration of an operator. The games considered have a countable state space, finite action spaces for each player, and a payoff sufficiently general to include classical stochastic games as well as Blackwell’s infiniteG _δ games of imperfect information. Research supported by National Science Foundation Grants DMS-8801085 and DMS-8911548.     

Update games and update networks

In this paper we model infinite processes with finite configurations as infinite games over finite graphs. We investigate those games, called update games, in which each configuration occurs an infinite number of times during a two-person play. We also present an efficient polynomial-time algorithm (and partial characterization) for deciding if a graph is an update network.     

On equilibrium points of diagonaln-person games

In this paper, we compute explicitly the equilibrium points of diagonaln-person games when all of them have the same number of strategies. This number is arbitrary. A wide generalization of two-person games is immediately obtained.The author is grateful to Professor Joel Cohen who visited IMASL during the winter of 1987 and commented on the paper.     

An impossibility result concerningn-person bargaining games

In this note we show that a solution proposed byRaiffa for two-person bargaining games, which has recently been axiomatized byKalai/Smorodinsky, does not generalize in a straightforward manner to generaln-person bargaining games. Specifically, the solution is not Pareto optimal on the class of alln-person bargaining games, and no solution which is can possess the other properties which characterizeRaiffa's solution in the two-person case.     

Two-Person Second-Order Games,Part 2: Restructuring Operations to Reach a Win-Win Profile

In Part 1 of the paper, using habitual domains theory and finite Markov chain theory, we have introduced a new model for describing the evolution of the states of mind of players over time, the two-person second-order game. The concepts of focal mind profile as well as the solution concept of win-win mind profile have been introduced as solution concepts for these games. In Part 2 of the paper, we address the problem of restructuring a game where the focal profile (1,1) is not reachable or is not a win-win profile into a game where the profile (1,1) is a reachable win-win profile. Precisely, under some reasonable assumptions, we derive the possibility theorem that it is always possible to reach a win-win mind profile in a two-person second-order game. Moreover, we provide practical operations for restructuring games for reaching a win-win profile. This research was partially supported by the National Science Council, Taiwan, NSC96-2416-H009-013.     

Structure of equilibria inN-person non-cooperative games

Here we study the structure of Nash equilibrium points forN-person games. For two-person games we observe that exchangeability and convexity of the set of equilibrium points are synonymous. This is shown to be false even for three-person games. For completely mixed games we get the necessary inequality constraints on the number of pure strategies for the players. Whereas the equilibrium point is unique for completely mixed two-person games, we show that it is not true for three-person completely mixed game without some side conditions such as convexity on the equilibrium set. It is a curious fact that for the special three-person completely mixed game with two pure strategies for each player, the equilibrium point is unique; the proof of this involves some combinatorial arguments.     

一般化两人零和模糊对策

定义一般化两人零和模糊对策,分别对具有纯策略和混合策略的一般化两人零和模糊对策进行研究,得到相应的最小最大值定理,以及一些与经典矩阵对策相类似的结果。     

The associated maximization problem for separable games

Two-person zero-sum games with separable payoff functions are examined using the geometric concept of dual cones. It is shown that the value of such games may be found by solving an associated maximization problem. Some numerical implications, particularly the application of linear programming to finding approximate solutions, are discussed. With the value known, optimal mixed strategies may, in principle, be readily determined.This research was sponsored in part by the U.S. Air Force Office of Scientific Research, Air Force Systems Command, USAF Grant AFOSR No. 71-2116A.     

模糊二人零和对策的纳什均衡求解

用三角模糊数刻画二人零和对策支付值的不确定性,提出了计算模糊二人零和对策纳什均衡解的多目标规划方法.给出了一种基于区间数比较的三角形模糊数排序方法,根据该方法将模糊二人零和对策转化为多目标线性规划.通过一个数值实例说明了该方法的有效性和实用性.     

Value and perfection in stochastic games

A stochastic game isvalued if for every playerk there is a functionr ^k:S→R from the state spaceS to the real numbers such that for every ε>0 there is an ε equilibrium such that with probability at least 1−ε no states is reached where the future expected payoff for any playerk differs fromr ^k(s) by more than ε. We call a stochastic gamenormal if the state space is at most countable, there are finitely many players, at every state every player has only finitely many actions, and the payoffs are uniformly bounded and Borel measurable as functions on the histories of play. We demonstrate an example of a recursive two-person non-zero-sum normal stochastic game with only three non-absorbing states and limit average payoffs that is not valued (but does have ε equilibria for every positive ε). In this respect two-person non-zero-sum stochastic games are very different from their zero-sum varieties. N. Vieille proved that all such non-zero-sum games with finitely many states have an ε equilibrium for every positive ε, and our example shows that any proof of this result must be qualitatively different from the existence proofs for zero-sum games. To show that our example is not valued we need that the existence of ε equilibria for all positive ε implies a “perfection” property. Should there exist a normal stochastic game without an ε equilibrium for some ε>0, this perfection property may be useful for demonstrating this fact. Furthermore, our example sews some doubt concerning the existence of ε equilibria for two-person non-zero-sum recursive normal stochastic games with countably many states. This research was supported financially by the German Science Foundation (Deutsche Forschungsgemeinschaft) and the Center for High Performance Computing (Technical University, Dresden). The author thanks Ulrich Krengel and Heinrich Hering for their support of his habilitation at the University of Goettingen, of which this paper is a part.     

Equilibrium points of nonatomic games over a nonreflexive Banach space

Schmeidler's results on the equilibrium points of nonatomic games with strategy sets in Euclidean n-space are generalized to nonatomic games with stategy sets in a separable Banach space whose dual possesses the Radon-Nikodým property.     

Denumerable state stochastic games with limiting average payoff

We study stochastic games with countable state space, compact action spaces, and limiting average payoff. ForN-person games, the existence of an equilibrium in stationary strategies is established under a certain Liapunov stability condition. For two-person zero-sum games, the existence of a value and optimal strategies for both players are established under the same stability condition.The authors wish to thank Prof. T. Parthasarathy for pointing out an error in an earlier version of this paper. M. K. Ghosh wishes to thank Prof. A. Arapostathis and Prof. S. I. Marcus for their hospitality and support.     

Take-and-guess games

This paper studies two classes of two-person zero-sum games in which the strategies of both players are of a special type. Each strategy can be split into two parts, a taking and a guessing part. In these games two types of asymmetry between the players can occur. In the first place, the number of objects available for taking does not need to be the same for both players. In the second place, the players can be guessing sequentially instead of simultaneously; the result is asymmetric information. The paper studies the value and equilibria of these games, for all possible numbers of objects available to the players, for the case with simultaneous guessing as well as for the variant with sequential guessing.      

The Compromise Value for Cooperative Games with Random Payoffs

This paper introduces and studies the compromise value for cooperative games with random payoffs, that is, for cooperative games where the payoff to a coalition of players is a random variable. This value is a compromise between utopia payoffs and minimal rights and its definition is based on the compromise value for NTU games and the τ-value for TU games. It is shown that the nonempty core of a cooperative game with random payoffs is bounded by the utopia payoffs and the minimal rights. Consequently, for such games the compromise value exists. Further, we show that the compromise value of a cooperative game with random payoffs coincides with the τ-value of a related TU game if the players have a certain type of preferences. Finally, the compromise value and the marginal value, which is defined as the average of the marginal vectors, coincide on the class of two-person games. This results in a characterization of the compromise value for two-person games.I thank Peter Borm, Ruud Hendrickx and two anonymous referees for their valuable comments.     

Characterizing properties of the value function of stochastic games

In the present note, the axiomatic characterization of the value function of two-person, zero-sum games in normal form by Vilkas and Tijs is extended to the value function of discounted, two-person, zero-sum stochastic games. The characterizing axioms can be indicated by the following terms: objectivity, monotony, and sufficiency for both players; or sufficiency for one of the players and symmetry. Also, a characterization without using the monotony axiom is given.