Pink Iguana

Home » References » Vickrey-Clarke-Groves Mechanism and GSP

Vickrey-Clarke-Groves Mechanism and GSP


Caltech, cs/ee144, Unfairness and Fraud in Ad Auctions, here.

In online ad auctions, advertisers want visitors to click on their ads to sell their products. A site owner has a certain number of impression slots to allocate, so advertisers compete in bidding to obtain these slots. There are two main models for payment, cost-per-click (CPC) and cost-per-impression (CPM). The site owner can guarantee impressions but cannot guarantee clicks because the quality and placement of the ad affects the click-through rate (CTR) of each user. This disparity suggests that site owners have an incentive to improve CTR for ads paid under the CPC model and increase the number of impressions without regard for CTR for ads paid under the CPM model.
Terms defined:
Cost-per-click (CPC): a model where the advertiser pays each time a visitor clicks on the ad
Cost-per-impression (CPM): a model where the advertiser pays each time a visitor is shown the ad
Click-through-rate (CTR): the rate at which a visitor who is shown the ad clicks on it
Edelman, Ostrovsky, and Schwarz, Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords, here. I like this paper so far.
We investigate the “generalized second-price” (GSP) auction, a new mechanism used by search engines to sell online advertising. Although GSP looks similar to the Vickrey-Clarke-Groves (VCG) mechanism, its properties are very different. Unlike the VCG mechanism, GSP generally does not have an equilibrium in  dominant strategies, and truth-telling is not an equilibrium of GSP. To analyze the properties of GSP, we describe the generalized English auction that corresponds to GSP and show that it has a unique equilibrium. This is an ex post equilibrium, with the same payoffs to all players as the dominant strategy equilibrium of VCG. (JEL D44, L81, M37)

Jeffrey Ely, 2009, the Vickrey-Clarke-Groves Mechanism, here.

Return now to the general social choice setup.
A society consisting of n individuals
A set A of alternatives from which to choose.
vi (x) is the value to i from alternative x 2 A being chosen.
Monetary transfer scheme t = (t1, . . . , tn).

Conitzer, Duke Thesis, Mechanism Design, here.

In order for a preference aggregator to choose a good outcome, she needs to be provided with the
agents’ (relevant) preferences. Usually, the only way of learning these preferences is by having the
agents report them. Unfortunately, in settings where the agents are self-interested, they will report
these preferences truthfully if and only if it is in their best interest to do so. Thus, the preference
aggregator has the difficult task of not only choosing good outcomes for the given preferences, but
also choosing outcomes in such a way that agents will not have any incentive to misreport their
preferences. This is the topic of mechanism design, and the resulting outcome selection functions
are called mechanisms.

Y. Narahari, July 2012, The Vickrey-Clarke-Groves Mechanisms, here.

The main result in this section is that in the quasilinear environment, there exist social choice functions
that are both allocatively efficient and dominant strategy incentive compatible. These are in general
called the VCG (Vickrey–Clarke–Groves) mechanisms.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: