Markov Perfect Equilibrium Existence for a Class of Undiscounted Infinite-Horizon Dynamic Games

We prove the existence of Markov perfect equilibria (MPE) for nonstationary undiscounted infinite-horizon dynamic games with alternating moves. A suitable finite-horizon equilibrium relaxation, the ending state constrained MPE, captures the relevant features of an infinite-horizon MPE for a long enough horizon, under a uniformly bounded reachability assumption.     

Approximation of Noncooperative Semi-Markov Games

An approximation of a general V-ergodic semi-Markov game with Borel state space by discrete-state space strongly-ergodic games is studied. The standard expected ratio-average criterion as well as the expected time-average criterion are considered. New theorems on the existence of ∊-equilibria are given.Communicated by D. A. CarlsonThe authors thank an anonymous referee for constructive comments. This work is supported by MEiN Grant 1P03A 01030.     

Identification of Efficient Subgame-Perfect Nash Equilibria in a Class of Differential Games1

We present a method for the characterization of subgame-perfect Nash equilibria being Pareto efficient in a class of differential games. For that purpose, we propose a new approach based on new necessary and sufficient conditions for computing subgame-perfect Nash equilibria.     

Polytope Games

Starting from the definition of a bimatrix game, we restrict the pair of strategy sets jointly, not independently. Thus, we have a set , which is the set of all feasible strategy pairs. We pose the question of whether a Nash equilibrium exists, in that no player can obtain a higher payoff by deviating. We answer this question affirmatively for a very general case, imposing a minimum of conditions on the restricted sets and the payoff. Next, we concentrate on a special class of restricted games, the polytope bimatrix game, where the restrictions are linear and the payoff functions are bilinear. Further, we show how the polytope bimatrix game is a generalization of the bimatrix game. We give an algorithm for solving such a polytope bimatrix game; finally, we discuss refinements to the equilibrium point concept where we generalize results from the theory of bimatrix games.     

Learing from each other in a duopoly: Numerical approach

We consider a price-setting duopoly producing differentiated goods, where the players can learn by doing and from each other. The unit production cost is modelled as a decreasing function of accumulated knowledge. The game is noncooperative, played in a discrete time over an infinite horizon. Feedback Nash equilibrium strategies are sought. An algorithm to compute such equilibria is given, and ressults of numerical experiments concerned with symmetric and asymmetric duopolies are reported.This research was supported by the Natural Sciences and Engineering Research Council of Canada and the Centre d'Études en Administration Internationale, École des Hautes Études commerciales, Montréal, Canada. The authors wish to thank an anonymous referee for very helpful comments.     

Some Classes of Imperfect Information Finite State-Space Stochastic Games with Finite-Dimensional Solutions

Stochastic games under imperfect information are typically computationally intractable even in the discrete-time/discrete-state case considered here. We consider a problem where one player has perfect information. A function of a conditional probability distribution is proposed as an information state. In the problem form here, the payoff is only a function of the terminal state of the system, and the initial information state is either linear or a sum of max-plus delta functions. When the initial information state belongs to these classes, its propagation is finite-dimensional. The state feedback value function is also finite-dimensional, and obtained via dynamic programming, but has a nonstandard form due to the necessity of an expanded state variable. Under a saddle point assumption, Certainty Equivalence is obtained and the proposed function is indeed an information state.     

On the Tikhonov Well-Posedness of Concave Games and Cournot Oligopoly Games

The purpose of this paper is to investigate whether theorems known to guarantee the existence and uniqueness of Nash equilibria, provide also sufficient conditions for the Tikhonov well-posedness (T-wp). We consider several hypotheses that ensure the existence and uniqueness of a Nash equilibrium (NE), such as strong positivity of the Jacobian of the utility function derivatives (Ref. 1), pseudoconcavity, and strict diagonal dominance of the Jacobian of the best reply functions in implicit form (Ref. 2). The aforesaid assumptions imply the existence and uniqueness of NE. We show that the hypotheses in Ref. 2 guarantee also the T-wp property of the Nash equilibrium.As far as the hypotheses in Ref. 1 are concerned, the result is true for quadratic games and zero-sum games. A standard way to prove the T-wp property is to show that the sets of -equilibria are compact. This last approach is used to demonstrate directly the T-wp property for the Cournot oligopoly model given in Ref. 3. The compactness of -equilibria is related also to the condition that the best reply surfaces do not approach each other near infinity.     

Static and Dynamic Equilibria in Games With Continuum of Players

This paper is a study of a general class of deterministic dynamic games with an atomless measure space of players and an arbitrary time space. The payoffs of the players depend on their own strategy, a trajectory of the system and a function with values being finite dimensional statistics of static profiles. The players' available decisions depend on trajectories of the system.The paper deals with relations between static and dynamic open-loop equilibria as well as their existence. An equivalence theorem is proven and theorems on the existence of a dynamic equilibrium are shown as consequences.     

Enumeration of All the Extreme Equilibria in Game Theory: Bimatrix and Polymatrix Games

Bimatrix and polymatrix games are expressed as parametric linear 0–1 programs. This leads to an algorithm for the complete enumeration of their extreme equilibria, which is the first one proposed for polymatrix games. The algorithm computational experience is reported for two and three players on randomly generated games for sizes up to 14 × 14 and 13 × 13 × 13.Communicated by P. M. PardalosThe authors thank Bernhard von Stengel for constructive comments on the contents of this paper.     

Existence of nash equilibria for constrained stochastic games

In this paper, we consider constrained noncooperative N-person stochastic games with discounted cost criteria. The state space is assumed to be countable and the action sets are compact metric spaces. We present three main results. The first concerns the sensitivity or approximation of constrained games. The second shows the existence of Nash equilibria for constrained games with a finite state space (and compact actions space), and, finally, in the third one we extend that existence result to a class of constrained games which can be “approximated” by constrained games with finitely many states and compact action spaces. Our results are illustrated with two examples on queueing systems, which clearly show some important differences between constrained and unconstrained games.Mathematics Subject Classification (2000): Primary: 91A15. 91A10; Secondary: 90C40     

On Existence of Nash Equilibria of Games with Constraints on Multistrategies

In this paper, sufficient conditions are given, which are less restrictivethan those required by the Arrow–Debreu–Nash theorem, on theexistence of a Nash equilibrium of an n-player game {₁, . . . , Y_n,f₁, . . . , f_n} in normal form with a nonempty closedconvex constraint C on the set Y=i Y_i of multistrategies. Theith player has to minimize the function fi with respect to the ithvariable. We consider two cases.In the first case, Y is a real Hilbert space and the loss function class isquadratic. In this case, the existence of a Nash equilibrium is guaranteedas a simple consequence of the projection theorem for Hilbert spaces. In thesecond case, Y is a Euclidean space, the loss functions are continuous, andf_i is convex with respect to the ith variable. In this case, the techniqueis quite particular, because the constrained game is approximated with asequence of free games, each with a Nash equilibrium in an appropriatecompact space X. Since X is compact, there exists a subsequence of theseNash equilibrium points which is convergent in the norm. If thelimit point is in C and if the order of convergence is greater than one,then this is a Nash equilibrium of the constrained game.     

On the Selection of One Feedback Nash Equilibrium in Discounted Linear-Quadratic Games

We study a selection method for a Nash feedback equilibrium of a one-dimensional linear-quadratic nonzero-sum game over an infinite horizon. By introducing a change in the time variable, one obtains an associated game over a finite horizon T > 0 and with free terminal state. This associated game admits a unique solution which converges to a particular Nash feedback equilibrium of the original problem as the horizon T goes to infinity.     

Linear Transformation of Products: Games and Economies

In this paper, we introduce situations involving the linear transformation of products (LTP). LTP situations are production situations where each producer has a single linear transformation technique. First, we approach LTP situations from a (cooperative) game theoretical point of view. We show that the corresponding LTP games are totally balanced. By extending an LTP situation to one where a producer may have more than one linear transformation technique, we derive a new characterization of (nonnegative) totally balanced games: each totally balanced game with nonnegative values is a game corresponding to such an extended LTP situation. The second approach to LTP situations is based on a more economic point of view. We relate (standard) LTP situations to economies in two ways and we prove that the economies are standard exchange economies (with production). Relations between the equilibria of these economies and the cores of cooperative LTP games are investigated.     

Probabilities of Pure Nash Equilibria in Matrix Games when the Payoff Entries of One Player Are Randomly Selected

The Nash equilibrium in pure strategies represents an important solution concept in nonzero sum matrix games. Existence of Nash equilibria in games with known and with randomly selected payoff entries have been studied extensively. In many real games, however, a player may know his own payoff entries but not the payoff entries of the other player. In this paper, we consider nonzero sum matrix games where the payoff entries of one player are known, but the payoff entries of the other player are assumed to be randomly selected. We are interested in determining the probabilities of existence of pure Nash equilibria in such games. We characterize these probabilities by first determining the finite space of ordinal matrix games that corresponds to the infinite space of matrix games with random entries for only one player. We then partition this space into mutually exclusive spaces that correspond to games with no Nash equilibria and with r Nash equilibria. In order to effectively compute the sizes of these spaces, we introduce the concept of top-rated preferences minimal ordinal games. We then present a theorem which provides a mechanism for computing the number of games in each of these mutually exclusive spaces, which then can be used to determine the probabilities. Finally, we summarize the results by deriving the probabilities of existence of unique, nonunique, and no Nash equilibria, and we present an illustrative example.     

Feedback Solution of a Class of Differential Games with Endogenous Horizons

In this paper, we consider a class of differential games in which the game ends when a subset of its state variables reaches a certain target at the terminal time. A special feature of the game is that its horizon is not fixed at the outset, but is determined endogenously by the actions of the players; conditions characterizing a feedback Nash equilibrium (FNE) solution of the game are derived for the first time. Extensions and illustrations of the derivation of FNE solutions of the game are provided.     

Harnack's Inequality for p-Harmonic Functions via Stochastic Games

We give a proof of asymptotic Lipschitz continuity of p-harmonious functions, that are tug-of-war game analogies of ordinary p-harmonic functions. This result is used to obtain a new proof of Lipschitz continuity and Harnack's inequality for p-harmonic functions in the case p > 2. The proof avoids classical techniques like Moser iteration, but instead relies on suitable choices of strategies for the stochastic tug-of-war game.     

A Class of Solvable Stopping Games

We consider a class of Dynkin games in the case where the underlying process evolves according to a one-dimensional but otherwise general diffusion. We establish general conditions under which both the value and the saddle point equilibrium exist and under which the exercise boundaries characterizing the saddle point strategy can be explicitly characterized in terms of a pair of standard first order necessary conditions for optimality. We also analyze those cases where an extremal pair of boundaries exists and investigate the overall impact of increased volatility on the equilibrium stopping strategies and their values.     

Infinite-Horizon Stochastic Differential Games with Branching Payoffs

In this paper, we consider infinite-horizon stochastic differential games with an autonomous structure and steady branching payoffs. While the introduction of additional stochastic elements via branching payoffs offers a fruitful alternative to modeling game situations under uncertainty, the solution to such a problem is not known. A theorem on the characterization of a Nash equilibrium solution for this kind of games is presented. An application in renewable resource extraction is provided to illustrate the solution mechanism.     

Noncooperative stochastic games under a n-stage local contraction assumption

We consider a class of noncooperative stochastic games with general state and action spaces and with a state dependent discount factor. The expected time duration between any two stages of the game is not bounded away from zero, so that the usual N-stage contraction assumption, uniform over all admissible strategies, does not hold. We propose milder sufficient regularity conditions, allowing strategies that give rise with probability one to any number of simultaneous stages. We give sufficient conditions for the existence of equilibrium and ∈-equilibrium stationary strategies in the sense of Nash. In the two-player zero-sum case, when an equilibrium strategy exists, the value of the game is the unique fixed point of a specific functional operator and can be computed by dynamic programming.     

动态需求背景下两阶段供应链博弈分析

在两阶段供应链中,市场营销也会导致需求的变动.引入营销费用与零售价格共同影响市场需求,并假设卖方决定订货批量,分别从非合作博弈和合作博弈两个角度对两阶段供应链管理问题进行分析.非合作博弈分析的是卖方或买方分别作为领导者时的Stackelberg模型;合作博弈是把卖方和买方的利润函数加权后作为目标函数,求出了帕累托最优解.结果证明,在合作博弈中存在帕累托有效解,与非合作博弈相比,合作博弈的订货批量更小,零售价格更低,市场营销费用更少.并列举案例,对模型中主要参数进行敏感性分析.