Minimal communication achieves strong team coordination in resource games
Achieving Robust Performance using Minimal Communication in Resource Allocation Games
Computer Science and Game Theory
Summary
When teams try to share resources without fully talking to each other, their coordination can suffer. This paper looks at how much communication is really needed to keep teamwork just as good as if everyone could talk all the time. The authors created a fast way to find the smallest communication setup that still keeps team performance high. They also figured out when teams can be stable in their choices and how communication affects that. They tested their methods on example games to show it works efficiently.
What this means in practice
- •For network schedulers: Design communication structures that minimize overhead while ensuring efficient resource distribution among devices in networks with limited connectivity.
- •For emergency response coordinators: Plan minimal communication strategies that ensure robust team coordination during disasters when usual communication channels are disrupted.
Authors
Brandon Collins, Colton Hill, Philip N. Brown
Abstract
Increasingly, resource allocation games are being proposed to model team coordination in denied communication environments. Of particular interest is understanding the impact of communication denial on the quality of emergent team coordination. In this work, we consider the situation with an arbitrary communication network and use the Price of Anarchy to quantify the quality of emergent behavior. Our main result is a computationally efficient algorithm that calculates a minimal communication network that has the same performance guarantee as the full information case. Additionally, we provide efficient algorithms that compute a Nash and a strict Nash equilibrium in the full information setting. Finally to support these algorithms, we provide sufficient conditions for the existence of a strict Nash equilibrium, characterize strict Nash equilibria across all communication networks, and show that each strict Nash equilibrium in the full information case has a necessary and sufficient set of communication links that induce it. We conclude by giving an execution time experiment of the proposed algorithm and examine several example games.