Chapter 7: The VCG Mechanism - You Pay What You Cost Others
In previous chapters, bidders wanted one thing (a single number). In this chapter, we look at Combinatorial Auctions.
The Setup: We are selling multiple items (e.g., License A and License B).
The Problem: Bidders have complex preferences.
Alice might pay $10 for A, $10 for B, but $100 for A and B together (Synergy).
How do we sell these items to maximize social welfare? And what do we charge to ensure truthfulness?
The Solution: The VCG Mechanism (Vickrey-Clarke-Groves)¶
The VCG mechanism is a generalization of the Second-Price auction. It works for any outcome structure.
The Rules¶
Allocation: Choose the outcome that maximizes Total Welfare (Total Happiness).
Payment: Each winner pays their “Social Cost” (or Externality).
What is “Social Cost”?¶
This is the brilliant insight of VCG. You pay exactly the amount of “harm” you cause to the other bidders by taking the items you won.
If your presence doesn’t hurt anyone (e.g., you take an apple nobody else wanted), you pay $0.
If you take an item that prevented Bob from getting $50 of value, you pay $50.
Let’s see this in action with a Spectrum Auction.
import itertools
def calculate_vcg(bidders, items):
"""
Runs a VCG Auction for a set of items and bidders.
"""
# 1. GENERATE ALL POSSIBLE OUTCOMES
# An outcome is an assignment of items to bidders.
# For simplicity in this demo, we assume items are unique.
# We check every permutation (Brute Force - VCG is computationally heavy!)
outcomes = []
# Create all possible assignments (Who gets Item A? Who gets Item B?)
# -1 represents "Nobody gets it"
bidder_indices = list(range(len(bidders))) + [-1]
# This generates all combinations of assigning items to bidders
import itertools
all_assignments = list(itertools.product(bidder_indices, repeat=len(items)))
best_outcome = None
max_welfare = -1
# 2. FIND OPTIMAL ALLOCATION (Maximize Social Welfare)
for assignment in all_assignments:
current_welfare = 0
current_bidders_items = {i: [] for i in range(len(bidders))}
# Build the bundles for this assignment
for item_idx, winner_idx in enumerate(assignment):
if winner_idx != -1:
current_bidders_items[winner_idx].append(items[item_idx])
# Calculate Value
possible = True
for b_idx in range(len(bidders)):
bundle = tuple(sorted(current_bidders_items[b_idx]))
# Get bidder's value for this specific bundle
val = bidders[b_idx].get(bundle, 0)
current_welfare += val
if current_welfare > max_welfare:
max_welfare = current_welfare
best_outcome = current_bidders_items
print(f"--- OPTIMAL OUTCOME (Social Welfare: ${max_welfare}) ---")
for b_idx, bundle in best_outcome.items():
if bundle:
print(f"Bidder {b_idx} wins: {bundle}")
print("-" * 30)
# 3. CALCULATE PAYMENTS (The VCG Formula)
# Payment_i = (Max Welfare WITHOUT i) - (Welfare of OTHERS in Optimal Outcome)
for i in range(len(bidders)):
# A. Calculate "Welfare of Others" in the current best outcome
welfare_others_current = 0
for b_idx, bundle in best_outcome.items():
if b_idx != i:
welfare_others_current += bidders[b_idx].get(tuple(sorted(bundle)), 0)
# B. Calculate "Max Welfare WITHOUT i" (Counterfactual)
# We re-run the optimization excluding bidder i
max_welfare_without_i = 0
for assignment in all_assignments:
# Skip assignments where i gets anything
if i in assignment:
continue
current_welfare_no_i = 0
current_bidders_items = {k: [] for k in range(len(bidders))}
for item_idx, winner_idx in enumerate(assignment):
if winner_idx != -1:
current_bidders_items[winner_idx].append(items[item_idx])
for b_idx in range(len(bidders)):
if b_idx == i: continue # Ignore i
bundle = tuple(sorted(current_bidders_items[b_idx]))
current_welfare_no_i += bidders[b_idx].get(bundle, 0)
if current_welfare_no_i > max_welfare_without_i:
max_welfare_without_i = current_welfare_no_i
# C. Final Calculation
payment = max_welfare_without_i - welfare_others_current
if best_outcome[i]: # If they won something
print(f"Bidder {i} Pays: ${payment} (External Harm: ${max_welfare_without_i} - ${welfare_others_current})")
# --- SCENARIO: The Telecom War ---
# Items: "North" and "South" spectrum licenses.
ITEMS = ["North", "South"]
# Bidder 0 (Regional North): Wants North ($100), doesn't care about South.
# Bidder 1 (Regional South): Wants South ($100), doesn't care about North.
# Bidder 2 (National Giant): Wants BOTH ($250). Useless individually.
bidders_data = [
# Bidder 0
{('North',): 100, ('South',): 0, ('North', 'South'): 100},
# Bidder 1
{('North',): 0, ('South',): 100, ('North', 'South'): 100},
# Bidder 2
{('North',): 0, ('South',): 0, ('North', 'South'): 250}
]
calculate_vcg(bidders_data, ITEMS)--- OPTIMAL OUTCOME (Social Welfare: $250) ---
Bidder 2 wins: ['North', 'South']
------------------------------
Bidder 2 Pays: $200 (External Harm: $200 - $0)
Analysis of the Output¶
You should see something interesting in the results:
Winner: Bidder 2 (The National Giant) wins both items.
This is correct because their value ($250) is higher than Bidder 0 + Bidder 1 combined ($100 + $100 = $200).
The Payment: Bidder 2 pays $200.
Why? If Bidder 2 wasn’t there, Bidder 0 would have won North ($100) and Bidder 1 would have won South ($100). Total Welfare = $200.
By showing up and winning, Bidder 2 “destroyed” $200 worth of value for the others.
Therefore, Bidder 2 pays exactly the damage they caused: $200.
Bidder 2 walks away with a profit of $50 ($250 value - $200 price).
The Catch: While VCG is theoretically perfect (Dominant Strategy Truthful), it has downsides:
Low Revenue: Sometimes the seller makes $0 even if the items are valuable.
Collusion: Losing bidders can team up to trick the system.
Complexity: As you saw in the code, we had to check every combination. For 100 items, this is impossible for a computer to solve!