Information Technology Reference
In-Depth Information
∑
(3)
E
Q
[
U
(
x
θ
)]
=
U
(
u
,
θ
)
q
(
θ
)
.
θ
Formula (2) determines the best network response to a given distribution
Q
of the
state of environment. The problem, however, is that distribution
Q
may not be fixed
or known to the network. In this paper we are interested in a case of external condi-
tions
controlled by an adversary or adversaries. In this case distribution
Q
is not fixed since adversarial selection of the distribution
Q
may be affected by se-
lection of the control action
x
. Insufficiency of the Bayesian approach (2)-(3) in
adversarial situations follows from well-known benefits of randomized strategies in
adversarial situations. However, Bayesian approach (2)-(3) results in is either deter-
ministic strategy or strategy, which is indifferent among several actions.
To develop a game theoretic model for making decisions under adversarial uncer-
tainty we need to quantify the network loss in performance resulted from non-optimal
selection of the control action
u
due to the uncertain environment
θ
∈
Θ
θ
. Following [3]
we will quantify this loss by the following regret or loss function:
(4)
L
(
x
θ
)
=
max
U
(
x
'
θ
)
−
U
(
x
θ
)
.
x
'
∈
X
Note that there is a certain degree of freedom in selection of the loss function
)
uL
[4]. This selection reflects the desired balance between different risk fac-
tors. Using loss function (4) in networking context has been proposed in [5]-[6].
(
θ
3
Guarding Against Adversarial Uncertainty
Multiple adversaries can be modeled as players participating in a non-cooperative
game, where different players are not capable of coordinating their strategies [7]. A
formal model of
K
adversaries assumes that parameter
θ
∈
Θ
is a vector with
K
θ =
(
1
θ
,..,
θ
)
θ
∈
Θ
component:
, where component
characterizes strategy of
K
k
k
K
adversary
k
, i.e.,
Θ
=
⊗
Θ
. Adversary
k
selects strategy
θ
∈
Θ
with prob-
k
k
k
k
=1
q
(
k
θ
)
ability
, and selections by all adversaries are jointly statistically independent:
k
K
(5)
∏
=
q
(
θ
)
=
q
(
θ
)
.
k
k
k
1
x
∈
X
p
(
x
)
Assuming that the network selects control action
with probability
, the
average loss is