Interactive Minority Game simulation: explore N-agent self-organization, strategy emergence, and efficiency phase transitions
The Minority Game (MG), proposed by Challet and Zhang (1997), is a mathematical formalization of Arthur's El Farol Bar Problem. N agents (odd N) simultaneously choose A (attend=1) or B (absent=0). Those on the minority side win. Each agent uses binary history of A(t) (1 if A>N/2, else 0) to decide. Key finding: even with simple deterministic strategies, the system self-organizes into an 'efficient' phase where attendance fluctuations are far below random guessing.
W. Brian Arthur (1994): El Farol bar in Santa Fe has Irish music on Thursdays, capacity 60. 100 people each decide whether to go — fewer than 60 is enjoyable, more is not. No 'correct' strategy exists — if everyone uses the same prediction, it fails (reflexivity). The MG formalizes this with inductive reasoning: agents hold multiple simple strategies and choose the best-performing one.
Classical game theory assumes perfect rationality. The MG models bounded rationality: agents don't optimize globally but maintain s simple strategies (lookup tables based on m-bit history) and pick the best historical performer. The 'weak coalition' effect is striking: individually dumb agents collectively achieve higher efficiency than random — a classic emergence phenomenon.
Each agent holds s strategies, each mapping m-bit history to an action (0 or 1). The key phase transition parameter is α = 2^m / N. At α ≈ 0.34 (2^m ≈ 0.34N), the system transitions from a symmetric phase (low efficiency, σ² ≈ N/4) to an asymmetric phase (high efficiency, σ² < N/4).
Efficiency is measured by attendance variance σ². σ² = N/4 is random guessing level. When α < α_c ≈ 0.34 (short memory, many agents), σ² > N/4 — worse than random due to herding. When α > α_c, σ² < N/4 — self-organized efficiency. The minimum σ² occurs at α = α_c, analogous to critical phenomena in physics (Ising model, percolation).
Total strategies = 2^(2^m), but agents hold only s. When N agents sample from the pool, some strategies are shared by multiple agents — causing crowding. The optimal m satisfies 2^m ≈ 0.34N, balancing information exploitation and strategy diversity.
The MG directly models markets: buyers vs sellers, minority profits (buy low, sell high). MG-predicted σ² behavior matches real market volatility clustering. It explains why technical analysis works in some markets (low diversity→predictable patterns) but not others (high diversity→patterns arbitraged away).
Daily commuting is a minority game: choose the less crowded route. GPS navigation makes this sharper — when everyone is routed to the 'fastest' path, it becomes slow. MG suggests navigation systems should intentionally introduce randomness or differentiated suggestions.
Wi-Fi channel selection, server load balancing, cloud task scheduling — all minority games. MG theory shows distributed algorithms (each node using simple strategies) can achieve near-optimal efficiency without centralized coordination.