GSP auction for online advertising

auction-theory-deep-dive

gsp-auction

online-advertising

mechanism-design

Analyze the Generalized Second-Price auction used by search engines: compute VCG payments vs GSP equilibrium payments, show that GSP is not truthful, and characterize locally envy-free equilibria.

Author

Raban Heller

Published

May 8, 2026

Modified

May 8, 2026

Keywords

GSP auction, generalized second-price, VCG, online advertising, position auction, locally envy-free

Introduction & motivation

Every time you type a query into Google, Bing, or another search engine, an auction takes place in milliseconds to determine which advertisements appear alongside the organic search results and in what order. This is the Generalized Second-Price (GSP) auction, and it is arguably the most economically significant auction mechanism in history — generating hundreds of billions of dollars in annual revenue for the major search platforms. The GSP auction is a position auction: there are $K$ advertising slots (positions) on the search results page, each with a different click-through rate (CTR) that declines with position (the top slot gets the most clicks, the second slot fewer, and so on). Advertisers submit bids representing their maximum willingness to pay per click, and the auction assigns positions to bidders in order of their bids, with each advertiser paying the bid of the advertiser in the position directly below them (hence “second-price” — but generalized to multiple positions).

The GSP auction has a fascinating relationship to two classic mechanisms. On one hand, it resembles the Vickrey (second-price) auction: each advertiser’s payment is determined by someone else’s bid, not their own. This might suggest that truthful bidding is optimal, as in the single-item Vickrey auction. But this intuition is wrong — the GSP auction is not truthful. An advertiser can sometimes benefit by lowering their bid to drop to a cheaper position where the cost-per-click savings outweigh the click-through rate loss. On the other hand, the GSP auction is related to the Vickrey-Clarke-Groves (VCG) mechanism, which is truthful and efficient. The VCG mechanism charges each advertiser the externality they impose on others, and it achieves efficient allocation with dominant-strategy truthfulness. However, VCG is not used in practice for search advertising, partly for historical reasons and partly because GSP generates weakly higher revenue than VCG in its most natural equilibrium.

The key theoretical result, due to Edelman, Ostrovsky, and Schwarz (2007) and Varian (2007), is that the GSP auction possesses a locally envy-free equilibrium (also called a “symmetric Nash equilibrium” by Varian) in which: (i) the allocation is identical to the VCG allocation (highest-value advertiser gets the top slot, etc.), (ii) each advertiser’s payment is at least as high as their VCG payment, and (iii) no advertiser envies the position directly above or below them. This equilibrium is the one that appears to be selected in practice, and it provides a natural benchmark for analyzing search advertising markets. In this tutorial, we implement a position auction with 3 to 5 advertisers, compute both VCG payments and GSP locally envy-free equilibrium payments, compare the revenue generated by each mechanism, and demonstrate that truthful bidding is not an equilibrium of the GSP by constructing a profitable deviation.

Mathematical formulation

Setup. There are $K$ positions with click-through rates $\alpha_1 > \alpha_2 > \cdots > \alpha_K > 0$ and $n \geq K$ advertisers with values per click $v_1 > v_2 > \cdots > v_n > 0$.

GSP mechanism. Advertisers bid $b_i$. Positions are assigned in decreasing bid order. The advertiser in position $k$ pays $b_{k+1}$ per click (the bid of the advertiser in position $k+1$), with the last positioned advertiser paying a reserve price $r$ (we set $r = 0$). Total payment of the advertiser in slot $k$:

\[ p_k^{\text{GSP}} = \alpha_k \cdot b_{k+1} \]

VCG mechanism. Under VCG, truthful bidding ($b_i = v_i$) is a dominant strategy. The payment of the advertiser in slot $k$ equals the externality they impose:

\[ p_k^{\text{VCG}} = \sum_{j=k+1}^{K} v_j (\alpha_{j-1} - \alpha_j) + v_{K+1} \cdot \alpha_K \]

where $v_{K+1} = 0$ if there are only $K$ advertisers (or the reserve price).

Locally envy-free (LEF) equilibrium. A bid profile is locally envy-free if no advertiser prefers the slot directly above (where they would pay more per click but get more clicks) or directly below. The LEF conditions for advertiser in slot $k$ with value $v_k$:

\[ \alpha_k (v_k - p_k) \geq \alpha_{k-1} (v_k - p_{k-1}) \quad \text{(no envy of slot above)} \] \[ \alpha_k (v_k - p_k) \geq \alpha_{k+1} (v_k - p_{k+1}) \quad \text{(no envy of slot below)} \]

where $p_k$ is the per-click price in slot $k$.

Key theorem (Edelman-Ostrovsky-Schwarz / Varian): The GSP has a locally envy-free equilibrium where bids satisfy:

\[ b_k = v_k - \frac{\alpha_{k+1}}{\alpha_k}(v_k - b_{k+1}), \quad b_{K+1} = 0 \]

This equilibrium yields revenue weakly above VCG: $p_k^{\text{LEF}} \geq p_k^{\text{VCG}}$ for all $k$.

R implementation

We implement the position auction, compute VCG and GSP locally envy-free payments, and demonstrate that GSP is not truthful.

# Position auction with K slots and n advertisers
# CTRs decline geometrically: alpha_k = alpha_1 * decay^(k-1)
compute_position_auction <- function(values, ctrs) {
  n <- length(values)
  K <- length(ctrs)

  # Sort values in decreasing order (efficient allocation)
  sorted_idx <- order(values, decreasing = TRUE)
  v <- values[sorted_idx]

  # VCG payments (per-click prices)
  vcg_total <- numeric(K)
  for (k in 1:K) {
    # Externality imposed by advertiser in slot k
    ext <- 0
    for (j in (k+1):min(K+1, n)) {
      if (j <= K) {
        ext <- ext + v[j] * (ctrs[j-1] - ctrs[j])
      }
    }
    # The last term: advertiser K+1 gets nothing without k, gets slot K with k removed
    if (K + 1 <= n) {
      ext <- ext + v[K+1] * ctrs[K]
    }
    vcg_total[k] <- ext
  }
  vcg_per_click <- vcg_total / ctrs

  # GSP locally envy-free equilibrium bids (bottom-up recursion)
  lef_bids <- numeric(K + 1)
  lef_bids[K + 1] <- 0  # reserve price
  if (K + 1 <= n) lef_bids[K + 1] <- v[K + 1]  # next-highest excluded bidder

  for (k in K:1) {
    # b_k = v_k - (alpha_{k+1}/alpha_k) * (v_k - b_{k+1})
    if (k < K) {
      alpha_ratio <- ctrs[k + 1] / ctrs[k]
    } else {
      alpha_ratio <- 0  # last position: no slot below (or use alpha_{K+1}=0)
    }
    lef_bids[k] <- v[k] - alpha_ratio * (v[k] - lef_bids[k + 1])
  }
  lef_bids <- lef_bids[1:K]

  # GSP payments: each position pays the bid of the one below
  gsp_per_click <- c(lef_bids[2:K], ifelse(K + 1 <= n, v[K + 1], 0))
  gsp_total <- ctrs * gsp_per_click

  # Advertiser surplus
  vcg_surplus <- ctrs * (v[1:K] - vcg_per_click)
  gsp_surplus <- ctrs * (v[1:K] - gsp_per_click)

  data.frame(
    slot = 1:K,
    advertiser = sorted_idx[1:K],
    value = v[1:K],
    ctr = ctrs,
    vcg_payment = vcg_total,
    vcg_per_click = vcg_per_click,
    gsp_bid = lef_bids,
    gsp_per_click = gsp_per_click,
    gsp_payment = gsp_total,
    vcg_surplus = vcg_surplus,
    gsp_surplus = gsp_surplus
  )
}

# Example: 5 advertisers, 3 positions
values_5 <- c(10, 8, 6, 4, 2)  # values per click
ctrs_3 <- c(0.20, 0.12, 0.06)  # CTRs for positions 1, 2, 3

results_5_3 <- compute_position_auction(values_5, ctrs_3)

cat("=== Position Auction: 5 advertisers, 3 slots ===\n\n")

=== Position Auction: 5 advertisers, 3 slots ===

cat("Click-through rates:", ctrs_3, "\n")

Click-through rates: 0.2 0.12 0.06

cat("Values per click:", values_5, "\n\n")

Values per click: 10 8 6 4 2

cat("Slot assignments and payments:\n")

Slot assignments and payments:

print(results_5_3, digits = 4)

  slot advertiser value  ctr vcg_payment vcg_per_click gsp_bid gsp_per_click
1    1          1    10 0.20        1.24           6.2     8.2             7
2    2          2     8 0.12        0.60           5.0     7.0             6
3    3          3     6 0.06        0.24           4.0     6.0             4
  gsp_payment vcg_surplus gsp_surplus
1        1.40        0.76        0.60
2        0.72        0.36        0.24
3        0.24        0.12        0.12

cat("\nTotal revenue comparison:\n")


Total revenue comparison:

cat("  VCG revenue: ", round(sum(results_5_3$vcg_payment), 4), "\n")

  VCG revenue:  2.08

cat("  GSP LEF revenue:", round(sum(results_5_3$gsp_payment), 4), "\n")

  GSP LEF revenue: 2.36

cat("  GSP >= VCG:", sum(results_5_3$gsp_payment) >= sum(results_5_3$vcg_payment) - 1e-10, "\n")

  GSP >= VCG: TRUE

Now we demonstrate that truthful bidding is NOT an equilibrium in GSP.

# Show that truthful bidding is not optimal in GSP
cat("=== Demonstrating GSP is NOT truthful ===\n\n")

=== Demonstrating GSP is NOT truthful ===

# Under truthful bidding in GSP, bids = values
# Payment in slot k = alpha_k * v_{k+1}
truthful_payments <- ctrs_3 * values_5[2:4]
truthful_surplus <- ctrs_3 * (values_5[1:3] - values_5[2:4])

cat("Truthful bidding (b_i = v_i):\n")

Truthful bidding (b_i = v_i):

for (k in 1:3) {
  cat(sprintf("  Slot %d: advertiser value=%d, pays %.2f per click, surplus=%.4f\n",
              k, values_5[k], values_5[k+1], truthful_surplus[k]))
}

  Slot 1: advertiser value=10, pays 8.00 per click, surplus=0.4000
  Slot 2: advertiser value=8, pays 6.00 per click, surplus=0.2400
  Slot 3: advertiser value=6, pays 4.00 per click, surplus=0.1200

# Consider advertiser 1 (value=10) deviating: bid just above v_3=6 to get slot 2
# instead of slot 1
cat("\nDeviation: Advertiser 1 (v=10) bids 6.01 instead of 10:\n")


Deviation: Advertiser 1 (v=10) bids 6.01 instead of 10:

cat("  Moves from slot 1 to slot 2\n")

  Moves from slot 1 to slot 2

deviation_surplus <- ctrs_3[2] * (values_5[1] - values_5[3])
cat(sprintf("  New surplus: %.2f * (10 - 6) = %.4f\n", ctrs_3[2], deviation_surplus))

  New surplus: 0.12 * (10 - 6) = 0.4800

cat(sprintf("  Old surplus: %.2f * (10 - 8) = %.4f\n", ctrs_3[1], truthful_surplus[1]))

  Old surplus: 0.20 * (10 - 8) = 0.4000

cat(sprintf("  Gain from deviation: %.4f\n", deviation_surplus - truthful_surplus[1]))

  Gain from deviation: 0.0800

if (deviation_surplus > truthful_surplus[1]) {
  cat("  => Truthful bidding is NOT optimal! GSP is not strategy-proof.\n")
} else {
  cat("  => Truthful bidding is optimal in this case.\n")
}

  => Truthful bidding is NOT optimal! GSP is not strategy-proof.

# Compare with VCG where truthful IS dominant
cat("\nUnder VCG, advertiser 1 pays:", round(results_5_3$vcg_payment[1], 4), "\n")


Under VCG, advertiser 1 pays: 1.24

cat("Under VCG, advertiser 1 surplus:", round(results_5_3$vcg_surplus[1], 4), "\n")

Under VCG, advertiser 1 surplus: 0.76

cat("VCG truthfulness is a DOMINANT strategy (no profitable deviation exists).\n")

VCG truthfulness is a DOMINANT strategy (no profitable deviation exists).

We also explore how revenue varies with different advertiser configurations.

# Compare GSP vs VCG across different value configurations
configs <- list(
  "Steep values" = c(20, 15, 10, 5, 1),
  "Flat values"  = c(10, 9, 8, 7, 6),
  "Moderate"     = c(10, 8, 6, 4, 2),
  "Top-heavy"    = c(25, 5, 4, 3, 2),
  "Competitive"  = c(12, 11, 10, 9, 8)
)

revenue_comparison <- lapply(names(configs), function(name) {
  res <- compute_position_auction(configs[[name]], ctrs_3)
  data.frame(
    config = name,
    vcg_revenue = sum(res$vcg_payment),
    gsp_revenue = sum(res$gsp_payment),
    premium_pct = (sum(res$gsp_payment) / sum(res$vcg_payment) - 1) * 100
  )
})
revenue_comp_df <- bind_rows(revenue_comparison)

cat("=== Revenue: GSP LEF vs VCG across configurations ===\n")

=== Revenue: GSP LEF vs VCG across configurations ===

print(revenue_comp_df, digits = 4)

        config vcg_revenue gsp_revenue premium_pct
1 Steep values        3.30        4.00      21.212
2  Flat values        2.94        3.08       4.762
3     Moderate        2.08        2.36      13.462
4    Top-heavy        1.42        1.56       9.859
5  Competitive        3.70        3.84       3.784

cat("\nGSP premium ranges from",
    round(min(revenue_comp_df$premium_pct), 1), "% to",
    round(max(revenue_comp_df$premium_pct), 1), "%\n")


GSP premium ranges from 3.8 % to 21.2 %

Static publication-ready figure

We visualize the per-slot payment comparison between VCG and GSP locally envy-free equilibrium.

payment_long <- results_5_3 |>
  select(slot, VCG = vcg_payment, `GSP LEF` = gsp_payment) |>
  pivot_longer(-slot, names_to = "Mechanism", values_to = "Payment") |>
  mutate(slot = factor(slot, labels = paste("Slot", 1:3)))

p_payments <- ggplot(payment_long, aes(x = slot, y = Payment, fill = Mechanism)) +
  geom_col(position = position_dodge(width = 0.7), width = 0.6, alpha = 0.85) +
  scale_fill_manual(values = c("VCG" = okabe_ito[1], "GSP LEF" = okabe_ito[5])) +
  # Add value labels on bars
  geom_text(aes(label = round(Payment, 3)),
            position = position_dodge(width = 0.7), vjust = -0.3, size = 3.2) +
  # Add slot details
  annotate("text", x = 1:3, y = -0.02,
           label = paste0("CTR=", ctrs_3, "\nv=", values_5[1:3]),
           size = 2.8, color = "grey40") +
  labs(
    title = "VCG vs. GSP locally envy-free payments by position",
    subtitle = "5 advertisers (v = 10,8,6,4,2), 3 slots (CTR = 0.20, 0.12, 0.06)",
    x = "", y = "Total payment"
  ) +
  theme_publication()

p_payments

Figure 1: Figure 1. Per-slot payment comparison between VCG and GSP locally envy-free (LEF) equilibrium for a position auction with 5 advertisers and 3 slots. GSP LEF payments (blue) weakly exceed VCG payments (orange) in every slot, confirming the theoretical prediction. The GSP premium arises because the GSP mechanism does not internalize the full VCG discount structure — it charges based on the next-lower bid rather than the true externality.

Interactive figure

The interactive figure shows advertiser surplus across both mechanisms and all positions, allowing exploration of the efficiency and distributional implications.

# Build a comprehensive comparison dataset for multiple slot counts
slot_configs <- list(
  "3 slots" = c(0.20, 0.12, 0.06),
  "4 slots" = c(0.20, 0.14, 0.09, 0.04),
  "5 slots" = c(0.20, 0.15, 0.10, 0.06, 0.03)
)

all_configs <- lapply(names(slot_configs), function(config_name) {
  ctrs <- slot_configs[[config_name]]
  K <- length(ctrs)
  # Need n > K advertisers
  vals <- seq(10, by = -2, length.out = K + 2)
  res <- compute_position_auction(vals, ctrs)
  res$config <- config_name
  res
})
all_configs_df <- bind_rows(all_configs)

# Plot surplus comparison
surplus_data <- all_configs_df |>
  select(slot, config, value, VCG = vcg_surplus, `GSP LEF` = gsp_surplus) |>
  pivot_longer(c(VCG, `GSP LEF`), names_to = "Mechanism", values_to = "Surplus") |>
  mutate(text = sprintf("Config: %s\nSlot: %d\nValue: %.0f\nMechanism: %s\nSurplus: %.4f",
                         config, slot, value, Mechanism, Surplus))

p_surplus <- ggplot(surplus_data, aes(x = interaction(slot, config),
                                       y = Surplus, fill = Mechanism, text = text)) +
  geom_col(position = position_dodge(width = 0.7), width = 0.6, alpha = 0.85) +
  scale_fill_manual(values = c("VCG" = okabe_ito[3], "GSP LEF" = okabe_ito[7])) +
  facet_wrap(~config, scales = "free_x") +
  labs(
    title = "Advertiser surplus: VCG vs GSP LEF across configurations",
    subtitle = "VCG gives higher surplus to advertisers; GSP extracts more for the platform",
    x = "Slot", y = "Surplus"
  ) +
  theme_publication() +
  theme(axis.text.x = element_text(angle = 45, hjust = 1))

ggplotly(p_surplus, tooltip = "text") |>
  config(displaylogo = FALSE,
         modeBarButtonsToRemove = c("select2d", "lasso2d"))

Figure 2

Interpretation

The analysis reveals several key features of the GSP auction that explain its dominance in practice despite its theoretical imperfections. First, the demonstration that GSP is not truthful is striking: in our example, the highest-value advertiser (value = 10) can increase surplus from 0.40 to 0.48 by shading their bid from 10 to just above 6, accepting the second slot instead of the first. This is fundamentally different from the single-item Vickrey auction, where truthful bidding is dominant regardless of other bidders’ strategies. The reason GSP breaks truthfulness is the multi-slot structure: by lowering their bid, an advertiser can drop to a position with a lower CTR but also a much lower per-click price, and the price savings can outweigh the CTR loss.

Second, the revenue comparison between VCG and GSP locally envy-free equilibrium consistently shows that GSP generates higher revenue for the platform. This is not a coincidence but a structural property: VCG payments are based on externalities (what each advertiser costs others by their presence), while GSP payments are based on the next-lower bid, which is generally higher. The GSP premium varies across advertiser configurations — it is highest when values are steep (large gaps between advertisers) and lowest when values are flat (intense competition), because with flat values, the GSP and VCG payments converge.

Third, the surplus analysis shows the flip side: advertisers prefer VCG because it gives them more surplus. The platform prefers GSP because it extracts more revenue. This creates a tension in mechanism design: VCG is incentive-compatible and efficient but leaves more money on the table for the platform, while GSP is not incentive-compatible but generates higher revenue in the locally envy-free equilibrium. Google’s choice of GSP over VCG reflects this revenue advantage, combined with the practical observation that advertisers seem to converge to the locally envy-free equilibrium in repeated play (each keyword auction is repeated millions of times, allowing learning). The locally envy-free condition is compelling because it means no advertiser wants to swap with their immediate neighbor — a natural stability concept for a ranked list of positions.

References

Reuse

CC BY-SA 4.0

Citation

BibTeX citation:

@online{heller2026,
  author = {Heller, Raban},
  title = {GSP Auction for Online Advertising},
  date = {2026-05-08},
  url = {https://r-heller.github.io/equilibria/tutorials/auction-theory-deep-dive/gsp-auction/},
  langid = {en}
}

For attribution, please cite this work as:

Heller, Raban. 2026. “GSP Auction for Online Advertising.” May 8. https://r-heller.github.io/equilibria/tutorials/auction-theory-deep-dive/gsp-auction/.

--- title: "GSP auction for online advertising" description: "Analyze the Generalized Second-Price auction used by search engines: compute VCG payments vs GSP equilibrium payments, show that GSP is not truthful, and characterize locally envy-free equilibria." author: "Raban Heller" date: 2026-05-08 date-modified: 2026-05-08 categories: - auction-theory-deep-dive - gsp-auction - online-advertising - mechanism-design keywords: ["GSP auction", "generalized second-price", "VCG", "online advertising", "position auction", "locally envy-free"] labels: ["auction-theory", "mechanism-design"] tier: 1 bibliography: ../../../references.bib vgwort: "TODO_VGWORT_auction-theory-deep-dive_gsp-auction" image: thumbnail.png image-alt: "Bar chart comparing VCG payments and GSP locally envy-free equilibrium payments across advertising positions" citation: type: webpage url: https://r-heller.github.io/equilibria/tutorials/auction-theory-deep-dive/gsp-auction/ license: "CC BY-SA 4.0" draft: false has_static_fig: true has_interactive_fig: true has_shiny_app: false --- ```{r} #| label: setup #| include: false library(ggplot2) library(dplyr) library(tidyr) library(plotly) okabe_ito <- c("#E69F00", "#56B4E9", "#009E73", "#F0E442", "#0072B2", "#D55E00", "#CC79A7", "#999999") theme_publication <- function(base_size = 12) { theme_minimal(base_size = base_size) + theme(plot.title = element_text(size = base_size * 1.2, face = "bold"), plot.subtitle = element_text(size = base_size * 0.9, color = "grey40"), axis.line = element_line(color = "grey30", linewidth = 0.3), panel.grid.minor = element_blank(), legend.position = "bottom", plot.margin = margin(10, 10, 10, 10)) } ``` ## Introduction & motivation Every time you type a query into Google, Bing, or another search engine, an auction takes place in milliseconds to determine which advertisements appear alongside the organic search results and in what order. This is the **Generalized Second-Price (GSP) auction**, and it is arguably the most economically significant auction mechanism in history — generating hundreds of billions of dollars in annual revenue for the major search platforms. The GSP auction is a **position auction**: there are $K$ advertising slots (positions) on the search results page, each with a different click-through rate (CTR) that declines with position (the top slot gets the most clicks, the second slot fewer, and so on). Advertisers submit bids representing their maximum willingness to pay per click, and the auction assigns positions to bidders in order of their bids, with each advertiser paying the bid of the advertiser in the position directly below them (hence "second-price" — but generalized to multiple positions). The GSP auction has a fascinating relationship to two classic mechanisms. On one hand, it resembles the Vickrey (second-price) auction: each advertiser's payment is determined by someone else's bid, not their own. This might suggest that truthful bidding is optimal, as in the single-item Vickrey auction. But this intuition is wrong — the GSP auction is **not truthful**. An advertiser can sometimes benefit by lowering their bid to drop to a cheaper position where the cost-per-click savings outweigh the click-through rate loss. On the other hand, the GSP auction is related to the **Vickrey-Clarke-Groves (VCG)** mechanism, which *is* truthful and efficient. The VCG mechanism charges each advertiser the externality they impose on others, and it achieves efficient allocation with dominant-strategy truthfulness. However, VCG is not used in practice for search advertising, partly for historical reasons and partly because GSP generates weakly higher revenue than VCG in its most natural equilibrium. The key theoretical result, due to Edelman, Ostrovsky, and Schwarz (2007) and Varian (2007), is that the GSP auction possesses a **locally envy-free equilibrium** (also called a "symmetric Nash equilibrium" by Varian) in which: (i) the allocation is identical to the VCG allocation (highest-value advertiser gets the top slot, etc.), (ii) each advertiser's payment is at least as high as their VCG payment, and (iii) no advertiser envies the position directly above or below them. This equilibrium is the one that appears to be selected in practice, and it provides a natural benchmark for analyzing search advertising markets. In this tutorial, we implement a position auction with 3 to 5 advertisers, compute both VCG payments and GSP locally envy-free equilibrium payments, compare the revenue generated by each mechanism, and demonstrate that truthful bidding is not an equilibrium of the GSP by constructing a profitable deviation. ## Mathematical formulation **Setup.** There are $K$ positions with click-through rates $\alpha_1 > \alpha_2 > \cdots > \alpha_K > 0$ and $n \geq K$ advertisers with values per click $v_1 > v_2 > \cdots > v_n > 0$. **GSP mechanism.** Advertisers bid $b_i$. Positions are assigned in decreasing bid order. The advertiser in position $k$ pays $b_{k+1}$ per click (the bid of the advertiser in position $k+1$), with the last positioned advertiser paying a reserve price $r$ (we set $r = 0$). Total payment of the advertiser in slot $k$: $$ p_k^{\text{GSP}} = \alpha_k \cdot b_{k+1} $$ **VCG mechanism.** Under VCG, truthful bidding ($b_i = v_i$) is a dominant strategy. The payment of the advertiser in slot $k$ equals the externality they impose: $$ p_k^{\text{VCG}} = \sum_{j=k+1}^{K} v_j (\alpha_{j-1} - \alpha_j) + v_{K+1} \cdot \alpha_K $$ where $v_{K+1} = 0$ if there are only $K$ advertisers (or the reserve price). **Locally envy-free (LEF) equilibrium.** A bid profile is locally envy-free if no advertiser prefers the slot directly above (where they would pay more per click but get more clicks) or directly below. The LEF conditions for advertiser in slot $k$ with value $v_k$: $$ \alpha_k (v_k - p_k) \geq \alpha_{k-1} (v_k - p_{k-1}) \quad \text{(no envy of slot above)} $$ $$ \alpha_k (v_k - p_k) \geq \alpha_{k+1} (v_k - p_{k+1}) \quad \text{(no envy of slot below)} $$ where $p_k$ is the per-click price in slot $k$. **Key theorem (Edelman-Ostrovsky-Schwarz / Varian):** The GSP has a locally envy-free equilibrium where bids satisfy: $$ b_k = v_k - \frac{\alpha_{k+1}}{\alpha_k}(v_k - b_{k+1}), \quad b_{K+1} = 0 $$ This equilibrium yields revenue weakly above VCG: $p_k^{\text{LEF}} \geq p_k^{\text{VCG}}$ for all $k$. ## R implementation We implement the position auction, compute VCG and GSP locally envy-free payments, and demonstrate that GSP is not truthful. ```{r} #| label: gsp-implementation # Position auction with K slots and n advertisers # CTRs decline geometrically: alpha_k = alpha_1 * decay^(k-1) compute_position_auction <- function(values, ctrs) { n <- length(values) K <- length(ctrs) # Sort values in decreasing order (efficient allocation) sorted_idx <- order(values, decreasing = TRUE) v <- values[sorted_idx] # VCG payments (per-click prices) vcg_total <- numeric(K) for (k in 1:K) { # Externality imposed by advertiser in slot k ext <- 0 for (j in (k+1):min(K+1, n)) { if (j <= K) { ext <- ext + v[j] * (ctrs[j-1] - ctrs[j]) } } # The last term: advertiser K+1 gets nothing without k, gets slot K with k removed if (K + 1 <= n) { ext <- ext + v[K+1] * ctrs[K] } vcg_total[k] <- ext } vcg_per_click <- vcg_total / ctrs # GSP locally envy-free equilibrium bids (bottom-up recursion) lef_bids <- numeric(K + 1) lef_bids[K + 1] <- 0 # reserve price if (K + 1 <= n) lef_bids[K + 1] <- v[K + 1] # next-highest excluded bidder for (k in K:1) { # b_k = v_k - (alpha_{k+1}/alpha_k) * (v_k - b_{k+1}) if (k < K) { alpha_ratio <- ctrs[k + 1] / ctrs[k] } else { alpha_ratio <- 0 # last position: no slot below (or use alpha_{K+1}=0) } lef_bids[k] <- v[k] - alpha_ratio * (v[k] - lef_bids[k + 1]) } lef_bids <- lef_bids[1:K] # GSP payments: each position pays the bid of the one below gsp_per_click <- c(lef_bids[2:K], ifelse(K + 1 <= n, v[K + 1], 0)) gsp_total <- ctrs * gsp_per_click # Advertiser surplus vcg_surplus <- ctrs * (v[1:K] - vcg_per_click) gsp_surplus <- ctrs * (v[1:K] - gsp_per_click) data.frame( slot = 1:K, advertiser = sorted_idx[1:K], value = v[1:K], ctr = ctrs, vcg_payment = vcg_total, vcg_per_click = vcg_per_click, gsp_bid = lef_bids, gsp_per_click = gsp_per_click, gsp_payment = gsp_total, vcg_surplus = vcg_surplus, gsp_surplus = gsp_surplus ) } # Example: 5 advertisers, 3 positions values_5 <- c(10, 8, 6, 4, 2) # values per click ctrs_3 <- c(0.20, 0.12, 0.06) # CTRs for positions 1, 2, 3 results_5_3 <- compute_position_auction(values_5, ctrs_3) cat("=== Position Auction: 5 advertisers, 3 slots ===\n\n") cat("Click-through rates:", ctrs_3, "\n") cat("Values per click:", values_5, "\n\n") cat("Slot assignments and payments:\n") print(results_5_3, digits = 4) cat("\nTotal revenue comparison:\n") cat(" VCG revenue: ", round(sum(results_5_3$vcg_payment), 4), "\n") cat(" GSP LEF revenue:", round(sum(results_5_3$gsp_payment), 4), "\n") cat(" GSP >= VCG:", sum(results_5_3$gsp_payment) >= sum(results_5_3$vcg_payment) - 1e-10, "\n") ``` Now we demonstrate that truthful bidding is NOT an equilibrium in GSP. ```{r} #| label: gsp-not-truthful # Show that truthful bidding is not optimal in GSP cat("=== Demonstrating GSP is NOT truthful ===\n\n") # Under truthful bidding in GSP, bids = values # Payment in slot k = alpha_k * v_{k+1} truthful_payments <- ctrs_3 * values_5[2:4] truthful_surplus <- ctrs_3 * (values_5[1:3] - values_5[2:4]) cat("Truthful bidding (b_i = v_i):\n") for (k in 1:3) { cat(sprintf(" Slot %d: advertiser value=%d, pays %.2f per click, surplus=%.4f\n", k, values_5[k], values_5[k+1], truthful_surplus[k])) } # Consider advertiser 1 (value=10) deviating: bid just above v_3=6 to get slot 2 # instead of slot 1 cat("\nDeviation: Advertiser 1 (v=10) bids 6.01 instead of 10:\n") cat(" Moves from slot 1 to slot 2\n") deviation_surplus <- ctrs_3[2] * (values_5[1] - values_5[3]) cat(sprintf(" New surplus: %.2f * (10 - 6) = %.4f\n", ctrs_3[2], deviation_surplus)) cat(sprintf(" Old surplus: %.2f * (10 - 8) = %.4f\n", ctrs_3[1], truthful_surplus[1])) cat(sprintf(" Gain from deviation: %.4f\n", deviation_surplus - truthful_surplus[1])) if (deviation_surplus > truthful_surplus[1]) { cat(" => Truthful bidding is NOT optimal! GSP is not strategy-proof.\n") } else { cat(" => Truthful bidding is optimal in this case.\n") } # Compare with VCG where truthful IS dominant cat("\nUnder VCG, advertiser 1 pays:", round(results_5_3$vcg_payment[1], 4), "\n") cat("Under VCG, advertiser 1 surplus:", round(results_5_3$vcg_surplus[1], 4), "\n") cat("VCG truthfulness is a DOMINANT strategy (no profitable deviation exists).\n") ``` We also explore how revenue varies with different advertiser configurations. ```{r} #| label: revenue-comparison-configs # Compare GSP vs VCG across different value configurations configs <- list( "Steep values" = c(20, 15, 10, 5, 1), "Flat values" = c(10, 9, 8, 7, 6), "Moderate" = c(10, 8, 6, 4, 2), "Top-heavy" = c(25, 5, 4, 3, 2), "Competitive" = c(12, 11, 10, 9, 8) ) revenue_comparison <- lapply(names(configs), function(name) { res <- compute_position_auction(configs[[name]], ctrs_3) data.frame( config = name, vcg_revenue = sum(res$vcg_payment), gsp_revenue = sum(res$gsp_payment), premium_pct = (sum(res$gsp_payment) / sum(res$vcg_payment) - 1) * 100 ) }) revenue_comp_df <- bind_rows(revenue_comparison) cat("=== Revenue: GSP LEF vs VCG across configurations ===\n") print(revenue_comp_df, digits = 4) cat("\nGSP premium ranges from", round(min(revenue_comp_df$premium_pct), 1), "% to", round(max(revenue_comp_df$premium_pct), 1), "%\n") ``` ## Static publication-ready figure We visualize the per-slot payment comparison between VCG and GSP locally envy-free equilibrium. ```{r} #| label: fig-gsp-payments #| fig-cap: "Figure 1. Per-slot payment comparison between VCG and GSP locally envy-free (LEF) equilibrium for a position auction with 5 advertisers and 3 slots. GSP LEF payments (blue) weakly exceed VCG payments (orange) in every slot, confirming the theoretical prediction. The GSP premium arises because the GSP mechanism does not internalize the full VCG discount structure — it charges based on the next-lower bid rather than the true externality." #| dev: [png, pdf] #| fig-width: 9 #| fig-height: 5 #| dpi: 300 payment_long <- results_5_3 |> select(slot, VCG = vcg_payment, `GSP LEF` = gsp_payment) |> pivot_longer(-slot, names_to = "Mechanism", values_to = "Payment") |> mutate(slot = factor(slot, labels = paste("Slot", 1:3))) p_payments <- ggplot(payment_long, aes(x = slot, y = Payment, fill = Mechanism)) + geom_col(position = position_dodge(width = 0.7), width = 0.6, alpha = 0.85) + scale_fill_manual(values = c("VCG" = okabe_ito[1], "GSP LEF" = okabe_ito[5])) + # Add value labels on bars geom_text(aes(label = round(Payment, 3)), position = position_dodge(width = 0.7), vjust = -0.3, size = 3.2) + # Add slot details annotate("text", x = 1:3, y = -0.02, label = paste0("CTR=", ctrs_3, "\nv=", values_5[1:3]), size = 2.8, color = "grey40") + labs( title = "VCG vs. GSP locally envy-free payments by position", subtitle = "5 advertisers (v = 10,8,6,4,2), 3 slots (CTR = 0.20, 0.12, 0.06)", x = "", y = "Total payment" ) + theme_publication() p_payments ``` ## Interactive figure The interactive figure shows advertiser surplus across both mechanisms and all positions, allowing exploration of the efficiency and distributional implications. ```{r} #| label: fig-gsp-interactive # Build a comprehensive comparison dataset for multiple slot counts slot_configs <- list( "3 slots" = c(0.20, 0.12, 0.06), "4 slots" = c(0.20, 0.14, 0.09, 0.04), "5 slots" = c(0.20, 0.15, 0.10, 0.06, 0.03) ) all_configs <- lapply(names(slot_configs), function(config_name) { ctrs <- slot_configs[[config_name]] K <- length(ctrs) # Need n > K advertisers vals <- seq(10, by = -2, length.out = K + 2) res <- compute_position_auction(vals, ctrs) res$config <- config_name res }) all_configs_df <- bind_rows(all_configs) # Plot surplus comparison surplus_data <- all_configs_df |> select(slot, config, value, VCG = vcg_surplus, `GSP LEF` = gsp_surplus) |> pivot_longer(c(VCG, `GSP LEF`), names_to = "Mechanism", values_to = "Surplus") |> mutate(text = sprintf("Config: %s\nSlot: %d\nValue: %.0f\nMechanism: %s\nSurplus: %.4f", config, slot, value, Mechanism, Surplus)) p_surplus <- ggplot(surplus_data, aes(x = interaction(slot, config), y = Surplus, fill = Mechanism, text = text)) + geom_col(position = position_dodge(width = 0.7), width = 0.6, alpha = 0.85) + scale_fill_manual(values = c("VCG" = okabe_ito[3], "GSP LEF" = okabe_ito[7])) + facet_wrap(~config, scales = "free_x") + labs( title = "Advertiser surplus: VCG vs GSP LEF across configurations", subtitle = "VCG gives higher surplus to advertisers; GSP extracts more for the platform", x = "Slot", y = "Surplus" ) + theme_publication() + theme(axis.text.x = element_text(angle = 45, hjust = 1)) ggplotly(p_surplus, tooltip = "text") |> config(displaylogo = FALSE, modeBarButtonsToRemove = c("select2d", "lasso2d")) ``` ## Interpretation The analysis reveals several key features of the GSP auction that explain its dominance in practice despite its theoretical imperfections. First, the demonstration that GSP is not truthful is striking: in our example, the highest-value advertiser (value = 10) can increase surplus from 0.40 to 0.48 by shading their bid from 10 to just above 6, accepting the second slot instead of the first. This is fundamentally different from the single-item Vickrey auction, where truthful bidding is dominant regardless of other bidders' strategies. The reason GSP breaks truthfulness is the multi-slot structure: by lowering their bid, an advertiser can drop to a position with a lower CTR but also a much lower per-click price, and the price savings can outweigh the CTR loss. Second, the revenue comparison between VCG and GSP locally envy-free equilibrium consistently shows that GSP generates higher revenue for the platform. This is not a coincidence but a structural property: VCG payments are based on externalities (what each advertiser costs others by their presence), while GSP payments are based on the next-lower bid, which is generally higher. The GSP premium varies across advertiser configurations — it is highest when values are steep (large gaps between advertisers) and lowest when values are flat (intense competition), because with flat values, the GSP and VCG payments converge. Third, the surplus analysis shows the flip side: advertisers prefer VCG because it gives them more surplus. The platform prefers GSP because it extracts more revenue. This creates a tension in mechanism design: VCG is incentive-compatible and efficient but leaves more money on the table for the platform, while GSP is not incentive-compatible but generates higher revenue in the locally envy-free equilibrium. Google's choice of GSP over VCG reflects this revenue advantage, combined with the practical observation that advertisers seem to converge to the locally envy-free equilibrium in repeated play (each keyword auction is repeated millions of times, allowing learning). The locally envy-free condition is compelling because it means no advertiser wants to swap with their immediate neighbor — a natural stability concept for a ranked list of positions. ## Extensions & related tutorials - [Revenue equivalence theorem](../revenue-equivalence/) — the benchmark single-item result that motivates the multi-slot analysis. - [First-price sealed-bid auctions](../first-price-sealed-bid/) — the single-item analog where bid shading is also optimal. - [Common-value auctions and the winner's curse](../common-value-winners-curse/) — common-value elements arise in search advertising when CTRs are uncertain. - [Dominant strategies and iterated elimination](../../foundations/dominant-strategies-iterated-elimination/) — why VCG achieves truthfulness through dominant strategies while GSP does not. - [Nash equilibrium in mixed strategies](../../foundations/nash-equilibrium-mixed/) — the equilibrium concept underlying the GSP equilibrium analysis. ## References ::: {#refs} :::