  After experimentation with other designs, the major search engines converged
on the weighted, generalized second-price auction (wGSP) for selling keyword
advertisements. Notably, this convergence occurred before position auctions
were well understood (or, indeed, widely studied) theoretically. While much
progress has been made since, theoretical analysis is still not able to settle
the question of why search engines found wGSP preferable to other position
auctions. We approach this question in a new way, adopting a new analytical
paradigm we dub "computational mechanism analysis." By sampling position
auction games from a given distribution, encoding them in a computationally
efficient representation language, computing their Nash equilibria, and then
calculating economic quantities of interest, we can quantitatively answer
questions that theoretical methods have not. We considered seven widely studied
valuation models from the literature and three position auction variants
(generalized first price, unweighted generalized second price, and wGSP). We
found that wGSP consistently showed the best ads of any position auction,
measured both by social welfare and by relevance (expected number of clicks).
Even in models where wGSP was already known to have bad worse-case efficiency,
we found that it almost always performed well on average. In contrast, we found
that revenue was extremely variable across auction mechanisms, and was highly
sensitive to equilibrium selection, the preference model, and the valuation
distribution.
