A polytopic game

We consider a discrete-time linear dynamic game instate-space form where the actions of two players are confined to belong to prescribed convex polytopes at all times. Each player has a "home set", a polyhedral domain in state space, and should devise a cooperative or a non-cooperative strategy (contingent on the known initial state) to reach her own home set in a finite number of steps and stay there, irrespective of the action taken by the opponent. Players act independently on the basis of the state at each time, using feedback strategies. Purpose of the analysis is to classify the set of initial states into winning-sets and draw-sets for each player, and prescribe strategies able to implement the kind of invariance home sets should enjoy. In the paper necessary and sufficient conditions for the existence of invariant sets with the above properties are derived. These conditions and the relative strategies are characterized in terms of linear programming problems that provide a straightforward algorithmic solution to the game. (C) 2000 Elsevier Science Ltd. All rights reserved.