On a linear pursuit game with an unknown trap

A linear pursuit game with a trap, the location of which is unknown to the evader, is defined and investigated. The cases in which one of the players has complete energy dominance over his adversary are solved completely. In the general case, when no player dominates, the solution is indicated for the two-stage game.This research was supported in part by the Technion Fund for promotion of research.     

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.     

Analysis of a combat problem: The turret game

The turret game is defined and solved to illustrate the nature of games of combat. This game represents a highly simplified version of air combat, yet it is sufficiently complex so as to exhibit a rich variety of combat phenomena. A review of the formulation of -combat games is included in this paper.on sabbatical leave from Technion, Israel Institute of Technology, Haifa, Israel.     

On games corresponding to sequencing situations with ready times

This paper considers the special class of cooperative sequencing games that arise from one-machine sequencing situations in which all jobs have equal processing times and the ready time of each job is a multiple of the processing time.By establishing relations between optimal orders of subcoalitions, it is shown that each sequencing game within this class is convex.This author is financially supported by the Dutch Organization for Scientific Research (NWO).     

Two-dimensional pursuit-evasion game with penalty on turning rates

An approach, both analytical and numerical, is used to solve a two-dimensional pursuit-evasion game characterized by a difficulty level intermediate between that of thesimple motion game (with freely and instantaneously oriented velocities) and that of thegame of two cars (with lower bounds on curvature radii). Each player's velocity has a constant modulus. The maneuvers are penalized by introducing, in the performance index, an integral term for the squared velocity turning rate.The local problem solution is relatively easy to find: the equations of motion and the adjoint equations can be integrated by means of elliptic functions and integrals. The global problem is more delicate to solve, because of the existence of a dispersal singular surface requiring an important numerical search to be determined. Thesynthesis problem (how to express the optimal strategies as functions of state) is not explicitly solvable, but a numerical approach using successive approximations can be developed. Illustrative interception trajectories are given.The authors are grateful to Mr. J. P. Peltier, Head, Guidance Group, Aerospace Mechanics Division, Systems Department, ONERA, Châtillon, France, for his suggestions and his efficient assistance in the numerical aspect of this study.     

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.     

Control of an aircraft landing in windshear

The problem of the feedback control of an aircraft landing in the presence of windshear is considered. The landing process is investigated up to the time when the runway threshold is reached. It is assumed that the bounds on the wind velocity deviations from some nominal values are known, while information about the windshear location and wind velocity distribution in the windshear zone is absent. The methods of differential game theory are employed for the control synthesis.The complete system of aircraft dynamic equations is linearized with respect to the nominal motion. The resulting linear system is decomposed into subsystems describing the vertical (longitudinal) motion and lateral motion. For each subsystem, an, auxiliary antagonistic differential game with fixed terminal time and convex payoff function depending on two components of the state vector is formulated. For the longitudinal motion, these components are the vertical deviation of the aircraft from the glide path and its time derivative; for the lateral motion, these components are the lateral deviation and its time derivative. The first player (pilot) chooses the control variables so as to minimize the payoff function; the interest of the second player (nature) in choosing the wind disturbance is just opposite.The linear differential games are solved on a digital computer with the help of corresponding numerical methods. In particular, the optimal (minimax) strategy is obtained for the first player. The optimal control is specified by means of switch surfaces having a simple structure. The minimax control designed via the auxiliary differential game problems is employed in connection with the complete nonlinear system of dynamical equations.The aircraft flight through the wind downburst zone is simulated, and three different downburst models are used. The aircraft trajectories obtained via the minimax control are essentially better than those obtained by traditional autopilot methods.     

Formulation and analysis of combat problems as zero-sum bicriterion differential games

In this paper, we present a formulation and analysis of a combat game between two players as a zero-sum bicriterion differential game. Each player's twin objectives of terminating the game on his own target set, while simultaneously avoiding his opponent's target set, are quantified in this approach. The solution in open-loop pure strategies is sought from among the Pareto-optimal security strategies of the players. A specific preference ordering on the outcomes is used to classify initial events in the assured win, draw, and mutual kill regions for the players. The method is compared with the event-constrained differential game approach, recently proposed by others. Finally, a simple example of the turret game is solved to illustrate the use of this method.     

A basic searchlight game

A searchlight game is a two-person zero-sum dynamic game of the pursuit-evasion type in which at least one of the two players has a searchlight. A searchlight can be flashed a given number of times within a fixed time period and the objective is to catch the opponent in the region illuminated by the flash. Olsder and Papavassilopoulos instituted the study of these games and, in this paper, we supplement their results, obtaining a closed formula for the value and optimal strategies for the players in their basic game.     

Totally monotonic games and flow games

Equivalences between totally balanced games and flow games, and between monotonic games and pseudoflow games are well-known. This paper shows that for every totally monotonic game there exists an equivalent flow game and that for every monotonic game, there exists an equivalent flow-based secondary market game.     

Accumulation Games,Part 1: Noisy Search

In an accumulation game, a hider places objects at locations, and a seeker examines these locations. If the seeker discovers an object, the seeker confiscates it. The goal of the hider is to accumulate a certain number of objects before a given time, and the goal of the seeker is to prevent this. In this paper, we first classify various possible variations on the accumulation game. Next, we discuss the so-called noisy accumulation game in which the hider can observe each action of the seeker. We present the solution of this game for all but some marginal cases and illustrate it with computational examples.     

Pricing problems with a continuum of customers as stochastic Stackelberg games

The pricing problem where a company sells a certain kind of product to a continuum of customers is considered. It is formulated as a stochastic Stackelberg game with nonnested information structure. The inducible region concept, recently developed for deterministic Stackelberg games, is extended to treat the stochastic pricing problem. Necessary and sufficient conditions for a pricing scheme to be optimal are derived, and the pricing problem is solved by first delineating its inducible region, and then solving a constrained optimal control problem.The research work reported here as supported in part by the National Science Foundation under Grant ECS-81-05984, Grant ECS-82-10673, and by the Air Force Office of Scientific Research under AFOSR Grant 80-0098.     

Different ways to represent weighted majority games

It is well known that every simple game is the intersection of weighted majority games. the aim of this paper is to gather together various ways of expressing weighted majority games and, for each game of this type, to give the simplest way to define it. Normalized representations, the parameters of a simple game and the characteristic invariants of a complete game merit special attention. Research partially supported by projects PR9509 of the Polytechnic University of Catalonia and PB96-0493 of DGES     

How to Distribute Costs Associated with a Delayed Project

In this paper we study how to distribute the cost caused by the delay of a project among the firms which are responsible for it. We present two rules, one based on serial cost sharing problems and the other, in game theory. Moreover, we introduce some desirable properties, inspired by well-known principles, and study which of them are satisfied by the rules.     

Crowding games are sequentially solvable

A sequential-move version of a given normal-form game Γ is an extensive-form game of perfect information in which each player chooses his action after observing the actions of all players who precede him and the payoffs are determined according to the payoff functions in Γ. A normal-form game Γ is sequentially solvable if each of its sequential-move versions has a subgame-perfect equilibrium in pure strategies such that the players' actions on the equilibrium path constitute an equilibrium of Γ.  A crowding game is a normal-form game in which the players share a common set of actions and the payoff a particular player receives for choosing a particular action is a nonincreasing function of the total number of players choosing that action. It is shown that every crowding game is sequentially solvable. However, not every pure-strategy equilibrium of a crowding game can be obtained in the manner described above. A sufficient, but not necessary, condition for the existence of a sequential-move version of the game that yields a given equilibrium is that there is no other equilibrium that Pareto dominates it. Received July 1997/Final version May 1998     

Learning algorithms for repeated bimatrix Nash games with incomplete information

The purpose of this paper is to study a particular recursive scheme for updating the actions of two players involved in a Nash game, who do not know the parameters of the game, so that the resulting costs and strategies converge to (or approach a neighborhood of) those that could be calculated in the known parameter case. We study this problem in the context of a matrix Nash game, where the elements of the matrices are unknown to both players. The essence of the contribution of this paper is twofold. On the one hand, it shows that learning algorithms which are known to work for zero-sum games or team problems can also perform well for Nash games. On the other hand, it shows that, if two players act without even knowing that they are involved in a game, but merely thinking that they try to maximize their output using the learning algorithm proposed, they end up being in Nash equilibrium.This research was supported in part by NSF Grant No. ECS-87-14777.     

A dynamic transfer scheme deriving from the dual similar associated game

Dynamic process is an approach to cooperative games, and it can be defined as that which leads the players to a solution for cooperative games. Hwang et al. (2005) adopted Hamiache’s associated game (2001) to provide a dynamic process leading to the Shapley value. In this paper, we propose a dynamic transfer scheme on the basis of the dual similar associated game, to lead to any solution satisfying both the inessential game property and continuity, starting from an arbitrary efficient payoff vector.     

Buyer-seller exactness in the assignment game

In the assignment game framework, we try to identify those assignment matrices in which no entry can be increased without changing the core of the game. These games will be called buyer-seller exact games and satisfy the condition that each mixed-pair coalition attains the corresponding matrix entry in the core of the game. For a given assignment game, a unique buyer-seller exact assignment game with the same core is proved to exist. In order to identify this matrix and to provide a characterization of those assignment games which are buyer-seller exact in terms of the assignment matrix, attainable upper and lower core bounds for the mixed-pair coalitions are found. As a consequence, an open question posed in Quint (1991) regarding a canonical representation of a “45^o-lattice” by means of the core of an assignment game can now be answered. Received: March 2002/Revised version: January 2003 RID="*" ID="*"  Institutional support from research grants BEC 2002-00642 and SGR2001-0029 is gratefully acknowledged RID="**" ID="**"  The authors thank the referees for their comments     

Effort Games and the Price of Myopia

We consider Effort Games, a game‐theoretic model of cooperation in open environments, which is a variant of the principal‐agent problem from economic theory. In our multiagent domain, a common project depends on various tasks; carrying out certain subsets of the tasks completes the project successfully, while carrying out other subsets does not. The probability of carrying out a task is higher when the agent in charge of it exerts effort, at a certain cost for that agent. A central authority, called the principal, attempts to incentivize agents to exert effort, but can only reward agents based on the success of the entire project. We model this domain as a normal form game, where the payoffs for each strategy profile are defined based on the different probabilities of carrying out each task and on the boolean function that defines which task subsets complete the project, and which do not. We view this boolean function as a simple coalitional game, and call this game the underlying coalitional game. We suggest the Price of Myopia (PoM) as a measure of the influence the model of rationality has on the minimal payments the principal has to make in order to motivate the agents in such a domain to exert effort. We consider the computational complexity of testing whether exerting effort is a dominant strategy for an agent, and of finding a reward strategy for this domain, using either a dominant strategy equilibrium or using iterated elimination of dominated strategies. We show these problems are generally #P‐hard, and that they are at least as computationally hard as calculating the Banzhaf power index in the underlying coalitional game. We also show that in a certain restricted domain, where the underlying coalitional game is a weighted voting game with certain properties, it is possible to solve all of the above problems in polynomial time. We give bounds on PoM in weighted voting effort games, and provide simulation results regarding PoM in another restricted class of effort games, namely effort games played over Series‐Parallel Graphs (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)