Phase VII — Game Theory for Optimization & Robotics | Week 15 | 2.5 hours Don't just play the game — design the rules so that self-interested agents produce the outcome you want.
The fleet controller must allocate tasks to robots — each robot privately knows its battery level, distance to task, and current load. Mechanism design provides auction-based allocation where truthful reporting is the dominant strategy. The VCG mechanism ensures efficient task assignment even when robots have private information.
Setting: A principal designs a game (mechanism) for $n$ agents with private types $\theta_i \in \Theta_i$.
A mechanism $(M, g)$ consists of: - Message spaces $M_i$ for each agent. - An outcome function $g: M_1 \times \cdots \times M_n \to X$ mapping messages to outcomes.
The revelation principle says: for any mechanism and equilibrium, there exists a direct mechanism where agents report types and truth-telling is an equilibrium, achieving the same outcome.
A direct mechanism is: - Dominant Strategy Incentive Compatible (DSIC): Truth-telling is a dominant strategy: $$u_i(\theta_i, g(\theta_i, \theta_{-i})) \geq u_i(\theta_i, g(\theta_i', \theta_{-i})) \quad \forall \theta_i, \theta_i', \theta_{-i}$$
Individual Rationality (IR): Each agent gets non-negative utility from participation.
The Vickrey-Clarke-Groves mechanism achieves efficient outcomes with truthful reporting.
The standard choice $h_i(\theta_{-i}) = \max_{x} \sum_{j \neq i} v_j(x, \theta_j)$ gives the Clarke pivot rule:
$$p_i = \underbrace{\max_x \sum_{j \neq i} v_j(x, \theta_j)}_{\text{welfare without } i} - \underbrace{\sum_{j \neq i} v_j(x^*(\theta), \theta_j)}_{\text{others' welfare with } i}$$
Agent $i$ pays the externality they impose on others.
| Auction | Rule | Equilibrium (IPV) |
|---|---|---|
| First-price sealed | Pay your bid | Shade bid: $b_i = \frac{n-1}{n}\theta_i$ |
| Second-price (Vickrey) | Pay 2nd highest | Bid truthfully: $b_i = \theta_i$ |
| English (ascending) | Open ascending | Stay until $\theta_i$ |
| Dutch (descending) | First to stop wins | Equivalent to first-price |
Revenue Equivalence Theorem (Myerson 1981): Under independent private values, symmetric equilibrium, and risk-neutral bidders, all standard auctions yield the same expected revenue:
$$E[\text{Revenue}] = E[\theta^{(2:n)}] = \frac{n-1}{n+1} \cdot \bar{\theta}$$
for uniform $\theta_i \sim U[0, \bar{\theta}]$, where $\theta^{(2:n)}$ is the second-highest valuation.
"""Mechanism design and auctions — Day 104"""
import numpy as np
from itertools import combinations
def vickrey_auction(bids):
"""Second-price sealed-bid auction.
Returns: (winner, payment)
"""
sorted_idx = np.argsort(bids)[::-1]
winner = sorted_idx[0]
payment = bids[sorted_idx[1]] # second-highest bid
return winner, payment
def first_price_auction(valuations, n_simulations=10000):
"""Simulate first-price auction with equilibrium bidding.
In symmetric IPV with uniform [0,1], equilibrium bid = (n-1)/n * valuation.
"""
n = len(valuations)
# Equilibrium bids
bids = [(n - 1) / n * v for v in valuations]
winner = np.argmax(bids)
payment = bids[winner]
return winner, payment, bids
def vcg_mechanism(valuations, items):
"""VCG mechanism for multi-item allocation.
Args:
valuations: dict of agent -> {item: value}
items: list of items to allocate
Returns:
allocation, payments
"""
agents = list(valuations.keys())
# Find efficient allocation (maximize total welfare)
best_alloc = None
best_welfare = -np.inf
# Simple: each item to one agent (no bundles)
from itertools import product as iproduct
for assignment in iproduct(agents, repeat=len(items)):
welfare = sum(valuations[assignment[j]].get(items[j], 0) for j in range(len(items)))
if welfare > best_welfare:
best_welfare = welfare
best_alloc = dict(zip(items, assignment))
# Compute VCG payments (Clarke pivot)
payments = {}
for i in agents:
# Welfare of others with i
others_welfare_with = sum(
valuations[best_alloc[item]].get(item, 0)
for item in items if best_alloc[item] != i
)
# Welfare of others without i (re-optimize excluding i)
other_agents = [a for a in agents if a != i]
best_without = -np.inf
for assignment in iproduct(other_agents, repeat=len(items)):
w = sum(valuations[assignment[j]].get(items[j], 0) for j in range(len(items)))
if w > best_without:
best_without = w
payments[i] = best_without - others_welfare_with
return best_alloc, payments
def simulate_revenue_equivalence(n_bidders=5, n_trials=50000):
"""Empirically verify revenue equivalence theorem."""
rev_first, rev_second = [], []
for _ in range(n_trials):
vals = np.random.uniform(0, 1, n_bidders)
# Vickrey (second-price): bid truthfully
_, pay_v = vickrey_auction(vals)
rev_second.append(pay_v)
# First-price: equilibrium shading
bids_fp = (n_bidders - 1) / n_bidders * vals
winner_fp = np.argmax(bids_fp)
rev_first.append(bids_fp[winner_fp])
theoretical = (n_bidders - 1) / (n_bidders + 1)
return {
'first_price': np.mean(rev_first),
'second_price': np.mean(rev_second),
'theoretical': theoretical
}
def prove_vickrey_ic():
"""Demonstrate incentive compatibility of Vickrey auction."""
true_value = 8.0
second_highest = 6.0 # fixed for demo
print("=== Vickrey IC Demonstration ===")
print(f"True value: {true_value}, Second-highest bid: {second_highest}\n")
for bid in [4, 6, 7, 8, 9, 10, 12]:
if bid > second_highest:
won = True
utility = true_value - second_highest # pay second-highest
else:
won = False
utility = 0
print(f" Bid {bid:2d}: {'WIN' if won else 'LOSE'}, utility = {utility:.1f}")
print(f"\nOptimal bid = {true_value} (truthful): no benefit from over/under-bidding")
# --- Demo ---
if __name__ == "__main__":
# Vickrey auction
bids = [10, 7, 8, 3, 9]
winner, payment = vickrey_auction(bids)
print(f"Vickrey: winner=Agent {winner} (bid={bids[winner]}), pays={payment}")
# VCG for task allocation
valuations = {
'R1': {'task_A': 10, 'task_B': 5},
'R2': {'task_A': 8, 'task_B': 7},
'R3': {'task_A': 3, 'task_B': 9},
}
alloc, payments = vcg_mechanism(valuations, ['task_A', 'task_B'])
print(f"\nVCG allocation: {alloc}")
print(f"VCG payments: {payments}")
# Revenue equivalence
rev = simulate_revenue_equivalence(n_bidders=5)
print(f"\nRevenue equivalence (5 bidders, U[0,1]):")
print(f" First-price: {rev['first_price']:.4f}")
print(f" Second-price: {rev['second_price']:.4f}")
print(f" Theoretical: {rev['theoretical']:.4f}")
prove_vickrey_ic()
P1. In a Vickrey auction with bids [12, 9, 15, 7], who wins and what do they pay? Why is bidding 15 optimal for the winner if their true value is 15?
P2. Compute VCG payments: 2 agents, 1 item. Agent A values it at 10, Agent B at 7.
P3. In a first-price auction with 3 bidders and values drawn from $U[0, 100]$, what is the equilibrium bid for a bidder with value 60?
E1. Implement Myerson's optimal auction for 2 bidders with $\theta_i \sim U[0,1]$. Show it sets a reserve price of $r = 1/2$ and compute expected revenue.
E2. Design a mechanism for allocating 3 tasks to 3 robots where each robot can handle at most 1 task. Prove your mechanism is DSIC and compute payments.
E3. Show that no mechanism can simultaneously satisfy DSIC, efficiency, individual rationality, and budget balance (Green-Laffont impossibility).