Schulz M. Control Theory in Physics and Other Fields of Science: Concepts, Tools, and Applications

Подождите немного. Документ загружается.

9.2 Optimal Control and Decision Theory 267

and the controller. Thus, the quantum system may have diﬀerent outcomes

for diﬀerent states of the controller.

The last ingredient we need for a control is the formulation of the control

aim. This is again deﬁned by performance or costs. We suppose that the cost

depends on which actions were chosen by both the controller and the system.

Thus we have a performance function J(u, X) with

J : U × S(u) → R (9.1)

Since we have discrete sets, the performance is often represented by a matrix.

For example, suppose that U and S each contains three actions. This results in

nine possible outcomes, which can be speciﬁed by the following cost matrix:









(9.2)

The controller action, u, selects a row and the system action, X, selects a

column of the cost matrix. The resulting cost is given by the corresponding

matrix element.

From this point of view, the control problem can be interpreted as a game

of the controller against the system. Therefore, it seems reasonable to solve the

optimal control problem by minimizing the performance in the framework of

the game theory. From this point of view, we suggest that the game theoretical

control concept is slightly diﬀerent from the ideas presented in the previous

chapters. Obviously, the controller does not modify the system dynamics as

was the case up to now. Rather, the controller cooperates with the system in

a special manner. In fact, the controller chooses its decisions in such a manner

that these together with the more or less open dynamics of the system yield

the expected control aim.

9.2 Optimal Control and Decision Theory

9.2.1 Nondeterministic and Probabilistic Regime

What is the best decision for the controller in its game against the system?

There are two general possibilities: either the controller knows the probability

with which the system answers its action or it does not. The ﬁrst case deﬁnes

the probabilistic regime while the second case is the complete nondeterminis-

tic regime [11]. The latter case occurs especially if only few or no observations

about the system actions are available so that we cannot estimate the proba-

bility distribution of the system outcomes.

Under the non-deterministic regime, there is no additional information

other than the knowledge of the actions and the cost matrix. The only rea-

sonable approach for the controller is to make a decision by assuming the worst

268 9 Game Theory

case. This pessimistic position is often humorously referred to as Murphy’s

law

[12]. Hence, the optimal decision of the controller is given by

∗

= arg min

u∈U



max

X∈S(u)

J(u, X)



(9.3)

The optimal action u

∗

may be interpreted as the lowest-cost choice under a

worst-case assumption.

The probabilistic regime is applicable if the controller has gathered enough

data to reliably estimate the conditional probability P (X | u) of a system

action X under the condition that the controller has taken the action u. This

formulation implies that we consider a stationary system. We use the expected

case assumption and conclude

∗

= arg min

u∈U



J(u, X)





(9.4)

with the conditional average

J(u, X)





X∈S(u)

J(u, X)P (X | u) (9.5)

For an illustration, let us consider a 3 × 3 cost matrix











1 −15

40−2

20−1





123

01 2

(9.6)

The worst-case analysis requires

max

X∈S

J(1,X) = 5 max

X∈S

J(2,X) = 4 max

X∈S

J(3,X) = 2 (9.7)

and therefore u

∗

= 3. On the other hand, the probabilistic regime requires the

knowledge of probabilities. Let us assume that the actions of the system and

the controller are independent of each other. Thus we have P (X | u)=P (X).

With the special choice P (X =1)=0.1, P (X =2)=0.6, and P (X =3)=

0.3, we obtain

J(1,X)



u=1

=1.0 J(2,X)



u=2

= −0.2 J(3,X)



u=3

= −0.1 (9.8)

so that u

∗

= 2. The best decision in case of the probabilistic regime depends

on the probability distribution. For instance, in case of P (X =1)=P (X =

2) = P (X =3)=1/3, our example yields u

∗

=3.

If anything can go wrong, it will.

9.2 Optimal Control and Decision Theory 269

9.2.2 Strategies

Suppose the controller has the possibility to receive information characterizing

the current state of the system immediately before opening a channel. These

observations may allow the controller to improve its decision with respect to

minimization of the costs.

For convenience, we suppose that the set O of possible observations Y is

ﬁnite. The set O(X) ⊆ O indicates the possible observations Y ∈ O(X) under

the consideration that the subsequent system action is X. Furthermore, in

the case of the probabilistic regime the conditional probabilities P (Y | X)

are available. The likelihood P (Y | X) suggests the observation Y before the

system action X occurs.

A strategy is a function θ connecting a given observation Y of the system

with the controller decision, i.e., u = θ(Y ). In other words, for each observation

Y the strategy θ provides an action to the controller in order to minimize the

costs.

Our aim is now to ﬁnd the optimal strategy. In the case of the nondeter-

ministic model, the sets O(X) must be used to determine the allowed system

actions. That means, we have to determine the sets

S(Y )={X ∈ S | Y ∈ O(X)} (9.9)

Then, the optimal strategy is

∗

(Y ) = arg min

u∈U



max

X∈S(Y )

J(u, X)



(9.10)

Obviously, the advantage of having the observation Y is that the set of avail-

able system states is reduced to S(Y ) ⊆ S. The probabilistic regime requires

the considerations of the above mentioned conditional probabilities. For the

sake of simplicity, we restrict ourselves to the case that the system action

depend does not on the controller action

, i.e., P (X | u)=P (X). Using the

Bayes theorem (8.18), we get

P (X | Y )=

P (Y | X)P (X)



∈S

P (Y | X



)P (X



)

(9.11)

Note that P (X | Y ) is again an “a posteriori” probability in the sense of

Bayesian statistics, which represents the probability that the system takes

the action X after we have measured the observation Y . In the same context,

the P (X) are the corresponding “a priori” probabilities. The optimal strategy

is then

∗

(Y ) = arg min

u∈U



J(u, X)





(9.12)

Otherwise, we need further information about the probability P (X | u, Y )thata

system takes the state X after the observation Y and the subsequent opening of

channel u by the controller.

270 9 Game Theory

with the conditional Bayes’ risk

J(u, X)





X∈S

J(u, X)P (X | Y ) (9.13)

Using (9.11), we may also write

J(u, X)



X∈S

J(u, X)P (Y | X)P (X)



∈S

P (Y | X



)P (X



)

(9.14)

and therefore

∗

(Y ) = arg min

u∈U





X∈S

J(u, X)P (Y | X)P (X)



∈S

P (Y | X



)P (X



)





= arg min

u∈U



X∈S

J(u, X)P (Y | X)P (X)

(9.15)

The problem can be extended to the case of multiple observations before the

controller opens a certain channel and the system answers with its action. In

this case the controller measures L observations, Y

,...,Y

; each is assumed

to belong to an observation space O

(i =1,...,L). The strategies now depend

on all observations

θ : O

× O

× ...×O

→ U (9.16)

The nondeterministic regime requires the selection of all admissible X which

belong to the observation set. This requires the knowledge of the subsets

S(Y

)={X ∈ S | Y

∈ O

(X)} (9.17)

which may be used to construct

S(Y

,...,Y

)=S(Y

) ∩ S(Y

) ∩···∩S(Y

) (9.18)

Thus, the optimal strategy for the nondeterministic regime is given by

∗

,...,Y

) = arg min

u∈U



max

X∈S(Y

,...,Y

)

J(u, X)



(9.19)

The probabilistic regime can be extended in the same way. For simplicity,

we assume that the observations are conditionally independent events. That

means we have

P (Y

,...,Y

| X)=



k=1

P (Y

| X) (9.20)

P (X | Y

, ..., Y

k=1

P (Y

| X)P (X)



∈S

k=1

P (Y

| X



)P (X



)

(9.21)

9.3 Zero-Sum Games 271

Following the same steps which led to (9.15), we now arrive at

∗

(Y ) = arg min

u∈U



X∈S

J(u, X)



k=1

P (Y

| X)P (X)

(9.22)

We remark that the conditional independence between the observations is an

additional assumption which we have used for a better illustration. However,

this simpliﬁcation is often used in practice, since the estimation of the com-

plete conditional probabilities P (Y

,...,Y

| X) requires a large record of

observations which is not always available.

Finally, we stress again on the speciﬁc feature of a control on the basis

of game theoretical concepts. In contrast to the concepts discussed above,

the controller does not force the system to a special (optimal) dynamics. The

controller chooses its actions in such a way that these decisions together with

the free, but nearly unknown dynamics of the system lead to the expected

control aim.

9.3 Zero-Sum Games

9.3.1 Two-Player Games

Many-player games are not often used for the control of a more or less passive

system. But these games are often used for modeling the intrinsic, partially

competing control mechanisms of systems with a very high degree of complex-

ity. In this sense, what follows may be understood as a part of control theory.

We now focus on two-player games. For the case of many players we refer to

the special literature [13, 14, 15, 16].

Suppose there are two players making their own decisions. Each player has

a ﬁnite set of actions U

and U

. Furthermore, each player has a cost function

) with u

∈ U

(i =1, 2). A zero-sum game is then given by

)+J

) = 0 (9.23)

That means, the cost for one player is a reward for the other. Obviously,

in zero-sum games the interests of the players are completely opposed. Con-

trollers with such properties are relatively rare. Because the theory of zero-sum

game is very clear, this concept is often used also when it is partially incorrect,

just to exploit the known results.

The goal of both players is to minimize their costs under symmetric condi-

tions. That means, both players make their decisions simultaneously. Further-

more, it is assumed that the players know the cost functions

and that both

opponents follow a reasonable concept. The latter condition requires that each

player is interested to obtain the best cost whenever possible.

This implies that each player knows the intentions of the opponent.

272 9 Game Theory

9.3.2 Deterministic Strategy

In order to obtain a solution of the two-player zero-sum game, we use the

worst-case concept. From the viewpoint of player 1, the opponent is assumed

to act similar to the passive system under the nondeterministic regime. Thus,

we have

∗

= arg min

∈U



max

∈U

)



(9.24)

Because of the symmetry of the game, we obtain immediately

∗

= arg min

∈U



max

∈U

)



(9.25)

or equivalently

∗

= arg max

∈U



min

∈U

)



(9.26)

The optimal actions u

∗(1)

and u

∗(2)

are also called security strategies. The

solution of this deterministic strategy problem must not lead to a unique

solution. For instance, the cost matrix J











10−1

−21 0

102





123

01 2

(9.27)

has the solutions u

∗

=1andu

∗

= 2 while the same problem gives a unique

solution for the second player, u

∗

= 2. This uncertainty cannot be solved in

the context of a deterministic strategy. Here, we need the probabilistic concept

presented below. However, we can deﬁne the estimate of the upper value of

the game from the viewpoint of player 1. This is simply the border J

deﬁned

= max

∈U

∗

) (9.28)

while the lower value is given by

−

= min

∈U

∗

) (9.29)

In our example, we have J

=1andJ

−

= 0. Then, we have the inequalities

−

≤ J

∗

) ≤ J

(9.30)

A unique solution for both players requires J

−

= J

. In this case, the security

strategies are denoted as a saddle point of the game. A saddle point always

requires

9.3 Zero-Sum Games 273

∗

) = min

∈U



max

∈U

)



= max

∈U



min

∈U

)



(9.31)

A saddle point is sometimes interpreted as an equilibrium of the game, be-

cause both players have no interest to change their choices. We remark that

a system can have multiple saddle points. A simple example is given by the

cost matrix J

















1 0 −3 1

22 02

1 0 −1 1

1 −132







12 34

01 2

(9.32)

with four saddle points (u

∗

), namely (1, 1), (1, 4), (3, 1), and (3, 4). From

the necessary condition for each saddle point, J

= J

−

, and from (9.30)it

follows immediately that all saddle points must have the same costs.

9.3.3 Random Strategy

The main problem of the deterministic strategy was the uncertainty in the

behavior of a player if no saddle point exists. To overcome this critical point,

we now introduce stochastic rules. That means, for each game each player

chooses randomly a certain action. Under the assumption that the same game

is repeatedly played over a suﬃciently large number of trials, the costs per

game tend to their expected value. Suppose that player i (i =1, 2) has m

actions, given by u

with u

=1,...,m

. Then, the probability that the player

i chooses the action u

is p

(i)

). The normalization requires



(i)

)=1 for i =1, 2 (9.33)

The two sets of probabilities are written as two vectors

(1)

(1),..., p

(1)

)

and p

(2)

(1),..., p

(2)

)

(9.34)

Because of p

(i)

) ≥ 0 and (9.33), each vector p

(i)

lies on a (m

− 1)-

dimensional simplex of the R

; see also Chap. 10. The expected costs

for

given probability vectors p

(1)

and p

(2)

are

(1)

(2)



(1)

(2)

) (9.35)

or in a more compact form

from the view of player 1.

274 9 Game Theory

(1)

(2)

)=p

(1)

(2)

(9.36)

where J

is the cost matrix with respect to player 1. Following the above

discussed concepts, the random security strategies are obtainable from an

appropriate choice of the probability vectors p

(1)

and p

(2)

through

∗(1)

= arg min

(1)



max

(2)

(1)

(2)

)



(9.37)

and

∗(2)

= arg max

(2)



min

(1)

(2)

)



(9.38)

Furthermore, the upper value of the expected cost function is given by

= max

(2)

∗(1)

(2)

) (9.39)

while the lower value is deﬁned by

−

= min

(1)

∗(2)

) (9.40)

The most fundamental result in the zero-sum game theory, namely the equiv-

alence between upper and lower values

= J

−

= J

(9.41)

was shown by von Neumann [17, 18]. The quantity J

is the expected value of

the game. The necessary existence of a saddle point under a random strategy

demonstrates the importance of a probabilistic concept when making deci-

sions against an intelligent player. Of course, when playing the game over a

suﬃciently long time with a deterministic strategy, the opponent could learn

the strategy and would win every time. But if the player uses a random strat-

egy, the second player has no concrete idea about the next strategy used by

the ﬁrst player and vice versa.

9.4 Nonzero-Sum Games

9.4.1 Nash Equilibrium

We focus again on two-player games. But now we allow arbitrary cost functions

)andJ

) for both players, i.e., the condition (9.23) is no longer

valid. That means, both players are not always in strict competition. There

may exist situations in which both players have similar interests, i.e., there is

the possibility for both players to win. This is a general concept of redundant

control systems. Both controllers, i.e., both players, have the same or nearly

the same intention in controlling the output of a system.

Each player would like to minimize its cost. Firstly, we consider again

deterministic strategies to solve the nonzero-sum game. Because of the inde-

pendence of the two players, each applies its security strategy without making

9.4 Nonzero-Sum Games 275

reference to the cost function of the other player. Because of the assumed de-

terministic character, the strategy of the opponent may be ﬁxed. Then we say

a pair of actions u

∗

and u

∗

is a Nash equilibrium if

∗

= J

∗

) = min

∈U

∗

) (9.42)

and

∗

= J

∗

) = min

∈U

∗

) (9.43)

Obviously, a Nash equilibrium can be detected in a pair of matrices J

and

by ﬁnding a matrix position (u

) such that the corresponding element

) is the lowest among all elements in the column u

of J

and the

element J

) is the lowest among all elements in row u

of J

. Let us

illustrate this procedure by a simple example. We consider the matrices





1 −1 0 2

30 14

21−2 3









−1 −1 12

2 0 21

421 2





(9.44)

It is simple to check that the Nash equilibria exist for the positions (1, 1),

(1, 2), and (3, 3). It is a typical feature that a nonzero game has multiple

Nash equilibria. From a ﬁrst glance, the Nash equilibrium at (1, 2) seems to

be the best choice because it yields negative costs for both players. However,

the general decision as to which Nash equilibrium is the optimal choice is by

no means a trivial procedure.

The simplest case occurs if both players do not have the same rights.

Then, one player, say player 1, is the master player while the second one is

the slave. Under this consideration a lexicographic order of the Nash equilibria

deﬁnes the optimal solution. That means, ﬁrstly we search for the pair (J

∗

)

which has the lowest value of J

∗

. If two or more pairs satisfy this condition,

we consider that pair of these candidates which has also the lowest value

of J

∗

. In our example such a concept would lead to the decision that the

nash equilibrium at (3, 3) is the optimal choice. That should be the typical

situation for possible intrinsic control mechanisms of complex systems. The

ﬁrst decision comes from the main controller, and only if it cannot give a

unique answer, does the second controller decide the common strategy.

The situation becomes much more complicated if both players have equal

rights. Then the deﬁnition of the best solution implies a suitable ordering

of the Nash equilibria. It is often only a partial ordering procedure because

some pairs (J

∗

) are incomparable

. In the last case, the player must com-

municate or collaborate in order to avoid higher costs. If the players do not

ﬁnd an agreement, the possibility of higher costs is often unavoidable. For

example, this is the case if both players favor actions which are related to

For example the pairs (0, 1) and (1, 0) cannot be ordered under the assumption

of players with equal rights.

276 9 Game Theory

diﬀerent Nash equilibria. Two well-known standard examples of such incom-

plete ordered Nash equilibria are the “Battle of the Sexes” and the “Prisoner’s

Dilemma” [19]. Finally, we remark that a nonzero-sum game also can have no

Nash equilibrium.

9.4.2 Random Nash Equilibria

Let us now analyze nonzero-sum games with random strategies. Similar to

Sect. 9.3.3, we introduce the probability vectors (9.34). Then we deﬁne the

expected costs

(1)

(2)



(1)

(2)

) (9.45)

(i =1, 2). Then a pair of probability vectors p

∗(1)

and p

∗(2)

is said to be a

mixed Nash equilibrium if

∗(1)

∗(2)

) = min

(1)

∗(2)

) (9.46)

and

∗(1)

∗(2)

) = min

(2)

∗(1)

(2)

) (9.47)

It was shown by Nash that every nonzero-sum game has a mixed Nash equi-

librium [2]. Unfortunately, it cannot be guaranteed that multiple mixed Nash

equilibria appear. That means there is no reliable way to avoid higher costs

at least for one player unless the players collaborate. The determination of a

mixed Nash equilibrium is a bilinear problem [3]. This requires usually nu-

merical investigations using nonlinear programming concepts [4, 5].

References

1. A. Einstein, B. Podolski, N. Rosen: Phys. Rev. 47, 777 (1935) 265

2. J. Nash: Ann. Math. 54, 286 (1951) 276

3. T. Basar, G.J. Olsder: Dynamic Noncooperative Game Theory, 2nd edn (Acad-

emic, London, 1995) 276

4. D.G. Luenberger: Introduction to Linear and Nonlinear Programming (Wiley,

New York, 1973) 276

5. S.G. Nash, A. Sofer: Linear and Nonlinear Programming (McGraw-Hill, New

York, 1996) 276

6. D. Bohm: Quantum Theory (Prentice-Hall, New York, 1951) 265

7. J.S. Bell: Physics 1, 195 (1965) 265

8. J.F. Clauser, A. Shimony: Rep. Prog. Phys. 41, 1881 (1978) 265

9. B. d’Espagnat: Scientiﬁc Am. 241, 128 (1979) 265

10. H. Kleinpoppen: Phys. Rev. Lett. 54, 1790 (1985) 265

11. M.A. Erdmann: on probabilistic strategies for robot tasks. PhD thesis, Massa-

chusetts Institute of Technology, Cambridge, MA (1989) 267