Budget Feasible Mechanisms: A Survey

Xiang Liu, Hau Chan, Minming Li, Weiwei Wu, Bo Jiang

Abstract

Budget-feasible mechanisms represent a critical intersection of auction theory and constrained optimization, specifically designed for procurement scenarios where a buyer must maximize utility under a strict budget. This paper provides a taxonomy of these mechanisms based on buyer valuation functions, ranging from simple additive models to complex submodular and non-monotone cases. We review the state-of-the-art approximation ratios, the role of randomization, and the extension of these models to online and crowdsourcing environments.

Introduction

In traditional auctions, multiple buyers compete for items from a seller. However, in many modern applications—such as federated learning, mobile crowdsensing, and cloud resource allocation—the roles are reversed. A single buyer (the requester) seeks to procure services or data from multiple strategic sellers (the workers). This "procurement" setting introduces three primary challenges: private information (sellers may misreport costs), budget constraints (total payments must not exceed a fixed limit), and optimization (maximizing buyer utility).

Budget-feasible mechanisms address these by ensuring truthfulness (incentivizing honest reporting), individual rationality (ensuring sellers do not incur losses), and budget feasibility (guaranteeing total payments stay within the budget).

Valuation Taxonomy and Mechanism Design

The complexity of a budget-feasible mechanism is largely determined by the buyer's valuation function ($V$):

  • Additive Valuations: The simplest case where total value is the sum of individual contributions.
  • Submodular Valuations: Reflects "diminishing returns," where the marginal value of a seller decreases as the buyer procures more services.
  • XOS and Subadditive Valuations: Capture complex dependencies and complementarities between items.

The foundational algorithmic approach for these mechanisms is the Proportional Share Allocation Rule. Sellers are typically sorted by their "density" (value-to-cost ratio). Selection continues as long as a seller's cost is below a threshold proportional to the remaining budget and their marginal contribution. To maintain truthfulness, Threshold Payments are employed, paying winners the maximum cost they could have reported while still being selected.

Performance and Approximation Ratios

Because budget constraints prevent the use of standard social-welfare-maximizing mechanisms like VCG, performance is measured by the approximation ratio ($\alpha$). This ratio compares the mechanism's utility to the theoretical optimum achievable with full information.

Additive and Large Market Scenarios

For additive valuations, deterministic mechanisms have achieved approximation ratios as low as 2.62, while randomized mechanisms can reach a ratio of 2. Under the "Large Market Assumption"—where no single seller's cost is dominant relative to the budget—these ratios improve significantly, approaching $e/(e-1) \approx 1.58$.

Table 1: Approximation ratios for additive valuation functions under different settings and assumptions.

Submodular and Non-Monotone Valuations

As the valuation function becomes more complex, the approximation gap widens. Monotone submodular functions generally see ratios around 4.3 to 4.45. However, non-monotone submodular functions—where adding a seller might actually decrease total value—are significantly more challenging. Recent breakthroughs have reduced these ratios from over 500 to approximately 12.

Table 2: Approximation ratios for monotone, non-monotone, and symmetric submodular valuation functions.

Key Insights

  1. The Budget-Feasibility Gap: Budget constraints act as a "hard wall," making optimization fundamentally more difficult than standard social welfare maximization.
  2. The Power of Randomization: Randomized mechanisms consistently outperform deterministic ones by allowing for more flexible exploration of the solution space.
  3. Online Adaptability: Research is increasingly focusing on online settings where sellers arrive dynamically, requiring immediate, irrevocable decisions without knowledge of future participants.

Future Directions

The field is moving toward relaxing strict economic properties, such as exploring $\epsilon$-truthfulness to gain utility. Additionally, there is a growing interest in Automated Mechanism Design, using machine learning to discover optimal rules for specific domains, and investigating the impact of risk-averse behavior among sellers.

Summary updated

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