Information Technology Reference
In-Depth Information
developing adaptive systems and protocols capable of responding to specific threats
and moving along frontier describing the optimal trade-offs among various conflict-
ing requirements is an ambitious and probably distant goal. The difficulty of this
problem is especially pronounced in a case of distributed, large-scale systems. The
Internet represents the ultimate example of such systems.
The purpose of this paper is discussing possibility of using game theoretic models
for design and optimization of survivable and secure systems and protocols. Game
theory provides a natural framework for dealing with adversarial situations. In appli-
cations, adversaries differ in terms of their resources, access, risk tolerance, and ob-
jectives. Different types of adversaries may be hackers, malicious insiders, industrial
competitors, terrorists, and national intelligence organizations [2]. According to the
game theoretic methodology resources and access are formalized in terms of the set
of feasible strategies for each player, while risk tolerance and objectives are formal-
ized in terms of the player utility function. Each player attempts to maximize his
utility function by selecting a feasible strategy. The paper is organized as follows.
Section 2 describes quantifies regrets, i.e., loss in performance due to uncertainty.
Section 3 describes a game theoretic framework, which draws on complexity theory
of algorithms and complexity theory.
2
Regrets Due to Uncertainty
We assume that the network utility, e.g., the revenue generated by the network, is
quantified by some known function
U
(
x
θ
)
x
∈
X
of the network control action
θ
∈
Θ
. For simplicity we further assume that both sets
X
and
and environment
Θ
are finite. Vector
x
may describe pricing, resource allocation, admission control,
routing, scheduling, etc., and vector
θ
may characterize topology, available resource,
traffic sources, etc. We consider a problem of selecting the network control action
x
under incomplete information on the state of environment
θ
. If the state of envi-
*
θ
x
=
x
(
θ
)
ronment
is known, the optimal control action
maximizes the network
utility:
*
(1)
x
(
θ
)
=
arg
max
U
(
x
θ
)
.
x
∈
X
Formula (1) determines the best network response to a given state of environment
θ
.
θ
∈
Θ
A situation of unknown external conditions
can be modeled by assuming
θ
Q
=
(
q
(
θ
))
that
. Baye-
sian framework [3] assumes that distribution
Q
is known and suggests selection of
the control action
is a random variable with some probability distribution
*
x
=
x
by maximizing the average network utility:
*
(2)
x
=
arg
max
E
[
U
(
x
θ
)]
,
Q
x
∈
X
where
