PaperlayerView exact revision on arXiv

Source-linked AI summary

General Auction Mechanism for Search Advertising

Gagan Aggarwal, S. Muthukrishnan, David Pal, Martin Pal

arXiv:0807.1297v1cs.GT

TL;DR

Sponsored-search auctions allocate advertising slots among competing advertisers, and the paper makes explicit a stable-matching model that includes existing mechanisms while allowing richer preferences and price bounds. It computes bidder-optimal stable matchings and uses them in a truthful mechanism; under general position, the matching is unique and computable in O(nk^3).

  • Problem

    Sponsored-search auctions allocate slots among competing advertisers, but existing mechanisms do not encompass practical features such as bidder- and position-specific price bounds or preferences beyond profit maximization.

    Source: §1 · pp. 1–2

  • Method

    The paper models auctions as one-to-one assignments with linear payoffs and price bounds, then solicits bidder preferences and computes a bidder-optimal stable matching.

    Source: §1 · p. 2, §3 · p. 3

  • Results

    Under general position, the auction has a unique bidder-optimal stable matching computable in O(nk^3), and truthful reporting is dominant for bidders whose preferences fit the max-value model.

    Source: §3.1 · p. 5

  • Takeaways & Limitations

    The model accommodates bidder- and position-specific price bounds and slot values, and the mechanism is truthful for max-value bidders.

    Source: §1 · p. 2, §3.1 · p. 5

    With exchange rates reflecting differing buyer and seller estimates of event probabilities, stable-matching existence and efficient computation are unknown.

    Source: §7 · p. 10

Abstract

from arXiv · show

In sponsored search, a number of advertising slots is available on a search results page, and have to be allocated among a set of advertisers competing to display an ad on the page. This gives rise to a bipartite matching market that is typically cleared by the way of an automated auction. Several auction mechanisms have been proposed, with variants of the Generalized Second Price (GSP) being widely used in practice. A rich body of work on bipartite matching markets builds upon the stable marriage model of Gale and Shapley and the assignment model of Shapley and Shubik. We apply insights from this line of research into the structure of stable outcomes and their incentive properties to advertising auctions. We model advertising auctions in terms of an assignment model with linear utilities, extended with bidder and item specific maximum and minimum prices. Auction mechanisms like the commonly used GSP or the well-known Vickrey-Clarke-Groves (VCG) are interpreted as simply computing a \emph{bidder-optimal stable matching} in this model, for a suitably defined set of bidder preferences. In our model, the existence of a stable matching is guaranteed, and under a non-degeneracy assumption a bidder-optimal stable matching exists as well. We give an algorithm to find such matching in polynomial time, and use it to design truthful mechanism that generalizes GSP, is truthful for profit-maximizing bidders, implements features like bidder-specific minimum prices and position-specific bids, and works for rich mixtures of bidders and preferences.

1 Introduction

The paper applies stable-matching ideas to sponsored-search auctions, making explicit a model that encompasses existing mechanisms and supports richer bidder preferences. It proposes a truthful mechanism and an efficient algorithm for computing bidder-optimal stable matchings.

1 Introduction

  • Sponsored search is a matching market in which advertisers compete for advertising slots offered by a publisher or search engine.The paper applies established work on stable outcomes and incentives in matching markets to sponsored search.Source: §1 · p. 1
  • The model interprets variants of GSP and VCG as computing stable matchings and includes existing mechanisms as special cases.It accommodates bidder- and position-specific minimum and maximum prices, plus different values for different slots.Source: §1 · pp. 1–2
  • The model allows preferences beyond profit maximization, including bidders who seek the highest possible slot while keeping its price below a personal cap.The passage notes that basic GSP is truthful for this described bidder class.Source: §1 · p. 2
  • The proposed mechanism solicits bidder preferences and computes a bidder-optimal stable matching, truthfully and—without money transfers among players—group-strategyproofly.The algorithm computes the matching and corresponding prices in O(nk^3), extending the Hungarian algorithm.Source: §1 · p. 2

2 Related Work

Related work develops stable and assignment models, their incentive properties, and extensions to richer preferences and payment rules. The paper places its one-to-one linear-payoff model among these approaches and relates it to sponsored-search mechanisms including GSP and VCG.

Matching Markets

  • In the stable-marriage model, deferred acceptance finds a man-optimal stable matching, and truthful reporting is a dominant strategy for men.A stable matching has no man and woman who would both prefer each other to their assigned partners.Source: §2 · p. 2
  • In the assignment model, side payments accompany partner values; stable outcomes correspond to maximum-weight matchings, and a man-optimal outcome matches VCG allocation and prices.The passage describes stable-outcome existence via linear programming and payoffs as dual variables of the matching LP.Source: §2 · p. 2
  • Prior work considered nonlinear payment utilities and man-optimal truthful mechanisms, but its continuity, strict-monotonicity, and full-domain conditions do not directly fit this setting.The cited results require utilities defined over the entire range from negative to positive infinity.Source: §2 · p. 2
  • Fujishige and Tamura’s broader many-to-many model establishes stable-outcome existence; this paper’s one-to-one special case adds bidder-optimality, truthfulness, and an efficient algorithm.Their model uses linear utilities and payment bounds, with existence shown under M♮-concavity.Source: §2 · pp. 2–3

Sponsored Search Auctions

  • GSP orders advertisers by bids and charges the next bid or a minimum price; it is not truthful for profit maximizers, while VCG is truthful but its prices may be harder to interpret.Some GSP variants have efficient Nash equilibria with VCG prices under assumptions, while a bidder-specific-minimum-price variant’s equilibrium is not tied to a natural VCG outcome.Source: §2 · p. 3
  • GSP’s usual preference ordering assumes bidders agree that higher slots are better, while position-preference features let advertisers restrict eligible positions.The passage notes that increasingly complex layouts and advertisers may weaken the universal-ordering assumption.Source: §2 · p. 3

3 Assignment Model with Maximum and Minimum Prices

The section defines an assignment model with bidder- and item-specific maximum and minimum prices, then states existence, computation, and truthfulness results for bidder-optimal stable matchings.

3 Assignment Model with Maximum and Minimum Prices

  • The max-value model specifies each bidder’s value and maximum price for each slot, alongside seller-set bidder-slot minimum prices.Minimum prices are assumed known to bidders in advance, with maximum prices no greater than values.Source: §3 · p. 3
  • The model seeks matchings that are simultaneously stable and feasible, with bidder-optimality comparing each bidder’s utility across stable feasible outcomes.A max-value bidder’s preferences can include profit maximizers and bidders seeking the highest affordable slot.Source: §3 · pp. 4–5
  • A bidder’s payoff is value minus price up to her maximum price, but becomes -1 above it; an unmatched bidder receives zero.This makes the payoff discontinuous at the maximum price and makes the bidder indifferent between zero payoff and being unmatched.Source: §3 · p. 5

3.1 Our Results

  • Every auction instance has a stable matching, and the mechanism assigns slots and charges their matching prices, or zero when unmatched.The bidder-optimal stable matching is unique under the stated general-position condition.Source: §3.1 · p. 5
  • Under general position, a unique bidder-optimal stable matching can be found in O(nk^3) time.Arbitrarily small symbolic perturbations or consistent tie-breaking can handle the assumption.Source: §3.1 · p. 5
  • Truthful reporting of values and maximum prices is a weakly dominant strategy for bidders whose preferences fit the max-value model.The mechanism computes a bidder-optimal stable matching from the submitted preferences.Source: §3.1 · p. 5

4 An Algorithm to Compute a Bidder-Optimal Matching

STABLEMATCH extends the Hungarian method to compute a stable, feasible matching while accounting for minimum- and maximum-price events. It uses shortest alternating paths and maintains stability as it updates utilities, prices, and assignments.

4 An Algorithm to Compute a Bidder-Optimal Matching

  • STABLEMATCH is an extension of the Hungarian method, adapted to handle events at minimum and maximum prices.The algorithm’s output is bidder-optimal when the auction instance is in general position.Source: §4 · pp. 5–6
  • Each iteration selects a minimum-weight alternating path, updates utilities and prices, then adjusts the assignment along that path.The algorithm starts with an empty matching and stops when no alternating path remains.Source: §4 · p. 6
  • STABLEMATCH maintains stability, making update-graph edge weights non-negative and allowing shortest paths to be computed in O(k^2) time.At most 2k vertices are reachable from the source at any time.Source: §4 · p. 7
  • Path-end handling depends on whether the path ends at a terminal, maximum-price, or reserve-price edge, with reserve-price cases receiving further matching-specific updates.For example, reaching a reserve price on an unmatched slot increases matching size, while a matched slot may require unmatching a bidder or flipping a cycle.Source: §4 · p. 7

5 Analysis

STABLEMATCH returns a feasible stable matching and, in general position, finds a bidder-optimal one in O(nk^3) time. Bidder-optimality is not guaranteed in degenerate instances, but exists outside such cases.

5 Analysis

  • In general position, STABLEMATCH computes a feasible, stable, bidder-optimal matching.Feasibility and stability follow from Lemma 9; Theorem 5 establishes bidder-optimality for instances in general position.Source: §5 · p. 8, §5.1 · p. 9
  • O(nk^3) is the overall running time, from at most n(2k + 1) iterations with O(k^2) work per iteration.The iteration bound is established by Lemma 10.Source: §5 · p. 8

5.1 Bidder Optimality

  • Outside general position, STABLEMATCH may return a stable, feasible matching that is not bidder-optimal, and bidder-optimal matchings need not exist.With one slot and two bidders sharing the same maximum bid, each stable matching favors a different bidder; outside such degenerate cases, bidder-optimality exists and STABLEMATCH finds it.Source: §5.1 · p. 8
  • General position excludes equal-weight alternating walks from a bidder to distinct reserve-price, maximum-price, or terminal edges; symbolic perturbation can enforce it.The implementation can break ties lexicographically by the identity of the walk’s final edge.Source: §5.1 · p. 8

6 Incentive Compatibility

The incentive-compatibility proof uses bidder-optimality to rule out outcomes that improve every bidder, then constrains blocking pairs in other feasible outcomes. It concludes that no bidder or coalition can manipulate bids so every coalition member strictly benefits.

6 Incentive Compatibility

  • Any feasible matching leaves at least one bidder no better off than in the bidder-optimal matching.The paper identifies this property as weak Pareto optimality.Source: §6 · p. 9
  • If a feasible matching has bidders better off than in the bidder-optimal matching, a blocking pair involves a bidder who is not better off.This lemma supports the manipulation result; the manipulated outcome is considered feasible for the true auction.Source: §6 · p. 9
  • No bidder or coalition can manipulate bids so that every coalition member strictly benefits.The theorem applies to the bidder-optimal stable matching mechanism.Source: §6 · p. 9

7 Conclusions

The paper applies stable-matching theory to sponsored-search auctions and identifies open questions about extending its results. Its model assumes a constant exchange rate; with bidder-item-dependent exchange rates, existence of stable or bidder-optimal matchings is unknown.

7 Conclusions

  • The authors describe their work as applying stable-matching theory to sponsored-search auctions and note that open questions remain.The conclusion does not specify further results in this passage.Source: §7 · p. 10
  • The authors identify extending worker- and firm-optimal equilibria and strategyproofness to a many-to-many model as an open question.The paper’s model is a special case of Fujishige and Tamura’s model.Source: §7 · p. 10
  • The max-value model assumes each dollar paid by a bidder is received by the seller at the same rate, independent of bidder and item.With click- or purchase-conditioned payments, differing buyer and seller probability estimates can create a revenue-cost discrepancy; stable matching existence in an exchange-rate model is unknown.Source: §7 · p. 10
  • Bidder-optimal matching existence may inform Nash-equilibrium existence in GSP under assumptions on bidder valuations or preferences.The authors ask whether a result on GSP equilibria can be re-derived and extended using guaranteed existence of bidder-optimal matchings.Source: §7 · p. 10

A Analysis of STABLEMATCH

This appendix passage identifies its contents as proofs of statements from Section 5.1.

A Analysis of STABLEMATCH

A.1 Invariants

The section proves five invariants of STABLEMATCH by induction, using two technical invariants whose proofs are omitted and rely on the general position assumption. The invariants are maintained through the algorithm’s updates, including the condition that unmatched slots have zero price.

A.1 Invariants

  • Five STABLEMATCH invariants are proved by induction; the technical invariants B1 and B2 rely on the general position assumption and their proofs are omitted.The proof uses B1 and B2 in the induction step for the first three invariants.Source: §A.1 · p. 12
  • Unmatched slots retain zero price: previously matched slots remain matched, at most one additional slot becomes matched, and all remaining slots keep price zero.The proof attributes the absence of forward edges to the general position assumption that reserve prices are positive.Source: §A.1 · p. 12
  • The induction step checks that the updated utilities, prices, and matching continue to satisfy the invariants across cases for matched and newly matched pairs.For pairs added along the alternating path, the proof distinguishes forward edges from a final reserve-price edge.Source: §A.1 · pp. 12–14

A.2 Proof of Lemma 10

Lemma 10 bounds STABLEMATCH’s iterations by counting edges in its update graph. Each iteration removes an edge, and the algorithm stops when no edges remain.

A.2 Proof of Lemma 10

  • At most 2nk+n iterations are needed: the initial graph has at most nk reserve-price edges, nk maximum-price edges, and n terminal edges, and each iteration removes one edge.The algorithm stops when the update graph has no edges left.Source: §A.2 · p. 14
  • The last edge of an iteration’s alternating path does not reappear in the next update graph, whether it is terminal, maximum-price, or reserve-price.The proof checks these three edge types separately.Source: §A.2 · p. 14
  • Utilities never increase and prices never decrease, so once that last edge disappears it cannot appear in any later update graph.This establishes that the edge count continues to fall across subsequent iterations.Source: §A.2 · p. 14

A.3 Proof of Lemma 14

The proof compares STABLEMATCH’s evolving utilities and prices with a feasible stable outcome. It establishes the update inequalities under the general position assumption and uses path-based claims to support the comparison.

A.3 Proof of Lemma 14

  • The comparison argument assumes general position and, without loss of generality, excludes matched pairs priced at their maximum price.The passage says this can be arranged by lowering some item prices and increasing some bidder utilities.Source: §A.3 · p. 14
  • For the inductive case, when current utilities and prices satisfy u(t) ≥ u′ and p(t) ≤ p′, Proposition 18 establishes the next-step bounds u(t+1) ≥ u′ and p(t+) ≤ p′.Source: §A.3 · p. 14
  • The proof establishes that each slot in J′ is matched to a bidder in I′ and each bidder in I′ is matched to a slot in J′, yielding a bijection between those sets.It then selects a slot in J′ with minimum distance from i0 to continue the path argument.Source: §A.3 · pp. 15–16

B Proofs of Incentive Compatibility

The incentive-compatibility proofs use reduced-auction and alternating-path arguments. The following section turns to examples of advertising auctions and their representation in the max-value model.

B Proofs of Incentive Compatibility

  • In the full-matching case, the proof examines STABLEMATCH’s last iteration and constructs a shorter alternating path ending in a reserve-price edge to obtain a contradiction.The argument uses the reserve-price edge’s length in forming the alternative path.Source: B Proofs of Incentive Compatibility · p. 16
  • For bidders whose utility exceeds the bidder-optimal utility, the proof constructs a reduced auction on I+ and J+, adjusting reserve prices to reflect bidders outside I+.The restricted bidder-optimal matching is feasible and stable in the reduced auction, which is used in the contradiction argument.Source: B Proofs of Incentive Compatibility · p. 17

C Modeling Advertising Auctions

C.1 Existing Mechanisms

The section recasts established search-auction outcomes as bidder-optimal stable matchings for corresponding bidder preferences. It then describes extensions for richer position and payment preferences, and relates stable outcomes through a lattice property.

C.1 Existing Mechanisms

  • Max-per-impression and max-per-click bidders have position-independent maximum costs; profit-maximizing bidders are modeled with value and maximum price equal to expected click value.The per-click model uses predicted click probabilities to translate click bids into maximum prices.Source: §C.1 · p. 18
  • Per-impression GSP, per-click GSP, and VCG outcomes are bidder-optimal stable matchings for max-per-impression, max-per-click, and profit-maximizing bidders, respectively.Source: §C.1 · p. 18
  • GSP can implement minimum prices, but the model also permits slot-specific reserves that are not easily implemented in GSP.A GSP reserve is the maximum of the bidder's reserve and the next bid.Source: §C.1 · p. 19

C.2 New Auction mechanisms

  • The max-value model expresses arbitrary position intervals and richer slot preferences, extending beyond studied GSP variants that let bidders specify a position prefix.The authors note that richer preferences may benefit content advertising with multiple ad areas.Source: §C.2 · p. 19
  • A mixed pool of click and impression bidders can be handled through stable matching, whereas a naive bid-order auction encourages bidders to report per-click payment.The incentive to report per-click applies when the click probability is below one.Source: §C.2 · p. 19
  • The proposed multiplier adjustment still permits profitable payment-type misreports when ctr2 < qC < ctr1 in the stated two-slot example.The example assumes ctr1 > ctr2; the second-position bidder can benefit when qC > ctr2, and the first-position bidder when qC < ctr1.Source: §C.2 · p. 20
  • The model accommodates bidders seeking price caps, selected positions, or profit, and the authors report no prior research on mechanisms for such diverse bidders.Source: §C.2 · p. 20

D Lattice Property

  • For auctions in general position, feasible stable matchings form a lattice; non-emptiness, closedness, and boundedness then imply minimum and maximum elements.This supplies an alternate proof that a bidder-optimal stable matching exists.Source: D Lattice Property · p. 20
Loading 0807.1297v1…