PaperlayerView exact revision on arXiv

Source-linked AI summary

Credible AUctions via MPC Gadgets: Bounding Information Leakage Under Abort

Matheus Venturyne Xavier Ferreira

arXiv:2609.27402v1cs.GTcs.CRecon.TH

TL;DR

Credible auctions face an abort asymmetry: an auctioneer with shill bidders may learn information and abort, while heavy-tailed valuations can defeat finite penalties. The SRA restricts MPC to revealing the winner’s identity and combines sequential revelation with penalties, achieving credibility for product distributions with vanishing revenue tails.

  • Problem

    Monolithic MPC can let an auctioneer with shill bidders learn its output and abort before honest parties receive theirs, while heavy-tailed distributions can make finite ex-ante penalties insufficient.

    Source: §1 · p. 3

  • Method

    The SRA uses a minimal MPC gadget to reveal only the winner’s identity, then applies sequential revelation and economic penalties.

    Source: §1 · pp. 3–4, §1.1 · p. 4

  • Results

    κ ≥ ∑_{i=1}^n Rev(F_i) is sufficient and tight for SRA credibility; every smaller penalty admits a profitable deviation for sufficiently large truncated equal-revenue distributions.

    Source: §9 · p. 31

  • Takeaways & Limitations

    The SRA achieves credibility for product distributions with vanishing revenue tails using a finite penalty bounded by the sum of bidders’ optimal revenues.

    Source: §9 · p. 31

    Constant-round MPC with identifiable abort is currently impractical, so the SRA is a feasibility result rather than a deployable protocol.

    Source: §9 · p. 31

Abstract

from arXiv · show

The design of credible auctions---mechanisms where a revenue-maximizing auctioneer has no incentive to deviate from the protocol---faces a fundamental cryptographic barrier when the auctioneer controls shill bidders. While a natural approach is to use Secure Multi-Party Computation (MPC) to remove the trusted auctioneer, the impossibility of fair coin flipping of Cleve (1986) implies that monolithic MPC protocols grant the auctioneer a "free option": they can learn the auction's outcome and unilaterally abort if the revenue is unsatisfactory. Cryptographic commitments with ex-ante penalties mitigate this abort asymmetry, but no finite penalty suffices for heavy-tailed distributions. We circumvent this barrier by introducing the MPC Decomposition Principle. Rather than encrypting the entire mechanism, we use MPC strictly as an information-restriction tool. We isolate the winner determination problem into a minimal MPC gadget that computes and reveals the winner's identity but no payment information. This qualitative restriction mathematically bounds the information leaked upon an abort. By combining this gadget with sequential revelation and finite economic penalties, we design the Sequential Revelation Auction (SRA). We prove that bounding the information leakage strictly bounds the value of the free option, showing that a penalty of $k \geq \sum_{i=1}^n Rev(F_i)$ is sufficient for credibility, and tight: for equal-revenue distributions, every smaller penalty admits a profitable deviation. Using constant-round MPC, the SRA resolves an open question of Akbarpour and Li (2020) and Ferreira and Weinberg (2020) by providing a constant-round, incentive-compatible, revenue-optimal credible auction for all product distributions with vanishing revenue tails

1 Introduction

Credible auctions must deter an auctioneer who can profit from undetectable deviations, but cryptographic approaches face abort-based information advantages. The SRA limits what an abort reveals by using MPC only for winner determination, then applies sequential revelation and penalties.

1 Introduction

  • Monolithic MPC gives an auctioneer a free option to observe provisional revenue and abort, while heavy-tailed valuations can make commitment-based abort penalties insufficient.In the Deferred Revelation Auction, a shill can wait for honest bidders to reveal valuations and then refuse to open its commitment.Source: §1 · p. 3

1.1 Technical Overview

  • The Winner Determination Gadget reveals only the winner’s identity; sequential revelation and a penalty κ ≥ sum_i Rev(F_i) bound the value of an abort.The auctioneer’s shill bids are ordered, and the proof reduces adaptive strategies to threshold strategies that account for information leaked at each abort.Source: §1.1 · p. 4, §1 · p. 4

1.2 Our Contribution

  • The MPC Decomposition Principle computes only winner determination inside MPC and determines payments outside it through sequential revelation.For credibility, minimizing the computed function matters more than encrypting the entire mechanism.Source: §1.2 · pp. 4–5
  • The SRA is revenue-optimal, incentive-compatible, and credible for product distributions with vanishing revenue tails when κ ≥ sum_i Rev(F_i).The penalty bound is tight for sufficiently large truncated equal-revenue distributions, and the protocol has constant rounds on the equilibrium path.Source: §1.2 · p. 5
  • For sufficiently large truncations of equal-revenue distributions, every penalty below sum_i Rev(F_i) admits a profitable deviation.The SRA’s equilibrium-path round complexity is constant, and its guarantee covers independent, non-identical distributions.Source: §1.2 · p. 5

1.3 Related Work

  • The SRA provides constant equilibrium-path rounds and handles independent, non-identical distributions, unlike prior general-credibility guarantees limited to i.i.d. bidders or expected-round bounds.Its worst-case round complexity remains unbounded and grows linearly with the number of bidders who abort.Source: §1.2 · p. 5, §1.3 · p. 6

1.4 Paper Organization

  • The paper proceeds from the credibility framework and black-box MPC failure to the SRA, leakage bound, general credibility proof, and matching lower bound.It also presents an equal-revenue warmup before proving credibility for every product distribution.Source: §1.4 · p. 7

2 Preliminaries

The preliminaries specify the independent-private-value auction setting and the revenue and incentive concepts used in the paper. They define credibility alongside the cryptographic abort model, where a party may learn its output before aborting and the aborting party is identified.

2 Preliminaries

  • The model has independent, risk-neutral honest bidders with private values and auctioneer-controlled, zero-value shill bidders.Shills share the auctioneer’s revenue-maximizing utility rather than maximizing their own allocation utility.Source: §2 · p. 7
  • A direct-revelation mechanism pairs an allocation rule with payments, and DSIC requires truthful reporting to maximize each honest bidder’s utility.For a single item, the Myerson mechanism allocates to the highest-ranked bidder with nonnegative ironed virtual value and charges a threshold payment.Source: §2 · pp. 7–9

2.1 Credibility

  • The credibility objective maximizes revenue subject to DSIC and the absence of a safe auctioneer deviation whose revenue exceeds honest execution.Deviation revenue subtracts penalties charged to shills; safety against honest abort additionally requires the protocol to continue with revenue at least that of the remaining bidders’ mechanism.Source: §2.1 · p. 10
  • Credibility must coexist with safety against honest abort, since a protocol must remain usable when a participant stops responding.Restarting can create a free option for an auctioneer who learns an outcome before aborting and then retries with that information.Source: §2.1 · p. 10

2.2 Cryptography

  • With identifiable abort, a party may learn its own output and prevent others from learning theirs, while the other parties learn the deviator’s identity.The security model permits the adversary to choose whether to continue after learning its outputs; constant-round protocols are available under standard assumptions and a broadcast channel.Source: §2.2 · p. 12

3 Strawman

The strawman realizes the full Myerson auction in MPC with safety restart, but its output lets an auctioneer exploit aborts to extract bidder surplus. Committing shill bids does not prevent the probing attack.

3 Strawman

  • For every ε > 0, a safe deviation extracts at least v − ε whenever v ≥ r* for a single bidder with a regular, bounded-support distribution.The honest mechanism charges r* when v ≥ r* and otherwise charges nothing.Source: §3 · p. 13
  • A shill can observe a payment that reveals the bidder’s valuation, abort, then use a fresh shill bid in the restart to extract nearly the full valuation.The construction uses two shills and is safe because the bidder’s views are consistent with an honest execution involving an abort.Source: §3 · p. 13
  • The full-outcome MPC functionality exposes the winner and price before honest parties act, making a safety restart a costless option to exploit payment information.Safety restart excludes an aborting party and reruns the auction with the remaining participants.Source: §3 · pp. 12–13
  • Committing shill bids does not stop probing: the auctioneer can commit bids 1 through k and abort shills above the highest honest bid.This probes the honest valuation at no cost.Source: §3 · p. 14
  • The SRA addresses this vulnerability by revealing only winner identity through minimal MPC gadgets and using penalties to deter aborts.Payments are not revealed by the gadget.Source: §3 · p. 14

4 The Protocol

The SRA uses MPC only to determine the provisional winner, then determines payments outside the gadget through sequential revelation. Winner deposits and penalties help make aborting unprofitable while preserving safe continuation.

4 The Protocol

  • The protocol separates winner determination from payment computation: the gadget reveals only the winner’s identity, while committed bids are revealed simultaneously to compute payments outside MPC.This prevents an abort from revealing payment information.Source: §4 · p. 14
  • The Winner Determination Gadget checks commitment openings and computes the allocation from consistent bidder inputs, outputting the winner’s identity if there is one.Parties with inconsistent openings are treated as having contributed no input.Source: §4 · pp. 14–15
  • The winner’s identity is public so the protocol can identify a provisional winner who refuses to reveal and charge a penalty to a named party.The gadget itself does not reveal payments or others’ valuations beyond what the allocation implies.Source: §4 · pp. 14–15
  • In the equal-revenue example, hiding the shill bid r2 restarts the auction with r1 and burns penalty κ; the real bidder then wins and pays 2.On this realization, hiding yields 2 − κ against honest revenue 1, but the ex-ante expected continuation revenue after hiding is at most Rev(F) = 1.Source: §4 · p. 15

4.1 Safety

  • The winner must deposit their valuation before other bidders reveal commitments, preventing the winner from seeing the price before deciding whether to participate.An abort after depositing results in forfeiture of the valuation, which by individual rationality exceeds any possible payment.Source: §4.1 · p. 15

11 else

The protocol preserves the Myerson outcome on surviving bidders after aborts, and its deviation analysis reduces the auctioneer’s choices to structured shill strategies. Under full revelation, the mechanism is DSIC for real bidders, and honest play weakly dominates aborting.

11 else

  • Theorem 4.3 establishes safety: after a non-auctioneer abort, the protocol either restarts with surviving bidders or terminates with revenue at least the Myerson revenue on that set.A WDG abort or inconsistent opening removes the identified party; revelation aborts remove the relevant bidder, while a winner abort after depositing yields revenue equal to their valuation.Source: §11 · p. 17

4.2 Characterizing Deviations

  • The refinement lemma shows that any safe deviation can be replaced by one with weakly greater expected revenue that reveals a shill once any bid has been revealed.Shills can also be relabeled in increasing order of their ironed virtual values.Source: §4.2 · p. 19

4.3 DSIC Property of the SRA

  • If all shills are revealed, the deviation is DSIC for real bidders because allocation is monotone and payments are the induced threshold payments.This is the full-revelation case; it does not cover deviations that abort shills.Source: §4.3 · p. 19
  • For any κ > 0, honest play weakly dominates aborting for real bidders at every information set of the protocol.Losers get zero either way if they continue, while a provisional winner’s net payoff is non-negative by individual rationality; aborting forfeits κ.Source: §4.3 · pp. 19–20

5 Example: Equal Revenue Distribution

The equal-revenue distribution is a stress test because it combines a heavy tail with identical expected revenue at every reserve. The warmup shows that κ ≥ 1 bounds expected revenue for a natural class of shill strategies.

5 Example: Equal Revenue Distribution

  • The distribution has a polynomial tail P[v > t] = 1/t and equal expected revenue r · P[v ≥ r] = 1 for every reserve r.The heavy tail permits high valuations to occur with probability decaying only polynomially.Source: §5 · p. 20
  • κ ≥ 1 bounds expected revenue at 1 for the warmup’s threshold shill strategies under the equal-revenue distribution.The auctioneer hides higher shills when the bidder’s valuation falls below their bids.Source: §5 · p. 20
  • The warmup bounds revenue by decomposing it into gross payments and penalties; the gross payment terms telescope, and penalties are non-decreasing in κ.The analysis uses the probabilities of valuation intervals and of each shill winning.Source: §5 · pp. 20–21

6 Bounding Information Leakage Under Abort

Conditioning on an abort event can make expected revenue exceed expected virtual surplus because integration by parts leaves nonzero boundary terms. The Information Leakage Lemma bounds this excess by the sum of bidders’ optimal monopoly revenues.

6 Bounding Information Leakage Under Abort

  • Conditioning on the event that no real bidder outranks a shill can make expected revenue exceed expected virtual surplus because integration-by-parts boundary terms no longer vanish.The lemma analyzes this conditional event for continuation mechanisms formed by the Myerson auction with a price floor.Source: §6 · pp. 21–22
  • The excess conditional revenue, or information leakage, is bounded by the sum of bidders’ optimal monopoly revenues, ∑_i Rev(F_i).Rev(F_i) is the expected revenue of the optimal monopoly posted price for bidder i’s distribution.Source: §6 · pp. 21, 23, 24
  • The proof expresses truncated revenue as truncated ironed virtual surplus plus one boundary term per bidder, then bounds each term by that bidder’s monopoly revenue.This uses integration by parts and an ironing equivalence on the truncated domain, with the threshold outside the interior of any ironed interval.Source: §6 · pp. 22–24
  • The bound applies to continuation mechanisms that rank by the paper’s ironed-bid ranking and use DSIC threshold payments, including those with higher price floors.The proof argues that the relevant allocation is constant on ironed intervals and that a higher floor only lowers the boundary utility being bounded.Source: §6 · pp. 22, 24

7 Sequential Revelation Auction is Credible

The Sequential Revelation Auction is credible when its abort penalty covers the sum of bidders’ monopoly revenues. Its proof reduces deviations to finitely many deterministic cases and shows that the penalty offsets the bounded leakage from each abort.

7 Sequential Revelation Auction is Credible

  • The auctioneer’s commitment-versus-free-option trade-off is bounded: hiding a shill permits a restart, but its option value is at most ∑_j Rev(F_j).Revealing a shill commits the auctioneer to a fixed price floor.Source: §7 · p. 25

7.1 Bounding Refined Deviations

  • A refined deviation orders shills by the ranking and processes them from highest to lowest; each deterministic case reveals one shill and aborts all higher shills.The cases include C0, which aborts all shills, and each case’s expected net revenue is at most optimal revenue when the penalty meets the bound.Source: §7.1 · p. 26
  • Any adaptive strategy is bounded by the best of k + 1 deterministic cases, and each abort’s leakage is offset by forfeited collateral when κ ≥ ∑_i Rev(F_i).Kuhn’s theorem reduces behavioral strategies to mixtures of pure strategies, and the refined strategy outcomes correspond to the deterministic cases.Source: §7 · p. 25, §7.1 · pp. 27–28

7 Sequential Revelation Auction is Credible

  • For product distributions with densities and vanishing revenue tails, the SRA is credible at penalty κ ≥ ∑_i Rev(F_i), implements the revenue-optimal auction, and terminates in a constant number of equilibrium-path rounds.The constant-round claim is for the path without shills or winner aborts.Source: §7 · p. 25, §7.1 · pp. 28–29

8 Lower Bound

The penalty threshold is tight: for every κ < n, some truncated equal-revenue instance admits a profitable safe deviation. Exponentially spaced shills make the deviation’s expected net revenue exceed the honest revenue for sufficiently large truncation.

8 Lower Bound

  • The equal-revenue distribution itself lacks a vanishing revenue tail, so the lower bound uses a truncated version that satisfies the theorem’s assumptions.The truncated distribution has monopoly revenue 1 and tail probability 1/y for y ≤ H.Source: §8 · p. 29
  • For every n ≥ 1 and κ < n, sufficiently large truncations of the equal-revenue distribution admit a safe deviation earning more than n, making κ ≥ ∑_i Rev(F_i) tight.Each bidder’s monopoly revenue is 1 in this family, so the honest optimal revenue is at most n.Source: §8 · p. 29
  • Exponentially growing shill bids yield positive marginal gains from some index onward when κ < n, so enough shills make the deviation’s expected profit exceed n.The construction chooses r_j = α^j and obtains a positive lower bound on later marginal gains.Source: §8 · pp. 30–31

9 Conclusion

The SRA combines a winner-only MPC gadget, sequential revelation, and penalties to achieve credibility for product distributions with vanishing revenue tails. Its penalty bound is sufficient and tight, while the conclusion identifies scope and implementation limits.

9 Conclusion

  • κ ≥ sum_i Rev(F_i) is sufficient for SRA credibility and tight: every smaller penalty admits a profitable deviation for sufficiently large truncated equal-revenue distributions.The gadget reveals only winner identity, not payment information.Source: §9 · p. 31
  • The analysis assumes independent private values and a static adversary; correlation breaks both Myerson’s benchmark and the leakage bound, while repeated auctions remain outside scope.The repeated-auction setting is excluded because the auctioneer’s information advantage compounds across rounds.Source: §9 · p. 31
  • The round bound is deterministic only on the equilibrium path; unlike Essaidi et al. (2022), the SRA does not improve worst-case rounds, which grow linearly with aborts.The SRA does provide a deterministic on-path bound and supports non-identical distributions.Source: §9 · p. 31
  • Whether richer gadgets or another revelation order can achieve credibility with smaller penalties remains open, as does tightening the constant in Opt(F) ≤ κ ≤ n · Opt(F).Source: §9 · p. 31
  • Current constant-round MPC with identifiable abort from MK-FHE or iO is impractical, though the gadget evaluates one O(nℓ) arg max rather than a full Myerson circuit.The SRA is therefore a feasibility result rather than a deployable protocol.Source: §9 · p. 31
Loading 2609.27402v1…