On Shortest Random Walks under Adversarial Uncertainty
Vladimir V. Marbukh
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 of the 40th Allerton Conference on Communications, Control, & Computing
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 December 2, 2023)