The Impact of Locality and Authority on Emergent Conventions: Initial Observations

James E. KittockAAAI 1994

Introduction

In multi-agent systems (MAS), such as swarms of autonomous robots or distributed software agents, achieving global coordination is a fundamental challenge. While designers can manually specify conventions—like "always drive on the right"—dynamic and complex environments often require these rules to emerge spontaneously through agent interaction, a process known as co-learning. This paper investigates how two critical real-world factors, locality (spatial or organizational proximity) and authority (asymmetric influence), shape the speed and success of this emergent consensus.

The Coordination Framework

The study utilizes a formal simulation where agents choose between two strategies, A and B. Coordination is modeled as a game where agents receive a positive reward for matching their neighbor's strategy and a penalty for mismatching.

The payoff matrix defining the rewards for agent interactions.

Agents update their strategies using the Highest Cumulative Reward (HCR) rule. With a minimal memory of just two interactions, agents select the strategy that has provided the highest total utility in their recent history. This simple local rule serves as the engine for global convention emergence.

The Role of Locality

In many theoretical models, agents are "well-mixed," meaning any agent can interact with any other. However, real-world agents are often constrained by geography or network topology. The author models this by placing agents on a 2D grid where the probability of interaction decays with distance.

Simulation of convention emergence over time (t) on a 32x32 grid. The "more constrained" scenario (top) shows the formation of stable sub-societies, while the "less constrained" scenario (bottom) converges more rapidly.

As shown in Figure 4, high locality constraints lead to the formation of "sub-societies" or islands of differing conventions. These macroscopic structures become self-reinforcing; agents in the center of an "A" island rarely interact with "B" agents, making the global transition to a single convention a slow process of boundary erosion. The convergence time on these grids scales polynomially with the number of agents ($O(n^{1.28})$ to $O(n^{1.45})$).

Authority and the Hierarchy Paradox

The paper further explores organizational structures: Trees (where agents only interact with parents and children) and Hierarchies (where agents also interact with peers). Authority is modeled as asymmetric feedback: a "boss" may ignore a "subordinate's" strategy, effectively forcing their own choice downward.

A surprising "Hierarchy Paradox" emerges: adding more communication channels can actually hinder coordination. In a strict Tree with high top-down authority, a convention flows efficiently from the root to the leaves, leading to fast, polynomial convergence ($O(n^{1.85})$). However, in a Hierarchy, peer-to-peer interactions "dilute" this top-down signal. Agents at the same level may coordinate with each other on a strategy that conflicts with their boss, creating local deadlocks that result in exponential convergence times ($O(e^{0.26n})$).

Conclusion

These initial observations suggest that more connectivity is not always better for multi-agent coordination. While locality naturally creates persistent sub-cultures, the introduction of horizontal communication in hierarchical systems can create significant friction against top-down consensus. For designers of autonomous systems, these results highlight a trade-off: strict, autocratic structures may be more efficient for rapid global alignment, whereas peer-to-peer interaction, while robust, may require bosses to be more "attentive" to subordinates to break local stalemates.

Summary updated

BibTeX
@inproceedings{kittock1994impact,
  author = {James E. Kittock},
  title = {{The Impact of Locality and Authority on Emergent Conventions: Initial Observations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure