Bidding for Transitions in Graph Games

26 concepts14 papers1 proposal

In traditional multi-agent systems and game theory, the order of play is usually rigid. In games like chess, players strictly alternate turns; in Markov decision processes, transitions are dictated by fixed stochastic matrices. But what happens when the right to make the next move is itself a scarce resource?

As shown by Kalai et al. (2015) in Bidding Games and Efficient Allocations, extensive-form games can be augmented with explicit bidding phases. Instead of relying on a fixed turn order, players expend resources to dynamically negotiate control over actions based on their current valuations. This framework, known as bidding games on graphs, models scenarios where players submit simultaneous secret bids to win the right to choose the next state transition. The core intuition is that players must balance their long-term strategic goals on the graph against the short-term preservation of their bidding power.

The Mechanics of Payment Rules

The strategic landscape of a bidding game depends fundamentally on where the winning bid goes. As surveyed by Avni et al. (2020) in A Survey of Bidding Games on Graphs, varying the payment scheme drastically alters optimal strategies and the mathematical properties of the game. Three primary payment rules define this space:

  1. Richman Bidding: The winning bidder pays their bid amount directly to the opponent. As explored by Avni et al. (2019) in Infinite-duration Bidding Games, this creates a self-balancing budget system. Losing a bid increases a player's future financial influence, meaning the initial budget ratio has less impact on specific long-term objectives.
  2. Poorman Bidding: The winning bid is paid to a neutral entity or central system, permanently removing those resources from the game. In this setup, studied by Sadhukhan et al. (2023) in Reachability Poorman Discrete-Bidding Games, resources are strictly consumed. Consequently, the initial ratio of the players' budgets critically dictates the guaranteed payoff.
  3. Taxman Bidding: To bridge these two extremes, Avni et al. (2021) introduced a unified framework in Bidding mechanisms in graph games that interpolates between Richman and Poorman rules via a tax parameter $\tau$. Their analysis reveals that as soon as any fraction of the bid is taxed ($\tau < 1$), the game's value becomes highly sensitive to the initial budget ratio, breaking the budget-insensitivity seen in pure Richman bidding.

Information, Discretization, and Budget Dynamics

The complexity of these games intensifies when moving away from idealized, continuous, perfect-information assumptions.

  • Partial Observability: In real-world deployments, players rarely know their opponent's exact financial reserves. Avni et al. (2023) analyzed this in Bidding Graph Games with Partially-Observable Budgets, demonstrating that under partial information, removing funds from the game makes resource management far more critical. Strikingly, they showed that these games do not necessarily possess a single unique "value" when players are restricted to pure strategies.
  • Discrete Bidding: While continuous budgets are mathematically elegant, practical applications require integer bids. Sadhukhan et al. (2023) proved that discrete-bidding games are fully determined and exhibit periodic winning conditions that smoothly converge to continuous models as budgets scale up.
  • Dynamic Replenishment: Rather than treating budgets as strictly finite, Goharshady et al. (2024) introduced Bidding Games with Charging. By allowing players to "recharge" their budgets at designated nodes on the graph, the game shifts from a zero-sum resource exchange into a complex spatial management problem where players must balance the immediate cost of winning transitions against the long-term necessity of reaching replenishment stations.

Mechanism Sensitivity in Complex Auctions

The core insight from graph-based bidding games—that subtle structural rules dictate strategic equilibria—extends directly to macro-level economic auctions. In fact, minor modifications to auction rules can completely upend what constitutes "rational" behavior.

As Weijia Jia outlines in Application of Game Theory in Different Auction Forms, introducing minor variations like hard deadlines or information feedback loops invalidates standard dominant strategies, forcing participants to navigate heightened strategic complexity. This sensitivity manifests across several domains:

  • Iterative and Sequential Auctions: The authors of Sequential Auctions for the Allocation of demonstrate that sequential auctions can effectively manage complex resource complementarities when simultaneous auctions are computationally prohibitive. However, as d'Eon et al. (2024) show using multi-agent reinforcement learning in Understanding Iterative Combinatorial Auction Designs via Multi-Agent Reinforcement Learning, subtle rule changes in how bids are processed can force bidders to adopt highly cautious strategies to maintain eligibility for future rounds, drastically altering revenue outcomes.
  • Market Design and Clearing Rules: In simulated travel markets, O’Malley et al. (2003) observed that specific auction mechanics can inadvertently incentivize artificial behaviors like premature bidding. Similarly, in energy markets, Manvi et al. (2024) note that the success of equilibrium-based bidding strategies is heavily contingent on specific uniform clearing rules, failing to generalize when alternative mechanisms are used. This dependency is echoed by Li et al. (2018), who show that the efficiency of decentralized capacity-price games varies significantly depending on whether a pay-as-bid or a quantity-based Cournot model is employed.

Key Foundational Work

The 2001 Trading Agent Competition (2003) — contributed 2 concept elements to this direction.
Sequential Auctions for the Allocation of Resources with Complementarities (1999) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_auction_mechanism_sensitivity_0cbb3c43,
  title = {auction mechanism sensitivity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/auction-mechanism-sensitivity/rdr_0cbb3c433bbb40ffb9b7c31c5a489125},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_auction_mechanism_sensitivity_0cbb3c43_v1,
  title = {auction mechanism sensitivity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/auction-mechanism-sensitivity/rdr_0cbb3c433bbb40ffb9b7c31c5a489125/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake