When approximate solvers break incentive compatibility — a profitable bid manipulation against a time-limited VCG combinatorial auction, and the branch-and-bound anchor effect that drives it.
📄 Read the write-up → · Full paper (PDF)
The Vickrey–Clarke–Groves mechanism is strategyproof only when the auctioneer solves the winner-determination problem (WDP) exactly. In practice the WDP is NP-hard, so real auctions run a MIP solver under a wall-clock time limit.
Across 100 random 60-item auctions, a focal bidder who commits to overbidding by 5× — without observing any competitor — turns a profit 72–75% of the time when the solver runs at 5–10% of the time it needs to be exact, for a mean utility gain of about +12. The exploit collapses by ~25% of exact solve time and is a net loss thereafter. Under exact solving it disappears entirely (0%), consistent with VCG's incentive-compatibility guarantee.
The VCG payment is p = W(B₋ᵢ) − (W(B) − vᵢ). Overbidding is profitable only if
the time-limited solver underestimates W(B₋ᵢ) (the market without the bidder)
more than it underestimates W(B). It does, structurally: a 5× overbid is a
high-value bid on a small bundle, so branch-and-bound pulls it into an early
incumbent and anchors the search — converging faster on the with-focal
instance. The without-focal instance has no such anchor and returns a more
suboptimal, lower welfare. That ~2-point asymmetry flows straight through the
payment formula, so the bidder is charged well below the incentive-compatible
price. (This is a diagnostic account consistent with the data, not a formal proof.)
index.html # the write-up (served via GitHub Pages)
report.pdf # full paper — IE 598 GTO, Spring 2026
make_figures.py # regenerates every figure from the committed CSVs
run_natural.py # the experiment that produced the data (see note below)
natural_raw.csv # full per-seed results — 4,800 rows (dist × strategy × time limit × seed)
natural_exact.csv # exact (no-time-limit) WDP solutions, used as the ground-truth reference
natural_plots/ # generated figures
requirements.txt
The figures are regenerable from the committed results with nothing but pandas/numpy/matplotlib:
pip install -r requirements.txt
python make_figures.py # reads natural_raw.csv + natural_exact.csv → natural_plots/On the raw data. run_natural.py is the script that generated the CSVs. It
drives the WDP solver from my combinatorial-auctions
project (a time-limited Gurobi branch-and-bound), which is not vendored here — so
run_natural.py is included as a record of the method, not as a one-command
rerun. The results it produced are committed (natural_raw.csv,
natural_exact.csv), so every number and figure in the paper is inspectable and
the analysis is fully reproducible from them.
That approximate winner determination can break VCG strategyproofness is known in general (Nisan & Ronen 2000; Lehmann, O'Callaghan & Shoham 2002). Prior work models adversarial or worst-case approximation; this study characterizes a specific, standard algorithmic implementation — Gurobi branch-and-bound under a wall-clock limit — and identifies the anchor mechanism behind it.
Course project for IE 598 (Game Theory & Optimization), Spring 2026 · Nick Trapp.