Source-linked AI summary
The power of randomness in Bayesian optimal mechanism design
Shuchi Chawla, David Malec, Balasubramanian Sivan
TL;DR
The paper studies whether randomization substantially improves revenue in Bayesian multi-parameter mechanism design for unit-demand agents. It relates multi-parameter mechanisms to single-parameter mechanisms through pseudo-agent reductions and establishes constant-factor bounds: 4 for independent values and 8 for additive values, with extensions to multiple agents. The general matroid setting has a weaker guarantee involving deterministic mechanisms implemented in undominated strategies.
Problem
The paper asks how much randomized mechanisms can outperform deterministic mechanisms when unit-demand agents have multi-dimensional values, since arbitrary correlations can yield an unbounded gap.
Method
The paper splits each unit-demand agent into independent single-service pseudo-agents, relates lottery pricings to single-parameter mechanisms, and constructs deterministic pricings from these comparisons.
Results
The gap between randomized and deterministic mechanisms is at most 4 for independent values and at most 8 for additive values, with constant-factor extensions to multiple-agent settings.
Takeaways & Limitations
Randomization provides only a small constant-factor revenue benefit for unit-demand agents under independent or additive value distributions.
Takeaways & Limitations
For general matroid feasibility, the bound compares optimal randomized truthful mechanisms with deterministic mechanisms implemented in undominated strategies, rather than with truthful deterministic mechanisms.
Abstract
from arXiv · showhide
We investigate the power of randomness in the context of a fundamental Bayesian optimal mechanism design problem--a single seller aims to maximize expected revenue by allocating multiple kinds of resources to "unit-demand" agents with preferences drawn from a known distribution. When the agents' preferences are single-dimensional Myerson's seminal work [Myerson '81] shows that randomness offers no benefit--the optimal mechanism is always deterministic. In the multi-dimensional case, where each agent's preferences are given by different values for each of the available services, Briest et al. [Briest, Chawla, Kleinberg, and Weinberg '10] recently showed that the gap between the expected revenue obtained by an optimal randomized mechanism and an optimal deterministic mechanism can be unbounded even when a single agent is offered only 4 services. However, this large gap is attained through unnatural instances where values of the agent for different services are correlated in a specific way. We show that when the agent's values involve no correlation or a specific kind of positive correlation, the benefit of randomness is only a small constant factor (4 and 8 respectively). Our model of positively correlated values (that we call additive values) is a natural model for unit-demand agents and items that are substitutes. Our results extend to multiple agent settings as well.
1 Introduction
The paper asks how much randomization helps in Bayesian multi-parameter mechanism design for unit-demand agents. It shows that, despite unbounded gaps under arbitrary correlations, the gap is bounded by constant factors for independent and additive values, and extends these results to multiple agents.
- Motivation: The problem concerns a seller allocating multiple services to unit-demand agents whose values for services form multi-dimensional types.The paper contrasts this setting with Myerson’s single-dimensional setting, where an optimal mechanism is deterministic.
- Mechanism models: Randomized mechanisms can offer lotteries over items, while deterministic mechanisms offer item-specific prices.For a single unit-demand agent, a lottery pricing is a menu of prices for distributions or convex combinations over items.
- Mechanism models: An example with independently uniform values in [5, 6] prices each item at p*= $5.097 and a (1/2, 1/2) lottery at p′ = $5.057.The lottery is allocated by tossing a coin between the two items.
- Prior results: Arbitrary correlations can make the lottery-pricing gap unbounded with only 4 items, whereas prior gaps were 3/2 overall and 1.1 under independent values.The paper motivates studying natural restrictions on value correlations.
- Results: For independent values, the gap between optimal lottery and item pricings is at most 4.The proof combines an upper bound using two related mechanisms with prior deterministic-approximation results.
- Results: For additive values, where v_i = t_0 + t_i, the gap is at most 8; the results also extend to multiple agents and feasibility constraints.The paper describes additive values as a natural limited-correlation model and reports constant-factor gaps in multi-agent settings.
2 Definitions and problem set-up
The paper formalizes Bayesian multi-parameter unit-demand mechanism design as revenue maximization under allocation feasibility constraints. Its reduction splits each unit-demand agent into independent single-service pseudo-agents, enabling comparisons with single-parameter mechanisms and deterministic approximations.
- Problem setup: There are n risk-neutral buyers, m services, random values v_ij, and a feasibility set system J over agent-service pairs.Each feasible subset in J is an allocation of services to agents, and each agent wants at most one service.
- Problem setup: The seller maximizes expected revenue over buyers’ valuations in the Bayesian multi-parameter unit-demand problem.Deterministic mechanisms map bids to feasible allocations and prices, while randomized mechanisms map bids to distributions over feasible allocations.
- Problem settings: The paper considers single-agent independent values, single-agent additive values, independent multi-agent matching, and matroid-feasibility settings.In the additive setting, v_j = t_0 + t_j with independently distributed components t_j.
- Reduction: The reduction creates I_copies by replacing each of n unit-demand agents with m independent pseudo-agents, one for each service.Pseudo-agent (i,j) values service j according to F_ij, under the same feasibility constraint.
- Reduction: The copies instance introduces additional competition, so its revenue can exceed the original instance’s revenue.The paper uses this comparison to transfer single-parameter mechanism guarantees to the multi-parameter problem.
- Known guarantees: For single-agent independent values, a truthful deterministic mechanism earns at least 1/2 of any truthful mechanism for I_copies; for multiple-agent matching, the factor is 4/27.For general matroid feasibility, a deterministic mechanism implemented in undominated strategies earns at least 1/8 of any truthful mechanism for I_copies.
3 Lotteries and randomized mechanisms
The paper represents randomized mechanisms as lottery pricings and extends this representation to multiple agents through agent-specific menus that depend on other agents’ values. It then constructs an equivalent copies-instance mechanism while preserving truthfulness, feasibility, and nonnegative revenue.
- Lottery mechanisms: A lottery is a price paired with probabilities over services, and a lottery pricing offers a unit-demand buyer arbitrarily many such options.The buyer selects the lottery maximizing expected utility, or chooses none.
- Lottery mechanisms: A lottery-based multi-agent mechanism offers each agent a lottery pricing determined by the other agents’ reported values.The selected lottery determines service-allocation probabilities subject to the mechanism’s feasibility constraint.
- Lottery mechanisms: Every truthful randomized BMUMD mechanism is equivalent to a truthful lottery-based mechanism.For fixed other-agent values, each attainable allocation-probability vector and price becomes a menu lottery; incentive compatibility preserves equivalence.
- Copies construction: The copies construction transforms each multi-service lottery into one-dimensional lottery menus for pseudo-agents, with price shifts chosen to ensure nonnegative prices at zero value.The resulting menus depend on values excluding the relevant pseudo-agent and remain truthful.
- Copies construction: The construction preserves allocation and supports feasibility, while nonnegative revenue enables upper bounds based on revenue from subsets of pseudo-agents.At most one pseudo-agent associated with each original agent is selected by a unit-demand allocation function.
4 Single-agent setting
For a single unit-demand agent, the paper bounds the advantage of lotteries over deterministic pricings under independent values and additive positive correlation. The resulting gaps are at most 4 and 8, respectively, rather than unbounded.
- Independent values: 4 is the maximum lottery-to-pricing revenue ratio when item values are independently distributed.Equivalently, the optimal deterministic mechanism earns at least one-fourth of the optimal randomized mechanism’s revenue.
- Independent values: The independent-values proof compares the lottery mechanism with a copies-instance auction, using the highest-valued item and a Vickrey-auction revenue term.The construction exploits that pseudo-agents effectively compete for the privilege of being served.
- Additive values: Additive values give each item value vi = ti + t0, combining an independently distributed service-specific value with an independently distributed base value.This models positive correlation arising from a common value for being served plus an item-specific component.
- Additive values: 8 is an upper bound on the revenue of any lottery system relative to some deterministic pricing under additive values.The proof first obtains factor 9, then improves it to 8 by separately analyzing the base-value pseudo-agent and the service-specific pseudo-agents.
- Additive values: The additive-values reduction preserves lottery revenue while replacing each lottery’s service probabilities with a feasible allocation involving the base item and at most one additional item.The transformed instance is uncorrelated but is not unit-demand, because the base item and one service item may both be sold.
- Additive values: The factor-8 improvement follows by combining cases according to whether the base-value pseudo-agent or a service-specific pseudo-agent has the highest value.The paper concludes that the claimed bound is 8.
5 Multi-agent setting
The multi-agent analysis bounds the revenue advantage of randomized mechanisms by reducing lottery-based mechanisms to deterministic mechanisms for a corresponding single-parameter instance with copies. For matching feasibility, the randomized-to-deterministic revenue gap is at most 33.75, while the general matroid-intersection setting yields a factor-40 bound for deterministic mechanisms implemented in undominated strategies.
- The multi-agent problem allows multiple item copies, independently distributed values, unit-demand buyers, and supply constraints for each item.
- Randomized mechanisms can be interpreted as lottery-based mechanisms, enabling comparison with deterministic single-parameter mechanisms for the copies instance.
- Matching feasibility: A lottery-based mechanism earns at most five times the expected revenue of Myerson’s mechanism for the corresponding copies instance.
- Proof strategy: The analysis uses three truthful deterministic mechanisms, with two mechanisms jointly covering the residual value after the first matching.
- General matroid intersection: 40 is the corresponding upper bound in the general matroid-intersection setting, relative to the optimal deterministic mechanism implemented in undominated strategies.
6 Discussion and open problems
The paper concludes that randomness provides only a small constant-factor benefit when unit-demand agents’ item values have little or no correlation, while identifying extensions to positively correlated values and beyond unit demand as open problems.
- Randomness offers only a small constant-factor benefit when unit-demand agents’ values for different items have little or no correlation.
- The authors identify arbitrary positive correlation, including Armstrong’s multiplicative-values model, as a direction for extending the result.
- Extending the techniques beyond unit-demand settings is another open problem.
Gap between lottery pricings and Myerson’s mechanism
For two independently and identically distributed equal-revenue valuations, a lottery pricing earns 2.275 + o(1), exceeding the copies-instance optimum and any item pricing by a factor of 1.13.
- The example uses one agent with independently and identically distributed equal-revenue valuations for two items, bounded at n.
- The optimal revenue for the copies instance, and the revenue of any item pricing, is bounded above by 2.
- The lottery assigns probabilities to the two items and charges a price as its third coordinate.
- 2.275 + o(1) is the revenue of the lottery pricing, obtained from the stated probability masses of its allocation regions.
- 1.13 is the factor by which the lottery pricing exceeds the optimal revenue for the copies instance or any item pricing.