Mechanism Design via the Interim Relaxation¶

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

This paper introduces a general framework for designing revenue-maximizing multi-agent mechanisms via an interim relaxation — a weaker feasibility requirement than ex-post — rounded to an implementable mechanism using a new primitive called a two-level online contention resolution scheme (tOCRS). The framework unifies and substantially improves approximation guarantees for a wide class of multi-item auction problems with downward-closed feasibility constraints.

Problem¶

Alaei's influential ex-ante relaxation framework for multi-agent mechanism design has two key limitations: it cannot handle correlated item valuations within an agent, and its rounding procedure (an OCRS in disguise) cannot accommodate the structured intra-agent dependencies that arise in the interim setting. Prior sequential mechanisms for matroid-constrained multi-item auctions had a best-known approximation of 70×, which left a large gap to optimality.

Method¶

The framework proceeds in three steps:

Interim LP relaxation: Solve an LP over interim allocation/payment rules \((π, q)\) that are feasible in expectation (per-agent allocations lie in their feasibility polytope \(P_{F_i}\), and the marginal allocation vector lies in the global polytope \(P_F\)). This LP has polynomial size for many constraint families, unlike the exponential-constraint LPs of Cai et al.
Two-level OCRS (tOCRS): Define a new rounding primitive over an \(n \times m\) element matrix where elements in the same row are conditionally independent given a row-level random draw \(d_i \sim D_i\) (the agent's type). A \((b,c)\)-selectable tOCRS guarantees each active element is selected with probability \(\geq c\). For Vertical-Horizontal (VH) constraints (feasibility decomposes per-agent and per-item), a black-box reduction (Theorem 2) constructs a \((b, c \cdot c')\)-selectable tOCRS from existing per-row and per-column OCRSs. For knapsack and multi-choice knapsack, tOCRSs are constructed from scratch (Theorems 3–4).
Mechanism construction (Algorithm 1): Approach agents sequentially; agent \(i\) reports \(r_i^*\), pays \(b(c-\epsilon) \cdot q_i(r_i^*)\), and items are allocated by running the tOCRS on active elements drawn at rate \(b \cdot \pi_{i,j}(r_i^*)\), with a Bernoulli-factory division coin to enforce exact BIC/BIR probabilities. The resulting mechanism is BIC-IR and \(\frac{\alpha}{b(c-\epsilon)}\)-approximately optimal (Theorem 1).

Key Contributions¶

Introduction of the two-level CRS/OCRS (tCRS/tOCRS) primitive capturing intra-agent correlations, with a formal definition distinguishing it from standard OCRS.
A black-box reduction (Theorem 2) for constructing tOCRSs for VH constraints from existing per-row/column OCRSs.
A \((b, \frac{1}{2+8b})\)-selectable tOCRS for Knapsack (Theorem 3), implying a \((1, 0.1)\)-selectable OCRS for knapsack — better than Feldman et al.'s 0.085.
A \((b, \frac{1}{2+7b})\)-selectable tOCRS for Multi-Choice Knapsack (Theorem 4).
A \(\frac{2e}{e-1} \approx 3.16\)-approximation sequential BIC-IR mechanism for matroid VH constraints (Application 1), improving the prior best of 70× for even the special case.
A 10-approximation sequential BIC-IR mechanism for knapsack-constrained multi-item auctions and a 9-approximation under multi-choice knapsack (Application 2).
Extension to multi-parameter procurement auctions via an OCRS for Stochastic Knapsack.

Results¶

Matroid VH constraints: \(\frac{2e}{e-1} \approx 3.16\) approximation (sequential, BIC-IR). Prior best: 70× approximation [Cai–Zhao 2017] for a strict special case (single-copy items, independent values).
Knapsack auctions: 10-approximation (sequential, BIC-IR, efficiently computable).
Multi-choice knapsack (each agent gets ≤1 item): 9-approximation (sequential, BIC-IR, efficiently computable).
Arbitrary valuations + knapsack: 9-approximation (sequential, BIC-IR, computationally inefficient in general).
Knapsack OCRS selectability: 0.1 (this work) vs. 0.085 [Feldman et al.] vs. ≈0.319 [Jiang et al., state-of-the-art].
Procurement auctions: \((3 + e^{-2})\)-approximation sequential mechanism by combining with Jiang et al.'s Stochastic Knapsack OCRS.

Limitations¶

The interim LP (LP1) may require exponentially many constraints to represent \(P_F\) and \(P_{F_i}\) for complex feasibility sets (e.g., general matroids), making end-to-end efficiency dependent on LP tractability.
The knapsack tOCRS selectability (0.1) is substantially weaker than the state-of-the-art OCRS for knapsack (≈0.319 [Jiang et al.]), so the resulting revenue approximation factors are not tight.
The \(\frac{2e}{e-1} \approx 3.16\) matroid result does not achieve the simplicity properties (e.g., posted-price mechanisms) of [Cai–Zhao 2017], and those simplicity guarantees are information-theoretically impossible for correlated items.
The Bernoulli-factory implementation introduces a \(\epsilon\)-slack in BIC compliance and requires \(O(\text{poly}(1/\epsilon^2))\) oracle queries.

Relevance to Agentic AI / LLM Agents¶

This paper is a theoretical algorithmic game theory / mechanism design contribution and has no direct relevance to Agentic AI or LLM agents. It addresses revenue-optimal auction design for strategic agents with additive preferences — a combinatorial optimization and microeconomics problem — with no connection to language models, autonomous AI systems, tool use, planning, or multi-agent LLM coordination. The "agents" here are economic bidders in an auction, not AI agents. Someone tracking Agentic AI / LLM Agents would not find actionable content in this work.