How Much Should It Cost to Walk Away? Exit Penalties as a Defense Against Fake-Identity Bidding

Online auctions and automated marketplaces cannot check who is behind a bid, so one participant can bid under several made-up names. Mechanisms built to resist this, called false-name-proof auctions, quietly assume that every winning bid is binding. Real platforms let winners back out, and once backing out is free, a known attack opens up. The attacker uses a throwaway identity to bend prices or allocations in its favor, then withdraws that identity's winnings. A cleaner remedy than redesigning the auction comes from a different literature. Leveled commitment contracts let anyone exit a deal by paying a penalty fixed in advance, and the penalty level is the design knob. This note proposes treating the exit penalty as that knob. The question is how large the penalty must be before the fake-identity-plus-withdrawal attack stops paying, and whether that level is still low enough to keep the efficiency gains that motivated letting people exit in the first place.

The two literatures pull in opposite directions. False-name-proofness with bid withdrawal studies only free exit. It shows that withdrawal makes false-name-proofness strictly harder to achieve, and that the Leveled Division Set protocol, a standard hierarchical-bundling false-name-proof auction, breaks under it. Simulations of leveled commitment contracts (Leveled Commitment Contracts with Myopic and Strategic Agents) find that low but nonzero penalties, roughly 10% to 25% of contract value, maximize welfare. Between zero and infinity there is a whole range of penalties that nobody has analyzed against fake identities.

Core Claim

Fix an auction $M$ that is false-name-proof when bids are binding. Let $\gamma$ be a withdrawal penalty charged as a fraction of the price the withdrawing identity would have paid. Define the attacker's withdrawal rent at penalty $\gamma$ as the best utility it can get by splitting into identities and withdrawing some of their wins, minus its utility from bidding truthfully under one name:

$$R_M(\gamma) = \max_{\text{splits } s,\ \text{withdrawn set } W} \Big[ u_s - \gamma \sum_{j \in W} p_j \Big] - u_{\text{truth}},$$

Here $u_s$ is the attacker's true value for what its kept identities receive minus their payments, and $p_j$ is the price assigned to withdrawn identity $j$. The critical penalty $\gamma^*(M)$ is the smallest $\gamma$ at which $R_M(\gamma) \le 0$ for every bidder and every profile, or in expectation under a prior for the Bayesian version.

Three claims structure the work. First, there is an easy upper bound. Suppose withdrawn items return to the seller and are not reallocated within the same run, and the penalty is paid to the seller. Then $\gamma = 1$ suffices for any false-name-proof $M$ when valuations allow free disposal. Paying full price and walking away is never better than keeping the item, and keeping it is covered by ordinary false-name-proofness. So $\gamma^*(M) \in [0,1]$, with $\gamma^* = 0$ exactly when $M$ already survives free withdrawal in the Guo–Conitzer sense.

Second, the interesting quantity is where $\gamma^*$ falls inside that interval for mechanisms that fail under free withdrawal, especially Leveled Division Set. A full-price penalty leaves honest bidders almost no reason to exit. If $\gamma^*$ is well below the 10–25% range, one mechanism can both resist Sybils and allow useful exits. If it is near 1, penalties are no substitute for redesign.

Third, the routing of the penalty is not a detail. If the penalty is paid to whoever receives the item next, or redistributed to other bidders, the attacker's own sock puppet can collect it, and the effective penalty falls toward zero. Penalties must go to the seller or be burned.

Research Program

The theoretical part has three pieces. The first is to prove the $\gamma = 1$ sufficiency result and to state exactly when it fails: when withdrawn items are reallocated in the same run, since the next recipient may be another fake identity, and when valuations violate free disposal. The second is to characterize $\gamma^*$ for Leveled Division Set and for the Vickrey–Clarke–Groves auction (the standard auction that charges each winner the welfare loss it imposes on others) outside the submodular case, where Guo and Conitzer show it fails under free withdrawal. The working hypothesis is that the rent is bounded by the price gap between adjacent levels of the bundle hierarchy, so $\gamma^*$ depends on how reserve prices are spaced. The third is a Bayesian version, following VCG under Sybil (False-Name) Attacks - A Bayesian Analysis. That paper shows that when enough bidders want single items (high "granularity" $q$), an attacker who splits risks competing against itself and loses. A positive penalty adds a second deterrent, because a throwaway identity that unexpectedly wins forces the attacker to pay to discard it. We expect the two effects to trade off: a curve $\gamma^*(q)$ that falls to zero exactly at the published granularity threshold.

The computational part reuses the linear-programming style of automated mechanism design from Guo and Conitzer. That method was exponential and limited to two items there, which is acceptable for computing exact $\gamma^*$ on discretized instances with two or three items and a few bidders. Exits by honest bidders are modeled as in Advantages of a Leveled Commitment Contracting Protocol: after the auction, each winner draws a random outside opportunity and exits when it beats the penalty plus the forgone surplus. Honest welfare can therefore be measured at the same penalty used against attackers.

The scope is deliberately narrow. Only bidders can exit. Seller-side revocation, studied with mutual bid bonds in Truthful Risk-Managed Combinatorial Auctions, opens a separate attack in which the attacker plants a fake backup bid to collect the seller's compensation. That case is treated only as a stress test of the routing claim.

Baselines

The naive reference point is Leveled Division Set (Robust Combinatorial Auction Protocol against False-Name Bids) with free withdrawal and a best-responding attacker. This is the situation Guo and Conitzer show to be broken, and it sets the floor. The opposite extreme is Leveled Division Set under full commitment. It is false-name-proof by construction and shows how much welfare from honest exits a binding auction leaves unclaimed.

The strongest existing competitor is Maximum Marginal Value Item Pricing, from False-name-proofness with bid withdrawal. It is provably robust to free withdrawal, so it needs no penalty and keeps every honest exit. Alongside it we run the Set protocol (all items sold as one bundle by second-price auction) and the Minimal Bundle protocol (A New Strategy-Proof Greedy-Allocation Combinatorial Auction Protocol and Its Extension to Open Ascending Auction Protocol), both also robust to free withdrawal. No reported welfare result was found on Lacuna for Maximum Marginal Value Item Pricing, Minimal Bundle, or Leveled Division Set against the Set protocol; the last is only described qualitatively as better on complementary goods. The one hard number available is the Bayesian Vickrey–Clarke–Groves result: 100% social welfare efficiency under truthful equilibrium when $q$ exceeds $q^* = 2/3$ for two bidders, or $q^* = 1/2$ for three or more bidders with uniform values (VCG under Sybil (False-Name) Attacks - A Bayesian Analysis). Vickrey–Clarke–Groves with penalty $\gamma$ is therefore the baseline in that model, and $\gamma = 0$ must reproduce those thresholds.

Every mechanism runs on identical instance sets and identical outside-opportunity draws. Each is evaluated against the same exact best-response attacker, computed by enumeration rather than a tuned heuristic, so no mechanism benefits from a weaker attacker. Where a mechanism has free parameters (reserve prices for Leveled Division Set, item prices for Maximum Marginal Value Item Pricing), each gets the same grid-search budget. The proposal beats the field if penalized Leveled Division Set, at its own $\gamma^*$, achieves higher expected welfare than Maximum Marginal Value Item Pricing with free withdrawal while the attacker earns zero rent. It must do so on a non-trivial share of distributions, specifically those with complementary goods, where Leveled Division Set's bundling should matter.

Two ablations isolate the key ingredients. The first routes the penalty to the next recipient of the item instead of the seller, which tests the routing claim. The second compares the penalty schedules from the contracting literature: fixed amount, percentage of price, and penalty growing with time since contracting. The point is to see whether $\gamma^*$ depends on how the penalty is indexed.

Why not just…?

Why not just make all wins binding? This kills the withdrawal attack outright, and when post-auction outside opportunities are rare it may be the right answer. That is a real threat. The contracting literature shows binding deals can be strictly worse, and sometimes no binding deal is acceptable to both sides (Advantages of a Leveled Commitment Contracting Protocol). Whether that matters here is an empirical question. Experiment 3 sweeps the arrival rate of outside opportunities, and we will report the rate below which full commitment ties or wins.

Why not just use Maximum Marginal Value Item Pricing, which already survives free withdrawal? If its welfare matches penalized Leveled Division Set, the mechanism-design part of this proposal is moot, and only the theory of $\gamma^*$ and routing remains. We have no published welfare numbers either way. Maximum Marginal Value Item Pricing prices items one at a time and coincides with Vickrey–Clarke–Groves only for additive values, so we expect it to lose ground when goods are strong complements. Experiment 3 decides this directly, and a loss will be reported as a loss.

Why not just verify identities? In open agent marketplaces, verification is often impractical or privacy-violating, and the cost of defeating checks like CAPTCHAs keeps falling (Using Mechanism Design to Prevent False-Name Manipulations). Verification also does nothing about honest-exit efficiency, which is the other half of the trade-off.

Why not just use bid bonds? A forfeited deposit is a penalty, so this is the proposal, not an alternative. The open question is how large it must be, and Holland and O'Sullivan never calibrate it against fake identities.

Proposed Experiments

Experiment 1 computes exact $\gamma^*$ for Leveled Division Set and Vickrey–Clarke–Groves. It uses discretized two- and three-item instances with three to four bidders under single-minded, additive, and complementary valuations, solved by enumeration and linear programming in the Guo–Conitzer style. Outputs are the worst-case $\gamma^*$, the expected attack rent as a function of $\gamma$, and a numerical check that the $\gamma = 1$ bound holds and fails exactly under same-run reallocation.

Experiment 2 works in the two-identical-item Bayesian model, using the cylindrical-algebraic-decomposition approach of Gafni et al. to compute $\gamma^*(q)$. The decisive sanity check is that $\gamma^*$ reaches zero at $q = 2/3$ for $n = 2$ and at $q = 1/2$ for uniform values with $n \ge 3$.

Experiment 3 measures expected welfare and seller revenue, net of best-response attacks, for all baselines across arrival rates of outside opportunities. Honest exit decisions follow the threshold rule from Algorithms for Optimizing Leveled Commitment.

The decisive outcomes come from Experiments 1 and 3. If $\gamma^*$ for Leveled Division Set sits below about 0.25 on typical distributions, and penalized Leveled Division Set beats Maximum Marginal Value Item Pricing on complementary goods, penalties are a practical defense. If $\gamma^*$ clusters near 1, the conclusion is negative but useful: exit penalties cannot repair a mechanism that breaks under withdrawal. As a scaling probe, learned attackers trained with the reinforcement-learning tools of Understanding Iterative Combinatorial Auction Designs via Multi-Agent Reinforcement Learning can test whether the trends hold on four to six items. Without exact best responses, those results are only lower bounds on the attacker's rent.