Vickrey–Clarke–Groves auction explained

A Vickrey–Clarke–Groves (VCG) auction is a type of sealed-bid auction of multiple items. Bidders submit bids that report their valuations for the items, without knowing the bids of the other bidders. The auction system assigns the items in a socially optimal manner: it charges each individual the harm they cause to other bidders.[1] It gives bidders an incentive to bid their true valuations, by ensuring that the optimal strategy for each bidder is to bid their true valuations of the items; it can be undermined by bidder collusion and in particular in some circumstances by a single bidder making multiple bids under different names. It is a generalization of a Vickrey auction for multiple items.

The auction is named after William Vickrey,[2] Edward H. Clarke,[3] and Theodore Groves[4] for their papers that successively generalized the idea.

The VCG auction is a specific use of the more general VCG mechanism. While the VCG auction tries to make a socially optimal allocation of items, VCG mechanisms allow for the selection of a socially optimal outcome out of a set of possible outcomes. If collusion is likely to occur among bidders, the VCG outperforms the generalized second-price auction for both revenues produced for the seller and allocative efficiency.[5]

Intuitive description

Consider an auction where a set of identical products are being sold. Bidders can take part in the auction by announcing the maximum price they are willing to pay to receive N products. Each buyer is allowed to declare more than one bid, since its willingness-to-pay per unit might be different depending on the total number of units it receives. Bidders cannot see other people's bids at any moment since they are sealed (only visible to the auction system). Once all the bids are made, the auction is closed.

All the possible combinations of bids are then considered by the auction system, and the one maximizing the total sum of bids is kept, with the condition that it does not exceed the total amount of products available and that at most one bid from each bidder can be used. Bidders who have made a successful bid then receive the product quantity specified in their bid. The price they pay in exchange, however, is not the amount they had bid initially but only the marginal harm their bid has caused to other bidders (which is at most as high as their original bid).

This marginal harm caused to other participants (i.e. the final price paid by each individual with a successful bid) can be calculated as: (sum of bids of the auction from the best combination of bids excluding the participant under consideration) − (what other winning bidders have bid in the current (best) combination of bids). If the sum of bids of the second best combination of bids is the same as that of the best combination, then the price paid by the buyers will be the same as their initial bid. In all other cases, the price paid by the buyers will be lower.

At the end of the auction, the total utility has been maximized since all the goods have been attributed to the people with the highest combined willingness-to-pay. If agents are fully rational and in the absence of collusion, we can assume that the willingness to pay have been reported truthfully since only the marginal harm to other bidders will be charged to each participant, making truthful reporting a weakly-dominant strategy. This type of auction, however, will not maximize the seller's revenue unless the sum of bids of the second best combination of bids is equal to the sum of bids of the best combination of bids.

Formal description

Notation

For any set of auctioned items

M=\{t1,\ldots,tm\}

and any set of bidders

N=\{b1,\ldots,bn\}

, let
M
V
N
be the social value of the VCG auction for a given bid-combination. That is, how much each person values the items they've just won, added up across everyone. The value of the item is zero if they do not win. For a bidder

bi

and item

tj

, let the bidder's bid for the item be

vi(tj)

. The notation

A\setminusB

means the set of elements of A which are not elements of B.

Assignment

A bidder

bi

whose bid for an item

tj

is an "overbid", namely

vi(tj)

, wins the item, but pays
M
V
N\setminus\{bi\
}-V^_, which is the social cost of their winning that is incurred by the rest of the agents.

Explanation

Indeed, the set of bidders other than

bi

is

N\setminus\{bi\}

. When item

tj

is available, they could attain welfare
M
V
N\setminus\{bi\
}. The winning of the item by

bi

reduces the set of available items to

M\setminus\{tj\}

, so the attainable welfare is now
M\setminus\{tj\
V
}_. The difference between the two levels of welfare is therefore the loss in attainable welfare suffered by the rest of the bidders, as predicted, given the winner

bi

got the item

tj

. This quantity depends on the offers of the rest of the agents and is unknown to agent

bi

.

Winner's utility

The winning bidder whose bid is the true value

A

for the item

tj

,

vi(tj)=A,

derives maximum utility

A-

M
\left(V
N\setminus\{bi\
}-V^_\right).

Examples

Two items, three bidders

Suppose two apples are being auctioned among three bidders.

First, the outcome of the auction is determined by maximizing bids: the apples go to bidder A and bidder B, since their combined bid of $5 + $2 = $7 is greater than the bid for two apples by bidder C who is willing to pay only $6. Thus, after the auction, the value achieved by bidder A is $5, by bidder B is $2, and by bidder C is $0 (since bidder C gets nothing). Note that the determination of winners is essentially a knapsack problem.

Next, the formula for deciding payments gives:

After the auction, A is $1 better off than before (paying $4 to gain $5 of utility), B is $1 better off than before (paying $1 to gain $2 of utility), and C is neutral (having not won anything).

Two bidders

Assume that there are two bidders,

b1

and

b2

, two items,

t1

and

t2

, and each bidder is allowed to obtain one item. We let

vi,j

be bidder

bi

's valuation for item

tj

. Assume

v1,1=10

,

v1,2=5

,

v2,1=5

, and

v2,2=3

. We see that both

b1

and

b2

would prefer to receive item

t1

; however, the socially optimal assignment gives item

t1

to bidder

b1

(so their achieved value is

10

) and item

t2

to bidder

b2

(so their achieved value is

3

). Hence, the total achieved value is

13

, which is optimal.

If person

b2

were not in the auction, person

b1

would still be assigned to

t1

, and hence person

b1

can gain nothing more. The current outcome is

10

; hence

b2

is charged

10-10=0

.

If person

b1

were not in the auction,

t1

would be assigned to

b2

, and would have valuation

5

. The current outcome is 3; hence

b1

is charged

5-3=2

.

Example #3

Consider an auction of

n

houses to

n

bidders, who are to each receive a house.

\tildevij

, represents the value player

i

has for house

j

. Possible outcomes are characterized by bipartite matchings pairing houses with people.If we know the values, then maximizing social welfare reduces to computing a maximum weight bipartite matching.

If we do not know the values, then we instead solicit bids

\tildebij

, asking each player

i

how much they would wish to bid for house

j

.Define

bi(a)=\tildebik

if bidder

i

receives house

k

in the matching

a

. Now compute

a*

, a maximum weightbipartite matching with respect to the bids, and compute

pi=\left[maxa\sumjbj(a)\right]-\sumj

*)
b
j(a
.

The first term is another max weight bipartite matching, and the second term can be computed easily from

a*

.

Optimality of truthful bidding

The following is a proof that bidding one's true valuations for the auctioned items is optimal.[6]

For each bidder

bi

, let

vi

be their true valuation of an item

ti

, and suppose (without loss of generality) that

bi

wins

ti

upon submitting their true valuations.Then the net utility

Ui

attained by

bi

is given by their own valuation of the item they've won, minus the price they've paid:

\begin{align} Ui&=

M
v
N\setminus\{bi\
}-V^_\right) \\&=\sum_v_j-\sum_v_j+V^_-V^M_ \\&=\sum_j v_j-V^_+V^_-V^M_ \\&=\sum_j v_j-V^M_\end

As

M
V
N\setminus\{bi\
} is independent of

vi

, the maximization of net utility is pursued by the mechanism along with the maximization of corporate gross utility

\sumjvj

for the declared bid

vi

.

To make it clearer, let us form the difference

Ui-Uj=\left[vi+

M\setminus\{ti\
V
}_\right] - \left[v_j + V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}\right] between net utility

Ui

of

bi

under truthful bidding

vi

gotten item

ti

, and net utility

Uj

of bidder

bi

under non-truthful bidding

v'i

for item

ti

gotten item

tj

on true utility

vj

.

\left[vj+

M\setminus\{tj\
V
}_\right] is the corporate gross utility obtained with the non-truthful bidding. But the allocation assigning

tj

to

bi

is different from the allocation assigning

ti

to

bi

which gets maximum (true) gross corporate utility. Hence

\left[vi+

M\setminus\{ti\
V
}_\right] - \left[v_j + V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}\right]\geq 0 and

Ui\geqUj

q.e.d.

See also

Notes and References

  1. Web site: von Ahn . Luis . Luis von Ahn . Sponsored Search . 15–396: Science of the Web Course Notes . Carnegie Mellon University . 2011-10-13 . https://web.archive.org/web/20150306210734/http://server251.theory.cs.cmu.edu/15-396/lectures_f11/lecture12.pdf . dead . 2015-03-06 . 2015-04-13.
  2. Counterspeculation, Auctions, and Competitive Sealed Tenders . Vickrey, William . The Journal of Finance . 1961 . 16 . 1 . 8–37 . 10.1111/j.1540-6261.1961.tb02789.x.
  3. Clarke, E. . 1971 . Multipart Pricing of Public Goods . Public Choice . 11 . 1 . 17–33 . 10.1007/bf01726210. 154860771 .
  4. Incentives in Teams . Groves, T. . Econometrica . 1973 . 41 . 4 . 617–631 . 10.2307/1914085. 1914085 .
  5. Decarolis . Francesco . Goldmanis . Maris . Penta . Antonio . Marketing agencies and collusive bidding in online ad auctions . National Bureau of Economic Research. Working Paper Series . 2017 . 10.3386/w23962 . 44056837 .
  6. Web site: Algorithms, Games, and Networks - Lecture 14. 2023-12-28 . Avrim. Blum . 2013-02-28.