Approximate Optimal Mechanism Design via the Interim Relaxation
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.
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.
