Graphon Design for Human-Machine Coordination under Bounded Rationality: Optimality of Stochastic Block Models
Computer Science and Game Theory
Summary
The authors study how to help different kinds of agents, like humans and machines, work better together in a game where cooperation is beneficial. They consider agents that don't always make perfect decisions and can make mistakes, making coordination tricky. To solve this, the authors design the connections between agents in a way that improves overall teamwork, using a mathematical approach called graphons to simplify the problem. They develop an algorithm to find good network structures and show how to create actual networks from these solutions without heavy computational costs.
Authors
Zhewei Wang, Vu Anh Phi, Marcos M. Vasconcelos
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.