Sequential Posted Pricing and Multi-parameter Mechanism Design

Shuchi Chawla; Jason Hartline; David Malec; Balasubramanian Sivan

Source-linked AI summary

Sequential Posted Pricing and Multi-parameter Mechanism Design

Shuchi Chawla, Jason Hartline, David Malec, Balasubramanian Sivan

arXiv:0907.2435v2Jul 14, 2009cs.GT

TL;DR

The paper addresses revenue-maximizing mechanism design in multi-dimensional settings, where optimal mechanisms are difficult to generalize and often impractical. It develops sequential posted prices as simple approximations, obtaining constant-factor guarantees across several settings while retaining practical advantages.

Problem
Revenue-maximizing mechanism design remains unresolved in multi-dimensional settings, where agents value multiple services and optimal single-dimensional mechanisms are often impractical.
Method
The paper represents each multi-dimensional agent by independent single-dimensional representatives and uses approximately optimal sequential posted price mechanisms, including mechanisms implemented in undominated strategies.
Results
The mechanisms provide constant-factor revenue approximations for several multi-dimensional problems, including multi-unit auctions and matroid constraints, with an illustrative sequential posted price revenue of $125 versus $133 for the optimal auction.
Takeaways & Limitations
Sequential posted prices offer practical benefits such as truthful responding, collusion resistance, limited information disclosure, and immediate outcomes, while also approximating VCG welfare.
Takeaways & Limitations
The approach assumes unit-demand agents with independently distributed values across services and does not extend beyond matroid and matroid-like feasibility settings.

Abstract

from arXiv · show

We consider the classical mathematical economics problem of {\em Bayesian optimal mechanism design} where a principal aims to optimize expected revenue when allocating resources to self-interested agents with preferences drawn from a known distribution. In single-parameter settings (i.e., where each agent's preference is given by a single private value for being served and zero for not being served) this problem is solved [Myerson '81]. Unfortunately, these single parameter optimal mechanisms are impractical and rarely employed [Ausubel and Milgrom '06], and furthermore the underlying economic theory fails to generalize to the important, relevant, and unsolved multi-dimensional setting (i.e., where each agent's preference is given by multiple values for each of the multiple services available) [Manelli and Vincent '07]. In contrast to the theory of optimal mechanisms we develop a theory of sequential posted price mechanisms, where agents in sequence are offered take-it-or-leave-it prices. These mechanisms are approximately optimal in single-dimensional settings, and avoid many of the properties that make optimal mechanisms impractical. Furthermore, these mechanisms generalize naturally to give the first known approximations to the elusive optimal multi-dimensional mechanism design problem. In particular, we solve multi-dimensional multi-unit auction problems and generalizations to matroid feasibility constraints. The constant approximations we obtain range from 1.5 to 8. For all but one case, our posted price sequences can be computed in polynomial time.

1 Introduction

The paper develops simple sequential posted-price mechanisms as practical approximations to optimal mechanism design, extending single-parameter ideas to multi-dimensional settings. Its results cover several feasibility constraints and preserve useful robustness properties, with constructive computation in most cases.

Motivation: Multi-dimensional mechanism design asks how to solicit preferences, allocate heterogeneous services, and calculate payments when agents have values across multiple outcomes.The hotel-room example illustrates this setting, with distributional knowledge used to optimize objectives such as revenue.
Mechanism: The paper reduces multi-dimensional settings to single-dimensional copies and transfers approximately optimal posted prices back to the original agents.Representatives for one multi-dimensional agent can be grouped and offered simultaneously, with the agent choosing the utility-maximizing offer.
Implications: The approach also applies to social welfare, where sequential posted pricing can approximate VCG welfare while potentially being more practical.The paper identifies social welfare as a setting in which optimal multi-dimensional mechanism design is already solved by VCG.
Mechanism: Sequential posted prices offer agents take-it-or-leave-it prices in sequence, providing simpler interaction and practical advantages over optimal auctions.Agents can respond truthfully as a dominant strategy, need only evaluate offers, and learn immediately whether they are served.
Results: For matroid settings, the revenue gap between an optimal mechanism and a VCG mechanism with suitable reserve prices is bounded by 2 for arbitrary valuation distributions.This answers a previously posed open question in the positive.

2 Problem set-up and preliminaries

The paper formalizes single-parameter and multi-parameter Bayesian mechanism-design environments and defines sequential and order-oblivious posted-price mechanisms. It also recalls Myerson’s virtual-surplus characterization for regular single-parameter distributions.

Single-parameter setting: In the single-parameter setting, independently distributed agent values are combined with a downward-closed feasibility set specifying which agent subsets may be served.The seller chooses an allocation and payment rule subject to this feasibility constraint.
Multi-parameter setting: In the multi-parameter unit-demand setting, each agent has independent values for multiple services but may receive at most one service.Services are grouped by targeted agent, and feasible allocations are specified over agent-service pairs.
Posted-price mechanisms: A sequential posted-price mechanism orders agents and offers each a fixed take-it-or-leave-it price whenever serving that agent remains feasible.Accepted agents are served, and later offers account for the already allocated set.
Posted-price mechanisms: Order-oblivious posted prices use fixed agent prices while allowing the offer order to be arbitrary or adversarial.The mechanism’s revenue is evaluated pessimistically over feasible sets of agents whose values meet their prices.
Myerson benchmark: For regular distributions, Myerson’s mechanism maximizes virtual surplus over feasible agent sets, and truthful revenue equals expected virtual surplus.This characterization supplies the benchmark for the posted-price approximations.

3 A reduction from multi-parameter MD to single-parameter MD

The paper reduces multi-dimensional unit-demand revenue maximization to a single-dimensional problem by replacing each agent with independent copies for its possible services. A good order-oblivious posted-price mechanism for the copies then yields a truthful approximation for the original instance.

Copies reduction: Each multi-dimensional agent is split into independent single-dimensional copies, one for each service the agent may want.The resulting copies instance introduces additional competition among copies of the same original agent.
Copies reduction: The optimal single-dimensional mechanism for the copies instance upper-bounds the revenue of any individually rational truthful deterministic mechanism in the original multi-dimensional instance.Lemma 3 formalizes this revenue comparison.
Approximation transfer: A truthful posted-price mechanism for the original instance inherits any α-approximation achieved by an order-oblivious posted-price mechanism for the copies instance.Theorem 4 transfers the approximation factor without changing α.

4 Sequential posted-price mechanisms

The paper constructs sequential posted-price mechanisms for single-dimensional feasibility systems and analyzes their revenue relative to Myerson’s mechanism. The approximation factors are constant for matroids and several related constraints, but can deteriorate substantially for general non-matroid systems.

Construction: The construction sets agent prices from Myerson allocation probabilities and orders agents by decreasing prices, with modifications for point masses and non-regular distributions.The analysis compares posted-price revenue with the virtual-surplus-based upper bound.
Matroids: 2-approximation holds for matroid feasibility constraints.The analysis accounts for revenue lost when previously served agents block later offers.
Uniform and partition matroids: e/(e −1) ≈1.58 approximation holds for uniform and partition matroids, including multi-unit auctions.The analysis is stated to be tight for the uniform-matroid case.
Matroid intersections: An (m + 1)-approximation holds for feasibility constraints formed by intersections of m matroids.Matching is given as an example of an intersection of two matroids.
Combinatorial auctions: An (m + 1)-approximation holds for single-parameter combinatorial auctions with known bundles of size at most m.The result applies when agents seek commonly known bundles and have a common value for their desired bundles.
General non-matroid systems: For general non-matroid systems, the ratio between Myerson revenue and optimal sequential posted-price revenue can be Ω(log n/ log log n).The same family can produce an Ω(h) social-welfare gap when values lie in [1, h], while a uniform price of 1 gives an O(h) upper bound.

5 Order-oblivious posted-prices

Order-oblivious posted pricings use prices fixed in advance and can approximate optimal revenue under several matroid constraints, though general-matroid prices lack a known efficient computation and non-matroid gaps can be large.

5 Order-oblivious posted-prices: Order-oblivious posted pricings fix agent prices in advance and offer them first-come, first-served under a feasibility constraint.Prices may match an approximately optimal sequential posted pricing or be set to infinity to exclude agents.
5.1 An O(log k) approximation for general matroids: O(log k) approximations are obtained for general matroids, where k is the matroid rank.The construction guarantees a revenue fraction of order 1/log k regardless of agent ordering.
5.1 An O(log k) approximation for general matroids: The general-matroid O(log k)-approximate order-oblivious pricing has no known efficient computation, unlike the 2-approximate sequential posted pricing.The computational limitation concerns finding the order-oblivious prices, not the approximation guarantee itself.
5.3 OPMs for matroid intersections: 6.75-approximations hold for intersections of two partition matroids, while intersections of m arbitrary matroids yield O(m log k) approximations.For non-matroid feasibility, the gap between optimal order-oblivious pricing and optimal sequential posted pricing can be Ω(log n/log log n).

6 Approximations for the multi-parameter setting

The paper extends posted-price approximations to multi-parameter settings, including unit-demand multi-unit auctions, graphical constraints, and broader feasibility systems under undominated-strategy implementation.

6 Approximations for the multi-parameter setting: A 6.75-approximate order-oblivious pricing is available for unit-demand agents buying among multiple item types with independent values.The prices for this mechanism can be computed in polynomial time.
6 Approximations for the multi-parameter setting: A 10.67-approximate order-oblivious pricing is available when agents seek one edge each and the seller must allocate a forest.The prices can be computed in polynomial time.
6.2 Approximation through implementation in undominated strategies: In the relaxed implementation model, an agent who desires only one service at the posted prices must accept it when offered.This behavioral property supports the approximation analysis for the multi-parameter mechanism.
6.2 Approximation through implementation in undominated strategies: For general matroid intersections and size-2 bundle auctions, sequential posted pricing implements an 8-approximation in undominated strategies.The mechanism relaxes truthfulness because an agent may reject a profitable current service when anticipating a better future offer.

7 Discussion

The approach gives constant-factor revenue approximations for several multi-dimensional settings but relies on matroid-like structure, unit demand, and independent service values.

7 Discussion: The posted-price approach does not extend beyond matroid and matroid-like settings, leaving broader feasibility constraints open.The authors suggest that other simple near-optimal mechanisms might eventually support broader extensions.
7 Discussion: The analysis assumes agents are unit-demand and have independently distributed values across services.Without either assumption, the copies-based upper bound on optimal revenue no longer remains valid.

A Myerson’s mechanism and revenue bounds for truthful mechanisms

Myerson’s mechanism maximizes expected virtual surplus in regular single-parameter settings, while ironed virtual surplus extends the revenue characterization to irregular distributions. These characterizations support upper bounds used to analyze posted-price mechanisms and translate guarantees to multi-dimensional settings.

Revenue characterization: Any truthful single-parameter mechanism’s expected revenue equals its expected virtual surplus.
Myerson’s mechanism: Myerson’s mechanism allocates to a feasible agent set maximizing virtual surplus, and is truthful when each virtual valuation is monotone.Regularity means each distribution’s virtual valuation is monotone non-decreasing.
Irregular distributions: For irregular distributions, ironing makes virtual valuations monotone; truthful mechanisms’ revenue is then bounded by expected ironed virtual surplus.Equality holds when allocation probabilities are constant over ranges with equal ironed virtual value.
Revenue optimality: Myerson’s mechanism earns at least as much revenue as every truthful mechanism.
Revenue bounds: Revenue bounds reduce each agent’s contribution to a single-agent mechanism with a matching service probability, enabling comparisons with posted-price mechanisms.The supplied proof develops this bound for regular and non-regular value distributions.
Multi-dimensional translation: A truthful multi-dimensional mechanism can be converted into a single-dimensional representative mechanism whose monotone allocation rule admits truthful payments.The construction preserves the allocation pattern and uses weak monotonicity to establish monotonicity.

C.2 Proof of Theorem 6: an e e−1 approximation for uniform and partition matroids

The proof establishes an e/(e−1) approximation for uniform and partition matroid feasibility constraints by comparing multi-unit posted pricing with a one-item construction. The analysis is tight for the stated setting.

Uniform matroids: e/(e−1) is the approximation factor achieved by the sequential posted-price mechanism for uniform matroids.A k-uniform matroid models a multi-unit auction with k identical units.
Reduction: The proof reduces the k-item case to a one-item case by scaling service probabilities qi to qi′ = qi/k.
Reduction: The one-item construction supplies revenue at least (1 − 1/e) times the corresponding posted-price benchmark, yielding the e/(e−1) guarantee.
Partition matroids: The same e/(e−1) approximation extends to partition matroids, which are disjoint unions of uniform matroids.
Tightness: The analysis is tight: with one item and independently distributed values equal to 1 with probability 1 − ε, Myerson’s revenue is 1 − o(1).

C.5 Bad gap example for general non-matroids

For general non-matroid feasibility constraints, sequential posted pricing can have logarithmically larger gaps than optimal mechanisms, while matroid-based approximation techniques do not extend generally.

Ω(log n / log log n) separates Myerson’s revenue from the optimal SPM for a symmetric non-matroid constraint.
In the constructed instance, Myerson’s mechanism obtains revenue Ω(m^2), whereas any SPM obtains at most 3m.
The resulting revenue gap is Ω(m) = Ω(log n / log log n).
With values in [1, h], the example yields an Ω(h) gap, while an O(h) upper bound is always achievable by uniform price 1.
For general matroids, the paper designs an O(log k)-approximate OPM, but uniform pricing cannot achieve an o(log h) approximation even when k = 1.
The broader development uses threshold rules, virtual values, and partitioning techniques to obtain constant-factor mechanisms under structured constraints.

D.5 Order-oblivious pricings in the non-matroid setting

In non-matroid settings, the ordering of agents can substantially affect posted-price revenue, motivating order-oblivious pricing mechanisms and revealing a logarithmic ordering gap.

Ω(log n / log log n) separates the best and worst agent orderings for optimal SPMs under a non-matroid constraint.
In the tree construction, root-to-leaf ordering offers at least m agents at each level and achieves high expected revenue.
Leaf-to-root ordering commits the mechanism to a specific path after the first served agent, limiting expected revenue to O(m).
The difference between the orderings is Ω(m), which becomes Ω(log n / log log n) because n = O(m^m).
The paper extends the analysis to randomized pricing and establishes revenue comparisons using acceptance probabilities and price randomization.

F Computing the near-optimal posted-price mechanisms

The near-optimal posted-price mechanisms can be computed from distributional and optimization oracles, with sampled probabilities yielding asymptotically accurate revenue estimates.

The computation assumes oracles for optimal prices, distribution functions and densities, ironed virtual values, and welfare maximization.
The algorithm samples value profiles, estimates Myerson allocation probabilities, clips small estimates, optimizes prices, and orders agents by decreasing prices.
The output prices are ordered by decreasing price and are compared with a mechanism using Myerson prices under the same ordering.
With probability at least 1 − 2/n, the estimated probabilities satisfy the stated multiplicative and additive accuracy bounds.
Conditioned on the estimation event, the computed mechanism achieves a (1 − o(1)) approximation to the comparison mechanism’s expected revenue.

G Approximations for the BMUMD

For Bayesian multi-dimensional multi-unit settings, the paper extends posted-price approximations to intersections involving graphical and unit-demand matroids, including implementations in undominated strategies.

The paper proves that a good OPM exists for BMUMD instances constrained by a graphical matroid and unit-demand constraints.
Viewing the graphical constraint as a union of 1-uniform matroids enables treatment as an intersection of two partition matroids.
10.67 is the stated approximation factor from scaling demand probabilities across the graphical and unit-demand constraints.
For the two multi-dimensional settings, the paper designs SPMs whose guarantees hold when agents use undominated strategies.
An agent who uniquely desires one service is guaranteed to accept it when offered under an undominated strategy.
The revenue analysis partitions services into sold, blocked, and unblocked sets and obtains an 8-approximation in the relevant setting.
The combinatorial-auction argument is stated to be identical and omitted.

H Approximating social welfare and other objectives via posted-price mechanisms

The paper extends sequential posted pricing beyond revenue maximization to objectives linear in social value and revenue, using virtual surplus under regularity. It obtains a 2-approximation in matroid settings and shows that suitably reserved VCG mechanisms achieve at least half of Myerson revenue.

The framework applies sequential posted pricing to any objective linear in social value and revenue.
Virtual surplus equals expected objective value for truthful mechanisms, enabling allocation-based optimization under regularity.The allocation rule maximizing virtual surplus is optimal among truthful mechanisms when the distributions satisfy the required regularity condition.
2-approximation: the mechanism SG achieves this guarantee for the objective G in matroid settings when all input distributions are regular with respect to G.SG prices agents using the mechanism MG's service probabilities and orders them by decreasing γi.
Irregular distributions can be handled by ironing virtual values, analogously to Myerson's approach.The paper leaves the details of this ironing procedure open.
Revenue maximization through VCG mechanisms: 1/2 of Myerson revenue: in matroid settings, some reserve prices make a VCG mechanism obtain at least half of Myerson's expected revenue.The argument uses that VCG revenue is at least SPM revenue with the same reserve prices, while high reserves preserve revenue performance.