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 X X X and Y Y Y , against a smart contract, which we henceforth also refer to as the pool . Initially, the state of the pool is denoted by ( x 0 , y 0 ) (x_0,y_0) ( x 0 , y 0 ) , meaning that the pool holds x 0 x_0 x 0 units of X X X and y 0 y_0 y 0 units of Y Y Y . The exchange rate for each trade is determined by a predefined pricing curve. For example, the widely adopted constant-product rule requires
( x 0 − x ) ( y 0 + y ) = C (x_0-x)(y_0+y)=C ( x 0 − x ) ( y 0 + y ) = C
for some positive constant C C C . Thus, starting from state ( x 0 , y 0 ) (x_0,y_0) ( x 0 , y 0 ) , a user who contributes y y y units of Y Y Y to the pool receives x x x units of X X X . Following the trade, the pool transitions to state ( x 0 − x , y 0 + y ) (x_0-x,y_0+y) ( x 0 − x , y 0 + y ) , preserving the invariant that the product of the reserves remains equal to C C C .
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 X X X with Y Y Y . Immediately before that order, the builder buys X X X 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 v v v and a budget Q Q Q , meaning that it wants to buy X X X using at most Q Q Q units of Y Y Y , and that it values each unit of X X X it acquires at v v v units of Y Y Y . 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.
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.
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 KZGJ20, 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.
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 Y Y Y may inject sell-X X X 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.
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 Y Y Y may only sell more Y Y Y .
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 ( 1 + 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, X X X and Y Y Y . The AMM pool has initial reserves ( x 0 , y 0 ) ∈ R + + 2 (x_0,y_0) \in\mathbb{R}_{++}^{2} ( x 0 , y 0 ) ∈ R ++ 2 . Its reserve curve is
R φ : = { ( x , φ ( x ) ) : x > 0 } . \mathcal{R}_{\varphi} := \{(x,\varphi(x)) : x > 0\}. R φ := {( x , φ ( 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) φ : ( 0 , ∞ ) → ( 0 , ∞ ) 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, x ↓ 0 lim φ ( x ) = ∞ , x ↑ ∞ lim φ ( x ) = 0 , and is differentiable at x 0 x_0 x 0 , where y 0 = φ ( x 0 ) y_0 = \varphi(x_0) y 0 = φ ( x 0 ) . The spot price of one unit of X X X , measured in units of Y Y Y , is
p 0 : = − φ ′ ( x 0 ) > 0. p_0 := -\varphi'(x_0) > 0. p 0 := − φ ′ ( x 0 ) > 0. For a net release z < x 0 z < x_0 z < x 0 of asset X X X , define the signed pool cost
C ( z ) : = φ ( x 0 − z ) − y 0 . C(z) := \varphi(x_0-z)-y_0. C ( z ) := φ ( x 0 − z ) − y 0 . Here z > 0 z > 0 z > 0 means that the pool releases z z z units of X X X , whereas z < 0 z < 0 z < 0 means that it absorbs − z -z − z units. Correspondingly, C ( z ) C(z) C ( z ) is the net amount of Y Y Y received by the pool and may be negative. The function C C C is continuous, strictly increasing, and convex, with
C ( 0 ) = 0 , lim z ↑ x 0 C ( z ) = + ∞ , lim z → − ∞ C ( z ) = − y 0 , C ′ ( 0 ) = p 0 . 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. C ( 0 ) = 0 , z ↑ x 0 lim C ( z ) = + ∞ , z → − ∞ lim C ( z ) = − y 0 , C ′ ( 0 ) = p 0 . Thus sending y ≥ 0 y \ge0 y ≥ 0 units of Y Y Y into the pool releases C − 1 ( y ) ∈ [ 0 , x 0 ) C^{-1}(y) \in[0,x_0) C − 1 ( y ) ∈ [ 0 , x 0 ) units of X X X , while sending x ≥ 0 x \ge0 x ≥ 0 units of X X X into the pool releases − C ( − x ) ∈ [ 0 , y 0 ) -C(-x) \in[0,y_0) − C ( − x ) ∈ [ 0 , y 0 ) units of Y Y Y . These two compensation maps are continuous, strictly increasing, and concave. Their initial marginal exchange rates are 1 / p 0 1/p_0 1/ p 0 and p 0 p_0 p 0 , respectively.
Constant product as a special case. If φ ( x ) = x 0 y 0 / x \varphi(x)=x_0y_0/x φ ( x ) = x 0 y 0 / x , then
C ( z ) = y 0 z x 0 − z , C − 1 ( y ) = x 0 y y 0 + y , − C ( − x ) = y 0 x x 0 + 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}. C ( z ) = x 0 − z y 0 z , C − 1 ( y ) = y 0 + y x 0 y , − C ( − x ) = x 0 + x y 0 x .
Consequently p 0 = y 0 / x 0 p_0=y_0/x_0 p 0 = y 0 / x 0 , the first compensation map has initial derivative x 0 / y 0 = 1 / p 0 x_0/y_0=1/p_0 x 0 / y 0 = 1/ p 0 , and the second has initial derivative y 0 / x 0 = p 0 y_0/x_0=p_0 y 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-Y Y Y orders. A sell-Y Y Y trader k k k has true type
( V k , Q k ) ∈ R ≥ 0 2 , (V_k,Q_k) \in\mathbb{R}_{\ge0}^2, ( V k , Q k ) ∈ R ≥ 0 2 ,
where V k V_k V k is its value for one unit of X X X , measured in units of Y Y Y , and Q k Q_k Q k is its true Y Y Y -budget. A sell-Y Y Y identity i i i reports
( v i , q i ) ∈ R ≥ 0 2 , (v_i,q_i) \in\mathbb{R}_{\ge0}^2, ( v i , q i ) ∈ R ≥ 0 2 ,
where v i v_i v i has the same units as V k V_k V k and q i q_i q i is its declared Y Y Y -budget. An outcome for this identity consists of S Y , i S_{Y,i} S Y , i units of Y Y Y sold and R X , i R_{X,i} R X , i units of X X X received, with
0 ≤ S Y , i ≤ q i , R X , i ≥ 0. (1) 0 \le S_{Y,i} \le q_i,\qquad R_{X,i} \ge0. \tag*{(1)} 0 ≤ S Y , i ≤ q i , R X , i ≥ 0. (1)
Its surplus evaluated at the report is v i R X , i − S Y , i v_iR_{X,i}-S_{Y,i} v i R X , i − S Y , i . A single sell-Y Y Y report is truthful when ( v i , q i ) = ( V k , Q k ) (v_i,q_i)=(V_k,Q_k) ( v i , q i ) = ( V k , Q k ) .
All values in this paper are denominated in units of Y Y Y per unit of X X X . Thus V k V_k V k and v i v_i v i are reciprocals of a positive reservation value for one unit of Y Y Y expressed in units of X X X . This convention puts both types of values on the same price scale.
Sell-X X X orders. A sell-X X X trader k k k has true type
( U k , R k ) ∈ R ≥ 0 2 , (U_k,R_k) \in\mathbb{R}_{\ge0}^2, ( U k , R k ) ∈ R ≥ 0 2 ,
where U k U_k U k is its reservation value for one unit of X X X , measured in units of Y Y Y , and R k R_k R k is its true X X X -budget. A sell-X X X identity i i i reports
( u i , r i ) ∈ R ≥ 0 2 . (u_i,r_i) \in\mathbb{R}_{\ge0}^2. ( u i , r i ) ∈ R ≥ 0 2 .
It sells S X , i S_{X,i} S X , i units of X X X and receives R Y , i R_{Y,i} R Y , i units of Y Y Y , where
0 ≤ S X , i ≤ r i , R Y , i ≥ 0. (2) 0 \le S_{X,i} \le r_i,\qquad R_{Y,i} \ge0. \tag*{(2)} 0 ≤ S X , i ≤ r i , R Y , i ≥ 0. (2)
Its surplus evaluated at the report is R Y , i − u i S X , i R_{Y,i}-u_iS_{X,i} R Y , i − u i S X , i . A single sell-X X X report is truthful when ( u i , r i ) = ( U k , R k ) (u_i,r_i)=(U_k,R_k) ( u i , r i ) = ( U k , R k ) .
A sell-Y Y Y order is eligible if v i ≥ p 0 v_i \ge p_0 v i ≥ p 0 , and a sell-X X X order is eligible if u i ≤ p 0 u_i \le p_0 u i ≤ p 0 . Unless stated otherwise, the truthful types under consideration satisfy V k ≥ p 0 V_k \ge p_0 V k ≥ p 0 for sell-Y Y Y and U k ≤ p 0 U_k \le p_0 U k ≤ p 0 for sell-X X X . At equality with p 0 p_0 p 0 , either direction may be designated as the trader’s type because it is indifferent at the spot price.
AMM mechanism. Let I Y I_Y I Y and I X I_X I X be the finite sets of reported sell-Y Y Y and sell-X X X identities. An AMM mechanism maps the reported orders to an outcome
( ( S Y , i , R X , i ) ) i ∈ I Y , ( ( S X , i , R Y , i ) ) i ∈ I X , \left((S_{Y,i},R_{X,i})\right)_{i\in I_Y},\qquad\left((S_{X,i},R_{Y,i})\right)_{i\in I_X}, ( ( S Y , i , R X , i ) ) i ∈ I Y , ( ( S X , i , R Y , i ) ) i ∈ I X ,
satisfying (1) and (2). The mechanism may match the two sides internally and trade the residual imbalance with the AMM pool.
For an outcome, define the net flows into the pool by
X p o o l : = ∑ i ∈ I Y R X , i − ∑ i ∈ I X S X , i , Y p o o l : = ∑ i ∈ I Y S Y , i − ∑ i ∈ I X R Y , i . (3) X_{\mathrm{pool}} := \sum_{i\in I_Y} R_{X,i} - \sum_{i\in I_X} S_{X,i},\qquad
Y_{\mathrm{pool}} := \sum_{i\in I_Y} S_{Y,i} - \sum_{i\in I_X} R_{Y,i}. \tag*{(3)} X pool := i ∈ I Y ∑ R X , i − i ∈ I X ∑ S X , i , Y pool := i ∈ I Y ∑ S Y , i − i ∈ I X ∑ R Y , i . (3)
Positive values mean that the pool releases X X X and receives Y Y Y ; negative values describe the reverse trade. Trades matched internally cancel from both expressions.
Definition 2.2 (Exact-settlement feasibility). An outcome is exact-settlement feasible if it satisfies the per-identity constraints (1) and (2) , and the terminal pool reserves satisfy
( x 0 − X p o o l , y 0 + Y p o o l ) ∈ R φ . (x_0-X_{\mathrm{pool}},y_0+Y_{\mathrm{pool}})\in\mathcal{R}_{\varphi}. ( x 0 − X pool , y 0 + Y pool ) ∈ R φ . Equivalently, its net pool flows satisfy
X p o o l < x 0 , Y p o o l = C ( X p o o l ) . X_{\mathrm{pool}}<x_0,\qquad Y_{\mathrm{pool}}=C(X_{\mathrm{pool}}). X pool < x 0 , Y pool = C ( X pool ) . Thus every unit paid to an identity is supplied by an opposite-side identity or by the pool, and every unit delivered by an identity is received by an opposite-side identity or by the pool. The aggregate user flows are exactly the negatives of the pool flows: no outside subsidy is used and no token is discarded. A mechanism is exact-settlement feasible if it produces such an outcome for every reported profile.
Definition 2.3 (Individual rationality). A mechanism is individually rational if, whenever every physical trader submits its single truthful order, every sell-Y trader k k k satisfies
0 ≤ S Y , k ≤ Q k , V k R X , k − S Y , k ≥ 0. 0\leq S_{Y,k}\leq Q_k,\qquad V_kR_{X,k}-S_{Y,k}\geq0. 0 ≤ S Y , k ≤ Q k , V k R X , k − S Y , k ≥ 0. and every sell-X trader k k k satisfies
0 ≤ S X , k ≤ R k , R Y , k − U k S X , k ≥ 0. 0\leq S_{X,k}\leq R_k,\qquad R_{Y,k}-U_kS_{X,k}\geq0. 0 ≤ S X , k ≤ R k , R Y , k − U k S X , k ≥ 0. Equivalently, these inequalities say that truthful participation gives every trader finite, nonnegative true utility. A trader that does not trade has utility zero.
Every declared budget is a hard per-identity trading limit. It is escrowed before the batch, cannot be transferred between identities during the batch, and cannot be replenished from another identity’s batch proceeds. Transfers and deliveries occur at final settlement.
Strategy Space and Utility
Strategy space. We consider a strategy space where not only misreporting value and budget is possible, but also the creation of Sybil identities — as long as reports in the same-direction of the trader’s true type do not exceed the user’s actual budget in aggregate. No cap is imposed on opposite-direction Sybil bids, i.e., the trader’s opposite direction budget may be arbitrarily large. The mechanism observes only the reported orders; it does not know which identities are controlled by the same physical trader.
More formally, fix a physical trader k k k , and let I Y ( k ) ⊆ I Y I_Y(k)\subseteq I_Y I Y ( k ) ⊆ I Y and I X ( k ) ⊆ I X I_X(k)\subseteq I_X I X ( k ) ⊆ I X denote its sell-Y and sell-X identities.
Definition 2.4 (Admissible two-sided Sybil strategy). An admissible strategy of trader k k k is a pair of finite collections
( ( v i , q i ) ) i ∈ I Y ( k ) , ( ( u i , r i ) ) i ∈ I X ( k ) , \left((v_i,q_i)\right)_{i\in I_Y(k)},\qquad\left((u_i,r_i)\right)_{i\in I_X(k)}, ( ( v i , q i ) ) i ∈ I Y ( k ) , ( ( u i , r i ) ) i ∈ I X ( k ) , with nonnegative reports, subject to the following direction-dependent constraint.
If k k k has true sell-Y Y Y type ( V k , Q k ) (V_k, Q_k) ( V k , Q k ) , then
∑ i ∈ I Y ( k ) q i ≤ Q k . \sum_{i \in I_Y(k)} q_i \le Q_k. i ∈ I Y ( k ) ∑ q i ≤ Q k .
The opposite-direction budgets r i r_i r i may be arbitrary finite nonnegative numbers.
If k k k has true sell-X X X type ( U k , R k ) (U_k, R_k) ( U k , R k ) , then
∑ i ∈ I X ( k ) r i ≤ R k . \sum_{i \in I_X(k)} r_i \le R_k. i ∈ I X ( k ) ∑ r i ≤ R k .
The opposite-direction budgets q i q_i q i may be arbitrary finite nonnegative numbers. The reported values v i v_i v i and u i u_i u i may also be arbitrary finite nonnegative numbers.
Aggregate net flow and utility. Define trader k k k ’s aggregate gross token flows by
S Y ( k ) : = ∑ i ∈ I Y ( k ) S Y , i , R X ( k ) : = ∑ i ∈ I Y ( k ) R X , i , S X ( k ) : = ∑ i ∈ I X ( k ) S X , i , R Y ( k ) : = ∑ i ∈ I X ( k ) R Y , i . \begin{aligned}
S_Y(k) &:= \sum_{i \in I_Y(k)} S_{Y,i}, & R_X(k) &:= \sum_{i \in I_Y(k)} R_{X,i},\\
S_X(k) &:= \sum_{i \in I_X(k)} S_{X,i}, & R_Y(k) &:= \sum_{i \in I_X(k)} R_{Y,i}.
\end{aligned} S Y ( k ) S X ( k ) := i ∈ I Y ( k ) ∑ S Y , i , := i ∈ I X ( k ) ∑ S X , i , R X ( k ) R Y ( k ) := i ∈ I Y ( k ) ∑ R X , i , := i ∈ I X ( k ) ∑ R Y , i .
Its net changes in token holdings are
Δ X , k : = R X ( k ) − S X ( k ) , Δ Y , k : = R Y ( k ) − S Y ( k ) . (4) \Delta_{X,k} := R_X(k) - S_X(k), \qquad\Delta_{Y,k} := R_Y(k) - S_Y(k). \tag*{(4)} Δ X , k := R X ( k ) − S X ( k ) , Δ Y , k := R Y ( k ) − S Y ( k ) . (4)
Thus − Δ X , k -\Delta_{X,k} − Δ X , k and − Δ Y , k -\Delta_{Y,k} − Δ Y , k are its net sales of X X X and Y Y Y , respectively. Utility is evaluated from these aggregate net flows, not by adding the identities’ reported surpluses.
For a true sell-Y Y Y type ( V k , Q k ) (V_k, Q_k) ( V k , Q k ) , define
Util k Y : = { − ∞ , if − Δ Y , k > Q k or ( − Δ Y , k < 0 and Δ X , k < 0 ) , V k Δ X , k + Δ Y , k , otherwise. (5) \operatorname{Util}^{Y}_k :=
\begin{cases}
-\infty, & \text{if } -\Delta_{Y,k} > Q_k \text{ or } (-\Delta_{Y,k} < 0 \text{ and } \Delta_{X,k} < 0),\\
V_k\Delta_{X,k} + \Delta_{Y,k}, & \text{otherwise.}
\end{cases} \tag*{(5)} Util k Y := { − ∞ , V k Δ X , k + Δ Y , k , if − Δ Y , k > Q k or ( − Δ Y , k < 0 and Δ X , k < 0 ) , otherwise. (5)
The first catastrophic event means that the trader’s net sale of Y Y Y exceeds its true budget. The second means that its aggregate trade is strictly opposite to its type: it gains Y Y Y while losing X X X .
For a true sell-X X X type ( U k , R k ) (U_k, R_k) ( U k , R k ) , define
Util k X = { − ∞ , if − Δ X , k > R k or ( − Δ X , k < 0 and Δ Y , k < 0 ) , Δ Y , k + U k Δ X , k , otherwise. (6) \operatorname{Util}^{X}_{k} =
\begin{cases}
-\infty, & \text{if } -\Delta_{X,k} > R_k \text{ or } (-\Delta_{X,k} < 0 \text{ and } \Delta_{Y,k} < 0),\\
\Delta_{Y,k} + U_k\Delta_{X,k}, & \text{otherwise.}
\end{cases} \tag*{(6)} Util k X = { − ∞ , Δ Y , k + U k Δ X , k , if − Δ X , k > R k or ( − Δ X , k < 0 and Δ Y , k < 0 ) , otherwise. (6)
Here the catastrophic events mean that the trader net-sells more X X X than its true budget, or that it gains X X X while losing Y Y Y .
These utility functions do not penalize a trader merely for receiving a net gain in its budget token when it does not lose the other token. Moreover, the catastrophic budget tests concern net rather than gross sales: receipts through opposite-side identities offset deliveries of the same token.
The truthful merged strategy of a sell-Y Y Y type ( V k , Q k ) (V_k, Q_k) ( V k , Q k ) is the single sell-Y Y Y order ( V k , Q k ) (V_k, Q_k) ( V k , Q k ) ; its utility reduces to V k R X ( k ) − S Y ( k ) V_k R_X(k) - S_Y(k) V k R X ( k ) − S Y ( k ) . The truthful merged strategy of a sell-X X X type ( U k , R k ) (U_k, R_k) ( U k , R k ) is the single sell-X X X order ( U k , R k ) (U_k, R_k) ( U k , R k ) ; its utility reduces to R Y ( k ) − U k S X ( k ) R_Y(k) - U_k S_X(k) R Y ( k ) − U k S X ( k ) .
Desired Properties
Sybil-robust incentive compatibility. Sybil-robust incentive compatibility says that the truthful strategy is profit-maximizing in light of the strategy space defined earlier.
Definition 2.6 (Sybil-robust incentive compatibility). A mechanism is Sybil-robust incentive compatible if, for every physical trader, every true type (including ineligible types), every fixed strategy profile of the other traders, and every admissible strategy in Theorem 2.4, the true utility from the truthful merged strategy is at least the true utility from the deviation. The applicable utility is (5) for a sell-Y Y Y type and (6) for a sell-X X X type.
Since the strategy space for a block builder — possibly having intrinsic value and demand — is the same as for an ordinary trader, Theorem 2.6 simultaneously captures dominant strategy incentive compatibility (DSIC) for individual traders, as well as strategy-proofness for a block builder.
Weak Pareto optimality for eligible bids. Fix a completed, exact-settlement-feasible outcome under truthful reporting. For each eligible user i i i , define its post-batch holdings and value coefficient by
( H i X , H i Y , t i ) : = { ( R X , i , Q i − S Y , i , V i ) , i is a sell- Y user , ( R i − S X , i , R Y , i , U i ) , i is a sell- X user. (7) (H_i^X, H_i^Y, t_i) :=
\begin{cases}
(R_{X,i}, Q_i - S_{Y,i}, V_i), & i \text{ is a sell-}Y\text{ user},\\
(R_i - S_{X,i}, R_{Y,i}, U_i), & i \text{ is a sell-}X\text{ user.}
\end{cases} \tag*{(7)} ( H i X , H i Y , t i ) := { ( R X , i , Q i − S Y , i , V i ) , ( R i − S X , i , R Y , i , U i ) , i is a sell- Y user , i is a sell- X user. (7)
Thus a change ( δ x i , δ y i ) (\delta x_i, \delta y_i) ( δ x i , δ y i ) in user i i i ’s holdings changes its utility by t i δ x i + δ y i t_i\delta x_i + \delta y_i t i δ x i + δ y i .
Definition 2.7 (Weak Pareto optimality). An exact-settlement-feasible two-sided outcome is weakly Pareto optimal for eligible bids if both of the following hold.
There is no subset J \mathcal{J} J of eligible users and no additional internal trade satisfying
∑ i ∈ J δ x i = 0 , ∑ i ∈ J δ y i = 0 , δ x i ≥ − H i X , δ y i ≥ − H i Y ( i ∈ J ) \sum_{i\in\mathcal{J}} \delta x_i = 0,\qquad
\sum_{i\in\mathcal{J}} \delta y_i = 0,\qquad
\delta x_i \ge-H_i^X,\qquad
\delta y_i \ge-H_i^Y\qquad(i \in\mathcal{J}) i ∈ J ∑ δ x i = 0 , i ∈ J ∑ δ y i = 0 , δ x i ≥ − H i X , δ y i ≥ − H i Y ( i ∈ J ) that weakly increases t i δ x i + δ y i t_i\delta x_i + \delta y_i t i δ x i + δ y i for every i ∈ J i \in\mathcal{J} i ∈ J and strictly increases it for at least one.
No eligible user can make a strictly utility-improving bilateral trade with the pool in the same direction as that user’s type, using its post-batch holding of the token it sells. A sell-Y Y Y user may tender additional Y Y Y to the pool for X X X , whereas a sell-X X X user may tender additional X X X to the pool for Y Y Y .
The second condition deliberately excludes a reverse-direction pool trade.
Sybil-robust incentive compatibility implies “no free lunch”. In practice, a strategic builder may have no intrinsic value or demand and participate solely to seek a risk-free profit. By risk-free profit, we mean a net gain in one asset without a net loss in the other—that is, a free lunch. We show below that Sybil-robust incentive compatibility (Theorem 2.6) rules out such profits, even when the builder may submit identities with arbitrarily large finite budgets in either asset. We begin by formalizing this guarantee as the no-free-lunch property.
Definition 2.8 (No free lunch). For any reported profile and any subset of identities J ⊆ I Y ∪ I X \mathcal{J} \subseteq\mathcal{I}_Y \cup\mathcal{I}_X J ⊆ I Y ∪ I X , define their aggregate net token gains by
Δ X ( J ) : = ∑ i ∈ J ∩ I Y R X , i − ∑ i ∈ J ∩ I X S X , i , \Delta_X(\mathcal{J}) := \sum_{i \in\mathcal{J} \cap\mathcal{I}_Y} R_{X,i} - \sum_{i \in\mathcal{J} \cap\mathcal{I}_X} S_{X,i}, Δ X ( J ) := i ∈ J ∩ I Y ∑ R X , i − i ∈ J ∩ I X ∑ S X , i , Δ Y ( J ) : = ∑ i ∈ J ∩ I X R Y , i − ∑ i ∈ J ∩ I Y S Y , i . \Delta_Y(\mathcal{J}) := \sum_{i \in\mathcal{J} \cap\mathcal{I}_X} R_{Y,i} - \sum_{i \in\mathcal{J} \cap\mathcal{I}_Y} S_{Y,i}. Δ Y ( J ) := i ∈ J ∩ I X ∑ R Y , i − i ∈ J ∩ I Y ∑ S Y , i . A mechanism satisfies no free lunch if, for every such profile and subset,
Δ X ( J ) > 0 ⟹ Δ Y ( J ) < 0 , Δ Y ( J ) > 0 ⟹ Δ X ( J ) < 0. \Delta_X(\mathcal{J}) > 0 \Longrightarrow\Delta_Y(\mathcal{J}) < 0,\qquad\Delta_Y(\mathcal{J}) > 0 \Longrightarrow\Delta_X(\mathcal{J}) < 0. Δ X ( J ) > 0 ⟹ Δ Y ( J ) < 0 , Δ Y ( J ) > 0 ⟹ Δ X ( J ) < 0. Thus no subset of identities can gain strictly positively in one token without losing the other token in aggregate.
Fact 2.9 (Sybil-robust IC implies no free lunch). Every mechanism satisfying Sybil-robust incentive compatibility (Theorem 2.6) satisfies no free lunch.
Proof. Fix a reported profile and a subset J \mathcal{J} J , and abbreviate its net gains as Δ X , Δ Y \Delta_X,\Delta_Y Δ X , Δ Y . Keep all reports outside J \mathcal{J} J fixed. Since the mechanism does not observe ownership, we may interpret J \mathcal{J} J as the identities of one physical trader. Set
Q : = ∑ i ∈ J ∩ I Y q i , R : = ∑ i ∈ J ∩ I X r i . Q := \sum_{i \in\mathcal{J} \cap\mathcal{I}_Y} q_i,\qquad R := \sum_{i \in\mathcal{J} \cap\mathcal{I}_X} r_i. Q := i ∈ J ∩ I Y ∑ q i , R := i ∈ J ∩ I X ∑ r i .
By Theorem 2.4, submitting these identities is admissible for a sell-Y Y Y trader with budget Q Q Q , or a sell-X X X trader with budget R R R , at any nonnegative true value. Suppose towards a contradiction that Δ X , Δ Y ≥ 0 \Delta_X,\Delta_Y \ge0 Δ X , Δ Y ≥ 0 , with at least one inequality strict. Neither catastrophic utility condition applies to these net gains.
If Δ Y > 0 \Delta_Y > 0 Δ Y > 0 , consider a sell-Y Y Y trader of true type ( 0 , Q ) (0,Q) ( 0 , Q ) . Its truthful merged utility is − δ Y t r ≤ 0 -\delta_Y^{\mathrm{tr}} \le0 − δ Y tr ≤ 0 , whereas submitting J \mathcal{J} J gives utility Δ Y > 0 \Delta_Y > 0 Δ Y > 0 . This contradicts Theorem 2.6.
If Δ X > 0 \Delta_X > 0 Δ X > 0 , for each u ≥ 0 u \ge0 u ≥ 0 let s ( u ) s(u) s ( u ) and r ( u ) r(u) r ( u ) denote the amounts of X X X sold and Y Y Y received by the single sell-X X X report ( u , R ) (u,R) ( u , R ) , against the same fixed outside reports. This report is an admissible deviation for a true type ( 0 , R ) (0,R) ( 0 , R ) , and its utility for that type is r ( u ) r(u) r ( u ) , since 0 ≤ s ( u ) ≤ R 0 \le s(u) \le R 0 ≤ s ( u ) ≤ R . Incentive compatibility for type ( 0 , R ) (0,R) ( 0 , R ) therefore gives
r ( u ) ≤ r ( 0 ) = : K < ∞ for every u ≥ 0. r(u) \le r(0) =: K < \infty\qquad\text{for every } u \ge0. r ( u ) ≤ r ( 0 ) =: K < ∞ for every u ≥ 0.
Choose a finite U > K / Δ X U > K/\Delta_X U > K / Δ X . The truthful utility of type ( U , R ) (U, R) ( U , R ) is at most
r ( U ) − U S ( U ) ≤ r ( U ) ≤ K , r(U) - U_S(U) \le r(U) \le K, r ( U ) − U S ( U ) ≤ r ( U ) ≤ K ,
whereas its admissible strategy J \mathcal{J} J gives Δ Y + U Δ X > K \Delta_Y + U\Delta_X > K Δ Y + U Δ X > K . This again contradicts Theorem 2.6, proving the claim.
Shi et al. [44 ] also show that their notion of incentive compatibility implies no free lunch, paralleling Theorem 2.9 . Their result does not apply directly here, however, because their strategy space permits budget overreporting, whereas ours caps a trader’s aggregate same-direction reports by its true budget.
Warmup: The One-Sided AMM Clinching Mechanism
As a warmup, we first present an AMM clinching mechanism assuming a one-sided market. Specifically, throughout this section, every submitted identity is in the sell-Y Y Y direction: it tenders Y Y Y and demands X X X . The full, two-sided mechanism will be introduced later in § 5 .
The One-Sided Model and Feasibility Requirements
More specifically, we specialize the model of § 2.2 and § 2.3 to a finite set of sell-Y Y Y identities I Y \mathcal{I}_Y I Y , with I X = ∅ \mathcal{I}_X = \varnothing I X = ∅ . Thus identity i i i reports ( v i , q i ) ∈ R ≥ 0 2 (v_i, q_i) \in\mathbb{R}_{\ge0}^2 ( v i , q i ) ∈ R ≥ 0 2 , where v i v_i v i is its value for one unit of X X X , measured in units of Y Y Y , and q i q_i q i is its Y Y Y -budget. It is eligible exactly when v i ≥ p 0 v_i \ge p_0 v i ≥ p 0 ; an ineligible identity receives zero. As before, the mechanism observes neither true types nor which identities have a common owner.
Write
x i : = R X , i , y i : = S Y , i . x_i := R_{X,i}, \qquad y_i := S_{Y,i}. x i := R X , i , y i := S Y , i .
The mechanism chooses x i ≥ 0 x_i \ge0 x i ≥ 0 and 0 ≤ y i ≤ q i 0 \le y_i \le q_i 0 ≤ y i ≤ q i : identity i i i receives x i x_i x i units of X X X , sells y i y_i y i units of Y Y Y , and has reported surplus v i x i − y i v_i x_i - y_i v i x i − y i .
On a truthful profile, identify each physical trader with its unique identity i i i , write its eligible true type as ( V i , Q i ) ∈ [ p 0 , ∞ ) × R ≥ 0 (V_i, Q_i) \in[p_0, \infty) \times\mathbb{R}_{\ge0} ( V i , Q i ) ∈ [ p 0 , ∞ ) × R ≥ 0 , and set ( v i , q i ) = ( V i , Q i ) (v_i, q_i) = (V_i, Q_i) ( v i , q i ) = ( V i , Q i ) . Its true utility is then V i x i − y i V_i x_i - y_i V i x i − y i . Indeed, y i ≤ q i = Q i y_i \le q_i = Q_i y i ≤ q i = Q i , and the opposite-direction catastrophe in (5) cannot occur because Δ X , i = x i ≥ 0 \Delta_{X,i} = x_i \ge0 Δ X , i = x i ≥ 0 . Same-direction Sybil strategies and their utilities retain the definitions of Theorem 2.4 and § 2.3 , specialized to I X = ∅ \mathcal{I}_X = \varnothing I X = ∅ .
On the one-sided domain 0 ≤ z < x 0 0 \le z < x_0 0 ≤ z < x 0 , C ( z ) C(z) C ( z ) is the amount of Y Y Y the pool must receive to release z z z units of X X X . Define its right marginal ask by
a ( z ) : = C + ′ ( z ) , a(z) := C'_+(z), a ( z ) := C + ′ ( z ) ,
so, in particular, a ( 0 ) = p 0 a(0) = p_0 a ( 0 ) = p 0 .
For any reported profile, define the aggregate allocation and payment by
X : = ∑ i ∈ I Y x i , Y : = ∑ i ∈ I Y y i . (8) X := \sum_{i \in\mathcal{I}_Y} x_i, \qquad Y := \sum_{i \in\mathcal{I}_Y} y_i. \tag*{(8)} X := i ∈ I Y ∑ x i , Y := i ∈ I Y ∑ y i . (8)
Because I X = ∅ \mathcal{I}_X = \varnothing I X = ∅ , the two-sided net pool flows (3) specialize to X p o o l = X X_{\mathrm{pool}} = X X pool = X and Y p o o l = Y Y_{\mathrm{pool}} = Y Y pool = Y . Consequently, Theorem 2.2 requires precisely
0 ≤ X < x 0 , Y = C ( X ) . (9) 0 \le X < x_0,\qquad Y = C(X). \tag*{(9)} 0 ≤ X < x 0 , Y = C ( X ) . (9)
The terminal pool reserves are then
( x 0 − X , y 0 + Y ) ∈ R φ . (x_0 - X, y_0 + Y) \in\mathcal{R}_{\varphi}. ( x 0 − X , y 0 + Y ) ∈ R φ .
Likewise, for a truthful one-sided bidder, S Y ( i ) = y i S_Y(i) = y_i S Y ( i ) = y i and R X ( i ) = x i R_X(i) = x_i R X ( i ) = x i . The two-sided individual-rationality requirement in Theorem 2.3 therefore specializes to
0 ≤ y i ≤ Q i , V i x i − y i ≥ 0. 0 \le y_i \le Q_i,\qquad V_i x_i - y_i \ge0. 0 ≤ y i ≤ Q i , V i x i − y i ≥ 0.
The mechanism below is designed to satisfy these specializations of the two-sided requirements. Allocations and payments are generated by an ascending price clock p p p , starting at the spot price p 0 p_0 p 0 .
State, Chord Target, and Demand
At clock price p p p , identity i i i has cumulative allocation x i x_i x i , cumulative payment y i y_i y i , and effective remaining budget b i b_i b i . While the identity remains in the auction, b i = q i − y i b_i = q_i - y_i b i = q i − y i . When it exits without spending all of its budget, the unspent amount is cancelled and b i b_i b i is set to zero. Together with the aggregate allocation X X X and payment Y Y Y defined in (8) , let
B : = ∑ i ∈ I Y b i B := \sum_{i \in\mathcal{I}_Y} b_i B := i ∈ I Y ∑ b i
denote the aggregate effective remaining budget.
The mechanism starts from
p = p 0 , x i = y i = 0 , X = Y = 0. (10) p = p_0,\qquad x_i = y_i = 0,\qquad X = Y = 0. \tag*{(10)} p = p 0 , x i = y i = 0 , X = Y = 0. (10)
Ineligible reports are removed as specified above. Every remaining identity initially has b i = q i b_i = q_i b i = q i .
After the target below is computed, all events at p 0 p_0 p 0 are processed before the clock rises. In particular, if T a m m ( p 0 , 0 , 0 ) > 0 T^{\mathrm{amm}}(p_0,0,0) > 0 T amm ( p 0 , 0 , 0 ) > 0 , that initial target is released as a supply lump, and identities with v i = p 0 v_i = p_0 v i = p 0 are treated as exiting identities. For the AMM, a positive initial target occurs precisely when C C C has a nontrivial initial linear piece of slope p 0 p_0 p 0 . Thus the general event order below also covers the initial state.
For any state satisfying Y ≥ C ( X ) Y \ge C(X) Y ≥ C ( X ) , define
g p ( z ) : = C ( z ) − Y − p ( z − X ) , z ∈ [ X , x 0 ) . g_p(z) := C(z) - Y - p(z - X),\qquad z \in[X,x_0). g p ( z ) := C ( z ) − Y − p ( z − X ) , z ∈ [ X , x 0 ) .
The AMM chord target is
T a m m ( p , X , Y ) : = max { z ∈ [ X , x 0 ) : g p ( z ) ≤ 0 } . (11) T^{\mathrm{amm}}(p,X,Y) := \max\{z \in[X,x_0) : g_p(z) \le0\}. \tag*{(11)} T amm ( p , X , Y ) := max { z ∈ [ X , x 0 ) : g p ( z ) ≤ 0 } . (11)
The maximum exists: the set is nonempty because g p ( X ) ≤ 0 g_p(X) \le0 g p ( X ) ≤ 0 , it is an interval by convexity, and it is bounded away from x 0 x_0 x 0 because C ( z ) → ∞ C(z) \to\infty C ( z ) → ∞ . At its right endpoint,
C ( T a m m ) = Y + p ( T a m m − X ) , a ( T a m m ) ≥ p . C(T^{\mathrm{amm}}) = Y + p(T^{\mathrm{amm}} - X),\qquad a(T^{\mathrm{amm}}) \ge p. C ( T amm ) = Y + p ( T amm − X ) , a ( T amm ) ≥ p .
The residual supply offered to the auction at the current price is
S : = T a m m − X . S := T^{\mathrm{amm}} - X. S := T amm − X .
Geometrically, T a m m T^{\mathrm{amm}} T amm is the rightmost intersection of C C C with the line of slope p p p through ( X , Y ) (X,Y) ( X , Y ) . Notice that a purchase of δ ≤ S \delta\le S δ ≤ S at price p p p changes the state to
X + = X + δ , Y + = Y + p δ , X^{+} = X + \delta,\qquad Y^{+} = Y + p\delta, X + = X + δ , Y + = Y + p δ ,
but leaves Y − p X Y-pX Y − pX , and hence T a m m T^{\mathrm{amm}} T amm , unchanged. The purchase reduces residual supply from S S S to S − δ S-\delta S − δ .
At the current price p p p , define
Active : = { i : v i > p , b i > 0 } , Exit : = { i : v i = p , b i > 0 } . (12) \operatorname{Active} := \{i : v_i > p,\ b_i > 0\},\qquad\operatorname{Exit} := \{i : v_i = p,\ b_i > 0\}. \tag*{(12)} Active := { i : v i > p , b i > 0 } , Exit := { i : v i = p , b i > 0 } . (12)
Thus Active is the set of active identities and Exit is the set of exiting identities that have not yet been processed. Until an exiting identity is processed, its budget remains part of B B B . Write
D i : = b i p , D − i : = ∑ j ≠ i : b j > 0 b j p D_i := \frac{b_i}{p},\qquad D_{-i} := \sum_{j\ne i:\,b_j>0}\frac{b_j}{p} D i := p b i , D − i := j = i : b j > 0 ∑ p b j
for its demand and the demand of the other unprocessed identities. The mechanism maintains the supply invariant
S ≤ D − i for every i ∈ Active . (13) S \le D_{-i}\qquad\text{for every }i\in\operatorname{Active}. \tag*{(13)} S ≤ D − i for every i ∈ Active . (13)
The set of clinching identities is
Clinch : = { i ∈ Active : S = D − i } . (14) \operatorname{Clinch} := \{i\in\operatorname{Active}: S = D_{-i}\}. \tag*{(14)} Clinch := { i ∈ Active : S = D − i } . (14)
It is convenient to introduce the water level
h : = B − p S . h := B-pS. h := B − pS .
Since p D − i = B − b i pD_{-i}=B-b_i p D − i = B − b i , the invariant and clinching condition are equivalently
b i ≤ h for every i ∈ Active , Clinch = { i ∈ Active : b i = h } . (15) b_i \le h\quad\text{for every }i\in\operatorname{Active},\qquad\operatorname{Clinch}=\{i\in\operatorname{Active}:b_i=h\}. \tag*{(15)} b i ≤ h for every i ∈ Active , Clinch = { i ∈ Active : b i = h } . (15)
Continuous Evolution
We use the clock price itself as the time variable, so d p / d p = 1 \mathrm{d}p/\mathrm{d}p=1 d p / d p = 1 . Consider an open interval containing no valuation exit, no discontinuity of the target, no change in the clinching set, and no terminal event. The clock and state paths are absolutely continuous on such an interval, and the target is always reevaluated from the algebraic identity
T a m m = T a m m ( p , X , Y ) , S = T a m m − X , h = B − p S . (16) T^{\mathrm{amm}} = T^{\mathrm{amm}}(p,X,Y),\qquad S = T^{\mathrm{amm}}-X,\qquad h = B-pS. \tag*{(16)} T amm = T amm ( p , X , Y ) , S = T amm − X , h = B − pS . (16)
The continuous evolution is defined by the following primitive conditions. An identity outside Clinch does not trade:
d x i d p = d y i d p = d b i d p = 0 , i ∉ Clinch . (17) \frac{\mathrm{d}x_i}{\mathrm{d}p}=\frac{\mathrm{d}y_i}{\mathrm{d}p}=\frac{\mathrm{d}b_i}{\mathrm{d}p}=0,\qquad i\notin\operatorname{Clinch}. \tag*{(17)} d p d x i = d p d y i = d p d b i = 0 , i ∈ / Clinch . (17)
Every identity in Clinch receives a nonnegative allocation at the current price, spends exactly that payment from its effective budget, and remains tight at the water level:
d x i d p ≥ 0 , d y i d p = p d x i d p , d b i d p = − d y i d p , d d p ( b i − h ) = 0 , i ∈ C l i n c h . (18) \frac{\mathrm{d}x_i}{\mathrm{d}p} \ge0,\qquad\frac{\mathrm{d}y_i}{\mathrm{d}p} = p\frac{\mathrm{d}x_i}{\mathrm{d}p},\qquad\frac{\mathrm{d}b_i}{\mathrm{d}p} = -\frac{\mathrm{d}y_i}{\mathrm{d}p},\qquad\frac{\mathrm{d}}{\mathrm{d}p}(b_i-h)=0,\qquad i\in\mathrm{Clinch}. \tag*{(18)} d p d x i ≥ 0 , d p d y i = p d p d x i , d p d b i = − d p d y i , d p d ( b i − h ) = 0 , i ∈ Clinch . (18)
Equations (16) –(18) form a differential-algebraic definition of the continuous auction path. They say directly that trade is charged at the clock price and that an identity which is just able to clinch remains just able to clinch. They apply without modification when S = 0 S=0 S = 0 : zero residual supply is a boundary state of the same dynamics, not a separate dynamic regime. No trading-rate formula is assumed. In § 4.2 we prove that these conditions determine a unique rate almost everywhere and derive its explicit form. Upward target jumps are handled by the event rules below.
Fixed-Price Operations and Events
For use in every event rule, define
Buy ( i , δ ; p ) , 0 ≤ δ ≤ min { S , b i / p } , \operatorname{Buy}(i,\delta;p),\qquad0\le\delta\le\min\{S,b_i/p\}, Buy ( i , δ ; p ) , 0 ≤ δ ≤ min { S , b i / p } ,
by
x i ← x i + δ , y i ← y i + p δ , b i ← b i − p δ . x_i\leftarrow x_i+\delta,\qquad y_i\leftarrow y_i+p\delta,\qquad b_i\leftarrow b_i-p\delta. x i ← x i + δ , y i ← y i + p δ , b i ← b i − p δ .
The aggregate variables X X X , Y Y Y , B B B are updated accordingly. A fixed-price purchase leaves both T a m m T^{\mathrm{amm}} T amm and h = B − p ( T a m m − X ) h=B-p(T^{\mathrm{amm}}-X) h = B − p ( T amm − X ) unchanged.
The continuous dynamics stop whenever one of the following events is reached.
A bidder joins the clinching set. There is no state jump. Add the identity to Clinch and continue with (16) –(18) .
A valuation exit. The identities in Exit are marked as exiting. If the stopping allocation is executed, simultaneous exits are served by the proportional rule specified below; otherwise, their remaining budgets are cancelled simultaneously.
A supply lump. A lump is an upward jump Δ T a m m > 0 \Delta T^{\mathrm{amm}}>0 Δ T amm > 0 of the target at a fixed price. Incorporate the entire jump by setting
T a m m ← T a m m + Δ T a m m , S ← S + Δ T a m m . (19) T^{\mathrm{amm}}\leftarrow T^{\mathrm{amm}}+\Delta T^{\mathrm{amm}},\qquad S\leftarrow S+\Delta T^{\mathrm{amm}}. \tag*{(19)} T amm ← T amm + Δ T amm , S ← S + Δ T amm . (19)
For the AMM, such a jump can occur only from a settled state ( X , C ( X ) ) (X,C(X)) ( X , C ( X )) when C C C has a linear piece of slope p p p beginning at X X X . If [ X , X ∗ ] [X,X^*] [ X , X ∗ ] is the remainder of the maximal such piece, then Δ T a m m = X ∗ − X \Delta T^{\mathrm{amm}}=X^*-X Δ T amm = X ∗ − X and the updated target is T a m m = X ∗ T^{\mathrm{amm}}=X^* T amm = X ∗ . At a price that is both a lump and an exit, incorporate the entire lump before processing any exiting identity.
After incorporating a possible lump and identifying every exit at p p p , update Active and Exit. Before cancelling any budget or making any restoration purchase, test
∑ i ∈ A c t i v e b i p ≤ S . (20) \sum_{i\in\mathrm{Active}}\frac{b_i}{p}\le S. \tag*{(20)} i ∈ Active ∑ p b i ≤ S . (20)
If (20) holds, perform the stopping allocation . First give every active identity its full demand by applying Buy ( i , b i / p ; p ) \operatorname{Buy}(i,b_i/p;p) Buy ( i , b i / p ; p ) for every i ∈ A c t i v e i \in\mathrm{Active} i ∈ Active . Let
L : = S − ∑ i ∈ A c t i v e b i p , B E : = ∑ i ∈ E x i t b i (21) L := S-\sum_{i\in\mathrm{Active}}\frac{b_i}{p},\qquad B_E := \sum_{i\in\mathrm{Exit}} b_i \tag*{(21)} L := S − i ∈ Active ∑ p b i , B E := i ∈ Exit ∑ b i (21)
be the residual quantity and the total exiting budget, both evaluated before these purchases. If B E > 0 B_E>0 B E > 0 , give each exiting identity the proportional quantity
δ i : = b i B E min { L , B E p } , i ∈ E x i t , (22) \delta_i := \frac{b_i}{B_E}\min\left\{L,\frac{B_E}{p}\right\},\qquad i\in\mathrm{Exit}, \tag*{(22)} δ i := B E b i min { L , p B E } , i ∈ Exit , (22)
at price p p p . Cancel every unspent exiting budget and end the run. At an ordinary exit the current chord is cleared. At a lump, the run may instead end partway through the linear piece: the unallocated suffix is not released by the pool. The proportional rule makes a simultaneous exit independent of how a physical order is partitioned among equal-valued identities.
Suppose instead that (20) fails. With the entire lump already incorporated, cancel all exiting budgets simultaneously:
b j ← 0 for every j ∈ E x i t , (23) b_j \leftarrow0\qquad\text{for every }j\in\mathrm{Exit}, \tag*{(23)} b j ← 0 for every j ∈ Exit , (23)
and update B B B . Define the post-event water level
h ⋆ : = B − p S , h^\star:= B-pS, h ⋆ := B − pS ,
where B B B is evaluated after all cancellations. For each i ∈ A c t i v e i\in\mathrm{Active} i ∈ Active with b i > h ⋆ b_i>h^\star b i > h ⋆ , apply exactly once
Buy ( i , b i − h ⋆ p ; p ) . (24) \operatorname{Buy}\left(i,\frac{b_i-h^\star}{p};p\right). \tag*{(24)} Buy ( i , p b i − h ⋆ ; p ) . (24)
These purchases reduce every affected active budget directly to h ⋆ h^\star h ⋆ . Each purchase leaves B − p S B-pS B − pS unchanged, so all purchases use the same post-event water level and their order is immaterial.
Set h ← h ⋆ h\leftarrow h^\star h ← h ⋆ , recompute T a m m T_{\mathrm{amm}} T amm , S S S , B B B , update Active, Exit, and Clinch using (12) and (15) , and resume the continuous dynamics. The stopping test need not be repeated: cancelling exiting budgets changes neither active demand nor residual supply, while each fixed-price purchase reduces them by the same amount. This one-shot restoration is equivalent to restoring after the lump and again after each exit, because every intermediate restoration purchase leaves the water level unchanged.
Continuation and Termination
Unless one of the terminal conditions below holds, raise the clock and follow the continuous evolution of § 3.3 until the next event. This continuation rule applies for every S ≥ 0 S\geq0 S ≥ 0 . In particular, clearing the current chord does not by itself terminate the mechanism: if S = 0 S=0 S = 0 and an active identity remains, the same primitive equations continue to govern the auction while the target is reevaluated as the clock rises.
The mechanism ends in any of the following circumstances:
the stopping allocation (20) is executed;
after all fixed-price operations at the current price have been processed, no active identity remains;
all effective budgets are exhausted.
Upon termination, cancel every unspent effective budget and make no further allocation or payment. The no-active-identity test is made only after a target lump at the same price and the valuation-exit procedure have been processed, so it does not preempt either operation.
There is no additional terminal condition associated with the AMM capacity x 0 x_0 x 0 . At every finite clock price and finite auction state, the chord target satisfies T a m m < x 0 T^{\mathrm{amm}} < x_0 T amm < x 0 , and hence the cumulative allocation satisfies X ≤ T a m m < x 0 X \le T^{\mathrm{amm}} < x_0 X ≤ T amm < x 0 . Thus neither the target nor the allocation reaches the capacity boundary at a finite state. The equality S = 0 S = 0 S = 0 only says that the current chord has been cleared; if an active identity remains, raising the clock eventually produces a target strictly above X X X . Exact settlement, individual rationality, and the incentive properties of this outcome are proved in § 4 .
Observe that the rules above refer to the AMM only through the target T a m m T^{\mathrm{amm}} T amm , its evolution as the clock rises, and the capacity x 0 x_0 x 0 ; the cost curve C C C and its marginal ask a a a appear only to explain what those rules mean for the AMM. § 4 exploits this by proving the guarantees for a general target, and then verifying that T a m m T^{\mathrm{amm}} T amm qualifies.
Proofs for the One-Sided AMM Clinching Mechanism
We now prove that the AMM adaptive clinching mechanism satisfies Sybil-robust incentive compatibility as well as weak Pareto optimality for eligible bids. Before we begin our proof, we first define an abstract target-based clinching mechanism in § 4.1 . This more generalized abstract mechanism allows us to isolate the proof arguments from the particular choice of supply function. Specifically, later in Section A, we point out that the classical ordinary adaptive clinching auction [16 , 4 ] , and its version with exogenous online supply [23 ] , are the special cases in which the target is constant. Thus, our proofs directly imply that these classical adaptive clinching auctions are sybil-proof too.
After defining the abstract target-based mechanism, we derive the explicit continuous rates implied by its primitive conditions. We then verify the abstract requirements directly for the AMM chord target, and establish the structural lemmas for a single run. We next compare a merged run with a Sybil run to prove the desired incentive compatibility properties.
Abstract Target-Based Clinching Mechanism
The AMM clinching mechanism is driven by its chord target T a m m ( p , X , Y ) T^{\mathrm{amm}}(p,X,Y) T amm ( p , X , Y ) , which determines how much cumulative supply is available at each auction state. We now abstract this role from the geometry of the AMM. The resulting target-based mechanism uses the same clinching rules, but allows a general admissible target function. Choosing T a m m T^{\mathrm{amm}} T amm as its target recovers the AMM mechanism.
Definition 4.1 (Abstract target-based mechanism). An abstract target-based mechanism is a five-tuple
T : = ( p ⋆ , σ , T σ , D σ , X ‾ σ ) , \mathcal{T} := (p_{\star}, \sigma, T_{\sigma}, \mathcal{D}_{\sigma}, \overline{X}_{\sigma}), T := ( p ⋆ , σ , T σ , D σ , X σ ) , whose components have the following meanings.
p ⋆ > 0 p_{\star} > 0 p ⋆ > 0 is the initial clock price.
σ \sigma σ is an environment description fixed independently of the submitted bids and common to every bid profile being compared. It contains any non-strategic information that the target rule may consult as the clock advances. If no such information is needed like in the AMM clinching case, σ = ∅ \sigma= \emptyset σ = ∅ and its subscript may be omitted.
T σ T_{\sigma} T σ is the cumulative target rule. At a state ( p , X , Y ) (p, X, Y) ( p , X , Y ) , it specifies the cumulative quantity that may be allocated.
D σ \mathcal{D}_{\sigma} D σ is the domain of auction states on which the target rule is defined.
X ‾ σ ∈ ( 0 , + ∞ ] \overline{X}_{\sigma} \in(0, +\infty] X σ ∈ ( 0 , + ∞ ] is the capacity bound.
Thus T σ T_{\sigma} T σ is a map from D σ \mathcal{D}_{\sigma} D σ into [ 0 , X ‾ σ ] [0, \overline{X}_{\sigma}] [ 0 , X σ ] ; its explicit price argument selects any clock-indexed information contained in σ \sigma σ .
At price p p p , aggregate allocation X X X , and aggregate payment Y Y Y , set
S : = T σ ( p , X , Y ) − X . S := T_{\sigma}(p, X, Y) - X. S := T σ ( p , X , Y ) − X . For an admissible abstract target-based mechanism, T σ ( p , X , Y ) ≥ X T_{\sigma}(p, X, Y) \ge X T σ ( p , X , Y ) ≥ X , so S S S is the part of the cumulative target not yet allocated. For the AMM application, p ⋆ = p 0 p_{\star} = p_{0} p ⋆ = p 0 , σ \sigma σ is trivial, and T σ = T a m m T_{\sigma} = T^{\mathrm{amm}} T σ = T amm ; the full specification is verified in § 4.3 .
Definition 4.2 (Admissible abstract target-based mechanism). An abstract target-based mechanism T \mathcal{T} T is admissible if the following properties hold.
Feasibility and partition independence. For every ( p , X , Y ) ∈ D σ (p, X, Y) \in\mathcal{D}_{\sigma} ( p , X , Y ) ∈ D σ ,
X ≤ T σ ( p , X , Y ) ≤ X ‾ σ , X \le T_{\sigma}(p, X, Y) \le\overline{X}_{\sigma}, X ≤ T σ ( p , X , Y ) ≤ X σ , where the specified capacity X ‾ σ \overline{X}_{\sigma} X σ is common to all bid profiles. The target depends on bidders only through ( X , Y ) (X, Y) ( X , Y ) , and not on their names or on the partition of an aggregate budget among identities.
Fixed-price invariance. If 0 ≤ δ ≤ S 0 \le\delta\le S 0 ≤ δ ≤ S , then the updated state belongs to the domain and
T σ ( p , X + δ , Y + p δ ) = T σ ( p , X , Y ) . (25) T_{\sigma}(p, X + \delta, Y + p\delta) = T_{\sigma}(p, X, Y). \tag*{(25)} T σ ( p , X + δ , Y + p δ ) = T σ ( p , X , Y ) . (25) Target decreases with mark-to-market gain. At a common ( p , σ ) (p, \sigma) ( p , σ ) , for any two states in the domain,
p X − Y ≤ p X ′ − Y ′ ⟹ T σ ( p , X , Y ) ≥ T σ ( p , X ′ , Y ′ ) . (26) pX - Y \le pX' - Y' \quad\Longrightarrow\quad T_{\sigma}(p, X, Y) \ge T_{\sigma}(p, X', Y'). \tag*{(26)} pX − Y ≤ p X ′ − Y ′ ⟹ T σ ( p , X , Y ) ≥ T σ ( p , X ′ , Y ′ ) . (26) Thus a state with the smaller aggregate mark-to-market gain has the weakly larger target. Equality of the gains forces equality of the targets.
Clock regularity. If ( X , Y ) (X,Y) ( X , Y ) is held fixed, the map p ↦ T σ ( p , X , Y ) p \mapsto T_\sigma(p,X,Y) p ↦ T σ ( p , X , Y ) is nondecreasing and right-continuous, is locally of bounded variation, and has only upward jumps. Away from those jumps it is locally absolutely continuous; write
λ σ ( p , X , Y ) : = d d r T σ ( r , X , Y ) ∣ r = p ≥ 0 (27) \lambda_\sigma(p,X,Y) := \left.\frac{\mathrm{d}}{\mathrm{d}r}T_\sigma(r,X,Y)\right|_{r=p} \ge0 \tag*{(27)} λ σ ( p , X , Y ) := d r d T σ ( r , X , Y ) r = p ≥ 0 (27)
for its almost-everywhere frozen-state clock rate.
Eventual supply release. For every ( p , X , Y ) ∈ D σ (p,X,Y) \in D_\sigma ( p , X , Y ) ∈ D σ such that T σ ( p , X , Y ) = X < X ‾ σ T_\sigma(p,X,Y)=X<\overline{X}_\sigma T σ ( p , X , Y ) = X < X σ , there is a price p ′ > p p'>p p ′ > p for which
( p ′ , X , Y ) ∈ D σ and T σ ( p ′ , X , Y ) > X . (28) (p',X,Y) \in D_\sigma\qquad\text{and}\qquad T_\sigma(p',X,Y)>X. \tag*{(28)} ( p ′ , X , Y ) ∈ D σ and T σ ( p ′ , X , Y ) > X . (28)
Thus the target may remain equal to X X X over a waiting interval, but it cannot remain there forever while X X X is strictly below the specified capacity.
The domain is also required to contain ( p ⋆ , 0 , 0 ) (p_\star,0,0) ( p ⋆ , 0 , 0 ) and to be upward closed in its price coordinate: if ( p , X , Y ) ∈ D σ (p,X,Y) \in D_\sigma ( p , X , Y ) ∈ D σ , then ( p ′ , X , Y ) ∈ D σ (p',X,Y) \in D_\sigma ( p ′ , X , Y ) ∈ D σ for every p ′ ≥ p p' \ge p p ′ ≥ p . These are requirements on one abstract target-based mechanism; none refers to an execution, a merged run, or a Sybil run. A state with X = X ‾ σ < + ∞ X=\overline{X}_\sigma<+\infty X = X σ < + ∞ is called capacity-saturated . Feasibility then forces T σ ( p , X , Y ) = X T_\sigma(p,X,Y)=X T σ ( p , X , Y ) = X at every such state.
The target-based clinching mechanism for an admissible Σ \Sigma Σ is obtained from the AMM mechanism of § 3 by replacing its AMM-specific variables as follows:
( p 0 , T a m m , x 0 ) ⟼ ( p ⋆ , T σ , X ‾ σ ) . (29) (p_0,T^{\mathrm{amm}},x_0) \longmapsto(p_\star,T_\sigma,\overline{X}_\sigma). \tag*{(29)} ( p 0 , T amm , x 0 ) ⟼ ( p ⋆ , T σ , X σ ) . (29)
Thus reports are eligible when v i ≥ p ⋆ v_i \ge p_\star v i ≥ p ⋆ , residual supply is S = T σ − X S=T_\sigma-X S = T σ − X , and the target is bounded by X ‾ σ \overline{X}_\sigma X σ . An upward jump of T σ T_\sigma T σ , whether inherent in its price dependence or encoded by σ \sigma σ , is the supply lump in (19) . Every state identity, primitive differential condition, event order, stopping allocation, restoration rule, and continuation rule is otherwise unchanged. The analytical quantity λ σ \lambda_\sigma λ σ in (27) is derived from T σ T_\sigma T σ and is not an additional component of Σ \Sigma Σ . The substitution therefore changes the source of target supply, not the clinching mechanics.
Convention at capacity saturation. Earlier in our AMM clinching mechanism, we never saturate the capacity, that is, T a m m < x 0 T^{\mathrm{amm}}<x_0 T amm < x 0 at every finite state. However, our generalized target-based mechanism may reach capacity saturation at a finite state, so we must explicitly specify what happens afterward. We adopt the following completion convention: attaining capacity does not itself terminate the execution. The clock and ordinary valuation exits continue under the usual rules. Theorem 4.5 shows that this continuation involves no further trade, so we call it the zero-trade completion convention . Allocations and payments are therefore already economically final; the continuation only retains effective budgets until their ordinary valuation exits. This prevents unused budgets from being treated as exhausted merely because the available capacity has been fully allocated.
Derived Form of the Continuous Dynamics
The preceding construction defines the auction through primitive differential conditions, without postulating a trading-rate formula. We now solve those conditions once for an arbitrary admissible abstract target-based mechanism. The resulting identities are consequences of the mechanism and will be used throughout the proofs below.
Lemma 4.3 (Fixed-price accounting). Suppose δ \delta δ units are allocated at price p p p and charged p δ p\delta p δ . Then T σ T_\sigma T σ and h = B − p S h = B - pS h = B − pS are unchanged, while S S S and the buyer’s effective budget decrease by δ \delta δ and p δ p\delta p δ , respectively.
Proof. Target invariance is (25) . The updates are X + = X + δ X^+ = X + \delta X + = X + δ , B + = B − p δ B^+ = B - p\delta B + = B − p δ , and S + = T σ − X + = S − δ S^+ = T_\sigma- X^+ = S - \delta S + = T σ − X + = S − δ . Therefore
B + − p S + = B − p δ − p ( S − δ ) = B − p S = h . B^+ - pS^+ = B - p\delta- p(S - \delta) = B - pS = h. B + − p S + = B − p δ − p ( S − δ ) = B − pS = h .
Lemma 4.4 (Explicit continuous dynamics). Consider an event-free interval on which the frozen-state target rate λ σ \lambda_\sigma λ σ exists, and write c = ∣ C l i n c h ∣ c = \lvert\mathrm{Clinch}\rvert c = ∣ Clinch ∣ . The primitive conditions (16) –(18) , after the target substitution (29) , uniquely determine the state derivatives almost everywhere. Define the derived rate
γ : = S ˙ + p λ σ . (30) \gamma:= \dot{S} + p\lambda_\sigma. \tag*{(30)} γ := S ˙ + p λ σ . (30) Then every identity follows
d x i d p = { γ / p , i ∈ C l i n c h , 0 , i ∉ C l i n c h , d y i d p = { γ , i ∈ C l i n c h , 0 , i ∉ C l i n c h . (31) \frac{\mathrm{d}x_i}{\mathrm{d}p} =
\begin{cases}
\gamma/p, & i \in\mathrm{Clinch},\\
0, & i \notin\mathrm{Clinch},
\end{cases}
\qquad
\frac{\mathrm{d}y_i}{\mathrm{d}p} =
\begin{cases}
\gamma, & i \in\mathrm{Clinch},\\
0, & i \notin\mathrm{Clinch}.
\end{cases} \tag*{(31)} d p d x i = { γ / p , 0 , i ∈ Clinch , i ∈ / Clinch , d p d y i = { γ , 0 , i ∈ Clinch , i ∈ / Clinch . (31) d b i d p = { − γ , i ∈ C l i n c h , 0 , i ∉ C l i n c h . (32) \frac{\mathrm{d}b_i}{\mathrm{d}p} =
\begin{cases}
-\gamma, & i \in\mathrm{Clinch},\\
0, & i \notin\mathrm{Clinch}.
\end{cases} \tag*{(32)} d p d b i = { − γ , 0 , i ∈ Clinch , i ∈ / Clinch . (32) The aggregate variables satisfy
d h d p = − γ , d T σ d p = λ σ , d S d p = λ σ − c γ p . (33) \frac{\mathrm{d}h}{\mathrm{d}p} = -\gamma,\qquad
\frac{\mathrm{d}T_\sigma}{\mathrm{d}p} = \lambda_\sigma,\qquad
\frac{\mathrm{d}S}{\mathrm{d}p} = \lambda_\sigma- \frac{c\gamma}{p}. \tag*{(33)} d p d h = − γ , d p d T σ = λ σ , d p d S = λ σ − p c γ . (33) In particular, h h h is nonincreasing. If, after all same-price events have been processed, S = 0 S = 0 S = 0 and there is exactly one active identity i i i , then i i i is the sole clincher and
d x i d p = λ σ , d y i d p = p λ σ , d b i d p = − p λ σ , d S d p = 0. (34) \frac{\mathrm{d}x_i}{\mathrm{d}p} = \lambda_\sigma,\qquad
\frac{\mathrm{d}y_i}{\mathrm{d}p} = p\lambda_\sigma,\qquad
\frac{\mathrm{d}b_i}{\mathrm{d}p} = -p\lambda_\sigma,\qquad
\frac{\mathrm{d}S}{\mathrm{d}p} = 0. \tag*{(34)} d p d x i = λ σ , d p d y i = p λ σ , d p d b i = − p λ σ , d p d S = 0. (34) Thus the sole active identity purchases every continuously appearing target increment at its appearance price.
Proof. First suppose c > 0 c > 0 c > 0 . The tightness condition in (18) requires every clincher’s budget to have the same derivative as h h h . Hence their common payment rate can be written
ρ : = − d h d p = d y i d p = − d b i d p , i ∈ C l i n c h . \rho:= -\frac{\mathrm{d}h}{\mathrm{d}p}
= \frac{\mathrm{d}y_i}{\mathrm{d}p}
= -\frac{\mathrm{d}b_i}{\mathrm{d}p},
\qquad i \in\mathrm{Clinch}. ρ := − d p d h = d p d y i = − d p d b i , i ∈ Clinch .
Current-price charging then gives
d B d p = − c ρ , d X d p = c ρ p , d Y d p = c ρ . (35) \frac{dB}{dp}=-c\rho,\qquad\frac{dX}{dp}=\frac{c\rho}{p},\qquad\frac{dY}{dp}=c\rho. \tag*{(35)} d p d B = − c ρ , d p d X = p c ρ , d p d Y = c ρ . (35)
The last two derivatives point in the fixed-price direction. By (25) , they do not move the target; only the frozen-state clock motion does. Therefore
d T σ d p = λ σ , d S d p = λ σ − c ρ p . \frac{dT_\sigma}{dp}=\lambda_\sigma,\qquad\frac{dS}{dp}=\lambda_\sigma-\frac{c\rho}{p}. d p d T σ = λ σ , d p d S = λ σ − p c ρ .
Differentiating h = B − p S h=B-pS h = B − pS and using (35) yields
− ρ = − c ρ − S − p ( λ σ − c ρ p ) = − S − p λ σ . -\rho=-c\rho-S-p\left(\lambda_\sigma-\frac{c\rho}{p}\right)=-S-p\lambda_\sigma. − ρ = − c ρ − S − p ( λ σ − p c ρ ) = − S − p λ σ .
Consequently ρ = S + p λ σ = γ \rho=S+p\lambda_\sigma=\gamma ρ = S + p λ σ = γ . Since S ≥ 0 S\ge0 S ≥ 0 and λ σ ≥ 0 \lambda_\sigma\ge0 λ σ ≥ 0 , the resulting allocation rates are nonnegative, as required by the primitive conditions. This proves existence and uniqueness of (31) –(33) when c > 0 c>0 c > 0 .
If c = 0 c=0 c = 0 , (17) fixes all individual states. Thus B ′ = X ′ = Y ′ = 0 B'=X'=Y'=0 B ′ = X ′ = Y ′ = 0 , while target evolution gives T σ ′ = λ σ T_\sigma'=\lambda_\sigma T σ ′ = λ σ . Differentiating S = T σ − X S=T_\sigma-X S = T σ − X and h = B − p S h=B-pS h = B − pS gives the same aggregate identities with c = 0 c=0 c = 0 . Finally, when S = 0 S=0 S = 0 and exactly one active identity remains, its outside demand is zero, so it is the sole clincher. Setting c = 1 c=1 c = 1 and S = 0 S=0 S = 0 in the formulas just proved gives (34) .
Lemma 4.5 (Capacity saturation is a zero-trade tail). Suppose a run reaches a capacity-saturated state. Thereafter its aggregate and individual allocations and payments remain constant. The clock and the ordinary valuation-exit accounting may continue, but no identity makes a further purchase.
Proof. At saturation, X = X ‾ σ X=\overline{X}_\sigma X = X σ . At every allowed future state, target feasibility gives X ≤ T σ ≤ X ‾ σ = X X\le T_\sigma\le\overline{X}_\sigma=X X ≤ T σ ≤ X σ = X . Hence T σ = X T_\sigma=X T σ = X , S = 0 S=0 S = 0 , and λ σ = 0 \lambda_\sigma=0 λ σ = 0 . The derived rate is therefore γ = S + p λ σ = 0 \gamma=S+p\lambda_\sigma=0 γ = S + p λ σ = 0 , so the continuous dynamics make no trade. There can be no future target lump. At a valuation exit with another active identity remaining, the stopping test fails, the exiting budgets are cancelled, and h ⋆ = B h^\star=B h ⋆ = B ; since every remaining budget is at most B B B , the restoration rule makes no purchase. When no active identity remains, the run terminates with zero residual supply. Thus no event in the completed tail changes an allocation or payment.
The AMM Target Specification Is Admissible
For use in the proof, define the marginal-supply function
Z ( p ) : = sup { z ∈ [ 0 , x 0 ) : a ( z ) ≤ p } , p ≥ p 0 . (36) Z(p):=\sup\{z\in[0,x_0):a(z)\le p\},\qquad p\ge p_0. \tag*{(36)} Z ( p ) := sup { z ∈ [ 0 , x 0 ) : a ( z ) ≤ p } , p ≥ p 0 . (36)
Thus Z ( p ) Z(p) Z ( p ) is the amount of pool supply available at a right marginal ask of at most p p p . If a a a is strictly increasing and continuous, then Z ( p ) = a − 1 ( p ) Z(p)=a^{-1}(p) Z ( p ) = a − 1 ( p ) . The generalized-inverse definition in (36) continues to apply when a a a has flat segments or jumps, because C C C is convex but need not be strictly convex or differentiable everywhere.
For the AMM, use the state domain
D a m m : = { ( p , X , Y ) : p ≥ p 0 , 0 ≤ X < x 0 , Y ≥ C ( X ) } . \mathcal{D}^{\mathrm{amm}} := \{(p,X,Y): p \ge p_0,\ 0 \le X < x_0,\ Y \ge C(X)\}. D amm := {( p , X , Y ) : p ≥ p 0 , 0 ≤ X < x 0 , Y ≥ C ( X )} .
The inequality Y ≥ C ( X ) Y \ge C(X) Y ≥ C ( X ) says that the current auction state lies on or above the pool cost curve.
Proposition 4.6 (Admissibility of the AMM target specification). Let σ a m m \sigma^{\mathrm{amm}} σ amm be the trivial environment description. If the reserve curve satisfies Theorem 2.1, then
T a m m : = ( p 0 , σ a m m , T a m m , D a m m , x 0 ) \mathcal{T}^{\mathrm{amm}} := (p_0,\sigma^{\mathrm{amm}},T^{\mathrm{amm}},\mathcal{D}^{\mathrm{amm}},x_0) T amm := ( p 0 , σ amm , T amm , D amm , x 0 ) is an admissible abstract target-based mechanism with unattained capacity. Its target-based clinching mechanism is the mechanism of § 3 .
Proof. Fix ( p , X , Y ) ∈ D a m m (p,X,Y) \in\mathcal{D}^{\mathrm{amm}} ( p , X , Y ) ∈ D amm and write g p ( z ) = C ( z ) − Y − p ( z − X ) g_p(z) = C(z) - Y - p(z-X) g p ( z ) = C ( z ) − Y − p ( z − X ) . The sublevel set
{ z ∈ [ X , x 0 ) : g p ( z ) ≤ 0 } \{z \in[X,x_0): g_p(z) \le0\} { z ∈ [ X , x 0 ) : g p ( z ) ≤ 0 } contains X X X , is an interval by convexity, and is bounded away from x 0 x_0 x 0 because C ( z ) → + ∞ C(z) \to+\infty C ( z ) → + ∞ . It therefore has a right endpoint T a m m ∈ [ X , x 0 ) T^{\mathrm{amm}} \in[X,x_0) T amm ∈ [ X , x 0 ) . Continuity gives
C ( T a m m ) = Y + p ( T a m m − X ) . (37) C(T^{\mathrm{amm}}) = Y + p(T^{\mathrm{amm}}-X). \tag*{(37)} C ( T amm ) = Y + p ( T amm − X ) . (37) The equality also holds when the target equals X X X , because g p ( X ) < 0 g_p(X) < 0 g p ( X ) < 0 would make a right neighborhood of X X X feasible. The right derivative of g p g_p g p at its right endpoint is nonnegative, hence a ( T a m m ) ≥ p a(T^{\mathrm{amm}}) \ge p a ( T amm ) ≥ p . This proves target feasibility and the capacity bound. The formula uses no individual reports, proving partition independence.
For a fixed-price purchase 0 ≤ δ ≤ T a m m − X 0 \le\delta\le T^{\mathrm{amm}} - X 0 ≤ δ ≤ T amm − X , every candidate z ≥ X + δ z \ge X+\delta z ≥ X + δ satisfies
C ( z ) − ( Y + p δ ) − p ( z − ( X + δ ) ) = C ( z ) − Y − p ( z − X ) . \begin{aligned}
C(z) - (Y+p\delta) - p(z-(X+\delta)) &= C(z)-Y-p(z-X).
\end{aligned} C ( z ) − ( Y + p δ ) − p ( z − ( X + δ )) = C ( z ) − Y − p ( z − X ) . Thus the right endpoint is unchanged. Moreover, convexity and the endpoint inequalities imply g p ( z ) ≤ 0 g_p(z) \le0 g p ( z ) ≤ 0 for every z ∈ [ X , T a m m ] z \in[X,T^{\mathrm{amm}}] z ∈ [ X , T amm ] ; consequently the updated state still satisfies Y + p δ ≥ C ( X + δ ) Y+p\delta\ge C(X+\delta) Y + p δ ≥ C ( X + δ ) . This proves fixed-price invariance and preservation of the domain.
To prove that the target decreases with mark-to-market gain, put
ψ p ( z ) : = p z − C ( z ) . \psi_p(z) := pz-C(z). ψ p ( z ) := p z − C ( z ) . The chord condition is ψ p ( z ) ≥ p X − Y \psi_p(z) \ge pX-Y ψ p ( z ) ≥ pX − Y , where p X − Y pX-Y pX − Y is the aggregate mark-to-market gain. The function ψ p \psi_p ψ p is concave, reaches its rightmost maximum at Z ( p ) Z(p) Z ( p ) , and is strictly decreasing on [ Z ( p ) , x 0 ) [Z(p),x_0) [ Z ( p ) , x 0 ) . The right endpoint of every nonempty superlevel set lies in that interval. Raising the required mark-to-market gain therefore weakly moves the right endpoint to the left, which is exactly (26).
If the state is held fixed and p p p rises, then for every z > X z>X z > X the quantity g p ( z ) g_p(z) g p ( z ) weakly decreases. Hence the chord target is nondecreasing. Convexity gives right-continuity and local bounded variation. On a continuous nondegenerate portion with S > 0 S>0 S > 0 and a ( T a m m ) > p a(T^{\mathrm{amm}})>p a ( T amm ) > p , differentiating (37) with ( X , Y ) (X,Y) ( X , Y ) fixed gives
λ a m m = T a m m − X a ( T a m m ) − p = S a ( T a m m ) − p . (38) \lambda^{\mathrm{amm}} = \frac{T^{\mathrm{amm}}-X}{a(T^{\mathrm{amm}})-p} = \frac{S}{a(T^{\mathrm{amm}})-p}. \tag*{(38)} λ amm = a ( T amm ) − p T amm − X = a ( T amm ) − p S . (38)
The only upward discontinuity can occur from a settled state ( X , C ( X ) ) (X,C(X)) ( X , C ( X )) when the clock reaches a ( X ) a(X) a ( X ) and C C C is linear from X X X to the right. The target then jumps to the right endpoint Z ( p ) Z(p) Z ( p ) of that linear piece. Indeed, the tangent line of slope p = a ( X ) p=a(X) p = a ( X ) agrees with C C C precisely on the maximal such piece and lies below C C C afterward. These are exactly the supply lumps specified in (19) .
Finally, no state with X < x 0 X<x_0 X < x 0 exhausts all future AMM supply: because C C C is finite at X X X and diverges only as z ↑ x 0 z \uparrow x_0 z ↑ x 0 , sufficiently large prices produce a target strictly above X X X . The capacity x 0 x_0 x 0 is never attained. For the AMM, substituting (38) into the derived rate (30) gives
γ = S + p S a ( T a m m ) − p = S a ( T a m m ) a ( T a m m ) − p . \gamma= S + p\frac{S}{a(T^{\mathrm{amm}})-p}
= S\frac{a(T^{\mathrm{amm}})}{a(T^{\mathrm{amm}})-p}. γ = S + p a ( T amm ) − p S = S a ( T amm ) − p a ( T amm ) .
At a settled state with one active identity, the target-increment identity (34) traces the generalized marginal-supply path Z Z Z , including its linear-piece jumps. Hence every AMM interpretation stated in § 3 follows from the uniform substitution (29) .
Single-Run Structure
The next lemmas concern one execution of the target-based clinching mechanism associated with an admissible abstract target-based mechanism. They are proved before any two executions are coupled.
Lemma 4.7 (Event restoration and stopping). At an event price, include the entire target jump before evaluating the stopping test. Let B A B_A B A and B E B_E B E be the total active and exiting budgets at that moment. Then:
the stopping test is equivalent to B E ≥ h B_E \ge h B E ≥ h ;
if it fails, cancelling all exiting budgets gives h ⋆ = h − B E > 0 h^\star= h-B_E>0 h ⋆ = h − B E > 0 , and the one-shot purchases ( b i − h ⋆ ) + / p (b_i-h^\star)_+/p ( b i − h ⋆ ) + / p are feasible and restore b i ≤ h ⋆ b_i\le h^\star b i ≤ h ⋆ for every active identity;
the truth value of the stopping test does not change during the fixed-price purchases; and
the exit of a clinching identity is a stopping event.
Proof. At the test, B = B A + B E B=B_A+B_E B = B A + B E , so
B A ≤ p S = B − h ⟺ B E ≥ h . B_A \le pS = B-h \quad\Longleftrightarrow\quad B_E \ge h. B A ≤ pS = B − h ⟺ B E ≥ h .
If the test fails, B E < h B_E<h B E < h . Cancellation changes B B B , and hence h h h , by − B E -B_E − B E , giving h ⋆ = h − B E > 0 h^\star=h-B_E>0 h ⋆ = h − B E > 0 . Reducing every budget above h ⋆ h^\star h ⋆ to h ⋆ h^\star h ⋆ restores the water-level inequalities. The total quantity required is feasible because
∑ i ( b i − h ⋆ ) + ≤ B A − h ⋆ = p S . \sum_i (b_i-h^\star)_+ \le B_A-h^\star=pS. i ∑ ( b i − h ⋆ ) + ≤ B A − h ⋆ = pS .
The inequality is immediate if no budget exceeds h ⋆ h^\star h ⋆ ; otherwise it follows by subtracting at least one copy of h ⋆ h^\star h ⋆ from a subsum of B A B_A B A . By Theorem 4.3, every such purchase leaves h ⋆ h^\star h ⋆ fixed and reduces active demand and residual supply by the same amount, proving the second and third statements. Finally, immediately before exiting, a clincher has b i = h b_i = h b i = h . A simultaneous target jump can only lower the newly computed h h h , so the total exiting budget is at least the post-jump water level. The first statement then implies stopping.
Lemma 4.8 (Allocation structure and clincher persistence). In a continuing run, the following statements hold.
The supply invariant is equivalent to
b i ≤ h ( i ∈ A c t i v e ) , C l i n c h = { i ∈ A c t i v e : b i = h } . (39) b_i \le h \quad(i \in\mathrm{Active}), \qquad\mathrm{Clinch} = \{i \in\mathrm{Active} : b_i = h\}. \tag*{(39)} b i ≤ h ( i ∈ Active ) , Clinch = { i ∈ Active : b i = h } . (39) An identity that has never clinched has received no allocation and made no payment.
Once an identity clinches, it remains a clincher until the run ends.
No positive effective budget is exhausted in a continuing run. Hence every identity with v i > p v_i > p v i > p and positive reported budget is active, and
b i = min { q i , h } ( i ∈ A c t i v e ) . (40) b_i = \min\{q_i, h\} \qquad(i \in\mathrm{Active}). \tag*{(40)} b i = min { q i , h } ( i ∈ Active ) . (40)
Proof. Because p D − i = B − b i pD_{-i} = B - b_i p D − i = B − b i , the inequality S ≤ D − i S \le D_{-i} S ≤ D − i is exactly b i ≤ B − p S = h b_i \le B - pS = h b i ≤ B − pS = h , with equality precisely for a clincher. This proves the first statement.
The mechanism allocates only to a current clincher, to an active identity in a restoration purchase, or as part of a stopping allocation. A restoration buyer finishes with budget equal to the water level and therefore becomes a clincher; a stopping allocation ends the run. When S = 0 S = 0 S = 0 and one active identity remains, that identity is a clincher because the demand of all other identities is zero. Thus a bidder that has never clinched has not traded in any continuing run, proving the second statement.
Between events, Theorem 4.4 decreases a clincher’s budget and h h h at the same rate. At a nonstopping event, the new level is positive and every active budget above it is reduced to it; in particular, every prior clincher is returned to equality. At an event where a clincher exits, Theorem 4.7 says that the run stops. When S = 0 S = 0 S = 0 and one active identity remains, the primitive tightness condition likewise preserves equality because that identity holds the entire effective budget. This proves persistence.
On a continuous interval a clincher can reach budget zero only when h = 0 h = 0 h = 0 , at which point every active budget is zero. At a nonstopping event the post-event level is strictly positive. Therefore exhaustion of a positive effective budget ends the run. If an active identity has never clinched, the second statement gives b i = q i ≤ h b_i = q_i \le h b i = q i ≤ h ; if it has clinched, persistence gives b i = h ≤ q i b_i = h \le q_i b i = h ≤ q i . This proves (40) and the fourth statement.
Lemma 4.9 (Exited identities in a continuing run). If a run continues after price p p p , every identity j j j with v j ≤ p v_j \le p v j ≤ p has x j = y j = 0 x_j = y_j = 0 x j = y j = 0 , and its entire unspent reported budget was cancelled when it exited.
Proof. If j j j had clinched before its exit, persistence would make it a clincher at that exit, which would stop the run by Theorem 4.7. If it first received allocation in the stopping allocation at its exit, the run would again have ended. The allocation-structure statement in Theorem 4.8 therefore gives x j = y j = 0 x_j = y_j = 0 x j = y j = 0 , and the nonstopping exit rule cancels its full budget.
Lemma 4.10 (Sole survivor for the AMM target). If a reachable AMM run continues at a state with S = 0 S = 0 S = 0 and p > p 0 p > p_0 p > p 0 , then exactly one identity has positive effective budget. In particular, at most one active identity remains.
Proof. Since S = 0 S = 0 S = 0 , the definition of the water level gives h = B h = B h = B . If some identity clinches, its budget is b i = h = B b_i = h = B b i = h = B by (39) , so every other effective budget is zero.
Suppose instead that nobody clinches. Clincher persistence implies that nobody has previously clinched, and the allocation-structure statement then gives X = Y = 0 X = Y = 0 X = Y = 0 . But at this state and any p > p 0 p > p_0 p > p 0 , the function C ( z ) − p z C(z) - pz C ( z ) − p z has right derivative p 0 − p < 0 p_0 - p < 0 p 0 − p < 0 at zero. It is therefore negative for all sufficiently small z > 0 z > 0 z > 0 , so T a m m ( p , 0 , 0 ) > 0 T^{\mathrm{amm}}(p,0,0) > 0 T amm ( p , 0 , 0 ) > 0 . This contradicts S = 0 S = 0 S = 0 . Thus a clincher exists and is the unique identity with positive effective budget. A continuing run has at least one such identity, completing the proof.
Feasibility and Efficiency
We now specialize the single-run structure to the AMM target. All statements in this subsection concern truthful one-sided sell-Y Y Y participation.
Theorem 4.11 (Exact settlement and individual rationality). Every completed one-sided AMM clinching run is exact-settlement feasible. On a truthful profile it is individually rational: for every identity i i i ,
0 ≤ y i ≤ Q i , V i x i − y i ≥ 0. (41) 0 \le y_i \le Q_i,\qquad V_i x_i - y_i \ge0. \tag*{(41)} 0 ≤ y i ≤ Q i , V i x i − y i ≥ 0. (41) Proof. We first prove exact settlement. Consider a stopping allocation and use the notation B A B_A B A , B E B_E B E , h h h immediately after a possible lump has been included. If h ≥ 0 h \ge0 h ≥ 0 , the stopping condition B E ≥ h B_E \ge h B E ≥ h and the proportional exit rule allocate
B A p + B E − h p = B − h p = S \frac{B_A}{p} + \frac{B_E-h}{p} = \frac{B-h}{p} = S p B A + p B E − h = p B − h = S units, so the final chord is cleared in full. Fixed-price invariance and the chord equality give
X f = T a m m , Y f = Y + p ( T a m m − X ) = C ( T a m m ) = C ( X f ) . X_f = T^{\mathrm{amm}},\qquad Y_f = Y + p(T^{\mathrm{amm}} - X) = C(T^{\mathrm{amm}}) = C(X_f). X f = T amm , Y f = Y + p ( T amm − X ) = C ( T amm ) = C ( X f ) . If h < 0 h < 0 h < 0 , the stopping event must follow a target lump: away from an upward target jump, h h h starts nonnegative, is continuous and nonincreasing by Theorem 4.4, and reaching zero exhausts all active budgets; a nonstopping exit leaves the positive level described in Theorem 4.7. At a lump, the selected chord is a linear piece of C C C of slope p p p . Every active and exiting identity exhausts its budget, leaving the suffix − h / p -h/p − h / p unallocated, but every purchased prefix still satisfies
Y f = Y + p ( X f − X ) = C ( X f ) . Y_f = Y + p(X_f - X) = C(X_f). Y f = Y + p ( X f − X ) = C ( X f ) . Every other terminal case has S = 0 S = 0 S = 0 . The target equality (37) then gives Y f = C ( X f ) Y_f = C(X_f) Y f = C ( X f ) . In particular, (34) shows that the one-active boundary path moves directly along the pool curve. Thus every terminal state satisfies (9) ; all pool output is assigned and all payments enter the pool.
For individual rationality, the mechanism never charges more than the reported budget, so truthful reporting gives y i ≤ q i = Q i y_i \le q_i = Q_i y i ≤ q i = Q i . Every increment received while
active is priced below v i = V i v_i = V_i v i = V i , and every increment received at its exit is priced exactly V i V_i V i . Therefore
y i = ∫ p d x i ≤ V i ∫ d x i = V i x i . y_i = \int p\,\mathrm{d}x_i \le V_i \int\mathrm{d}x_i = V_i x_i. y i = ∫ p d x i ≤ V i ∫ d x i = V i x i .
This includes fixed-price event purchases and Stieltjes jumps. Hence (41) holds.
For a truthful bidder, let
r i : = Q i − y i r_i := Q_i-y_i r i := Q i − y i
denote its terminal unspent Y Y Y -budget, and let a ( X f ) = C + ′ ( X f ) a(X_f)=C'_+(X_f) a ( X f ) = C + ′ ( X f ) be the terminal right marginal pool ask.
Lemma 4.12 (Terminal certificate). Every completed truthful one-sided run satisfies:
if x j > 0 x_j>0 x j > 0 and V i > V j V_i>V_j V i > V j , then r i = 0 r_i=0 r i = 0 ; and
if r i > 0 r_i>0 r i > 0 , then V i ≤ a ( X f ) V_i\le a(X_f) V i ≤ a ( X f ) .
Proof. For the first statement, consider how identity j j j first receives allocation. If it receives allocation while clinching or in a restoration purchase, it remains a clincher until the run ends. If the run reaches its exit at V j V_j V j , that exit stops the run; if the run ends earlier, both i i i and j j j are still active. In either case the stopping rule gives identity i i i its full remaining demand and exhausts its budget. If j j j first receives allocation in that stopping event, the same conclusion follows directly from the stopping rule. If j j j receives allocation in the one-active boundary regime, every other effective budget, including that of the higher-valued identity i i i , is already zero. These cases exhaust the allocation rules and prove item 1.
Let p f p_f p f be the terminal clock price. We first note that
p f ≤ a ( X f ) . (42) p_f \le a(X_f). \tag*{(42)} p f ≤ a ( X f ) . (42)
At a fully cleared chord this follows from a ( T a m m ) ≥ p f a(T^{\mathrm{amm}})\ge p_f a ( T amm ) ≥ p f ; at a partial lump it follows because the final point lies on a linear piece of slope p f p_f p f . In the one-active boundary regime, the bidder either waits below the next ask or trades at the marginal ask, so the same inequality holds.
If identity i i i exited, then V i ≤ p f V_i\le p_f V i ≤ p f , and (42) proves item 2. If it did not exit and r i > 0 r_i>0 r i > 0 , suppose for contradiction that V i > a ( X f ) V_i>a(X_f) V i > a ( X f ) . Exact settlement places the state at ( X f , C ( X f ) ) (X_f,C(X_f)) ( X f , C ( X f )) . By right continuity of the convex cost, a sufficiently small additional amount of X X X has average incremental cost strictly below V i V_i V i , and i i i has enough value and positive residual budget to purchase some such amount. The continuation rule would not have terminated at X f X_f X f , a contradiction.
Theorem 4.13 (Weak Pareto optimality in the sell-Y Y Y direction). The truthful one-sided AMM clinching outcome is weakly Pareto optimal for eligible bids in the sense of Theorem 2.7.
Proof. First consider an additional internal trade among eligible users. If every user has r i = 0 r_i=0 r i = 0 , nobody holds Y Y Y that can be tendered, while every holder values its X X X positively; a Pareto improvement is impossible. Otherwise set
λ : = max { V i : r i > 0 } . \lambda:= \max\{V_i:r_i>0\}. λ := max { V i : r i > 0 } .
Item 1 of Theorem 4.12 implies that every user holding positive X X X has value at least λ \lambda λ , while every user able to tender Y Y Y has value at most λ \lambda λ .
Represent a proposed internal trade by changes ( δ x i , δ y i ) i (\delta x_i,\delta y_i)_i ( δ x i , δ y i ) i in user holdings. Conservation gives ∑ i δ x i = ∑ i δ y i = 0 \sum_i \delta x_i=\sum_i \delta y_i=0 ∑ i δ x i = ∑ i δ y i = 0 , and the utility change is V i δ x i + δ y i V_i\delta x_i+\delta y_i V i δ x i + δ y i . Let Q = ∑ δ x i > 0 δ x i Q=\sum_{\delta x_i>0}\delta x_i Q = ∑ δ x i > 0 δ x i . A user paying Y Y Y must have r i > 0 r_i>0 r i > 0 , and weak improvement requires
− δ y i ≤ V i δ x i ≤ λ δ x i . -\delta y_i \le V_i\delta x_i \le\lambda\delta x_i. − δ y i ≤ V i δ x i ≤ λ δ x i .
Thus buyers can pay at most λ Q \lambda Q λ Q . Every supplier of X X X has positive initial X X X -holdings after the mechanism and hence value at least λ \lambda λ ; weak improvement requires
δ y j ≥ V j ( − δ x j ) ≥ λ ( − δ x j ) . \delta y_j \ge V_j(-\delta x_j) \ge\lambda(-\delta x_j). δ y j ≥ V j ( − δ x j ) ≥ λ ( − δ x j ) .
Suppliers therefore require at least λ Q \lambda Q λ Q . Conservation forces equality throughout, so every participant’s utility change is zero. No strict Pareto improvement exists.
It remains to consider an additional same-direction pool trade. Exact settlement starts it from ( X f , C ( X f ) ) (X_f,C(X_f)) ( X f , C ( X f )) . Buying δ > 0 \delta>0 δ > 0 more units of X X X costs at least
C ( X f + δ ) − C ( X f ) ≥ a ( X f ) δ . C(X_f+\delta)-C(X_f)\ge a(X_f)\delta. C ( X f + δ ) − C ( X f ) ≥ a ( X f ) δ .
Any bidder able to fund the trade has r i > 0 r_i>0 r i > 0 , and therefore V i ≤ a ( X f ) V_i\le a(X_f) V i ≤ a ( X f ) by item 2 of the terminal certificate. Its utility change is nonpositive. This proves both clauses of the one-sided restriction of Theorem 2.7.
Sybil-Robust Incentive Compatibility
Fix a physical sell-Y Y Y bidder with true type ( V , Q ) (V,Q) ( V , Q ) , where V ≥ p ⋆ V\ge p_\star V ≥ p ⋆ . In the merged run M \mathcal{M} M , it submits the single report ( V , Q ) (V,Q) ( V , Q ) . In the Sybil run S \mathcal{S} S , it submits a finite set G G G of sell-Y Y Y identities
( v i , q i ) i ∈ G , q G : = ∑ i ∈ G q i ≤ Q . (43) (v_i,q_i)_{i\in G}, \qquad q_G:=\sum_{i\in G}q_i\le Q. \tag*{(43)} ( v i , q i ) i ∈ G , q G := i ∈ G ∑ q i ≤ Q . (43)
The set N N N of outside identities, their reports, and the exogenous target state are identical in the two runs. Every unit allocated to an identity in G G G has the physical bidder’s true value V V V . Thus the two utilities to be compared are
U G M = V X G M − Y G M , U G S = V X G S − Y G S . U_G^{\mathcal{M}}=VX_G^{\mathcal{M}}-Y_G^{\mathcal{M}}, \qquad U_G^{\mathcal{S}}=VX_G^{\mathcal{S}}-Y_G^{\mathcal{S}}. U G M = V X G M − Y G M , U G S = V X G S − Y G S .
Lemma 4.14 (Capping value overreports ). Replacing every Sybil value report v i v_i v i by min { v i , V } \min\{v_i,V\} min { v i , V } weakly increases the physical bidder’s true utility.
Proof. The original and capped executions coincide below price V V V , because value reports affect the mechanism only when identities exit. Allocations made at price V V V have zero true marginal surplus, whereas allocations made above V V V have negative true marginal surplus V − p V-p V − p . Capping all overreports simultaneously removes only zero- or negative-surplus trades and cannot remove any positive-surplus trade.
For any fixed set of identities I \mathcal{I} I , let X I ( p ) X_{\mathcal{I}}(p) X I ( p ) and Y I ( p ) Y_{\mathcal{I}}(p) Y I ( p ) denote its cumulative allocation and payment through clock price p p p . If a run ends, extend both quantities constantly. Define its mark-to-market gain by
Γ I ( p ) : = p X I ( p ) − Y I ( p ) . (44) \Gamma_{\mathcal{I}}(p):=pX_{\mathcal{I}}(p)-Y_{\mathcal{I}}(p). \tag*{(44)} Γ I ( p ) := p X I ( p ) − Y I ( p ) . (44)
Lemma 4.15 (Mark-to-market identity). Under current-price charging,
Γ I ( p ) = ∫ p ⋆ p X I ( s ) d s . \Gamma_{\mathcal{I}}(p)=\int_{p_\star}^{p}X_{\mathcal{I}}(s)\,\mathrm{d}s. Γ I ( p ) = ∫ p ⋆ p X I ( s ) d s . In particular, Γ I \Gamma_{\mathcal{I}} Γ I is continuous across fixed-price purchases and is locally absolutely continuous, with derivative X I X_{\mathcal{I}} X I almost everywhere. If every identity in I \mathcal{I} I reports at most V V V , then its aggregate true utility is Γ I ( V ) \Gamma_{\mathcal{I}}(V) Γ I ( V ) .
Proof. Current-price charging gives the Stieltjes identity Y I ( p ) = ∫ [ p ⋆ , p ] s d X I ( s ) Y_{\mathcal{I}}(p)=\int_{[p_\star,p]}s\,\mathrm{d}X_{\mathcal{I}}(s) Y I ( p ) = ∫ [ p ⋆ , p ] s d X I ( s ) . Integration by parts yields
p X I ( p ) − Y I ( p ) = p ⋆ X I ( p ⋆ ) − Y I ( p ⋆ ) + ∫ p ⋆ p X I ( s ) d s . pX_{\mathcal{I}}(p)-Y_{\mathcal{I}}(p)=p_\star X_{\mathcal{I}}(p_\star)-Y_{\mathcal{I}}(p_\star)+\int_{p_\star}^{p}X_{\mathcal{I}}(s)\,\mathrm{d}s. p X I ( p ) − Y I ( p ) = p ⋆ X I ( p ⋆ ) − Y I ( p ⋆ ) + ∫ p ⋆ p X I ( s ) d s .
Every allocation at the initial price is charged p ⋆ p_\star p ⋆ , so the first two terms cancel. A jump of X I X_{\mathcal{I}} X I at price p p p is accompanied by the payment jump p Δ X I p\,\Delta X_{\mathcal{I}} p Δ X I , making Γ I \Gamma_{\mathcal{I}} Γ I continuous. If all reports are at most V V V , no member of I \mathcal{I} I buys above V V V , and evaluating (44) at V V V gives its true utility.
For a run R ∈ { M , S } \mathcal{R}\in\{\mathcal{M},\mathcal{S}\} R ∈ { M , S } , write B N R B_N^{\mathcal{R}} B N R for the outsiders’ total effective remaining budget and define
W N R : = X N R + B N R p . (45) W_N^{\mathcal{R}}:=X_N^{\mathcal{R}}+\frac{B_N^{\mathcal{R}}}{p}. \tag*{(45)} W N R := X N R + p B N R . (45)
Thus W N R W_N^{\mathcal{R}} W N R is the outsiders’ quantity-denominated wealth in run R \mathcal{R} R : the X X X they have already received plus the amount of X X X their remaining effective budget could purchase at the current price. At and after a terminal state, all effective budgets are set to zero for this accounting convention. Put
GainGap G ( p ) : = Γ G M ( p ) − Γ G S ( p ) , GainGap N ( p ) : = Γ N S ( p ) − Γ N M ( p ) . \operatorname{GainGap}_G(p):=\Gamma_G^{\mathcal{M}}(p)-\Gamma_G^{\mathcal{S}}(p),\qquad\operatorname{GainGap}_N(p):=\Gamma_N^{\mathcal{S}}(p)-\Gamma_N^{\mathcal{M}}(p). GainGap G ( p ) := Γ G M ( p ) − Γ G S ( p ) , GainGap N ( p ) := Γ N S ( p ) − Γ N M ( p ) .
Thus the group gain gap is oriented as merged minus Sybil, whereas the outsider gain gap is oriented as Sybil minus merged. By Theorem 4.15, GainGap G \operatorname{GainGap}_G GainGap G and GainGap N \operatorname{GainGap}_N GainGap N are locally absolutely continuous and
GainGap G ′ = X G M − X G S , GainGap N ′ = X N S − X N M almost everywhere . \operatorname{GainGap}_G'=X_G^{\mathcal{M}}-X_G^{\mathcal{S}},\qquad\operatorname{GainGap}_N'=X_N^{\mathcal{S}}-X_N^{\mathcal{M}}\quad\text{almost everywhere}. GainGap G ′ = X G M − X G S , GainGap N ′ = X N S − X N M almost everywhere .
Lemma 4.16 (Group allocation gap). At every price below V V V at which the merged run continues,
X G M − X G S ≥ min { 0 , W N S − W N M + T M − T S } . (46) X_G^{\mathcal{M}}-X_G^{\mathcal{S}}\geq\min\{0,W_N^{\mathcal{S}}-W_N^{\mathcal{M}}+T^{\mathcal{M}}-T^{\mathcal{S}}\}. \tag*{(46)} X G M − X G S ≥ min { 0 , W N S − W N M + T M − T S } . (46) Here a target of a run that has already ended is evaluated at its fixed terminal state and the current common price and environment.
Proof. The merged identity is active with positive budget. Its supply invariant is
T M − X M ≤ B N M p , T^{\mathcal{M}}-X^{\mathcal{M}}\leq\frac{B_N^{\mathcal{M}}}{p}, T M − X M ≤ p B N M ,
and therefore
X G M ≥ T M − W N M . (47) X_G^{\mathcal{M}}\geq T^{\mathcal{M}}-W_N^{\mathcal{M}}. \tag*{(47)} X G M ≥ T M − W N M . (47)
If the Sybil group has never clinched and its run continues, then X G S = 0 X^{S}_{G}=0 X G S = 0 by Theorem 4.8, so X G M − X G S ≥ 0 X^{M}_{G}-X^{S}_{G}\ge0 X G M − X G S ≥ 0 . Otherwise, if the Sybil run continues, some group identity i i i is currently a clincher. Its clinching equality gives
T S − X S = D − i S ≥ B N S p . T^{S}-X^{S}=D^{S}_{-i}\ge\frac{B^{S}_{N}}{p}. T S − X S = D − i S ≥ p B N S .
so X G S ≤ T S − W N S X^{S}_{G}\le T^{S}-W^{S}_{N} X G S ≤ T S − W N S . If the Sybil run has ended, then B N S = 0 B^{S}_{N}=0 B N S = 0 , and target feasibility at its terminal state gives T S ≥ X S T^{S}\ge X^{S} T S ≥ X S , hence the same inequality. Subtracting this upper bound from (47) proves (46) in the latter cases, while the first case gives its zero branch.
Lemma 4.17 (Outsider accounting). Fix a price p < V p<V p < V at which the merged run continues, and let
Φ p ( t ) : = ∑ j ∈ N : v j > p min { q j , t } . \Phi_{p}(t):=\sum_{j\in N:v_{j}>p}\min\{q_{j},t\}. Φ p ( t ) := j ∈ N : v j > p ∑ min { q j , t } . If the Sybil run also continues, then
Y N S − Y N M = Φ p ( h M ) − Φ p ( h S ) , (48) Y^{S}_{N}-Y^{M}_{N}=\Phi_{p}(h^{M})-\Phi_{p}(h^{S}), \tag*{(48)} Y N S − Y N M = Φ p ( h M ) − Φ p ( h S ) , (48) p ( W N S − W N M ) = GainGap N , (49) p(W^{S}_{N}-W^{M}_{N})=\operatorname{GainGap}_{N}, \tag*{(49)} p ( W N S − W N M ) = GainGap N , (49) and
β M − β S = Q − q G + d G S ≥ 0 , β : = Y + B , (50) \beta^{M}-\beta^{S}=Q-q_{G}+d^{S}_{G}\ge0,\qquad\beta:=Y+B, \tag*{(50)} β M − β S = Q − q G + d G S ≥ 0 , β := Y + B , (50) where d G S d^{S}_{G} d G S is the total Sybil budget cancelled so far, including budgets removed as ineligible at the initial price. If the Sybil run has ended, then
Y N S ≥ Y N M , p ( W N S − W N M ) ≥ GainGap N . (51) Y^{S}_{N}\ge Y^{M}_{N},\qquad p(W^{S}_{N}-W^{M}_{N})\ge\operatorname{GainGap}_{N}. \tag*{(51)} Y N S ≥ Y N M , p ( W N S − W N M ) ≥ GainGap N . (51)
Proof. Suppose both runs continue. By Theorem 4.9, every outsider with v j ≤ p v_{j}\le p v j ≤ p has paid zero and had its full budget cancelled in both runs. Every outsider with v j > p v_{j}>p v j > p is active and, by (40) , has budget min { q j , h } \min\{q_{j},h\} min { q j , h } . Summing its payment q j − min { q j , h } q_{j}-\min\{q_{j},h\} q j − min { q j , h } proves (48) . Since β = Y + B \beta=Y+B β = Y + B equals the sum of initial budgets minus cancelled budgets, the outsider cancellations agree in the two runs, while the merged identity has no cancellation below V V V . This proves (50) . Finally,
p W N = p X N + B N = Γ N + Y N + B N = Γ N + ∑ j ∈ N : v j > p q j pW_{N}=pX_{N}+B_{N}=\Gamma_{N}+Y_{N}+B_{N}=\Gamma_{N}+\sum_{j\in N:v_{j}>p}q_{j} p W N = p X N + B N = Γ N + Y N + B N = Γ N + j ∈ N : v j > p ∑ q j
in both continuing runs, proving (49) .
Now suppose the Sybil run ended at p 1 ≤ p p_{1}\le p p 1 ≤ p . Capacity saturation is not a terminal event under the completion convention. Every outsider with v j > p 1 v_{j}>p_{1} v j > p 1 was active at its terminal event and exhausted its budget. An outsider with v j ≤ p 1 v_{j}\le p_{1} v j ≤ p 1 pays zero in the continuing merged run and a nonnegative amount in the Sybil run. Thus Y N S ≥ Y N M Y^{S}_{N}\ge Y^{M}_{N} Y N S ≥ Y N M . Because terminal effective budgets are set to zero,
p ( W N S − W N M ) = GainGap N + Y N S − Y N M − B N M . p(W^{S}_{N}-W^{M}_{N})=\operatorname{GainGap}_{N}+Y^{S}_{N}-Y^{M}_{N}-B^{M}_{N}. p ( W N S − W N M ) = GainGap N + Y N S − Y N M − B N M .
The last two terms are nonnegative identity by identity: an outsider active in the merged run has paid its full budget in the ended run, and an outsider already exited from the merged run has zero effective budget and zero payment there. Hence p ( W N S − W N M ) ≥ GainGap N p(W^{S}_{N}-W^{M}_{N})\ge\operatorname{GainGap}_{N} p ( W N S − W N M ) ≥ GainGap N .
Theorem 4.18 (Sybil-proofness for an admissible target-based mechanism). In any admissible abstract target-based mechanism T \mathcal{T} T , truthful participation as the merged identity ( V , Q ) (V,Q) ( V , Q ) weakly dominates every same-direction Sybil strategy (43):
V X G M − Y G M ≥ V X G S − Y G S . (52) VX_G^M-Y_G^M \ge VX_G^S-Y_G^S. \tag*{(52)} V X G M − Y G M ≥ V X G S − Y G S . (52)
Proof. By Theorem 4.14, it is enough to consider v i ≤ V v_i \le V v i ≤ V for every i ∈ G i \in G i ∈ G . Then Theorem 4.15 identifies the two utilities with Γ G M ( V ) \Gamma_G^M(V) Γ G M ( V ) and Γ G S ( V ) \Gamma_G^S(V) Γ G S ( V ) , so it remains to prove GainGap G ( V ) ≥ 0 \operatorname{GainGap}_G(V) \ge0 GainGap G ( V ) ≥ 0 .
Let p 1 ≤ V p_1 \le V p 1 ≤ V be the price at which the merged run ends, taking p 1 = V p_1=V p 1 = V if it continues up to the merged identity’s exit. We first show that, for almost every p ∈ [ p ⋆ , p 1 ) p \in[p_\star,p_1) p ∈ [ p ⋆ , p 1 ) ,
GainGap G ≤ GainGap N ⟹ GainGap G ′ ≥ min { 0 , GainGap N / p } , (53) \operatorname{GainGap}_G \le\operatorname{GainGap}_N \quad\Longrightarrow\quad\operatorname{GainGap}'_G \ge\min\{0,\operatorname{GainGap}_N/p\}, \tag*{(53)} GainGap G ≤ GainGap N ⟹ GainGap G ′ ≥ min { 0 , GainGap N / p } , (53)
GainGap G ≥ GainGap N ⟹ GainGap N ′ ≥ GainGap N / p . (54) \operatorname{GainGap}_G \ge\operatorname{GainGap}_N \quad\Longrightarrow\quad\operatorname{GainGap}'_N \ge\operatorname{GainGap}_N/p. \tag*{(54)} GainGap G ≥ GainGap N ⟹ GainGap N ′ ≥ GainGap N / p . (54)
The total mark-to-market gain difference is
GainGap G − GainGap N = ( p X M − Y M ) − ( p X S − Y S ) . (55) \operatorname{GainGap}_G-\operatorname{GainGap}_N=(pX^M-Y^M)-(pX^S-Y^S). \tag*{(55)} GainGap G − GainGap N = ( p X M − Y M ) − ( p X S − Y S ) . (55)
If GainGap G ≤ GainGap N \operatorname{GainGap}_G \le\operatorname{GainGap}_N GainGap G ≤ GainGap N , the fact that the target decreases with mark-to-market gain gives T M ≥ T S T^M \ge T^S T M ≥ T S . By Theorem 4.17, W N S − W N M ≥ GainGap N / p W_N^S-W_N^M \ge\operatorname{GainGap}_N/p W N S − W N M ≥ GainGap N / p , whether the Sybil run continues or has already ended. The group allocation bound then gives
GainGap G ′ = X G M − X G S ≥ min { 0 , W N S − W N M + T M − T S } ≥ min { 0 , GainGap N / p } , \operatorname{GainGap}'_G=X_G^M-X_G^S\ge\min\{0,W_N^S-W_N^M+T^M-T^S\}\ge\min\{0,\operatorname{GainGap}_N/p\}, GainGap G ′ = X G M − X G S ≥ min { 0 , W N S − W N M + T M − T S } ≥ min { 0 , GainGap N / p } ,
proving (53) .
Suppose GainGap G ≥ GainGap N \operatorname{GainGap}_G \ge\operatorname{GainGap}_N GainGap G ≥ GainGap N . Then the fact that the target decreases with mark-to-market gain gives T M ≤ T S T^M \le T^S T M ≤ T S . If the Sybil run has ended, (51) and
p ⋅ GainGap N ′ = p ( X N S − X N M ) = GainGap N + Y N S − Y N M (56) p\cdot\operatorname{GainGap}'_N=p(X_N^S-X_N^M)=\operatorname{GainGap}_N+Y_N^S-Y_N^M \tag*{(56)} p ⋅ GainGap N ′ = p ( X N S − X N M ) = GainGap N + Y N S − Y N M (56)
gives (54) . If both runs continue, use
h = β + ( p X − Y ) − p T σ . h=\beta+(pX-Y)-pT_\sigma. h = β + ( pX − Y ) − p T σ .
Together with (50) , (55) , and T M ≤ T S T^M \le T^S T M ≤ T S , this gives
h M − h S = ( β M − β S ) + ( GainGap G − GainGap N ) − p ( T M − T S ) ≥ 0. h^M-h^S=(\beta^M-\beta^S)+(\operatorname{GainGap}_G-\operatorname{GainGap}_N)-p(T^M-T^S)\ge0. h M − h S = ( β M − β S ) + ( GainGap G − GainGap N ) − p ( T M − T S ) ≥ 0.
The function Φ p \Phi_p Φ p is nondecreasing, so (48) gives Y N S ≥ Y N M Y_N^S \ge Y_N^M Y N S ≥ Y N M . Equation (56) again proves (54) .
We next show that both gain gaps are nonnegative on [ p ⋆ , p 1 ] [p_\star,p_1] [ p ⋆ , p 1 ] :
GainGap G ≥ 0 , GainGap N ≥ 0. \operatorname{GainGap}_G\ge0,\qquad\operatorname{GainGap}_N\ge0. GainGap G ≥ 0 , GainGap N ≥ 0.
Let
μ : = min { GainGap G , GainGap N } . \mu:=\min\{\operatorname{GainGap}_G,\operatorname{GainGap}_N\}. μ := min { GainGap G , GainGap N } .
It is locally absolutely continuous and μ ( p ⋆ ) = 0 \mu(p_\star)=0 μ ( p ⋆ ) = 0 . At almost every price where the relevant functions are differentiable, if μ < 0 \mu<0 μ < 0 , then
μ ′ ≥ μ p . \mu'\ge\frac{\mu}{p}. μ ′ ≥ p μ .
Indeed, if GainGap G ≤ GainGap N \operatorname{GainGap}_{G} \le\operatorname{GainGap}_{N} GainGap G ≤ GainGap N , then (53) gives
GainGap G ′ ≥ min { 0 , GainGap N / p } ≥ μ / p . \operatorname{GainGap}_{G}^{\prime} \ge\min\{0,\operatorname{GainGap}_{N}/p\} \ge\mu/p. GainGap G ′ ≥ min { 0 , GainGap N / p } ≥ μ / p .
If instead GainGap N ≤ GainGap G \operatorname{GainGap}_{N} \le\operatorname{GainGap}_{G} GainGap N ≤ GainGap G , then (54) gives
GainGap N ′ ≥ GainGap N / p = μ / p . \operatorname{GainGap}_{N}^{\prime} \ge\operatorname{GainGap}_{N}/p = \mu/p. GainGap N ′ ≥ GainGap N / p = μ / p .
At equality points the same conclusion follows from the almost-everywhere derivative of the minimum. If μ \mu μ ever became negative, take the last preceding price p 2 p_2 p 2 at which μ ( p 2 ) = 0 \mu(p_2) = 0 μ ( p 2 ) = 0 . On the subsequent negative interval,
( μ ( p ) p ) ′ = p μ ′ ( p ) − μ ( p ) p 2 ≥ 0 , \left(\frac{\mu(p)}{p}\right)^{\prime} = \frac{p\mu^{\prime}(p)-\mu(p)}{p^2} \ge0, ( p μ ( p ) ) ′ = p 2 p μ ′ ( p ) − μ ( p ) ≥ 0 ,
which contradicts μ ( p 2 ) / p 2 = 0 \mu(p_2)/p_2 = 0 μ ( p 2 ) / p 2 = 0 . Thus GainGap G , GainGap N ≥ 0 \operatorname{GainGap}_{G}, \operatorname{GainGap}_{N} \ge0 GainGap G , GainGap N ≥ 0 through p 1 p_1 p 1 .
If p 1 = V p_1 = V p 1 = V , this already gives the result. Suppose p 1 < V p_1 < V p 1 < V . Capacity saturation is followed by zero-trade completion rather than termination, so the merged run has ended through one of the ordinary terminal rules. Its identity is still below its value and hence has not exited: a stopping allocation gives it its full remaining demand, while either of the other terminal rules is compatible with it remaining active only if its effective budget is zero. Because none of its budget is cancelled below V V V , it has therefore exhausted its budget: Y G M = Q Y_{G}^{M} = Q Y G M = Q . At p 1 p_1 p 1 , let b G S b_{G}^{S} b G S and d G S d_{G}^{S} d G S be the Sybil group’s remaining and cancelled budgets. Since Y G S = q G − d G S − b G S Y_{G}^{S} = q_{G} - d_{G}^{S} - b_{G}^{S} Y G S = q G − d G S − b G S ,
p 1 ( X G M ( p 1 ) − X G S ( p 1 ) ) − b G S = GainGap G ( p 1 ) + Q − q G + d G S ≥ 0. p_1\left(X_{G}^{M}(p_1) - X_{G}^{S}(p_1)\right) - b_{G}^{S} = \operatorname{GainGap}_{G}(p_1) + Q - q_{G} + d_{G}^{S} \ge0. p 1 ( X G M ( p 1 ) − X G S ( p 1 ) ) − b G S = GainGap G ( p 1 ) + Q − q G + d G S ≥ 0.
Every unit subsequently obtained by the Sybil group costs at least p 1 p_1 p 1 , so its additional allocation is at most
b G S p 1 ≤ X G M ( p 1 ) − X G S ( p 1 ) . \frac{b_{G}^{S}}{p_1} \le X_{G}^{M}(p_1) - X_{G}^{S}(p_1). p 1 b G S ≤ X G M ( p 1 ) − X G S ( p 1 ) .
Consequently X G M ( p ) − X G S ( p ) ≥ 0 X_{G}^{M}(p) - X_{G}^{S}(p) \ge0 X G M ( p ) − X G S ( p ) ≥ 0 for every p ∈ [ p 1 , V ] p \in[p_1,V] p ∈ [ p 1 , V ] . Because GainGap G ′ = X G M − X G S \operatorname{GainGap}_{G}^{\prime} = X_{G}^{M} - X_{G}^{S} GainGap G ′ = X G M − X G S almost everywhere, GainGap G \operatorname{GainGap}_{G} GainGap G is nondecreasing on that interval. Therefore GainGap G ( V ) ≥ GainGap G ( p 1 ) ≥ 0 \operatorname{GainGap}_{G}(V) \ge\operatorname{GainGap}_{G}(p_1) \ge0 GainGap G ( V ) ≥ GainGap G ( p 1 ) ≥ 0 , proving (52) . □
Theorem 4.19 (One-sided AMM incentive compatibility). Fix all reports of the other sell-Y traders. A physical sell-Y trader of true type ( V , Q ) (V,Q) ( V , Q ) cannot improve its utility by replacing its truthful merged identity ( V , Q ) (V,Q) ( V , Q ) with finitely many sell-Y identities having arbitrary value reports and aggregate reported budget at most Q Q Q . Thus the one-sided AMM clinching mechanism is Sybil-robust incentive compatible.
Proof. By Theorem 4.6, T a m m \mathcal{T}^{\mathrm{amm}} T amm is an admissible abstract target-based mechanism. Apply Theorem 4.18. Since the aggregate Sybil payment is at most the aggregate reported budget, which is at most Q Q Q , both sides of (52) are finite utilities under (5) restricted to sell-Y identities. □
Combining Theorems 4.11, 4.13 and 4.19, the one-sided AMM clinching mechanism is exact-settlement feasible, individually rational, weakly Pareto optimal for eligible bids, and Sybil-robust incentive compatible.
Full Two-Sided AMM Clinching Mechanism
We now extend our one-sided mechanism in § 3 to allow both sell-Y Y Y and sell-X X X bids. Types, eligibility, outcomes, and settlement retain their definitions from § 2 .
The idea is to fill the minority side in full at the spot price. Its orders then supply an initial quantity to the other side, which competes for this quantity and additional pool output through the one-sided clinching mechanism. The main additional proof challenge is the treatment of cross-directional strategies, that is, a sell-Y Y Y -type user can potentially post sell-X X X -type bids under its Sybil identities.
Dominant and Minority Sides
Let E Y ⊆ I Y \mathcal{E}_Y \subseteq\mathcal{I}_Y E Y ⊆ I Y and E X ⊆ I X \mathcal{E}_X \subseteq\mathcal{I}_X E X ⊆ I X be the eligible identities. Measure both sides at the spot price in units of X X X :
D Y : = ∑ i ∈ E Y q i p 0 , D X : = ∑ i ∈ E X r i , M : = min { D Y , D X } . D_Y := \sum_{i\in\mathcal{E}_Y} \frac{q_i}{p_0}, \qquad D_X := \sum_{i\in\mathcal{E}_X} r_i, \qquad M := \min\{D_Y,D_X\}. D Y := i ∈ E Y ∑ p 0 q i , D X := i ∈ E X ∑ r i , M := min { D Y , D X } .
The side with the smaller quantity is the minority ; the other is the dominant side . Here M M M is the minority fill in units of X X X . If the quantities are equal, designate sell-X X X as the minority. As shown below, either designation gives full internal matching at p 0 p_0 p 0 and leaves the pool unchanged.
Allocation and Settlement
No matter whether sell-Y Y Y or sell-X X X is dominant, ineligible identities receive zero outcomes. The eligible identities are processed as follows — note that minority-fill proceeds are transferred only at final settlement and cannot finance another order in the same batch.
Sell-Y Y Y is dominant. Suppose D Y ≥ D X D_Y \ge D_X D Y ≥ D X , so sell-X X X is the minority and M = D X M = D_X M = D X . Fold the minority supply directly into the cost faced by the dominant sell-Y Y Y auction:
C ~ M ( z ) : = { p 0 z , 0 ≤ z ≤ M , p 0 M + C ( z − M ) , M ≤ z < M + x 0 . (57) \widetilde{C}_M(z) :=
\begin{cases}
p_0z, & 0 \le z \le M, \\
p_0M + C(z-M), & M \le z < M+x_0.
\end{cases} \tag*{(57)} C M ( z ) := { p 0 z , p 0 M + C ( z − M ) , 0 ≤ z ≤ M , M ≤ z < M + x 0 . (57)
The first M M M units cost p 0 p_0 p 0 each and represent the sell-X X X minority orders, whose total compensation is p 0 M p_0M p 0 M . After those units are allocated, the cost of further output is the original pool cost. Thus the dominant auction treats internally matched supply and pool supply as a single cost curve. This curve records aggregate supply costs; individual dominant trades are still charged at the auction clock price.
For a state with Y ≥ C ~ M ( X ) Y \ge\widetilde{C}_M(X) Y ≥ C M ( X ) , define its chord target by the same construction as (11) :
T ~ M ( p , X , Y ) : = max { z ∈ [ X , M + x 0 ) : C ~ M ( z ) ≤ Y + p ( z − X ) } . \widetilde{T}_M(p,X,Y) := \max\{z \in[X,M+x_0) : \widetilde{C}_M(z) \le Y+p(z-X)\}. T M ( p , X , Y ) := max { z ∈ [ X , M + x 0 ) : C M ( z ) ≤ Y + p ( z − X )} .
In particular, even if the original pool cost is strictly convex, the extended cost has a linear segment whenever M > 0 M>0 M > 0 . This is why the one-sided construction includes supply lumps and does not assume strict convexity. Execute the following rules.
Assign each eligible minority identity its full spot-price trade:
S X , i = r i , R Y , i = p 0 r i ( i ∈ E X ) . S_{X,i}=r_i,\qquad R_{Y,i}=p_0r_i\qquad(i\in E_X). S X , i = r i , R Y , i = p 0 r i ( i ∈ E X ) .
Run the one-sided mechanism of § 3 on the reports ( v i , q i ) i ∈ E Y (v_i,q_i)_{i\in E_Y} ( v i , q i ) i ∈ E Y , replacing ( C , T a m m , x 0 ) (C,T^{\mathrm{amm}},x_0) ( C , T amm , x 0 ) by ( C ~ M , T ~ M , M + x 0 ) (\widetilde{C}_M,\widetilde{T}_M,M+x_0) ( C M , T M , M + x 0 ) . The clock still starts at p 0 p_0 p 0 . Use the same continuous dynamics, initial lump, event order, proportional exit rule, and continuation rule. If its output is ( x i , y i ) (x_i,y_i) ( x i , y i ) , set
R X , i = x i , S Y , i = y i , X f : = ∑ i ∈ E Y x i , Y f : = ∑ i ∈ E Y y i . R_{X,i}=x_i,\qquad S_{Y,i}=y_i,\qquad X_f:=\sum_{i\in E_Y}x_i,\qquad Y_f:=\sum_{i\in E_Y}y_i. R X , i = x i , S Y , i = y i , X f := i ∈ E Y ∑ x i , Y f := i ∈ E Y ∑ y i .
Settle all transfers simultaneously. The pool releases X f − M X_f-M X f − M units of X X X and receives Y f − p 0 M Y_f-p_0M Y f − p 0 M units of Y Y Y .
In Theorem 6.3 we prove that X f ≥ M X_f\ge M X f ≥ M and Y f − p 0 M = C ( X f − M ) Y_f-p_0M=C(X_f-M) Y f − p 0 M = C ( X f − M ) , so all these transfers are funded and the net pool trade lies on the original reserve curve.
Sell-X X X is dominant. Suppose D Y < D X D_Y<D_X D Y < D X , so sell-Y Y Y is the minority and M = D Y M=D_Y M = D Y . Exchange the roles of the assets. In the exchanged coordinates the reserve curve is φ − 1 \varphi^{-1} φ − 1 , the initial spot price is 1 / p 0 1/p_0 1/ p 0 , and the one-sided pool cost is
C r e v ( w ) : = − C − 1 ( − w ) , 0 ≤ w < y 0 . C^{\mathrm{rev}}(w):=-C^{-1}(-w),\qquad0\le w<y_0. C rev ( w ) := − C − 1 ( − w ) , 0 ≤ w < y 0 .
The extended cost, now measured as units of X X X needed to release w w w units of Y Y Y , is
C ~ M r e v ( w ) : = { w / p 0 , 0 ≤ w ≤ p 0 M , M + C r e v ( w − p 0 M ) , p 0 M ≤ w < p 0 M + y 0 . \widetilde{C}^{\mathrm{rev}}_M(w):=
\begin{cases}
w/p_0, & 0\le w\le p_0M,\\
M+C^{\mathrm{rev}}(w-p_0M), & p_0M\le w<p_0M+y_0.
\end{cases} C M rev ( w ) := { w / p 0 , M + C rev ( w − p 0 M ) , 0 ≤ w ≤ p 0 M , p 0 M ≤ w < p 0 M + y 0 .
At a reverse-auction state, let p r e v p^{\mathrm{rev}} p rev be the price in units of X X X per unit of Y Y Y , let X r e v X^{\mathrm{rev}} X rev be the cumulative amount of Y Y Y allocated, and let Y r e v Y^{\mathrm{rev}} Y rev be the cumulative amount of X X X paid. Define
T ~ M r e v ( p r e v , X r e v , Y r e v ) : = max { w ∈ [ X r e v , p 0 M + y 0 ) : C ~ M r e v ( w ) ≤ Y r e v + p r e v ( w − X r e v ) } . \widetilde{T}^{\mathrm{rev}}_M(p^{\mathrm{rev}},X^{\mathrm{rev}},Y^{\mathrm{rev}}):=\max\left\{w\in[X^{\mathrm{rev}},p_0M+y_0):\widetilde{C}^{\mathrm{rev}}_M(w)\le Y^{\mathrm{rev}}+p^{\mathrm{rev}}(w-X^{\mathrm{rev}})\right\}. T M rev ( p rev , X rev , Y rev ) := max { w ∈ [ X rev , p 0 M + y 0 ) : C M rev ( w ) ≤ Y rev + p rev ( w − X rev ) } .
Assign each eligible minority sell-Y Y Y identity its full spot-price trade: it pays q i q_i q i and receives q i / p 0 q_i/p_0 q i / p 0 . Run the one-sided mechanism on the dominant sell-X X X identities with reported values$^{9 }[eq] 1/u_i, b u d g e t s , budgets , b u d g e t s r_i, a n d c l o c k , and clock , an d c l oc k p^{\mathrm{rev}}s t a r t i n g a t starting at s t a r t in g a t 1/p_0, r e p l a c i n g t h e c o s t , t a r g e t , a n d c a p a c i t y b y , replacing the cost, target, and capacity by , r e pl a c in g t h ecos t , t a r g e t , an d c a p a c i t y b y (\widetilde{C}^{\mathrm{rev}}_M,\widetilde{T}^{\mathrm{rev}}_M,p_0M+y_0). A n a l l o c a t i o n . An allocation . A na l l oc a t i o n x_i^{\mathrm{rev}}a n d p a y m e n t and payment an d p a y m e n t y_i^{\mathrm{rev}}i n t h i s a u c t i o n m e a n in this auction mean in t hi s a u c t i o nm e an R_{Y,i}=x_i^{\mathrm{rev}}a n d and an d S_{X,i}=y_i^{\mathrm{rev}}$.
Proofs for the Two-Sided AMM Clinching Mechanism
We first justify the extended auction and settlement. For incentives, the one-sided Sybil theorem already handles splitting and value reports while the fill is fixed. The additional issue is that opposite-direction orders can enlarge that fill or change which side is dominant. A bound on the value of extra spot-price supply handles the former; the initial water level handles the latter. We then use the one-sided terminal certificate to prove weak Pareto optimality for eligible bids from both sides.
Extended Targets, Termination, and Exact Settlement
Once the minority fill is folded into the dominant side’s cost curve, that curve and its domain fully determine the resulting one-sided AMM clinching auction. The curve’s right derivative at zero gives the initial clock price, the endpoint of its domain gives the capacity, the condition that an auction state lies on or above the curve gives the state domain, and the chord construction gives the target. Thus the one-sided clinching auction when sell-Y Y Y is dominant is determined by C ~ M \widetilde{C}_M C M , while the reverse auction when sell-X X X is dominant is determined by C ~ M r e v \widetilde{C}^{\mathrm{rev}}_M C M rev .
Lemma 6.1 (The extended auction inherits the one-sided results). For every fixed M ≥ 0 M \ge0 M ≥ 0 , the one-sided AMM clinching auction generated by C ~ M \widetilde{C}_M C M is an admissible target-based mechanism with unattained capacity M + x 0 M+x_0 M + x 0 . Its cost curve is continuous, strictly increasing, and convex on [ 0 , M + x 0 ) [0,M+x_0) [ 0 , M + x 0 ) , starts at zero with right derivative p 0 p_0 p 0 , and diverges at M + x 0 M+x_0 M + x 0 . The reverse one-sided AMM clinching auction generated by C ~ M r e v \widetilde{C}^{\mathrm{rev}}_M C M rev is likewise admissible; its cost curve has the corresponding properties on [ 0 , p 0 M + y 0 ) [0,p_0M+y_0) [ 0 , p 0 M + y 0 ) , with initial right derivative 1 / p 0 1/p_0 1/ p 0 and unattained capacity p 0 M + y 0 p_0M+y_0 p 0 M + y 0 .
Consequently, the single-run structural lemmas, exact-settlement theorem, and terminal certificate from § 4 apply to the one-sided auction generated by C ~ M \widetilde{C}_M C M and, separately, to the reverse one-sided auction generated by C ~ M r e v \widetilde{C}^{\mathrm{rev}}_M C M rev . Same-direction Sybil-robust incentive compatibility (Theorem 4.18 ) also applies separately to these two auctions.
Proof. The two branches of (57) agree at M M M , and their slopes meet at p 0 = C + ′ ( 0 ) p_0=C'_+(0) p 0 = C + ′ ( 0 ) . The right derivative is p 0 p_0 p 0 on [ 0 , M ) [0,M) [ 0 , M ) and a ( z − M ) a(z-M) a ( z − M ) on [ M , M + x 0 ) [M,M+x_0) [ M , M + x 0 ) ; it is positive and nondecreasing. The other asserted cost properties follow directly from those of C C C . The proof of Theorem 4.6 uses precisely these properties of the cost, so it applies with C C C replaced by C ~ M \widetilde{C}_M C M . The structural lemmas and Theorem 4.18 then apply to the resulting admissible target. Likewise, the proofs of Theorems 4.11 and 4.12 use only this chord construction and the same cost properties.
The inverse of a strictly decreasing convex reserve curve is again strictly decreasing and convex. It has the same reserve-limit properties and is differentiable at y 0 y_0 y 0 , with derivative − 1 / p 0 -1/p_0 − 1/ p 0 . Hence exchanging the assets gives an admissible AMM, and the argument applies to C ~ M r e v \widetilde{C}^{\mathrm{rev}}_M C M rev as well.
Theorem 6.2 below addresses a boundary case in the reverse auction. When sell-X X X is dominant, a sell-X X X report with reservation value u i = 0 u_i=0 u i = 0 has transformed one-sided value 1 / u i = + ∞ 1/u_i=+\infty 1/ u i = + ∞ . Since our earlier analysis of the one-sided case allows only finite-value reports, it is convenient to replace this infinite transformed value by a sufficiently large finite one without affecting the outcome.
Lemma 6.2 (Infinite bids admit finite truncation). Let C ^ \widehat{C} C be either extended cost, let p ⋆ p_\star p ⋆ be its initial clock price, and let B 0 B_0 B 0 be the total initial budget in that auction. Set
z B : = C ^ − 1 ( B 0 ) , P B : = C ^ + ′ ( z B ) < ∞ . z_B := \widehat{C}^{-1}(B_0), \qquad P_B := \widehat{C}'_+(z_B) < \infty. z B := C − 1 ( B 0 ) , P B := C + ′ ( z B ) < ∞.
The run terminates at a finite clock price. Any value report above P B P_B P B can be replaced by any other value above P B P_B P B , or by + ∞ +\infty + ∞ , without changing the outcome. In particular, an identity with infinite clock value spends its entire budget.
Proof. At a continuing state after all events at the current price, the structural lemmas give h > 0 h>0 h > 0 . With β : = Y + B ≤ B 0 \beta:= Y+B \le B_0 β := Y + B ≤ B 0 , the chord identity gives
C ~ ( T ) = Y + p ( T − X ) = β − h ≤ B 0 , p ≤ C ~ + ′ ( T ) ≤ C ~ + ′ ( z B ) = P B . \widetilde{C}(T)=Y+p(T-X)=\beta-h\le B_0,\qquad p\le\widetilde{C}'_+(T)\le\widetilde{C}'_+(z_B)=P_B. C ( T ) = Y + p ( T − X ) = β − h ≤ B 0 , p ≤ C + ′ ( T ) ≤ C + ′ ( z B ) = P B .
Here z B z_B z B lies below the capacity and its right derivative is finite, including when B 0 = z B = 0 B_0=z_B=0 B 0 = z B = 0 . Choose a finite H > P B H>P_B H > P B for every infinite report. With these finite reports the usual termination rule stops the run no later than its largest value report; the bound above forces termination before H H H . Indeed, a continuing clock could not pass through the interval ( P B , H ) (P_B,H) ( P B , H ) . Reports above P B P_B P B therefore never exit before termination, and their exact values do not affect any allocation rule. This both defines and proves termination for the infinite-report convention. Such an identity is still active when the run ends, unless its budget was already zero; the stopping and exhaustion rules spend its entire budget.
Theorem 6.3 (Two-sided settlement and individual rationality). The two-sided mechanism terminates, is exact-settlement feasible, and is individually rational. Specifically, when sell-Y Y Y is dominant,
X f ≥ M , Y f = C ~ M ( X f ) = p 0 M + C ( X f − M ) , 0 ≤ X f − M < x 0 . (58) X_f\ge M,\qquad Y_f=\widetilde{C}_M(X_f)=p_0M+C(X_f-M),\qquad0\le X_f-M<x_0. \tag*{(58)} X f ≥ M , Y f = C M ( X f ) = p 0 M + C ( X f − M ) , 0 ≤ X f − M < x 0 . (58) For every reported profile, executed prices also satisfy
S Y , i ≥ p 0 R X , i ( i ∈ I Y ) , R Y , i ≤ p 0 S X , i ( i ∈ I X ) . (59) S_{Y,i}\ge p_0R_{X,i}\quad(i\in I_Y),\qquad R_{Y,i}\le p_0S_{X,i}\quad(i\in I_X). \tag*{(59)} S Y , i ≥ p 0 R X , i ( i ∈ I Y ) , R Y , i ≤ p 0 S X , i ( i ∈ I X ) . (59) Thus a sell-Y Y Y identity buys X X X at prices at least p 0 p_0 p 0 , and a sell-X X X identity sells X X X at prices at most p 0 p_0 p 0 .
Proof. When sell-Y Y Y is dominant, D Y ≥ D X D_Y\ge D_X D Y ≥ D X . The initial target is
T ~ M ( p 0 , 0 , 0 ) = M + Z ( p 0 ) = : Δ 0 , (60) \widetilde{T}_M(p_0,0,0)=M+Z(p_0)=:\Delta_0, \tag*{(60)} T M ( p 0 , 0 , 0 ) = M + Z ( p 0 ) =: Δ 0 , (60) the length of the extended cost’s initial linear segment. The total dominant budget is B 0 = p 0 D Y B_0=p_0D_Y B 0 = p 0 D Y . If the run stops at p 0 p_0 p 0 , the stopping rule allocates X f = min { Δ 0 , B 0 / p 0 } X_f=\min\{\Delta_0,B_0/p_0\} X f = min { Δ 0 , B 0 / p 0 } : it clears the whole initial target when the budget suffices, and otherwise spends every budget on a prefix of that linear segment. Both Δ 0 \Delta_0 Δ 0 and B 0 / p 0 = D Y B_0/p_0=D_Y B 0 / p 0 = D Y are at least M M M , so X f ≥ M X_f\ge M X f ≥ M .
If the run continues beyond p 0 p_0 p 0 , its terminal allocation is at least Δ 0 \Delta_0 Δ 0 . To see this, recall the two settlement cases in the proof of Theorem 4.11 . A fully cleared terminal chord has allocation at the rightmost chord endpoint, which is at or beyond the initial linear segment. A terminal point in a partially allocated lump lies on a linear segment of slope p f > p 0 p_f>p_0 p f > p 0 , which is also beyond that initial segment. The boundary case S = 0 S=0 S = 0 is a fully cleared chord. Thus the minority fill is absorbed in every case.
By Theorems 6.1 and 6.2, the dominant run terminates and satisfies Y f = C ~ M ( X f ) Y_f=\widetilde{C}_M(X_f) Y f = C M ( X f ) . Substituting X f ≥ M X_f\ge M X f ≥ M gives (58) . The minority supplies M M M units of X X X and receives p 0 M p_0M p 0 M units of Y Y Y ; the remaining flows are X p o o l = X f − M X_{\mathrm{pool}}=X_f-M X pool = X f − M and Y p o o l = C ( X f − M ) Y_{\mathrm{pool}}=C(X_f-M) Y pool = C ( X f − M ) . This is exactly Theorem 2.2, with no deficit in either asset.
Dominant identities obey their reported budgets and pay at most their reported values per unit, by the one-sided rules. Minority identities receive p 0 r i ≥ u i r i p_0r_i \ge u_ir_i p 0 r i ≥ u i r i . These facts give individual rationality on truthful profiles. They also show that buyers pay clock prices at least p 0 p_0 p 0 , while sellers receive exactly p 0 p_0 p 0 , proving (59) in this case.
Exchanging the assets proves the corresponding settlement and budget claims when sell-X X X is dominant. Sellers then pay at most their reciprocal value in the exchanged auction, so their original surplus R Y , i − u i S X , i R_{Y,i}-u_iS_{X,i} R Y , i − u i S X , i is nonnegative. For u i = 0 u_i=0 u i = 0 this is immediate. The ascending clock p r e v ≥ 1 / p 0 p^{\mathrm{rev}} \ge1/p_0 p rev ≥ 1/ p 0 pays sellers original prices 1 / p r e v ≤ p 0 1/p^{\mathrm{rev}} \le p_0 1/ p rev ≤ p 0 , while minority buyers pay exactly p 0 p_0 p 0 .
Finally, if D Y = D X = M D_Y=D_X=M D Y = D X = M , the entire dominant budget buys exactly M M M units at p 0 p_0 p 0 . The initial stopping rule spends every identity’s budget, including those exiting at p 0 p_0 p 0 , and the pool is unchanged. This also proves that the tie designation is immaterial. □
The Initial Fill and the Imbalance
Recall that Z ( p 0 ) Z(p_0) Z ( p 0 ) is the value at p 0 p_0 p 0 of the marginal-supply function defined in (36) .
Lemma 6.4 (Guaranteed allocation at the spot price). Suppose sell-Y Y Y is dominant, and let η = D Y − M \eta=D_Y-M η = D Y − M . At the initial price p 0 p_0 p 0 , first set the residual supply to the initial target S = T ~ M ( p 0 , 0 , 0 ) = M + Z ( p 0 ) S=\widetilde{T}_M(p_0,0,0)=M+Z(p_0) S = T M ( p 0 , 0 , 0 ) = M + Z ( p 0 ) . Before processing any identities that exit at p 0 p_0 p 0 , the water level is
h 0 = p 0 D Y − p 0 ( M + Z ( p 0 ) ) = p 0 ( η − Z ( p 0 ) ) ≤ p 0 η . (61) h_0=p_0D_Y-p_0\left(M+Z(p_0)\right)=p_0\left(\eta-Z(p_0)\right)\le p_0\eta. \tag*{(61)} h 0 = p 0 D Y − p 0 ( M + Z ( p 0 ) ) = p 0 ( η − Z ( p 0 ) ) ≤ p 0 η . (61) Every eligible dominant identity receives at least
x i ( p 0 ) ≥ ( q i p 0 − η ) + . x_i(p_0)\ge\left(\frac{q_i}{p_0}-\eta\right)_+. x i ( p 0 ) ≥ ( p 0 q i − η ) + . Consequently a truthful identity ( V , Q ) (V,Q) ( V , Q ) , V ≥ p 0 V\ge p_0 V ≥ p 0 , obtains utility at least ( V − p 0 ) ( Q / p 0 − η ) + (V-p_0)(Q/p_0-\eta)_+ ( V − p 0 ) ( Q / p 0 − η ) + .
Proof. Equation (61) follows from (60) . Let B E B_E B E be the total budget of identities exiting at p 0 p_0 p 0 . If the run continues, restoration lowers each active budget to at most h ⋆ = h 0 − B E ≤ p 0 η h^\star=h_0-B_E\le p_0\eta h ⋆ = h 0 − B E ≤ p 0 η , so its spot-price purchase is ( q i − h ⋆ ) + / p 0 (q_i-h^\star)_+/p_0 ( q i − h ⋆ ) + / p 0 . An exiting identity receives nothing in this case, but q i ≤ B E < h 0 ≤ p 0 η q_i\le B_E<h_0\le p_0\eta q i ≤ B E < h 0 ≤ p 0 η , so its claimed lower bound is zero. If the run stops, every active budget is spent. The total unspent exiting budget is max { h 0 , 0 } \max\{h_0,0\} max { h 0 , 0 } , so each exiting identity spends at least ( q i − max { h 0 , 0 } ) + (q_i-\max\{h_0,0\})_+ ( q i − max { h 0 , 0 } ) + . This proves the allocation bound in all cases. All later truthful purchases have nonnegative surplus, proving the utility bound. □
Thus the imbalance measures how much of a dominant bidder’s spot-price demand can remain unfilled. The pool’s own initial linear segment can only improve this guarantee. This observation will bound the gain from changing which side is the minority.
The Value of Additional Spot-Price Supply
The same-direction Sybil theorem, Theorem 4.18 , already shows that, for a fixed extended cost curve, a trader cannot benefit by splitting its sell-Y Y Y participation among multiple identities or misreporting their values. Thus the new issue in the two-sided incentive proof is the effect of opposite-direction sell-X X X identities on the cost curve faced by the trader’s merged sell-Y Y Y identity.
The proof in § 6.4 first considers a strategic trader with true sell-Y Y Y type; the sell-X X X case follows by exchanging the assets. Suppose the truthful profile has sell-Y Y Y as the dominant side. If the trader submits opposite-direction sell-X X X identities and sell-Y Y Y remains dominant, those identities enlarge the minority fill from M M M to M + E M+E M + E , thereby lengthening the initial p 0 p_0 p 0 -price segment of the extended cost curve. This additional supply may benefit the trader’s merged sell-Y Y Y identity, but supplying the E E E units of X X X through its opposite-direction identities costs the trader ( V − p 0 ) E (V-p_0)E ( V − p 0 ) E in surplus. Theorem 6.5 shows that the gain from the enlarged fill cannot exceed this cost. A deviation that changes which side is dominant is handled separately in § 6.4 .
Fix outside sell-Y Y Y reports and a true value V ≥ p 0 V \ge p_0 V ≥ p 0 . Let U ( M , Q ) U(M,Q) U ( M , Q ) denote the utility of the single truthful identity ( V , Q ) (V,Q) ( V , Q ) in the one-sided run on C ~ M \widetilde{C}_M C M . In this notation the fill is a parameter of the cost; no minority orders are part of this one-sided comparison.
Lemma 6.5 (Fill-shift bound). For all M , E , Q ≥ 0 M,E,Q \ge0 M , E , Q ≥ 0 ,
U ( M + E , Q + p 0 E ) ≤ U ( M , Q ) + ( V − p 0 ) E . U(M+E,Q+p_0E) \le U(M,Q) + (V-p_0)E. U ( M + E , Q + p 0 E ) ≤ U ( M , Q ) + ( V − p 0 ) E .
The comparison gives the bidder both E E E extra units of initial supply and the p 0 E p_0E p 0 E needed to buy them. The lemma says that its utility can increase by no more than the surplus of buying those units at the spot price. Because the extra supply can change the whole auction path, the proof compares mark-to-market gains, as in the one-sided incentive proof.
Proof. If V = p 0 V=p_0 V = p 0 , both utilities are zero. If Q = 0 Q=0 Q = 0 , then U ( M , 0 ) = 0 U(M,0)=0 U ( M , 0 ) = 0 , and a budget of p 0 E p_0E p 0 E buying only at prices at least p 0 p_0 p 0 gives surplus at most ( V − p 0 ) E (V-p_0)E ( V − p 0 ) E . Hence assume V > p 0 V>p_0 V > p 0 and Q > 0 Q>0 Q > 0 .
Call the smaller-fill run 0 and the larger-fill run 1. Their costs are C 0 : = C ~ M C_0 := \widetilde{C}_M C 0 := C M and C 1 : = C ~ M + E C_1 := \widetilde{C}_{M+E} C 1 := C M + E , and the focal identity k k k has budgets Q Q Q and Q + p 0 E Q+p_0E Q + p 0 E , respectively. All outsider reports N N N are the same. Use T r T^r T r , h r h^r h r , β r = Y r + B r \beta^r=Y^r+B^r β r = Y r + B r for the state of run r r r , and use Γ N r \Gamma_N^r Γ N r , Γ N r \Gamma_N^r Γ N r , W N r W_N^r W N r as in (44) and (45) . After a run ends, allocations and payments stay fixed, effective budgets are zero, and its target is evaluated at the current comparison price.
The costs satisfy the translation identity
C 1 ( z + E ) = C 0 ( z ) + p 0 E . (62) C_1(z+E)=C_0(z)+p_0E. \tag*{(62)} C 1 ( z + E ) = C 0 ( z ) + p 0 E . (62)
Consequently translating an auction state by ( E , p 0 E ) (E,p_0E) ( E , p 0 E ) translates its rightmost chord endpoint by E E E . Define the shift-adjusted gain gap of the focal identity and the outsider gain gap by
GainGap k : = Γ k 0 − Γ k 1 + ( p − p 0 ) E , GainGap N : = Γ N 1 − Γ N 0 . \operatorname{GainGap}_k := \Gamma_k^0-\Gamma_k^1+(p-p_0)E,\qquad\operatorname{GainGap}_N := \Gamma_N^1-\Gamma_N^0. GainGap k := Γ k 0 − Γ k 1 + ( p − p 0 ) E , GainGap N := Γ N 1 − Γ N 0 .
Both functions are locally absolutely continuous and vanish at p 0 p_0 p 0 by Theorem 4.15. Moreover,
GainGap k ′ = x k 0 − x k 1 + E , p GainGap N ′ = GainGap N + Y N 1 − Y N 0 . (63) \operatorname{GainGap}'_k=x_k^0-x_k^1+E,\qquad p\operatorname{GainGap}'_N=\operatorname{GainGap}_N+Y_N^1-Y_N^0. \tag*{(63)} GainGap k ′ = x k 0 − x k 1 + E , p GainGap N ′ = GainGap N + Y N 1 − Y N 0 . (63)
almost everywhere. At p = V p = V p = V , the desired inequality is exactly GainGap k ( V ) ≥ 0 \operatorname{GainGap}_k(V) \ge0 GainGap k ( V ) ≥ 0 .
Write ψ p r ( z ) : = p z − C r ( z ) \psi^r_p(z) := pz - C_r(z) ψ p r ( z ) := p z − C r ( z ) . The chord equality and (62) give
GainGap k − GainGap N = ψ p 0 ( T 0 ) − ψ p 1 ( T 1 ) + ( p − p 0 ) E = ψ p 1 ( T 0 + E ) − ψ p 1 ( T 1 ) . \operatorname{GainGap}_k-\operatorname{GainGap}_N=\psi^0_p(T^0)-\psi^1_p(T^1)+(p-p_0)E=\psi^1_p(T^0+E)-\psi^1_p(T^1). GainGap k − GainGap N = ψ p 0 ( T 0 ) − ψ p 1 ( T 1 ) + ( p − p 0 ) E = ψ p 1 ( T 0 + E ) − ψ p 1 ( T 1 ) .
Both arguments in the last expression are on the decreasing branch of ψ p 1 \psi^1_p ψ p 1 : they are rightmost chord endpoints, with the first one translated as above. The same strict monotonicity used in the proof of Theorem 4.6 therefore implies
GainGap k ≤ GainGap N ⟹ T 1 ≤ T 0 + E , GainGap k ≥ GainGap N ⟹ T 1 ≥ T 0 + E . (64) \begin{aligned}
\operatorname{GainGap}_k\le\operatorname{GainGap}_N&\ \Longrightarrow\ T^1\le T^0+E,\\
\operatorname{GainGap}_k\ge\operatorname{GainGap}_N&\ \Longrightarrow\ T^1\ge T^0+E. \tag*{(64)}
\end{aligned} GainGap k ≤ GainGap N GainGap k ≥ GainGap N ⟹ T 1 ≤ T 0 + E , ⟹ T 1 ≥ T 0 + E . (64)
Let p 1 p_1 p 1 be the terminal price of run 0, or V V V if that run continues to the focal identity’s exit. Consider almost every p ∈ ( p 0 , p 1 ) p\in(p_0,p_1) p ∈ ( p 0 , p 1 ) . The outsider accounting from Theorem 4.17 uses only the common outsider reports and the single-run structural lemmas, so it gives
W N 1 − W N 0 ≥ GainGap N / p . (65) W^1_N-W^0_N\ge\operatorname{GainGap}_N/p. \tag*{(65)} W N 1 − W N 0 ≥ GainGap N / p . (65)
There is equality while both runs continue. If run 1 has ended, the same terminal accounting gives Y N 1 ≥ Y N 0 Y^1_N\ge Y^0_N Y N 1 ≥ Y N 0 .
When both runs continue, identical outsiders have had identical budgets cancelled, and the focal identity has not exited. Thus β 1 − β 0 = p 0 E \beta^1-\beta^0=p_0E β 1 − β 0 = p 0 E . Since h r = β r − C r ( T r ) h^r=\beta^r-C_r(T^r) h r = β r − C r ( T r ) , the cost translation gives
h 0 − h 1 = C 1 ( T 1 ) − C 1 ( T 0 + E ) . h^0-h^1=C_1(T^1)-C_1(T^0+E). h 0 − h 1 = C 1 ( T 1 ) − C 1 ( T 0 + E ) .
If GainGap k ≥ GainGap N \operatorname{GainGap}_k\ge\operatorname{GainGap}_N GainGap k ≥ GainGap N , then T 1 ≥ T 0 + E T^1\ge T^0+E T 1 ≥ T 0 + E , hence h 1 ≤ h 0 h^1\le h^0 h 1 ≤ h 0 . The outsider payment formula (48) gives Y N 1 ≥ Y N 0 Y^1_N\ge Y^0_N Y N 1 ≥ Y N 0 . This also holds when run 1 has ended, so (63) yields
GainGap k ≥ GainGap N ⟹ GainGap N ′ ≥ GainGap N / p . (66) \operatorname{GainGap}_k\ge\operatorname{GainGap}_N\quad\Longrightarrow\quad\operatorname{GainGap}'_N\ge\operatorname{GainGap}_N/p. \tag*{(66)} GainGap k ≥ GainGap N ⟹ GainGap N ′ ≥ GainGap N / p . (66)
For the other inequality, the supply invariant of the active focal identity in run 0 gives x k 0 ≥ T 0 − W N 0 x^0_k\ge T^0-W^0_N x k 0 ≥ T 0 − W N 0 , exactly as in the proof of Theorem 4.16. If the focal identity in continuing run 1 has never clinched, then x k 1 = 0 x^1_k=0 x k 1 = 0 and GainGap k ′ ≥ 0 \operatorname{GainGap}'_k\ge0 GainGap k ′ ≥ 0 . Otherwise clincher persistence, or target feasibility if that run has ended, gives x k 1 ≤ T 1 − W N 1 x^1_k\le T^1-W^1_N x k 1 ≤ T 1 − W N 1 . Therefore, when GainGap k ≤ GainGap N \operatorname{GainGap}_k\le\operatorname{GainGap}_N GainGap k ≤ GainGap N , (64) and (65) imply
GainGap k ′ ≥ min { 0 , GainGap N / p } . (67) \operatorname{GainGap}'_k\ge\min\{0,\operatorname{GainGap}_N/p\}. \tag*{(67)} GainGap k ′ ≥ min { 0 , GainGap N / p } . (67)
Indeed, in the latter case the sharper bound is GainGap k ′ ≥ T 0 + E − T 1 + W N 1 − W N 0 ≥ GainGap N / p \operatorname{GainGap}'_k\ge T^0+E-T^1+W^1_N-W^0_N\ge\operatorname{GainGap}_N/p GainGap k ′ ≥ T 0 + E − T 1 + W N 1 − W N 0 ≥ GainGap N / p .
Equations (66) and (67) are precisely the two differential inequalities used in the first-crossing argument of Theorem 4.18 . Applying that already proved argument to min { GainGap k , GainGap N } \min\{\operatorname{GainGap}_k,\operatorname{GainGap}_N\} min { GainGap k , GainGap N } , which starts at zero, gives GainGap k , GainGap N ≥ 0 \operatorname{GainGap}_k,\operatorname{GainGap}_N\ge0 GainGap k , GainGap N ≥ 0 through p 1 p_1 p 1 .
If p 1 = V p_1=V p 1 = V , this proves the claim. Otherwise run 0 ended below V V V , so its focal identity spent all of Q Q Q . No focal budget has been cancelled in run 1 below V V V ; write b k 1 b^1_k b k 1 for its remaining budget at p 1 p_1 p 1 , taking it to be zero if run 1 has ended. The definition of GainGap k \operatorname{GainGap}_k GainGap k now gives
0 ≤ GainGap k ( p 1 ) = p 1 ( x k 0 ( p 1 ) − x k 1 ( p 1 ) + E ) − b k 1 . 0\le\operatorname{GainGap}_k(p_1)=p_1\left(x^0_k(p_1)-x^1_k(p_1)+E\right)-b^1_k. 0 ≤ GainGap k ( p 1 ) = p 1 ( x k 0 ( p 1 ) − x k 1 ( p 1 ) + E ) − b k 1 .
Every later unit in run 1 costs at least p 1 p_1 p 1 , so its focal allocation can never exceed x k 0 ( p 1 ) + E x^0_k(p_1)+E x k 0 ( p 1 ) + E . Hence GainGap k ′ ≥ 0 \operatorname{GainGap}'_k\ge0 GainGap k ′ ≥ 0 from p 1 p_1 p 1 to V V V , and GainGap k ( V ) ≥ 0 \operatorname{GainGap}_k(V)\ge0 GainGap k ( V ) ≥ 0 follows.
Sybil-Robust Incentive Compatibility Across Directions
Theorem 6.6 (Two-sided Sybil-robust incentive compatibility). The two-sided AMM clinching mechanism satisfies Sybil-robust incentive compatibility (Theorem 2.6) for the full strategy space in Theorem 2.4.
Proof. Fix a physical trader k k k and all reports of the other traders. Truthful utility is finite and nonnegative by Theorem 6.3 , so a deviation giving utility − ∞ -\infty − ∞ cannot improve it. For all other deviations we compare the linear surplus of the aggregate net flows, as required by (5) and (6) .
Eligible true sell-Y Y Y type. Suppose that trader k k k has type ( V , Q ) (V,Q) ( V , Q ) , with V ≥ p 0 V \ge p_0 V ≥ p 0 . Remove ineligible identities from the deviation, since they have no effect. Let
Q d e v : = ∑ i ∈ I Y ( k ) ∩ E Y q i ≤ Q Q^{\mathrm{dev}} := \sum_{i\in\mathcal{I}_Y(k)\cap\mathcal{E}_Y} q_i \le Q Q dev := i ∈ I Y ( k ) ∩ E Y ∑ q i ≤ Q
be trader k k k 's aggregate eligible sell-Y Y Y budget in the deviating strategy, and let e : = S X ( k ) e := S_X(k) e := S X ( k ) be the amount of X X X actually delivered by its sell-X X X identities. Recall from (4) that Δ X , k \Delta_{X,k} Δ X , k and Δ Y , k \Delta_{Y,k} Δ Y , k are trader k k k 's aggregate net changes in its holdings of X X X and Y Y Y . The executed-price inequalities (59) imply
V Δ X , k + Δ Y , k ≤ ( V − p 0 ) ( Q d e v p 0 − e ) . (68) V\Delta_{X,k}+\Delta_{Y,k}\le(V-p_0)\left(\frac{Q^{\mathrm{dev}}}{p_0}-e\right). \tag*{(68)} V Δ X , k + Δ Y , k ≤ ( V − p 0 ) ( p 0 Q dev − e ) . (68)
For clarity, if its sell-Y Y Y identities spend s ≤ Q d e v s\le Q^{\mathrm{dev}} s ≤ Q dev , their allocation is at most s / p 0 s/p_0 s / p 0 , so their surplus is at most ( V / p 0 − 1 ) s ≤ ( V − p 0 ) Q d e v / p 0 (V/p_0-1)s\le(V-p_0)Q^{\mathrm{dev}}/p_0 ( V / p 0 − 1 ) s ≤ ( V − p 0 ) Q dev / p 0 . Its opposite-direction identities receive at most p 0 e p_0e p 0 e for an asset worth V e Ve V e to this same physical trader. Combining these two contributions proves the deviation-surplus bound in (68) . In particular, the case V = p 0 V=p_0 V = p 0 is immediate: every deviation has nonpositive linear surplus and truthfulness gives zero.
Suppose V > p 0 V>p_0 V > p 0 . If sell-X X X is dominant in the truthful profile, the focal identity spends all of Q Q Q at p 0 p_0 p 0 and obtains ( V − p 0 ) Q / p 0 (V-p_0)Q/p_0 ( V − p 0 ) Q / p 0 . Equation (68) , with Q d e v ≤ Q Q^{\mathrm{dev}}\le Q Q dev ≤ Q and e ≥ 0 e\ge0 e ≥ 0 , shows that no deviation can exceed this utility.
It remains to consider a truthful profile in which sell-Y Y Y is dominant. Let M M M be the total eligible outside sell-X X X budget and let η = D Y − M \eta=D_Y-M η = D Y − M . The truthful utility is U ( M , Q ) \mathcal{U}(M,Q) U ( M , Q ) , and Theorem 6.4 gives
U ( M , Q ) ≥ ( V − p 0 ) ( Q / p 0 − η ) + . (69) \mathcal{U}(M,Q)\ge(V-p_0)(Q/p_0-\eta)_+. \tag*{(69)} U ( M , Q ) ≥ ( V − p 0 ) ( Q / p 0 − η ) + . (69)
There are two cases.
The deviation leaves sell-Y Y Y dominant. All eligible opposite-direction identities are then filled in full at p 0 p_0 p 0 . Write E = e E=e E = e for their total X X X -budget. The dominant cost becomes C ~ M + E \widetilde{C}_{M+E} C M + E . On this fixed cost, Theorems 4.18 and 6.1 bound the group's sell-Y Y Y surplus by that of a single truthful identity with budget Q + p 0 E Q+p_0E Q + p 0 E , since Q d e v ≤ Q ≤ Q + p 0 E Q^{\mathrm{dev}}\le Q\le Q+p_0E Q dev ≤ Q ≤ Q + p 0 E . After accounting for the opposite-direction deliveries, the full linear surplus is at most
U ( M + E , Q + p 0 E ) − ( V − p 0 ) E ≤ U ( M , Q ) , \mathcal{U}(M+E,Q+p_0E)-(V-p_0)E\le\mathcal{U}(M,Q), U ( M + E , Q + p 0 E ) − ( V − p 0 ) E ≤ U ( M , Q ) ,
where the last step is Theorem 6.5. The larger budget here is only an upper bound used in the proof; the admissible deviation still has the original cap $Q^{\mathrm{dev}}\le Q`.
The deviation makes sell-X dominant. Its new total demand is D Y d e v = D Y − Q / p 0 + Q d e v / p 0 D^{\mathrm{dev}}_Y = D_Y - Q/p_0 + Q^{\mathrm{dev}}/p_0 D Y dev = D Y − Q / p 0 + Q dev / p 0 . By the exchanged version of Theorem 6.3 , the dominant sell-X identities deliver at least D Y d e v D^{\mathrm{dev}}_Y D Y dev units of X to cover that minority fill. The outside sell-X identities can deliver at most M M M , hence
e ≥ D Y d e v − M = Q d e v / p 0 − Q / p 0 + η . e \ge D^{\mathrm{dev}}_Y - M = Q^{\mathrm{dev}}/p_0 - Q/p_0 + \eta. e ≥ D Y dev − M = Q dev / p 0 − Q / p 0 + η .
Combining this with (68) gives linear surplus at most ( V − p 0 ) ( Q / p 0 − η ) (V-p_0)(Q/p_0-\eta) ( V − p 0 ) ( Q / p 0 − η ) , which is bounded above by the truthful utility in (69) . This case also includes a change of sides caused solely by withholding same-direction budget.
Eligible true sell-X type. First suppose 0 < U ≤ p 0 0 < U \le p_0 0 < U ≤ p 0 , and exchange the assets. The trader’s truthful value and budget in the exchanged auction are ( 1 / U , R ) (1/U,R) ( 1/ U , R ) . Admissibility becomes exactly the sell-Y constraint already considered: the same-direction budgets sum to at most R R R , while the opposite budgets are unrestricted. Its linear surplus in the exchanged numeraire is
Δ Y , k + U Δ X , k U , \frac{\Delta_{Y,k}+U\Delta_{X,k}}{U}, U Δ Y , k + U Δ X , k ,
a positive multiple of its original surplus. Thus the preceding proof applies. Any zero outside reservation reports can be represented by a common finite clock value above the bounds for the runs being compared, using Theorem 6.2.
For U = 0 U=0 U = 0 , take true values ε > 0 \varepsilon>0 ε > 0 tending to zero, with the same budget R R R and fixed outside reports and deviation. For all sufficiently small ε \varepsilon ε , the truthful report ( ε , R ) (\varepsilon,R) ( ε , R ) produces exactly the outcome of ( 0 , R ) (0,R) ( 0 , R ) : if it is minority its fill is unchanged, and if it is dominant its reciprocal value exceeds the finite clock bound. The inequality just proved for linear surpluses is R Y t r − ε S X t r ≥ Δ Y , k d e v + ε Δ X , k d e v R^{\mathrm{tr}}_Y-\varepsilon S^{\mathrm{tr}}_X\ge\Delta^{\mathrm{dev}}_{Y,k}+\varepsilon\Delta^{\mathrm{dev}}_{X,k} R Y tr − ε S X tr ≥ Δ Y , k dev + ε Δ X , k dev . Letting ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0 proves the required bound for every finite-utility deviation of a zero-reservation type as well.
Ineligible true types. Finally, although our standing convention considers eligible true types, the definition also quantifies over ineligible ones. Summing (59) over a physical trader’s identities gives, under every strategy,
Δ Y , k ≤ − p 0 Δ X , k . (70) \Delta_{Y,k}\le-p_0\Delta_{X,k}. \tag*{(70)} Δ Y , k ≤ − p 0 Δ X , k . (70)
A sell-Y Y Y type with V < p 0 V<p_0 V < p 0 has nonpositive linear surplus when Δ X , k ≥ 0 \Delta_{X,k}\ge0 Δ X , k ≥ 0 . When Δ X , k < 0 \Delta_{X,k}<0 Δ X , k < 0 , finite utility requires Δ Y , k ≤ 0 \Delta_{Y,k}\le0 Δ Y , k ≤ 0 , so its surplus is again nonpositive. A sell-X X X type with U > p 0 U>p_0 U > p 0 has surplus at most ( U − p 0 ) Δ X , k ≤ 0 (U-p_0)\Delta_{X,k}\le0 ( U − p 0 ) Δ X , k ≤ 0 when Δ X , k ≤ 0 \Delta_{X,k}\le0 Δ X , k ≤ 0 ; if Δ X , k > 0 \Delta_{X,k}>0 Δ X , k > 0 , (70) makes the trade strictly opposite to its type and its utility is − ∞ -\infty − ∞ . Truthful ineligible reports receive zero. This completes the proof for every true type and for the stated net-flow utility functions.
The two cases explain why opposite-direction identities do not help. If they remain on the minority side, their full delivery costs the trader at least the extra utility made possible by the enlarged fill. If they change which side is dominant, conservation forces enough actual delivery to offset the improvement in the trader’s buying price. Both comparisons value every identity’s trades at the physical trader’s true value.
Weak Pareto Optimality for Eligible Bids
Theorem 6.7 (Two-sided weak Pareto optimality). Under truthful reporting, the two-sided AMM clinching outcome is weakly Pareto optimal for eligible bids in the sense of Theorem 2.7.
Proof. Use the holdings and coefficients ( H i X , H i Y , t i ) (H_i^X,H_i^Y,t_i) ( H i X , H i Y , t i ) already defined in (7). We first show that there is a positive cutoff λ \lambda λ such that
H i Y > 0 ⟹ t i ≤ λ , H i X > 0 ⟹ t i ≥ λ . (71) H_i^Y > 0 \Longrightarrow t_i \le\lambda,\qquad H_i^X > 0 \Longrightarrow t_i \ge\lambda. \tag*{(71)} H i Y > 0 ⟹ t i ≤ λ , H i X > 0 ⟹ t i ≥ λ . (71)
Thus everyone who can pay Y Y Y values X X X no more highly than anyone who can supply it.
When sell-Y Y Y is dominant, let
λ : = { max { V i : Q i − S Y , i > 0 , i ∈ E Y } , if this set is nonempty , p 0 , otherwise . \lambda:=
\begin{cases}
\max\{V_i: Q_i-S_{Y,i}>0,\ i\in E_Y\}, & \text{if this set is nonempty},\\
p_0, & \text{otherwise}.
\end{cases} λ := { max { V i : Q i − S Y , i > 0 , i ∈ E Y } , p 0 , if this set is nonempty , otherwise .
Minority sell-X X X users have holdings ( 0 , p 0 R i ) (0,p_0R_i) ( 0 , p 0 R i ) and values U i ≤ p 0 ≤ λ U_i\le p_0\le\lambda U i ≤ p 0 ≤ λ . Dominant users with remaining Y Y Y have values at most λ \lambda λ by definition. Every holder of X X X is a dominant user; its value is at least λ \lambda λ by the first part of Theorem 4.12 applied to C ~ M \widetilde C_M C M , or by eligibility if no dominant user has residual budget. This proves (71) in this case.
When sell-X X X is dominant, let
λ : = { min { U i : R i − S X , i > 0 , i ∈ E X } , if this set is nonempty , p 0 , otherwise . \lambda:=
\begin{cases}
\min\{U_i: R_i-S_{X,i}>0,\ i\in E_X\}, & \text{if this set is nonempty},\\
p_0, & \text{otherwise}.
\end{cases} λ := { min { U i : R i − S X , i > 0 , i ∈ E X } , p 0 , if this set is nonempty , otherwise .
A zero-reservation dominant user spends all of its X X X -budget by Theorem 6.2, so 0 < λ ≤ p 0 0<\lambda\le p_0 0 < λ ≤ p 0 . Minority sell-Y Y Y users have holdings ( Q i / p 0 , 0 ) (Q_i/p_0,0) ( Q i / p 0 , 0 ) and values V i ≥ p 0 ≥ λ V_i\ge p_0\ge\lambda V i ≥ p 0 ≥ λ . Every other holder of X X X has value at least λ \lambda λ by definition. A dominant user j j j holding positive Y Y Y must have U j ≤ U i U_j\le U_i U j ≤ U i for every dominant user i i i with residual X X X : for positive reservation values this is the first terminal-certificate statement with reciprocal values, and for U j = 0 U_j=0 U j = 0 it is immediate. If no such residual user exists, eligibility gives U j ≤ p 0 = λ U_j\le p_0=\lambda U j ≤ p 0 = λ . Thus (71) holds in this case too.
The internal-trade argument in Theorem 4.13 now applies to all eligible users together. To spell out its use of the cutoff, a user paying Y Y Y can pay at most λ \lambda λ times the X X X it receives while weakly improving its utility. A user supplying X X X requires at least λ \lambda λ times that quantity in Y Y Y . Conservation of both tokens forces equality in all these bounds and leaves every utility unchanged. Hence there is no strict Pareto improvement through internal trade, even when the trading subset includes both original directions.
It remains to check each user’s permitted same-direction pool trade. When sell-Y Y Y is dominant, set z : = X f − M ≥ 0 z:=X_f-M\ge0 z := X f − M ≥ 0 . A dominant user with unspent Y Y Y satisfies
V i ≤ C ~ M , + ′ ( X f ) = a ( z ) V_i\le\widetilde C_{M,+}'(X_f)=a(z) V i ≤ C M , + ′ ( X f ) = a ( z )
by the second terminal-certificate statement. From the settled pool state, receiving another δ > 0 \delta>0 δ > 0 units of X X X costs C ( z + δ ) − C ( z ) ≥ a ( z ) δ C(z+\delta)-C(z)\ge a(z)\delta C ( z + δ ) − C ( z ) ≥ a ( z ) δ , so that user cannot gain. Minority sell-X X X users have no remaining X X X to tender in their own direction, because their endowments were filled in full. When sell-X X X is dominant, write w : = ∑ i ∈ E X R Y , i − ∑ i ∈ E Y Q i ≥ 0 w := \sum_{i\in E_X} R_{Y,i} - \sum_{i\in E_Y} Q_i \ge0 w := ∑ i ∈ E X R Y , i − ∑ i ∈ E Y Q i ≥ 0 for the net Y Y Y released by the pool, and put a r e v : = ( C r e v ) + ′ a^{\mathrm{rev}} := (C^{\mathrm{rev}})'_+ a rev := ( C rev ) + ′ . A dominant user with residual X X X has U i > 0 U_i > 0 U i > 0 , and the exchanged terminal certificate gives
1 / U i ≤ a r e v ( w ) . 1/U_i \le a^{\mathrm{rev}}(w). 1/ U i ≤ a rev ( w ) .
Receiving an additional δ > 0 \delta> 0 δ > 0 units of Y Y Y costs at least C r e v ( w + δ ) − C r e v ( w ) ≥ a r e v ( w ) δ C^{\mathrm{rev}}(w+\delta)-C^{\mathrm{rev}}(w) \ge a^{\mathrm{rev}}(w)\delta C rev ( w + δ ) − C rev ( w ) ≥ a rev ( w ) δ units of X X X . Its utility change is therefore at most ( 1 − U i a r e v ( w ) ) δ ≤ 0 (1-U_i a^{\mathrm{rev}}(w))\delta\le0 ( 1 − U i a rev ( w )) δ ≤ 0 . Minority sell-Y Y Y users have spent all of their Y Y Y -budgets, so they cannot make an additional trade in their own direction. This proves the second clause of Theorem 2.7 and completes the proof.
Impossibility with Budget Overreporting
The positive incentive results above restrict a trader’s aggregate declared budget in its true direction to its actual budget. We now show that this restriction is essential. Suppose instead that a trader may declare a larger budget, with the deviation regarded as feasible whenever the amount actually paid does not exceed its true budget. Even without Sybil identities or opposite-direction orders, this enlarged strategy space is incompatible with the other desired properties.
Under the enlarged strategy space considered here, a true eligible type ( V , Q ) (V,Q) ( V , Q ) may replace its report by any single finite eligible report ( v , q ) (v,q) ( v , q ) . If that report produces ( x , y ) (x,y) ( x , y ) , the deviation has finite utility precisely when y ≤ Q y \le Q y ≤ Q . Incentive compatibility with budget overreporting therefore requires
y ≤ Q ⟹ V x t r − y t r ≥ V x − y , y \le Q \quad\Longrightarrow\quad Vx^{\mathrm{tr}}-y^{\mathrm{tr}} \ge Vx-y, y ≤ Q ⟹ V x tr − y tr ≥ V x − y ,
where ( x t r , y t r ) (x^{\mathrm{tr}},y^{\mathrm{tr}}) ( x tr , y tr ) is the truthful outcome. In particular, when the mechanism does not require advance escrow of the entire declared budget, budget overreporting becomes possible as long as its realized payment remains affordable.
Theorem 7.1 (Budget-overreporting impossibility). For a constant-product AMM, there is no deterministic mechanism that, on every profile of two eligible sell-Y Y Y users, simultaneously satisfies:
individual rationality (Theorem 2.3);
exact settlement (Theorem 2.2);
both clauses of weak Pareto optimality in Theorem 2.7; and
incentive compatibility against single-identity eligible value and budget misreports, including budget overreports whose realized payment does not exceed the true budget.
All true types and reports used in the proof are eligible and have finite values and budgets.
We stress that this impossibility holds in a strong sense. It assumes neither symmetry nor resistance to Sybil or opposite-direction deviations, and it already applies to the much smaller class of deviations that replace one sell-Y Y Y report by another. As a practical implication, the impossibility holds even when the underlying consensus protocol provides fair sequencing [13 , 33 , 30 , 31 , 32 ZSC+20] and censorship resilience [2 , 25 , 19 ] .
Normalization and Basic Consequences
By rescaling, we may assume without loss of generality that x 0 = y 0 = 1 x_0 = y_0 = 1 x 0 = y 0 = 1 , and hence p 0 = 1 p_0 = 1 p 0 = 1 , throughout the proof. The pool then releases
F ( y ) : = C − 1 ( y ) = y 1 + y , F ′ ( y ) = 1 ( 1 + y ) 2 , F(y) := C^{-1}(y) = \frac{y}{1+y}, \qquad F'(y) = \frac{1}{(1+y)^2}, F ( y ) := C − 1 ( y ) = 1 + y y , F ′ ( y ) = ( 1 + y ) 2 1 ,
and a sell-Y Y Y value is eligible exactly when V ≥ 1 V \ge1 V ≥ 1 .
For V > 1 V > 1 V > 1 , define
Util p o o l ( V , y ) : = V F ( y ) − y , y ⋆ ( V ) : = V − 1 , y ˉ ( V ) : = V − 1. \operatorname{Util}^{\mathrm{pool}}(V,y) := V F(y) - y, \qquad y^\star(V) := \sqrt{V} - 1, \qquad\bar{y}(V) := V - 1. Util pool ( V , y ) := V F ( y ) − y , y ⋆ ( V ) := V − 1 , y ˉ ( V ) := V − 1.
Here Util p o o l ( V , y ) \operatorname{Util}^{\mathrm{pool}}(V,y) Util pool ( V , y ) is the utility of a value-V V V user that receives all pool output generated by a payment y y y . It increases up to its unique maximizer y ⋆ ( V ) y^\star(V) y ⋆ ( V ) , then decreases; its two zeros are 0 0 0 and y ˉ ( V ) \bar{y}(V) y ˉ ( V ) . In particular,
0 < y ⋆ ( V ) < y ˉ ( V ) , Util p o o l ( V , y ⋆ ( V ) ) = ( V − 1 ) 2 . 0 < y^\star(V) < \bar{y}(V), \qquad\operatorname{Util}^{\mathrm{pool}}(V,y^\star(V)) = (\sqrt{V} - 1)^2. 0 < y ⋆ ( V ) < y ˉ ( V ) , Util pool ( V , y ⋆ ( V )) = ( V − 1 ) 2 .
Set y ⋆ ( 1 ) = y ˉ ( 1 ) = 0 y^\star(1) = \bar{y}(1) = 0 y ⋆ ( 1 ) = y ˉ ( 1 ) = 0 .
The first lemma is a strict priority property. A higher-valued user that still has some Y Y Y available could profitably purchase any allocation held by a lower-valued user. Weak Pareto optimality therefore prevents the lower value from receiving anything.
Lemma 7.2 (Internal-trade priority). Consider a truthful profile of two eligible sell-Y Y Y users. Denote their values and budgets by ( V 1 , q 1 ) (V_1,q_1) ( V 1 , q 1 ) and ( V 2 , q 2 ) (V_2,q_2) ( V 2 , q 2 ) , and their respective allocations and payments by ( x 1 , y 1 ) (x_1,y_1) ( x 1 , y 1 ) and ( x 2 , y 2 ) (x_2,y_2) ( x 2 , y 2 ) . If V 1 > V 2 V_1 > V_2 V 1 > V 2 and y 1 < q 1 y_1 < q_1 y 1 < q 1 , then x 2 = y 2 = 0 x_2 = y_2 = 0 x 2 = y 2 = 0 .
Proof. Suppose x 2 > 0 x_2 > 0 x 2 > 0 . Choose a price P ∈ ( V 2 , V 1 ) P \in(V_2,V_1) P ∈ ( V 2 , V 1 ) and a sufficiently small δ > 0 \delta> 0 δ > 0 such that P δ ≤ q 1 − y 1 P\delta\le q_1 - y_1 P δ ≤ q 1 − y 1 and δ < x 2 \delta< x_2 δ < x 2 . Let user 1 give P δ P\delta P δ units of Y Y Y to user 2 in exchange for δ \delta δ units of X X X . The utility gains are ( V 1 − P ) δ > 0 (V_1 - P)\delta> 0 ( V 1 − P ) δ > 0 and ( P − V 2 ) δ > 0 (P - V_2)\delta> 0 ( P − V 2 ) δ > 0 , and both users retain nonnegative holdings. This contradicts the internal-trade clause of weak Pareto optimality. Hence x 2 = 0 x_2 = 0 x 2 = 0 , and individual rationality with V 2 > 0 V_2 > 0 V 2 > 0 forces y 2 = 0 y_2 = 0 y 2 = 0 .
We will repeatedly use two other consequences of individual rationality, settlement, and weak Pareto optimality. Write Y = y 1 + y 2 Y = y_1 + y_2 Y = y 1 + y 2 . First, if either user has unspent budget, a small additional payment to the terminal pool cannot be profitable, so
y 1 < q 1 ⟹ V 1 F ′ ( Y ) ≤ 1 , y 2 < q 2 ⟹ V 2 F ′ ( Y ) ≤ 1. (72) \begin{aligned}
y_1 < q_1 &\Longrightarrow V_1 F'(Y) \le1,\\
y_2 < q_2 &\Longrightarrow V_2 F'(Y) \le1. \tag*{(72)}
\end{aligned} y 1 < q 1 y 2 < q 2 ⟹ V 1 F ′ ( Y ) ≤ 1 , ⟹ V 2 F ′ ( Y ) ≤ 1. (72)
Second, if V max : = max { V 1 , V 2 } > 1 V_{\max} := \max\{V_1,V_2\} > 1 V m a x := max { V 1 , V 2 } > 1 , individual rationality and exact settlement give
F ( Y ) = x 1 + x 2 ≥ y 1 V 1 + y 2 V 2 ≥ Y V max , F(Y) = x_1 + x_2 \ge\frac{y_1}{V_1} + \frac{y_2}{V_2} \ge\frac{Y}{V_{\max}}, F ( Y ) = x 1 + x 2 ≥ V 1 y 1 + V 2 y 2 ≥ V m a x Y ,
and hence Y ≤ y ˉ ( V max ) Y \le\bar{y}(V_{\max}) Y ≤ y ˉ ( V m a x ) .
{#eq:73}
We next derive several standard consequences of value incentive compatibility when the reported budget is held fixed. In particular, incentive compatibility implies the continuity properties used later; we do not separately assume that the mechanism or its allocation and payment rules are continuous.
Lemma 7.3 (Fixed-budget Myerson lemma [38 ] ). Fix one user’s declared budget q q q and the other user’s report. Let ( x ( V ) , y ( V ) ) (x(V),y(V)) ( x ( V ) , y ( V )) be its outcome when its reported value is V V V , and put Util ( V ) : = V x ( V ) − y ( V ) \operatorname{Util}(V) := Vx(V)-y(V) Util ( V ) := V x ( V ) − y ( V ) . On the eligible interval [ 1 , ∞ ) [1,\infty) [ 1 , ∞ ) , the functions x x x , y y y , and Util \operatorname{Util} Util are nondecreasing, and Util \operatorname{Util} Util is nonnegative, convex, and continuous (with one-sided continuity at 1 1 1 ). Moreover, the standard single-parameter payment identity and its normalized-utility form are, for 1 ≤ V < W 1 \le V < W 1 ≤ V < W ,
Util ( W ) − Util ( V ) = ∫ V W x ( t ) d t , Util ( W ) W − Util ( V ) V = ∫ V W y ( t ) t 2 d t . (73) \operatorname{Util}(W)-\operatorname{Util}(V)=\int_V^W x(t)\,\mathrm{d}t,\qquad
\frac{\operatorname{Util}(W)}{W}-\frac{\operatorname{Util}(V)}{V}=\int_V^W\frac{y(t)}{t^2}\,\mathrm{d}t. \tag*{(73)} Util ( W ) − Util ( V ) = ∫ V W x ( t ) d t , W Util ( W ) − V Util ( V ) = ∫ V W t 2 y ( t ) d t . (73)
Proof. For eligible values 1 ≤ V < W 1 \le V < W 1 ≤ V < W , incentive compatibility in both directions gives
x ( W ) ≥ x ( V ) , V ( x ( W ) − x ( V ) ) ≤ y ( W ) − y ( V ) ≤ W ( x ( W ) − x ( V ) ) . x(W)\ge x(V),\qquad V\bigl(x(W)-x(V)\bigr)\le y(W)-y(V)\le W\bigl(x(W)-x(V)\bigr). x ( W ) ≥ x ( V ) , V ( x ( W ) − x ( V ) ) ≤ y ( W ) − y ( V ) ≤ W ( x ( W ) − x ( V ) ) .
Thus allocation and payment are nondecreasing. Moreover,
Util ( V ) = sup v ≥ 1 { V x ( v ) − y ( v ) } , \operatorname{Util}(V)=\sup_{v\ge1}\{Vx(v)-y(v)\}, Util ( V ) = v ≥ 1 sup { V x ( v ) − y ( v )} ,
with the supremum attained at v = V v=V v = V . It is therefore a finite convex nondecreasing function, and hence continuous; individual rationality makes it nonnegative.
The same incentive inequalities bound Util ( W ) − Util ( V ) \operatorname{Util}(W)-\operatorname{Util}(V) Util ( W ) − Util ( V ) between ( W − V ) x ( V ) (W-V)x(V) ( W − V ) x ( V ) and ( W − V ) x ( W ) (W-V)x(W) ( W − V ) x ( W ) . Summing over partitions and taking upper and lower sums gives the first identity in (73) . Thus Util \operatorname{Util} Util is locally absolutely continuous and Util ′ ( V ) = x ( V ) \operatorname{Util}'(V)=x(V) Util ′ ( V ) = x ( V ) almost everywhere. Since Util ( V ) = V x ( V ) − y ( V ) \operatorname{Util}(V)=Vx(V)-y(V) Util ( V ) = V x ( V ) − y ( V ) , it follows almost everywhere that
d d V ( Util ( V ) V ) = V x ( V ) − Util ( V ) V 2 = y ( V ) V 2 . \frac{\mathrm{d}}{\mathrm{d}V}\left(\frac{\operatorname{Util}(V)}{V}\right)=\frac{Vx(V)-\operatorname{Util}(V)}{V^2}=\frac{y(V)}{V^2}. d V d ( V Util ( V ) ) = V 2 V x ( V ) − Util ( V ) = V 2 y ( V ) .
Integrating proves the second identity.
The next lemma establishes the spot-price normalization needed below using only eligible reports: when one user’s value equals the initial spot price, that user receives nothing. Intuitively, such a user gains nothing from the pool, whose average price exceeds the spot price, so it could gain only by being subsidized by the other user; weak Pareto optimality alone does not exclude this when the other user has exhausted its budget. The proof instead squeezes the other user’s utility: incentive compatibility, through the normalized-utility identity of Theorem 7.3, guarantees it at least the utility it would obtain by trading alone against the pool, whereas feasibility caps it at that amount, with a strict loss whenever the spot-value user receives any allocation.
Lemma 7.4 (A spot-value user receives zero). For any budgets q , Q ≥ 0 q,Q\ge0 q , Q ≥ 0 and any eligible value V ≥ 1 V\ge1 V ≥ 1 , consider the profile
( ( V , q ) , ( 1 , Q ) ) . ((V,q),(1,Q)). (( V , q ) , ( 1 , Q )) . The spot-value user receives ( x 2 , y 2 ) = ( 0 , 0 ) (x_2,y_2)=(0,0) ( x 2 , y 2 ) = ( 0 , 0 ) , while the first user receives the sole-user optimum
y 1 = min { q , y ⋆ ( V ) } , x 1 = F ( y 1 ) . y_1=\min\{q,y^\star(V)\},\qquad x_1=F(y_1). y 1 = min { q , y ⋆ ( V )} , x 1 = F ( y 1 ) . The same conclusion holds with the two user positions interchanged.
Proof. Fix the second report ( 1 , Q ) (1,Q) ( 1 , Q ) , vary the first user’s reported value V > 1 V>1 V > 1 , and write its outcome as ( x 1 ( V ) , y 1 ( V ) ) (x_1(V),y_1(V)) ( x 1 ( V ) , y 1 ( V )) and its reported utility as Util 1 ( V ) : = V x 1 ( V ) − y 1 ( V ) \operatorname{Util}_1(V):=Vx_1(V)-y_1(V) Util 1 ( V ) := V x 1 ( V ) − y 1 ( V ) . At V = 1 V=1 V = 1 , both values equal the spot value. Individual rationality and exact settlement imply F ( Y ) = x 1 + x 2 ≥ Y F(Y)=x_1+x_2\ge Y F ( Y ) = x 1 + x 2 ≥ Y . Since F ( Y ) < Y F(Y)<Y F ( Y ) < Y for Y > 0 Y>0 Y > 0 , both users receive zero and Util 1 ( 1 ) = 0 \operatorname{Util}_1(1)=0 Util 1 ( 1 ) = 0 .
Now let V > 1 V>1 V > 1 . If the first user does not exhaust its budget, Theorem 7.2 gives x 2 = y 2 = 0 x_2=y_2=0 x 2 = y 2 = 0 , and (72) gives V F ′ ( y 1 ( V ) ) ≤ 1 VF'(y_1(V))\le1 V F ′ ( y 1 ( V )) ≤ 1 , or equivalently y 1 ( V ) ≥ y ⋆ ( V ) y_1(V)\ge y^\star(V) y 1 ( V ) ≥ y ⋆ ( V ) . If it does exhaust its budget, y 1 ( V ) = q y_1(V)=q y 1 ( V ) = q . Consequently
y 1 ( V ) ≥ min { q , y ⋆ ( V ) } . y_1(V)\ge\min\{q,y^\star(V)\}. y 1 ( V ) ≥ min { q , y ⋆ ( V )} .
The normalized-utility identity in (73) now gives
Util 1 ( V ) V ≥ ∫ 1 V min { q , y ⋆ ( t ) } t 2 d t = max 0 ≤ z ≤ q { F ( z ) − z V } . \frac{\operatorname{Util}_1(V)}{V}\ge\int_1^V \frac{\min\{q,y^\star(t)\}}{t^2}\,\mathrm{d}t
=\max_{0\le z\le q}\left\{F(z)-\frac{z}{V}\right\}. V Util 1 ( V ) ≥ ∫ 1 V t 2 min { q , y ⋆ ( t )} d t = 0 ≤ z ≤ q max { F ( z ) − V z } .
For the equality, the maximizer on the right is z = min { q , y ⋆ ( V ) } z=\min\{q,y^\star(V)\} z = min { q , y ⋆ ( V )} ; differentiating both sides with respect to V V V , starting from their common value zero at V = 1 V=1 V = 1 , gives the same integrand.
Conversely, individual rationality for the spot-value user gives x 2 ≥ y 2 x_2\ge y_2 x 2 ≥ y 2 . Exact settlement and F ′ ≤ 1 F'\le1 F ′ ≤ 1 therefore imply
Util 1 ( V ) V = F ( y 1 + y 2 ) − x 2 − y 1 V ≤ F ( y 1 + y 2 ) − y 2 − y 1 V ≤ F ( y 1 ) − y 1 V ≤ max 0 ≤ z ≤ q { F ( z ) − z V } . \begin{aligned}
\frac{\operatorname{Util}_1(V)}{V}=F(y_1+y_2)-x_2-\frac{y_1}{V} \\
&\le F(y_1+y_2)-y_2-\frac{y_1}{V} \\
&\le F(y_1)-\frac{y_1}{V} \\
&\le\max_{0\le z\le q}\left\{F(z)-\frac{z}{V}\right\}.
\end{aligned} V Util 1 ( V ) = F ( y 1 + y 2 ) − x 2 − V y 1 ≤ F ( y 1 + y 2 ) − y 2 − V y 1 ≤ F ( y 1 ) − V y 1 ≤ 0 ≤ z ≤ q max { F ( z ) − V z } .
The second inequality is strict when y 2 > 0 y_2>0 y 2 > 0 . Equality with the lower bound forces y 2 = 0 y_2=0 y 2 = 0 , then x 2 = 0 x_2=0 x 2 = 0 , and strict concavity of F F F forces y 1 = min { q , y ⋆ ( V ) } y_1=\min\{q,y^\star(V)\} y 1 = min { q , y ⋆ ( V )} . Interchanging the fixed user positions gives the same proof; no symmetry assumption is needed. □
Consequently, no eligible report can buy X X X below the spot price: a user with the spot value, which obtains zero utility by Theorem 7.4, could otherwise profit by imitating that report.
Corollary 7.5 (Spot-price payment bound). Every profile of two eligible users satisfies
x 1 ≤ y 1 and x 2 ≤ y 2 . x_1\le y_1 \qquad\text{and}\qquad x_2\le y_2. x 1 ≤ y 1 and x 2 ≤ y 2 . In particular, a user that pays zero receives zero.
Proof. Hold user 2’s eligible report fixed. If user 1 had the spot value 1 and its current budget, Theorem 7.4 would give it zero utility. It can instead submit its current eligible value report without changing its budget. Incentive compatibility for the spot-value true type therefore gives 0 ≥ x 1 − y 1 0\ge x_1-y_1 0 ≥ x 1 − y 1 . Interchanging the two user positions gives 0 ≥ x 2 − y 2 0\ge x_2-y_2 0 ≥ x 2 − y 2 . □
Two Large-Budget Comparisons
We now establish two complementary facts. In the first, a large declared budget belongs to the lower-valued user. In the second, it belongs to the higher-valued user. Together they show that a declared budget can control the allocation even when most of that budget is never paid.
Theorem 7.6 below considers the former case. It shows that a lower-valued user with a large budget sets the price for a budget-constrained higher-valued user, much as a second price would: the higher-valued user spends its entire budget at a unit price equal to the lower value. The lower-valued user takes the remaining supply at a strictly positive profit, and its payment stays bounded no matter how large its declared budget is.
Lemma 7.6 (Large budget on the lower-valued user). Fix V 1 > 1 V_1>1 V 1 > 1 , 0 < Q 1 < y ˉ ( V 1 ) 0<Q_1<\bar{y}(V_1) 0 < Q 1 < y ˉ ( V 1 ) , and Q l a r g e > y ˉ ( V 1 ) Q^{\mathrm{large}}>\bar{y}(V_1) Q large > y ˉ ( V 1 ) , and put
V c u t : = Q 1 F ( Q 1 ) = 1 + Q 1 , V_{\mathrm{cut}}:=\frac{Q_1}{F(Q_1)}=1+Q_1, V cut := F ( Q 1 ) Q 1 = 1 + Q 1 , so that 1 < V c u t < V 1 1<V_{\mathrm{cut}}<V_1 1 < V cut < V 1 . For every V 2 ∈ ( V c u t , V 1 ) V_2\in(V_{\mathrm{cut}},V_1) V 2 ∈ ( V cut , V 1 ) , the profile ( ( V 1 , Q 1 ) , ( V 2 , Q l a r g e ) ) ((V_1,Q_1),(V_2,Q^{\mathrm{large}})) (( V 1 , Q 1 ) , ( V 2 , Q large )) satisfies
y 1 = Q 1 , x 1 = Q 1 V 2 , y 2 ≤ y ˉ ( V 2 ) − Q 1 , V 2 x 2 − y 2 > 0. (74) y_1=Q_1,\qquad x_1=\frac{Q_1}{V_2},\qquad y_2\leq\bar{y}(V_2)-Q_1,\qquad V_2x_2-y_2>0. \tag*{(74)} y 1 = Q 1 , x 1 = V 2 Q 1 , y 2 ≤ y ˉ ( V 2 ) − Q 1 , V 2 x 2 − y 2 > 0. (74)
Proof. Fix V 2 V_2 V 2 , vary the first user’s value v ∈ [ 1 , V 1 ] v\in[1,V_1] v ∈ [ 1 , V 1 ] while holding its budget at Q 1 Q_1 Q 1 , and keep the second report ( V 2 , Q l a r g e ) (V_2,Q^{\mathrm{large}}) ( V 2 , Q large ) fixed. Write ( x 1 ( v ) , y 1 ( v ) ) (x_1(v),y_1(v)) ( x 1 ( v ) , y 1 ( v )) for the first user’s outcome and Util 1 ( v ) : = v x 1 ( v ) − y 1 ( v ) \operatorname{Util}_1(v):=vx_1(v)-y_1(v) Util 1 ( v ) := v x 1 ( v ) − y 1 ( v ) . By (73), total payment never exceeds y ˉ ( V 1 ) < Q l a r g e \bar{y}(V_1)<Q^{\mathrm{large}} y ˉ ( V 1 ) < Q large , so the second user always has unspent budget.
When v < V 2 v<V_2 v < V 2 , internal-trade priority gives ( x 1 ( v ) , y 1 ( v ) ) = ( 0 , 0 ) (x_1(v),y_1(v))=(0,0) ( x 1 ( v ) , y 1 ( v )) = ( 0 , 0 ) ; continuity therefore gives Util 1 ( V 2 ) = 0 \operatorname{Util}_1(V_2)=0 Util 1 ( V 2 ) = 0 . Suppose y 1 ( v 0 ) < Q 1 y_1(v_0)<Q_1 y 1 ( v 0 ) < Q 1 for some v 0 > V 2 v_0>V_2 v 0 > V 2 . Payment monotonicity then gives y 1 ( v ) < Q 1 y_1(v)<Q_1 y 1 ( v ) < Q 1 throughout a right neighborhood of V 2 V_2 V 2 . The first user is the higher-valued user there and also has unspent budget, so priority gives the second user zero. Exact settlement and the pool condition imply
x 1 ( v ) = F ( y 1 ( v ) ) , y 1 ( v ) ≥ y ∗ ( v ) , Util 1 ( v ) = Util p o o l ( v , y 1 ( v ) ) . x_1(v)=F(y_1(v)),\qquad y_1(v)\geq y^*(v),\qquad\operatorname{Util}_1(v)=\operatorname{Util}^{\mathrm{pool}}(v,y_1(v)). x 1 ( v ) = F ( y 1 ( v )) , y 1 ( v ) ≥ y ∗ ( v ) , Util 1 ( v ) = Util pool ( v , y 1 ( v )) .
The monotone limit y l i m : = lim v ↓ V 2 y 1 ( v ) y_{\mathrm{lim}}:=\lim_{v\downarrow V_2}y_1(v) y lim := lim v ↓ V 2 y 1 ( v ) consequently satisfies
y ∗ ( V 2 ) ≤ y l i m < Q 1 < y ˉ ( V 2 ) . y^*(V_2)\leq y_{\mathrm{lim}}<Q_1<\bar{y}(V_2). y ∗ ( V 2 ) ≤ y lim < Q 1 < y ˉ ( V 2 ) .
Continuity of Util 1 \operatorname{Util}_1 Util 1 would give Util p o o l ( V 2 , y l i m ) = Util 1 ( V 2 ) = 0 \operatorname{Util}^{\mathrm{pool}}(V_2,y_{\mathrm{lim}})=\operatorname{Util}_1(V_2)=0 Util pool ( V 2 , y lim ) = Util 1 ( V 2 ) = 0 , contradicting the fact that Util p o o l ( V 2 , ⋅ ) \operatorname{Util}^{\mathrm{pool}}(V_2,\cdot) Util pool ( V 2 , ⋅ ) is strictly positive between its two zeros. Hence y 1 ( v ) = Q 1 y_1(v)=Q_1 y 1 ( v ) = Q 1 for every v ∈ ( V 2 , V 1 ] v\in(V_2,V_1] v ∈ ( V 2 , V 1 ] .
With payment fixed at Q 1 Q_1 Q 1 , incentive compatibility forces allocation to be constant on this interval, say x 1 ( v ) = x c o n s t x_1(v)=x_{\mathrm{const}} x 1 ( v ) = x const . Taking v ↓ V 2 v\downarrow V_2 v ↓ V 2 in Util 1 ( v ) = v x c o n s t − Q 1 \operatorname{Util}_1(v)=vx_{\mathrm{const}}-Q_1 Util 1 ( v ) = v x const − Q 1 gives V 2 x c o n s t − Q 1 = Util 1 ( V 2 ) = 0 V_2x_{\mathrm{const}}-Q_1=\operatorname{Util}_1(V_2)=0 V 2 x const − Q 1 = Util 1 ( V 2 ) = 0 , so x c o n s t = Q 1 / V 2 x_{\mathrm{const}}=Q_1/V_2 x const = Q 1 / V 2 . This proves the first two claims in (74) . Individual rationality for user 2 and exact settlement give
F ( Q 1 + y 2 ) = Q 1 V 2 + x 2 ≥ Q 1 + y 2 V 2 F(Q_1+y_2)=\frac{Q_1}{V_2}+x_2\geq\frac{Q_1+y_2}{V_2} F ( Q 1 + y 2 ) = V 2 Q 1 + x 2 ≥ V 2 Q 1 + y 2
and therefore Q 1 + y 2 ≤ y ˉ ( V 2 ) Q_1+y_2\le\bar{y}(V_2) Q 1 + y 2 ≤ y ˉ ( V 2 ) .
It remains to show that user 2 has strictly positive utility. Keep the first report ( V 1 , Q 1 ) (V_1,Q_1) ( V 1 , Q 1 ) fixed, vary user 2’s reported value v v v while holding its declared budget at Q l a r g e Q^{\mathrm{large}} Q large , and write its reported utility v x 2 − y 2 vx_2-y_2 v x 2 − y 2 as Util 2 ( v ) \operatorname{Util}_2(v) Util 2 ( v ) . If Util 2 ( V 2 ) = 0 \operatorname{Util}_2(V_2)=0 Util 2 ( V 2 ) = 0 , nonnegativity and monotonicity give Util 2 ( v ) = 0 \operatorname{Util}_2(v)=0 Util 2 ( v ) = 0 for every v ∈ ( V c u t , V 2 ) v\in(V_{\mathrm{cut}},V_2) v ∈ ( V cut , V 2 ) . Choose such a v v v . The conclusions already proved give y 1 = Q 1 y_1=Q_1 y 1 = Q 1 and x 1 = Q 1 / v x_1=Q_1/v x 1 = Q 1 / v . Zero utility for user 2 and exact settlement then give
F ( Q 1 + y 2 ) = Q 1 + y 2 v , y 2 = y ˉ ( v ) − Q 1 > 0. F(Q_1+y_2)=\frac{Q_1+y_2}{v},\qquad y_2=\bar{y}(v)-Q_1>0. F ( Q 1 + y 2 ) = v Q 1 + y 2 , y 2 = y ˉ ( v ) − Q 1 > 0.
A true type ( V 2 , Q l a r g e ) (V_2,Q^{\mathrm{large}}) ( V 2 , Q large ) could instead report ( v , Q l a r g e ) (v,Q^{\mathrm{large}}) ( v , Q large ) and obtain ( V 2 − v ) x 2 > 0 (V_2-v)x_2>0 ( V 2 − v ) x 2 > 0 , contradicting incentive compatibility. Thus Util 2 ( V 2 ) > 0 \operatorname{Util}_2(V_2)>0 Util 2 ( V 2 ) > 0 .
Theorem 7.7 below considers the mirror case, in which the higher-valued user has a large budget. It shows that this user effectively trades alone against the pool, while the lower-valued user receives nothing. The only thing the mechanism can do to the higher-valued user is impose a minimum purchase, and incentive compatibility keeps the resulting overpayment small when the lower-valued user’s budget is small.
Lemma 7.7 (Large budget on the higher-valued user). Fix V 1 > V 2 > 1 V_1>V_2>1 V 1 > V 2 > 1 , Q 2 > 0 Q_2>0 Q 2 > 0 , and Q l a r g e > y ˉ ( V 1 ) Q^{\mathrm{large}}>\bar{y}(V_1) Q large > y ˉ ( V 1 ) . For v ∈ [ V 2 , V 1 ] v\in[V_2,V_1] v ∈ [ V 2 , V 1 ] , consider the profile ( ( v , Q l a r g e ) , ( V 2 , Q 2 ) ) ((v,Q^{\mathrm{large}}),(V_2,Q_2)) (( v , Q large ) , ( V 2 , Q 2 )) , and write the first user’s outcome as ( x 1 ( v ) , y 1 ( v ) ) (x_1(v),y_1(v)) ( x 1 ( v ) , y 1 ( v )) . For v > V 2 v>V_2 v > V 2 , user 2 receives zero and
x 1 ( v ) = F ( y 1 ( v ) ) , y 1 ( v ) ≥ y ⋆ ( v ) . x_1(v)=F(y_1(v)),\qquad y_1(v)\ge y^\star(v). x 1 ( v ) = F ( y 1 ( v )) , y 1 ( v ) ≥ y ⋆ ( v ) . The limit y l i m : = lim v ↓ V 2 y 1 ( v ) y_{\mathrm{lim}}:=\lim_{v\downarrow V_2}y_1(v) y lim := lim v ↓ V 2 y 1 ( v ) exists and satisfies
y l i m ≥ y ⋆ ( V 2 ) , Util p o o l ( V 2 , y l i m ) ≥ Util p o o l ( V 2 , y ⋆ ( V 2 ) ) − V 2 Q 2 , (75) y_{\mathrm{lim}}\ge y^\star(V_2),\qquad\operatorname{Util}^{\mathrm{pool}}(V_2,y_{\mathrm{lim}})\ge\operatorname{Util}^{\mathrm{pool}}(V_2,y^\star(V_2))-V_2Q_2, \tag*{(75)} y lim ≥ y ⋆ ( V 2 ) , Util pool ( V 2 , y lim ) ≥ Util pool ( V 2 , y ⋆ ( V 2 )) − V 2 Q 2 , (75) and, for every v ∈ ( V 2 , V 1 ] v\in(V_2,V_1] v ∈ ( V 2 , V 1 ] ,
y 1 ( v ) = max { y l i m , y ⋆ ( v ) } . (76) y_1(v)=\max\{y_{\mathrm{lim}},y^\star(v)\}. \tag*{(76)} y 1 ( v ) = max { y lim , y ⋆ ( v )} . (76)
Proof. The total-payment bound gives Y ≤ y ˉ ( V 1 ) < Q l a r g e Y\le\bar{y}(V_1)<Q^{\mathrm{large}} Y ≤ y ˉ ( V 1 ) < Q large , so the first user never exhausts its declared budget. For v > V 2 v>V_2 v > V 2 , internal-trade priority therefore gives user 2 zero. Settlement and the pool condition yield the two displayed assertions. Monotonicity and boundedness of y 1 y_1 y 1 give the limit y l i m ≥ y ⋆ ( V 2 ) y_{\mathrm{lim}}\ge y^\star(V_2) y lim ≥ y ⋆ ( V 2 ) . If Util 1 ( v ) : = v x 1 ( v ) − y 1 ( v ) \operatorname{Util}_1(v):=vx_1(v)-y_1(v) Util 1 ( v ) := v x 1 ( v ) − y 1 ( v ) , continuity gives
Util 1 ( V 2 ) = lim v ↓ V 2 Util p o o l ( v , y 1 ( v ) ) = Util p o o l ( V 2 , y l i m ) . \operatorname{Util}_1(V_2)=\lim_{v\downarrow V_2}\operatorname{Util}^{\mathrm{pool}}(v,y_1(v))=\operatorname{Util}^{\mathrm{pool}}(V_2,y_{\mathrm{lim}}). Util 1 ( V 2 ) = v ↓ V 2 lim Util pool ( v , y 1 ( v )) = Util pool ( V 2 , y lim ) .
To lower-bound this utility, choose a finite eligible value v a u x v_{\mathrm{aux}} v aux so large that
v a u x F ′ ( y ⋆ ( V 2 ) + Q 2 ) > 1. v_{\mathrm{aux}}F'\bigl(y^\star(V_2)+Q_2\bigr)>1. v aux F ′ ( y ⋆ ( V 2 ) + Q 2 ) > 1.
A true type ( V 2 , Q l a r g e ) (V_2,Q^{\mathrm{large}}) ( V 2 , Q large ) can deviate to the report ( v a u x , y ⋆ ( V 2 ) ) (v_{\mathrm{aux}},y^\star(V_2)) ( v aux , y ⋆ ( V 2 )) . In the resulting profile ( ( v a u x , y ⋆ ( V 2 ) ) , ( V 2 , Q 2 ) ) ((v_{\mathrm{aux}},y^\star(V_2)),(V_2,Q_2)) (( v aux , y ⋆ ( V 2 )) , ( V 2 , Q 2 )) , the first user must pay all y ⋆ ( V 2 ) y^\star(V_2) y ⋆ ( V 2 ) : otherwise it would have unspent budget and (72) , together with Y < y ⋆ ( V 2 ) + Q 2 Y<y^\star(V_2)+Q_2 Y < y ⋆ ( V 2 ) + Q 2 , would imply
1 ≥ v a u x F ′ ( Y ) ≥ v a u x F ′ ( y ⋆ ( V 2 ) + Q 2 ) > 1. 1\ge v_{\mathrm{aux}}F'(Y)\ge v_{\mathrm{aux}}F'\bigl(y^\star(V_2)+Q_2\bigr)>1. 1 ≥ v aux F ′ ( Y ) ≥ v aux F ′ ( y ⋆ ( V 2 ) + Q 2 ) > 1.
By Theorem 7.5 , user 2 receives at most x 2 ≤ y 2 ≤ Q 2 x_2 \le y_2 \le Q_2 x 2 ≤ y 2 ≤ Q 2 . Exact settlement therefore gives the deviating user at least F ( y ∗ ( V 2 ) ) − Q 2 F(y^*(V_2))-Q_2 F ( y ∗ ( V 2 )) − Q 2 units of X X X . The deviation is affordable because it pays y ∗ ( V 2 ) < Q l a r g e y^*(V_2)<Q^{\mathrm{large}} y ∗ ( V 2 ) < Q large , and incentive compatibility yields
Util p o o l ( V 2 , y l i m ) = Util 1 ( V 2 ) ≥ V 2 ( F ( y ∗ ( V 2 ) ) − Q 2 ) − y ∗ ( V 2 ) = Util p o o l ( V 2 , y ∗ ( V 2 ) ) − V 2 Q 2 . \begin{aligned}
\operatorname{Util}^{\mathrm{pool}}(V_2,y_{\mathrm{lim}})=\operatorname{Util}_1(V_2) \\
&\ge V_2\left(F(y^*(V_2))-Q_2\right)-y^*(V_2) \\
&=\operatorname{Util}^{\mathrm{pool}}(V_2,y^*(V_2))-V_2Q_2.
\end{aligned} Util pool ( V 2 , y lim ) = Util 1 ( V 2 ) ≥ V 2 ( F ( y ∗ ( V 2 )) − Q 2 ) − y ∗ ( V 2 ) = Util pool ( V 2 , y ∗ ( V 2 )) − V 2 Q 2 .
which proves (75) . Notice that v a u x v_{\mathrm{aux}} v aux is finite; the proof does not use an infinite value report.
It remains to identify the payment path. Payment monotonicity already gives y 1 ( v ) ≥ y l i m y_1(v)\ge y_{\mathrm{lim}} y 1 ( v ) ≥ y lim , and the pool condition gives y 1 ( v ) ≥ y ∗ ( v ) y_1(v)\ge y^*(v) y 1 ( v ) ≥ y ∗ ( v ) . The function y 1 y_1 y 1 is continuous on ( V 2 , V 1 ] (V_2,V_1] ( V 2 , V 1 ] : its one-sided limits exist by monotonicity, and continuity of Util 1 ( v ) = Util p o o l ( v , y 1 ( v ) ) \operatorname{Util}_1(v)=\operatorname{Util}^{\mathrm{pool}}(v,y_1(v)) Util 1 ( v ) = Util pool ( v , y 1 ( v )) , together with strict decrease of Util p o o l ( v , ⋅ ) \operatorname{Util}^{\mathrm{pool}}(v,\cdot) Util pool ( v , ⋅ ) on [ y ∗ ( v ) , ∞ ) [y^*(v),\infty) [ y ∗ ( v ) , ∞ ) , forces those limits to agree.
If y 1 ( v ) > max { y l i m , y ∗ ( v ) } y_1(v)>\max\{y_{\mathrm{lim}},y^*(v)\} y 1 ( v ) > max { y lim , y ∗ ( v )} at some v v v , continuity and the definition of y l i m y_{\mathrm{lim}} y lim provide v ′ ∈ ( V 2 , v ) v'\in(V_2,v) v ′ ∈ ( V 2 , v ) such that
max { y l i m , y ∗ ( v ) } < y 1 ( v ′ ) < y 1 ( v ) . \max\{y_{\mathrm{lim}},y^*(v)\}<y_1(v')<y_1(v). max { y lim , y ∗ ( v )} < y 1 ( v ′ ) < y 1 ( v ) .
Both reports give the first user the entire pool output. Because Util p o o l ( v , ⋅ ) \operatorname{Util}^{\mathrm{pool}}(v,\cdot) Util pool ( v , ⋅ ) strictly decreases above y ∗ ( v ) y^*(v) y ∗ ( v ) , a true value v v v would strictly prefer the report v ′ v' v ′ , contradicting incentive compatibility. This proves (76) .
The Contradiction
The proof constructs a truthful profile of two eligible users in which each user has an affordable budget overreport, that is, one whose realized payment does not exceed its true budget. By Theorem 7.7, the first user’s overreport guarantees it utility 1, which is the entire surplus that the batch can generate. By Theorem 7.6, the second user’s overreport guarantees it strictly positive utility. Incentive compatibility requires the truthful outcome to give each user at least what its overreport guarantees, and these two guarantees together exceed the available surplus.
Proof of Theorem 7.1 . In normalized units, consider the truthful profile
( V 1 , Q 1 ) = ( 4 , 1 ) , ( V 2 , Q 2 ) = ( 100 49 , 2 49 ) . (V_1,Q_1)=(4,1),\qquad(V_2,Q_2)=\left(\frac{100}{49},\frac{2}{49}\right). ( V 1 , Q 1 ) = ( 4 , 1 ) , ( V 2 , Q 2 ) = ( 49 100 , 49 2 ) .
and let Q l a r g e = 4 Q^{\mathrm{large}}=4 Q large = 4 be the larger budget used in the two deviations below. Both values are strictly eligible. Write Util 1 t r : = V 1 x 1 t r − y 1 t r \operatorname{Util}^{\mathrm{tr}}_1:=V_1x^{\mathrm{tr}}_1-y^{\mathrm{tr}}_1 Util 1 tr := V 1 x 1 tr − y 1 tr and Util 2 t r : = V 2 x 2 t r − y 2 t r \operatorname{Util}^{\mathrm{tr}}_2:=V_2x^{\mathrm{tr}}_2-y^{\mathrm{tr}}_2 Util 2 tr := V 2 x 2 tr − y 2 tr .
The first user can safely overreport its budget. Apply Theorem 7.7; its hypotheses hold because V 1 > V 2 > 1 V_1>V_2>1 V 1 > V 2 > 1 and Q l a r g e = 4 > y ˉ ( V 1 ) = 3 Q^{\mathrm{large}}=4>\bar y(V_1)=3 Q large = 4 > y ˉ ( V 1 ) = 3 . We have
y ∗ ( V 2 ) = 3 7 , Util p o o l ( V 2 , y ∗ ( V 2 ) ) = 9 49 , Util p o o l ( V 2 , 1 ) = 1 49 . y^*(V_2)=\frac{3}{7},\qquad\operatorname{Util}^{\mathrm{pool}}(V_2,y^*(V_2))=\frac{9}{49},\qquad\operatorname{Util}^{\mathrm{pool}}(V_2,1)=\frac{1}{49}. y ∗ ( V 2 ) = 7 3 , Util pool ( V 2 , y ∗ ( V 2 )) = 49 9 , Util pool ( V 2 , 1 ) = 49 1 .
Consequently,
Util p o o l ( V 2 , y l i m ) ≥ 9 49 − 100 49 ⋅ 2 49 = 241 2401 > 1 49 = Util p o o l ( V 2 , 1 ) . \operatorname{Util}^{\mathrm{pool}}(V_2,y_{\mathrm{lim}})\ge\frac{9}{49}-\frac{100}{49}\cdot\frac{2}{49}=\frac{241}{2401}>\frac{1}{49}=\operatorname{Util}^{\mathrm{pool}}(V_2,1). Util pool ( V 2 , y lim ) ≥ 49 9 − 49 100 ⋅ 49 2 = 2401 241 > 49 1 = Util pool ( V 2 , 1 ) .
Since y lim ≥ y ⋆ ( V 2 ) y_{\lim} \ge y^\star(V_2) y l i m ≥ y ⋆ ( V 2 ) and Util p o o l ( V 2 , ⋅ ) \operatorname{Util}^{\mathrm{pool}}(V_2,\cdot) Util pool ( V 2 , ⋅ ) strictly decreases after its maximizer, this implies y lim < 1 y_{\lim}<1 y l i m < 1 . Equation (76) at v = V 1 = 4 v=V_1=4 v = V 1 = 4 therefore gives
y 1 ( V 1 ) = max { y lim , y ⋆ ( 4 ) } = 1. y_1(V_1)=\max\{y_{\lim},y^\star(4)\}=1. y 1 ( V 1 ) = max { y l i m , y ⋆ ( 4 )} = 1.
Thus, if user 1 reports ( V 1 , Q l a r g e ) = ( 4 , 4 ) (V_1,Q^{\mathrm{large}})=(4,4) ( V 1 , Q large ) = ( 4 , 4 ) , it actually pays exactly its true budget Q 1 = 1 Q_1=1 Q 1 = 1 , receives F ( 1 ) = 1 / 2 F(1)=1/2 F ( 1 ) = 1/2 , and obtains utility 1. Incentive compatibility requires
Util 1 t r ≥ 1. (77) \operatorname{Util}_1^{\mathrm{tr}}\ge1. \tag*{(77)} Util 1 tr ≥ 1. (77)
The second user’s truthful utility must be zero. Let Y t r = y 1 t r + y 2 t r Y^{\mathrm{tr}}=y_1^{\mathrm{tr}}+y_2^{\mathrm{tr}} Y tr = y 1 tr + y 2 tr . Exact settlement and V 1 > V 2 V_1>V_2 V 1 > V 2 give
Util 1 t r + Util 2 t r = V 1 F ( Y t r ) − Y t r − ( V 1 − V 2 ) x 2 t r ≤ Util p o o l ( V 1 , Y t r ) ≤ Util p o o l ( V 1 , y ⋆ ( V 1 ) ) = 1. \operatorname{Util}_1^{\mathrm{tr}}+\operatorname{Util}_2^{\mathrm{tr}}
=V_1F(Y^{\mathrm{tr}})-Y^{\mathrm{tr}}-(V_1-V_2)x_2^{\mathrm{tr}}
\le\operatorname{Util}^{\mathrm{pool}}(V_1,Y^{\mathrm{tr}})
\le\operatorname{Util}^{\mathrm{pool}}(V_1,y^\star(V_1))=1. Util 1 tr + Util 2 tr = V 1 F ( Y tr ) − Y tr − ( V 1 − V 2 ) x 2 tr ≤ Util pool ( V 1 , Y tr ) ≤ Util pool ( V 1 , y ⋆ ( V 1 )) = 1.
Together with (77) and individual rationality, this forces Util 2 t r = 0 \operatorname{Util}_2^{\mathrm{tr}}=0 Util 2 tr = 0 .
The second user can also safely overreport its budget. Now let user 2 report ( V 2 , Q l a r g e ) (V_2,Q^{\mathrm{large}}) ( V 2 , Q large ) , keeping user 1 at ( V 1 , Q 1 ) (V_1,Q_1) ( V 1 , Q 1 ) . The hypotheses of Theorem 7.6 hold because
V c u t = Q 1 F ( Q 1 ) = 2 < V 2 < V 1 , Q l a r g e = 4 > y ˉ ( V 1 ) = 3. V_{\mathrm{cut}}=\frac{Q_1}{F(Q_1)}=2<V_2<V_1,\qquad Q^{\mathrm{large}}=4>\bar y(V_1)=3. V cut = F ( Q 1 ) Q 1 = 2 < V 2 < V 1 , Q large = 4 > y ˉ ( V 1 ) = 3.
The lemma gives user 2 strictly positive utility, while its realized payment satisfies
y 2 ≤ y ˉ ( V 2 ) − Q 1 = 51 49 − 1 = 2 49 = Q 2 . y_2\le\bar y(V_2)-Q_1=\frac{51}{49}-1=\frac{2}{49}=Q_2. y 2 ≤ y ˉ ( V 2 ) − Q 1 = 49 51 − 1 = 49 2 = Q 2 .
This deviation is therefore affordable under its true budget and strictly improves upon its truthful utility of zero, a contradiction.
Only the two deviations in the final contradiction overreport a budget. Every preparatory incentive comparison keeps the budget fixed or reports a smaller one. Both overreports keep the value truthful and realize a payment within the true budget. This pinpoints the obstruction: a declared budget can influence priority and allocation even when the mechanism never collects the overstated portion.
Finally, the theorem also rules out a two-sided mechanism with the same four properties. Restrict such a mechanism to the two sell-Y Y Y profiles used above. Exact settlement becomes x 1 + x 2 = F ( y 1 + y 2 ) x_1+x_2=F(y_1+y_2) x 1 + x 2 = F ( y 1 + y 2 ) , both weak-Pareto clauses remain applicable, and every deviation in the proof is still an available single sell-Y Y Y deviation. Thus the restricted mechanism would contradict Theorem 7.1 . The aggregate true-budget cap in Theorem 2.4 excludes exactly these two fatal deviations.
Acknowledgments
This work began in 2023, and the final writeup is a collaboration between human and artificial intelligence. Human intelligence was solely responsible for all the conceptual contributions, and for devising the main AMM adaptive clinching mechanism. AI proved our conjecture regarding Sybil-robust incentive compatibility.
Elaine Shi acknowledges Hubert Chan and Alireza Farhadi for helpful technical discussions during an earlier phase of the project. Elaine Shi is also grateful to Leo Fan and his family for their kindness, generosity, and the logistical support that made this cross-institutional collaboration possible.
Fixed and Online Supply as Constant Targets
The target-based clinching mechanism of § 4.1 separates the clinching mechanics from the source of supply. This appendix shows that the two classical supply models are instances of it: the ordinary adaptive clinching auction [16 , 4 ] for a fixed divisible supply, and adaptive clinching with exogenous online supply, due to Goel, Mirrokni, and Paes Leme [23 ] . In both cases the target ignores the auction state ( X , Y ) (X,Y) ( X , Y ) and the clock price: it is the constant function equal to the available supply. The admissibility requirements of Theorem 4.2 then hold trivially.
The main content of the appendix is a rule-by-rule correspondence showing that, with a constant target, the rules of § 3 reduce to those of the classical auction. The only genuine boundary convention is that the abstract clock starts at a positive price p ⋆ p_{\star} p ⋆ , whereas the classical clock starts at zero. A constant target also attains its capacity, but the zero-trade completion convention makes that boundary identical to the classical clock after all supply has been allocated and creates no exception in the incentive theorem.
Fixed Divisible Supply
The classical auction. We recall the adaptive clinching auction in the notation of § 3 . A divisible supply s > 0 s>0 s > 0 of a single good is offered to finitely many identities; [4 ] normalizes s = 1 s=1 s = 1 , whereas [23 ] keeps s s s general. Identity i i i reports a value v i ≥ 0 v_i \ge0 v i ≥ 0 per unit and a hard budget q i ≥ 0 q_i \ge0 q i ≥ 0 ; these are v i v_i v i and B i B_i B i in [4 , 23 ] . A price clock p p p ascends from zero. At clock price p p p , identity i i i has cumulative allocation x i x_i x i , cumulative payment y i y_i y i , and effective remaining budget b i b_i b i , which equals q i − y i q_i-y_i q i − y i while the identity is in the auction and is set to zero when it exits. The unallocated supply is S = s − ∑ i x i S=s-\sum_i x_i S = s − ∑ i x i , the demand of identity i i i is b i / p b_i/p b i / p , and the sets Active, Exit, and Clinch are those of (12) and (14) . The auction maintains the supply invariant (13) . Every trade is charged at the current clock price. A clinching identity trades at the rates
d x i d p = S p , d y i d p = S , d b i d p = − S , i ∈ C l i n c h , (78) \frac{dx_i}{dp}=\frac{S}{p}, \qquad\frac{dy_i}{dp}=S, \qquad\frac{db_i}{dp}=-S, \qquad i\in\mathrm{Clinch}, \tag*{(78)} d p d x i = p S , d p d y i = S , d p d b i = − S , i ∈ Clinch , (78)
and no other identity trades [BCMX10, Figure 1, Step (II)], [GMP13, Definition 4.2(ii)]. When the clock reaches the value of one or more identities, the stopping condition (20) is tested. If it holds, every active identity receives its full demand b i / p b_i/p b i / p , the exiting identities receive the rest of the supply, and the auction ends [4 Figure 1, Step (I)] .
Otherwise the exiting budgets are cancelled, and each active identity i i i clinches
( S − ∑ k ∈ A c t i v e ∖ { i } b k p ) + (79) \left(S-\sum_{k\in\mathrm{Active}\setminus\{i\}}\frac{b_k}{p}\right)^{+} \tag*{(79)} S − k ∈ Active ∖ { i } ∑ p b k + (79)
units at the exit price [4 Lemma 3.1] , [23 Definition 4.2(iv)] .
Definition A.1 (Constant target). Fix a supply s > 0 s>0 s > 0 and an initial price p ⋆ > 0 p_{\star}>0 p ⋆ > 0 . The constant target is
T s f i x ( p , X , Y ) ≔ s for every ( p , X , Y ) ∈ D s f i x , T_s^{\mathrm{fix}}(p,X,Y) \coloneqq s \qquad\text{for every }(p,X,Y)\in D_s^{\mathrm{fix}}, T s fix ( p , X , Y ) : = s for every ( p , X , Y ) ∈ D s fix , on the state domain
D s f i x ≔ { ( p , X , Y ) : p ≥ p ⋆ , 0 ≤ X ≤ s , Y ≥ 0 } , D_s^{\mathrm{fix}}\coloneqq\{(p,X,Y):p\ge p_{\star},\ 0\le X\le s,\ Y\ge0\}, D s fix : = {( p , X , Y ) : p ≥ p ⋆ , 0 ≤ X ≤ s , Y ≥ 0 } , Let σ f i x \sigma^{\mathrm{fix}} σ fix denote the trivial environment description, and define the constant-target specification
T s f i x ≔ ( p ⋆ , σ f i x , T s f i x , D s f i x , s ) . \mathcal{T}_s^{\mathrm{fix}}\coloneqq(p_{\star},\sigma^{\mathrm{fix}},T_s^{\mathrm{fix}},D_s^{\mathrm{fix}},s). T s fix : = ( p ⋆ , σ fix , T s fix , D s fix , s ) . Its residual supply S = s − X S=s-X S = s − X is the unallocated supply of the classical auction. For the unit supply of [4 ] , the target is the constant 1 1 1 .
Proposition A.2 (Admissibility of the constant-target specification). For every s > 0 s>0 s > 0 and p ⋆ > 0 p_{\star}>0 p ⋆ > 0 , T s f i x \mathcal{T}_s^{\mathrm{fix}} T s fix is an admissible abstract target-based mechanism. Its frozen-state clock rate vanishes, λ ≡ 0 \lambda\equiv0 λ ≡ 0 , and its only supply lump is the initial release T s f i x ( p ⋆ , 0 , 0 ) = s T_s^{\mathrm{fix}}(p_{\star},0,0)=s T s fix ( p ⋆ , 0 , 0 ) = s . Unlike the AMM capacity, the capacity s s s is attainable: T s f i x = X T_s^{\mathrm{fix}}=X T s fix = X precisely when X = s X=s X = s .
Proof. We verify the five requirements of Theorem 4.2 in order.
Feasibility and partition independence. On the domain, X ≤ s = T s f i x = X ‾ X\le s=T_s^{\mathrm{fix}}=\overline{X} X ≤ s = T s fix = X . A constant depends on the bidders through nothing at all; in particular it depends neither on their names nor on the partition of a budget among identities.
Fixed-price invariance. If 0 ≤ δ ≤ S = s − X 0\le\delta\le S=s-X 0 ≤ δ ≤ S = s − X , then X + δ ≤ s X+\delta\le s X + δ ≤ s and Y + p δ ≥ 0 Y+p\delta\ge0 Y + p δ ≥ 0 , so the updated state lies in D s f i x D_s^{\mathrm{fix}} D s fix . The target is unchanged because it is constant.
Target decreases with mark-to-market gain. Both targets in (26) equal s s s . The implication therefore holds, with equality, whatever the two gains are.
Clock regularity. For fixed ( X , Y ) (X,Y) ( X , Y ) , the map p ↦ s p\mapsto s p ↦ s is constant. It is nondecreasing, right-continuous, of bounded variation, free of jumps, and absolutely continuous, and (27) gives λ = 0 \lambda=0 λ = 0 .
Eventual supply release. The target equals X X X only if X = s = X ‾ X=s=\overline{X} X = s = X . Thus there is no state satisfying the premise T s f i x = X < X ‾ T_s^{\mathrm{fix}}=X<\overline{X} T s fix = X < X of (28) .
Finally, D s f i x D_s^{\mathrm{fix}} D s fix contains the initial state ( p ⋆ , 0 , 0 ) (p_{\star},0,0) ( p ⋆ , 0 , 0 ) and is closed under raising p p p with ( X , Y ) (X,Y) ( X , Y ) held fixed. The positive initial target is released at p ⋆ p_{\star} p ⋆ as the initial lump, as prescribed after (10) . □
Proposition A.3 (The constant-target mechanism is adaptive clinching). The target-based clinching mechanism associated with T s f i x \mathcal{T}_s^{\mathrm{fix}} T s fix is the adaptive clinching auction for supply s s s with its clock started at p ⋆ p_{\star} p ⋆ . Equivalently, apply the target substitution (29) with ( p ⋆ , T σ , X σ ) = ( p ⋆ , T s f i x , s ) (p_{\star},T_{\sigma},X_{\sigma})=(p_{\star},T_s^{\mathrm{fix}},s) ( p ⋆ , T σ , X σ ) = ( p ⋆ , T s fix , s ) . More precisely:
Start. Identities with v i < p ⋆ v_i < p_\star v i < p ⋆ are ineligible. The whole supply is released at p ⋆ p_\star p ⋆ as the initial lump, so S = s S=s S = s , and the event rules in items 3 and 4 are applied at p ⋆ p_\star p ⋆ , with the identities having v i = p ⋆ v_i=p_\star v i = p ⋆ as the exiting identities.
Continuous evolution. The derived rate (30) is γ = S \gamma=S γ = S . Clinching identities trade at the classical rates (78) , no other identity trades, and, with c = ∣ C l i n c h ∣ c=\lvert\mathrm{Clinch}\rvert c = ∣ Clinch ∣ *,
d S d p = − c S p , d h d p = − S . (80) \frac{\mathrm{d}S}{\mathrm{d}p}=-\frac{cS}{p},\qquad\frac{\mathrm{d}h}{\mathrm{d}p}=-S. \tag*{(80)} d p d S = − p c S , d p d h = − S . (80)
In particular, S S S remains positive between events.
Nonstopping exits. If the stopping test fails, the one-shot restoration purchase (24) of an active identity i i i is the classical clinch (79) .
Stopping. The stopping test (20) and the full-demand purchases of the active identities are Step (I) of [4 Figure 1] , and the proportional rule (22) specifies how the remainder L L L of (21) is divided among the exiting identities. At every stopping price above p ⋆ p_\star p ⋆ , some identity exits and
0 ≤ L ≤ 1 p ( B E − max i ∈ E x i t b i ) . (81) 0\le L\le\frac{1}{p}\left(B_E-\max_{i\in\mathrm{Exit}}b_i\right). \tag*{(81)} 0 ≤ L ≤ p 1 ( B E − i ∈ Exit max b i ) . (81)
Thus L = 0 L=0 L = 0 unless at least two identities exit simultaneously, the exiting identities can afford all of L L L , and the stopping allocation sells the entire residual supply.
Capacity completion and termination. After the initial release the target has no lump. A nonstopping event saturates capacity exactly when it leaves a single active identity, which buys the entire residual supply at that price. The allocation and payment are then complete, and the clock follows the zero-trade tail of Theorem 4.5 until that identity exits. Every run that does not enter such a tail ends with a stopping allocation. In particular, before capacity saturation at least two identities are active whenever a run continues.
Proof. Item 1 is the initialization rule stated after (10) , together with the eligibility rule that accompanies (29) .
For item 2, Theorem A.2 gives λ = 0 \lambda=0 λ = 0 , so Theorem 4.4 yields γ = S + p λ = S \gamma=S+p\lambda=S γ = S + p λ = S . Equations (31) and (32) then become (78) , and (33) becomes (80) . On an event-free interval beginning at p a p_a p a , the first equation integrates to S ( p ) = S ( p a ) ( p a / p ) c S(p)=S(p_a)(p_a/p)^c S ( p ) = S ( p a ) ( p a / p ) c , which is positive whenever S ( p a ) S(p_a) S ( p a ) is.
For item 3, after the cancellation (23) the aggregate budget is B = ∑ k ∈ A c t i v e b k B=\sum_{k\in\mathrm{Active}}b_k B = ∑ k ∈ Active b k . Hence h ⋆ = ∑ k ∈ A c t i v e b k − p S h^\star=\sum_{k\in\mathrm{Active}}b_k-pS h ⋆ = ∑ k ∈ Active b k − pS and
b i − h ⋆ p = S − ∑ k ∈ A c t i v e ∖ { i } b k p . (82) \frac{b_i-h^\star}{p}=S-\sum_{k\in\mathrm{Active}\setminus\{i\}}\frac{b_k}{p}. \tag*{(82)} p b i − h ⋆ = S − k ∈ Active ∖ { i } ∑ p b k . (82)
The purchase (24) is made exactly when this quantity is positive, which is (79) .
For item 4, the test and the purchases Buy ( i , b i / p ; p ) \operatorname{Buy}(i,b_i/p;p) Buy ( i , b i / p ; p ) are literally Step (I) of [4 Figure 1] . Let p > p ⋆ p>p_\star p > p ⋆ be a stopping price. Some identity exits at p p p . Indeed, by Theorem 4.7 the stopping test is equivalent to B E ≥ h B_E\ge h B E ≥ h . If an identity i i i is still active at p p p , then h ≥ b i > 0 h\ge b_i>0 h ≥ b i > 0 by (15) , so B E > 0 B_E>0 B E > 0 ; if none is were active immediately before p p p all exit at p p p . Every i ∈ E x i t i \in\mathrm{Exit} i ∈ Exit was active immediately before p p p , and a constant target has no lump at p p p . The supply invariant therefore gives
S ≤ D − i = ∑ k ∈ A c t i v e b k p + ∑ k ∈ E x i t ∖ { i } b k p . S \le D_{-i} = \sum_{k\in\mathrm{Active}} \frac{b_k}{p} + \sum_{k\in\mathrm{Exit}\setminus\{i\}} \frac{b_k}{p}. S ≤ D − i = k ∈ Active ∑ p b k + k ∈ Exit ∖ { i } ∑ p b k .
Subtracting the active demand yields L ≤ ( B E − b i ) / p L \le(B_E-b_i)/p L ≤ ( B E − b i ) / p for every i ∈ E x i t i \in\mathrm{Exit} i ∈ Exit , which is (81) ; and L ≥ 0 L \ge0 L ≥ 0 is the stopping test. Consequently L ≤ B E / p L \le B_E/p L ≤ B E / p , the proportional rule distributes exactly L L L , and the total stopping allocation is ∑ k ∈ A c t i v e b k / p + L = S \sum_{k\in\mathrm{Active}} b_k/p+L=S ∑ k ∈ Active b k / p + L = S .
For item 5, a lump is an upward jump of the target, and a constant has none after its initial release. By item 2, S S S does not vanish between events, so S = 0 S=0 S = 0 can only be produced by the fixed-price purchases of an event. A stopping event ends the run. At a nonstopping event, let m m m be the number of active identities with b i > h ⋆ b_i>h^\star b i > h ⋆ . If m = 0 m=0 m = 0 , nothing is bought and S S S stays positive. If m ≥ 1 m\ge1 m ≥ 1 , then p S = ∑ k ∈ A c t i v e b k − h ⋆ pS=\sum_{k\in\mathrm{Active}}b_k-h^\star pS = ∑ k ∈ Active b k − h ⋆ shows that the restoration purchases leave the residual supply
S = ∑ i ∈ A c t i v e ( b i − h ⋆ ) + p = 1 p ( ∑ i ∈ A c t i v e : b i ≤ h ⋆ b i + ( m − 1 ) h ⋆ ) . S=\sum_{i\in\mathrm{Active}}\frac{(b_i-h^\star)_+}{p}
=\frac{1}{p}\left(\sum_{i\in\mathrm{Active}:b_i\le h^\star}b_i+(m-1)h^\star\right). S = i ∈ Active ∑ p ( b i − h ⋆ ) + = p 1 ( i ∈ Active : b i ≤ h ⋆ ∑ b i + ( m − 1 ) h ⋆ ) .
Since h ⋆ > 0 h^\star>0 h ⋆ > 0 by Theorem 4.7 and active budgets are positive, this vanishes if and only if Active is a singleton. Conversely, a single active identity i i i at a nonstopping event has b i > b i − p S = h ⋆ b_i>b_i-pS=h^\star b i > b i − pS = h ⋆ and buys S S S by (82) . Then S = 0 S=0 S = 0 and X = s X=s X = s , so the capacity is saturated and Theorem 4.5 applies. An event that leaves no active identity passes the stopping test trivially. Hence, outside the zero-trade tail, at least two identities are active whenever a run continues.
The zero-trade completion in item 5 is exactly the classical convention: once the supply has been exhausted, the clock keeps rising with S = 0 S=0 S = 0 until the surviving identity reaches its value, and nothing further is traded. Apart from the start price, the only difference between the two descriptions is the treatment of identities that exit simultaneously. [4 , 23 ] process them one at a time in a fixed order. At a nonstopping event this produces the same state as the simultaneous cancellation and one-shot restoration, as noted after (24) . At a stopping event it divides L L L among the tied exiting identities in an order-dependent way, where the mechanism of § 3 uses the proportional rule. By item 4 of Theorem A.3, the two agree whenever no two identities exit at the stopping price.
The remaining difference is the start of the clock. The classical clock starts at zero, where every positive budget has infinite demand, whereas § 4.1 fixes p ⋆ > 0 p_\star>0 p ⋆ > 0 . By the zero-start auction we mean the auction of items 2–5 above with the clock started at zero and identities with v i = 0 v_i=0 v i = 0 removed at the outset. If a single identity of positive value and budget remains, no other identity has demand, and (79) lets it clinch the whole supply at price zero.
Lemma A.4 (Starting the clock at zero). Consider a profile in which the set P P P of identities with v i > 0 v_i>0 v i > 0 and q i > 0 q_i>0 q i > 0 has at least two elements, and put
p † : = min { min i ∈ P v i , 1 s ( ∑ i ∈ P q i − max i ∈ P q i ) } > 0. (83) p^\dagger:= \min\left\{\min_{i\in P}v_i,\frac{1}{s}\left(\sum_{i\in P}q_i-\max_{i\in P}q_i\right)\right\}>0. \tag*{(83)} p † := min { i ∈ P min v i , s 1 ( i ∈ P ∑ q i − i ∈ P max q i ) } > 0. (83) For every p ⋆ ∈ ( 0 , p † ) p_\star\in(0,p^\dagger) p ⋆ ∈ ( 0 , p † ) , the zero-start auction and the target-based mechanism for ( p ⋆ , T s f i x , s ) (p_\star,T^{\mathrm{fix}}_s,s) ( p ⋆ , T s fix , s ) produce the same outcome.
Proof. The price p † p^\dagger p † is the first event of the zero-start auction [23 proof of Theorem D.2] . Indeed, no identity of P P P exits below min i ∈ P v i \min_{i\in P} v_i min i ∈ P v i , and as long as nothing has been traded,
D − i = ∑ j ∈ P ∖ { i } q j p ≥ 1 p ( ∑ j ∈ P q j − max j ∈ P q j ) > s = S for p < p † , D_{-i}=\sum_{j\in P\setminus\{i\}}\frac{q_j}{p}\geq\frac{1}{p}\left(\sum_{j\in P}q_j-\max_{j\in P}q_j\right)>s=S\qquad\text{for }p<p^\dagger, D − i = j ∈ P ∖ { i } ∑ p q j ≥ p 1 j ∈ P ∑ q j − j ∈ P max q j > s = S for p < p † ,
so the supply invariant is strict and nobody clinches. At price p ⋆ < p † p_\star<p^\dagger p ⋆ < p † the state of the zero-start auction is therefore x i = y i = 0 x_i=y_i=0 x i = y i = 0 , b i = q i b_i=q_i b i = q i for i ∈ P i\in P i ∈ P , and S = s S=s S = s .
This is also the state of the target-based mechanism after its initial event. Identities outside P P P are ineligible or have no budget. No identity of P P P has v i = p ⋆ v_i=p_\star v i = p ⋆ , so none exits. The stopping test fails because ∑ i ∈ P q i > p ⋆ s \sum_{i\in P}q_i>p_\star s ∑ i ∈ P q i > p ⋆ s . After the initial release, h ⋆ = ∑ i ∈ P q i − p ⋆ s > max i ∈ P q i h^\star=\sum_{i\in P}q_i-p_\star s>\max_{i\in P}q_i h ⋆ = ∑ i ∈ P q i − p ⋆ s > max i ∈ P q i , so no restoration purchase is made. From p ⋆ p_\star p ⋆ on, both auctions follow the rules of Theorem A.3.
Thus p ⋆ p_\star p ⋆ acts as a reserve price, and the classical auction is recovered for all sufficiently small p ⋆ p_\star p ⋆ : profile by profile, and simultaneously on any finite family of profiles, such as a merged profile and a Sybil profile. The start price is visible only on a profile with a single identity of positive value and budget. That identity receives min { s , q i / p ⋆ } \min\{s,q_i/p_\star\} min { s , q i / p ⋆ } units at the unit price p ⋆ p_\star p ⋆ , which tends to the whole supply at zero payment as p ⋆ ↓ 0 p_\star\downarrow0 p ⋆ ↓ 0 .
Exogenous Online Supply
In the online supply model of [23 Definition 3.1 and Example 3.2] , the supply of the good is revealed over steps t = 0 , 1 , … , m t=0,1,\ldots,m t = 0 , 1 , … , m as a nondecreasing sequence of cumulative supplies
0 = s 0 ≤ s 1 ≤ ⋯ ≤ s m . (84) 0=s_0\leq s_1\leq\cdots\leq s_m. \tag*{(84)} 0 = s 0 ≤ s 1 ≤ ⋯ ≤ s m . (84)
The sequence is exogenous: it may be deterministic, random, or adversarial, but it does not depend on the reports, and at step t t t the auctioneer knows only s 0 , … , s t s_0,\ldots,s_t s 0 , … , s t . The identities, their reports, and their budgets are fixed before the first step. At every step the auctioneer must announce a cumulative allocation and a cumulative payment for each identity, and it may only augment those of the previous step. Online adaptive clinching announces, at step t t t , the outcome ( x ( s t ) , y ( s t ) ) (x(s_t),y(s_t)) ( x ( s t ) , y ( s t )) of the adaptive clinching auction of Section A.1 run to completion with supply s t s_t s t . Between steps t − 1 t-1 t − 1 and t t t it therefore allocates x ( s t ) − x ( s t − 1 ) x(s_t)-x(s_{t-1}) x ( s t ) − x ( s t − 1 ) and charges y ( s t ) − y ( s t − 1 ) y(s_t)-y(s_{t-1}) y ( s t ) − y ( s t − 1 ) .
Let the environment description be the supply revealed so far, and let the target be its last entry:
σ t : = ( s 0 , … , s t ) , T σ t ( p , X , Y ) : = s t , X ‾ σ t : = s t , D σ t : = D s t f i x , \sigma_t:=(s_0,\ldots,s_t),\qquad T_{\sigma_t}(p,X,Y):=s_t,\qquad\overline{X}_{\sigma_t}:=s_t,\qquad D_{\sigma_t}:=D^{\mathrm{fix}}_{s_t}, σ t := ( s 0 , … , s t ) , T σ t ( p , X , Y ) := s t , X σ t := s t , D σ t := D s t fix ,
T t : = ( p ⋆ , σ t , T σ t , D σ t , X ‾ σ t ) . \mathcal{T}_t:=(p_\star,\sigma_t,T_{\sigma_t},D_{\sigma_t},\overline{X}_{\sigma_t}). T t := ( p ⋆ , σ t , T σ t , D σ t , X σ t ) .
Proposition A.5 (Online supply as a family of constant targets). Fix a realized supply path (84) and a step t t t with s t > 0 s_t>0 s t > 0 . Then T t \mathcal{T}_t T t is an admissible abstract target-based mechanism, and the cumulative outcome of online adaptive clinching after step t t t , with every clock started at p ⋆ p_\star p ⋆ , is the outcome of its target-based clinching mechanism. The description σ t \sigma_t σ t is common to all bid profiles. If s t = 0 s_t=0 s t = 0 , no supply has arrived and the cumulative outcome is zero.
Proof. Since T σ t = T s t f i x T_{\sigma_t}=T^{\mathrm{fix}}_{s_t} T σ t = T s t fix , the first two claims are Theorems A.2 and A.3, with Theorem A.4 relating the start price p ⋆ p_\star p ⋆ to a clock started at zero. During the run that settles step t t t , the fixed environment description is σ t \sigma_t σ t : the step index is not the clock. Clock regularity therefore holds with λ σ t = 0 \lambda_{\sigma_t}=0 λ σ t = 0 and no target lump. Finally, σ t \sigma_t σ t is determined by the supply path alone. Because the path is exogenous, every bid profile faces the same σ t \sigma_t σ t , and hence the same target and the same capacity. This is what Theorem 4.2 requires of the capacity, and what § 4.6 requires when it lets the merged run and the Sybil run share the same environment description. □
Remark A.6 (Two time axes). The online step t t t and the clock price p p p are different objects. At step t t t the clock is run afresh from p ⋆ p_\star p ⋆ against the constant target s t s_t s t ; the auction does not pause one ascending clock and resume it when more supply arrives. Accordingly, online adaptive clinching is a family of target-based mechanisms indexed by σ t \sigma_t σ t , one for every prefix of the supply path, and not a single run with a growing target. A statement about one prefix, such as a single-run lemma of § 4.4 or a comparison between two bid profiles that face the same σ t \sigma_t σ t , is a statement about one admissible abstract target-based mechanism. Whether the increments x ( s t ) − x ( s t − 1 ) x(s_t)-x(s_{t-1}) x ( s t ) − x ( s t − 1 ) and y ( s t ) − y ( s t − 1 ) y(s_t)-y(s_{t-1}) y ( s t ) − y ( s t − 1 ) are nonnegative, so that the family can be implemented online, is a different kind of statement: it compares the targets T σ t − 1 T_{\sigma_{t-1}} T σ t − 1 and T σ t T_{\sigma_t} T σ t on one fixed bid profile. This is the supply-monotonicity theorem [23 Theorem 4.1] . It is neither used nor implied by the results of § 4 . On a profile that has at least two identities of positive value and budget and no tied values, and with p ⋆ p_\star p ⋆ below the threshold (83) for the largest supply s m s_m s m , which is the smallest threshold along the path, every run is exactly the auction of [23 ] , and that theorem applies verbatim.
Remark A.7 (A different notion: supply released along the clock). Theorem 4.2 also allows the fixed environment description to contain a schedule indexed by the clock. The simplest example is an exogenous release schedule: a nondecreasing, right-continuous function s : [ p ⋆ , ∞ ) → [ 0 , ∞ ) s:[p_\star,\infty)\to[0,\infty) s : [ p ⋆ , ∞ ) → [ 0 , ∞ ) , not identically zero, whose continuous part is locally absolutely continuous, together with
σ : = s ( ⋅ ) , T σ ( p , X , Y ) : = s ( p ) , X ‾ σ : = sup p s ( p ) , \sigma:=s(\cdot), \qquad T_\sigma(p,X,Y):=s(p), \qquad\overline{X}_\sigma:=\sup_p s(p), σ := s ( ⋅ ) , T σ ( p , X , Y ) := s ( p ) , X σ := p sup s ( p ) ,
D σ : = { ( p , X , Y ) : p ≥ p ⋆ , 0 ≤ X ≤ s ( p ) , Y ≥ 0 } . D_\sigma:=\{(p,X,Y):p\ge p_\star,\ 0\le X\le s(p),\ Y\ge0\}. D σ := {( p , X , Y ) : p ≥ p ⋆ , 0 ≤ X ≤ s ( p ) , Y ≥ 0 } .
The first three requirements hold because the target ignores ( X , Y ) (X,Y) ( X , Y ) , and the domain is closed under raising the clock because s s s is nondecreasing. Clock regularity is the assumption on s s s , with λ σ = s ′ ( p ) \lambda_\sigma=s'(p) λ σ = s ′ ( p ) almost everywhere and with supply lumps at the jumps of s s s . If s ( p ) = X < sup q s ( q ) s(p)=X<\sup_q s(q) s ( p ) = X < sup q s ( q ) , then some p ′ > p p'>p p ′ > p satisfies s ( p ′ ) > X s(p')>X s ( p ′ ) > X , which verifies (28) . Here a single clock is never restarted: supply that arrives at clock price p p p is sold at prices at least p p p , clinchers trade at the rate γ = S + p s ′ ( p ) \gamma=S+ps'(p) γ = S + p s ′ ( p ) of (30) , and the mechanism waits while s ( p ) = X s(p)=X s ( p ) = X . This variant exercises the clauses of Theorem 4.2 that concern clock-dependent environment data, target lumps, and waiting on T σ = X T_\sigma=X T σ = X , none of which is used by the AMM target or by a constant target. It is not the model of [23 ] , in which every prefix is settled by a fresh run, and we mention it only to illustrate the definition.
Incentives for Fixed and Online Supply
The general incentive theorem now applies directly at an attained capacity: capacity saturation begins a zero-trade tail rather than ending the execution with unused budgets. Thus no separate terminal comparison is needed.
Corollary A.8 (Fixed- and online-supply incentives). Let s > 0 s > 0 s > 0 and p ⋆ > 0 p_{\star} > 0 p ⋆ > 0 . In the target-based mechanism for the constant target T s t f i x T_{s_t}^{\mathrm{fix}} T s t fix , truthful participation as the merged identity ( V , Q ) (V,Q) ( V , Q ) , where V ≥ p ⋆ V \ge p_{\star} V ≥ p ⋆ , weakly dominates every same-direction Sybil strategy (43) . Hence, at every step t t t with s t > 0 s_t > 0 s t > 0 of an exogenous online supply path, the truthful merged identity weakly dominates every such strategy in cumulative utility. The same conclusions hold for the classical zero-start auctions, with the simultaneous proportional rule at tied stopping exits.
Proof. The constant-target specification is admissible by Theorem A.2, so the fixed-supply conclusion is an immediate application of Theorem 4.18 . At online step t t t , Theorem A.5 identifies the cumulative outcome with the same mechanism for the constant target T σ t = T s t f i x T_{\sigma_t} = T_{s_t}^{\mathrm{fix}} T σ t = T s t fix . The supply prefix σ t \sigma_t σ t is exogenous and therefore common to the merged and Sybil runs, so the theorem applies pointwise to that prefix.
For the zero-start conclusions, assume V > 0 V > 0 V > 0 and Q > 0 Q > 0 Q > 0 , since otherwise no strategy yields positive utility. If the merged profile and the Sybil profile each contain at least two identities of positive value and budget, choose p ⋆ p_{\star} p ⋆ below V V V and below both thresholds (83) ; on a finite online path it may be chosen below the thresholds for the largest supply, and hence for every prefix. By Theorem A.4, the two positive-start executions equal their zero-start counterparts. In the remaining singleton cases the comparison is immediate: either no outsider has positive value and budget, and the merged identity obtains the whole supply at zero payment, or the Sybil group has no such identity and obtains nothing.