PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Zhewei Wang, Vu Anh Phi, Marcos M. Vasconcelos

arXiv:2608.27851v1eess.SYcs.GT

TL;DR

The paper addresses graph design for coordination among boundedly rational human and machine agents, where discrete optimization is computationally difficult. It uses graphons and logit learning to analyze the problem, showing that bimodal rationality permits stochastic block model search and a water-filling algorithm for local optimization.

  • Problem

    The paper seeks network topologies that promote coordination in heterogeneous human-machine networks despite bounded rationality, while discrete graph optimization is computationally intractable.

  • Method

    The paper relaxes network design to graphons, models behavior with heterogeneous logit learning, and uses variational optimization for bimodal rationality profiles.

  • Results

    For bimodal rationality, an optimal graphon exists within the stochastic block model ensemble, and a greedy water-filling algorithm allocates edge densities across blocks.

  • Takeaways & Limitations

    Finite graphs can be sampled from optimized graphons, providing a route around the combinatorial complexity of discrete graph optimization.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper studies coordination in heterogeneous human-machine networks using the Stag Hunt game and seeks graphon-based network designs that address bounded rationality and discrete optimization difficulties.

  • The Stag Hunt models coordination through risky, highly rewarding stag hunting versus a safe, low-rewarding hare alternative.
  • Heterogeneous human-machine networks require accounting for different rationality levels, while rigorous frameworks for allocating links to promote coordination remain limited.
  • Discrete graph optimization is difficult because the graph space grows combinatorially and heterogeneous rationality lacks a closed-form stationary distribution.
  • The graphon mean-field relaxation represents large-scale networks continuously and avoids both discrete combinatorial complexity and reliance on a closed-form stationary distribution.
  • For bimodal rationality profiles, optimal graphons can be sought within the stochastic block model ensemble, and a water-filling algorithm computes a locally optimal profile.
  • The model represents agents on a unit-mass population with humans and machines, using a symmetric measurable graphon W and fixed edge density ρ.

B. Potential Game Structure

The graphon coordination game is a potential game whose global potential maximizers are the two perfectly aligned action profiles, with the preferred profile determined by the difficulty parameter.

  • The graphon coordination game has a potential function whose Gâteaux derivative equals the payoff difference between actions 1 and 0.
  • The perfectly aligned profiles are the only global maximizers of the potential when the graphon has positive aggregate connectivity.
  • When θ < 1/2, all agents choosing action 1 uniquely maximizes potential; when θ > 1/2, all agents choosing action 0 does; at θ = 1/2, both maximize.

III. LOGIT LEARNING DYNAMICS

The paper models boundedly rational human-machine behavior with heterogeneous logit learning dynamics and optimizes graphons to increase asymptotic adoption of the socially desirable equilibrium.

  • Agents update continuously through a logit learning dynamic, choosing actions probabilistically according to expected-utility incentives and type-dependent rationality.
  • The rationality parameter β(x) interpolates between uniform random choice as β(x) approaches 0 and perfect best response as β(x) approaches infinity.
  • The model assumes a bimodal rationality profile with human rationality βH lower than machine rationality βM.
  • Because the game is potential-based, the logit dynamics converge asymptotically to a steady-state profile a∞(x).
  • For θ < 1/2, the performance metric is the asymptotic fraction of agents adopting the socially desirable all-1 equilibrium.
  • The graphon optimization problem maximizes this adoption objective subject to the nonlinear equality constraint imposed by the steady-state equation.

B. Uniqueness of the steady state

The paper imposes a contraction condition on heterogeneous logit dynamics to ensure a unique steady state for every admissible graphon, making the optimization problem well posed.

  • Potential-game structure guarantees asymptotic convergence of the logit dynamics to a steady-state profile.
  • The degree D(x) is the integral of W(x,y) over neighboring agents and enters the contraction bound.
  • Under Assumption 1, the update operator is a contraction on the bounded profile space.The contraction factor satisfies κ < 1.
  • The Banach fixed-point theorem therefore guarantees a unique steady state a∞ for each graphon.
  • If β(x) < 4 for all agents, the contraction condition holds for every graphon in Wρ.

IV. FIRST-ORDER OPTIMALITY CONDITIONS

Using calculus of variations and a Lagrangian, the paper derives first-order and KKT conditions characterizing locally optimal graphons under steady-state and density constraints.

  • The adjoint satisfies μ⋆(x) > 0, and local optimality requires a nonpositive directional derivative toward every feasible graphon.
  • KKT conditions assign W⋆(x,y)=1 when G⋆(x,y)>2λ, zero when G⋆(x,y)<2λ, and any value in [0,1] at equality.
  • The Lagrangian enforces both the steady-state fixed-point equation and the graphon density constraint.
  • Stationarity with respect to the agent profile yields an adjoint integral equation for μ⋆.
  • At fixed state, adjoint, and multiplier, the Lagrangian is linear in W.

V. STRUCTURE OF THE OPTIMAL GRAPHON FOR BIMODAL RATIONALITY

For a bimodal rationality profile, exchangeability within human and machine groups allows symmetrization without lowering the objective, yielding an optimal graphon with stochastic block structure.

  • The bimodal profile partitions agents into two exchangeable groups: humans and machines.
  • Averaging over within-group measure-preserving permutations produces an SBM graphon with objective value at least that of a local maximizer.
  • The averaged graphon has steady-state adoption and adjoint profiles constant within each agent type.
  • The optimality function takes three blockwise values, corresponding to human-human, human-machine, and machine-machine interactions.
  • The blockwise KKT condition assigns a constant edge probability to each block, so every local maximizer is an SBM.

VI. GREEDY EDGE DENSITY ALLOCATION

Once optimization is restricted to SBMs, the connectivity budget is allocated across three agent-type blocks by a water-filling rule based on their marginal values.

  • The SBM optimization allocates the connectivity budget across machine-machine, human-machine, and human-human blocks.
  • A block is fully active when Gij>2λ, partially active when Gij=2λ, and inactive when Gij<2λ.
  • As density ρ increases, blocks activate in decreasing order of their values Gij.
  • The algorithm ranks the three blocks, identifies the marginal block, and sets λ from its value.
  • Because the objective is nonconvex, the water-filling allocation satisfies KKT conditions and yields a locally optimal SBM solution.

VII. NUMERICAL RESULTS

Numerical experiments use a bimodal human-machine population with machines that respond more sharply to network externalities than humans, under parameters ensuring a unique equilibrium.

  • The experiments set βM = 3.99 and βH = 2, so machines have sharper responses to network externalities than humans.The equal population masses are ℓ = 1 − ℓ = 0.5, with θ = 0.3.

A. Allocation and adoption across density budgets

The water-filling allocation fills machine-machine, human-machine, and finally human-human blocks as density increases, with transitions at ρ = 0.25 and ρ = 0.75. Machine adoption rises above the irrational baseline as connectivity is allocated.

  • Evaluation across budgets: The allocation study evaluates optimal block weights, steady-state risky-action adoption, and aggregate adoption J1 across density budgets ρ ∈ {0.1, 0.2, ..., 0.9}.The tested ordering remains self-consistent at every density budget, yielding a local optimum.
  • Water-filling allocation: The optimal block-weight curves undergo phase transitions at ρ = 0.25 and ρ = 0.75.Figure 2 presents the optimal weights wMM, wHM, and wHH as functions of ρ.
  • Water-filling allocation: The MM block receives the entire budget until ρ = 0.25, HM fills from ρ = 0.25 to ρ = 0.75, and HH receives the remainder thereafter.These thresholds mark shifts in the marginal block.
  • Adoption outcomes: Machine adoption increases to aM = 0.873 by ρ = 0.9 from a baseline of 0.51, while human adoption begins increasing when the HM block fills at ρ = 0.25.Human adoption later reaches aH = 0.692.
  • Adoption outcomes: The baseline adoption level is 0.5, corresponding to completely irrational behavior modeled as a fair-coin decision.Figure 3 uses this value as its reference line.

B. Prioritizing human connectivity rather than machines

Prioritizing machine connectivity outperforms uniform and human-prioritizing allocations under the same density budget. The reported ordering is self-consistent across tested budgets and rationality parameters, supporting machine-machine links as the highest-return priority in this setting.

  • Allocation comparison: The human-prioritizing allocation fills blocks in the order GHH ≥ GHM ≥ GMM, whereas the optimal comparison uses machine-prioritizing connectivity.Both alternatives use the same density budget ρ.
  • Allocation comparison: The machine-prioritizing allocation strictly dominates uniform and human-prioritizing alternatives for every ρ ∈ (0, 1).At ρ = 0.5, it achieves J1 = 0.662 versus 0.616 uniformly and 0.594 under reversed priorities.
  • Allocation comparison: At ρ = 0.5, aggregate adoption is J1 = 0.662 for the optimal allocation, compared with 0.616 for uniform allocation and 0.594 for reversed allocation.The gap is largest at intermediate density values.
  • Priority consistency: For the considered parameters, GMM ≥ GHM ≥ GHH is the only self-consistent water-filling priority pattern across all tested ρ and ℓ.Alternative permutations fail the consistency verification in the reported cases.
  • Priority consistency: The reported priority pattern is associated with βM ≈ 2βH, under which machines respond more strongly to network externalities than humans.This makes machine-machine connections a higher-return investment for promoting coordination in the studied system.

C. Finite human-machine network

The graphon formulation converts network-design optimization into an infinite-dimensional fixed-density problem, and the bimodal rationality setting admits an optimal graphon within stochastic block models. A finite network can be sampled from this block structure, although global optimality and finite-sample guarantees remain open.

  • Finite sampled network: For ρ = 0.35 and ℓ = 0.5, the locally optimal graphon has wMM = 1.00, wHM = 0.20, and wHH = 0.00.The corresponding sampled network contains n = 20 nodes, split into 10 machines and 10 humans, with a complete machine sub-network of 45 edges.
  • Graphon formulation: The population is modeled as a continuum playing a stag-hunt game under logit learning, with topology design formulated as fixed-density optimization over graphons.This mean-field formulation addresses coordination in a population with heterogeneous bounded rationalities.
  • SBM optimality: For a bimodal rationality profile, an optimal graphon exists within the ensemble of stochastic block models.This follows from the result that optimal steady-state and adjoint functions are constant within each agent type.
  • SBM optimality: A greedy water-filling algorithm allocates edge densities across the stochastic-block-model blocks.The algorithm is derived from variational first-order optimality conditions.
  • Limitations and open directions: Global optimality of the SBM over the full graphon class is conjectured but unproved, and finite-sample performance guarantees remain open.Extensions to continuous rationality profiles and distributed convergence algorithms are also identified as future work.
Loading 2608.27851v1…