Budget-Feasible Mechanism Design: Simpler, Better Mechanisms and General Payment Constraints
Bibliographic record
Abstract
In budget-feasible mechanism design, a buyer wishes to procure a set of items of maximum value from self-interested rational players. We are given an item-set U and a nonnegative valuation function v: 2^U ↦ ℝ_+. Each item e is held by a player who incurs a private cost c_e for supplying item e. The goal is to devise a truthful mechanism such that the total payment made to the players is at most some given budget B, and the value of the set returned is a good approximation to OPT: = max {v(S): c(S) ≤ B, S ⊆ U}. We call such a mechanism a budget-feasible mechanism. More generally, there may be additional side constraints requiring that the set returned lies in some downwards-monotone family ℐ ⊆ 2^U. Budget-feasible mechanisms have been widely studied, but there are still significant gaps in our understanding of these mechanisms, both in terms of what kind of oracle access to the valuation is required to obtain good approximation ratios, and the best approximation ratio that can be achieved. We substantially advance the state of the art of budget-feasible mechanisms by devising mechanisms that are simpler, and also better, both in terms of requiring weaker oracle access and the approximation factors they obtain. For XOS valuations, we devise the first polytime O(1)-approximation budget-feasible mechanism using only demand oracles, and also significantly improve the approximation factor. For subadditive valuations, we give the first explicit construction of an O(1)-approximation mechanism, where previously only an existential result was known. We also introduce a fairly rich class of mechanism-design problems that we dub using the umbrella term generalized budget-feasible mechanism design, which allow one to capture payment constraints that are much-more nuanced than a single constraint on the total payment doled out. We demonstrate the versatility of our ideas by showing that our constructions can be adapted to yield approximation guarantees in such general settings as well. A prominent insight to emerge from our work is the usefulness of a property called nobossiness, which allows us to nicely decouple the truthfulness + approximation, and budget-feasibility requirements. Some of our constructions can be viewed as reductions showing that an O(1)-approximation budget-feasible mechanism can be obtained provided we have a (randomized) truthful mechanism satisfying nobossiness that returns a (random) feasible set having (expected) value Ω(OPT).
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.016 | 0.037 |
| Meta-epidemiology (narrow) | 0.003 | 0.002 |
| Meta-epidemiology (broad) | 0.004 | 0.004 |
| Bibliometrics | 0.002 | 0.004 |
| Science and technology studies | 0.001 | 0.002 |
| Scholarly communication | 0.005 | 0.023 |
| Open science | 0.006 | 0.003 |
| Research integrity | 0.005 | 0.008 |
| Insufficient payload (model declined to judge) | 0.012 | 0.002 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".