Tug of Peace: Distributed Learning for Quality of Service Guarantees
Siddharth Chandak, Ilai Bistritz, Nicholas Bambos · 2023
Consider$N$players, where the action of player$n$is a number in the interval$[0,\ B_{n}]$that is interpreted as its “pull”. Each player has a reward function that depends on all actions. We define Tug-of-War (ToW) games where increasing the action of one player decreases the rewards of all others. Tug-of-War games can model networking scenarios such as transmission power control and activation in sensor networks. We propose Tug-of-Peace algorithm, a simple stochastic approximation, and prove that in Tug-of-War games, it converges to a equilibrium that satisfies a target feasible Quality of Service reward vector for the players. Moreover, with high probability it converges to the “minimal pull” equilibrium. Our algorithm uses infrequent 1-bit communication between the players, but we also propose a fully distributed modification that does not require any communication at all and achieves almost the same guarantees. We then simulate our algorithms in the power control and sensor activation scenarios.