Randomization to Balance Performance under Nominal and Compromised Communication

Abstract

It is well-known that under nominal communication, where agents are able to share information with one another, game-theoretic methods provide system-level performance guarantees in multiagent cyber-physical human systems such as distributed resource allocation. However, approaches that depend on communication are frequently not robust when communication is compromised. While randomized decision-making can prevent arbitrarily poor outcomes under compromised communication, these performance guarantees often do not improve when communication abilities are restored. Thus, it remains unclear whether a single approach can perform well under nominal communication and remain robust under compromised communication. In this paper, we study whether a system operator can inform agents about how much they should randomize their choice when selecting actions in order to balance performance across both settings. We show that for any scenario (e.g., a multiagent resource allocation instance), there exists a level of randomization where nominal efficiency is near-optimal while compromised efficiency is strictly positive. We then show that this guarantee weakens as agents must choose between increasingly many resources. These results provide an initial step toward understanding randomization as a tool for robust performance across communication settings.