Source-linked AI summary
Composable and Efficient Mechanisms
Vasilis Syrgkanis, Eva Tardos
TL;DR
The paper addresses how to preserve efficiency when players participate in multiple mechanisms without a feasible global coordinator. It defines smoothness-based conditions and shows that they compose across mechanisms, with extensions to no-overbidding and budget-constrained settings.
Problem
The paper studies how to guarantee efficient outcomes when players participate in multiple mechanisms simultaneously or sequentially, rather than in isolated mechanisms.
Method
The authors define smooth mechanisms and extend complement-free valuation concepts across mechanisms to analyze parallel and sequential composition.
Results
Smooth mechanisms compose in parallel and sequentially, preserving welfare guarantees in equilibrium, Bayesian, and learning settings; weakly smooth mechanisms provide analogous guarantees under no overbidding.
Takeaways & Limitations
Local smoothness conditions can deliver global efficiency guarantees for markets composed of multiple mechanisms, including applications to well-known auctions.
Takeaways & Limitations
The framework assumes no complements across outcomes of different mechanisms, and its main valuation model is quasi-linear.
Abstract
from arXiv · showhide
We initiate the study of efficient mechanism design with guaranteed good properties even when players participate in multiple different mechanisms simultaneously or sequentially. We define the class of smooth mechanisms, related to smooth games defined by Roughgarden, that can be thought of as mechanisms that generate approximately market clearing prices. We show that smooth mechanisms result in high quality outcome in equilibrium both in the full information setting and in the Bayesian setting with uncertainty about participants, as well as in learning outcomes. Our main result is to show that such mechanisms compose well: smoothness locally at each mechanism implies efficiency globally. For mechanisms where good performance requires that bidders do not bid above their value, we identify the notion of a weakly smooth mechanism. Weakly smooth mechanisms, such as the Vickrey auction, are approximately efficient under the no-overbidding assumption. Similar to smooth mechanisms, weakly smooth mechanisms behave well in composition, and have high quality outcome in equilibrium (assuming no overbidding) both in the full information setting and in the Bayesian setting, as well as in learning outcomes. In most of the paper we assume participants have quasi-linear valuations. We also extend some of our results to settings where participants have budget constraints.
1. INTRODUCTION
The paper develops a theory for efficient mechanism design when players participate in multiple mechanisms, showing that smoothness supports global efficiency, robustness to information, and learning behavior. It also extends the framework to weakly smooth mechanisms, complement-free valuations, and budget-constrained participants.
- Motivation: The paper asks which local mechanism properties guarantee global efficiency when mechanisms operate simultaneously or sequentially.This addresses online markets where separate principals run multiple mechanisms and global coordination is infeasible.
- Smooth Mechanisms and Efficiency: The authors define (λ, µ)-smooth mechanisms as approximate market-clearing mechanisms with guarantees robust to incomplete information and learning behavior.A smooth mechanism achieves at least a λ/max(1,µ) fraction of maximum social welfare in correlated equilibria and no-internal-regret outcomes, with a Bayesian extension.
- Composability of Smooth Mechanisms: Smooth mechanisms compose in parallel: fractionally subadditive valuations preserve (λ, µ)-smoothness and yield a λ/max(1,µ) welfare fraction globally.The guarantee applies in full-information correlated equilibria and mixed Bayes-Nash equilibria.
- Composability of Smooth Mechanisms: Sequential composition preserves smoothness with parameter (λ, µ + 1), yielding a λ/(µ + 1) fraction of optimal social welfare when value is the maximum allocation obtained.The result covers sequentially run mechanisms under the specified maximum-valued-allocation valuation.
- Applications: Applications include first-price, all-pay, position, greedy combinatorial, and bandwidth-allocation auctions, with composition applying to sets of these auctions.The first-price auction gives an approximately 1.58 simultaneous-item-auction bound; all-pay and simple first-price position auctions give a bound of 2.
- No-overbidding and Budget Constraints: Weakly smooth mechanisms handle settings such as second-price auctions where good performance assumes bidders do not overbid, while budget-constrained results use effective welfare.Effective welfare caps each player’s welfare contribution by their budget, and simultaneous-mechanism efficiency results extend to this benchmark.
2. COMPOSITION FRAMEWORK
The framework models players participating in multiple mechanisms with quasi-linear utilities and valuations over outcome vectors. It represents simultaneous and sequential mechanisms as global mechanisms, seeking conditions under which local properties guarantee global efficiency.
- Framework: Players may participate in multiple mechanisms, with valuations defined over vectors of mechanism outcomes.The framework assumes quasi-linear utility in the extended outcome space.
- Framework: A mechanism is a triple of action space, allocation function, and payment function.The allocation function maps action profiles to outcomes, while the payment function maps them to player payments.
- Composition: The central objective is to identify local mechanism properties that guarantee efficiency for the composed global mechanism.This applies when mechanisms operate simultaneously or sequentially.
- Composition: Simultaneous composition forms a global mechanism by combining action spaces, outcomes, and payments across component mechanisms.Sequential composition uses history-dependent contingency plans for later actions.
- Efficiency: The framework measures efficiency by social welfare relative to an allocation maximizing total valuation.Players can also choose not to participate, ensuring non-negative utility at rational outcomes.
3. HIERARCHY OF VALUATIONS
The paper develops valuation classes for outcomes spanning multiple mechanisms, focusing on conditions that exclude complementarities across mechanisms. It relates these classes to XOS representations and derives strengthened forms for monotone and lattice-structured valuations.
- Valuation Classes: Composability requires valuations without complements across outcomes from different mechanisms.The framework extends subadditive, fractionally subadditive, and submodular concepts to arbitrary component outcomes.
- XOS Equivalence: Fractionally subadditive valuations across mechanisms are equivalent to XOS valuations, including their β-approximated versions.XOS valuations represent value through additive component valuations.
- Set Valuations: Set-submodular valuations have diminishing marginal benefits as allocations span more mechanisms.Set-monotonicity additionally requires value not to decrease when more mechanisms provide non-empty allocations.
- Hierarchy: Set-monotone, set-submodular valuations are XOS, while set-monotone, set-subadditive valuations are Hm-XOS.The latter representation uses the m-th harmonic number Hm.
- Restricted Classes: Monotone β-fractionally subadditive valuations admit β-XOS representations with component valuations preserving monotonicity.On distributive product lattices, monotone diminishing-returns valuations admit XOS representations using capped marginal valuations.
4. SMOOTH MECHANISMS
Smooth mechanisms provide an approximate market-clearing interpretation and welfare guarantees across equilibrium, learning, and incomplete-information settings. The analysis defines smoothness through deviations and uses random sampling and bluffing to extend guarantees to Bayesian games.
- Interpretation: The smoothness condition is an aggregate, approximate version of bidders obtaining desired bundles at current prices.This motivates interpreting smooth mechanisms as generating approximately market-clearing prices.
- Full Information: A (λ, µ)-smooth mechanism guarantees welfare of at least λ/max(µ,1) of optimum at every correlated equilibrium.The guarantee also covers no-internal-regret learning outcomes in the full-information setting.
- Definition and Scope: The paper’s smoothness definition permits deviations depending on the deviating player’s action, enabling sequential-game composability but limiting the equilibrium theorem to correlated equilibria.The mechanism is analyzed with quasi-linear utilities and an option to withdraw.
- Bayesian Extension: Random sampling handles unknown other-player valuations, while bluffing handles dependence on the deviating player’s equilibrium action.These techniques construct deviations using only a player’s private value and equilibrium strategies.
- Incomplete Information: The same welfare fraction holds at every mixed Bayes-Nash equilibrium under any independent valuation distributions.Players must have the option to withdraw from the mechanism.
5. COMPOSITION THEOREMS
The composition theorems transfer smoothness from individual mechanisms to global mechanisms under valuation and timing conditions. Simultaneous composition preserves (λ, µ)-smoothness, while sequential composition changes it to (λ, µ + 1)-smoothness and remains robust to information released during play.
- Simultaneous Composition: Simultaneously composed mechanisms remain (λ, µ)-smooth when each component is (λ, µ)-smooth and valuations are fractionally subadditive across mechanisms.The valuation can be represented as XOS by component valuations.
- Simultaneous Composition: The simultaneous theorem applies to restricted valuation classes when each component mechanism’s smoothness guarantee holds for the corresponding restricted valuations.Applications include classes containing single-minded valuations and monotone lattice-submodular settings.
- Sequential Composition: Sequentially composing m (λ, µ)-smooth mechanisms yields a global mechanism that is (λ, µ + 1)-smooth for best-of-mechanism valuations.The valuation is the maximum value obtained across mechanisms.
- Sequential Composition: The sequential guarantee is independent of what information players observe during the sequential rounds.Players may condition later actions on observed histories, with the information structure common knowledge.
- Combined Composition: The simultaneous and sequential composition theorems can be combined when each round contains several mechanisms run simultaneously.This extends local smoothness guarantees to mechanisms organized in sequences of rounds.
6. AN APPLICATION: ITEM AUCTIONS
This section analyzes first-price, all-pay, and second-price single-item auctions within the smoothness framework, including their simultaneous and sequential compositions. First-price composition achieves strong welfare guarantees, while second-price auctions require no-overbidding.
- First-Price Auction: First-price auctions are (1 − 1/e, 1)-smooth, yielding welfare at least (1−1/e) of optimal under simultaneous composition with fractionally subadditive valuations.The guarantee applies to correlated equilibria in full information and mixed Bayes-Nash equilibria in incomplete information.
- First-Price Auction: First-price auctions composed sequentially with unit-demand bidders achieve welfare at least 1/e of optimal.The result applies to correlated equilibria and Bayes-Nash equilibria.
- All-Pay Auction: All-pay auctions are (1/2, 1)-smooth, giving efficiency guarantees of 1/2 under simultaneous composition and 1/4 under sequential composition.These guarantees hold in the Bayesian setting and for learning outcomes.
- Second-Price Auction: Second-price auctions can have arbitrarily bad equilibria when bidders overbid and can exhibit unbounded inefficiency under sequential composition with unit-demand bidders.No-overbidding assumptions are therefore used to obtain efficiency guarantees for second-price-type mechanisms.
7. WEAK SMOOTHNESS
The paper extends smoothness to mechanisms whose efficiency guarantees rely on no-overbidding. Weak smoothness incorporates bidders’ maximum willingness to pay and remains composable under simultaneous and sequential composition.
- Definition and Motivation: Weak smoothness adds a willingness-to-pay term to smoothness so mechanisms can be analyzed when bidders do not overbid their values.The framework generalizes no-overbidding assumptions used for second-price auctions.
- Definition and Motivation: A player’s maximum willingness to pay for allocation x_i is the greatest amount she could ever pay conditional on receiving x_i.This quantity is defined for a mechanism, allocation, and strategy.
- Equilibrium Guarantees: Under no-overbidding, weakly (λ, µ1, µ2)-smooth mechanisms achieve efficiency at least λ/(µ2+max{µ1,1}) in correlated and mixed Bayes-Nash equilibria.The guarantee applies respectively in full-information and Bayesian settings.
- Composition: Simultaneous composition preserves weak (λ, µ1, µ2)-smoothness, while sequential composition changes the parameters to (λ, µ1 + 1, µ2).Thus the framework supports both forms of composition, with a sequential adjustment to µ1.
- Definition and Motivation: The framework can use no-overbidding in expectation rather than pointwise because willingness-to-pay is incorporated into the smoothness definition.Earlier approaches related directly to value and therefore required pointwise no-overbidding for second-price auctions.
8. BUDGET CONSTRAINTS
This section extends composable efficiency guarantees to bidders with hard budget constraints. Because budgets limit attainable welfare, the paper uses effective welfare and proves simultaneous-composition results under conservative smoothness.
- Effective Welfare: Effective welfare caps each player’s contribution to welfare by that player’s budget.The benchmark reflects that low-budget players cannot necessarily maximize their full value.
- Conservative Smoothness: Conservative smoothness extends smoothness to budget-constrained settings while restricting the payments induced by smoothness deviations.The paper also extends the section’s results to weak smoothness under no-overbidding.
- Equilibrium Guarantees: A conservatively (λ, µ)-smooth mechanism achieves at least λ/max{1,µ} of expected maximum effective welfare at correlated and Bayes-Nash equilibria.In incomplete information, player types include both valuation and budget.
- Composition: Sequential composition does not carry over because a useful deviation may require waiting until a later mechanism, potentially exhausting the player’s budget.This is the principal composition limitation identified for budget-constrained bidders.
- Composition: Simultaneous composition preserves efficiency guarantees for budget-constrained bidders under conservative smoothness, XOS valuations, and valuation spaces closed under capping.The resulting welfare is at least λ/max{1,µ} of expected maximum effective welfare.
9. APPLICATIONS
The paper applies its framework to several auction families and derives efficiency guarantees that extend across compositions, valuations, budgets, and no-overbidding conditions. The applications include single-item, position, multi-unit, bandwidth, and greedy direct auctions.
- Overview: The applications establish new smoothness proofs or reinterpret prior analyses, with guarantees preserved under the relevant compositions of mechanisms.The stated equilibrium settings include correlated equilibria and mixed Bayes-Nash equilibria.
- Single-Item Auctions: Simultaneous first-price auctions with fractionally subadditive valuations and budgets achieve efficiency at least 1 −1/e of optimal effective welfare.This extends the first-price composition result to budget-constrained bidders.
- Greedy Direct Auctions: A first-price greedy combinatorial auction based on a c-approximation improves the efficiency bound from c + O(log(c)) to c + 0.58.The mechanism is conservatively (1−e−1/c, c)-smooth.
- Position Auctions: Position auctions yield a 1/2 simultaneous-composition guarantee for monotone fractionally subadditive valuations and budgets, and a 1/4 sequential-composition guarantee under maximum-value aggregation.The second-price version yields a 1/4 composition guarantee under no-overbidding.
- Multi-Unit Auctions: For multi-unit auctions, the smooth analysis improves a prior O(log(m)) guarantee to a constant bound for a first-price payment rule.The bounds extend to simultaneous composition with budgets and monotone lattice-submodular valuations.
A.1 Single Item Auctions
This section characterizes smoothness and efficiency guarantees for single-item auctions, including composed settings, budgets, sequential play, and greedy combinatorial mechanisms.
- Single-item auctions: First-price auctions are conservatively (1−1/e, 1)-smooth, yielding an e−1 ≈0.63 welfare fraction under simultaneous budgets.The same framework gives sequential unit-demand guarantees, though the supplied passage truncates their numerical value.
- Single-item auctions: All-pay auctions are (1/2, 1)-smooth, guaranteeing one-half of optimal effective welfare with simultaneous budgets and one-quarter of optimal welfare sequentially.These guarantees apply to correlated equilibria and Bayes-Nash equilibria in the stated settings.
- Single-item auctions: Second-price auctions are weakly (1, 0, 1)-smooth and achieve one-half welfare under simultaneous budgets or sequential unit-demand valuations with no overbidding.The no-overbidding assumption is required for these guarantees.
- Hybrid auctions: For γ-hybrid auctions, the simultaneous-with-budgets guarantee is 1/(1+(1−γ)^2), while the sequential guarantee is 2/(2+(1−γ)^2).The winner pays the bid with probability γ and the second-highest bid otherwise.
- Greedy combinatorial auctions: Greedy c-approximate first-price combinatorial auctions achieve (1−e^(−c))/c of expected optimal welfare, including effective welfare with budgets.The framework also supplies simultaneous and sequential composition results for these auctions.
A.3 Position Auctions
The section extends mechanism analysis to position auctions with monotone position valuations, including pay-per-impression and threshold-price variants under simultaneous and sequential composition.
- Position mechanisms: Position valuations are monotone across ordered slots, and each position mechanism assigns slots and payments from a single bid per player.The framework allows values to combine per-click and per-impression components.
- Pay-per-impression mechanisms: A greedy first-price pay-per-impression mechanism is smooth for position-monotone valuations and supports composition with budget constraints.The result uses closure of monotone valuations under capping.
- Pay-per-impression mechanisms: Simultaneous pay-per-impression mechanisms achieve at least one-half expected optimal effective welfare with budgets, while sequential mechanisms achieve one-quarter expected optimal welfare.The simultaneous result assumes monotone fractionally subadditive valuations; the sequential result assumes unit-demand valuations.
- Threshold-price mechanisms: The threshold-price variant charges each player the bid of the player below them and is analyzed using weak and conservative smoothness.Its guarantees require the no-overbidding assumption.
- Threshold-price mechanisms: With no overbidding, threshold-price mechanisms achieve one-quarter of expected optimal effective welfare simultaneously with budgets and one-quarter of expected optimal welfare sequentially.The sequential setting assumes unit-demand valuations.
A.3.1 Per-Click Valuations
This section studies position auctions with per-click valuations, covering non-separable click-through rates, the standard GFP specialization, and first- and second-price variants.
- Scope: The per-click valuation class is not closed under capping, so the section’s smoothness results do not extend to budget constraints.Some isolated or special complement-free cases remain covered.
- General per-click model: The generalized first-price position mechanism uses one bid per player, allocates slots by weighted bids, and charges the allocated player per-click.For non-separable rates, the weight at position j is a_ij b_i and the payment is a_ij b_i.
- General per-click model: When click-through rates and per-click valuations are monotone by position, the mechanism is smooth; separable rates specialize it to the Generalized First Price auction.Separable rates satisfy a_ij = α_jγ_i.
- Position-independent values: For position-independent per-click values, the first-price mechanism has stronger smoothness even with non-separable click-through rates.This is a stronger special case than the general position-dependent valuation model.
- Second-price variants: The second-price and threshold-price variants are weakly smooth under stated monotonicity and position-independent-value conditions, including non-separable rates for the threshold-price mechanism.The results rely on weak smoothness rather than ordinary smoothness.
A.5 Proportional Bandwidth Allocation Mechanism
The proportional bandwidth mechanism allocates bandwidth proportionally to bids and provides smoothness-based efficiency guarantees for concave valuations, including composed and budget-constrained settings.
- Mechanism: Each bidder submits a bid, pays that bid regardless of received bandwidth, and receives bandwidth proportional to the bid.Bidders have concave value functions with v(0)=0 and quasi-linear utility.
- Smoothness: The proportional bandwidth allocation mechanism is conservatively (2−3/e, 1)-smooth for concave value functions with v(0)=0.This smoothness result underlies the section’s equilibrium and composition guarantees.
- Efficiency guarantees: The resulting efficiency guarantee is approximately one-quarter for correlated equilibria, Bayes-Nash equilibria, and simultaneous or sequential compositions.The simultaneous budget-constrained case also receives this approximate guarantee.
- Simultaneous composition: With simultaneous mechanisms, submodular valuations and budgets yield at least 1/3.73 of expected optimal effective welfare.Capped submodular valuations remain submodular, enabling the budget result.
- Sequential composition: With sequential mechanisms and unit-demand valuations, every correlated equilibrium and Bayes-Nash equilibrium achieves at least 1/3 of expected optimal social welfare.The sequential valuation is the maximum across values on different links.
A.6 Multi-Unit Auctions with Concave Values
The section analyzes greedy multi-unit auctions with concave values, showing smoothness properties that yield efficiency guarantees under simultaneous and sequential composition. It also extends related guarantees to uniform-price auctions, budgets, and no-overbidding settings.
- Greedy Multi-Unit Auctions: The greedy multi-unit auction is (1, 1)-smooth, implying an efficiency guarantee of 1−1/e.This supports welfare guarantees for equilibrium and learning outcomes.
- Composition and Budgets: m simultaneous greedy multi-unit auctions with submodular valuations and budget constraints achieve at least e−1/3.16 of expected optimal effective welfare in every CE and BNE.The valuation condition is submodularity on the product lattice.
- Composition and Budgets: m sequential greedy multi-unit auctions with unit-demand valuations over mechanisms achieve at least e−1/6.32 of expected optimal social welfare in every CE and BNE.Sequential composition requires mechanism-specific concave value functions combined through a maximum across mechanisms.
- Weak Smoothness: Under no-overbidding, the second-price-equivalent auction is weakly smooth and improves on a prior logarithmic O(log(k)) bound for mixed and Bayes-Nash equilibria.The stated efficiency guarantee begins with 1/ but the supplied passage does not preserve its denominator.
- Greedy Multi-Unit Auctions: The greedy allocation rule with additive proxies is equivalent to simultaneous first-price auctions with XOS valuations and is (1−1/e, 1)-smooth.Its efficiency guarantee matches the best approximation algorithm for the corresponding optimization problem.
- Equilibrium and Learning Guarantees: For a (λ, µ)-smooth game, every coarse correlated equilibrium has expected welfare at least λ/(1+µ) of optimum, and no-regret learning approaches approximately optimal welfare.Conditional smoothness preserves guarantees for correlated equilibria and no-internal-regret learning, but can worsen the coarse-correlated-equilibrium bound.
B.2 Extension Theorem to Bayesian Setting
The Bayesian extension shows that conditional smoothness transfers full-information efficiency guarantees to incomplete-information games. The proof uses deviations based on private types and a bluffing technique to handle type-dependent strategy profiles.
- Definition: A Bayesian game is conditionally smooth when each induced complete-information game is conditionally smooth.The definition allows deviations associated with a type profile and an action profile.
- Relation to Earlier Results: Unlike earlier extension results, the theorem applies to conditional smoothness even though the designated deviation may depend on the previous action of the deviating player.Earlier approaches used stronger smoothness conditions that did not allow this dependence.
- Extension Theorem: Theorem B.5 bounds the Bayes-Nash Price of Anarchy of a (λ, µ)-conditionally smooth Bayesian game by λ/(1+µ).The theorem extends conditional-smoothness efficiency guarantees to incomplete information.
- Proof Strategy: The proof uses randomized deviations that sample a type profile and let each player deviate using the sampled equilibrium profile while retaining their true type.This bluffing technique addresses the mismatch between a player’s private type and a deviation depending on the full type profile.
C.1 Section 3: Hierarchy of Valuations
The section develops a hierarchy connecting fractionally subadditive and XOS valuations over mechanism outcomes, including monotone and lattice-structured variants. It then establishes composition results for smooth and weakly smooth mechanisms, including capped valuations for budget constraints.
- Fractionally Subadditive and XOS Valuations: Any fractionally subadditive valuation can be expressed as an XOS valuation using only single-minded induced valuations.This generalizes the equivalence between fractionally subadditive and XOS valuations from set outcomes to mechanism outcomes.
- Fractionally Subadditive and XOS Valuations: The hierarchy proof establishes the bound V(x*) ≤ v(x*) ≤ βV(x*) for the constructed representation.The construction uses fractional covers and LP duality.
- Lattice-Structured Valuations: With a distributive lattice and monotonicity, diminishing marginal returns is equivalent to lattice submodularity.Diminishing marginal returns always implies lattice submodularity; the converse requires the stated lattice and monotonicity conditions.
- Composition of Weakly Smooth Mechanisms: Simultaneous composition preserves weak (λ, µ1, µ2)-smoothness, while sequential composition changes the parameters to weak (λ, µ1+1, µ2)-smoothness.These results apply when each component mechanism is weakly smooth for the relevant restricted valuation class.
- Composition and Budgets: Simultaneous composition of conservatively (λ, µ)-smooth mechanisms remains conservatively (λ, µ)-smooth under XOS valuations.The component valuations must admit the required induced-valuation representation.
- Composition and Budgets: Capping an XOS valuation at a budget preserves XOS structure and yields induced valuations that are capped versions of the original component valuations.This structural property supports composition guarantees under budget constraints.