Lune

NeurIPS2025Top-tier venue

Mechanism Design via the Interim Relaxation

Kshipra Bhawalkar, Marios Mertzanidis, Divyarthi Mohan, Alexandros Psomas

Abstract

We study revenue maximization for agents with additive preferences, subject to downward-closed constraints on the set of feasible allocations. In seminal work, Alaei [Ala14] introduced a powerful multi-to-single agent reduction based on an ex-ante relaxation of the multi-agent problem. This reduction employs a rounding procedure which is an online contention resolution scheme (OCRS) in disguise, a now widely-used method for rounding fractional solutions in online Bayesian and stochastic optimization problems. In this paper, we leverage our vantage point, 10 years after the work of Alaei, with a rich OCRS toolkit and modern approaches to analyzing multi-agent mechanisms; we introduce a general framework for designing non-sequential and sequential multi-agent, revenue-maximizing mechanisms, capturing a wide variety of problems Alaei's framework could not address. Our framework uses an interim relaxation, that is rounded to a feasible mechanism using what we call a two-level OCRS, which allows for some structured dependence between the activation of its input elements. For a wide family of constraints, we can construct such schemes using existing OCRSs as a black box; for other constraints, such as knapsack, we construct such schemes from scratch. We demonstrate numerous applications of our framework, including a sequential mechanism that guarantees a 2e e-1 ≈ 3.16 approximation to the optimal revenue for the case of additive agents subject to matroid feasibility constraints. The simplicity of our developed two-level CRSs and OCRSs highlights the strength of our framework: even with a simple analysis, it yields state-of-the-art approximation guarantees across a wide range of settings. Finally, we show how it naturally extends to multi-parameter procurement auctions.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

2 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • From Welfare to Utility: Generalized Objectives in Budget-Feasible Procurement cites Tight Guarantees for Multi-unit Prophet Inequalities and Online Stochastic Knapsack
  • Hallucinating Flows for Optimal Mechanisms cites An Efficient ∊-BIC to BIC Transformation and Its Application to Black-Box Reduction in Revenue Maximization
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. From Welfare to Utility: Generalized Objectives in Budget-Feasible ProcurementAlon Eden, Kira Goldner, Eldar Kerner, Thodoris TsilivisICML 2026 · 2 citations
  2. Hallucinating Flows for Optimal MechanismsMarios Mertzanidis, Athina TerzoglouSODA 2026 · 1 citation

Builds on7

  1. An O(log log m) Prophet Inequality for Subadditive Combinatorial AuctionsPaul Dütting, Thomas Kesselheim, Brendan LucierFOCS 2020 · 22 citations
  2. Tight Guarantees for Multi-unit Prophet Inequalities and Online Stochastic KnapsackJiashuo Jiang, Will Ma, Jiawei ZhangSODA 2022 · 20 citations
  3. An Efficient ∊-BIC to BIC Transformation and Its Application to Black-Box Reduction in Revenue MaximizationYang Cai, Argyris Oikonomou, Grigoris Velegkas, Mingfei ZhaoSODA 2021 · 10 citations
  4. On Infinite Separations Between Simple and Optimal MechanismsAlexandros Psomas, Ariel Schvartzman, S. Matthew WeinbergNeurIPS 2022 · 8 citations
  5. Simple Mechanisms for Welfare Maximization in Rich Advertising AuctionsGagan Aggarwal, Kshipra Bhawalkar, Aranyak Mehta, Divyarthi Mohan et al.NeurIPS 2022 · 8 citations

Related papers

  1. A Multi-Dimensional Online Contention Resolution Scheme for Revenue MaximizationShuchi Chawla, Dimitris Christou, Trung Dang, Zhiyi Huang et al.SODA 2025
  2. Simple and Optimal Greedy Online Contention Resolution SchemesVasilis LivanosNeurIPS 2022 · 1 citation
  3. Fully Dynamic Online Selection through Online Contention Resolution SchemesVashist Avadhanula, Andrea Celli, Riccardo Colini-Baldeschi, Stefano Leonardi et al.AAAI 2023 · 1 citation
  4. Computing simple mechanisms: Lift-and-round over marginal reduced formsYang Cai, Argyris Oikonomou, Mingfei ZhaoSTOC 2022 · 6 citations
  5. A Unifying Framework for Online Optimization with Long-Term ConstraintsMatteo Castiglioni, Andrea Celli, Alberto Marchesi, Giulia Romano et al.NeurIPS 2022 · 59 citations
Dusk over the sea between two cliffs drawn in fine vertical lines