Graphon Design for Human-Machine Coordination under Bounded Rationality: Optimality of Stochastic Block Models

Abstract

Coordination is a desirable feature in multi-agent systems, ranging from robotic swarms to socioeconomic networks. This paper is concerned with promoting coordination among heterogeneous agents, e.g., machines and humans, interacting in a stag-hunt game. In our model the agents exhibit bounded rationality at different levels, which leads to uncertainty and a propensity for errors during learning and decision-making processes. This paper addresses the problem of designing a network topology that maximizes a global metric of coordination under such constraints. While optimizing over the discrete space of finite graphs is generally computationally intractable, we employ a mean-field approach to lift the problem into the space of graphons. Within this framework, we analyze agents following a logit learning dynamics. Using calculus of variations, we show that for systems with a bimodal rationality profile, it suffices to search for optimal graphons in the ensemble of stochastic block models. We then propose a water-filling algorithm to find a locally optimal graphon. Finite graphs can then be sampled from the optimized graphon, bypassing the inherent combinatorial complexities of discrete graph optimization.