Mechanism Design

Sources: Wikipedia (CC BY-SA 4.0) · Vickrey (1961), Clarke (1971), Groves (1973)

Mechanism design is game theory in reverse. Instead of analyzing what players do in a given game, you design the game so that self-interested players produce the outcome you want. The revelation principle says: if any mechanism works, there is a direct mechanism where truthful reporting is optimal.

The revelation principle

For any mechanism where agents play some equilibrium strategy, there exists an equivalent direct mechanism where each agent simply reports their true type, and truthful reporting is a (Bayesian) Nash equilibrium. This is powerful: you only need to search over direct, truthful mechanisms. It does not say truth-telling is always optimal in practice; it says any achievable outcome can be achieved by a truthful mechanism.

Scheme

; Revelation principle illustration
; Direct mechanism: agents report values, mechanism decides

; Simple example: allocate one item to the highest-value agent
; Each agent reports their value. Truthful reporting is optimal
; in a second-price (Vickrey) mechanism.

(define (second-price-auction bids)
  ; Winner = highest bidder, pays second-highest price
  (let* ((sorted (sort bids >))
         (winner-bid (car sorted))
         (second-bid (cadr sorted))
         (winner-idx
           (let loop ((i 0) (bs bids))
             (if (= (car bs) winner-bid) i
                 (loop (+ i 1) (cdr bs))))))
    (list winner-idx second-bid)))

(define bids (list 30 50 20 45))
(define result (second-price-auction bids))
(display "Bids: ") (display bids) (newline)
(display "Winner: agent ") (display (car result)) (newline)
(display "Payment: $") (display (cadr result)) (newline)
(display "Winner's value: $") (display (list-ref bids (car result)))

Incentive compatibility

A mechanism is incentive compatible (IC) if every agent maximizes their payoff by reporting truthfully. Dominant-strategy IC means truth-telling is optimal regardless of what others do. Bayesian IC means it is optimal in expectation over others' types. The stronger the IC condition, the fewer mechanisms qualify, but the more robust the design.

Scheme

; Why truth-telling is dominant in Vickrey auction
; Agent's payoff = value - payment if they win, 0 otherwise
; Payment = second-highest bid (independent of own bid)

(define (payoff my-value my-bid other-bids)
  (let* ((all-bids (cons my-bid other-bids))
         (sorted (sort all-bids >))
         (highest (car sorted))
         (second (cadr sorted)))
    (if (= my-bid highest)
        (- my-value second)  ; win: value minus second price
        0)))                 ; lose

(define my-value 50)
(define others (list 30 20 45))

; Truthful bid
(display "Truthful (bid=50): ")
(display (payoff my-value 50 others)) (newline)

; Overbid: still win, same payment
(display "Overbid  (bid=80): ")
(display (payoff my-value 80 others)) (newline)

; Underbid: might lose (bid=40 < 45)
(display "Underbid (bid=40): ")
(display (payoff my-value 40 others)) (newline)

(display "Truth-telling is weakly dominant.")

The VCG mechanism

The Vickrey-Clarke-Groves mechanism generalizes second-price auctions to any allocation problem. Each agent reports their value for every possible outcome. The mechanism picks the allocation that maximizes total reported value. Each agent pays the externality they impose: the difference in others' welfare between the world with and without them. Truth-telling is a dominant strategy.

Scheme

; VCG mechanism for two items, three agents
; Each agent has values for items A and B
; Efficient allocation maximizes total value

; Values: (agent (value-for-A value-for-B))
(define vals
  (list (list 10 5)    ; agent 0
        (list 8 12)    ; agent 1
        (list 6 7)))   ; agent 2

; Efficient: assign A to agent 0 (val=10), B to agent 1 (val=12)
; Total welfare = 22

; VCG payment for agent 0:
; Without agent 0: best allocation gives agent1=12, agent2=7 => 19
; With agent 0: others get agent1=12, agent2=0 => 12
; Payment = 19 - 12 = 7

; VCG payment for agent 1:
; Without agent 1: agent0=10, agent2=7 => 17
; With agent 1: others get agent0=10, agent2=0 => 10
; Payment = 17 - 10 = 7

(display "Efficient allocation:") (newline)
(display "  Agent 0 gets A (value=10)") (newline)
(display "  Agent 1 gets B (value=12)") (newline)
(display "Total welfare: 22") (newline) (newline)
(display "VCG payments:") (newline)
(display "  Agent 0 pays: 7 (externality)") (newline)
(display "  Agent 1 pays: 7 (externality)") (newline)
(display "Net surplus:") (newline)
(display "  Agent 0: 10 - 7 = 3") (newline)
(display "  Agent 1: 12 - 7 = 5")

; VCG mechanism for two items, three agents
; Each agent has values for items A and B
; Efficient allocation maximizes total value

; Values: (agent (value-for-A value-for-B))
(define vals
  (list (list 10 5)    ; agent 0
        (list 8 12)    ; agent 1
        (list 6 7)))   ; agent 2

; Efficient: assign A to agent 0 (val=10), B to agent 1 (val=12)
; Total welfare = 22

; VCG payment for agent 0:
; Without agent 0: best allocation gives agent1=12, agent2=7 => 19
; With agent 0: others get agent1=12, agent2=0 => 12
; Payment = 19 - 12 = 7

; VCG payment for agent 1:
; Without agent 1: agent0=10, agent2=7 => 17
; With agent 1: others get agent0=10, agent2=0 => 10
; Payment = 17 - 10 = 7

(display "Efficient allocation:") (newline)
(display "  Agent 0 gets A (value=10)") (newline)
(display "  Agent 1 gets B (value=12)") (newline)
(display "Total welfare: 22") (newline) (newline)
(display "VCG payments:") (newline)
(display "  Agent 0 pays: 7 (externality)") (newline)
(display "  Agent 1 pays: 7 (externality)") (newline)
(display "Net surplus:") (newline)
(display "  Agent 0: 10 - 7 = 3") (newline)
(display "  Agent 1: 12 - 7 = 5")

Neighbors

Cross-references

Hedges 2018 — compositional game theory: mechanisms as composed open games
Game Theory Ch.6 — Nash equilibrium, the solution concept underlying IC
🎲 Game Theory — mechanism design is reverse game theory: design the rules to produce the desired equilibrium
🏷 VCG Mechanism — the canonical mechanism design result
june.kim/vector-space — mechanism design applied to embedding-space ad auctions

Foundations (Wikipedia)

← Fiscal and Monetary Policy by june.kim Behavioral Economics →