The Substitution Metric and the Performance of Clock Auctions
summary
Design for the U.S. incentive auction treats market clearing as a hard production problem: NP‑complete channel‑assignment (graph‑coloring/SAT with ~600,000 constraints) must be solved many times in real time, so the mechanism uses a greedy rejection/deferred‑acceptance descending clock with bidder‑specific multipliers (population/interference weights) instead of full optimization. Tests with CPLEX and Gurobi show greedy rules hit the optimum in the 90%+ range, avoiding Vickrey pricing instability; a hierarchy/approximate matroid (rho) metric predicts that performance.
AI-written summary · about