Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 37 ยท Mechanism Design and Auctions

Mechanism Design and the VCG Mechanism

Design rules so that selfish players reveal the truth: incentive compatibility, the revelation principle and the VCG mechanism, with a brute-force Python implementation.

Game theory usually asks: given the rules, what will players do? Mechanism design turns the question around: given what we want to happen, what rules should we write? It is "reverse game theory". A city wants to build a park only if it is worth the cost. A government wants to allocate spectrum to those who value it most. A platform wants advertisers to be honest. The difficulty is that the information needed (who values what) is private, and people can lie to their advantage.

The ingredients

A mechanism design problem has:

  • Agents i = 1..n, each with a private type (here, a valuation function v_i over outcomes).
  • A set of outcomes (who gets which item, whether a project is built).
  • A mechanism: agents report types (or bids), and a rule picks an outcome and payments p_i.
  • Quasi-linear utility: u_i = v_i(outcome) - p_i.

A mechanism is dominant-strategy incentive compatible (DSIC), or strategy-proof, if reporting your true type is a dominant strategy. The revelation principle says that if a goal can be reached by any mechanism in equilibrium, it can be reached by a truthful direct mechanism, so it is enough to search among truth-telling mechanisms.

Mechanism design

Goal An outcome we want, such as efficiency
Private types Agents know their own values
Rules Outcome and payments from reports
Incentive compatible Truth is the best report

The revelation principle lets us focus on truthful mechanisms.

1 / 2

The VCG mechanism

The Vickrey-Clarke-Groves (VCG) mechanism works for any set of outcomes:

  1. Ask every agent to report a valuation for every outcome.
  2. Choose the outcome that maximizes the sum of reported values (social welfare).
  3. Charge each agent i the externality they impose on the others: the best total value the others could achieve if i were absent, minus the total value the others actually receive at the chosen outcome. This is the Clarke pivot rule.

Agent i's payment is thus the harm their presence does to everyone else. Their utility becomes their value plus the others' values at the chosen outcome, minus a constant independent of their report. That is the total welfare, which the mechanism maximizes if reports are truthful. So truth-telling is dominant.

For one item, VCG is the Vickrey auction: the winner imposes on the others the loss of the best alternative, the second-highest value.

Implementing VCG by brute force

For small problems, we can enumerate all outcomes. Here: a set of items and bidders with arbitrary values for each item bundle. For simplicity, each bidder wants at most one item (unit demand) and has a value per item.

Python A VCG implementation for unit-demand bidders

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The result: Ann gets x and Bob gets y (total 17). Ann pays 6: without Ann, Bob would take x (8) and Cy y (5), a total of 13 for the others, but with Ann present the others get only 7 (Bob's y), so Ann's externality is 13 - 7 = 6. Bob pays 5: without Bob, Ann takes x (10) and Cy takes y (5) for 15, against 10 for the others now, so 15 - 10 = 5. Cy gets nothing and pays nothing.

Checking strategy-proofness

The theory says truthful reporting is dominant. Let the program test it: each bidder tries every misreport on a grid, while the others report truthfully, and we compare utilities (computed using true values).

Python Brute-force test of truthfulness

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The largest gain is 0: no one benefits from lying, whatever grid report they try.

What VCG achieves, and its limits

  • Efficient: it maximizes the true total value if everyone is truthful.
  • Individually rational: with the pivot rule, nobody pays more than their value, and nobody has a negative utility from participating.
  • Never runs a deficit in typical auctions: payments are non-negative.

But there are catches:

  • Low revenue. VCG can collect little; in the example above the total payments are far below the welfare created.
  • Complexity. Finding the welfare-maximizing outcome is NP-hard for combinatorial auctions, and all agents need to describe values for many bundles.
  • Collusion and false names. Agents can sometimes gain by splitting into several identities.
  • Budget balance. For public projects, no efficient, strategy-proof mechanism can also balance the budget exactly (Green-Laffont and Myerson-Satterthwaite impossibility results).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the VCG mechanism choose?

    VCG is efficient with respect to reports: it maximizes total reported welfare.
  2. 2. What does an agent pay under the Clarke pivot rule?

    They pay what the others would gain if they were absent, minus what the others get now.
  3. 3. What does the revelation principle say?

    So when designing mechanisms we can restrict attention to ones where telling the truth is an equilibrium.
  4. 4. For a single item, VCG reduces to which auction?

    The winner's externality is the second-highest value, which is the Vickrey payment.

Summary

  • Mechanism design chooses rules so that self-interested agents with private information produce a desired outcome.
  • DSIC means truth-telling is a dominant strategy; the revelation principle lets us focus on such mechanisms.
  • VCG picks the welfare-maximizing outcome and charges each agent their externality.
  • It is efficient and truthful, but revenue, computational complexity and false-name attacks are limits.
  • The Vickrey auction is VCG for one item.

Next: Cooperative Games and the Shapley Value