Quitting games – An example

Quitting games are multi-player sequential games in which, at every stage, each player has the choice between continuing and quitting. The game ends as soon as at least one player chooses to quit; each player i then receives a payoff r _S ⁱ, which depends on the set S of players that did choose to quit. If the game never ends, the payoff to each player is zero.? We exhibit a four-player quitting game, where the “simplest” equilibrium is periodic with period two. We argue that this implies that all known methods to prove existence of an equilibrium payoff in multi-player stochastic games are therefore bound to fail in general, and provide some geometric intuition for this phenomenon. Received: October 2001     

A consistent value for games with n players and r alternatives

In Bolger [1993], an efficient value was obtained for a class of games called games with n players and r alternatives. In these games, each of the n players must choose one and only one of the r alternatives. This value can be used to determine a player’s “a priori” value in such a game. In this paper, we show that the value has a consistency property similar to the “consistency” for TU games in Hart/Mas-Colell [1989] and we present a set of axioms (including consistency) which characterizes this value.  The games considered in this paper differ from the multi-choice games considered by Hsiao and Raghavan [1993]. They consider games in which the actions of the players are ordered in the sense that, if i >j, then action i carries more “weight” than action j.  These games also differ from partition function games in that the worth of a coalition depends not only on the partitioning of the players but also on the action chosen by each subset of the partition. Received: April 1994/final version: June 1999     

An alternative characterization of the weighted Banzhaf value

We provide a new characterization of the weighted Banzhaf value derived from some postulates in a recent paper by Radzik, Nowak and Driessen [7]. Our approach owes much to the work by Lehrer [4] on the classical Banzhaf value based on the idea of amalgamation of pairs of players and an induction construction of the value. Compared with the approach in [7] we consider two new postulates: a weighted version of Lehrer’s “2-efficiency axiom” [4] and a generalized “null player out” property studied in terms of symmetric games by Derks and Haller [2]. Received: December 1997/final version: October 1999     

A note on isomorphism and strategic equivalence of cooperative games

In this note, we will give several examples to illustrate that two essential games which are isomorphic are not necessarily S-equivalent when the cores of both games are “small” or empty. In other words, we show that whether two isomorphic games are S-equivalent can not be justified in terms of the “size” of the core.     

Structural stability and robustness to bounded rationality for non-compact cases

We study the model M consisting of “general games” with noncompact action space, together with an associated abstract rationality function. We prove that M is structurally stable and robust to ϵ-equilibria for “almost all” parameters. As applications, we investigate structural stability and robustness to bounded rationality for noncooperative games, multiobjective optimizations and fixed point problems satisfying existence and some continuity conditions. Specifically, we introduce concrete rationality functions for such three kinds of problems with both payoffs and strategy sets, objective functions and domain spaces, and correspondence and domain spaces as parameters, respectively, and show the generic structural stability and robustness to bounded rationality for the corresponding model Ms.     

Qualitative analysis of secured outcome regions for two-target games

Qualitative (game of kind) outcomes of two-target games are analyzed in this paper, under both the zero-sum and nonzero-sum preference ordering of outcomes by the players. The outcome regions of each player are defined from a security standpoint. The secured draw and mutual-kill regions of a player depend explicitly on his preference ordering of outcomes and should be constructed separately for each player, especially in a nonzero-sum game. General guidelines are presented for identifying the secured outcome regions of players in a class of two-target games that satisfy an Isaacs-like condition, in terms of the qualitative solutions of the two underlying single-target pursuit-evasion games. A construction has been proposed for obtaining the qualitative solution of a large class of two-target games. Illustrative examples are included.This work was done while the first author was a Research Associate in the Department of Electrical Engineering at the Indian Institute of Science, Bangalore, and was financially supported by the Council of Scientific and Industrial Research, Delhi, India.     

Combat games

We propose a mathematical formulation of a combat game between two opponents with offensive capabilities and offensive objectives. Resolution of the combat involves solving two differential games with state constraints. Depending on the game dynamics and parameters, the combat can terminate in one of four ways: (i) the first player wins, (ii) the second player wins, (iii) a draw (neither wins), or (iv) joint capture. In the first two cases, the optimal strategies of the two players are determined from suitable zero-sum games, whereas in the latter two the relevant games are nonzero-sum. Further, to avoid certain technical difficulties, the concept of a -combat game is introduced.Dedicated to G. LeitmannThe first author wishes to acknowledge the friendship and guidance of George Leitmann, beginning in the author's student days at Berkeley and continuing to the present time. All the authors thank George Leitmann for many recent fruitful discussions on differential games.on sabbatical leave from Technion, Israel Institute of Technology, Haifa, Israel.     

Game theoretical optimization inspired by information theory

Inspired by previous work on information theoretical optimization problems, the basics of an axiomatic theory of certain special two-person zero-sum games is developed. One of the players, “Observer”, is imagined to have a “mind”, the other, “Nature”, not. These ideas lead to un-symmetric modeling as the two players are treated quite differently. Basic concavity- and convexity results as well as a general minimax theorem are derived from the axioms.     

On the existence of a minimum integer representation for?weighted voting systems

A basic problem in the theory of simple games and other fields is to study whether a simple game (Boolean function) is weighted (linearly separable). A second related problem consists in studying whether a weighted game has a minimum integer realization. In this paper we simultaneously analyze both problems by using linear programming. For less than 9 voters, we find that there are 154 weighted games without minimum integer realization, but all of them have minimum normalized realization. Isbell in 1958 was the first to find a weighted game without a minimum normalized realization, he needed to consider 12 voters to construct a game with such a property. The main result of this work proves the existence of weighted games with this property with less than 12 voters. This research was partially supported by Grant MTM 2006-06064 of “Ministerio de Ciencia y Tecnología y el Fondo Europeo de Desarrollo Regional” and SGRC 2005-00651 of “Generalitat de Catalunya”, and by the Spanish “Ministerio de Ciencia y Tecnología” programmes ALINEX (TIN2005-05446 and TIN2006-11345).     

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.     

A game-theoretic taxonomy of social dilemmas

Both social psychology and experimental economics empirically investigate social dilemmas. However, these two disciplines sometimes use different notions for very similar scenarios. While it is irrelevant for economists whether an experimental public-good game is conceptualised as a take-some or give-some game – i.e., whether something is conceptualised as produced or extracted – it is not irrelevant for some psychologists: they grasp public-goods games as “give-some” games. And whereas most economists define social dilemmas in reference to a taxonomy of goods, some psychologists think that dominant strategies are a necessary attribute. This paper presents a taxonomy that relies on a formal game-theoretic analysis of social dilemmas, which integrates and clarifies both approaches. Because this taxonomy focuses on the underlying incentive structure, it facilitates the evaluation of experimental results from both social psychology and experimental economics.     

Open-Loop Viable Control Under Uncertain Initial State Information

We consider the problem of open-loop viable control of a nonlinear system in Rⁿ in the case of a nonexactly known initial state. We characterize the family of those initial sets for which the problem is solvable. The characterization employs the notion of a contingent field to a given collection of sets introduced in the paper. It also involves an appropriate set-dynamic equation that describes the evolution of the state estimation within a prescribed collection of sets. An extension of the classical concept of viability kernel with respect to this set-dynamic equation is the key tool. We present an approximation scheme for the viability kernel which is numerically realizable in the case of low dimension and simple collections of sets chosen for state estimation (balls, ellipsoids, polyhedrons, etc.). As an application, we consider a viability differential game, where the uncertainty may enter also in the dynamics of the system as an input which is not known in advance. The control is then sought as a nonanticipative strategy depending on the uncertain input.     

The unit-level-core for multi-choice games: the replicated core for TU games

This note extends the solution concept of the core for traditional transferable-utility (TU) games to multi-choice TU games, which we name the unit-level-core. It turns out that the unit-level-core of a multi-choice TU game is a “replicated subset” of the core of a corresponding “replicated” TU game. We propose an extension of the theorem of Bondareva (Probl Kybern 10:119–139, 1963) and Shapley (Nav Res Logist Q 14:453–460, 1967) to multi-choice games. Also, we introduce the reduced games for multi-choice TU games and provide an axiomatization of the unit-level-core on multi-choice TU games by means of consistency and its converse.     

Numerical integration of ordinary differential equations on manifolds

Summary This paper is concerned with the problem of developing numerical integration algorithms for differential equations that, when viewed as equations in some Euclidean space, naturally evolve on some embedded submanifold. It is desired to construct algorithms whose iterates also evolve on the same manifold. These algorithms can therefore be viewed as integrating ordinary differential equations on manifolds. The basic method “decouples” the computation of flows on the submanifold from the numerical integration process. It is shown that two classes of single-step and multistep algorithms can be posed and analyzed theoretically, using the concept of “freezing” the coefficients of differential operators obtained from the defining vector field. Explicit third-order algorithms are derived, with additional equations augmenting those of their classical counterparts, obtained from “obstructions” defined by nonvanishing Lie brackets.     

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.     

Proper rationalizability and backward induction

This paper introduces a new normal form rationalizability concept, which in reduced normal form games corresponding to generic finite extensive games of perfect information yields the unique backward induction outcome. The basic assumption is that every player trembles “more or less rationally” as in the definition of a ε-proper equilibrium by Myerson (1978). In the same way that proper equilibrium refines Nash and perfect equilibrium, our model strengthens the normal form rationalizability concepts by Bernheim (1984), B?rgers (1994) and Pearce (1984). Common knowledge of trembling implies the iterated elimination of strategies that are strictly dominated at an information set. The elimination process starts at the end of the game tree and goes backwards to the beginning. Received: October 1996/Final version: May 1999     

Viability property for a backward stochastic differential equation and applications to partial differential equations

In the present paper, we study conditions under which the solutions of a backward stochastic differential equation remains in a given set of constraints. This property is the so-called “viability property”. In a separate section, this condition is translated to a class of partial differential equations. Received: 23 April 1998 / Published online: 14 February 2000     

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     

Aircraft Take-Off in Windshear: A Viability Approach

This paper is devoted to the analysis of aircraft dynamics during tage-off in the presence of windshear. We formulate the take-off problem as a differential game against Nature. Here, the first player is the relative angle of attack of the aircraft (considered as the control variable) and the second player is the disturbance caused by a windshear. We impose state constraints on the state variables of the game, which represents aircraft safety constraints (minimum altitude, given altitude rate). By using viability theory, we address the question of existence of an open loop control assuring a viable trajectory (i.e. satisfying the state constraints) no matter the disturbance is, i.e. for all admissible disturbances causeed by the windshear. Through numerical simulations of the viability kernel algorithm, we demonstrate the capabilities of this approach for determining safe flight domains of an aircraft during take-off within windshear.     

Exploitation of natural resources and pollution

This paper provides some differential game models of natural resource exploitation when environmental pollution takes place. The classical approach to determine optimal harvest rates of renewable resources utilizes Optimal Control models, i.e. there is either a monopolistic market structure or there is pure competition. In case of pollution, however, all agents can be put together, forming the groups of the resource harvesters on one side and of polluters on the other side. So differential games can be used to analyze environmental problems. The models introduced in this paper are put together in order to showdifferent problems that can all be analyzed using differential games.