Research map / Multi-agent systems and games / Games and equilibria
Mechanism Design via the Interim Relaxation
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 an interim-relaxation framework for multi-agent revenue maximization built on two-level (online) contention resolution schemes, yielding sequential BIC-IR mechanisms with approximation guarantees such as 2e/(e-1) for matroid constraints and 10 for knapsack.
Problem
Revenue maximization for agents with additive preferences under downward-closed feasibility constraints, where Alaei's ex-ante relaxation framework is limited to ex-post supply constraints.
Approach
Replace the ex-ante relaxation with an interim relaxation feasible in expectation, and round it using two-level (C)OCRSs that allow structured dependence between elements of the same agent (row-wise conditional independence given the agent's type), with a Bernoulli factory for division to implement the required coins.
Key results
- Sequential BIC-IR mechanism with 2e/(e-1) ≈ 3.16 approximation to optimal revenue for additive agents under matroid VH constraints.
- A (b, 1/(2+8b))-selectable tOCRS for Knapsack, implying a 1/10-selectable OCRS for knapsack; yields a 10-approximate sequential mechanism for knapsack-constrained item auctions and 9 for multi-choice knapsack.
- A new stochastic knapsack OCRS that is max{(1-k*)/(2-k*), 1/6}-selectable, improving on Feldman et al. when k* ≤ 1/3, and yielding a 3+e^-2 (≈3.13) approximate sequential procurement auction when combined with Jiang et al.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the interim relaxation and matroid tOCRS instead of the prior sequential mechanism | Sequential matroid-constrained auction · Matroid Vertical-Horizontal auction | revenue approximation factor: 70 -> 3.16 | Helped |
| Use the new knapsack OCRS when k* is small (k* ≤ 1/3) | Stochastic Knapsack OCRS · Stochastic Knapsack | selectability: \max\{\frac{1-k^*}{2-k^*}, \frac{1}{6} \} vs. \frac{1}{3+e^{-2}} | Helped |
| Use the new knapsack OCRS rather than the Feldman et al. knapsack OCRS | Knapsack OCRS · Knapsack constraints | selectability: 0.1 vs. 0.085 | Helped |
| Use the new knapsack OCRS rather than the Jiang et al. knapsack OCRS | Knapsack OCRS · Knapsack constraints | selectability: 0.1 vs. 0.319 | Hurt |
| Use the interim-relaxation framework for additive agents under knapsack feasibility | Sequential knapsack auction · Knapsack auction | revenue approximation factor | Helped |
| Use the interim-relaxation framework with the multi-choice knapsack tOCRS | Sequential multi-choice knapsack auction · Multi-Choice Knapsack auction | revenue approximation factor | Helped |
| Use the interim-relaxation framework with the stochastic knapsack OCRS | Sequential procurement auction · Stochastic Knapsack procurement auction | value approximation factor: 3+e^{-2} (≈ 3.13) | Helped |
Limitations
- Efficient end-to-end computation depends on whether feasibility polytopes have polynomial representations (e.g., matroid constraints may be exponential).
- Sequential mechanisms in the matroid case have constant approximation (2e/(e-1)) but no simplicity guarantees such as posted prices.
- Approximate coin-flipping for knapsack incurs a small loss in the selectability constant.
Experimental setup
Metrics: approximation ratio to optimal revenue selectability constant
Baselines: Cai and Zhao sequential mechanism (70-approximation) Feldman et al. OCRS for knapsack (0.085) Jiang et al. OCRS for stochastic knapsack (1/(3+e^-2))
Builds on: Alaei ex-ante relaxation framework contention resolution schemes online contention resolution schemes Bernoulli factory for division (Morina)
Closest papers by meaning
- A Unified Framework for Uniform-Price Resource Allocation Mechanisms (NeurIPS 2026 · similarity 0.87)
- 1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations (AAAI 2024 · similarity 0.87)
- Fair Allocation in Dynamic Mechanism Design (NeurIPS 2024 · similarity 0.86)
- Non-stochastic Budgeted Online Pricing with Semi-Bandit Feedback (AAAI 2025 · similarity 0.86)
- Optimal Mechanism in a Dynamic Stochastic Knapsack Environment (AAAI 2024 · similarity 0.86)
- Procurement Auctions via Approximately Optimal Submodular Optimization (ICML 2025 · similarity 0.86)
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.