Decentralized Resource Contention in Multi Player Bandits

129 concepts101 papers1 proposal

Imagine a crowded room where multiple people are trying to connect to a limited number of Wi-Fi channels. If two people attempt to transmit on the same channel at the exact same millisecond, their signals interfere, resulting in a packet collision where neither receives any data. Crucially, there is no central router assigning channels, and the users cannot talk to one another to coordinate. Each user must independently figure out which channels are high-quality while simultaneously learning how to stay out of everyone else's way.

This scenario defines the core challenge of decentralized resource contention in multi-player multi-armed bandits (MP-MABs) and matching markets. It flips the classic exploration-exploitation tradeoff on its head: agents must not only learn the environmental rewards of available resources but must also implicitly coordinate to orthogonalize their choices.

The Multi Player Collision Problem

In a standard multi-armed bandit problem, a single agent pulls an arm, observes a stochastic reward, and updates its strategy. However, as noted by Amir Leshem et al. in Game of Thrones: Fully Distributed Learning for Multiplayer Bandits, when multiple independent players share the same environment, simultaneous selection of the same resource causes a collision that zeroes out the reward for all involved parties.

This introduces a severe coordination gap. As Keqin Liu et al. explain in Decentralized Multi-Armed Bandit with Multiple Distributed Players, maximizing the total system utility requires agents to find a conflict-free allocation—effectively partitioning the optimal arms among themselves—without any centralized oversight or direct communication.

The Confounded Feedback Signal

What makes this problem mathematically vexing is the information blindspot it creates. In many practical settings, agents suffer from a lack of collision sensing.

Chengshuai Shi demonstrates in Decentralized Multi-player Multi-armed Bandits with No Collision Information that when an agent selects an arm and receives a reward of zero, the feedback signal is confounded. The agent cannot easily distinguish between two entirely different realities:

  1. The arm is inherently low-quality (high variance or low mean reward).
  2. The arm is highly lucrative, but another agent happened to select it at the same time.

If an agent mistakes a collision for poor resource quality, it might prematurely abandon an optimal arm, leading to suboptimal long-term performance (high regret). Conversely, if it blindly persists, it will suffer continuous collisions.

Mechanisms for Uncoordinated Coordination

To bypass this blindspot without a central coordinator, researchers have engineered several decentralized protocols that allow coordination to naturally emerge from local feedback.

Musical Chairs: Lock-In on Success

One intuitive approach is the "Musical Chairs" paradigm introduced by Jonathan Rosenski et al. in Multi-Player Bandits - a Musical Chairs Approach. The algorithm operates in two phases:

  • Exploration: Players randomly sample arms to estimate the top $N$ resources available in the environment.
  • Exploitation (The Game): Players randomly choose among these top $N$ arms. If a player selects an arm and experiences no collision, they "sit down"—meaning they fixate on that arm for all remaining rounds.

Because a seated player never leaves their arm, the pool of available optimal arms shrinks for the remaining unseated players, who continue to scramble for the remaining "chairs" until everyone is conflict-free.

Collision-Penalized Indexing

When agents cannot explicitly see whether a collision occurred, they can modify their decision-making metrics to account for interference implicitly. In {Multi-Player Bandits Revisited}, Lilian Besson et al. show that integrating collision penalties directly into reward estimation indices (like the Upper Confidence Bound, or UCB) forces natural agent dispersion.

By treating a collision simply as a zero-value reward sample, the empirical mean of a highly contested arm drops rapidly. This makes the resource appear less attractive than a slightly lower-quality, uncontested arm, causing agents to naturally self-segregate across the resource pool.

Hacking Collisions as Communication

Perhaps the most radical insight in this domain is that collisions do not have to be purely destructive; they can be repurposed as a signaling mechanism.

Etienne Boursier et al. prove in SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits that players can use deliberate, structured collisions to transmit information. By intentionally colliding on specific arms at specific times, agents can broadcast their internal rankings and statistics to one another. This "collision-based protocol" allows decentralized systems to match the theoretical performance bounds of a fully centralized controller.

Extending to Two-Sided Matching Markets

The challenges of uncoordinated resource contention extend beyond identical channel selection into two-sided matching markets (such as freelance platforms or ride-sharing networks), where both the agents and the resources have distinct preferences.

As surveyed by Shuai Li et al. in A Survey on Bandit Learning in Matching Markets, when multiple agents simultaneously attempt to match with the same preferred target, the target accepts only its top choice. The rejected agents receive zero utility and learn nothing about their own compatibility with that target.

To resolve this competitive interference, algorithms like ML-ETC, developed by Yirui Zhang et al. in Matching in Multi-arm Bandit with Collision, combine multi-layer exploration phases with collision-based signaling. These methods allow decentralized participants to converge to a stable, globally optimal matching configuration, proving that stable market equilibria can be achieved purely through trial, error, and strategic friction.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 104 papers
  2. Version 1 · 2026-10-04 · 219 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_decentralized_resource_contention_dce2ba04,
  title = {decentralized resource contention},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/decentralized-resource-contention/rdr_dce2ba04cb2f43128a0214ed95307d9b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_decentralized_resource_contention_dce2ba04_v2,
  title = {decentralized resource contention},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/decentralized-resource-contention/rdr_dce2ba04cb2f43128a0214ed95307d9b/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake