Optimal Teaming for Coordination with Bounded Rationality via Convex Optimization
Zhewei Wang, Olugbenga Moses Anubi, Marcos M. Vasconcelos · 2025
Read Optimal Teaming for Coordination with Bounded Rationality via Convex Optimization by Zhewei Wang, Olugbenga Moses Anubi, Marcos M. Vasconcelos (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-04290.txt.
Introduction
Zhewei Wang, Olugbenga Moses Anubi, and Marcos Vasconcelos design the wiring diagram of a team so its members can learn to cooperate. Their agents are boundedly rational: they grope toward good joint behaviour by a standard noisy learning rule, and who is connected to whom shapes what they settle on. The design goal mixes a high chance of landing on a stable joint strategy with a low wiring cost.
Cast as a convex optimization, the problem still explodes with team size. Using the problem's symmetry, the trio proves a matching-strength network is optimal when no sparsity is demanded, cutting the search to one dial. That best dial shrinks as agents grow more rational: smarter teams need less wiring.
Catalog record
| CREATOR | Zhewei Wang, Olugbenga Moses Anubi, Marcos M. Vasconcelos |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-04290
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimal Teaming for Coordination with Bounded Rationality via Convex Optimization Zhewei Wang, Olugbenga Moses Anubi, Marcos M. Vasconcelos Abstract Teaming is the process of establishing connections among agents within a system to enable collaboration toward achieving a collective goal. This paper examines teaming in the context of a network of agents learning to coordinate with bounded rationality. In our framework, the team structure is represented via a weighted graph, and the agents use log-linear learning. We formulate the design of the graph’s weight matrix as a convex optimization problem whose objective is to maximize the probability of learning a Nash equilibrium while minimizing a connectivity cost. Despite its convexity, solving this optimization problem is computationally challenging, as the objective function involves the summation over the action profile space, which grows exponentially with the number of agents. Leveraging the underlying symmetry and convexity properties of the problem, when there are no sparsity constraints, we prove that there exists an optimal solution corresponding to a uniformly weighted graph, simplifying to a one-dimensional convex optimization problem. Additionally, we show that the optimal weight decreases monotonically with the agent’s rationality, implying that when the agents become more rational the optimal team requires less connectivity. I Introduction In strategic decision-making over a social network, every agent must take into account the behavior of its neighbors when choosing an action. Agents in the system are often characterized by a certain level of rationality, which can be modeled on how much weight (if any) is assigned to the actions taken by its neighbors. In one extreme, a completely irrational agent makes decisions by randomly picking an action over a finite discrete set with a uniform distribution. On the opposite extreme, a fully rational agent optimizes its local objective taking into account the actions played by its neighbors, in other words, the agent plays a best-response . Somewhere in between these extremes, an agent with bounded rationality will make suboptimal decisions with non-negligible probability, resulting in loss of performance. The focus of this paper is on the design of undirected weighted networks when the agents are coordinating binary actions under bounded rationality using log-linear learning (LLL). The objective of the system designer consists of two terms: the first is the stationary probability that the agents will learn to coordinate at the game’s Nash equilibrium and the second is a cost on the overall connectivity of the graph, represented here by the total sum of the graph weights. We show that the optimal design of weights for any specified connectivity/sparsity pattern is a convex optimization problem. Then, we establish that if the sparsity pattern is complete, there exists an optimal graph with uniform weight distribution over the edges. The optimal weight is a non-trivial function of the agents’ rationality parameter, the number of agents in the graph, and the connectivity cost. We analytically show that as the agents become more rational, the optimal weights decrease and vice-versa. To the best of our knowledge this is the first time such results appear in the literature. We also report numerical results that show that when incomplete sparsity pattern constraints are introduced, the optimal solutions are asymmetric in general. Fig. 1: Framework for learning to coordinate over a network with bounded rationality. The teaming problem is to choose the weights that maximize the probability of learning to coordinate at a Nash equilibrium. I-A Related Literature The interplay between network structure and agent behavior in coordination games has been extensively studied. Foundational contributions such as [ 1 , 2 , and references therein] introduced general network game models. The seminal work reported in [ 3 ] established the first analytical results in the Markovian dynamics and stationary distributions of LLL. Additional convergence properties of LLL, particularly under asynchronous updates, were further analyzed in [ 4 ] . Recent studies, such as [ 5 , 6 ] , applied LLL to network coordination games in an adversarial setting. One of the important questions in the field of network games is how the network topology influences coordination efficiency, and the convergence rate of the learning process. The studies in [ 7 , 8 ] shows how structural properties affect the speed and likelihood of converging to the right Nash equilibrium. However, the afore mentioned results rely on the agents’ rationality to grow unbounded. We are interested in the case where the agents operate under bounded rationality. Due to cognitive, informational and computational limitations, the concept of bounded rationality has gained increasing attention in recent literature [ 9 , 10 , 11 , 12 ] . Learning for coordination in the presence incomplete information have been considered in [ 13 , 14 , 15 ] . Adaptive learning algorithms under bounded rationality have also been explored in [ 16 , 17 ] , where the agents’ rationality strongly influences their ability to coordinate, adaptation speed, and long-term performance. Recent work in [ 18 ] captures bounded rationality by assuming that the agents only have local information about constraints in a network game. Our prior work [ 19 , 20 ] showed that increased connectivity improves coordination under bounded rationality in LLL, both in regular and irregular graph structures. Motivated by [ 21 ] , we considered the extension of our prior work to the design and analysis of weighted graphs for learning to coordinate under bounded rationality. Our results reported herein use convex optimization techniques in a different context than the now classic results from [ 22 ] , and provide many new research directions in the design of network systems of strategic agents. I-B Notation Let N denote the number of agents in the network. Each agent selects an action a_{i}\in\{0,1\} , and the joint action profile is denoted by a=[a_{1},\ldots,a_{N}]^{T}\in\{0,1\}^{N} . The communication topology is modeled as an undirected graph with symmetric weight matrix \mathbf{W}=[w_{ij}]\in\mathbb{R}^{N\times N} , where w_{ij}\in[0,1] represents the weight of the edge between agents i and j , and w_{ij}=0 if (i,j)\notin\mathcal{E} . The scalar \theta\in\mathbb{R} is a parameter representing task difficulty. The parameter \beta\geq 0 represents the agents’ rationality level. The function \Phi_{\mathbf{W}}(a) denotes the potential function evaluated at action profile a , and \mu_{\mathbf{W}}(a\mid\beta) is the stationary distribution over joint actions under log-linear learning with weight matrix W and rationality \beta . The regularization parameter \rho>0 penalizes total connectivity in the graph. The vectors \mathbb{1},\mathbb{0}\in\mathbb{R}^{N} denote the all-ones and the all-zeroes column vectors. The identity matrix is denoted by \mathbf{I} . I-C Organization The remainder of this paper is organized as follows. Section II introduces the networked coordination game setup, defines the potential function, and formulates the weight optimization problem. In Section III, we analyze the structure of the optimal weight matrix. In Section IV we characterize the dependence of the optimal graph weight with the rationality parameter. Section V extends the formulation to graphs with arbitrary sparsity patterns and discusses implications for network design in the face of bounded rationality. In Section VI, we conclude the paper. II Weighted Network Coordination Games II-A Definition and preliminary properties Consider a team with N agents connected by a weighted graph \mathcal{G}([N],\mathcal{E}) , i.e., each link in the graph is is associated with a weight w_{ij}\in[0,1] . If (i,j)\notin\mathcal{E} , then