VCG is strategyproof only when the auctioneer solves the winner-determination problem
exactly. Real auctions don't — the WDP is NP-hard, so solvers run under a time limit.
This study shows that a bidder who simply overbids 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 —
and that the exploit vanishes once the solver is given a quarter of that time.
72–75%
profitable at 5–10% solve time
+11.8
mean utility gain (×5 overbid)
~25%
solve time where it collapses
The finding: a manipulation window that slams shut
Each bidder commits to a fixed overbid multiplier before the auction, knowing
the distribution of competitors but never their realized bids. We sweep the solver's time limit as a
fraction of the mean exact solve time and measure, across 100 seeds, how often overbidding beats
truthful bidding.
Overbid ×5Overbid ×2Overbid ×1.25
Left: fraction of 100 instances where overbidding beat truthful bidding.
Right: mean utility gain over truthful. The manipulation lives entirely in the
shaded window where the solver runs at under ~20% of the time it needs to be exact;
past 25% it is a net loss. Common-value instances; x-axis is time limit ÷ mean exact solve time.
Under exact solving the picture inverts, exactly as theory predicts: overbidding is
unprofitable (0% at unlimited time), confirming VCG is incentive-compatible when the solver reaches proven
optimality. The exploit is a pure artifact of stopping early.
Why it happens: the anchor effect
The VCG payment charges a winner the welfare the rest of the market loses by their presence:
p = W(B₋ᵢ) − (W(B) − vᵢ).
Overbidding pays off only if the solver underestimatesW(B₋ᵢ) — the market's welfare without
the bidder — more than it underestimates W(B). Under time pressure, it does, and there's a structural
reason.
With focal bidder — W(B)
~4% below exact at 5% time limit
The 5× overbid is a high-value bid on a small bundle. Branch-and-bound grabs it into an early incumbent
and spends the rest of its budget on the smaller leftover problem. The overbid anchors the search.
Without focal bidder — W(B₋ᵢ)
~6% below exact at 5% time limit
No anchor. The solver must find the best allocation among all ~1,600 competing bids from scratch, and with
~0.15 s it explores far fewer branches — returning a more suboptimal, lower welfare.
That ~2-point asymmetry — roughly 8 welfare units — flows straight through the payment formula.
The bidder is charged for a market that the solver has quietly undervalued, so they pay far less than the
incentive-compatible price.
The price of the exploit
For a 5× overbid, exact VCG would charge a payment of about 34 — more than the bidder's mean
true value of ~29, which is precisely why honest mechanisms make overbidding unprofitable. Under a 5% time
limit the charged payment collapses to about 14:
Payment @ 5% limit
≈ 14
Mean true value
≈ 29
IC payment (exact)
≈ 34
Winning a ~29-value bundle for a ~14 payment nets roughly +15 in utility. By 25% of exact
solve time the payment recovers to ~33 and the gain is gone.
StrategiesFixed overbid ×{1.25, 2.0, 5.0}, committed before the auction
Seeds100 independent · 95% confidence intervals throughout
On novelty. 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. To my knowledge that
particular mechanism has not been characterized before. The anchor effect is a diagnostic account consistent with
the data, not a formal proof.