📈 economics

Rapid evolution under heterogeneous linking costs

This paper demonstrates that in a social coordination model with endogenous network formation and heterogeneous linking costs, the presence of high-cost agents can accelerate convergence to payoff-dominant conventions and shape equilibrium diversity, particularly when agents are limited to linking with fewer than half the population.

Original authors: Zhiwei Cui, Jinhua Liu

Published 2026-09-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhiwei Cui, Jinhua Liu

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the quiet machinery of social life, people constantly face a choice: stick with what is safe and familiar, or risk moving toward something better. This is the essence of a coordination problem, a situation where success depends not just on one's own decision, but on whether others make the same choice. Think of a community deciding between two different technologies, like two competing software languages. If everyone picks the same one, they can communicate and work together efficiently. If they split, the system breaks down. Usually, the group tends to settle on the option that is easiest to coordinate on, even if it is not the most powerful or profitable one. This happens because people are often too afraid to switch to the better option unless they are sure everyone else will follow.

Researchers have long studied how these groups eventually find their way to the best possible outcome. A key factor in this process is how people connect with one another. In many real-world scenarios, forming a connection is not free; it requires time, effort, or resources. Some people might find it easy to build these bridges, while others face steep barriers. A new study by Zhiwei Cui and Jinhua Liu at Renmin University of China explores what happens when a group contains a mix of people with very different costs for making connections. They ask whether these differences in cost might actually help the group escape a mediocre state and rush toward a superior one, rather than slowing them down as one might expect.

The researchers built a model of a finite group of people who must choose between two actions, which we can call Option A and Option B. Option A is the safe choice; it is the one people are most likely to pick if they are unsure what others will do. Option B is the better choice; if everyone picks it, the group earns the highest possible reward. However, reaching Option B is difficult because it requires a critical mass of people to switch first. In this model, people also decide who they will interact with. They can form links with others, but each link comes with a price tag. The study introduces a twist: some people pay a low price for these links, while others pay a high price. The high-cost individuals face a strict limit on how many connections they can afford to maintain, while the low-cost individuals have more freedom.

When the researchers analyzed the stable states of this system, they discovered something surprising. In a world where everyone pays the same price for connections, the group usually ends up stuck in the safe, less efficient Option A. But when a small number of people face high connection costs, a new kind of balance emerges. In this mixed group, the high-cost individuals naturally gravitate toward the better Option B, while the low-cost individuals stick with the safe Option A. This happens because the high-cost people cannot afford to waste their limited connections on the wrong group; they must focus entirely on the better option to make their few links worthwhile. This creates a stable situation where the two groups coexist, each playing a different role.

The most significant finding concerns how quickly the group moves from the safe state to the better state. The researchers simulated a process where people occasionally make mistakes or try new strategies, allowing the group to explore different outcomes over time. They measured the "waiting time," which is essentially how long it takes for the group to stumble upon the better convention and lock into it. In a group where everyone has low connection costs, this waiting time is very long, growing exponentially as the group size increases. However, the presence of even a small number of high-cost agents drastically shortens this wait. These high-cost individuals act as a catalyst. Because they are so constrained, they are much easier to convince to switch to the better option. Once a few of them switch, they pull the rest of the group along with them, accelerating the transition to the superior outcome.

The study shows that this acceleration is not just a slight improvement but a fundamental shift in the speed of evolution. The waiting time drops to a much lower order of magnitude, meaning the group reaches the efficient solution far faster than it would otherwise. This happens because the high-cost agents serve as a bridge; their constraints force them to adopt the better strategy sooner, which in turn makes it easier for the low-cost agents to follow. The researchers found that this effect holds true as long as the number of links any single person can form is less than half the total population. If the population is too large relative to the number of links people can make, the dynamics change, but within the studied limits, the high-cost minority acts as a powerful engine for progress.

This work challenges the intuition that friction and constraints always slow things down. In the context of social coordination, having a subgroup that faces higher barriers to connection actually helps the whole system move more quickly toward the best possible outcome. While the high-cost individuals pay a personal price for their limited connections, the group as a whole benefits from their presence. The study suggests that diversity in the costs of interaction is not just a complication to be managed, but a feature that can drive efficiency. By understanding how these different costs shape behavior, we can see that the path to a better collective future might be paved by the very people who find the journey most difficult.

Technical Summary: Rapid Evolution under Heterogeneous Linking Costs

Problem Statement
This paper investigates the long-run outcomes of social coordination in a setting where agents simultaneously choose an action in a $2 \times 2$ coordination game and endogenously form costly links with other agents. The central problem addresses two issues: (1) whether agents coordinate on the same action, and (2) whether they coordinate on the most efficient (payoff-dominant) action. The study specifically explores the impact of heterogeneous linking costs, where a subset of agents incurs high costs per link while others incur low costs. This heterogeneity introduces constraints on network formation that differ from existing models where agents face uniform costs. The authors aim to determine how these cost differences affect the existence of mixed-action equilibria and the speed of convergence to efficient conventions under perturbed learning dynamics.

Methodology
The authors employ a model of a finite population of $n$ agents engaging in a symmetric $2 \times 2$ coordination game with actions $A$ (risk-dominant) and $B$ (payoff-dominant). The payoff structure satisfies $b > a > c > d > 0$ , where $(B,B)$ is payoff-dominant and $(A,A)$ is risk-dominant.

Network Formation: Agents form directed links to interact. Each agent $i$ faces a constraint on the number of outgoing links, $k \leq n-1$ . Crucially, agents incur heterogeneous costs: a low cost $\gamma_l$ (where $0 \leq \gamma_l \leq d$ ) for a subset $I_l$ and a high cost $\gamma_h$ (where $d < \gamma_h \leq c$ ) for a subset $I_h$ .
Strategy: A pure strategy consists of an action choice and a linking decision. Payoffs are the sum of interaction payoffs minus the total cost of maintained links.
Dynamics: The authors analyze the system using perturbed myopic best-response dynamics (à la Kandori, Mailath, and Rob, 1993; Young, 1993). Agents update strategies to maximize current payoffs with probability $1-\rho$ and make random mistakes (mutations) with probability $\rho$ .
Stochastic Stability: The long-run behavior is characterized by identifying stochastically stable states (the support of the limit invariant distribution as $\rho \to 0$ ).
Convergence Speed: The paper calculates the expected waiting time to reach the basin of attraction of the stochastically stable states. This is measured using the order of magnitude in terms of the mutation probability $\epsilon$ (specifically $\Theta(\epsilon^{-c})$ ), utilizing the Radius-(Modified) Coradius theorem (Ellison, 2000) and iterative cycle decompositions.

Key Contributions

Existence of Action-Heterogeneous Nash Equilibria: Unlike previous models with homogeneous linking costs (e.g., Staudigl and Weidenholzer, 2014), this paper demonstrates that when linking costs are heterogeneous, action-heterogeneous Nash equilibria can exist. In these equilibria, agents with low linking costs play the risk-dominant action ( $A$ ), while agents with high linking costs play the payoff-dominant action ( $B$ ). This occurs because high linking costs restrict the ability of high-cost agents to form links with $A$ -players, making it optimal for them to cluster with other $B$ -players.
Stochastic Stability with Constraints: The authors establish that if agents can form links with fewer than half the population ( $k \leq (n-1)/2$ ), the payoff-dominant convention (where all agents play $B$ ) is the unique stochastically stable state, even in the presence of heterogeneous costs.
Acceleration of Convergence: The primary contribution is the demonstration that the presence of high-linking-cost agents accelerates convergence to the payoff-dominant convention. The paper quantifies this by showing that the order of the expected waiting time is strictly lower in the heterogeneous case compared to a homogeneous low-cost benchmark.

Key Results

Nash Equilibria: Action-heterogeneous equilibria exist if and only if the number of high-cost agents ( $n_h$ ) falls within a specific range defined by the game parameters and the link constraint $k$ . In these equilibria, $I_l$ plays $A$ and $I_h$ plays $B$ .
Stochastic Stability (Theorem 1): Under the constraint $k \leq (n-1)/2$ , the set of stochastically stable states $S^*$ consists solely of the profile where all agents play $B$ and form $k$ links ( $\vec{B}$ ). The intuition is that once a sufficient number of agents play $B$ , it becomes optimal for everyone to switch, and exiting this basin requires more mutations than entering it.
Waiting Time (Theorem 2): The expected waiting time $W(S^*, \epsilon)$ $W (S^{*}, ϵ)$ to reach the payoff-dominant state is of a strictly lower order in the presence of heterogeneity.
- In a homogeneous low-cost benchmark (Staudigl and Weidenholzer, 2014), the waiting time is of order $\Theta(\epsilon^{-\lceil \frac{a-d}{b-d}k \rceil})$ .
- In the heterogeneous model, the waiting time is of order $\Theta(\epsilon^{-c^*})$ or $O(\epsilon^{-\min\{c^*, c^{**}\}})$ , where $c^*$ and $c^{**}$ are strictly smaller than the homogeneous benchmark exponent (provided $k$ is large).
- Mechanism: High-linking-cost agents act as a "catalytic minority." Because they face tighter constraints, fewer mutations (switches from $A$ to $B$ ) are required to trigger a cascade where the high-cost agents switch to $B$ , which in turn induces the low-cost agents to switch. This "reforming effect" reduces the number of mutations needed to escape the risk-dominant basin.

Significance and Claims
The paper claims that heterogeneity in linking costs shapes both equilibrium diversity and the speed of convergence toward efficient conventions.

Efficiency vs. Diversity: While heterogeneous costs allow for the existence of mixed-action equilibria (diversity) in the short run, the long-run stochastic stability still selects the efficient (payoff-dominant) convention.
Speed of Evolution: The presence of a small group of agents with high linking costs serves to accelerate the evolution toward the efficient convention. The authors argue that this "reform effect" implies that limited welfare losses for high-cost agents (due to their high costs) can yield positive social benefits by improving the coordination efficiency of the entire population.
Policy/Design Implication: The findings suggest that introducing or maintaining friction (high costs) for a specific subgroup can paradoxically speed up the adoption of socially optimal standards, provided the population size and link constraints allow for the catalytic mechanism to function.

The authors remain modest in their scope, noting that obtaining the exact order of waiting time in all parameter regions is computationally cumbersome due to the complexity of iterative cycle decompositions, and thus they provide tight upper bounds and specific cases where exact orders are derived. They do not propose new experimental designs but rather extend existing theoretical frameworks (Staudigl and Weidenholzer, 2014; Cui and Shi, 2022) to incorporate cost heterogeneity.

Technical Summary: Rapid Evolution under Heterogeneous Linking Costs

More like this