betaFeedback

WorksComputer Science

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

Abstract

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.

Introduction

Automated Market Makers (AMMs) are arguably the most widely used application in decentralized finance (DeFi). An AMM is a smart contract that stands ready to trade with anyone: rather than matching buyers against sellers through an order book, it holds an inventory of assets and quotes an exchange rate determined by a publicly known pricing curve. By far the most common deployment is the two-asset AMM, exemplified by Uniswap [45].

In a typical two-asset AMM, users trade one of two assets, denoted XX and YY, against a smart contract, which we henceforth also refer to as the pool. Initially, the state of the pool is denoted by (x0,y0)(x_0,y_0), meaning that the pool holds x0x_0 units of XX and y0y_0 units of YY. The exchange rate for each trade is determined by a predefined pricing curve. For example, the widely adopted constant-product rule requires

(x0−x)(y0+y)=C(x_0-x)(y_0+y)=C

for some positive constant CC. Thus, starting from state (x0,y0)(x_0,y_0), a user who contributes yy units of YY to the pool receives xx units of XX. Following the trade, the pool transitions to state (x0−x,y0+y)(x_0-x,y_0+y), preserving the invariant that the product of the reserves remains equal to CC.

Widespread incentive attacks. Because the price a user receives depends on the pool state when its trade executes, and that state is moved by every preceding trade in the same block, an AMM is acutely sensitive to who controls the contents and the ordering of a block. A block builder can exploit this directly. Suppose a user submits an order to buy XX with YY. Immediately before that order, the builder buys XX cheaply for itself, driving the price up to the user’s declared slippage tolerance—the worst price at which it is still willing to trade. The user’s order then executes at that price and pushes the price higher still, and the builder sells immediately after it. The builder has thus bought low and sold high within a single block, at essentially no risk, since it sees the user’s order before committing to either leg. The two legs are known respectively as front-running and back-running, and the pair as a sandwich attack; a substantial body of work [50, 39, 29] documents how prevalent and how profitable such attacks are in practice.

Such incentive attacks are commonly referred to as Miner (or Maximum) Extractable Value (MEV), and the harm they do extends well beyond the users who are sandwiched. Because the profit accrues to whoever controls the contents and ordering of a block, MEV fosters opaque off-chain markets in which block builders, traders, and specialized searchers compete to identify and exploit these opportunities, and it rewards most those participants with the best access to order flow and the deepest capital. These forces push the ecosystem steadily toward centralization. Indeed, a recent measurement study by Yang et al. [47] found that the top two block builders produce more than 85% of Ethereum blocks, severely undermining the decentralized vision of blockchain systems.

A theory on AMM mechanism design. Motivated by these attacks, a line of work [12, 35, 44] has formulated AMM as a mechanism-design problem. In this formulation, the AMM mechanism receives a batch of bids (typically all trade requests contained in one block). It then decides, for every bid, how much of each asset that bid sends and receives. Each bid comes in one of two directions. A sell-Y bid specifies a value vv and a budget QQ, meaning that it wants to buy XX using at most QQ units of YY, and that it values each unit of XX it acquires at vv units of YY. A sell-X bid is defined symmetrically.

Two structural features distinguish the problem from traditional auctions. First, the market is two-sided: a batch may contain both sell-X and sell-Y bids, which can trade with each other as well as with the pool. Second, the mechanism must exactly settle: every token paid out is funded either by an opposite-side bid or by the pool, no outside subsidy is used, no token is discarded, and the end state of the pool lands back on the prescribed pricing curve.

Within this formulation, one may ask for a dream AMM mechanism, namely one that simultaneously achieves the following two desiderata.

  1. Sybil-robust incentive compatibility. The mechanism should encourage truthful bidding by an individual trader, and it should moreover be strategy-proof against a block builder who may itself be a trader with intrinsic value and demand. Concretely, a trader or builder can misreport both its value and its budget, and can inject any finite number of fake bids under pseudonymous identities, carrying arbitrary values and budgets. Further, a builder can arbitrarily sequence the bids contained in the batch. We refer to the resulting incentive notion as Sybil-robust incentive compatibility. We stress that Sybil-robustness is critical in blockchain environments since creating arbitrary pseudonyms is essentially free.

  1. Pareto optimality. The outcome should be Pareto optimal: no incremental trade among a subset of traders can make some of them better off without making any of them worse off, and no trader can improve its own utility by trading further with the pool.

Throughout the paper, we assume that a strategic builder cannot censor other traders’ bids, meaning that every submitted bid must be included in the mechanism’s input. This matches the usual assumption in classical mechanism design: a strategic participant may manipulate its own reports, or even inject fake bids (Sybil attacks), but cannot suppress the reports submitted by other participants. In practice, this is ensured in blockchain systems when the underlying consensus protocol provides censorship resilience [2, 19, 25], a guarantee that major blockchain projects such as Ethereum are committed to offering at the consensus layer [19]. Such an assumption is also unavoidable: it is known that once censorship is admissible, Sybil-robust incentive compatibility is unattainable in AMM mechanism design even without imposing any efficiency requirement [44].

Impossibility of a dream AMM mechanism. Unfortunately, such a dream AMM mechanism is unattainable. Shi et al. [44] and Li et al. [35] show that Pareto optimality and Sybil-robust incentive compatibility are mutually incompatible for exact-settlement AMM mechanisms. Further, this impossibility holds in a very strong sense, even when the strategy space consists only of single-identity valuation misreports, and even if the mechanism additionally has access to unfor geable auxiliary information attached to each bid (e.g., trusted timestamps on transactions determined by a decentralized sequencer [13 KZ​GJ20, 30, 31, 32 ZSC+20]).

Our Results and Contributions

In this paper we identify two natural relaxations of the dream specification under which feasibility is restored, and we present an AMM adaptive clinching mechanism that attains it. Both relaxations are needed: neither one on its own restores feasibility, as we explain later in this section, after stating our main feasibility result.

  1. No aggregate budget overreporting. Our first relaxation restricts the strategy space. A trader may still split itself into arbitrarily many pseudonymous identities and report arbitrary values, but the budgets that its identities declare in its own trading direction must sum to at most its true budget. No restriction whatsoever is placed on the budgets that it declares in the opposite direction: a trader who genuinely wishes to sell YY may inject sell-XX identities carrying arbitrary finite budgets.

This assumption is well motivated, because a declared budget must be backed by escrowed funds, and that escrow cannot be replenished out of a sibling identity’s proceeds during the batch. A trader whose identities collectively declare more than it owns would therefore have to fund the excess up front, which by definition it cannot do. In practice a trader is of course escrow-limited on the opposite side as well, but our guarantees do not need this: they hold even against a deviator that can escrow arbitrarily large opposite-direction budgets.

  1. Weak Pareto optimality. Our second relaxation weakens the efficiency requirement to weak Pareto optimality for eligible bids, a notion suggested by Li et al. [35] and Shi et al. [44] for overcoming impossibilities pertaining to full Pareto optimality. A bid is eligible if it is willing to trade at the pool’s initial spot price. We require that, under truthful reporting, (a) no subset of eligible traders can re-trade among themselves, subject to their post-batch holdings, in a way that Pareto improves their joint utilities; and (b) no eligible trader can strictly improve its utility by making an additional trade with the pool in the direction of its own type—a trader who came to sell YY may only sell more YY.

Intuitively, the impossibility results of Li et al. [35] and Shi et al. [44] suggest that incentive compatibility is easier to achieve if the mechanism can raise the price as competition for the pool’s output intensifies, and close the batch at a marginal price exceeding the values of the traders it has served — provided that the average price each trader actually pays remains below its value. Weak Pareto optimality opens up our design space in this direction, by not counting such reverse-direction trades with the pool as Pareto improvements.

Our main result. Under these two relaxations, we obtain the following.

Theorem 1.1 (Sybil-robust and weakly Pareto optimal AMM). Assume that a strategic trader cannot overreport its budget in aggregate across the Sybil identities it submits in its own trading direction. Then there exists an AMM mechanism that is individually rational, exactly settles against the pool, and simultaneously satisfies Sybil-robust incentive compatibility and weak Pareto optimality for eligible bids.

As argued below, both relaxations are necessary to obtain Theorem 1.1, thus the combination of properties we achieve is essentially best possible. Moreover, as discussed later in this section, the techniques used to achieve Theorem 1.1 reveal exciting connections to classical algorithmic game theory.

Necessity of both relaxations. Both relaxations are necessary. If one insists on full Pareto optimality, impossibility persists even when aggregate same-direction budget overreporting is prohibited [44].8 Conversely, we prove that if aggregate same-direction budget overreporting is permitted, impossibility persists even after relaxing full Pareto optimality to our weak notion, as stated in the following theorem:

Theorem 1.2 (Impossibility when overreporting budget is permitted). Suppose that traders can arbitrarily misreport their values and budgets. Then, no deterministic AMM mechanism can simultaneously satisfy Sybil-robust incentive compatibility and weak Pareto optimality.

In fact, this impossibility holds in a very strong sense. Its proof needs only deviations that replace a single sell-Y report with another, and does not rely on Sybil identities or opposite-direction orders. Moreover, this impossibility holds even when the mechanism has access to unforgeable auxiliary information attached to each bid.

Zhang et al. [ZXS+26] prove a similar impossibility. In comparison with our Theorem 1.2, their impossibility holds for a much weaker efficiency notion, but it critically relies on the builder’s capabilities to reorder bids within a batch, and it ceases to hold if the underlying consensus can provide trusted timestamps on the submitted bids, e.g., generated by a decentralized sequencer [13, 33, 30, 31, 32 ZSC+20] — indeed, a feasibility result [12] is known in this setting satisfying their weaker efficiency notion.

Connections to classical algorithmic game theory. To obtain Theorem 1.1, we generalize the adaptive clinching auction of Dobzinski, Lavi, and Nisan [16], the classical mechanism for multi-unit auctions with hard budget limits. In the classical setting, a fixed divisible supply is offered to budget-constrained bidders by an ascending price clock, and a bidder clinches a unit precisely when the residual demand of the other bidders no longer covers the remaining supply.

The challenge in our setting is that an AMM has no fixed, exogenous supply: its pricing curve makes the supply available for trade depend on the mechanism’s current state. Our central observation is that adaptive clinching extends to this setting by replacing fixed supply with a carefully chosen state-dependent target.

Our work reveals exciting connections between classical algorithmic game theory (AGT) and modern blockchain mechanism design. On one hand, our results give a compelling demonstration of how classical AGT ideas contribute to the formation of a much needed scientific foundation for incentive-compatible blockchain markets. On the other hand, the proof techniques developed for our AMM setting advance the state-of-the-art understanding of classical AGT — in particular, we show that the fixed-supply adaptive clinching auction of Dobzinski, Lavi, and Nisan [16] satisfies Sybil proofness, as stated in the following theorem.

Theorem 1.3 (Sybil-proofness of fixed-supply adaptive clinching). *In the adaptive clinching auction for a fixed divisible supply, truthful participation as a single identity

weakly dominates every strategy that replaces the bidder with finitely many identities having arbitrary reported values and aggregate declared budget at most the bidder’s true budget.

Theorem 1.3 strengthens the incentive guarantees previously established for adaptive clinching with fixed divisible supply [16, 4]. The previous analyses allow value misreports and, in the case of Bhattacharya et al. [4], budget under-reporting, but do not prove any guarantees in the presence of pseudonymous splitting.

The fixed-supply auction is not obtained directly as a special case of our AMM mechanism. Instead, our proofs introduce an abstract target-based clinching framework that embodies both mechanisms as special cases. We establish Sybil-robust incentive compatibility at this abstract level, thus extending the guarantees to any auction that falls within this target-based clinching framework. This new framework, which can be viewed as a generalization of the ordinary adaptive clinching, may be of independent interest. For example, to demonstrate its usefulness, we show that the framework also captures the adaptive clinching mechanism with exogenous online supply introduced by Goel, Mirrokni, and Paes Leme [23], yielding the following consequence:

Theorem 1.4 (Sybil-proofness with exogenous online supply). At every positive-supply step of the adaptive clinching mechanism with an exogenous online supply path, truthful participation as a single identity weakly dominates, in cumulative utility, every strategy that replaces the bidder with finitely many identities having arbitrary reported values and aggregate declared budget at most the bidder’s true budget.

Additional Related Work

AMM mechanism design. Our study builds directly on the AMM mechanism-design framework introduced by Chan et al. [12]. They also construct a Sybil-robust incentive-compatible mechanism, but their result has two limitations. First, their mechanism does not achieve weak Pareto optimality (wPO). It instead satisfies weak local efficiency (wLE) for eligible users, which corresponds to only the pool-trade clause of our wPO definition. Theorem 1.2 shows that this loss of efficiency is unavoidable in their strategy space, which permits a trader to overreport its aggregate budget. Second, they require an overly stringent assumption, that the consensus layer assigns a trustworthy arrival time to every bid. Although a line of work [13, 33, 30, 31, 32 ZSC+20] has explored how to provide such a trusted timestamp, existing schemes are known to be manipulatable, e.g., by a client who deliberately creates Condorcet cycles [46].

Subsequent work [35, 44] further delineates the feasibility frontier in this model. Li et al. [35] prove a trilemma among incentive compatibility, weak local efficiency, and uniform pricing: any two of these properties can be achieved, but no mechanism can satisfy all three. Thus, contrary to a common intuition, clearing a batch at a uniform price does not by itself yield strong MEV resilience while preserving even weak local efficiency.

Li et al. [35] and Shi et al. [44] also show that full Pareto optimality is fundamentally incompatible with Sybil-robust incentive compatibility. Shi et al. [44] circumvent this barrier by relaxing exact settlement to permit “burning”. Their model allows the pool to release more units than are allocated to traders, with the surplus diverted for the benefit of the broader community. For example, the surplus can subsidize transaction fees, reward liquidity providers, or be returned to the pool to reduce the price impact of future trades. Under this relaxation, they construct a simple and computationally efficient “dream” AMM that achieves both full Pareto optimality and Sybil-robust incentive compatibility.

Sybil proofness in mechanism design. Sybil-proofness, also known as false-name-proofness, has been studied in a variety of settings, including voting [10, 1], resource exchange [6], and combinatorial auctions [43, 48, 49, 27]. A recurring theme is that auctions that are truthful when identities cannot be faked may cease to be truthful once Sybil attacks are possible; most notably, the VCG mechanism is not false-name-proof in general [43, 49, 21]. To the best of our knowledge, the Sybil resilience of adaptive-clinching-style auctions for divisible goods under budget constraints has not been analyzed before. The closest related works are those of Iwasaki et al. [28] and Sakurai et al. [42]. Both works aim to design Sybil-resilient auctions for indivisible goods. Iwasaki et al. [28] focuses on a setting without budget constraints, and Sakurai et al. [42] considers non-quasi-linear utilities which include budget constraints. Since their settings and auction mechanics are fundamentally different from ours, their Sybil-proofness arguments do not carry over to our setting. Moreover, both Iwasaki et al. [28] and Sakurai et al. [42] sacrifice efficiency to obtain Sybil resilience. In fact, in the setting of Iwasaki et al., Pareto efficiency is known to be incompatible with Sybil-proofness [49]. Thus Iwasaki et al. evaluate efficiency only empirically, through simulations, and Sakurai et al. leave the analysis of efficiency loss to future work. In contrast, we identify meaningful relaxations under which we provide provable efficiency guarantees.

Adaptive clinching and extensions. The original work by Dobzinsi et al. [16] that proposed the adaptive clinching auction assumed that the budgets are public (i.e., unforgeable). The subsequent work of Bhattacharya et al. [4] show that, for a divisible good, underreporting a budget is never profitable, so adaptive clinching is incentive compatible as long as budgets cannot be overreported. It is also known that with private budgets, simultaneously achieving incentive compatibility and Pareto optimality is impossible [16]. Our feasibility and infeasibility pair (Theorem 1.1 and Theorem 1.2) can thus be viewed as AMM analogue of classical budget-constrained auctions of divisible goods.

Adaptive clinching [16] has been extended to polymatroidal environments, including the Adwords polytope for sponsored search with multiple keywords and slots [22], as well as to other sponsored-search and combinatorial settings [CBH15, FLSS11], heterogeneous items [15], two-sided markets [26], online supply [23], and payment constraints more general than hard budgets [24]. Most of these works assume public budgets, and none considers Sybil identities. More fundamentally, in all of them the feasible allocations are fixed exogenously or, with online supply, revealed independently of the bids. In an AMM, the supply is instead created by the very payments the auction collects, along the pool’s cost curve. Our target-based framework captures this endogenous supply, and it recovers fixed and online supply as constant targets (Section A). Our two-sided setting also differs from that of Hirai and Sato [26], whose sellers are assumed to be truthful and are paid at least their reserve prices. In contrast, our pool must receive exactly the amount that returns it to its curve, and traders in both directions are strategic.

Even with public budgets, no deterministic mechanism attains the guarantees of adaptive clinching once identical items may be complements [34], marginal values decrease [22, 5], or items are heterogeneous with multi-dimensional valuations [15]. Another line of work replaces Pareto optimality with approximations of liquid welfare: Dobzinski and Paes Leme [17] show that adaptive clinching 2-approximates it when budgets are public, and Lu and Xiao [36] improve the ratio to (1+5)/2(1+\sqrt{5})/2 with a different auction. Devanur et al. [14] use clinching as a building block for prior-free revenue and welfare guarantees when agents share a common budget. We instead retain an exact, albeit weaker, Pareto guarantee.

Other related work. Ferreira and Parkes [20] suggest having the consensus layer enforce verifiable, application-specific sequencing rules that limit how a block builder may order transactions, and they give such rules for AMMs with weak but provable guarantees against MEV extraction. Their approach has several limitations. First, it places application-specific logic in the consensus layer, a shared infrastructure layer that ought to remain application agnostic. Second, their framework is overly restrictive and requires transactions to be executed one by one in the order in which they appear in the block, thus leading to strong impossibilities. In particular, risk-free profit cannot be eliminated in their model.

Among other work on AMMs, Milionis, Moallemi, and Roughgarden [37] characterize profit-maximizing demand curves for a market maker among those that elicit truthful reports from traders. Since traders in their model trade directly with the market maker, strategic ordering and attacks such as front-running and back-running fall outside its scope. Bartoletti et al. [3] compute a block builder’s optimal MEV-extraction strategy — their goal is to characterize MEV extraction rather than to prevent it.

Batch trading has also been studied as an approach to mitigating MEV. Canidio and Fritsch [7, 8] propose a function-maximizing AMM and analyze the elimination of arbitrage profits under idealized perfect competition among arbitrageurs sharing a common external reference price. CoW Protocol [11] deploys batch trading through competition among solvers. Canidio and Henneke [9] propose fair combinatorial auctions for trade intents, studying the trade-off between execution fairness and total value returned to traders under strategic solver bidding. Ramseyer et al. [41] study equilibrium computation and design trade-offs for batch exchanges incorporating CFMMs. These works do not establish incentive compatibility for finite populations of strategic traders, which is our focus. Within the AMM mechanism-design framework discussed above, Li et al. [35] show that uniform pricing cannot be combined with both incentive compatibility and weak local efficiency.

In a smart-contract implementation, the escrow that prevents budget overreporting must be protected against flash loans [40], which would let a trader borrow funds and repay the loan within the same transaction. The attack can be avoided by splitting execution into two phases: traders escrow their budgets in one block, and the batch is settled in a later block, so that no flash loan can span both.

Definitions

AMM Reserve and Cost Curves

There are two divisible assets, XX and YY. The AMM pool has initial reserves (x0,y0)∈R++2(x_0,y_0) \in\mathbb{R}_{++}^{2}. Its reserve curve is

Rφ:={(x,φ(x)):x>0}.\mathcal{R}_{\varphi} := \{(x,\varphi(x)) : x > 0\}.

During a batch, every pool trade settles on this reserve curve.

Definition 2.1 (Admissible AMM). The AMM is admissible if φ:(0,∞)→(0,∞)\varphi: (0,\infty) \to(0,\infty) is continuous, strictly decreasing, and convex, satisfies

lim⁡x↓0φ(x)=∞,lim⁡x↑∞φ(x)=0,\lim_{x\downarrow0}\varphi(x) = \infty,\qquad\lim_{x\uparrow\infty}\varphi(x) = 0,

and is differentiable at x0x_0, where y0=φ(x0)y_0 = \varphi(x_0). The spot price of one unit of XX, measured in units of YY, is

p0:=−φ′(x0)>0.p_0 := -\varphi'(x_0) > 0.

For a net release z<x0z < x_0 of asset XX, define the signed pool cost

C(z):=φ(x0−z)−y0.C(z) := \varphi(x_0-z)-y_0.

Here z>0z > 0 means that the pool releases zz units of XX, whereas z<0z < 0 means that it absorbs −z-z units. Correspondingly, C(z)C(z) is the net amount of YY received by the pool and may be negative. The function CC is continuous, strictly increasing, and convex, with

C(0)=0,lim⁡z↑x0C(z)=+∞,lim⁡z→−∞C(z)=−y0,C′(0)=p0.C(0)=0,\qquad\lim_{z\uparrow x_0}C(z)=+\infty,\qquad\lim_{z\to-\infty}C(z)=-y_0,\qquad C'(0)=p_0.

Thus sending y≥0y \ge0 units of YY into the pool releases C−1(y)∈[0,x0)C^{-1}(y) \in[0,x_0) units of XX, while sending x≥0x \ge0 units of XX into the pool releases −C(−x)∈[0,y0)-C(-x) \in[0,y_0) units of YY. These two compensation maps are continuous, strictly increasing, and concave. Their initial marginal exchange rates are 1/p01/p_0 and p0p_0, respectively.

Constant product as a special case. If φ(x)=x0y0/x\varphi(x)=x_0y_0/x, then

C(z)=y0zx0−z,C−1(y)=x0yy0+y,−C(−x)=y0xx0+x.C(z)=\frac{y_0z}{x_0-z},\qquad C^{-1}(y)=\frac{x_0y}{y_0+y},\qquad-C(-x)=\frac{y_0x}{x_0+x}.

Consequently p0=y0/x0p_0=y_0/x_0, the first compensation map has initial derivative x0/y0=1/p0x_0/y_0=1/p_0, and the second has initial derivative y0/x0=p0y_0/x_0=p_0. Thus constant product satisfies Theorem 2.1.

AMM Mechanism

A physical trader has one of two types, according to the asset it wishes to sell.

Sell-YY orders. A sell-YY trader kk has true type

(Vk,Qk)∈R≥02,(V_k,Q_k) \in\mathbb{R}_{\ge0}^2,

where VkV_k is its value for one unit of XX, measured in units of YY, and QkQ_k is its true YY-budget. A sell-YY identity ii reports

(vi,qi)∈R≥02,(v_i,q_i) \in\mathbb{R}_{\ge0}^2,

where viv_i has the same units as VkV_k and qiq_i is its declared YY-budget. An outcome for this identity consists of SY,iS_{Y,i} units of YY sold and RX,iR_{X,i} units of XX received, with

0≤SY,i≤qi,RX,i≥0.(1)0 \le S_{Y,i} \le q_i,\qquad R_{X,i} \ge0. \tag*{(1)}

Its surplus evaluated at the report is viRX,i−SY,iv_iR_{X,i}-S_{Y,i}. A single sell-YY report is truthful when (vi,qi)=(Vk,Qk)(v_i,q_i)=(V_k,Q_k).

All values in this paper are denominated in units of YY per unit of XX. Thus VkV_k and viv_i are reciprocals of a positive reservation value for one unit of YY expressed in units of XX. This convention puts both types of values on the same price scale.

Sell-XX orders. A sell-XX trader kk has true type

(Uk,Rk)∈R≥02,(U_k,R_k) \in\mathbb{R}_{\ge0}^2,

References

  1. [1]Haris Aziz, Yoram Bachrach, Edith Elkind, and Mike Paterson. False-name manipulations in weighted voting games. Journal of Artificial Intelligence Research, 40:57–93, 2011.
  2. [2]Ittai Abraham, Yuval Efron, and Ling Ren. The latency cost of censorship resistance. IACR Cryptol. ePrint Arch., 2025:2136, 2025.
  3. [3]Massimo Bartoletti, James Hsin-yu Chiang, and Alberto Lluch Lafuente. Maximizing extractable value from automated market makers. In Financial Cryptography and Data Security: 26th International Conference, FC 2022, Grenada, May 2–6, 2022, Revised Selected Papers, page 3–19, Berlin, Heidelberg, 2022.arxiv.org/abs/2106.01870
  4. [4]Sayan Bhattacharya, Vincent Conitzer, Kamesh Munagala, and Lirong Xia. Incentive compatible budget elicitation in multi-unit auctions. In SODA, pages 554–572, 2010.arxiv.org/abs/0904.3501
  5. [5]Riccardo Colini-Baldeschi, Monika Henzinger, Stefano Leonardi, and Martin Starnberger. On multiple keyword sponsored search auctions with budgets. In Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP), volume 7392 of Lecture Notes in Computer Science, pages 1–12. Springer, 2012.
  6. [6]Yukun Cheng, Xiaotie Deng, Yuhao Li, and Xiang Yan. Tight incentive analysis on sybil attacks to market equilibrium of resource exchange over general networks. In Proceedings of the 23rd ACM Conference on Economics and Computation (EC), pages 792–793, 2022.DOI
  7. [7]Andrea Canidio and Robin Fritsch. Batching trades on automated market makers. In AFT, 2023.
  8. [8]Andrea Canidio and Robin Fritsch. Arbitrageurs’ profits, lvr, and sandwich attacks: batch trading as an amm design response. 2024.arxiv.org/abs/2307.02074
  9. [9]Andrea Canidio and Felix Henneke. Fair combinatorial auction for blockchain trade intents: Being fair without knowing what is fair, 2024.
  10. [10]Vincent Conitzer. Anonymity-proof voting rules. In Internet and Network Economics (WINE), pages 295–306, 2008.
  11. [11]https://cow.fi/cow-protocol.
  12. [12]T-H. Hubert Chan, Ke Wu, and Elaine Shi. Mechanism design for automated market makers. In AFT, 2025.arxiv.org/abs/2402.09357
  13. [13]Challenging periods reimagined: The key role of sequencer decentralization. Ethereum Research.
  14. [14]Nikhil R. Devanur, Bach Q. Ha, and Jason D. Hartline. Prior-free auctions for budgeted agents. In Proceedings of the 14th ACM Conference on Electronic Commerce (EC), pages 287–304, 2013.
  15. [15]Paul Dütting, Monika Henzinger, and Martin Starnberger. Auctions with heterogeneous items and budget limits. In Proceedings of the 8th International Conference on Web and Internet Economics (WINE), volume 7695 of Lecture Notes in Computer Science, pages 44–57. Springer, 2012.arxiv.org/abs/1209.6448
  16. [16]Shahar Dobzinski, Ron Lavi, and Noam Nisan. Multi-unit auctions with budget limits. In Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’08, pages 260–269, USA, 2008. IEEE Computer Society.
  17. [17]Shahar Dobzinski and Renato Paes Leme. Efficiency guarantees in auctions with budgets. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), volume 8572 of Lecture Notes in Computer Science, pages 392–404. Springer, 2014.arxiv.org/abs/1304.7048
  18. [19]Eip-7805: Fork-choice enforced inclusion lists (focil). https://eips.ethereum.org/EIPS/eip-7805.
  19. [20]Matheus Venturyne Xavier Ferreira and David C. Parkes. Credible decentralized exchange design via verifiable sequencing rules. In STOC, 2023.DOI
  20. [21]Yotam Gafni, Ron Lavi, and Moshe Tennenholtz. VCG under sybil (false-name) attacks – A Bayesian analysis. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 1966–1973. AAAI Press, 2020.DOI
  21. [22]Gagan Goel, Vahab Mirrokni, and Renato Paes Leme. Polyhedral clinching auctions and the AdWords polytope. In STOC, 2012.
  22. [23]Gagan Goel, Vahab Mirrokni, and Renato Paes Leme. Clinching auctions with online supply. In SODA, pages 605–619, 2013.
  23. [24]Gagan Goel, Vahab Mirrokni, and Renato Paes Leme. Clinching auctions beyond hard budget constraints. In Proceedings of the 15th ACM Conference on Economics and Computation (EC), pages 167–184, 2014.arxiv.org/abs/1404.5000
  24. [25]Pranav Garimidi, Joachim Neu, and Max Resnick. Multiple concurrent proposers: Why and how. Cryptology ePrint Archive, Paper 2025/1772, 2025.arxiv.org/abs/2509.23984
  25. [26]Hiroshi Hirai and Ryosuke Sato. Polyhedral clinching auctions for two-sided markets. Mathematics of Operations Research, 47(1):259–285, 2022.
  26. [27]Atsushi Iwasaki, Vincent Conitzer, Yoshifusa Omori, Yuko Sakurai, Taiki Todo, Mingyu Guo, and Makoto Yokoo. Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 633–640, 2010.DOI
  27. [28]Atsushi Iwasaki, Makoto Yokoo, and Kenji Terada. A robust open ascending-price multi-unit auction protocol against false-name bids. In Proceedings of the 4th ACM Conference on Electronic Commerce (EC), pages 85–92, 2003.
  28. [29]Kshitij Kulkarni, Theo Diamandis, and Tarun Chitra. Towards a theory of maximal extractable value I: constant function market makers. CoRR, abs/2207.11835, 2022.arxiv.org/abs/2207.11835
  29. [30]Mahimna Kelkar, Soubhik Deb, and Sreeram Kannan. Order-fair consensus in the permissionless setting. In APKC ’22: Proceedings of the 9th ACM on ASIA Public-Key Cryptography Workshop, 2022.DOI
  30. [31]Mahimna Kelkar, Soubhik Deb, Sishan Long, Ari Juels, and Sreeram Kannan. Themis: Fast, strong order-fairness in Byzantine consensus. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 475–489. Association for Computing Machinery, 2023.DOI
  31. [32]Klaus Kursawe. Wendy, the good little fairness widget: Achieving order fairness for blockchains. In Proceedings of the 2nd ACM Conference on Advances in Financial Technologies, 2020.DOI
  32. [33]Mahimna Kelkar, Fan Zhang, Steven Goldfeder, and Ari Juels. Order-fairness for byzantine consensus. In CRYPTO, page 451–480, 2020.DOI
  33. [34]Ron Lavi and Marina May. A note on the incompatibility of strategy-proofness and Pareto-optimality in quasi-linear settings with public budgets. Economics Letters, 115(1):100–103, 2012.
  34. [35]Yuhao Li, Elaine Shi, and Mengqian Zhang. A trilemma in amm mechanism design. In Financial Cryptography and Data Security (FC), 2026.arxiv.org/abs/2605.27602
  35. [36]Pinyan Lu and Tao Xiao. Improved efficiency guarantees in auctions with budgets. In Proceedings of the 16th ACM Conference on Economics and Computation (EC), pages 397–413, 2015.arxiv.org/abs/1407.8325
  36. [37]Jason Milionis, Ciamac C. Moallemi, and Tim Roughgarden. A Myersonian framework for optimal liquidity provision in automated market makers. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), volume 287 of Leibniz International Proceedings in Informatics (LIPIcs), pages 81:1–81:19. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2024.DOI
  37. [38]Roger B. Myerson. Optimal auction design. Math. Oper. Res., 6(1), 1981.DOI
  38. [39]Andreas Park. The conceptual flaws of decentralized automated market making. Management Science, 69(11):6731–6751, 2023.DOI
  39. [40]Kaihua Qin, Liyi Zhou, Benjamin Livshits, and Arthur Gervais. Attacking the DeFi ecosystem with flash loans for fun and profit. In Financial Cryptography and Data Security: 25th International Conference, FC 2021, Virtual Event, March 1–5, 2021, Revised Selected Papers, Part I, 2021.arxiv.org/abs/2003.03810
  40. [41]Geoffrey Ramseyer, Mohak Goyal, Ashish Goel, and David Mazières. Augmenting batch exchanges with constant function market makers. In EC, 2024.arxiv.org/abs/2210.04929
  41. [42]Yuko Sakurai, Yasumasa Saito, Atsushi Iwasaki, and Makoto Yokoo. Beyond quasi-linear utility: Strategy/false-name-proof multi-unit auction protocols. In IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT), volume 2, pages 417–423, 2008.
  42. [43]Yuko Sakurai, Makoto Yokoo, and Shigeo Matsubara. A limitation of the generalized Vickrey auction in electronic commerce: Robustness against false-name bids. In AAAI, 1999.
  43. [44]Elaine Shi, Mengqian Zhang, Hao Chung, and Yuhao Li. Otter: A provably mev-resilient automated market maker via surplus redistribution. arXiv:2609.03474, 2026.arxiv.org/abs/2609.03474
  44. [45]Uniswap. https://app.uniswap.org/.
  45. [46]Mohammad Amin Vafadar and Majid Khabbazian. Condorcet attack against fair transaction ordering. In 5th Conference on Advances in Financial Technologies (AFT 2023), volume 282 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1–15:21. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2023.
  46. [47]Sen Yang, Kartik Nayak, and Fan Zhang. Decentralization of ethereum’s builder market. In 2025 IEEE Symposium on Security and Privacy (SP), page 1512–1530. IEEE, May 2025.DOI
  47. [48]Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara. Robust combinatorial auction protocol against false-name bids. Artificial Intelligence, 130(2):167–181, 2001.
  48. [49]Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara. The effect of false-name bids in combinatorial auctions: New fraud in Internet auctions. Games and Economic Behavior, 46(1):174–188, 2004.DOI
  49. [50]Liyi Zhou, Kaihua Qin, Christof Ferreira Torres, Duc Viet Le, and Arthur Gervais. High-frequency trading on decentralized on-chain exchanges. In IEEE Symposium on Security and Privacy, 2021.

Paper details

vlnc:W_tk4nf7ar
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents