Research map / Learning theory and algorithms / Submodular and game algorithms
Truthful Aggregation of Budget Proposals with Proportionality Guarantees
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Uniform Phantom rather than proportional aggregation | Truthful budget aggregation with 2 projects · Budget aggregation, 2 projects | worst-case ℓ1-loss: 1/2 | Helped |
| Use Piecewise Uniform moving phantoms | Truthful budget aggregation with 3 projects · Budget aggregation, 3 projects | worst-case ℓ1-loss: (2/3+ε) | Helped |
| Use Independent Markets instead of Piecewise Uniform | Moving phantom mechanisms · Budget aggregation, 3 projects | worst-case ℓ1-loss: 0.6862 vs. (2/3+ε) | Hurt |
| Require truthfulness | Budget aggregation mechanisms · Budget aggregation, m projects | worst-case ℓ1-loss lower bound: 1/2 | Hurt |
| Restrict mechanisms to moving phantom mechanisms | Truthful budget aggregation · Budget aggregation, m projects | worst-case ℓ1-loss lower bound: 1-1/m | Hurt |
| Use Piecewise Uniform or Independent Markets as the number of projects grows | Proportional moving phantom mechanisms · Budget aggregation, m projects, m ≥ 8 | worst-case ℓ1-loss lower bound: 2- \frac{8}{m^{1/3}} | Hurt |
| Maximize utilitarian social welfare | Utilitarian budget aggregation mechanisms · Budget aggregation, m projects | worst-case ℓ1-loss: 2-\frac{4}{m+1} | Hurt |
Closest papers by meaning
- Project-Fair and Truthful Mechanisms for Budget Aggregation (AAAI 2024 · similarity 0.94)
- A Unified Framework for Uniform-Price Resource Allocation Mechanisms (NeurIPS 2026 · similarity 0.86)
- Fair Division via the Cake-Cutting Share (AAAI 2025 · similarity 0.85)
- Plant-and-Steal: Truthful Fair Allocations via Predictions (NeurIPS 2024 · similarity 0.85)
- On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness (NeurIPS 2025 · similarity 0.84)
- The Distortion of Public-Spirited Participatory Budgeting (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.