On Shortest Random Walks under Adversarial Uncertainty

Published

May 1, 2003

Author(s)

Vladimir V. Marbukh

Abstract

Finding shortest feasible paths in a weighted graph has numerous applications including admission and routing in communication networks. This paper discusses a game theoretic framework intended to incorporate a concept of path stability into the process of shortest path selection. Route stability is an important issue in a wire-line and especially in wireless network due to node mobility as well as limited node reliability and power supply. The framework assumes that the link weights are selected within certain ¿confidence intervals¿ by an adversary or set of adversaries. The width of the confidence interval for the path weight represents the path stability. One of the immediate benefits of this framework is justification for randomized routing interpreted as a mixed Nash equilibrium strategy in the corresponding game. To demonstrate a wide range of possible applications of the proposed framework the paper briefly discusses possible application to robust traffic engineering.

Proceedings Title

Proceedings of the 40th Allerton Conference on Communications, Control, & Computing

Volume

40

Issue

No. 2

Conference Dates

October 1, 2002

Conference Title

(Champaign, Illinois)

Pub Type

Conferences

Download Paper

Local Download

Keywords

shortest random walks, weighted graph

Citation

Marbukh, V. (2003), On Shortest Random Walks under Adversarial Uncertainty, Proceedings of the 40th Allerton Conference on Communications, Control, & Computing, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=50726 (Accessed October 11, 2025)