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:
- Incentive Compatibility (Truthfulness): Sellers are incentivized to report their true costs.
- Budget Feasibility: Total payments to winners never exceed $B$.
- 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)$.
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.
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 - Costmodel to account for risk-averse sellers or participants with their own internal budget constraints.
Summary updated