Research map / Learning theory and algorithms / Prediction and decision losses
Mechanism design augmented with output advice
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces mechanism design with output advice (a recommended outcome rather than predicted types), measured by a new "quality of recommendation" metric, and derives consistency/robustness/smoothness results for facility location, scheduling, house allocation, and auctions.
Problem
Strategyproof mechanism design with machine-learned advice about the outcome (not the agent types), where performance should degrade gracefully with the quality of the recommended outcome.
Approach
Replace type-prediction error with a universal quality-of-recommendation metric: the approximation ratio of the recommended outcome's cost (or welfare) to the optimum on the true input. The recommendation is plugged into existing mechanisms (minimum bounding box, coordinatewise median with predictions, AllocationScaledGreedy, TTC, maximal-in-range VCG) to obtain refined bounds.
Key results
- Minimum Bounding Box is min{quality of recommendation, sqrt(2)+1}-approximate for egalitarian facility location, and the bound is tight.
- AllocationScaledGreedy for scheduling is (beta+1)-consistent and n^2/beta-robust, with an asymptotically tight min{(beta+1)err, n+err, n^2/beta} approximation.
- On real location datasets, the quality of recommendation grows more slowly than the prediction error eta, which can grow very large (e.g., Earthquake).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use recommendation quality $\err$ to analyze Minimum Bounding Box | Facility Location (egalitarian) · Facility Location (egalitarian) | approximation ratio: $\min\{\err, \sqrt{2}+1\}$ | Helped |
| use recommendation quality $\err$ to analyze Coordinatewise Median with Predictions | Facility Location (utilitarian) · Facility Location (utilitarian) | approximation ratio: $\min\{\sqrt{2}\err, \err + \sqrt{2}, \frac{\sqrt{2\lambda^2+2}}{1-\lambda}\}$ | Helped |
| add output recommendation and tune confidence parameter $\beta$ | AllocationScaledGreedy · Unrelated-machine scheduling (makespan) | approximation ratio: $\min\{(\beta + 1)\err, n+\err, \frac{n^2}{\beta}\}$ | Helped |
| use the recommendation as the initial endowment for TTC | House Allocation · House Allocation (unit-range valuations) | approximation ratio: $\min\{\err, n\}$ | Helped |
| add the recommended outcome to the maximal-in-range mechanism's range | Combinatorial auctions · Combinatorial auctions | approximation ratio: $\min\{\err, \rho_M\}$ | Helped |
| use quality of recommendation $\err$ rather than prediction error $\eta$ for the utilitarian facility-location analysis | Coordinatewise Median with Predictions · Facility Location (utilitarian) | approximation ratio bound accuracy: $\sqrt{2}\err = 1.618$; $\frac{\sqrt{2\lambda^2+2}}{1+\lambda} + \eta > 1 + \eta = 1.707$ | Helped |
| use quality of recommendation $\err$ rather than prediction error $\eta$ for the egalitarian facility-location analysis | Minimum Bounding Box · Facility Location (egalitarian) | approximation ratio bound accuracy: $\err = \sqrt{2.5} \approx 1.581$; $\eta= 1/\sqrt{2} \approx 0.707 | Helped |
Surprising findings
- Prediction error (eta) can be arbitrarily large while the optimal outcome is unchanged, so eta-based bounds can be overly pessimistic.
- Existing SimpleScaledGreedy and ScaledGreedy mechanisms are not smooth: approximation ratio is Omega(n) for prediction error arbitrarily close to 1.
Limitations
- Lower bounds on consistency-robustness trade-off are shown only within the class of weighted VCG mechanisms
- Experiments are limited to facility location on location datasets with one mechanism
- Scheduling consistency is stated as (beta+1), which is approximate and exact only as (n-1)beta/n+1
Experimental setup
Datasets: Twitter Brightkite Gowalla Earthquake Autotel
Benchmarks: Twitter Brightkite Gowalla Earthquake Autotel
Metrics: quality of recommendation prediction error eta approximation ratio
Baselines: Minimum Bounding Box mechanism Coordinatewise Median with Predictions SimpleScaledGreedy ScaledGreedy VCG
Builds on: learning-augmented framework (consistency and robustness) Coordinatewise Median with Predictions SimpleScaledGreedy / ScaledGreedy maximal-in-range VCG
Closest papers by meaning
- Recommender Ecosystems: A Mechanism Design Perspective on Holistic Modeling and Optimization (AAAI 2024 · similarity 0.88)
- Strategic Linear Contextual Bandits (NeurIPS 2024 · similarity 0.87)
- Learning to Recommend in Unknown Games (NeurIPS 2026 · similarity 0.85)
- Automated Design of Affine Maximizer Mechanisms in Dynamic Settings (AAAI 2024 · similarity 0.85)
- Nash Incentive-compatible Online Mechanism Learning via Weakly Differentially Private Online Learning (ICML 2024 · similarity 0.85)
- Online Information Acquisition: Hiring Multiple Agents (ICLR 2024 · similarity 0.85)
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.