7 min read
On this page

Online Mechanism Design

Overview

Online mechanism design combines mechanism design with online algorithms: agents arrive over time, decisions must be made irrevocably without knowledge of future arrivals, and the mechanism must maintain incentive compatibility throughout. This setting models real-world markets, auctions, and resource allocation problems where participants interact sequentially.

Online Auctions

Sequential Posted Prices

The mechanism offers a take-it-or-leave-it price to each arriving agent:

  • Agent arrives, observes price, accepts or rejects
  • If accepted: agent receives the item and pays the posted price
  • If rejected: agent leaves permanently

Strategyproofness: Trivially DSIC since agents have a binary choice with no strategic dimension (accept iff value >= price).

Optimal pricing: With known value distribution F, set price p* = argmax_p p(1-F(p)). This is Myerson's monopoly price. Expected revenue = p*(1-F(p*)).

Online Auction Design Challenges

  • Irrevocability: Allocations cannot be undone once made
  • Uncertainty: Future demand is unknown (or partially known via distributional assumptions)
  • Inventory constraints: Limited supply; allocating to early agents may prevent serving more valuable later agents
  • Incentive compatibility: Must hold for each agent at the time of their decision, given partial information about the mechanism's state

Digital Goods Auctions

Unlimited supply (zero marginal cost); selling to n bidders with values drawn i.i.d. from unknown F.

Fixed-price benchmark: Optimal fixed price p* (with hindsight) yields revenue R* = p* * |{i: v_i >= p*}|.

Competitive ratio: No deterministic truthful mechanism achieves constant-factor approximation to R* without distributional knowledge. Randomized mechanisms (random sampling) achieve O(1)-competitive ratios.

Random Sampling Optimal Price: Split bidders randomly into two halves. Use each half to set the price for the other. Achieves constant-competitive ratio against the fixed-price benchmark.

Prophet Inequalities

Classical Prophet Inequality

A gambler observes a sequence of n independent (not necessarily identical) random variables X_1, ..., X_n drawn from known distributions F_1, ..., F_n. After observing each X_i, the gambler irrevocably accepts or rejects. Goal: maximize expected value of the accepted variable.

Theorem (Krengel-Sucheston, 1977-78): There exists a threshold strategy achieving E[reward] >= (1/2) * E[max_i X_i]. The factor 1/2 is tight.

Threshold strategy: Set threshold t such that P(max_i X_i >= t) = 1/2. Accept the first X_i >= t. This guarantees E[reward] >= t/2 + ... >= E[max_i X_i]/2.

Single threshold suffices: The gambler does not need to adapt the threshold over time; a fixed threshold based on the joint distribution achieves the 1/2 guarantee.

Connection to Mechanism Design

The prophet inequality directly yields a mechanism for single-item allocation with n agents:

  • Posted price mechanism: Offer each agent a take-it-or-leave-it price (the prophet threshold)
  • Achieves 1/2 of optimal welfare in expectation
  • DSIC: Trivially strategyproof (each agent faces a binary accept/reject decision)
  • Improved bounds: For i.i.d. agents, the factor improves to 1 - 1/e ~ 0.632 (Samuel-Cahn); for the order-selection prophet inequality (adversarial order vs. adversarial distributions), 1/2 remains tight

Prophet Inequality Variants

| Variant | Competitive Ratio | |---|---| | Classical (adversarial order) | 1/2 | | I.I.D. distributions | 1 - 1/e | | Random order | 1 - 1/e (approximately) | | k items (choose k) | 1 - O(1/sqrt(k)) | | Matroids (feasibility constraint) | 1/2 | | Combinatorial (submodular) | O(1) in many cases |

Matroid prophet inequality (Kleinberg-Weinberg, 2012): When the feasibility constraint is a matroid, a 1/2-competitive DSIC mechanism exists using per-element thresholds. This generalizes the single-item result.

Secretary Problem

Classical Secretary Problem

n candidates arrive in uniformly random order. After observing each candidate's rank (relative to those seen so far), irrevocably accept or reject. Goal: maximize probability of selecting the best overall candidate.

Optimal strategy (1/e-law): Reject the first n/e candidates (observation phase); then accept the first candidate better than all previously seen. Probability of selecting the best = 1/e ~ 0.368 as n -> infinity.

Value-maximization variant: Maximize E[value of selected candidate] / E[max value]. Dynkin's algorithm achieves a constant competitive ratio.

Matroid Secretary Problem

Select a set of candidates forming an independent set in a matroid (generalization of cardinality, partition, graphic matroids). Candidates arrive in random order.

Conjecture: An O(1)-competitive algorithm exists for all matroids.

Known results:

  • Uniform matroid (cardinality k): 1 - 1/sqrt(k) competitive
  • Graphic matroids: O(1)-competitive
  • Transversal matroids: O(1)-competitive
  • General matroids: O(log log rank)-competitive (Lachish, Feldman-Svensson-Zenklusen)

Secretary with Multiple Choices

k-secretary: Select k candidates to maximize total value. Random order. O(1)-competitive for constant k; 1-O(1/sqrt(k)) for growing k.

Knapsack secretary: Candidates have sizes and values; knapsack constraint. O(1)-competitive in random order.

Dynamic Mechanism Design

Multi-Period Mechanisms

Agents interact with the mechanism over multiple time periods, with evolving types:

  • Agent's type at time t: theta_i^t (may depend on previous types and actions)
  • Mechanism: Observes reports, makes allocation and payment decisions at each period
  • IC constraint: Truthful reporting in each period must be a BNE (or DSIC) given future optimal behavior

Dynamic VCG (Bergemann-Valimaki)

Extends VCG to dynamic settings. The payment at each period accounts for the externality the agent imposes on others over the entire future horizon. Requires a specific "team" formulation where each agent's payoff equals the total social welfare minus a term independent of their reports.

Challenge: Computing payments requires knowledge of future value distributions and agent strategies, which may be computationally intractable.

Bank Account Mechanisms

Agent arrives, interacts over T periods. Mechanism maintains a "bank account" per agent:

  • Deposits from agent payments
  • Withdrawals for allocation costs
  • IC maintained by threatening to close the account (future exclusion)

Dynamic pivot mechanism: Each period, run VCG given current reports, adjusted by predicted future contributions. Achieves periodic ex-post IC.

Revenue Management Applications

  • Airline pricing: Dynamic seat allocation with stochastic demand; posted prices adjust over time
  • Cloud computing: Spot instances (auction-based) vs. on-demand pricing
  • Ride-sharing: Dynamic pricing (surge pricing) as a mechanism design problem

Learning in Auctions

Learning from Bidding Data

Reserve price optimization: Given historical bid data, learn the revenue-maximizing reserve price. Sample complexity: O(1/epsilon^2) samples to learn an epsilon-optimal reserve (from a single distribution).

Multi-item pricing: Learn item prices or bundle prices from buyer behavior. Harder due to combinatorial structure.

Regret Minimization in Repeated Auctions

Buyer's perspective: Agent facing repeated auctions with unknown competing bids. Use no-regret algorithms (e.g., multiplicative weights, EXP3) to learn optimal bidding strategy. Regret O(sqrt(T)) over T rounds.

Seller's perspective: Set prices/reserves to maximize cumulative revenue. Multi-armed bandit formulation: each price level is an arm; observe revenue (but not agent values). UCB and Thompson sampling approaches.

Learning-Augmented Mechanism Design

Use ML predictions to improve mechanism performance:

  • Predicted values: If the mechanism has noisy predictions of agent values, can it improve revenue beyond worst-case guarantees?
  • Consistency-robustness trade-off: Good performance when predictions are accurate (consistency) while maintaining worst-case guarantees (robustness)
  • Sample complexity of mechanism design: How many samples from the value distribution are needed to design a near-optimal mechanism? Theta(1/epsilon^2) for single-item auctions, polynomial for simple multi-item mechanisms.

Bandit Mechanisms

Incentive-Compatible Exploration

In a multi-armed bandit setting, the mechanism recommends actions to strategic agents who have private information about their preferences. Agents may not follow recommendations if exploration harms their immediate utility.

Incentivized exploration (Mansour-Slivkins-Syrgkanis): Design payment schemes that compensate agents for exploring suboptimal arms, maintaining IC while achieving near-optimal social welfare. Budget for exploration must be bounded.

Dynamic Incentive Compatibility

Bayesian exploration exploitation: When agents are Bayesian (aware that the mechanism is learning), the mechanism must be IC against sophisticated Bayesian agents. This is harder than IC against myopic agents.

Information asymmetry: The mechanism may have more information (from previous agents) than the current agent. Can the mechanism exploit this information advantage while remaining IC?

Posted Price Mechanisms in Practice

Practical Considerations

  • Simplicity: Posted prices are simple for agents to understand (no complex bidding strategies)
  • Privacy: Agents reveal only accept/reject, not their exact valuations
  • Computational efficiency: No need to solve complex optimization problems
  • Revenue comparison: Posted prices achieve constant-factor approximation to optimal auction revenue in many settings (Chawla et al.)

Buy-Now Prices in Auctions

Hybrid mechanisms combining auctions with posted prices (eBay's "Buy It Now"). Theoretical analysis shows that adding a buy-now option can improve revenue by reducing risk for risk-averse bidders and attracting impatient buyers. Optimal buy-now prices depend on the value distribution and bidder risk preferences.

Online Matching and Allocation

Beyond single items: online bipartite matching (Karp-Vazirani-Vazirani achieve 1-1/e), AdWords problem (Mehta et al., 1-1/e competitive), and display ad allocation as online mechanism design problems. These combine algorithmic challenges (online decisions under uncertainty) with incentive considerations (truthful reporting of advertiser values).