Information Technology Reference
In-Depth Information
(6)
K
∑∑
∏
L
(
P
Q
)
=
L
(
x
θ
)
p
(
x
)
q
(
θ
)
.
k
k
x
∈∈
X
θ
k
=
1
Generally mixed, Nash equilibrium strategy in this game determines optimal ran-
domized strategy for the network
opt
opt
P
=
(
p
(
x
))
, which guards against the worst-
opt
opt
Q
=
(
q
(
θ
))
case scenario mixed strategy for the adversaries
.
Optimization of distributed adaptive protocols presents additional challenges due
to the stability concerns. Distributed protocols are often formalized as a non-
cooperative game, where each agents, representing a local protocol component, at-
tempts to maximize its own utility independently of other agents. The individual
utilities are defined through network resource pricing so that (hopefully unique) Nash
equilibrium in the game optimizes the overall network performance [8]. In practice,
each agent maximizes its individual utility by learning evolution, i.e., by making
decisions based on the observed history of its own decisions and obtained utility [7].
If this dynamic process converges, the resulting equilibrium is the Nash equilibrium
in the corresponding game [7] and thus optimizes the overall steady-state network
performance. The problem, however, is that learning algorithms, based on the best
responses to the empirical average utilities, do not converge if a typical case when the
corresponding game has mixed, i.e., involving randomization, Nash equilibrium [7].
This instability may result in overloading the network with the network state updates
and cause undesirable transient effects.
References
1. Neumann, P.G.: Practical Architectures for Survivable Systems and Networks. Technical
report, SRI International (2000): http://www.csl.sri.com/neumann/survivability.pdf
2. Salter, C., Saydjari, O.S., Schneier, B., Walner, J.: Towards a Secure System Engineering
Methodology. Technical Report.: http://www.counterpane.com/secure-methodology.pdf
3. Blackwell, D., Girschick, M.: Theory of Games and Statistical Decisions.: Wiley, New York
(1954)
4. Marbukh, V.: Minimum Regret Approach to Network Management under Uncertainty with
Applications to Connection Admission Control and Routing.: First International Conference
on Networking (ICN2001), Colmar, France, 309-318
5. Koutsoupias, E., Papadimitriou, C.H.: Beyond competitive analysis. In: Foundations of
Computer Science, 1994. (Updated version available at http:/www.cs.berkeley.edu/christos/)
6. Marbukh, V.: Network Management under Incomplete Information on the Operational
Environment. In: International Symposium on Information Theory and Its Applications
(ISITA2000), Honolulu, Hawaii, 637-640
7. Fudenberg, D., Tirole, J.: Game Theory.: MIT Press, Cambridge, Massachusetts (2000)
8. Marbukh, V.: Optimization of Adaptive Distributed Protocols as a Game.: ACM
SIGMETRICS 2003: First Workshop on Algorithms and Architectures for Self-Managing
Systems, San Diego, CA, USA (2003)
