Budget Feasible Mechanisms: A Survey

Xiang Liu, Hau Chan, Minming Li, Weiwei Wu

Introduction

Budget Feasible Mechanisms (BFM) represent a specialized class of procurement auctions where a buyer seeks to maximize a valuation function while adhering to a strict budget constraint. Unlike standard auctions where sellers aim to maximize revenue, procurement auctions involve a buyer acquiring items or services from multiple sellers. The primary challenge in BFM design is ensuring that the mechanism remains incentive-compatible (truthful) and budget-feasible simultaneously. This survey explores over a decade of research, tracing the evolution of these mechanisms from simple additive models to complex submodular and subadditive functions.

The Core Challenge: Truthfulness vs. Budget

In a typical procurement setting, a buyer might use a standard Vickrey-Clarke-Groves (VCG) auction to ensure truthfulness. However, VCG payments often exceed the buyer's budget $B$. To address this, BFM designers must craft rules where:

  1. Incentive Compatibility (Truthfulness): Sellers are incentivized to report their true costs.
  2. Budget Feasibility: Total payments to winners never exceed $B$.
  3. Efficiency: The mechanism achieves a high approximation ratio relative to the optimal (but often NP-hard) selection.

Algorithmic Foundations

The field, pioneered by Singer in 2010, relies on several core algorithmic strategies to balance these competing goals. Most mechanisms utilize a Proportional Share Allocation Rule, which typically involves:

  • Greedy Selection: Sellers are ranked by a cost-efficiency ratio (Value/Cost).
  • Threshold Payments: To maintain truthfulness, winners are paid a "threshold" price—the maximum bid they could have submitted while still winning—rather than their actual bid.
  • Randomization: Randomized mechanisms often outperform deterministic ones by smoothing out worst-case scenarios, leading to tighter approximation ratios.

Performance Bounds and Valuation Hierarchies

The complexity of designing a BFM depends heavily on the buyer's valuation function. The research community has established a hierarchy of difficulty, ranging from simple additive functions to complex subadditive functions.

Additive Valuations

For additive functions, where the total value is the sum of individual items, the bounds have been significantly refined. Early work established a deterministic approximation ratio of 5, which has since been improved. Notably, under the "Large Market Assumption"—where no single seller's cost is significant relative to the budget—the approximation ratio approaches the theoretical limit of $e/(e-1)$.

Table 1: Evolution of approximation ratios for additive valuation functions under various market assumptions.

Submodular Valuations

Submodular functions, which model diminishing returns, present a greater challenge. The survey highlights a clear gap between monotone and non-monotone submodular functions. While monotone functions currently see approximation ratios as low as 4.3 (randomized), non-monotone functions remain much harder to approximate, with current best-in-class results reaching 12 for randomized and 64 for deterministic settings.

Table 2: Summary of state-of-the-art approximation ratios for submodular valuation functions across different literature.

Key Insights

  • The "Information Rent": To ensure truthfulness, buyers must often pay sellers more than their reported costs. This "rent" is the primary obstacle to staying within budget while maximizing value.
  • Market Scale: Approximation ratios improve significantly in large markets, where the influence of any single participant is minimized.
  • Beyond Static Auctions: Recent research has expanded into online settings (where sellers arrive sequentially) and two-sided markets involving multiple buyers and sellers.

Future Directions

The survey identifies several emerging frontiers in BFM research:

  • Approximate Economic Properties: Exploring $\epsilon$-truthful mechanisms that might offer better performance by relaxing the requirement for perfect truthfulness.
  • Automated Mechanism Design: Utilizing deep learning to learn optimal auction rules for specific seller distributions.
  • Non-linear Utility: Moving beyond the standard Payment - Cost model to account for risk-averse sellers or participants with their own internal budget constraints.

Summary updated

BibTeX
@inproceedings{liu2024budget,
  author = {Xiang Liu and Hau Chan and Minming Li and Weiwei Wu},
  title = {{Budget Feasible Mechanisms: A Survey}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure