Dmitrii Lozovanul

Stefan Pickl
email: stefan.pickl@unibw.de

Multilayered Decision Problems

Keywords: Dimitrii Lozovanul, Stefan Decision Theory, c-Game, Layered Network

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction -The General Model

In the following we describe the general underlying model for our decision problem. This is a short summary. For details we refer to [START_REF] Lozovanu | Polynomial Time Algorithms for Determining Optimal Strategies[END_REF][START_REF] Lozovanu | Dynamic games with p players on networks[END_REF].

Let L be a discrete dynamical system with the set of states X ⊆ R m . At every timestep t = 0, 1, 2 . . . the state of L is x(t) ∈ X. Two states x 0 and x f are given in X, where x 0 = x(0) represents the starting point of L and x f is the state into which the system L must be brought, i.e. x f is the final state of L. We assume that the system L reaches the final state x f at the time step T (x f ) such that

T 1 ≤ T (x f ) ≤ T 2 ,
where T 1 and T 2 are given. The dynamics of the system are described as follows x(t + 1) = g t (x(t), u(t)), t = 0, 1, 2, . . . where

x(0) = x 0 and u(t) ∈ R m represents the vector of control parameters.

For u(t) at any time step t let there be given a nonempty set U t (x(t)) such that

u(t) ∈ U t (x(t)), t = 0, 1, 2, . . . , (1)
i.e. U t (x(t)) is the admissible (decision) set for vector of control parameters at the timestep t when the state of system L is x = x(t) ∈ X. We assume that the derivatives g t (x(t), u(t)) are known and uniquely determine x(t + 1) for given x(t) and u(t) at every moment of time t = 0, 1, 2, . . . . In addition we assume that at each point in time t the cost c t (x(t), x(t + 1)) is known with c t (x(t), x(t + 1)) = c t (x(t), g t (x(t), u(t))) of system's passage from the state x(t) to the state x(t + 1).

Let

x 0 = x(0), x(1), x(2), . . . , x(t), . . . be the trajectory generated by given vectors of control parameters u(0), u(1), . . . , u(t -1), . . . .

Either this trajectory passes through the state x f at time T (x f ) or it does not pass through x f . By

F x 0 x f (u(t)) = T (x f )-1 t=0 c t (x(t), g t (x(t), u(t))) (2)
we denote the integral-time cost of system's passage from

x 0 to x f if T 1 ≤ T (x f ) ≤ T 2 ; otherwise we stipulate F x 0 x f (u(t)) = ∞.

Multiobjective Control Problem

The multiobjective control problem is defined in the following way: Minimize the function F x 0 x f (u(t)) which is defined by (2) according to [START_REF] Krabs | Analysis, Controllability and Optimization of Time-Discrete Systems and Dynamical Games[END_REF]. Thus, we consider the discrete control problem which consists of cases with a fixed number of stages (T 1 = T 2 ) and the number of stages is not limited

(T 1 = 1, T 2 = ∞).
Before we deal with the decision problem we introduce in the following section the special structure of Nash equilibria.

Problem Formulation for Determining a Nash Equilibrium

In order to characterize suitable Nash equilibria we consider the dynamic system L over discrete moments in time t = 0, 1, 2, . . . . At every time-step t the state of this L is x(t) ∈ X ⊆ R m . The dynamics of the system L are controlled by p players and it is described as follows

x(t + 1) = g t (x(t), u 1 (t), u 2 (t), . . . , u p (t)), t = 0, 1, 2, . . . . (3)
Here x(0) = x 0 is the starting point of the system L and u i (t) ∈ R m i represents the vectors of control parameters of player i, i ∈ {1, 2, . . . , p}. The state x(t + 1) of the system L at time-step t+1 is obtained uniquely if the state x(t) at the time-step t is known and the players 1, 2, . . . , p fix their vectors of control parameters u 1 (t), u 2 (t), . . . , u p (t), respectively. For each player i, i ∈ {1, 2, . . . , p} the admissible sets U i t (x(t)) for the vectors of control parameters u i (t) are given, i.e.

u i (t) ∈ U i t (x(t)), t = 0, 1, 2, . . . ; i = 1, p.
We assume that U i t (x(t + 1)), t = 0, 1, 2, . . . ; i = 1, p, are non-empty finite sets and that

U i t (x(t)) ∩ U j t (x(t)) = ∅, i = j, t = 0, 1, 2, . . .
We assume that the players 1, 2, . . . , p fix their vectors of control parameters u 1 (t), u 2 (t), . . . , u p (t); t = 0, 1, 2, . . . , respectively, and the starting state x 0 and final state x f of the system L are known. Then for fixed vectors of control parameters u 1 (t), u 2 (t), . . . , u p (t) either a unique trajectory x 0 = x(0), x(1), x(2), . . . , x(T (x f )) = x f from x 0 to x f exists and T (x f ) represents the time-moment when the state x f is reached, or such trajectory from x 0 to x f does not exist. We denote by

F i x 0 x f (u 1 (t), u 2 (t), . . . , u p (t)) = T -1 t=0 c i t (x(t), g t (x(t), u 1 (t), u 2 (t), . . . , u p (t)))
the integral-time cost of system's passage from x 0 to x f for the player i, i ∈ {1, 2, . . . , p} if the vectors u 1 (t), u 2 (t), . . . .u p (t) generate a trajectory

x 0 = x(0), x(1), x(2), . . . , x(T (x f )) = x f from x 0 to x f such that u i (t) ∈ U i t (x(t)), t = 0, 1, 2, . . . , T (x f ) -1,
and

T 1 ≤ T (x f ) ≤ T 2 .
Otherwise we stipulate

F i x 0 x f (u 1 (t), u 2 (t), . . . , u p (t)) = ∞.
Note that c i t (x(t), g t (x(t), u 1 (t), u 2 (t), . . . , u p (t))) = c i t (x(t), x(t + 1)) represent the costs of the system's passage from the state x(t) to the state x(t + 1) at the stage [t, t + 1] for the player i. Then we obtain the following problem on networks:

Problem: Decison Problem on Networks

If we find vectors of control parameters

u 1 * (t), u 2 * (t), . . . , u i-1 * (t), u i * (t), u i+1 * (t), . . . , u p * (t)
which satisfy the following condition

F i x 0 x f (u 1 * (t), u 2 * (t), . . . , u i-1 * (t), u i * (t), u i+1 * (t), . . . , u p * (t)) ≤ ≤ F i x 0 x f (u 1 * (t), u 2 * (t), . . . , u i-1 * (t), u i (t), u i+1 * (t), . . . , u p * (t)) ∀ u i (t) ∈ R m i , t = 0, 1, 2. . . . ; i = 1, p
(the expression i = 1, p is equivalent to i = {1, . . . , p}.), then we get a solution in the sense of Nash for our control problem on a network. In the following we present a sketch of the algorithmic principle.

Algorithmic Determination -Layered Structure

If we search for an suitable algorithmic principle we can orientate on similar problems of shortest path on a network. For that reason we present an application of Dijkstra's algorithm for a multiobjective version of the optimal paths problem in a weighted directed graph. The algorithm is able to determine the stationary Pareto strategy s * ∈ S of the players for the multiobjective control problem on the network (G, X, c 1 , c 2 , . . . , c p , x 0 , x f , T 1 , T 2 ) with an arbitrary starting position x ∈ X and given final positions x f ∈ X. We then obtain a tree which obtains all Pareto optimal paths from every x ∈ X to x f .

Complexity Results

If we consider the following

INSTANCE: [Multiobjective Decision Problem]

Let L be a dynamic system with a finite set of states X, |X| = n. We interprete these states as nodes of a graph G(X, E) where X is now the set of nodes (i.e. the states of our dynamic system) and E is a set of edges which have the following property: At every discrete moment of time t = 0, 1, 2, . . . the state of the system L is x(t) ∈ X. Note, that here we associate x(t) with an abstract element. Furthermore we have a multiobjective control problem on the network (G, X, c 1 , c 2 , . . . , c p , x 0 , x f ) with p players: The dynamics of the system L is described by a directed graph of passages in the graph G = (X, E). Two states x 0 and x f are chosen in X, where x 0 is a starting point of the system L, x 0 = x(0), and x f is a final state of the system, i.e. x f is a state in which the system L must be brought. An edge e = (x, y) signifies the possibility of passages of the system L from the state x = x(t) to the state y = x(t + 1) at any point in time t = 0, 1, 2, . . . , T (x f ). (We assume that the system L reaches the final state x f at the time step T (x f )). For simplicity we assume that the graph G = (X, E) is connected. To each edge e = (x, y) ∈ E of the graph of passages p functions c 1 e (t), c 2 e (t), . . . , c p e (t) are assigned, where c i e (t) expresses the cost of system's passage from the state x = x(t) to the state y = x(t + 1) at the stage [t, t + 1] for the player i. For the stationary case the functions c i e (t) do not depend on t. According to the algorithmic principle the existence of a partition X = X 1 (t) ∪ X 2 (t) ∪ . . . ∪ X p (t), (X i (t) ∪ X j ) = ø, i = j can be proved. Here, X i (t) correspond to the set of positions of player i at time-step t. The proposed algorithm determines the optimal strategy s * which is closely related with a distinguished partition for the set X.

According to following input parameter we define the problem for the instance Multiobjective Decision Problem:

Instance Multiobjective Decision Problem

Input Parameter: n, p, T PROBLEM: Determine a stationary Pareto strategy.

Then we can prove that Theorem: Our constructive algorithm determines for the instance Multiobjective Decision Problem Pareto stationary strategies of the players for every given starting position x and final position x f . The running-time of the algorithm is O(n 3 T p).

Conclusion

Games which are defined on networks are very interesting from a practical and theoretical point of view. We present a decision problem in the context of emissions trading. A special structure is exploited to obtain a polynomial algorithm. First numerical results will be discussed.