PaperlayerView exact revision on arXiv

Source-linked AI summary

Sybil-Proofness of Generalized Adaptive Clinching and Implications for Blockchain Mechanism Design

Chengkai Zhang, Yuhao Li, Elaine Shi, Mengqian Zhang, Lirong Xia, Qishen Han

arXiv:2610.36629v1cs.GTecon.TH

TL;DR

The paper asks whether adaptive clinching’s guarantees can survive when bidders split across fake identities, a concern in settings where pseudonyms are cheap. It generalizes adaptive clinching and applies it to AMMs; the resulting mechanism achieves Sybil-robust incentives and weak Pareto optimality under a budget-reporting restriction, while impossibility results delimit those guarantees.

  • Problem

    Whether adaptive-clinching guarantees survive when a bidder can split across fake identities remains open, and pseudonyms are essentially free in blockchain environments.

    Source: §1 · p. 5

  • Method

    The paper generalizes adaptive clinching with a target-based framework and uses it to construct an AMM mechanism with state-dependent supply.

    Source: §1.1 · p. 6

  • Results

    With aggregate same-direction budget overreporting prohibited, an AMM can be individually rational, exactly settled, Sybil-robust, and weakly Pareto optimal for eligible bids.

    Source: §1.1 · p. 6

  • Takeaways & Limitations

    Both restrictions matter: full Pareto optimality is incompatible with Sybil-robust incentives, and permitting aggregate budget overreporting rules out even weak Pareto optimality.

    Source: §1.1 · p. 7

    Without advance escrow of the entire declared budget, budget overreporting can be possible when realized payment remains affordable.

    Source: §7 · p. 47

Abstract

from arXiv · show

The adaptive clinching auction of Dobzinski, Lavi, and Nisan (FOCS'08) is a cornerstone of mechanism design with budget-constrained bidders, and it has since inspired a broad range of extensions to substantially richer market settings. Adaptive clinching enjoys compelling guarantees: it is Pareto optimal, and truthful bidding is a dominant strategy whenever budgets cannot be overreported. In many real-world environments, however, identities are cheap to create, making resilience to Sybil attacks an additional requirement. Whether the guarantees of adaptive clinching survive when a bidder can split its budget across fake identities has remained open. We introduce a generalized framework for adaptive clinching and prove that it satisfies Sybil-robust incentive compatibility: a bidder cannot benefit from splitting into any finite number of identities with arbitrary value reports, provided their aggregate reported budget does not exceed the bidder's enforceable true budget. Sybil resilience thus joins the list of ideal properties of adaptive clinching. Our work is motivated by practical problems in decentralized finance, where automated market makers (AMMs) are among the most widely used applications. We design a new AMM mechanism that extends classical adaptive clinching in two ways: it supports a two-sided market and protects against two-sided strategies, and it allows the supply function to depend on the auction state. Its one-sided special case is captured by our generalized adaptive clinching framework, and our proof techniques show that the full two-sided mechanism simultaneously satisfies Sybil-robust incentive compatibility and a relaxed notion of Pareto optimality. We argue that these guarantees are essentially the best possible via impossibility results. More broadly, our work reveals new connections between classical algorithmic game theory and modern decentralized blockchains.

1 Introduction

AMMs trade from pool inventory at prices set by a public curve, but batch ordering creates opportunities for block builders to profit from users’ trades. The paper develops an adaptive-clinching AMM with Sybil-robust incentives under a budget-reporting restriction, and explains why its efficiency guarantee must be relaxed.

1 Introduction

  • Block builders can sandwich user trades by buying before them and selling afterward, while control over transaction ordering contributes to MEV and centralization concerns.The paper frames Sybil resilience as important because pseudonymous identities are cheap to create.Source: §1 · pp. 4–5

1.1 Our Results and Contributions

  • The proposed AMM is individually rational, exactly settles against the pool, and achieves Sybil-robust incentive compatibility and weak Pareto optimality for eligible bids.The guarantee assumes a trader’s same-direction budgets across Sybil identities do not exceed its true budget.Source: §1.1 · p. 6
  • Both relaxations are necessary: full Pareto optimality remains incompatible with Sybil-robust incentives, while permitting aggregate budget overreporting rules out even weak Pareto optimality.The latter impossibility holds for deterministic AMMs even when deviations replace a single sell-Y report and use no Sybil identities.Source: §1.1 · p. 7
  • The generalized target-based clinching framework extends adaptive clinching to state-dependent supply and captures fixed-supply and exogenous-online-supply auctions.It includes the online-supply mechanism of Goel, Mirrokni, and Paes Leme [GMP13].Source: §1.1 · pp. 7–8
  • The framework also proves Sybil-proofness for fixed-supply adaptive clinching: truthful single-identity participation weakly dominates finite identity splits with arbitrary values and aggregate budgets within the true budget.This strengthens prior incentive analyses that did not establish guarantees against pseudonymous splitting [BCMX10].Source: §1.1 · pp. 7–8

1.2 Additional Related Work

  • Prior Sybil-proof auction work studies settings such as indivisible goods, whereas this paper analyzes divisible goods under budget constraints and provides provable efficiency guarantees under relaxations.The related-work discussion notes that earlier approaches sacrifice efficiency or leave its loss unanalyzed.Source: §1.2 · p. 9
  • Earlier adaptive-clinching extensions generally use exogenous supply; this framework captures AMM supply generated by payments along the pool’s cost curve, with strategic traders on both sides.This distinguishes the setting from Hirai and Sato, whose sellers are truthful and receive at least their reserve prices.Source: §1.2 · pp. 9–10

2 Definitions

This section defines the AMM cost and settlement model, the two-sided strategy space and utilities, and the incentive and welfare properties used in the paper. It also connects Sybil-robust incentive compatibility to a no-free-lunch guarantee.

2.1 AMM Reserve and Cost Curves

  • An admissible AMM has a continuous, strictly decreasing, convex reserve curve, while its signed cost curve maps net X release to Y received.The cost curve can take negative values when the pool absorbs X.Source: §2.1 · p. 11

2.2 AMM Mechanism

  • Two-sided outcomes may match sell-X and sell-Y orders internally, but exact settlement requires every token paid out to come from the opposite side or the pool.The pool's net flows must lie on its reserve curve, with no outside subsidy or discarded tokens.Source: §2.2 · pp. 12–13

2.3 Strategy Space and Utility

  • A trader may split into finite identities and misreport values, but same-direction budgets are capped in aggregate by its true budget; opposite-direction budgets are unrestricted.The mechanism observes reports, not common ownership, and evaluates utility from aggregate net token flows.Source: §2.3 · pp. 13–14

2.4 Desired Properties

  • Sybil-robust incentive compatibility makes truthful reporting optimal against admissible deviations and covers both individual traders and block builders.The builder may have intrinsic value and demand, or may seek risk-free profit.Source: §2.3 · p. 14, §2.4 · p. 15
  • Sybil-robust incentive compatibility implies no free lunch: no subset of identities can gain in one token without losing the other in aggregate.Weak Pareto optimality separately rules out eligible-user improvements through internal trades or same-direction trades with the pool.Source: §2.4 · pp. 15–16

3 Warmup: The One-Sided AMM Clinching Mechanism

The warmup specializes adaptive clinching to sell-Y bids and an ascending price clock. Its state-dependent chord target governs available supply, while continuous clinching, fixed-price events, and termination rules determine the auction path.

3 Warmup: The One-Sided AMM Clinching Mechanism

  • The warmup considers only sell-Y identities, with allocations and payments generated by an ascending price clock starting at the pool's spot price.The one-sided mechanism is presented before the full two-sided mechanism.Source: §3 · p. 17, §3.1 · pp. 17–18

3.1 The One-Sided Model and Feasibility Requirements

  • In the one-sided model, each identity receives X and sells Y within its reported budget, and the pool's net flows must satisfy the specialized feasibility and individual-rationality requirements.The mechanism starts from the spot price and uses the one-sided pool cost curve to characterize supply.Source: §3.1 · pp. 17–18

3.2 State, Chord Target, and Demand

  • The AMM chord target is the rightmost point where the price-p line from the current pool state meets the cost curve; residual supply is the target minus current allocation.Purchases at price p leave the target unchanged while reducing residual supply.Source: §3.2 · pp. 18–19

3.3 Continuous Evolution

  • Between events, only identities at the water level clinch, trading at the clock price while remaining tight at that level.The primitive differential-algebraic conditions determine the continuous path without assuming a trading-rate formula.Source: §3.3 · pp. 19–20

3.4 Fixed-Price Operations and Events

  • At fixed-price events, the mechanism incorporates supply lumps before exits, then either executes a stopping allocation or cancels exiting budgets and restores active identities to the post-event water level.Simultaneous exiting identities receive proportional quantities when stopping allocation is executed.Source: §3.4 · pp. 20–21

3.5 Continuation and Termination

  • The auction continues after the current chord is cleared whenever an active identity remains, and ends on stopping allocation, no active identities, or exhaustion of all effective budgets.At every finite state the target remains below capacity, so clearing a chord alone is not terminal.Source: §3.5 · pp. 21–22

4 Proofs for the One-Sided AMM Clinching Mechanism

This section establishes incentive and welfare properties of the one-sided AMM clinching mechanism, including Sybil-robust incentive compatibility, exact-settlement feasibility, individual rationality, and weak Pareto optimality for eligible bids. It also extends the analysis to admissible target-based mechanisms and verifies that the AMM target fits that framework.

4 Proofs for the One-Sided AMM Clinching Mechanism

  • The generalized proof establishes Sybil-proofness for the classical ordinary adaptive clinching auction [BCMX10] and its exogenous-online-supply version [GMP13], whose targets are constant.The section’s proof also establishes Sybil-robust incentive compatibility and weak Pareto optimality for eligible bids in the AMM mechanism.Source: §4 · p. 22

4.1 Abstract Target-Based Clinching Mechanism

  • The abstract mechanism preserves the clinching rules while allowing an admissible target, including the AMM chord target; admissibility requires partition independence, fixed-price invariance, decreasing targets with mark-to-market gain, clock regularity, and eventual supply release.The target depends on aggregate allocation and payment rather than identity or budget partition.Source: §4.1 · pp. 23–24

4.2 Derived Form of the Continuous Dynamics

  • Fixed-price purchases leave the target and h = B − pS unchanged, while reducing residual supply and effective budget; with one active identity and no residual supply, that identity buys each continuous target increment at its appearance price.After capacity saturation, allocations and payments remain constant, so the continuing tail involves no further trade.Source: §4.2 · pp. 25–26

4.3 The AMM Target Specification Is Admissible

  • If the reserve curve satisfies Theorem 2.1, the AMM chord target is admissible with unattained capacity, and its target-based mechanism recovers the mechanism of Section 3.The derived continuous rates specialize to the AMM target, and a settled state with one active identity follows the generalized marginal-supply path, including linear-piece jumps.Source: §4.3 · pp. 27–28

4.4 Single-Run Structure

  • At event prices, the mechanism processes the full target jump before testing for stopping; if the test fails, it cancels exiting budgets and restores active budgets, while fixed-price purchases preserve the test and a clincher’s exit triggers stopping.Source: §4.4 · p. 28
  • In a continuing run, active budgets do not exceed h, identities that clinch remain clinchers, and no positive effective budget is exhausted.An identity that has never clinched has received no allocation and made no payment.Source: §4.4 · p. 29
  • In a continuing run after price p, identities valued at or below p have zero allocation and payment, while a continuing AMM run with S = 0 and p > p0 has exactly one positive-effective-budget identity.Source: §4.4 · pp. 29–30

4.5 Feasibility and Efficiency

  • Every completed one-sided AMM clinching run is exact-settlement feasible and individually rational on truthful profiles.Exact settlement assigns all pool output and directs all payments into the pool; truthful bidders are charged no more than their reported budgets and buy at prices no higher than their values.Source: §4.5 · pp. 30–31
  • The truthful one-sided AMM clinching outcome is weakly Pareto optimal for eligible bids in the sell-Y direction.The result rules out both Pareto-improving internal trades among eligible users and additional same-direction pool trades.Source: §4.5 · pp. 31–32

4.6 Sybil-Robust Incentive Compatibility

  • Truthful participation as a merged identity weakly dominates every same-direction Sybil strategy in any admissible abstract target-based mechanism.The proof caps Sybil value overreports, then compares merged and Sybil outcomes using mark-to-market gains, group allocation bounds, and outsider accounting.Source: §4.6 · pp. 32–34
  • Capping Sybil value reports at the bidder’s true value weakly increases utility, and current-price charging yields a continuous mark-to-market gain with derivative equal to cumulative allocation almost everywhere.When all identity reports are at most the true value, aggregate true utility equals the group’s mark-to-market gain evaluated at that value.Source: §4.6 · pp. 32–33
  • The one-sided AMM clinching mechanism is exact-settlement feasible, individually rational, weakly Pareto optimal for eligible bids, and Sybil-robust incentive compatible.Source: §4.6 · p. 36

5 Full Two-Sided AMM Clinching Mechanism

The mechanism extends the one-sided AMM clincher to two-sided batches by filling the smaller eligible side at the spot price and using one-sided clinching for the dominant side. Its extended cost curve combines internally matched supply with pool output, and final transfers remain funded and on the reserve curve.

5 Full Two-Sided AMM Clinching Mechanism

  • The mechanism extends the one-sided AMM clincher to batches containing both sell-Y and sell-X bids.The bids retain their earlier definitions for types, eligibility, outcomes, and settlement.Source: §5 · p. 37

5.2 Allocation and Settlement

  • The minority side is filled at the spot price first, supplying initial quantity for a one-sided clinching run on the dominant side.The proof must also handle cross-directional strategies, such as a sell-Y user posting sell-X bids through Sybil identities.Source: §5 · p. 37, §5.2 · pp. 37–38

5.1 Dominant and Minority Sides

  • At the initial spot price, the side with the smaller measured quantity is the minority, and its quantity M is fully matched internally; ties designate sell-X as minority.Either designation in a tie leaves the pool unchanged.Source: §5.1 · p. 37

5.2 Allocation and Settlement

  • Minority-fill proceeds transfer only at final settlement and cannot finance another order in the same batch.Source: §5.2 · p. 37
  • The dominant sell-Y auction treats the first M units as spot-priced minority supply and further output at the original pool cost.This creates a linear segment when M > 0, so the construction does not require strict convexity.Source: §5.2 · p. 37
  • At simultaneous settlement, the pool releases Xf − M and receives Yf − p0M; the transfers are funded and the net pool trade lies on the original reserve curve.Source: §5.2 · p. 38
  • When sell-X is dominant, the construction exchanges asset roles and uses the inverse reserve curve, with initial spot price 1/p0.Source: §5.2 · p. 38

6 Proofs for the Two-Sided AMM Clinching Mechanism

This section proves key properties of the two-sided AMM clinching mechanism, including termination, exact settlement, and individual rationality. It establishes Sybil-robust incentive compatibility against opposite-direction strategies and weak Pareto optimality of the truthful outcome for eligible bids.

6 Proofs for the Two-Sided AMM Clinching Mechanism

  • The proof combines the one-sided terminal certificate with bounds on extra spot-price supply to establish weak Pareto optimality for eligible bids from both sides.Opposite-direction orders can enlarge the fill or change which side is dominant; the initial water level handles the latter case.Source: §6 · p. 39

6.1 Extended Targets, Termination, and Exact Settlement

  • The extended cost curves define admissible one-sided auctions in both directions, so the structural results, exact settlement, terminal certificate, and same-direction Sybil-robustness results apply to each.The sell-Y-dominant curve has unattained capacity M + x0 and initial right derivative p0; the reverse auction has capacity p0M + y0 and initial right derivative 1/p0.Source: §6.1 · p. 39
  • The mechanism terminates, is exact-settlement feasible, and is individually rational; when sell-Y is dominant, final flows follow the extended cost curve after the minority fill.The final allocation satisfies Xf ≥ M and Yf = eCM(Xf) = p0M + C(Xf − M), with 0 ≤ Xf − M < x0.Source: §6.1 · p. 40

6.2 The Initial Fill and the Imbalance

  • The initial water level and imbalance determine a guaranteed allocation at the spot price, bounding how much dominant-side demand can remain unfilled.The pool’s initial linear segment can improve this guarantee, which is used to bound gains from changing which side is the minority.Source: §6.2 · p. 41

6.3 The Value of Additional Spot-Price Supply

  • When opposite-direction identities enlarge the minority fill by E while sell-Y remains dominant, the resulting utility gain cannot exceed the surplus cost of supplying those units at p0.Supplying E units of X costs (V − p0)E in surplus; the proof bounds the gain even though extra supply may change the auction path.Source: §6.3 · pp. 42–43

6.4 Sybil-Robust Incentive Compatibility Across Directions

  • The two-sided AMM clinching mechanism satisfies Sybil-robust incentive compatibility for the full strategy space.The proof handles deviations that preserve or change the dominant side, and extends the sell-Y argument to sell-X by exchanging the assets.Source: §6.4 · p. 44
  • Opposite-direction identities do not help: their delivery costs offset enlarged fills, or conservation forces delivery that offsets any buying-price improvement.Both comparisons value every identity’s trades at the physical trader’s true value; the proof concludes for every true type and the stated net-flow utility functions.Source: §6.4 · p. 45

6.5 Weak Pareto Optimality for Eligible Bids

  • Under truthful reporting, the two-sided AMM clinching outcome is weakly Pareto optimal for eligible bids.For internal trades, a cutoff λ bounds what users paying Y can give for X and what users supplying X require in Y; conservation forces equality, leaving utilities unchanged.Source: §6.5 · p. 46
  • Permitted same-direction pool trades cannot improve users’ utility: dominant users face marginal costs at least their values, while minority users have spent their endowments.The proof checks both dominant-side cases and concludes that no user can gain from an additional trade in their own direction.Source: §6.5 · pp. 46–47

7 Impossibility with Budget Overreporting

This section derives constraints on allocations and payments to show that allowing affordable budget overreports makes the desired mechanism properties incompatible, even with two eligible sell-Y users and single-identity deviations. It extends the impossibility to two-sided mechanisms with the four properties and shows that an aggregate true-budget cap excludes the deviations used in the contradiction.

7 Impossibility with Budget Overreporting

  • No deterministic mechanism for two eligible sell-Y users can satisfy individual rationality, exact settlement, both weak Pareto clauses, and incentive compatibility against affordable single-identity budget and value misreports.The impossibility holds without assuming symmetry or resistance to Sybil or opposite-direction deviations; it already applies when a user only replaces one sell-Y report with another.Source: §7 · p. 47

7.1 Normalization and Basic Consequences

  • Weak Pareto optimality gives a higher-valued user with unspent budget strict priority, while fixed-budget value incentive compatibility yields nondecreasing allocations and payments and continuous, convex, nonnegative utility.The fixed-budget Myerson lemma also supplies the payment identity used in the proof.Source: §7.1 · pp. 48–49
  • A spot-value user receives nothing, and every eligible user's allocation is at most its payment.The sole-user allocation is the pool optimum; the payment bound also implies that a user paying zero receives zero.Source: §7.1 · pp. 49–50

7.2 Two Large-Budget Comparisons

  • With a large budget on the lower-valued user, the higher-valued user spends its full budget at the lower value, while the lower-valued user earns strictly positive utility and its payment remains bounded.The lower user's payment is bounded regardless of how large its declared budget is.Source: §7.2 · pp. 51–52
  • With a large budget on the higher-valued user, the lower-valued user receives nothing and the higher-valued user effectively trades alone against the pool, subject to a minimum purchase.Incentive compatibility keeps the resulting overpayment small when the lower-valued user's budget is small.Source: §7.2 · p. 52

7.3 The Contradiction

  • In the contradiction, one user's affordable overreport guarantees utility 1 and the other's guarantees strictly positive utility, exceeding the batch's available surplus.Incentive compatibility would require the truthful outcome to provide both guarantees, which is impossible given the available surplus.Source: §7.3 · p. 53
  • User 2 can overreport its budget, obtain strictly positive utility, and pay an amount within its true budget, improving on truthful utility of zero.The deviation reports (V2, Qlarge) while user 1 remains at (V1, Q1).Source: §7.3 · p. 54
  • Both final budget overreports keep values truthful and payments within true budgets, yet declared budgets can influence priority and allocation.The obstruction remains even when the mechanism never collects the overstated budget portion.Source: §7.3 · p. 54
  • Any two-sided mechanism with the same four properties would contradict Theorem 7.1 when restricted to the two sell-Y profiles.The aggregate true-budget cap in Theorem 2.4 excludes the two fatal deviations.Source: §7.3 · p. 54

A Fixed and Online Supply as Constant Targets

The target-based clinching framework captures both fixed divisible supply and exogenous online supply as special cases. For fixed supply, its rules reproduce the classical adaptive clinching auction apart from boundary conventions.

A Fixed and Online Supply as Constant Targets

A.1 Fixed Divisible Supply

The appendix shows that a constant target recovers the adaptive clinching auction for fixed divisible supply. It identifies how the rules correspond and clarifies the effects of the initial clock price and simultaneous exits.

A.1 Fixed Divisible Supply

  • The constant-target specification is admissible, with zero clock rate and an initial supply lump of s at p⋆.The target is s throughout its domain, independent of price and auction state.Source: §A.1 · p. 60
  • The target-based mechanism for constant target s is the adaptive clinching auction for supply s, with its clock started at p⋆.The whole supply is released at p⋆; identities with value below p⋆ are ineligible.Source: §A.1 · pp. 60–61
  • Between events, only clinching identities trade, at the classical clinching rates; nonstopping exits trigger the classical one-shot clinch.Supply remains positive between events.Source: §A.1 · p. 61
  • At stopping, active identities receive full demand and the remainder L is divided among exiting identities; L is zero unless at least two exit together and can afford it.The stopping allocation sells the entire residual supply.Source: §A.1 · pp. 59, 61
  • Capacity is saturated at a nonstopping event only when a single active identity buys all residual supply, after which a zero-trade tail completes the run.Outside that tail, at least two identities remain active whenever the run continues.Source: §A.1 · pp. 61–62
  • At simultaneous stopping exits, the classical auction's fixed-order allocation can differ from the target-based mechanism's proportional division of L.The two agree whenever no two identities exit at the stopping price.Source: §A.1 · p. 62
  • The positive start price acts as a reserve price and is visible for a sole identity with positive value and budget.That identity receives min{s, qi/p⋆} units at unit price p⋆, tending to the whole supply at zero payment as p⋆ decreases to zero.Source: §A.1 · pp. 62–63
  • For profiles with at least two positive-value, positive-budget identities, every sufficiently small positive p⋆ yields the same outcome as the zero-start auction.The equivalence holds profile by profile and simultaneously on any finite family of profiles.Source: §A.1 · pp. 62–63

A.2 Exogenous Online Supply

Exogenous online supply can be represented as a family of constant-target mechanisms, one for each supply prefix. The appendix distinguishes this repeated-run model from a single clock whose target changes over time.

A.2 Exogenous Online Supply

  • The exogenous supply path may be deterministic, random, or adversarial, but it does not depend on reports, which are fixed before the first step.At each step the auctioneer knows only the cumulative supply revealed so far.Source: §A.2 · p. 63
  • For each positive supply prefix st, the cumulative online adaptive-clinching outcome equals the target-based mechanism for constant target st, with the clock started at p⋆.When st is zero, the cumulative outcome is zero.Source: §A.2 · p. 63
  • The supply path is exogenous, so each prefix description is common to all bid profiles and supplies the same target and capacity across profiles.This shared environment description supports comparisons between merged and Sybil runs.Source: §A.2 · p. 64
  • Online adaptive clinching runs the clock afresh from p⋆ against each prefix's constant supply; it does not pause and resume one ascending clock as supply arrives.The online step and clock price are different time axes.Source: §A.2 · p. 64
  • A separate clock-indexed release schedule allows supply to arrive during one run, with clinching rate γ = S + ps′(p) and waiting while s(p) = X.This variant illustrates clock-dependent target data and is not the online model in which each prefix is settled by a fresh run.Source: §A.2 · p. 64

A.3 Incentives for Fixed and Online Supply

For fixed and exogenous online supply, the appendix applies the incentive theorem to show that truthful merged participation weakly dominates same-direction Sybil strategies. The conclusion also holds for classical zero-start auctions under the stated tie rule.

A.3 Incentives for Fixed and Online Supply

  • For fixed supply, truthful participation as the merged identity (V, Q), with V ≥ p⋆, weakly dominates every same-direction Sybil strategy.The same conclusion holds for each positive prefix of an exogenous online supply path in cumulative utility.Source: §A.3 · p. 65
  • The incentive guarantee also holds for classical zero-start auctions when tied stopping exits use the simultaneous proportional rule.Source: §A.3 · p. 65

Related papers

Loading 2610.36629v1…