The generalized second price (GSP) auction has served as the core selling
mechanism for sponsored search ads for over a decade. However, recent trends
expanding the set of allowed ad formats---to include a variety of sizes,
decorations, and other distinguishing features---have raised critical problems
for GSP-based platforms. Alternatives such as the Vickrey-Clarke-Groves (VCG)
auction raise different complications because they fundamentally change the way
prices are computed. In this paper we report on our efforts to redesign a
search ad selling system from the ground up in this new context, proposing a
mechanism that optimizes an entire slate of ads globally and computes prices
that achieve properties analogous to those held by GSP in the original, simpler
setting of uniform ads. A careful algorithmic coupling of
allocation-optimization and pricing-computation allows our auction to operate
within the strict timing constraints inherent in real-time ad auctions. We
report performance results of the auction in Yahoo's Gemini Search platform.

该研究报告探讨了随着广告形式的变革，GSP 拍卖架构在计算价格时所遇到的问题，并提出了一种重新设计搜索广告销售系统的机制来解决这些问题。

带有丰富广告的赞助搜索拍卖

Sponsored Search Auctions with Rich Ads

The Generalized Second Price (GSP) auction is the primary auction used for
monetizing the use of the Internet. It is well-known that truthtelling is not a
dominant strategy in this auction and that inefficient equilibria can arise. In
this paper we study the space of equilibria in GSP, and quantify the efficiency
loss that can arise in equilibria under a wide range of sources of uncertainty,
as well as in the full information setting. The traditional Bayesian game
models uncertainty in the valuations (types) of the participants. The
Generalized Second Price (GSP) auction gives rise to a further form of
uncertainty: the selection of quality factors resulting in uncertainty about
the behavior of the underlying ad allocation algorithm. The bounds we obtain
apply to both forms of uncertainty, and are robust in the sense that they apply
under various perturbations of the solution concept, extending to models with
information asymmetries and bounded rationality in the form of learning
strategies.
We present a constant bound (2.927) on the factor of the efficiency loss
(\emph{price of anarchy}) of the corresponding game for the Bayesian model of
partial information about other participants and about ad quality factors. For
the full information setting, we prove a surprisingly low upper bound of 1.282
on the price of anarchy over pure Nash equilibria, nearly matching a lower
bound of 1.259 for the case of three advertisers. Further, we do not require
that the system reaches equilibrium, and give similarly low bounds also on the
quality degradation for any no-regret learning outcome. Our conclusion is that
the number of advertisers in the auction has almost no impact on the price of
anarchy, and that the efficiency of GSP is very robust with respect to the
belief and rationality assumptions imposed on the participants.

本文研究了广义第二价格 (GSP) 拍卖中的均衡状态空间，并量化了广泛来源的不确定性和完全信息设置下可能出现的低效均衡状态损失。通过贝叶斯博弈模型，得出了 2.927 的损失因子上限，证明了拍卖参与者关于其他参与者和广告质量因素的部分信息的贝叶斯模型中的效率损失。此外，在完全信息设置中，我们证明了对于三个广告商的情况下，纯纳什均衡的 “惩罚因子” 的上限接近于 1.282，同时我们展示了类似的低上限的结果适用于任何遵循无后悔策略的拍卖结果。

广义二价定价拍卖中结果低效性的限制

Bounding the inefficiency of outcomes in generalized second price  auctions

Sponsored search involves running an auction among advertisers who bid in
order to have their ad shown next to search results for specific keywords.
Currently, the most popular auction for sponsored search is the "Generalized
Second Price" (GSP) auction in which advertisers are assigned to slots in the
decreasing order of their "score," which is defined as the product of their bid
and click-through rate. In the past few years, there has been significant
research on the game-theoretic issues that arise in an advertiser's interaction
with the mechanism as well as possible redesigns of the mechanism, but this
ranking order has remained standard.
From a search engine's perspective, the fundamental question is: what is the
best assignment of advertisers to slots? Here "best" could mean "maximizing
user satisfaction," "most efficient," "revenue-maximizing," "simplest to
interact with," or a combination of these. To answer this question we need to
understand the behavior of a search engine user when she sees the displayed
ads, since that defines the commodity the advertisers are bidding on, and its
value. Most prior work has assumed that the probability of a user clicking on
an ad is independent of the other ads shown on the page.
We propose a simple Markovian user model that does not make this assumption.
We then present an algorithm to determine the most efficient assignment under
this model, which turns out to be different than that of GSP. A truthful
auction then follows from an application of the Vickrey-Clarke-Groves (VCG)
mechanism. Further, we show that our assignment has many of the desirable
properties of GSP that makes bidding intuitive. At the technical core of our
result are a number of insights about the structure of the optimal assignment.

通过研究用户行为，提出一种基于马尔可夫模型的最高效广告分配算法，结合 VCG 机制实现真实拍卖，得到了和 GSP 相似的拍卖稳定性和直观性。