Introduction
MEV, short for Miner (or Maximum) Extractable Value, refers to the widespread phenomenon whereby a block builder leverages its unilateral control over the inclusion and ordering of transactions within a block to extract profit from this privileged position. MEV is harmful in multiple respects. It not only imposes additional costs on ordinary users, but also fosters opaque off-chain markets in which block builders, traders, and specialized searchers compete to identify and exploit MEV opportunities. These off-chain ecosystems, in turn, create strong forces toward centralization. Indeed, a recent measurement study by Yang et al. [YNZ25] found that the top two block builders produce more than 85% of Ethereum blocks, severely undermining the decentralized vision of blockchain systems.
In this work, we focus on Automated Market Makers (AMMs), one of the most widely used applications in decentralized finance (DeFi) and a major source of MEV. Numerous prior works [ZQT+21, Par23, KDC22] have demonstrated how a strategic block builder can exploit its control over transaction inclusion and ordering to launch front-running and back-running attacks, often collectively referred to as sandwich attacks . Through such attacks, the block builder can extract essentially risk-free profits at the expense of ordinary users.
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 .
Our Results and Contributions
Our main contribution is a new two-asset AMM mechanism called Otter (short for “Optimal Truthful Trading with Excess Redistribution”) that achieves provable MEV resilience, assuming that the underlying consensus protocol provides censorship resilience and that block space is uncongested (i.e., there is ample capacity to include all relevant transactions). Specifically, compared with today’s AMMs, our mechanism satisfies several desirable properties:
Provable MEV resilience. We prove that a block builder (henceforth simply a builder ) cannot benefit from any strategic manipulation within its control, including misreporting its true type, manipulating transaction ordering, or creating pseudonymous identities to inject sybil bids. Since we assume that the underlying consensus protocol provides censorship resilience, censoring transactions lies outside the builder’s strategy space. Moreover, this guarantee continues to hold even when the builder is itself a user with an intrinsic demand to trade; we refer to such an entity as a builder-as-user . In particular, the profit-maximizing strategy for a builder or builder-as-user is to truthfully report its type (if it has an intrinsic demand to trade) and refrain from injecting sybil bids. Our mechanism is inherently order-independent : its outcome does not depend on the ordering of transactions within a block. Consequently, the builder gains no advantage from reordering transactions and may order them arbitrarily without affecting the outcome.
2. Truthful reporting and sybil-proofness. We prove that every user’s profit-maximizing strategy is to truthfully report its type, including both its valuation for the asset being purchased and its budget, where both quantities may be denominated in units of the other asset. Furthermore, no user can benefit by creating pseudonymous identities and submitting additional bids through them—a property we refer to as sybil-proofness .
This stands in sharp contrast to today’s AMMs. Under common MEV attacks, most notably sandwich attacks [ZQT+21, Par23, KDC22], users may be forced to trade at the worst possible price permitted by their reported slippage tolerance. Consequently, users face an inherently strategic choice when setting their slippage tolerance: it must be sufficiently permissive for the transaction to execute, yet sufficiently restrictive to limit their exposure to MEV extraction.
Today’s users may also have an incentive to delay submitting their bids, hoping to first observe others’ bids and then choose their own actions strategically. By contrast, the incentive-compatibility guarantees of our mechanism hold ex post : even after observing all other bids, each user, builder, or builder-as-user still maximizes its own profit by behaving truthfully. Thus, observing others’ bids before submitting one’s own confers no strategic advantage, eliminating the incentive for last-minute bid submission.
3. Social welfare optimization. Since truthful behavior constitutes an equilibrium for all participants, including users, builders, and builders-as-users, we show that our AMM maximizes social welfare in a strong sense at equilibrium. By contrast, today’s AMMs generally encourage both users and builders to behave strategically, and their resulting equilibrium behavior is poorly understood. Without a well-characterized equilibrium, it is difficult for a mechanism designer to provide rigorous guarantees about economic objectives such as social welfare.
Last but not least, our new AMM is intuitive, conceptually simple, and computationally efficient, making it a promising candidate for practical implementation and deployment.
Surplus redistribution as a new paradigm. To simultaneously achieve the above desiderata, we introduce a new paradigm called surplus redistribution . Most popular AMMs today [50 ] , as well as a large body of the literature [28 , 20 , 40 ] , impose two requirements: (1) all tokens output by the pool must be completely distributed to the users, and no surplus should remain; and (2) the resulting state of the pool, after each trade or batch of trades, must land on the prescribed pricing curve (e.g., the constant-product curve).
We depart from this conventional model. While we still require the end state of the pool to conform to the pricing curve, we allow only a portion of the tokens output by the pool to be paid to the users. Rather than allowing the remaining surplus to be captured as MEV by privileged participants, our mechanism redistributes it for the benefit of the broader community. For example, the surplus may be transferred to a smart contract governed through a decentralized mechanism and subsequently allocated in various ways that benefit the community, such as:
as additional rewards for liquidity providers, thereby incentivizing greater liquidity provision and, in turn, reducing price impact and slippage for users;
back to the pool itself, thereby deepening liquidity and reducing the cost of future trades;
to subsidize or offset users’ transaction fees; and/or
to the underlying layer-one blockchain or its stakeholders, where it can support the continued development and maintenance of the blockchain, or provide economic incentives that strengthen the security and robustness of the broader ecosystem.
We summarize our main contribution in the following theorem:
Theorem 1 (MEV-resilient AMM mechanism). Suppose that the underlying consensus layer ensures censorship resilience, and that we allow surplus redistribution. Then, there exists an AMM mechanism that incentivizes truthful reporting, achieves strategy-proofness for a block builder who may or may not have intrinsic demand, and maximizes social welfare in a strong sense (to be formally defined later). Further, the mechanism can be computed in O ( n log n ) O(n \log n) O ( n log n ) operations for a batch of n n n orders.
Mitigating the externalities of an already centralized builder economy. We argue that deploying our new AMM alongside, and in direct competition with, legacy AMMs can significantly mitigate the negative externalities arising from today’s highly centralized builder economy, in the following ways:
Eliminating builders’ privileged control over economic surplus. Today, MEV extraction has contributed to a severe centralization of the builder economy, which has effectively become a duopoly [YNZ25]. This concentration allows a small number of dominant builders to capture a disproportionate share of the economic surplus generated through MEV. By contrast, our new AMM prevents this surplus from being captured as MEV and instead redistributes it to the broader decentralized ecosystem.
Pressuring builders to offer competitive pricing. The first three avenues for surplus redistribution described above can all, directly or indirectly, reduce users’ effective trading costs, making our AMM economically competitive with legacy AMMs. Under today’s AMMs, users targeted by MEV attacks effectively suffer from the worst execution price permitted by their reported slippage tolerance. By contrast, in our new AMM, increases in the execution price arise naturally from competition among users, and provably never from MEV extraction.
Deploying our AMM alongside legacy AMMs therefore creates competitive pressure on the existing builder economy. Builders may be compelled to offer users more favorable pricing, effectively returning a greater share of the economic surplus to users and liquidity providers rather than capturing it as MEV.
Necessity of the censorship-resilience assumption. To establish the desirable properties of our AMM, we assume that the underlying consensus layer provides censorship resilience. We argue that this assumption is both necessary and reasonable. We first establish its necessity through the following impossibility result: if block space is finite and the builder has the ability to censor bids, then no non-trivial AMM can simultaneously guarantee truthful reporting for individual users and strategy-proofness for a builder-as-user.
Theorem 2 (Necessity of censorship resilience). Suppose that block space is finite and that the block builder can censor bids. Then, no non-trivial AMM mechanism can simultaneously incentivize truthful reporting by every individual user and be strategy-proof for a builder-as-user.
The censorship-resilience assumption is also well motivated, as numerous blockchain projects are actively pursuing censorship resilience at the consensus layer, most notably Ethereum through FOCIL [27 ] . Beyond FOCIL, a variety of other approaches to achieving censorship resilience have been proposed [31 , 1 ] . More broadly, motivated in part by the urgency of mitigating MEV and its negative externalities, many blockchain projects are exploring enhancements to their consensus protocols that provide stronger guarantees over transaction inclusion and ordering. These efforts include censorship resilience [27 , 31 , 1 ] , fair sequencing [dec, esp, KZGJ20, KDK22, KDL+21, Kur20, ZSC+20], and private transaction submission [Dra, BO22, AFP, FPTX25, BLT25, GWWW26, CGPW25, BFOQ25].
Despite this growing effort at the consensus layer, relatively little is understood about how such guarantees can expand the possibilities for application-layer mechanism design from a game-theoretic perspective. In particular, can stronger consensus-layer guarantees enable fundamentally new mechanism-design feasibility results that would otherwise be impossible?
Our results provide a concrete affirmative answer to this question. Our AMM construction and Theorem 2 jointly establish a separation between consensus layers with and without censorship resilience: the desired incentive guarantees are achievable in the former setting, whereas no non-trivial AMM can achieve them in the latter. Thus, our results mathematically confirm the community’s wide-spread intuition that censorship resilience at the consensus layer can play a fundamental role in mitigating MEV at the application layer.
Additional results. As a by-product of our analysis, we also characterize the permissible forms of builder compensation when a portion of the surplus is allocated to the builder. Specifically, we prove the following:
Theorem 3 (Constraints on surplus returned to the builder). For any AMM mechanism that incentivizes truthful reporting and is strategy-proof for a builder-as-user, the amount of surplus returned to the builder must be constant and independent of the outcome of the AMM.
Interestingly, the proofs of both Theorem 2 and Theorem 3 draw on techniques from the recent literature on transaction fee mechanisms (TFMs) [47 , 19 ] . Our results thus uncover a useful connection between TFM and AMM mechanism design, demonstrating how techniques and insights developed in the study of one can inform the other.
Last but not the least, we also prove that allowing surplus redistribution is essential for obtaining a “dream” AMM mechanism that simultaneously satisfies our desired incentive compatibility and efficiency guarantees.
Theorem 4 (The necessity of surplus redistribution). If we do not allow surplus redistribution, then no deterministic AMM mechanism can simultaneously incentivize truthful reporting and achieve Pareto optimality for orders with “reasonable” asks (to be formally defined later).
Theorem 4 also explains why recent works on AMM mechanism design that do not allow surplus redistribution [20 , 40 ] cannot achieve reasonable notions of social welfare maximization. We stress, however, that we introduce surplus redistribution not merely as a technical device to circumvent the impossibility of Theorem 4, but more importantly, as a desirable paradigm itself to provably defend against MEV and substantially reduce the negative externalities of the already centralized builder economy [YNZ25].
Both Theorem 3 and Theorem 4 hold in a strong sense, even when the underlying consensus offers strong properties including censorship resilience and fair sequencing.
Comparison with Existing Approaches of MEV Mitigation
Capturing MEV through builder auction. A line of work [25 , 23 , 49 ] has explored capturing MEV through auctions for block-building or transaction-ordering rights. Such auction-based approaches have also been deployed by major blockchain ecosystems, including Ethereum’s Proposer-Builder Separation (PBS) framework [45 ] and Arbitrum’s Timeboost [49 ] . Broadly, these approaches allocate privileged block-building or transaction-ordering rights through competitive bidding, allowing some of the associated MEV to be captured by the protocol or returned to the broader community. Unfortunately, such approaches may exacerbate builder centralization by favoring participants with superior access to high-value order flow or other MEV opportunities, thereby disadvantaging smaller builders with fewer resources or customers [YNZ25, BCS24]. As the builder economy becomes increasingly concentrated, diminished competition may in turn allow dominant builders to exercise market power, extract monopoly rents, and retain a larger share of the MEV, ultimately undermining the goal of returning MEV to the broader community.
Application-specific MEV mitigation or recovery at the consensus layer. Several academic works, as well as discussions in the blockchain community, have proposed implementing application-specific MEV mitigation or recovery directly at the consensus layer. For example, Ferreira and Parkes [28 ] propose enforcing application-specific sequencing rules at the consensus layer that restrict how a block builder may order transactions, thereby limiting its ability to extract MEV. In particular, they design sequencing rules for AMM contracts that provide weak but provable guarantees against MEV extraction. Beyond enforcing verifiable sequencing rules, the cryptocurrency communityhave also informally explored the possibility of estimating the amount of MEV extracted by a builder and requiring the builder to return, or pay as a tax, an amount proportional to the estimated MEV to the underlying blockchain.
A fundamental drawback of this general approach is that it pushes application-specific logic into the consensus layer, blurring the architectural boundary between consensus and applications. As the ecosystem grows to support an increasingly diverse collection of applications, incorporating application-specific MEV rules into consensus could substantially increase the complexity of the consensus layer. In the extreme, the consensus layer would need to understand increasingly rich aspects of application semantics in order to determine which builder behaviors are permissible.
Consensus-level MEV recovery faces an additional challenge: it requires the consensus layer to identify and quantify MEV across potentially arbitrary smart contracts. Such an approach may be inherently difficult to sustain in a permissionless environment, where developers can continually deploy new or deliberately obfuscated contracts. Each new application may require the consensus protocol or its maintainers to analyze the contract’s semantics and devise an application-specific method for detecting and quantifying its MEV. This creates an inherently reactive dynamic: as new strategies and contracts emerge, the consensus layer must continually adapt its MEV-detection mechanisms to keep pace.
Our approach instead preserves a clean separation of concerns. We ask the consensus layer to provide only generic, application-agnostic primitives—most importantly, censorship resilience—while leaving application-specific incentive design to the application layer. Our results demonstrate that even such a generic consensus-layer guarantee can be sufficient to enable strong, provable MEV resilience at the application layer.
The approach of Ferreira and Parkes [28 ] also faces additional limitations specific to their model. Their framework requires trades to be executed sequentially, with the pool state satisfying the prescribed pricing curve after every individual trade. Under this restriction, they establish strong impossibility results. In particular, even arbitrage resilience—a guarantee strictly weaker than the incentive-compatibility properties we seek—is impossible in their model. They therefore consider a substantially weaker MEV-resilience notion: roughly speaking, if the builder earns risk-free profit, then each user must receive an execution price at least as favorable as the price it would have received had its order been the only order in the block.
Additional Related Work
Comparison with closely related work. Our work is directly inspired by that of Chan, Wu, and Shi [20 ] , who construct an AMM that processes trades in batches while ensuring that the pool’s end state conforms to the pricing curve. Their AMM achieves the same game-theoretic guarantees as ours, but has two important limitations in comparison. First, their construction relies on a substantially stronger assumption about the consensus layer—namely, fair sequencing. Moreover, the idealized fair-sequencing model assumed in their work is stronger than existing guarantees in the literature [dec, esp, KZGJ20, KDK22, KDL+21, Kur20, ZSC+20], which provide only approximate sequencing fairness. It remains unclear whether their idealized notion of fair sequencing can be realized in practice. Second, unlike our AMM, their mechanism does not achieve optimal social welfare.
Automated market makers. Milionis, Moallemi, and Roughgarden [41 ] study the design of a market maker’s demand curve with the dual objectives of maximizing profit and eliciting truthful reports from traders. Their focus is orthogonal to ours, as their model does not seek to capture or mitigate MEV. In particular, traders submit orders directly to the market maker, and their model does not capture strategic transaction ordering and associated arbitrage opportunities, such as front-running or back-running other traders’ orders. Bartoletti et al. [6 ] study how to determine an adversary’s optimal MEV-extraction strategy in an AMM. In particular, they develop an algorithmic procedure for strategically ordering user transactions and inserting adversarial trades so as to maximize the value extracted from users. Their work seeks to characterize and optimize MEV extraction, rather than to design mechanisms that prevent or mitigate MEV.
A line of work has explored batch trading, particularly batch clearing at a uniform price [12 , 13 , 18 , 46 ] . However, uniform-price batch clearing alone does not guarantee incentive compatibility: when the clearing price depends on orders in the batch, users may benefit from misreporting their valuations or budgets. For example, Canidio and Fritsch [12 , 13 ] propose a uniform-price batch AMM with a modified potential function that achieves arbitrage resilience, but only provides incentive compatibility when there is an infinite number of competing arbitrageurs; with finitely many arbitrageurs, strategic misreporting can be profitable. Other batch-trading mechanisms [15 ] similarly do not satisfy our notion of incentive compatibility. Zhang et al. [ZLS+25] likewise observe this limitation and study optimal strategic behavior under batch clearing. A recent work by Li, Shi, and Zhang [40 ] establishes a somewhat counterintuitive tension between uniform pricing and incentive compatibility. Although uniform pricing eliminates internal arbitrage, they show that it is fundamentally incompatible with the stronger goal of incentive compatibility: in the absence of surplus redistribution, no efficient AMM mechanism can simultaneously achieve uniform pricing and incentive compatibility.
Other related work. Chitra et al. [16 ] propose to redistribute MEV to stake-holders to enhance the blockchain’s economic security; however, their work does not suggest any secure mechanism for capturing the MEV without leading to builder centralization. In this sense, their work is orthogonal to ours. In particular, the surplus accumulated through our Otter mechanism can also be (in part) redistributed to stake-holders as they suggest. Zhang et al. [ZYZ25] propose a mechanism that captures MEV in AMMs and redistributes it to users and liquidity providers. However, their mechanism does not incentivize truthful reporting for users. Moreover, it relies on a stronger assumption about the underlying consensus layer: in addition to censorship resilience, the consensus layer must support private transaction submission [ZYZ25].
Our surplus-redistribution paradigm is closely related to the distinction between strong and weak budget balance in classical mechanism design. Strong budget balance requires that all payments collected from participants be fully redistributed among them, whereas weak budget balance permits a surplus while still ruling out outside subsidies. Under standard bilateral trade assumptions, the Myerson–Satterthwaite theorem shows that it is impossible to simultaneously achieve Bayesian incentive compatibility, individual rationality, and ex post Pareto optimality, even under weak budget balance [42 ] . In our setting, requiring all pool output to be fully distributed to users is a token-wise analog of strong budget balance among the pool and users in the current batch. Surplus redistribution relaxes this requirement, paralleling weak budget balance. We view this relaxation as a fundamental shift in AMM mechanism design: it enables a provably MEV-resilient AMM while making the resulting surplus available for redistribution to the broader blockchain community, with layer-one blockchain and its stakeholders among the possible beneficiaries. This addresses the broader question of how the underlying blockchain benefits from the applications it supports [But25]. Theorem 4 further establishes that this relaxation is necessary for the desired incentive and efficiency guarantees.
Hartline and Roughgarden [HR08] study routing, scheduling, anti-spam, and resource-allocation settings in which conventional monetary transfers are undesirable or technologically unavailable. They design mechanisms that instead require agents to destroy resources — for example, by expending computation or accepting degraded service — and use such resource destruction as an instrument for providing incentives. Although our work shares the high-level idea of burning, it differs fundamentally in both setting and objective. In our mechanism, the burnt surplus is redistributed to the broader community and therefore contributes to social welfare; in their framework, by contrast, burnt resources constitute a social loss. Burning has also been used as a mechanism design tool in the recent transaction fee mechanism literature [47 , 19 ] .
The elegant work of Yokoo et al. [YSM04] considered combinatorial auctions with a finite set of indivisible items. They showed that, under a suitable submodularity condition on the welfare function, the VCG auction is sybil-proof, even though VCG is not sybil-proof in general. While our approach to achieving Sybil-proofness is reminiscent of that of Yokoo et al. [YSM04], we stress that our auction setting differs substantially from theirs, and thus their proof does not directly carry over to our setting. Specifically, in our setting, the tokens being traded are infinitely divisible, trades with the pool are governed by a pricing curve, and agents are subject to budget caps. Moreover, our Sybil strategy space is broader: Sybil identities may not only misreport both valuations and budgets, but may also submit bids in the opposite trading direction.
Our setting resembles multi-unit auctions with budget limits [22 ] , in which buyers compete for a fixed supply of X X X using Y Y Y , subject to hard payment budgets. Such budgets make utility non-quasilinear and preclude a standard VCG treatment, motivating their adaptive clinching auction. At first glance, it may therefore be surprising that VCG works in our setting despite the presence of budget constraints. One might try to reconcile the two by viewing each budget-constrained buyer as a capacitated seller of Y Y Y , but this does not make our procurement-VCG construction applicable to their setting [22 ] : because their supply of X X X is fixed independently of the amount of Y Y Y collected, it corresponds in our formulation to a constant compensation curve F F F . The resulting procurement problem is degenerate—additional input generates no marginal output, so the welfare-maximizing allocation selects no trade. In an AMM, by contrast, additional input generates output along an increasing concave curve, making seller-side VCG both meaningful and feasible.
Model
Imagine a pool that holds two crypto-assets (also called tokens) named X X X and Y Y Y , respectively. Users can trade with the pool through two types of orders, called sell-Y Y Y and sell-X X X orders, respectively.
Sell-Y Y Y orders. A real user i i i of sell-Y Y Y profile has type ( v i , q i ) ∈ R ≥ 0 2 (v_i,q_i) \in\mathbb{R}_{\geq0}^{2} ( v i , q i ) ∈ R ≥ 0 2 , indicating that the user has a budget of q i ≥ 0 q_i \geq0 q i ≥ 0 units of Y Y Y to spend on purchasing X X X , and its reservation value of each unit of Y Y Y is v i ≥ 0 v_i \geq0 v i ≥ 0 , measured in units of X X X . A sell-Y Y Y identity reports a per-unit ask and a declared budget ( v ~ i , q ~ i ) ∈ R ≥ 0 2 (\widetilde{v}_i,\widetilde{q}_i) \in\mathbb{R}_{\geq0}^{2} ( v i , q i ) ∈ R ≥ 0 2 . Truthful reporting means ( v ~ i , q ~ i ) = ( v i , q i ) (\widetilde{v}_i,\widetilde{q}_i)=(v_i,q_i) ( v i , q i ) = ( v i , q i ) .
Sell-X X X orders. Symmetrically, a real user j j j of sell-X X X profile has type ( u j , r j ) ∈ R ≥ 0 2 (u_j,r_j) \in\mathbb{R}_{\geq0}^{2} ( u j , r j ) ∈ R ≥ 0 2 , where r j r_j r j is its budget in units of X X X , and u j u_j u j is its reservation value for one unit of X X X , measured in units of Y Y Y . A sell-X X X identity reports ( u ~ j , r ~ j ) ∈ R ≥ 0 2 (\widetilde{u}_j,\widetilde{r}_j) \in\mathbb{R}_{\geq0}^{2} ( u j , r j ) ∈ R ≥ 0 2 , and truthful reporting means ( u ~ j , r ~ j ) = ( u j , r j ) (\widetilde{u}_j,\widetilde{r}_j)=(u_j,r_j) ( u j , r j ) = ( u j , r j ) .
AMM mechanism. An AMM mechanism receives as input a list of orders, each of either sell-Y Y Y or sell-X X X type, and decides an outcome ( x i , y i ) (x_i,y_i) ( x i , y i ) for each order:
For a sell-Y Y Y order ( v ~ i , q ~ i ) (\widetilde{v}_i,\widetilde{q}_i) ( v i , q i ) , it means that the user obtains x i x_i x i units in X X X in exchange for y i y_i y i units of Y Y Y . It is required that 0 ≤ y i ≤ q ~ i 0 \leq y_i \leq\widetilde{q}_i 0 ≤ y i ≤ q i .
For a sell-X X X order, it means that the user obtains y i y_i y i units in Y Y Y in exchange for x i x_i x i units of X X X . It is required that 0 ≤ x i ≤ r ~ i 0 \leq x_i \leq\widetilde{r}_i 0 ≤ x i ≤ r i .
Unless otherwise noted, we require that an AMM mechanism satisfy the following natural properties:
Individual rationality. Under truthful reporting, every user obtains nonnegative utility.
Feasibility. Every token paid to an order is funded by tokens supplied by opposite-side orders or by an AMM trade. No outside subsidy is required. Any surplus compensation token is burnt (i.e., redistributed the decentralized community).
We assume that the AMM mechanism pays no fee to the builder. § 7 justifies this assumption by showing that our desired incentive guarantees preclude outcome-dependent builder fees. This restriction does not rule out a fixed exogenous payment, funded, for example, by surplus that the mechanism previously redistributed to the community. Provided that this payment is independent of the current batch’s outcome, it has no effect on our game-theoretic analysis.
Strategy Space and Utility
Strategy space. A truthful user always reports its true type. A strategic user, however, can not only misrepresent its valuation and budget, but also create an arbitrary finite number of identities, and inject sybil bids. The declared valuation and budget associated with each sybil identity can be arbitrary finite nonnegative reals. Moreover, the bids submitted by a strategic user need not be in the same direction as its true type. For example, a sell-Y Y Y user may submit sell-X X X bids, and vice versa.
A strategic builder can arbitrarily order the bids in the block, and inject sybil bids. If the strategic builder also has intrinsic demand, then it can also misreport its valuation and budget. Note that the mechanism observes only the declared valuations and budgets, and it is not aware which identities belong to the same real user or builder-as-user.
Utility. Let Y \mathcal{Y} Y and X \mathcal{X} X be the sets of identities that have sell-Y Y Y and sell-X X X profiles, respectively. For the finite set I \mathcal{I} I of identities controlled by one real user, define aggregate token flows
S Y ( I ) : = ∑ i ∈ I ∩ Y y i , R X ( I ) : = ∑ i ∈ I ∩ Y x i , S X ( I ) : = ∑ i ∈ I ∩ X x i , R Y ( I ) : = ∑ i ∈ I ∩ X y i . (1) S_Y(\mathcal{I}) := \sum_{i\in\mathcal{I}\cap\mathcal{Y}} y_i,\quad R_X(\mathcal{I}) := \sum_{i\in\mathcal{I}\cap\mathcal{Y}} x_i,\quad S_X(\mathcal{I}) := \sum_{i\in\mathcal{I}\cap\mathcal{X}} x_i,\quad R_Y(\mathcal{I}) := \sum_{i\in\mathcal{I}\cap\mathcal{X}} y_i. \tag*{(1)} S Y ( I ) := i ∈ I ∩ Y ∑ y i , R X ( I ) := i ∈ I ∩ Y ∑ x i , S X ( I ) := i ∈ I ∩ X ∑ x i , R Y ( I ) := i ∈ I ∩ X ∑ y i . (1)
Here S T S_T S T denotes the amount of token T ∈ { X , Y } T \in\{X,Y\} T ∈ { X , Y } supplied by the user and R T R_T R T denotes the amount of token T T T received by the user. Its net token changes are
Δ X ( I ) : = R X ( I ) − S X ( I ) , Δ Y ( I ) : = R Y ( I ) − S Y ( I ) . \Delta_X(\mathcal{I}) := R_X(\mathcal{I}) - S_X(\mathcal{I}),\quad\Delta_Y(\mathcal{I}) := R_Y(\mathcal{I}) - S_Y(\mathcal{I}). Δ X ( I ) := R X ( I ) − S X ( I ) , Δ Y ( I ) := R Y ( I ) − S Y ( I ) .
A true sell-Y Y Y user of type ( v , q ) (v,q) ( v , q ) has utility
Util Y ( I ; v , q ) : = { − ∞ , if − Δ Y ( I ) > q or ( − Δ Y ( I ) < 0 and Δ X ( I ) < 0 ) Δ X ( I ) + v Δ Y ( I ) , o.w. (2) \operatorname{Util}^{Y}(\mathcal{I};v,q) :=
\begin{cases}
-\infty, & \text{if }-\Delta_Y(\mathcal{I}) > q\text{ or }(-\Delta_Y(\mathcal{I}) < 0\text{ and }\Delta_X(\mathcal{I}) < 0)\\
\Delta_X(\mathcal{I}) + v\Delta_Y(\mathcal{I}), & \text{o.w.}
\end{cases} \tag*{(2)} Util Y ( I ; v , q ) := { − ∞ , Δ X ( I ) + v Δ Y ( I ) , if − Δ Y ( I ) > q or ( − Δ Y ( I ) < 0 and Δ X ( I ) < 0 ) o.w. (2)
Thus a true sell-Y Y Y user receives catastrophic utility if its realized net sale in Y Y Y exceeds the true budget q q q , or if its aggregate trade is strictly in the opposite direction of its desire, namely, if it obtains a strict net gain in Y Y Y while incurring a strict net loss in X X X . Otherwise its utility is computed in the normal quasilinear way from its aggregate net trade. In particular, the utility function does not penalize a sell-Y Y Y user merely for obtaining a net gain in Y Y Y when it does not lose X X X ; this includes a potential free-lunch outcome with weak net gains in both tokens. Nor does it penalize the user if it gross-sells more than q q q units of Y Y Y through some identities provided opposite-direction identities buy back enough Y Y Y that its final net sale does not exceed q q q . This makes the possible strategy larger and will later make our game-theoretic definitions stronger.
Symmetrically, for a true sell-X X X user of type ( u , r ) (u,r) ( u , r ) , its utility is defined as:
Util X ( I ; u , r ) : = { − ∞ , if − Δ X ( I ) > r or ( − Δ X ( I ) < 0 and Δ Y ( I ) < 0 ) Δ Y ( I ) + u Δ X ( I ) , o.w. \operatorname{Util}^{X}(\mathcal{I};u,r) :=
\begin{cases}
-\infty, & \text{if }-\Delta_X(\mathcal{I}) > r\text{ or }(-\Delta_X(\mathcal{I}) < 0\text{ and }\Delta_Y(\mathcal{I}) < 0)\\
\Delta_Y(\mathcal{I}) + u\Delta_X(\mathcal{I}), & \text{o.w.}
\end{cases} Util X ( I ; u , r ) := { − ∞ , Δ Y ( I ) + u Δ X ( I ) , if − Δ X ( I ) > r or ( − Δ X ( I ) < 0 and Δ Y ( I ) < 0 ) o.w.
Thus a true sell-X X X user receives utility − ∞ -\infty − ∞ if it net-sells more than r r r units of X X X , or if it obtains a strict net gain in X X X while incurring a strict net loss in Y Y Y .
A Concave AMM Pricing Curve
Suppose the pool initially holds finite reserves x 0 > 0 x_0 > 0 x 0 > 0 and y 0 > 0 y_0 > 0 y 0 > 0 of tokens X X X and Y Y Y , respectively. Let y ^ \hat{y} y ^ denote the curve’s effective Y Y Y -payout capacity, where 0 < y ^ ≤ y 0 0 < \hat{y} \le y_0 0 < y ^ ≤ y 0 . Trades are governed by a pricing curve
F : ( − y ^ , + ∞ ) ⟶ ( − ∞ , x 0 ) . F : (-\hat{y},+\infty) \longrightarrow(-\infty,x_0). F : ( − y ^ , + ∞ ) ⟶ ( − ∞ , x 0 ) .
A signed amount y ∈ ( − y ^ , + ∞ ) y \in(-\hat{y},+\infty) y ∈ ( − y ^ , + ∞ ) denotes net Y Y Y sent into the AMM, and F ( y ) F(y) F ( y ) denotes net X X X sent out of the AMM. Thus y > 0 y > 0 y > 0 describes selling Y Y Y to the AMM and receiving X X X , while y < 0 y < 0 y < 0 describes withdrawing Y Y Y while depositing X X X . We assume:
(A1) F ( 0 ) = 0 F(0)=0 F ( 0 ) = 0 ;
(A2) F F F is continuous, strictly increasing, and concave;
(A3) F F F is differentiable at 0 0 0 with 0 < F ′ ( 0 ) < ∞ 0 < F'(0) < \infty 0 < F ′ ( 0 ) < ∞ ;
(A4) F F F has the lower-endpoint behavior lim p ↓ − y ^ F ( p ) = − ∞ \lim_{p\downarrow-\hat{y}}F(p)=-\infty lim p ↓ − y ^ F ( p ) = − ∞ .
Define the initial prices
σ 0 : = F ′ ( 0 ) ( X per Y ) , ρ 0 : = 1 F ′ ( 0 ) = 1 σ 0 ( Y per X ) . \sigma_0 := F'(0) \quad(X\ \text{per}\ Y), \qquad\rho_0 := \frac{1}{F'(0)} = \frac{1}{\sigma_0} \quad(Y\ \text{per}\ X). σ 0 := F ′ ( 0 ) ( X per Y ) , ρ 0 := F ′ ( 0 ) 1 = σ 0 1 ( Y per X ) .
For the sell-Y direction, the mechanism uses the restriction of F F F to [ 0 , + ∞ ) [0,+\infty) [ 0 , + ∞ ) . In our mechanism description later, whenever we use F F F as a compensation curve for the sell-Y direction, we are implicitly using F F F restricted to [ 0 , + ∞ ) [0,+\infty) [ 0 , + ∞ ) . The pool pays out F ( y ) ∈ [ 0 , x 0 ) F(y) \in[0,x_0) F ( y ) ∈ [ 0 , x 0 ) units of X X X upon receiving y ≥ 0 y \ge0 y ≥ 0 units of Y Y Y , and the initial marginal compensation is σ 0 \sigma_0 σ 0 . For the sell-X direction, let
H : [ 0 , + ∞ ) ⟶ [ 0 , y ^ ) , H ( x ) : = − F − 1 ( − x ) . H : [0,+\infty) \longrightarrow[0,\hat{y}), \qquad H(x) := -F^{-1}(-x). H : [ 0 , + ∞ ) ⟶ [ 0 , y ^ ) , H ( x ) := − F − 1 ( − x ) .
The pool pays out H ( x ) H(x) H ( x ) units of Y Y Y upon receiving x ≥ 0 x \ge0 x ≥ 0 units of X X X . Its initial marginal compensation is ρ 0 = 1 / σ 0 \rho_0 = 1/\sigma_0 ρ 0 = 1/ σ 0 . Assumptions (A2) and (A4) ensure that F − 1 ( − x ) F^{-1}(-x) F − 1 ( − x ) exists for every x ≥ 0 x \ge0 x ≥ 0 . Since F F F is increasing and concave, H H H is increasing and concave. Thus the mechanism uses F ∣ [ 0 , + ∞ ) F|_{[0,+\infty)} F ∣ [ 0 , + ∞ ) and H H H as its two one-sided compensation curves. Both are increasing and concave and have unbounded nonnegative input domains.
Constant product as a special case. For a constant-product AMM with initial reserves ( x 0 , y 0 ) (x_0,y_0) ( x 0 , y 0 ) and k = x 0 y 0 k = x_0y_0 k = x 0 y 0 , take y ^ = y 0 \hat{y} = y_0 y ^ = y 0 . Then, we have the following:
F ( y ) = x 0 − k y 0 + y , y > − y 0 . F(y) = x_0 - \frac{k}{y_0+y}, \qquad y > -y_0. F ( y ) = x 0 − y 0 + y k , y > − y 0 .
F ′ ( y ) = k ( y 0 + y ) 2 > 0 , F ′ ′ ( y ) = − 2 k ( y 0 + y ) 3 < 0 , σ 0 = x 0 y 0 , ρ 0 = y 0 x 0 . F'(y) = \frac{k}{(y_0+y)^2} > 0, \qquad F''(y) = -\frac{2k}{(y_0+y)^3} < 0, \qquad\sigma_0 = \frac{x_0}{y_0}, \qquad\rho_0 = \frac{y_0}{x_0}. F ′ ( y ) = ( y 0 + y ) 2 k > 0 , F ′′ ( y ) = − ( y 0 + y ) 3 2 k < 0 , σ 0 = y 0 x 0 , ρ 0 = x 0 y 0 .
In other words, the pool pays out x 0 − k y 0 + y x_0 - \frac{k}{y_0+y} x 0 − y 0 + y k units of X X X for receiving y ≥ 0 y \ge0 y ≥ 0 units of Y Y Y , and it pays out − F − 1 ( − x ) = y 0 − k x 0 + x -F^{-1}(-x) = y_0 - \frac{k}{x_0+x} − F − 1 ( − x ) = y 0 − x 0 + x k units of Y Y Y for receiving x ≥ 0 x \ge0 x ≥ 0 units of X X X . Hence constant product is a special case of our generalized concave pricing curve formulation.
Desired Properties
We would like the AMM mechanism to satisfy the following desired properties.
User incentive compatibility (a.k.a. truthfulness). User incentive compatibility (UIC) requires that truthfully reporting both the reservation value and the budget be a dominant strategy over the entire admissible strategy space. In particular, a user cannot benefit from misreporting either its valuation or its budget, nor from creating additional identities and injecting sybil bids.
Strategy proofness for the builder or builder-as-user. For either a builder or a builder-as-user, acting honestly is a dominant strategy. Specifically, the builder or builder-as-user is incentivized to truthfully report its valuation and budget (if there is any intrinsic demand), refrain from injecting any sybil bids, and order the bids in the prescribed manner6 .
Pareto optimality for eligible bids. A bid is considered eligible if its ask is no greater than the initial spot compensation. In other words, a sell-Y Y Y order ( v ~ , q ~ ) (\tilde{v},\tilde{q}) ( v ~ , q ~ ) is eligible iff v ~ ≤ σ 0 \tilde{v} \le\sigma_0 v ~ ≤ σ 0 ; and a sell-X X X order ( u ~ , r ~ ) (\tilde{u},\tilde{r}) ( u ~ , r ~ ) is eligible iff u ~ ≤ ρ 0 \tilde{u} \le\rho_0 u ~ ≤ ρ 0 . We require the following Pareto optimality condition for eligible bids: under truthful reporting,
(a) no subset of users can trade among themselves (subject to available budgets) in a way that achieves a Pareto improvement in their joint utilities; and
(b) no individual user can make an additional trade directly with the pool that strictly improves its utility.
Remark 5 (Our definitions imply sybil-proofness). Since our strategy space allows the user or builder(-as-user) to create sybil identities and inject sybil bids, our user incentive compatibility and strategy proofness for the builder(-as-user) definitions directly imply sybil-proofness against these strategic players. Sybil-proofness is also referred to as false-name-proofness in some prior literature [YSM04, SSIY08, GLT20].
Remark 6 (Why restrict Pareto optimality only to eligible bids). Later in Section A, we prove an impossibility result showing that Pareto optimality cannot be achieved, subject to our incentive-compatibility notions, if non-eligible users are also taken into account. In light of this impossibility, excluding ineligible users from consideration is a natural design choice. Intuitively, the initial spot price can be viewed as setting a baseline price for eligible trades, so that only users whose asks are at least as favorable as this baseline are considered. A similar approach has been adopted in prior work on AMM mechanism design [40 ] .
Remark 7 (Regarding social welfare maximization). In our formulation, the two tokens have no common numeraire, and users may value them at different exchange rates. It is tricky to define a global notion of social welfare since utilities denominated in different tokens cannot be canonically aggregated. To argue that our mechanism achieves a reasonable notion of social welfare maximization, we proceed in two steps.
Here we first define Pareto optimality for eligible users. Any reasonable notion of welfare maximization restricted to eligible users should, at a minimum, preclude a Pareto improvement for those users.
Later in § 6 , we show that our game-theoretic requirements impose strong restrictions on the structure of a mechanism. Given these structural restrictions, we can subsequently introduce a natural welfare criterion for eligible users and prove that our mechanism maximizes it.
Thus, Pareto optimality provides a numeraire-free efficiency requirement at the model level, while welfare maximization is established later within the structure implied by our incentive requirements.
Basic Facts
Relationship between UIC and strategy-proofness for a builder(-as-user). We first prove a couple facts stating the relationship between UIC and strategy-proofness for a builder(-as-user).
Fact 8 (Strategy-proofness for a builder-as-user implies UIC). Strategy-proofness for a builder-as-user implies UIC.
Proof. Fix any user’s true type and all other users’ reports. If the user had a profitable deviation, the same user acting as builder could reproduce both the truthful and deviating executions, including their bid orderings. The mechanism cannot distinguish builder-owned bids, and pays no builder fee, so the user’s utility in each execution would be unchanged. The deviation would therefore also benefit the builder-as-user, contradicting strategy-proofness. □
Fact 9 (Order-insensitive mechanism: UIC ⇔ strategy-proofness for or builder(-as-user)). Suppose that the AMM mechanism treats the input bids as an unordered set. Then, under our strategy space, UIC and strategy proofness for the builder(-as-user) are equivalent.
Proof. Under our strategy space, the only privilege of the builder(-as-user) over an ordinary user is its ability to reorder bids within the block. However, if the mechanism is insensitive to ordering, this ability is useless. Therefore, if the builder(-as-user) with intrinsic type ( v , q ) (v,q) ( v , q ) has a profitable deviation, then so does an ordinary user with the same type. This observation, combined with Theorem 8, gives the conclusion. □
Since our proposed mechanism is order-insensitive, Theorem 9 implies that proving UIC is sufficient for establishing both UIC and strategy-proofness for the builder(-as-user).
Strategy-proofness for a builder(-as-user) implies no arbitrage. Some earlier works [20 , 40 ] on AMM mechanism design also defined an extra property called no free lunch . No free lunch requires that for any subset I \mathcal{I} I of identities, let Δ X : = Δ X ( I ) \Delta_X := \Delta_X(\mathcal{I}) Δ X := Δ X ( I ) and Δ Y : = Δ Y ( I ) \Delta_Y := \Delta_Y(\mathcal{I}) Δ Y := Δ Y ( I ) be their net gain in the tokens X X X and Y Y Y , respectively. Then, it must be that Δ X > 0 ⟹ Δ Y < 0 \Delta_X > 0 \Longrightarrow\Delta_Y < 0 Δ X > 0 ⟹ Δ Y < 0 and Δ Y > 0 ⟹ Δ X < 0 \Delta_Y > 0 \Longrightarrow\Delta_X < 0 Δ Y > 0 ⟹ Δ X < 0 . Intuitively, no free lunch implies that no user or builder(-as-user) can make risk free profit, i.e., the mechanism is arbitrage-free . It also means that for a user or builder with no intrinsic demand and budget, playing honestly without placing any bids is a profit-maximizing strategy.
The following fact shows that strategy-proofness for a builder(-as-user) implies the no free lunch property, even when the mechanism depends on the ordering of bids. A similar observation was made by Chan et al. [20 ] .
Fact 10 (Strategy-proofness for a builder(-as-user) implies no free lunch). Suppose that a deterministic AMM mechanism satisfies strategy-proofness for a builder(-as-user) as defined above. Suppose also that an honest zero-budget builder-as-user of either direction receives zero utility. Then the mechanism satisfies no free lunch for every ordering of the bids.
Proof. Fix any ordered list of bids and any subset I \mathcal{I} I of its identities. Write Δ X : = Δ X ( I ) \Delta_X := \Delta_X(\mathcal{I}) Δ X := Δ X ( I ) and Δ Y : = Δ Y ( I ) \Delta_Y := \Delta_Y(\mathcal{I}) Δ Y := Δ Y ( I ) . Suppose, towards a contradiction, that Δ X > 0 \Delta_X > 0 Δ X > 0 and Δ Y ≥ 0 \Delta_Y \ge0 Δ Y ≥ 0 ; the other direction is symmetric. Interpret I \mathcal{I} I as the sybil identities of a sell-Y Y Y builder-as-user with true type ( v , q ) = ( 0 , 0 ) (v,q) = (0,0) ( v , q ) = ( 0 , 0 ) , and keep all other bids fixed. The builder can submit these sybil bids and reproduce the chosen ordering. Since the mechanism does not observe bid ownership, this reproduces the same outcome. The resulting net sale of Y Y Y is − Δ Y ≤ 0 = q -\Delta_Y \le0 = q − Δ Y ≤ 0 = q , and the builder has a strict net gain in X X X , so neither catastrophic-utility condition applies. Under our no-builder-fee assumption, its utility is therefore Util Y ( I ; 0 , 0 ) = Δ X > 0 \operatorname{Util}^{Y}(\mathcal{I};0,0) = \Delta_X > 0 Util Y ( I ; 0 , 0 ) = Δ X > 0 . Honest behavior gives utility zero by assumption, so this deviation contradicts strategy-proofness for a builder-as-user. □
For our mechanism, the zero-budget normalization in Theorem 10 is automatic: a truthful report with q = 0 q = 0 q = 0 (or r = 0 r = 0 r = 0 ) has zero allocation, and hence zero compensation. Therefore, once the full cross-direction UIC guarantee is established in § 5.3 , order-insensitivity and Theorem 9 give strategy-proofness for the builder(-as-user), and Theorem 10 yields no free lunch as a corollary.
Warmup: A One-Sided VCG Auction
As a warmup, we first present an AMM mechanism assuming that there are only sell-Y Y Y bids and no sell-X X X bids are allowed. For the opposite case, in which there are only sell-X X X bids, a symmetric mechanism can be defined. The one-sided construction applies more generally to any compensation curve
F : [ 0 , + ∞ ) ⟶ R ≥ 0 , F : [0,+\infty) \longrightarrow\mathbb{R}_{\ge0}, F : [ 0 , + ∞ ) ⟶ R ≥ 0 ,
that is continuous, strictly increasing, and concave, with
F ( 0 ) = 0 , σ 0 : = F + ′ ( 0 ) ∈ ( 0 , + ∞ ) . F(0)=0,\qquad\sigma_0:=F'_+(0)\in(0,+\infty). F ( 0 ) = 0 , σ 0 := F + ′ ( 0 ) ∈ ( 0 , + ∞ ) .
The restriction of the signed AMM curve from § 2.2 to [ 0 , + ∞ ) [0,+\infty) [ 0 , + ∞ ) is one such curve. The rest of this section is organized as follows. § 3.1 describes the auction in VCG terms. § 3.3 gives an intuitive and efficient implementation that computes both the allocation and the compensation rules in quasilinear time, and shows that it is equivalent to the VCG view. § 3.2 proves that the auction satisfies the desired properties.
One-Sided Auction: VCG View
A reported sell-Y Y Y user i i i has per-unit ask v ~ i ≥ 0 \tilde{v}_i\ge0 v ~ i ≥ 0 and a budget of q ~ i ≥ 0 \tilde{q}_i\ge0 q ~ i ≥ 0 . Let 0 ≤ y i ≤ q ~ i 0\le y_i\le\tilde{q}_i 0 ≤ y i ≤ q ~ i be the amount of Y Y Y user i i i ends up spending. For a finite set S S S of bids, define the social welfare under the outcome { y i } i ∈ S \{y_i\}_{i\in S} { y i } i ∈ S as
SW F ( S , { y i } i ∈ S ) : = F ( ∑ i ∈ S y i ) − ∑ i ∈ S v ~ i y i . \operatorname{SW}_F(S,\{y_i\}_{i\in S}):=F\left(\sum_{i\in S}y_i\right)-\sum_{i\in S}\tilde{v}_i y_i. SW F ( S , { y i } i ∈ S ) := F ( i ∈ S ∑ y i ) − i ∈ S ∑ v ~ i y i .
Specifically, the social welfare is defined using X X X as a numeraire, and accounts for the total utility of the sell-Y Y Y users, as well as the burnt amount that is effectively redistributed to the community. In the above definition of SW F ( S ) \operatorname{SW}_F(S) SW F ( S ) , the first term is the amount of X X X tokens output by the pool, and the second term can be viewed as a production cost of the Y Y Y tokens sent to the pool.
The maximum achievable social welfare given a finite set S S S of sell-Y Y Y bids is defined as follows:
W F ( S ) : = max 0 ≤ y i ≤ q ~ i ( i ∈ S ) { SW F ( S , { y i } i ∈ S ) } . (3) W_F(S):=\max_{\substack{0\le y_i\le\tilde{q}_i\\(i\in S)}}\left\{\operatorname{SW}_F(S,\{y_i\}_{i\in S})\right\}. \tag*{(3)} W F ( S ) := 0 ≤ y i ≤ q ~ i ( i ∈ S ) max { SW F ( S , { y i } i ∈ S ) } . (3)
We run a VCG-style auction [51 , 17 , 32 ] defined as follows.
Allocation rule. The allocation rule decides how much Y Y Y each user spends. Among welfare maximizers, first choose one maximizing total Y Y Y sold and then apply an arbitrary exogenous tie-breaking rule. Let y i ∗ y_i^* y i ∗ be the resulting allocation chosen for seller i i i , and let Y ∗ = ∑ i y i ∗ Y^*=\sum_i y_i^* Y ∗ = ∑ i y i ∗ .
x i ∗ : = F ( Y ∗ ) − ∑ j ≠ i v ~ j y j ∗ − W F ( S ∖ { i } ) . (4) x_i^*:=F(Y^*)-\sum_{j\ne i}\tilde{v}_j y_j^*-W_F(S\setminus\{i\}). \tag*{(4)} x i ∗ := F ( Y ∗ ) − j = i ∑ v ~ j y j ∗ − W F ( S ∖ { i }) . (4)
Equivalently, let
ϕ i : = W F ( S ) − W F ( S ∖ { i } ) , \phi_i:=W_F(S)-W_F(S\setminus\{i\}), ϕ i := W F ( S ) − W F ( S ∖ { i }) ,
then user i i i 's compensation can be written as
x i ∗ = v ~ i y i ∗ + ϕ i (5) x_i^*=\tilde{v}_i y_i^*+\phi_i \tag*{(5)} x i ∗ = v ~ i y i ∗ + ϕ i (5)
where the first term represents the cost to user i i i for spending y i ∗ y_i^* y i ∗ units of Y Y Y , and the second term represents a rebate to user i i i that is equal to the increase in welfare due to user i i i 's existence.
Efficient implementation. In general, VCG auctions are not necessarily efficient to compute. However, in our case, we show a simple and efficient implementation that takes quasilinear time in Section 3.3.
Proof challenges. In Section 3.2, we prove our one-sided mechanism to satisfy UIC, which implies strategy-proofness for the builder(as-user) due to Theorem 9. Since the mechanism ignores the sequencing of the orders within the batch, it is easy to see that sequencing strategies do not help. Using standard VCG arguments, we show that misreporting value or budget also does not help. However, standard VCG arguments do not directly imply that injecting fake bids is not profitable. To show this, our key idea is to prove that the welfare function is submodular, and use the properties of submodularity to make the argument. Submodularity has also been used to establish Sybil-proofness of VCG in combinatorial auctions [YSM04, AM06]. Those analyses concern a fixed supply of indivisible goods, whereas our mechanism procures divisible tokens through a concave AMM curve, subject to privately reported budget caps. Their results therefore do not apply directly.
Proofs for the One-Sided Auction
We now state and prove the guarantees of the one-sided VCG auction. By Theorem 14 , they apply verbatim to its efficient implementation in Theorem 13.
Theorem 11 (One-sided VCG auction). Let F : [ 0 , + ∞ ) → R ≥ 0 F : [0,+\infty) \to\mathbb{R}_{\ge0} F : [ 0 , + ∞ ) → R ≥ 0 be a compensation curve satisfying the one-sided curve conditions stated at the beginning of this section. Suppose that only sell-Y bids are allowed. Then, the one-sided VCG auction of § 3.1 satisfies the following properties:
(a) Well-formedness: every user’s allocation and compensation are within the desired ranges:
0 ≤ y i ∗ ≤ q ~ i and 0 ≤ x i ∗ ≤ F ( Y ∗ ) − F ( Y ∗ − y i ∗ ) ≤ σ 0 y i ∗ ; (6) 0 \le y_i^* \le\tilde{q}_i \quad\text{and} \quad0 \le x_i^* \le F(Y^*) - F(Y^* - y_i^*) \le\sigma_0 y_i^*; \tag*{(6)} 0 ≤ y i ∗ ≤ q ~ i and 0 ≤ x i ∗ ≤ F ( Y ∗ ) − F ( Y ∗ − y i ∗ ) ≤ σ 0 y i ∗ ; (6) (b) Individual rationality: every user’s truthful utility is nonnegative;
(c) Feasibility: aggregate VCG compensation is covered by the concave output:
∑ i x i ∗ ≤ F ( Y ∗ ) ; (7) \sum_i x_i^* \le F(Y^*); \tag*{(7)} i ∑ x i ∗ ≤ F ( Y ∗ ) ; (7) (d) Submodularity of welfare: the set function W F W_F W F is normalized, monotone, and submodular;
(e) UIC: the mechanism satisfies user incentive compatibility (UIC).
Proof. The allocation bounds in part (a) follow directly from the feasible region in (3) . Under truthful reporting,
Util i = x i ∗ − v i y i ∗ = W F ( S ) − W F ( S ∖ { i } ) ≥ 0 , \operatorname{Util}_i = x_i^* - v_i y_i^* = W_F(S) - W_F(S \setminus\{i\}) \ge0, Util i = x i ∗ − v i y i ∗ = W F ( S ) − W F ( S ∖ { i }) ≥ 0 ,
because adding an optional user cannot reduce the optimum. This proves (b) and also shows ϕ i ≥ 0 \phi_i \ge0 ϕ i ≥ 0 in (5) . To obtain the upper bound, delete user i i i but retain every other user’s selected allocation. This is feasible for S ∖ { i } S \setminus\{i\} S ∖ { i } , so
W F ( S ∖ { i } ) ≥ F ( Y ∗ − y i ∗ ) − ∑ j ≠ i v ~ j y j ∗ . W_F(S \setminus\{i\}) \ge F(Y^* - y_i^*) - \sum_{j \ne i} \tilde{v}_j y_j^*. W F ( S ∖ { i }) ≥ F ( Y ∗ − y i ∗ ) − j = i ∑ v ~ j y j ∗ .
Substitution into (4) yields
x i ∗ ≤ F ( Y ∗ ) − F ( Y ∗ − y i ∗ ) . x_i^* \le F(Y^*) - F(Y^* - y_i^*). x i ∗ ≤ F ( Y ∗ ) − F ( Y ∗ − y i ∗ ) .
Because a concave function has nonincreasing marginal slope and initial right slope σ 0 \sigma_0 σ 0 ,
F ( Y ∗ ) − F ( Y ∗ − y i ∗ ) ≤ σ 0 y i ∗ . F(Y^*) - F(Y^* - y_i^*) \le\sigma_0 y_i^*. F ( Y ∗ ) − F ( Y ∗ − y i ∗ ) ≤ σ 0 y i ∗ .
Nonnegativity follows from (5) . Together with the allocation bound proved above, this completes the proof of (a).
Summing the above upper bound on x i ∗ x_i^* x i ∗ gives
∑ i x i ∗ ≤ ∑ i ( F ( Y ∗ ) − F ( Y ∗ − y i ∗ ) ) . \sum_i x_i^* \le\sum_i \left(F(Y^*) - F(Y^* - y_i^*)\right). i ∑ x i ∗ ≤ i ∑ ( F ( Y ∗ ) − F ( Y ∗ − y i ∗ ) ) .
If Y ∗ = 0 Y^* = 0 Y ∗ = 0 , the claim is immediate since it must be the case that for every i i i , y i ∗ = 0 y_i^* = 0 y i ∗ = 0 and x i ∗ ≤ F ( Y ∗ ) − F ( Y ∗ − y i ∗ ) = 0 x_i^* \le F(Y^*) - F(Y^* - y_i^*) = 0 x i ∗ ≤ F ( Y ∗ ) − F ( Y ∗ − y i ∗ ) = 0 . Otherwise concavity and F ( 0 ) = 0 F(0) = 0 F ( 0 ) = 0 imply
F ( Y ∗ − y i ∗ ) ≥ ( 1 − y i ∗ Y ∗ ) F ( Y ∗ ) . F(Y^* - y_i^*) \ge\left(1 - \frac{y_i^*}{Y^*}\right)F(Y^*). F ( Y ∗ − y i ∗ ) ≥ ( 1 − Y ∗ y i ∗ ) F ( Y ∗ ) .
Therefore
F ( Y ∗ ) − F ( Y ∗ − y i ∗ ) ≤ y i ∗ Y ∗ F ( Y ∗ ) . F(Y^*) - F(Y^* - y_i^*) \le\frac{y_i^*}{Y^*}F(Y^*). F ( Y ∗ ) − F ( Y ∗ − y i ∗ ) ≤ Y ∗ y i ∗ F ( Y ∗ ) .
Summing over i i i proves (7) , and hence (c).
We next prove submodularity. For t ∈ [ 0 , σ 0 ] t \in[0,\sigma_0] t ∈ [ 0 , σ 0 ] , let
D S ( t ) : = ∑ i ∈ S q ~ i 1 { v ~ i ≤ t } D_S(t) := \sum_{i\in S} \tilde q_i 1\{\tilde v_i \le t\} D S ( t ) := i ∈ S ∑ q ~ i 1 { v ~ i ≤ t }
be aggregate capacity of Y Y Y whose ask is at most t t t , and let
K F ( t ) : = sup { y ≥ 0 : F + ′ ( y ) ≥ t } , K_F(t) := \sup\{y \ge0 : F_+'(y) \ge t\}, K F ( t ) := sup { y ≥ 0 : F + ′ ( y ) ≥ t } ,
where the supremum is allowed to be + ∞ +\infty + ∞ . Let α S ( y ) \alpha_S(y) α S ( y ) be the inverse aggregate supply curve: the minimum reported per-unit cost of the y y y th infinitesimal unit of the capacity. For a fixed total input Y Y Y , the minimum reported cost is
∫ 0 Y α S ( y ) d y , \int_0^Y \alpha_S(y)\,dy, ∫ 0 Y α S ( y ) d y ,
while concavity gives
F ( Y ) = ∫ 0 Y F + ′ ( y ) d y . F(Y) = \int_0^Y F_+'(y)\,dy. F ( Y ) = ∫ 0 Y F + ′ ( y ) d y .
Since F + ′ F_+' F + ′ is nonincreasing and α S \alpha_S α S is nondecreasing, their difference is nonincreasing. Maximizing over Y Y Y therefore integrates exactly the region where marginal compensation is at least marginal cost. A layer-cake/Fubini argument gives
W F ( S ) = ∫ 0 σ 0 min { D S ( t ) , K F ( t ) } d t . (8) W_F(S) = \int_0^{\sigma_0} \min\{D_S(t),K_F(t)\}\,dt. \tag*{(8)} W F ( S ) = ∫ 0 σ 0 min { D S ( t ) , K F ( t )} d t . (8)
For every fixed t t t , the map
S ↦ min { ∑ i ∈ S q ~ i 1 { v ~ i ≤ t } , K F ( t ) } S \mapsto\min\left\{\sum_{i\in S} \tilde q_i 1\{\tilde v_i \le t\},K_F(t)\right\} S ↦ min { i ∈ S ∑ q ~ i 1 { v ~ i ≤ t } , K F ( t ) }
is a capped modular set function and is therefore monotone and submodular. Integration preserves these properties, and W F ( ∅ ) = 0 W_F(\varnothing)=0 W F ( ∅ ) = 0 . This proves (d).
Finally, we prove UIC. Fix all reports not controlled by one real user, and denote their set by O O O . Let the user, whose true cost is v y v y v y on [ 0 , q ] [0,q] [ 0 , q ] , submit an arbitrary finite collection I \mathcal{I} I of admissible reports — a singleton collection is an ordinary joint misreport of value and cap. Let y i , x i y_i,x_i y i , x i be the selected sale and compensation of report i ∈ I i\in\mathcal{I} i ∈ I , and let
Y I : = ∑ i ∈ I y i . Y_{\mathcal{I}} := \sum_{i\in\mathcal{I}} y_i. Y I := i ∈ I ∑ y i .
The reports may have budget caps whose sum exceeds q q q . If Y I > q Y_{\mathcal{I}}>q Y I > q , the real user’s utility is − ∞ -\infty − ∞ , so the deviation is immediately unprofitable. It therefore remains only to analyze the case Y I ≤ q Y_{\mathcal{I}}\le q Y I ≤ q . Put
ϕ i : = W F ( O ∪ I ) − W F ( O ∪ ( I ∖ { i } ) ) . \phi_i := W_F(O\cup\mathcal{I})-W_F(O\cup(\mathcal{I}\setminus\{i\})). ϕ i := W F ( O ∪ I ) − W F ( O ∪ ( I ∖ { i })) .
By (5) ,
x i = v ~ i y i + ϕ i . x_i=\tilde{v}_i y_i+\phi_i. x i = v ~ i y i + ϕ i .
Submodularity implies
∑ i ∈ I ϕ i ≤ W F ( O ∪ I ) − W F ( O ) . \sum_{i\in\mathcal{I}}\phi_i\le W_F(O\cup\mathcal{I})-W_F(O). i ∈ I ∑ ϕ i ≤ W F ( O ∪ I ) − W F ( O ) .
Hence the real user’s utility from the possibly sybil deviation is
Util S y b = ∑ i ∈ I x i − v Y I ≤ ∑ i ∈ I v ~ i y i + W F ( O ∪ I ) − W F ( O ) − v Y I . \begin{aligned}
\operatorname{Util}^{\mathrm{Syb}}=\sum_{i\in\mathcal{I}}x_i-vY_{\mathcal{I}} \\
&\le\sum_{i\in\mathcal{I}}\tilde{v}_i y_i+W_F(O\cup\mathcal{I})-W_F(O)-vY_{\mathcal{I}}.
\end{aligned} Util Syb = i ∈ I ∑ x i − v Y I ≤ i ∈ I ∑ v ~ i y i + W F ( O ∪ I ) − W F ( O ) − v Y I .
At the chosen allocation for O ∪ I O\cup\mathcal{I} O ∪ I , the reported costs of the sybil identities I \mathcal{I} I cancel with the same terms inside W F ( O ∪ I ) W_F(O\cup\mathcal{I}) W F ( O ∪ I ) . Thus
Util S y b ≤ F ( Y I + ∑ j ∈ O y j ) − ∑ j ∈ O v ~ j y j − v Y I − W F ( O ) . \operatorname{Util}^{\mathrm{Syb}}\le F\left(Y_{\mathcal{I}}+\sum_{j\in O}y_j\right)-\sum_{j\in O}\tilde{v}_j y_j-vY_{\mathcal{I}}-W_F(O). Util Syb ≤ F Y I + j ∈ O ∑ y j − j ∈ O ∑ v ~ j y j − v Y I − W F ( O ) .
Because Y I ≤ q Y_{\mathcal{I}}\le q Y I ≤ q , the first three terms are the welfare of a feasible allocation after merging I \mathcal{I} I into a truthful user of type ( v , q ) (v,q) ( v , q ) that sells Y I ≤ q Y_{\mathcal{I}}\le q Y I ≤ q . Therefore
Util S y b ≤ W F ( O ∪ { ( v , q ) } ) − W F ( O ) , \operatorname{Util}^{\mathrm{Syb}}\le W_F(O\cup\{(v,q)\})-W_F(O), Util Syb ≤ W F ( O ∪ {( v , q )}) − W F ( O ) ,
which is exactly the utility from reporting ( v , q ) (v,q) ( v , q ) truthfully as a single identity. Hence no deviation is profitable. This proves UIC, including ordinary joint misreports and sybil bids, and establishes (e).
Efficient Implementation
We now describe how to implement our VCG auction efficiently in quasilinear time. We shall focus on the one-sided mechanism of § 3 below. Since our full two-sided mechanism in § 4 calls the one-sided VCG auction as a building block, if the one-sided version can be computed in quasilinear time, so can the two-sided mechanism.
Specifically, the VCG view defines the allocation and compensation rules through optimization problems: the allocation solves (3) , and the compensation (4) of every user i i i additionally requires the counterfactual optimum W F ( S ∖ { i } ) W_F(S\setminus\{i\}) W F ( S ∖ { i }) . We now give a simple algorithm that computes the allocation and all compensations in quasilinear time, and we prove that its outcome coincides exactly with that of the VCG view. Throughout, let n : = ∣ S ∣ n:=|S| n := ∣ S ∣ .
Intuition: computing the allocation. Imagine selling Y Y Y to the pool one infinitesimal unit at a time. When y y y units have been sold so far, the next unit d Y dY d Y fetches d X = F + ′ ( y ) d Y dX=F'_+(y)\,dY d X = F + ′ ( y ) d Y units of X X X from the pool; since F F F is concave, this marginal rate d X d Y \frac{dX}{dY} d Y d X can only decrease as more Y Y Y is sold. The cheapest way to supply the next unit is to take it from a user with the smallest ask among those with remaining budget, and selling the unit increases welfare as long as the current marginal rate is at least this ask. Hence a welfare-maximizing allocation fills the users’ budgets in nondecreasing order of ask, and stops as soon as the marginal rate drops below the ask of the user currently being filled; that user may thus sell only part of its budget, and all subsequent users sell nothing.
Geometrically, index the users in nondecreasing order of ask, and draw a staircase whose k k k th step has height v ~ k \tilde{v}_k v ~ k and width q ~ k \tilde{q}_k q ~ k , so that the step spans the quantities [ Q k − 1 , Q k ] [Q_{k-1},Q_k] [ Q k − 1 , Q k ] , where Q k Q_k Q k is the total budget of the first k k k users. Draw also the nonincreasing marginal-rate curve y ↦ F + ′ ( y ) y\mapsto F'_+(y) y ↦ F + ′ ( y ) , as in Figure 1 (a). The auction sells Y Y Y up to the point Y ∗ Y^* Y ∗ at which the curve drops below the staircase. The area under the curve to the left of Y ∗ Y^* Y ∗ is F ( Y ∗ ) F(Y^*) F ( Y ∗ ) , the amount of X X X output by the pool, and the area under the staircase to the left of Y ∗ Y^* Y ∗ is the total reported cost of the units sold; hence W F ( S ) W_F(S) W F ( S ) is the area between the curve and the staircase to the left of Y ∗ Y^* Y ∗ . For the k k k th step, the only relevant information about the curve is a single number: the crossing point τ k \tau_k τ k at which the marginal rate drops below the step’s height v ~ k \tilde{v}_k v ~ k , marked by a dot in the figure. The k k k th step is used in full if and only if it ends no later than its crossing point, i.e., Q k ≤ τ k Q_k\leq\tau_k Q k ≤ τ k . As k k k increases, the step ends Q k Q_k Q k move to the right, whereas the crossing points τ k \tau_k τ k move to the left, since the nonincreasing curve drops below a higher step earlier. Hence the auction stops at the first step k k k that ends beyond its crossing point, which can be found by binary search, and the total quantity sold is max { Q k − 1 , τ k } \max\{Q_{k-1},\tau_k\} max { Q k − 1 , τ k } (if there is no such step, all budgets are exhausted). In Figure 1 (a), the auction stops at step 3: users 1 and 2 exhaust their budgets, user 3 sells τ 3 − Q 2 \tau_3-Q_2 τ 3 − Q 2 units, and users 4 and 5 sell nothing. We stress that this process determines only how much each user sells: the compensation of a user is not the amount of X X X fetched by its own units, but its Clarke pivot compensation (4) .
Figure 1. The staircase picture of the one-sided auction with five users, indexed in nondecreasing order of ask. The horizontal axis is the quantity of Y Y Y sold, and the vertical axis is measured in units of X X X per unit of Y Y Y . The k k k th step has height v ~ k \tilde{v}_k v ~ k and width q ~ k \tilde{q}_k q ~ k , and the dot labeled τ k \tau_k τ k marks its crossing point, i.e., the point at which the marginal-rate curve F + ′ F'_+ F + ′ drops to the step’s height. (a) Steps 1 and 2 end before their crossing points, whereas steps 3, 4, and 5 end after theirs (dotted lines). Hence the auction stops at step 3 and sells Y ∗ = τ 3 Y^*=\tau_3 Y ∗ = τ 3 units in total. The gray area is the total reported cost ∑ j v ~ j y j ∗ \sum_j \tilde{v}_j y_j^* ∑ j v ~ j y j ∗ , and the blue area is the optimal welfare W F ( S ) W_F(S) W F ( S ) ; together, they form the area F ( Y ∗ ) F(Y^*) F ( Y ∗ ) under the curve. (b) Removing user 2 deletes its step, and the later steps slide to the left by q ~ 2 \tilde{q}_2 q ~ 2 (dashed: the original staircase), whereas the curve and the crossing points do not change. The auction now stops at step 4 and sells τ 4 \tau_4 τ 4 units in total. The blue area is W F ( S ∖ { 2 } ) W_F(S\setminus\{2\}) W F ( S ∖ { 2 }) , and the hatched area between the two staircases is the welfare gain ϕ 2 = W F ( S ) − W F ( S ∖ { 2 } ) \phi_2=W_F(S)-W_F(S\setminus\{2\}) ϕ 2 = W F ( S ) − W F ( S ∖ { 2 }) .
Intuition: computing the compensations. The compensation of user i i i depends on W F ( S ∖ { i } ) W_F(S \setminus\{i\}) W F ( S ∖ { i }) , the optimal welfare of the same auction without user i i i . Solving each of these n n n counterfactual problems from scratch would take quadratic time overall. The key observation is that removing user i i i changes the staircase in a very structured way: the i i i th step disappears and every later step slides to the left by exactly q ~ i \tilde{q}_i q ~ i , whereas the heights of all remaining steps, and hence their crossing points, remain unchanged; see Figure 1 (b), where i = 2 i = 2 i = 2 . Consequently, the crossing points can be computed once and reused in every counterfactual problem. Moreover, every step end of a counterfactual staircase is obtained in constant time from the original one, by subtracting q ~ i \tilde{q}_i q ~ i if the step is at or after position i i i , and similarly for the accumulated costs. Each counterfactual problem is then solved by a single binary search for its stopping step, followed by a single evaluation of F F F . In Figure 1 (b), for instance, step 3 now ends before its crossing point, so the search stops at step 4 instead, and only τ 4 \tau_4 τ 4 units are sold. Computing the allocation itself is the special case in which no user is removed. The figure also illustrates the welfare gain ϕ i = W F ( S ) − W F ( S ∖ { i } ) \phi_i = W_F(S) - W_F(S \setminus\{i\}) ϕ i = W F ( S ) − W F ( S ∖ { i }) : since the staircase without user i i i lies on or above the original one, ϕ i \phi_i ϕ i is the area below the curve and between the two staircases, and the compensation (5) of user i i i adds its reported cost v ~ i y i ∗ \tilde{v}_i y_i^* v ~ i y i ∗ to this area.
Tie-breaking rule. For concreteness, we instantiate the exogenous tie-breaking rule of § 3.1 by a fixed priority order over the identities: among the welfare maximizers that maximize the total Y Y Y sold, the rule selects the one in which a user sells a positive amount only if every higher-priority user with the same ask has exhausted its budget. The proof of Theorem 14 below shows that exactly one such welfare maximizer exists. Other tie-breaking rules are discussed in Theorem 16.
Computational model. We count arithmetic operations and comparisons on real numbers at unit cost, and we access the curve F F F through two primitives: evaluating F F F at a given point, and computing a crossing point
τ F ( v , b ) : = max ( arg max 0 ≤ y ≤ b { F ( y ) − v y } ) , v ≥ 0 , b ≥ 0 , \tau_F(v,b) := \max\left(\underset{0 \le y \le b}{\operatorname{arg\,max}}\left\{F(y) - vy\right\}\right), \qquad v \ge0,\ b \ge0, τ F ( v , b ) := max ( 0 ≤ y ≤ b arg max { F ( y ) − v y } ) , v ≥ 0 , b ≥ 0 ,
i.e., the largest maximizer of F ( y ) − v y F(y) - vy F ( y ) − v y over y ∈ [ 0 , b ] y \in[0,b] y ∈ [ 0 , b ] , which exists since F F F is continuous. Because F ( y ) − v y F(y) - vy F ( y ) − v y is concave in y y y , it is nondecreasing on [ 0 , τ F ( v , b ) ] [0,\tau_F(v,b)] [ 0 , τ F ( v , b )] and strictly decreasing on [ τ F ( v , b ) , b ] [\tau_F(v,b),b] [ τ F ( v , b ) , b ] .7 Intuitively, τ F ( v , b ) \tau_F(v,b) τ F ( v , b ) is the point, clipped to [ 0 , b ] [0,b] [ 0 , b ] , at which the marginal compensation of F F F drops below v v v . If F F F is differentiable and strictly concave, τ F ( v , b ) \tau_F(v,b) τ F ( v , b ) is simply the point at which F ′ F' F ′ crosses v v v , clipped to [ 0 , b ] [0,b] [ 0 , b ] ; the definition also covers curves with kinks or linear pieces. For example, for the constant-product curve of § 2.2 , τ F ( 0 , b ) = b \tau_F(0,b) = b τ F ( 0 , b ) = b and
τ F ( v , b ) = min { b , max { 0 , x 0 y 0 / v − y 0 } } for v > 0 , \tau_F(v,b) = \min\left\{b,\ \max\left\{0,\ \sqrt{x_0 y_0 / v} - y_0\right\}\right\} \qquad\text{for } v > 0, τ F ( v , b ) = min { b , max { 0 , x 0 y 0 / v − y 0 } } for v > 0 ,
so both primitives take a constant number of arithmetic operations and square roots.
Preprocessing. Sort the users in S S S in nondecreasing order of ask, breaking ties by priority, and index them as 1 , 2 , … , n 1,2,\ldots,n 1 , 2 , … , n in this order, so that v ~ 1 ≤ v ~ 2 ≤ ⋯ ≤ v ~ n \widetilde{v}_1 \le\widetilde{v}_2 \le\cdots\le\widetilde{v}_n v 1 ≤ v 2 ≤ ⋯ ≤ v n . For k = 0 , 1 , … , n k=0,1,\ldots,n k = 0 , 1 , … , n , define the prefix sums
Q k : = ∑ j = 1 k q ~ j , C k : = ∑ j = 1 k v ~ j q ~ j . (9) Q_k := \sum_{j=1}^{k}\widetilde{q}_j,\qquad C_k := \sum_{j=1}^{k}\widetilde{v}_j\widetilde{q}_j. \tag*{(9)} Q k := j = 1 ∑ k q j , C k := j = 1 ∑ k v j q j . (9)
Thus Q k Q_k Q k is the total budget of the first k k k users, C k C_k C k is the total reported cost of exhausting these budgets, Q 0 = C 0 = 0 Q_0=C_0=0 Q 0 = C 0 = 0 , and Q n Q_n Q n is the total budget of all users. For k = 1 , … , n k=1,\ldots,n k = 1 , … , n , define the crossing points
τ k : = τ F ( v ~ k , Q n ) . (10) \tau_k := \tau_F(\widetilde{v}_k,Q_n). \tag*{(10)} τ k := τ F ( v k , Q n ) . (10)
Each τ k \tau_k τ k depends only on the curve, on the ask v ~ k \widetilde{v}_k v k , and on the total budget Q n Q_n Q n , which is an upper bound on the total quantity sold in the actual profile as well as in every counterfactual profile considered below. Hence the crossing points are computed only once.
Lemma 12 (Monotone crossing points). For every b ≥ 0 b \ge0 b ≥ 0 , the crossing point τ F ( v , b ) \tau_F(v,b) τ F ( v , b ) is nonincreasing in v v v . In particular, τ 1 ≥ τ 2 ≥ ⋯ ≥ τ n \tau_1 \ge\tau_2 \ge\cdots\ge\tau_n τ 1 ≥ τ 2 ≥ ⋯ ≥ τ n .
Proof. Let 0 ≤ v < v ′ 0 \le v < v' 0 ≤ v < v ′ , and write s : = τ F ( v , b ) s := \tau_F(v,b) s := τ F ( v , b ) and s ′ : = τ F ( v ′ , b ) s' := \tau_F(v',b) s ′ := τ F ( v ′ , b ) . By the optimality of s s s and s ′ s' s ′ ,
F ( s ) − v s ≥ F ( s ′ ) − v s ′ , F ( s ′ ) − v ′ s ′ ≥ F ( s ) − v ′ s . F(s)-vs \ge F(s')-vs',\qquad F(s')-v's' \ge F(s)-v's. F ( s ) − v s ≥ F ( s ′ ) − v s ′ , F ( s ′ ) − v ′ s ′ ≥ F ( s ) − v ′ s .
Adding these two inequalities gives ( v ′ − v ) ( s − s ′ ) ≥ 0 (v'-v)(s-s') \ge0 ( v ′ − v ) ( s − s ′ ) ≥ 0 , and hence s ≥ s ′ s \ge s' s ≥ s ′ .
Counterfactual welfare query. Once the preprocessing is done, a subroutine called Query ( i ) \operatorname{Query}(i) Query ( i ) outputs a pair given an index i ∈ { 0 , 1 , … , n } i \in\{0,1,\ldots,n\} i ∈ { 0 , 1 , … , n } :
W ( − i ) W^{(-i)} W ( − i ) : the optimal welfare of the profile S ∖ { i } S \setminus\{i\} S ∖ { i } , in which user i i i is removed; and
Y ( − i ) Y^{(-i)} Y ( − i ) : the largest welfare-maximizing total quantity of that profile.
We use i = 0 i=0 i = 0 as a dummy index that removes nobody; for this index, we adopt the conventions v ~ 0 = q ~ 0 : = 0 \widetilde{v}_0=\widetilde{q}_0:=0 v 0 = q 0 := 0 and S ∖ { 0 } : = S S\setminus\{0\}:=S S ∖ { 0 } := S . Removing user i i i is equivalent to setting its budget to zero while keeping its position in the sorted order. Accordingly, the prefix sums of the profile S ∖ { i } S\setminus\{i\} S ∖ { i } are
Q k ( − i ) : = Q k − q ~ i ⋅ 1 { k ≥ i } , C k ( − i ) : = C k − v ~ i q ~ i ⋅ 1 { k ≥ i } , k = 0 , 1 , … , n , (11) Q_k^{(-i)} := Q_k-\widetilde{q}_i\cdot1\{k\ge i\},\qquad C_k^{(-i)} := C_k-\widetilde{v}_i\widetilde{q}_i\cdot1\{k\ge i\},\qquad k=0,1,\ldots,n, \tag*{(11)} Q k ( − i ) := Q k − q i ⋅ 1 { k ≥ i } , C k ( − i ) := C k − v i q i ⋅ 1 { k ≥ i } , k = 0 , 1 , … , n , (11)
each of which takes constant time to compute from (9) ; in particular, no new arrays are needed. The query finds, by binary search, the smallest index k ∈ { 1 , … , n } k\in\{1,\ldots,n\} k ∈ { 1 , … , n } such that
Q k ( − i ) > τ k . (12) Q_k^{(-i)}>\tau_k. \tag*{(12)} Q k ( − i ) > τ k . (12)
Binary search applies because this test is monotone in k k k : Q k ( − i ) Q_k^{(-i)} Q k ( − i ) is nondecreasing in k k k , whereas τ k \tau_k τ k is nonincreasing in k k k by Theorem 12; hence once (12) holds for some k k k , it holds for all larger indices. Finally, Query ( i ) \operatorname{Query}(i) Query ( i ) returns the pair ( Y ( − i ) , W ( − i ) ) (Y^{(-i)},W^{(-i)}) ( Y ( − i ) , W ( − i ) ) defined as follows.
Y ( − i ) : = Q n ( − i ) , W ( − i ) : = F ( Y ( − i ) ) − C n ( − i ) . (13) Y^{(-i)}:=Q_n^{(-i)},\qquad W^{(-i)}:=F\left(Y^{(-i)}\right)-C_n^{(-i)}. \tag*{(13)} Y ( − i ) := Q n ( − i ) , W ( − i ) := F ( Y ( − i ) ) − C n ( − i ) . (13)
Otherwise, let k k k be the smallest such index. The users before position k k k exhaust their budgets, user k k k sells until the total reaches its crossing point (possibly selling nothing), and the users after position k k k sell nothing:
Y ( − i ) : = max { Q k − 1 ( − i ) , τ k } , W ( − i ) : = F ( Y ( − i ) ) − C k − 1 ( − i ) − v ~ k ( Y ( − i ) − Q k − 1 ( − i ) ) . (14) Y^{(-i)}:=\max\left\{Q_{k-1}^{(-i)},\tau_k\right\},\qquad W^{(-i)}:=F\left(Y^{(-i)}\right)-C_{k-1}^{(-i)}-\widetilde{v}_k\left(Y^{(-i)}-Q_{k-1}^{(-i)}\right). \tag*{(14)} Y ( − i ) := max { Q k − 1 ( − i ) , τ k } , W ( − i ) := F ( Y ( − i ) ) − C k − 1 ( − i ) − v k ( Y ( − i ) − Q k − 1 ( − i ) ) . (14)
The query uses O ( log n ) O(\log n) O ( log n ) arithmetic operations and comparisons and a single evaluation of F F F ; in particular, it requires no new crossing-point computation.
The algorithm. Putting these pieces together, we obtain the following algorithm. The allocation is obtained from Query(0), i.e., from the full profile, by filling the budgets in the sorted order up to the selected total quantity, and the compensations are obtained from Query(1), …, Query(n).
Algorithm 13 (Efficient one-sided VCG auction). Given the bids { ( v ~ i , q ~ i ) } i ∈ S \{(\tilde v_i,\tilde q_i)\}_{i\in S} {( v ~ i , q ~ i ) } i ∈ S and the priority order:
Sort: sort the users by nondecreasing ask, breaking ties by priority, and index them as 1 , … , n 1,\ldots,n 1 , … , n in this order.
Preprocess: compute the prefix sums Q k Q_k Q k and C k C_k C k for k = 0 , … , n k=0,\ldots,n k = 0 , … , n as in (9) , and the crossing points τ k \tau_k τ k for k = 1 , … , n k=1,\ldots,n k = 1 , … , n as in (10) .
Allocation: compute ( Y ( − 0 ) , W ( − 0 ) ) : = Query ( 0 ) (Y^{(-0)},W^{(-0)}):=\operatorname{Query}(0) ( Y ( − 0 ) , W ( − 0 ) ) := Query ( 0 ) , which removes nobody. Let Y a l g : = Y ( − 0 ) Y^{\mathrm{alg}}:=Y^{(-0)} Y alg := Y ( − 0 ) and, for every j = 1 , … , n j=1,\ldots,n j = 1 , … , n , let
y j a l g : = min { q ~ j , max { 0 , Y a l g − Q j − 1 } } . y_j^{\mathrm{alg}}:=\min\{\tilde q_j,\max\{0,Y^{\mathrm{alg}}-Q_{j-1}\}\}. y j alg := min { q ~ j , max { 0 , Y alg − Q j − 1 }} . Compensations: for every i = 1 , … , n i=1,\ldots,n i = 1 , … , n , compute ( Y ( − i ) , W ( − i ) ) : = Query ( i ) (Y^{(-i)},W^{(-i)}):=\operatorname{Query}(i) ( Y ( − i ) , W ( − i ) ) := Query ( i ) , and let
x i a l g : = v ~ i y i a l g + W ( − 0 ) − W ( − i ) . x_i^{\mathrm{alg}}:=\tilde v_i y_i^{\mathrm{alg}}+W^{(-0)}-W^{(-i)}. x i alg := v ~ i y i alg + W ( − 0 ) − W ( − i ) . Output: return ( y i a l g , x i a l g ) (y_i^{\mathrm{alg}},x_i^{\mathrm{alg}}) ( y i alg , x i alg ) for every user i i i , under its original identity.
Equivalence with the VCG view. We now show that Theorem 13 computes exactly the outcome of the VCG view, within the claimed time bound.
Theorem 14 (Equivalence of the efficient implementation and the VCG view). Let F F F satisfy the one-sided curve conditions, and let S S S be a finite set of n n n sell-Y Y Y bids. Then Theorem 13 outputs exactly the outcome of the one-sided VCG auction of § 3.1 under the priority tie-breaking rule, i.e., y i a l g = y i ∗ y_i^{\mathrm{alg}}=y_i^* y i alg = y i ∗ and x i a l g = x i ∗ x_i^{\mathrm{alg}}=x_i^* x i alg = x i ∗ for every user i ∈ S i\in S i ∈ S . Moreover, the algorithm uses O ( n log n ) O(n\log n) O ( n log n ) arithmetic operations and comparisons, O ( n ) O(n) O ( n ) evaluations of F F F , O ( n ) O(n) O ( n ) crossing-point computations, and O ( n ) O(n) O ( n ) space.
The core of the proof is the following lemma, which shows that each query solves its counterfactual problem exactly.
Lemma 15 (Correctness of the query). For every i ∈ { 0 , 1 , … , n } i\in\{0,1,\ldots,n\} i ∈ { 0 , 1 , … , n } , Query ( i ) \operatorname{Query}(i) Query ( i ) returns W ( − i ) = W F ( S ∖ { i } ) W^{(-i)}=W_F(S\setminus\{i\}) W ( − i ) = W F ( S ∖ { i }) . Moreover, Y ( − i ) Y^{(-i)} Y ( − i ) is the largest total quantity ∑ j y j \sum_j y_j ∑ j y j among all optimal solutions { y j } \{y_j\} { y j } of (3) for the profile S ∖ { i } S\setminus\{i\} S ∖ { i } .
Proof. Fix i i i , and let T : = S ∖ { i } T:=S\setminus\{i\} T := S ∖ { i } . Since removing user i i i is equivalent to setting its budget to zero, we view T T T as the sorted users 1 , … , n 1,\ldots,n 1 , … , n with budgets q ~ j ( − i ) : = q ~ j \tilde q_j^{(-i)}:=\tilde q_j q ~ j ( − i ) := q ~ j for j ≠ i j\ne i j = i and q ~ i ( − i ) : = 0 \tilde q_i^{(-i)}:=0 q ~ i ( − i ) := 0 , so that Q k ( − i ) = ∑ j ≤ k q ~ j ( − i ) Q_k^{(-i)}=\sum_{j\le k}\tilde q_j^{(-i)} Q k ( − i ) = ∑ j ≤ k q ~ j ( − i ) and C k ( − i ) = ∑ j ≤ k v ~ j q ~ j ( − i ) C_k^{(-i)}=\sum_{j\le k}\tilde v_j\tilde q_j^{(-i)} C k ( − i ) = ∑ j ≤ k v ~ j q ~ j ( − i ) .
Minimum-cost supply. For 0 ≤ y ≤ Q n ( − i ) 0\le y\le Q_n^{(-i)} 0 ≤ y ≤ Q n ( − i ) , let
C ( y ) : = min { ∑ j = 1 n v ~ j y j : 0 ≤ y j ≤ q ~ j ( − i ) ( 1 ≤ j ≤ n ) , ∑ j = 1 n y j = y } . C(y):=\min\left\{\sum_{j=1}^{n}\tilde v_j y_j: 0\le y_j\le\tilde q_j^{(-i)}\ (1\le j\le n),\ \sum_{j=1}^{n}y_j=y\right\}. C ( y ) := min { j = 1 ∑ n v ~ j y j : 0 ≤ y j ≤ q ~ j ( − i ) ( 1 ≤ j ≤ n ) , j = 1 ∑ n y j = y } .
be the minimum reported cost of supplying y y y units of Y Y Y . An exchange argument shows that C ( y ) C(y) C ( y ) is attained by filling the budgets in the sorted order: if a user sells a positive amount while an earlier user has unused budget, then shifting a small amount of sale from the former to the latter does not increase the cost, since the latter’s ask is no larger. Consequently, for every j ∈ { 1 , … , n } j \in\{1,\ldots,n\} j ∈ { 1 , … , n } ,
C ( y ) = C j − 1 ( − i ) + v ~ j ( y − Q j − 1 ( − i ) ) C(y) = C_{j-1}^{(-i)} + \widetilde{v}_j\left(y-Q_{j-1}^{(-i)}\right) C ( y ) = C j − 1 ( − i ) + v j ( y − Q j − 1 ( − i ) )
whenever Q j − 1 ( − i ) ≤ y ≤ Q j ( − i ) Q_{j-1}^{(-i)} \le y \le Q_j^{(-i)} Q j − 1 ( − i ) ≤ y ≤ Q j ( − i ) , (15)
which holds trivially if this j j j th interval has zero length (e.g., if j = i j=i j = i ). That is, C C C is continuous and piecewise linear, with slope v ~ j \widetilde{v}_j v j on the j j j th interval [ Q j − 1 ( − i ) , Q j ( − i ) ] [Q_{j-1}^{(-i)},Q_j^{(-i)}] [ Q j − 1 ( − i ) , Q j ( − i ) ] .
Reduction to one dimension. A feasible allocation for T T T with total y y y has welfare at most Ψ ( y ) : = F ( y ) − C ( y ) \Psi(y):=F(y)-C(y) Ψ ( y ) := F ( y ) − C ( y ) , with equality if and only if its reported cost equals C ( y ) C(y) C ( y ) . Hence
W F ( T ) = max 0 ≤ y ≤ Q n ( − i ) Ψ ( y ) . W_F(T)=\max_{0\le y\le Q_n^{(-i)}}\Psi(y). W F ( T ) = 0 ≤ y ≤ Q n ( − i ) max Ψ ( y ) .
and the totals of the optimal solutions of (3) for T T T are exactly the maximizers of Ψ \Psi Ψ . It therefore suffices to show that Y ( − i ) Y^{(-i)} Y ( − i ) is the largest maximizer of Ψ \Psi Ψ , and that W ( − i ) = Ψ ( Y ( − i ) ) W^{(-i)}=\Psi(Y^{(-i)}) W ( − i ) = Ψ ( Y ( − i ) ) .
By (15), on the j j j th interval, Ψ \Psi Ψ coincides with the concave function y ↦ F ( y ) − v ~ j y y\mapsto F(y)-\widetilde{v}_jy y ↦ F ( y ) − v j y up to an additive constant. Recall that τ j \tau_j τ j is the largest maximizer of this function over [ 0 , Q n ] ⊇ [ 0 , Q n ( − i ) ] [0,Q_n]\supseteq[0,Q_n^{(-i)}] [ 0 , Q n ] ⊇ [ 0 , Q n ( − i ) ] ; hence the function is nondecreasing on [ 0 , τ j ] [0,\tau_j] [ 0 , τ j ] and strictly decreasing on [ τ j , Q n ] [\tau_j,Q_n] [ τ j , Q n ] .
Case 1: no index satisfies (12) . Then Q j ( − i ) ≤ τ j Q_j^{(-i)}\le\tau_j Q j ( − i ) ≤ τ j for every j j j , so the j j j th interval lies within [ 0 , τ j ] [0,\tau_j] [ 0 , τ j ] , and Ψ \Psi Ψ is nondecreasing on it. Thus Ψ \Psi Ψ is nondecreasing on its entire domain [ 0 , Q n ( − i ) ] [0,Q_n^{(-i)}] [ 0 , Q n ( − i ) ] . Its largest maximizer is therefore Q n ( − i ) = Y ( − i ) Q_n^{(-i)}=Y^{(-i)} Q n ( − i ) = Y ( − i ) , and (15) gives Ψ ( Q n ( − i ) ) = F ( Q n ( − i ) ) − C n ( − i ) = W ( − i ) \Psi(Q_n^{(-i)})=F(Q_n^{(-i)})-C_n^{(-i)}=W^{(-i)} Ψ ( Q n ( − i ) ) = F ( Q n ( − i ) ) − C n ( − i ) = W ( − i ) .
Case 2: k k k is the smallest index satisfying (12) . Write L : = Q k − 1 ( − i ) L:=Q_{k-1}^{(-i)} L := Q k − 1 ( − i ) and z : = Y ( − i ) = max { L , τ k } z:=Y^{(-i)}=\max\{L,\tau_k\} z := Y ( − i ) = max { L , τ k } . Since L ≤ Q k ( − i ) L\le Q_k^{(-i)} L ≤ Q k ( − i ) and τ k < Q k ( − i ) \tau_k<Q_k^{(-i)} τ k < Q k ( − i ) , the point z z z lies in the k k k th interval [ L , Q k ( − i ) ] [L,Q_k^{(-i)}] [ L , Q k ( − i ) ] , so (15) gives Ψ ( z ) = W ( − i ) \Psi(z)=W^{(-i)} Ψ ( z ) = W ( − i ) as defined in (14) . It remains to show that z z z is the largest maximizer of Ψ \Psi Ψ .
No point to the left of z z z is better. By the minimality of k k k , every j < k j<k j < k satisfies Q j ( − i ) ≤ τ j Q_j^{(-i)}\le\tau_j Q j ( − i ) ≤ τ j , so Ψ \Psi Ψ is nondecreasing on [ 0 , L ] [0,L] [ 0 , L ] , as in Case 1. If z > L z>L z > L , then z = τ k z=\tau_k z = τ k , and [ L , z ] [L,z] [ L , z ] lies within both the k k k th interval and [ 0 , τ k ] [0,\tau_k] [ 0 , τ k ] , so Ψ \Psi Ψ is nondecreasing on [ L , z ] [L,z] [ L , z ] as well. Hence Ψ ( y ) ≤ Ψ ( z ) \Psi(y)\le\Psi(z) Ψ ( y ) ≤ Ψ ( z ) for all y ∈ [ 0 , z ] y\in[0,z] y ∈ [ 0 , z ] .
Every point to the right of z z z is strictly worse. Let z < y ≤ Q n ( − i ) z<y\le Q_n^{(-i)} z < y ≤ Q n ( − i ) . Since z ≥ L z\ge L z ≥ L , the interval [ z , y ] [z,y] [ z , y ] is covered by the intervals j ≥ k j\ge k j ≥ k , on which the slope of C C C is v ~ j ≥ v ~ k \widetilde{v}_j\ge\widetilde{v}_k v j ≥ v k . Hence C ( y ) − C ( z ) ≥ v ~ k ( y − z ) C(y)-C(z)\ge\widetilde{v}_k(y-z) C ( y ) − C ( z ) ≥ v k ( y − z ) , and
Ψ ( y ) − Ψ ( z ) ≤ ( F ( y ) − v ~ k y ) − ( F ( z ) − v ~ k z ) < 0 , \Psi(y)-\Psi(z)\le\bigl(F(y)-\widetilde{v}_ky\bigr)-\bigl(F(z)-\widetilde{v}_kz\bigr)<0, Ψ ( y ) − Ψ ( z ) ≤ ( F ( y ) − v k y ) − ( F ( z ) − v k z ) < 0 ,
where the strict inequality holds because τ k ≤ z < y ≤ Q n \tau_k\le z<y\le Q_n τ k ≤ z < y ≤ Q n and F ( y ) − v ~ k y F(y)-\widetilde{v}_ky F ( y ) − v k y is strictly decreasing on [ τ k , Q n ] [\tau_k,Q_n] [ τ k , Q n ] .
Therefore z = Y ( − i ) z=Y^{(-i)} z = Y ( − i ) is the largest maximizer of Ψ \Psi Ψ , which completes the proof. □ \square □
Proof of Theorem 15. We first show that the allocation is correct. By Theorem 15 with i = 0 i=0 i = 0 , Y a l g Y^{\mathrm{alg}} Y alg is the largest total quantity among all welfare maximizers for S S S , i.e., Y a l g = Y ∗ Y^{\mathrm{alg}}=Y^* Y alg = Y ∗ is exactly the total selected by the quantity-maximizing rule. As shown in the proof of Theorem 15, the welfare maximizers with total Y ∗ Y^* Y ∗ are exactly the feasible allocations with total Y ∗ Y^* Y ∗ whose reported cost is minimum. Let { y j } \{y_j\} { y j } be such an allocation that also obeys the priority rule, and suppose that some user j ′ j' j ′ sells a positive amount while some user j < j ′ j<j' j < j ′ , i.e., a user earlier in the sorted order, has unused budget. If v ~ j < v ~ j ′ \widetilde{v}_j<\widetilde{v}_{j'} v j < v j ′ , then shifting a small amount of sale from j ′ j' j ′ to j j j strictly lowers the reported cost, contradicting cost minimality; if v ~ j = v ~ j ′ \widetilde{v}_j=\widetilde{v}_{j'} v j = v j ′ , then j j j has a higher priority than j ′ j' j ′ , contradicting the priority rule. Hence the allocation fills the budgets in the sorted order, and since its total is Y ∗ Y^* Y ∗ , it must be y j = min { q ~ j , max { 0 , Y ∗ − Q j − 1 } } = y j a l g y_j = \min\{\widetilde{q}_j, \max\{0, Y^* - Q_{j-1}\}\} = y_j^{\mathrm{alg}} y j = min { q j , max { 0 , Y ∗ − Q j − 1 }} = y j alg for every j j j . Conversely, { y j a l g } \{y_j^{\mathrm{alg}}\} { y j alg } has total Y ∗ Y^* Y ∗ , has minimum reported cost by the exchange argument in the proof of Theorem 15, and obeys the priority rule. Therefore it is exactly the allocation selected by the VCG view, i.e., y j a l g = y j ∗ y_j^{\mathrm{alg}} = y_j^* y j alg = y j ∗ for every j j j .
Next, by Theorem 15, W ( − 0 ) = W F ( S ) W^{(-0)} = W_F(S) W ( − 0 ) = W F ( S ) and W ( − i ) = W F ( S ∖ { i } ) W^{(-i)} = W_F(S \setminus\{i\}) W ( − i ) = W F ( S ∖ { i }) for every i ∈ S i \in S i ∈ S . Hence, by (5) ,
x i a l g = v ~ i y i ∗ + W F ( S ) − W F ( S ∖ { i } ) = v ~ i y i ∗ + ϕ i = x i ∗ . x_i^{\mathrm{alg}} = \widetilde{v}_i y_i^* + W_F(S) - W_F(S \setminus\{i\}) = \widetilde{v}_i y_i^* + \phi_i = x_i^*. x i alg = v i y i ∗ + W F ( S ) − W F ( S ∖ { i }) = v i y i ∗ + ϕ i = x i ∗ .
Finally, we bound the cost. Step 1 uses O ( n log n ) O(n \log n) O ( n log n ) comparisons. Step 2 uses O ( n ) O(n) O ( n ) arithmetic operations and n n n crossing-point computations. Steps 3 and 4 make n + 1 n + 1 n + 1 calls to Query, each using O ( log n ) O(\log n) O ( log n ) arithmetic operations and comparisons and one evaluation of F F F , plus O ( n ) O(n) O ( n ) further arithmetic operations. Step 5 takes O ( n ) O(n) O ( n ) operations. The algorithm stores O ( n ) O(n) O ( n ) numbers, namely the sorted bids, the prefix sums, and the crossing points, and the queries can be run one at a time with O ( 1 ) O(1) O ( 1 ) additional space. □
Remark 16 (Other tie-breaking rules). The queries compute the welfare values W F ( S ) W_F(S) W F ( S ) and W F ( S ∖ { i } ) W_F(S \setminus\{i\}) W F ( S ∖ { i }) , which do not depend on how ties are broken. By the exchange argument in the proof of Theorem 14 , any other exogenous tie-breaking rule can only change how users with one and the same ask split their joint sale. Given the resulting allocation, the compensations are still obtained from (5) with O ( n ) O(n) O ( n ) additional arithmetic operations.
The Full Two-Sided Mechanism
We now describe our full Otter mechanism, which extends the one-sided mechanism in § 3 .
Intuition and additional proof challenges. The full mechanism first discards all ineligible bids whose asks are less favorable than the initial price. Among the remaining eligible bids, it then computes the spot-eligible supply on both sides at the initial spot price. Henceforth, let D Y D_Y D Y and D X D_X D X denote the quantities of Y Y Y and X X X , respectively, available to be sold at the initial spot price or better. Without loss of generality, if D Y ≥ ρ 0 D X D_Y \ge\rho_0 D_X D Y ≥ ρ 0 D X , we say that the sell-Y Y Y side is dominant ; the other case is symmetric. The mechanism then fully executes all eligible sell-X X X orders at the initial spot price. On the sell-Y Y Y side, we run the one-sided VCG auction of § 3 using an adjusted curve F ~ Y M ( y ) \widetilde{F}_Y^M(y) F Y M ( y ) , obtained by extending F ( y ) F(y) F ( y ) so that the first M : = ρ 0 D X M := \rho_0 D_X M := ρ 0 D X units of Y Y Y sold enjoy the initial spot price. Equivalently, we can view the pool as being augmented with D X D_X D X units of X X X at the initial spot price.
Our two-sided mechanism raises a new proof challenge: strategic players can now report bids in the opposite direction of their true type, and such a bid can replace their true bid under their original identity, or be injected as fake bids under fake names. Our two-sided proofs in § 5 introduce new techniques to prove that injecting opposite-direction bids does not help. Specifically, the more interesting case is when the user’s true direction is dominant in the deviating outcome; here, opposite-direction bids can change the very curve used to compute the user’s VCG payments. The effects are two-fold: the opposite-direction trades incur a net utility cost, but extending the favorable initial spot-price segment can benefit the user. We introduce a key technical lemma, the curve-shift lemma (Theorem 20), which, together with the one-sided Sybil bound, shows that the extra benefit cannot exceed this net utility cost, even when buying tokens back allows the user’s gross sales to exceed its true budget.
Detailed description. A sell-Y Y Y report is willing to sell at the initial spot price exactly when v ~ i ≤ σ 0 \tilde{v}_i \le\sigma_0 v ~ i ≤ σ 0 . Define total spot-eligible sell-Y Y Y quantity, in units of Y Y Y , by
D Y : = ∑ i ∈ Y q ~ i 1 { v ~ i ≤ σ 0 } . D_Y := \sum_{i\in Y} \tilde{q}_i 1\{\tilde{v}_i \le\sigma_0\}. D Y := i ∈ Y ∑ q ~ i 1 { v ~ i ≤ σ 0 } .
Similarly, define total spot-eligible sell-X X X quantity, in units of X X X , by
D X : = ∑ j ∈ X r ~ j 1 { u ~ j ≤ ρ 0 } . D_X := \sum_{j\in X} \tilde{r}_j 1\{\tilde{u}_j \le\rho_0\}. D X := j ∈ X ∑ r ~ j 1 { u ~ j ≤ ρ 0 } .
At the spot price, D X D_X D X units of X X X require ρ 0 D X \rho_0D_X ρ 0 D X units of Y Y Y as compensation. We call a profile sell-Y Y Y dominated if
D Y ≥ ρ 0 D X , (15) D_Y \ge\rho_0D_X, \tag*{(15)} D Y ≥ ρ 0 D X , (15)
and sell-X X X dominated otherwise. Ties are resolved in favor of the sell-Y Y Y direction.
Sell-Y Y Y dominated profiles. Suppose (15) holds and define
M : = ρ 0 D X . M := \rho_0D_X. M := ρ 0 D X .
Thus M M M is the number of units of Y Y Y needed to buy all spot-eligible sell-X X X supply at the initial price. First, fully execute every sell-X X X order with u ~ j ≤ ρ 0 \tilde{u}_j \le\rho_0 u ~ j ≤ ρ 0 at the initial spot price:
x j = r ~ j , y j = ρ 0 r ~ j . (16) x_j = \tilde{r}_j,\qquad y_j = \rho_0\tilde{r}_j. \tag*{(16)} x j = r ~ j , y j = ρ 0 r ~ j . (16)
Every sell-X X X identity with u ~ j > ρ 0 \tilde{u}_j > \rho_0 u ~ j > ρ 0 is assigned zero allocation and zero compensation. These minority-side trades supply D X D_X D X units of X X X and require exactly M M M units of Y Y Y as compensation. The dominant sell-Y Y Y side faces the following effective compensation curve, measured in units of X X X available as a function of units of Y Y Y sold:
F ~ Y M ( y ) : = { σ 0 y , 0 ≤ y ≤ M , D X + F ( y − M ) , y ≥ M . (17) \widetilde{F}^{M}_{Y}(y) :=
\begin{cases}
\sigma_0 y, & 0 \le y \le M,\\
D_X + F(y-M), & y \ge M.
\end{cases} \tag*{(17)} F Y M ( y ) := { σ 0 y , D X + F ( y − M ) , 0 ≤ y ≤ M , y ≥ M . (17)
Because D X = σ 0 M D_X = \sigma_0M D X = σ 0 M and F + ′ ( 0 ) = σ 0 F'_+(0) = \sigma_0 F + ′ ( 0 ) = σ 0 , the two pieces meet continuously with the same initial marginal slope. Since F F F is concave, F ~ Y M \widetilde{F}^{M}_{Y} F Y M is increasing and concave, and therefore satisfies the one-sided curve conditions.
Run the one-sided VCG mechanism of § 3 on all sell-Y Y Y reports with compensation curve F ~ Y M \widetilde{F}^{M}_{Y} F Y M . The interpretation of (17) is intuitive: the first M = ρ 0 D X M = \rho_0D_X M = ρ 0 D X units of dominant-side Y Y Y can be compensated using the D X D_X D X units of X X X supplied by the sell-X X X orders at the initial spot price. If more than M M M units of Y Y Y are sold, only the excess Y Y Y is sent to the AMM and the original curve F F F is used thereafter.
Fact 17. Let Q Y Q_Y Q Y be the aggregate Y Y Y spent by the sell-Y Y Y users. Then, Q Y ≥ M Q_Y \ge M Q Y ≥ M .
Proof. By definition, the total reported budget of sell-Y Y Y identities with ask at most σ 0 \sigma_0 σ 0 is at least M M M . On [ 0 , M ] [0,M] [ 0 , M ] , the marginal compensation of F ~ Y M \widetilde{F}^{M}_{Y} F Y M is exactly σ 0 \sigma_0 σ 0 . If a welfare maximizer sold a total Q Y < M Q_Y < M Q Y < M , some unsold spot-eligible capacity would remain. Increasing a seller with ask strictly below σ 0 \sigma_0 σ 0 would strictly increase welfare; increasing one with ask exactly σ 0 \sigma_0 σ 0 would preserve welfare while increasing total sold quantity. Either alternative contradicts optimality together with our quantity-maximizing tie rule. Hence Q Y ≥ M Q_Y \ge M Q Y ≥ M .
Since F ~ Y M \widetilde{F}^{M}_{Y} F Y M satisfies the one-sided curve conditions, Theorem 13 computes the one-sided VCG auction on this curve exactly, by Theorem 14 . The algorithm accesses the curve only through evaluations and crossing points, and by (17) , each of these takes at most one call to the corresponding primitive of F F F plus O ( 1 ) O(1) O ( 1 ) arithmetic operations. For instance, τ ~ F Y M ( v , b ) \widetilde{\tau}^{M}_{FY}(v,b) τ F Y M ( v , b ) equals 0 0 0 if v > σ 0 v>\sigma_0 v > σ 0 , equals b b b if v ≤ σ 0 v\leq\sigma_0 v ≤ σ 0 and b ≤ M b\leq M b ≤ M , and equals M + τ F ( v , b − M ) M+\tau_F(v,b-M) M + τ F ( v , b − M ) otherwise. Moreover, by definition, the curve stays fixed when the auction computes the counterfactual welfare values that determine the compensations, so the crossing points are still computed only once. The remaining steps — computing D Y D_Y D Y and D X D_X D X , determining the dominant side, settling the minority side, and computing the burnt amount — take O ( n ) O(n) O ( n ) operations and one more evaluation of F F F . Hence the full mechanism can be computed within the bounds of Theorem 14 , where n n n now denotes the total number of reports; for the constant-product curve of § 2.2 , this amounts to O ( n log n ) O(n\log n) O ( n log n ) operations. The sell-X X X dominated case below is symmetric, with H H H in place of F F F .
Sell-X X X dominated profiles. The sell-X X X dominated case is handled symmetrically. We describe the full details below for completeness. Suppose D Y < ρ 0 D X D_Y<\rho_0D_X D Y < ρ 0 D X . Define the amount of X X X needed to buy all spot-eligible sell-Y Y Y supply at the initial spot price:
M : = σ 0 D Y = D Y ρ 0 . M:=\sigma_0D_Y=\frac{D_Y}{\rho_0}. M := σ 0 D Y = ρ 0 D Y .
First, fully execute every sell-Y Y Y order with v ~ i ≤ σ 0 \widetilde{v}_i\leq\sigma_0 v i ≤ σ 0 at the initial spot price:
y i = q ~ i , x i = σ 0 q ~ i . y_i=\widetilde{q}_i,\qquad x_i=\sigma_0\widetilde{q}_i. y i = q i , x i = σ 0 q i .
Every sell-Y Y Y identity with v ~ i > σ 0 \widetilde{v}_i>\sigma_0 v i > σ 0 is assigned zero allocation and zero compensation. These minority-side trades supply D Y D_Y D Y units of Y Y Y and require exactly M M M units of X X X as compensation. The dominant sell-X X X side faces the effective compensation curve, now in units of Y Y Y available as a function of units of X X X sold,
H ~ X M ( x ) : = { ρ 0 x , 0 ≤ x ≤ M , D Y + H ( x − M ) , x ≥ M . \widetilde{H}^{M}_{X}(x):=
\begin{cases}
\rho_0x, & 0\leq x\leq M,\\
D_Y+H(x-M), & x\geq M.
\end{cases} H X M ( x ) := { ρ 0 x , D Y + H ( x − M ) , 0 ≤ x ≤ M , x ≥ M .
Because D Y = ρ 0 M D_Y=\rho_0M D Y = ρ 0 M and H + ′ ( 0 ) = ρ 0 H'_+(0)=\rho_0 H + ′ ( 0 ) = ρ 0 , this is increasing and concave. It therefore satisfies the one-sided curve conditions. Run the one-sided VCG mechanism of § 3 on all sell-X X X reports using H ~ X M \widetilde{H}^{M}_{X} H X M .
Fact 18. Let Q X Q_X Q X denote the aggregate X X X spent by sell-X X X users. Then, Q X ≥ M Q_X\geq M Q X ≥ M .
Proof. The proof is symmetric to that of Theorem 17. □
Theorem 19 (Main theorem: our full two-sided mechanism). Suppose that the pricing curve F F F satisfies assumptions ( A 1 ) (A1) ( A 1 ) –( A 4 ) (A4) ( A 4 ) defined in § 2.2 . Our full two-sided mechanism is well-formed and satisfies individual rationality, feasibility, user incentive compatibility (UIC), strategy-proofness against a builder(-as-user), and Pareto optimality for eligible users.
The remainder of the paper proves the theorem. In comparison with our one-sided guarantees in Theorem 11 , we must now account for deviations that can change which side is dominant or submit reports in both directions.
Proofs for the Two-Sided Mechanism
Well-Formedness, Individual Rationality, and Feasibility
Without loss of generality, we prove well-formedness, individual rationality, and feasibility only for the sell-Y Y Y dominated case, since the other case is symmetric.
Well-formedness and individual rationality. Well-formedness and individual rationality for the minority side follow in a straightforward fashion. Well-formedness and individual rationality for the dominant side follow directly from Theorem 11 .
Feasibility. By Lemma 17, the aggregate Y Y Y spent by sell-Y Y Y users satisfies Q Y ≥ M Q_Y \ge M Q Y ≥ M . Recall that the minority sell-X X X orders supply D X D_X D X units of X X X and must receive M = ρ 0 D X M = \rho_0 D_X M = ρ 0 D X units of Y Y Y . Thus the compensation to sell-X X X users is fully funded by the sell-Y Y Y orders. After using M M M units of the dominant sell-Y Y Y supply to compensate the sell-X X X users, the residual y : = Q Y − M ≥ 0 y := Q_Y - M \ge0 y := Q Y − M ≥ 0 units of Y Y Y are sent into the AMM’s pool, which returns exactly F ( y ) F(y) F ( y ) units of X X X . The total amount of X X X available to compensate dominant sell-Y Y Y sellers is therefore
D X + F ( Q Y − M ) = F ~ Y M ( Q Y ) . D_X + F(Q_Y - M) = \widetilde{F}^{M}_{Y}(Q_Y). D X + F ( Q Y − M ) = F Y M ( Q Y ) .
By Equation (7) of Theorem 11 ,
P X : = ∑ i ∈ Y x i ≤ F ~ Y M ( Q Y ) = D X + F ( Q Y − M ) . P_X := \sum_{i \in\mathcal{Y}} x_i \le\widetilde{F}^{M}_{Y}(Q_Y) = D_X + F(Q_Y - M). P X := i ∈ Y ∑ x i ≤ F Y M ( Q Y ) = D X + F ( Q Y − M ) .
where x i x_i x i is the amount of X X X tokens compensated to user i ∈ Y i \in\mathcal{Y} i ∈ Y . Thus every dominant-side compensation payment is fully funded, and the burnt surplus B X : = D X + F ( Q Y − M ) − P X ≥ 0 B_X := D_X + F(Q_Y - M) - P_X \ge0 B X := D X + F ( Q Y − M ) − P X ≥ 0 .
Pareto Optimality for Eligible Users
We now prove Pareto optimality for eligible users. Without loss of generality, we assume the sell-Y Y Y dominated case, since the proof for the other case is symmetric.
Every eligible sell-X X X user is on the minority side and, by (16) , exhausts its input budget. Consequently, after the mechanism executes, no eligible sell-X X X user has any X X X left available to sell. Any nontrivial trade among eligible users would require both a user supplying X X X and a user supplying Y Y Y . Thus no subset of eligible users can make an additional admissible trade among themselves, let alone one that is a Pareto improvement.
It remains to rule out a strictly beneficial additional trade with the pool. Let v ~ i ≤ σ 0 \tilde{v}_i \le\sigma_0 v ~ i ≤ σ 0 be the ask of an eligible sell-Y Y Y user. Let y : = Q Y − M ≥ 0 y := Q_Y - M \ge0 y := Q Y − M ≥ 0 be the residual Y Y Y input to the pool after compensating the sell-X X X users where Q Y Q_Y Q Y is the aggregate Y Y Y spent by sell-Y Y Y users. Define the final marginal prices by
σ e : = F + ′ ( y ) ( X per Y ) , ρ e : = 1 σ e . \sigma_e := F'_+(y) \quad(X\text{ per }Y), \qquad\rho_e := \frac{1}{\sigma_e}. σ e := F + ′ ( y ) ( X per Y ) , ρ e := σ e 1 .
An eligible user whose input budget is exhausted cannot make such a trade. Fix, therefore, a dominant-side sell-Y Y Y user i i i that is underfilled, i.e., y i < q ~ i y_i < \tilde{q}_i y i < q ~ i . For convenience, let G ( ⋅ ) : = F ~ Y M ( ⋅ ) G(\cdot) := \widetilde{F}^{M}_{Y}(\cdot) G ( ⋅ ) := F Y M ( ⋅ ) . If its ask satisfied v ~ i < G + ′ ( Q Y ) \tilde{v}_i < G'_+(Q_Y) v ~ i < G + ′ ( Q Y ) , then increasing y i y_i y i by a sufficiently small amount would raise reported welfare, contradicting the optimality of social welfare achieved by the allocation rule. Hence
v ~ i ≥ G + ′ ( Q Y ) = F + ′ ( Q Y − M ) = σ e \tilde{v}_i \ge G'_+(Q_Y) = F'_+(Q_Y - M) = \sigma_e v ~ i ≥ G + ′ ( Q Y ) = F + ′ ( Q Y − M ) = σ e
where the first equality follows from the fact that Q Y ≥ M Q_Y \ge M Q Y ≥ M and the two pieces of (17) meet with the same slope. For any additional amount 0 < δ ≤ q ^ i − y i 0 < \delta\le\widehat{q}_i-y_i 0 < δ ≤ q i − y i , concavity of F F F gives
F ( y + δ ) − F ( y ) ≤ F + ′ ( y ) δ = σ e δ ≤ v ~ i δ . F(y+\delta)-F(y)\le F_+'(y)\delta=\sigma_e\delta\le\widetilde{v}_i\delta. F ( y + δ ) − F ( y ) ≤ F + ′ ( y ) δ = σ e δ ≤ v i δ .
The additional pool output is therefore no greater than the user’s reported cost of supplying the additional input, so the trade cannot strictly improve its utility. This proves both Pareto-optimality conditions in a sell-Y dominated profile.
Incentive Compatibility
It suffices to prove user incentive compatibility (UIC), since by Theorem 9, UIC directly gives strategy-proofness for a builder(-as-user) for our mechanism which is order-insensitive.
We first prove a technical lemma which will later help us bound the utility of a strategic user who submits opposite-direction sybil orders, effectively extending the curve’s available offering at the initial price.
Lemma 20 (Curve-shift lemma). Fix a finite set O O O of sell-Y reports other than one comparison seller, and for M , q ≥ 0 M,q \ge0 M , q ≥ 0 let
ϕ Y ( M ; v , q ) : = W F ~ Y M ( O ∪ { ( v , q ) } ) − W F ~ Y M ( O ) . \phi_Y(M;v,q):=W_{\widetilde{F}_Y^M}\bigl(O\cup\{(v,q)\}\bigr)-W_{\widetilde{F}_Y^M}(O). ϕ Y ( M ; v , q ) := W F Y M ( O ∪ {( v , q )} ) − W F Y M ( O ) . For every v ≤ σ 0 v\le\sigma_0 v ≤ σ 0 , every α ≥ 0 \alpha\ge0 α ≥ 0 , and every comparison cap q ^ \widehat{q} q satisfying 0 ≤ q ^ ≤ q + α 0\le\widehat{q}\le q+\alpha 0 ≤ q ≤ q + α ,
ϕ Y ( M + α ; v , q ^ ) ≤ ϕ Y ( M ; v , q ) + ( σ 0 − v ) α . (18) \phi_Y(M+\alpha;v,\widehat{q})\le\phi_Y(M;v,q)+(\sigma_0-v)\alpha. \tag*{(18)} ϕ Y ( M + α ; v , q ) ≤ ϕ Y ( M ; v , q ) + ( σ 0 − v ) α . (18) Symmetrically, if O O O is a fixed set of sell-X reports and
ϕ X ( M ; u , r ) : = W H ~ X M ( O ∪ { ( u , r ) } ) − W H ~ X M ( O ) , \phi_X(M;u,r):=W_{\widetilde{H}_X^M}\bigl(O\cup\{(u,r)\}\bigr)-W_{\widetilde{H}_X^M}(O), ϕ X ( M ; u , r ) := W H X M ( O ∪ {( u , r )} ) − W H X M ( O ) , then for u ≤ ρ 0 u\le\rho_0 u ≤ ρ 0 , α ≥ 0 \alpha\ge0 α ≥ 0 , and 0 ≤ r ^ ≤ r + α 0\le\widehat{r}\le r+\alpha 0 ≤ r ≤ r + α ,
ϕ X ( M + α ; u , r ^ ) ≤ ϕ X ( M ; u , r ) + ( ρ 0 − u ) α . \phi_X(M+\alpha;u,\widehat{r})\le\phi_X(M;u,r)+(\rho_0-u)\alpha. ϕ X ( M + α ; u , r ) ≤ ϕ X ( M ; u , r ) + ( ρ 0 − u ) α .
Proof. We prove (18) since the other direction is symmetric. Apply the layer-cake representation (8) . Let D O ( t ) D_O(t) D O ( t ) be the aggregate capacity in O O O with ask at most t t t , and let K M ( t ) K_M(t) K M ( t ) be the threshold quantity associated with the curve F ~ Y M \widetilde{F}_Y^M F Y M . Extending the initial spot-price segment from M M M to M + α M+\alpha M + α translates this threshold by α \alpha α : for almost every t ∈ [ 0 , σ 0 ] t\in[0,\sigma_0] t ∈ [ 0 , σ 0 ] ,
K M + α ( t ) = K M ( t ) + α . K_{M+\alpha}(t)=K_M(t)+\alpha. K M + α ( t ) = K M ( t ) + α .
For v ≤ σ 0 v\le\sigma_0 v ≤ σ 0 , the layer-cake formula gives
ϕ Y ( M ; v , q ) = ∫ v σ 0 min { q , ( K M ( t ) − D O ( t ) ) + } d t . \phi_Y(M;v,q)=\int_v^{\sigma_0}\min\{q,(K_M(t)-D_O(t))_+\}\,\mathrm{d}t. ϕ Y ( M ; v , q ) = ∫ v σ 0 min { q , ( K M ( t ) − D O ( t ) ) + } d t .
For every real w w w , every q , α ≥ 0 q,\alpha\ge0 q , α ≥ 0 , and every 0 ≤ q ^ ≤ q + α 0\le\widehat{q}\le q+\alpha 0 ≤ q ≤ q + α ,
min { q ^ , ( w + α ) + } ≤ min { q , w + } + α . (19) \min\{\widehat{q},(w+\alpha)_+\}\le\min\{q,w_+\}+\alpha. \tag*{(19)} min { q , ( w + α ) + } ≤ min { q , w + } + α . (19)
Indeed, replacing q ^ \widehat{q} q by the larger q + α q+\alpha q + α can only increase the left-hand side, after which the inequality is immediate by considering w ≥ 0 w\ge0 w ≥ 0 , − α < w < 0 -\alpha<w<0 − α < w < 0 , and w ≤ − α w\le-\alpha w ≤ − α . Apply Equation (19) pointwise with w = K M ( t ) − D O ( t ) w=K_M(t)-D_O(t) w = K M ( t ) − D O ( t ) and integrate over t ∈ [ v , σ 0 ] t\in[v,\sigma_0] t ∈ [ v , σ 0 ] . The interval has length σ 0 − v \sigma_0-v σ 0 − v , yielding Equation (18) .
A Real Sell-Y User
Fix all reports of other real users and consider one real sell-Y Y Y user of type ( v , q ) (v,q) ( v , q ) . Let
D Y o t h : = ∑ i other sell- Y v ~ i ≤ σ 0 q ~ i , D X o t h : = ∑ i other sell- X u ~ i ≤ ρ 0 r ~ i , M Y o t h : = ρ 0 D X o t h . D_Y^{\mathrm{oth}} := \sum_{\substack{i\ \text{other sell-}Y\\ \tilde{v}_i\leq\sigma_0}} \tilde{q}_i,\qquad D_X^{\mathrm{oth}} := \sum_{\substack{i\ \text{other sell-}X\\ \tilde{u}_i\leq\rho_0}} \tilde{r}_i,\qquad M_Y^{\mathrm{oth}} := \rho_0D_X^{\mathrm{oth}}. D Y oth := i other sell- Y v ~ i ≤ σ 0 ∑ q ~ i , D X oth := i other sell- X u ~ i ≤ ρ 0 ∑ r ~ i , M Y oth := ρ 0 D X oth .
where D Y o t h D_Y^{\mathrm{oth}} D Y oth and D X o t h D_X^{\mathrm{oth}} D X oth are the total spot-eligible sell-Y Y Y and sell-X X X capacities of the other users, respectively. Thus D Y o t h D_Y^{\mathrm{oth}} D Y oth , D X o t h D_X^{\mathrm{oth}} D X oth , and M Y o t h M_Y^{\mathrm{oth}} M Y oth are fixed before the strategic user’s sybil identities are introduced.
Truthful utility. The following facts about truthful utility are easy to see:
If v > σ 0 v>\sigma_0 v > σ 0 , truthful utility is zero.
If v ≤ σ 0 v\leq\sigma_0 v ≤ σ 0 and D Y o t h + q < M Y o t h D_Y^{\mathrm{oth}}+q<M_Y^{\mathrm{oth}} D Y oth + q < M Y oth , the truthful user is on the minority side and receives
U t i l t r = ( σ 0 − v ) q . \mathrm{Util}^{\mathrm{tr}}=(\sigma_0-v)q. Util tr = ( σ 0 − v ) q .
Moreover, we have
ϕ Y ( M Y o t h ; v , q ) = ( σ 0 − v ) q = U t i l t r . (20) \phi_Y(M_Y^{\mathrm{oth}};v,q)=(\sigma_0-v)q=\mathrm{Util}^{\mathrm{tr}}. \tag*{(20)} ϕ Y ( M Y oth ; v , q ) = ( σ 0 − v ) q = Util tr . (20)
U t i l t r = ϕ Y ( M Y o t h ; v , q ) ≥ ( σ 0 − v ) ℓ , ℓ : = ( M Y o t h − D Y o t h ) + . (21) \mathrm{Util}^{\mathrm{tr}}=\phi_Y(M_Y^{\mathrm{oth}};v,q)\geq(\sigma_0-v)\ell,\qquad\ell:=\left(M_Y^{\mathrm{oth}}-D_Y^{\mathrm{oth}}\right)^+. \tag*{(21)} Util tr = ϕ Y ( M Y oth ; v , q ) ≥ ( σ 0 − v ) ℓ , ℓ := ( M Y oth − D Y oth ) + . (21)
Replace the truthful identity by an arbitrary finite set I \mathcal{I} I of sybil bids in either direction. Henceforth, we use the aggregate flow notation from Equation (1) . The user’s net Y Y Y sale is − Δ Y = S Y − R Y -\Delta_Y=S_Y-R_Y − Δ Y = S Y − R Y . If − Δ Y > q -\Delta_Y>q − Δ Y > q , the attack has utility − ∞ -\infty − ∞ by Equation (2) . A negative net sale is not catastrophic by itself: under Equation (2) we must also show that it entails a strict net loss in X X X . We verify this separately in each dominance regime below. After doing so, essentially we only need to consider the regime
0 ≤ − Δ Y ≤ q . (22) 0\leq-\Delta_Y\leq q. \tag*{(22)} 0 ≤ − Δ Y ≤ q . (22)
Notice that Equation (22) does not imply S Y ≤ q S_Y\leq q S Y ≤ q .
The sybil profile is sell-Y Y Y dominated. Every spot-eligible sell-X X X sybil identity is then on the minority side and is fully executed at the spot price; every ineligible one executes zero. Therefore R Y = ρ 0 S X R_Y=\rho_0S_X R Y = ρ 0 S X . These opposite-direction sybils extend the dominant sell-Y Y Y crossing parameter from M Y o t h M_Y^{\mathrm{oth}} M Y oth to M Y o t h + R Y M_Y^{\mathrm{oth}}+R_Y M Y oth + R Y .
The individual payment bound (6) , summed over the user’s dominant-side sell-Y Y Y sybils, gives R X ≤ σ 0 S Y R_X\leq\sigma_0S_Y R X ≤ σ 0 S Y . If net Y Y Y sale − Δ Y = S Y − R Y < 0 -\Delta_Y=S_Y-R_Y<0 − Δ Y = S Y − R Y < 0 , then Δ X = R X − S X = R X − σ 0 R Y ≤ σ 0 ( S Y − R Y ) < 0 \Delta_X=R_X-S_X=R_X-\sigma_0R_Y\leq\sigma_0(S_Y-R_Y)<0 Δ X = R X − S X = R X − σ 0 R Y ≤ σ 0 ( S Y − R Y ) < 0 . In this case, the second catastrophic condition in (2) applies, and the attack has − ∞ -\infty − ∞ utility. Moreover, if − Δ Y = S Y − R Y > q -\Delta_Y=S_Y-R_Y>q − Δ Y = S Y − R Y > q , the attack also has − ∞ -\infty − ∞ utility. Thus we may assume
R Y ≤ S Y ≤ q + R Y . (23) R_Y\leq S_Y\leq q+R_Y. \tag*{(23)} R Y ≤ S Y ≤ q + R Y . (23)
The user’s utility is
U t i l s y b = R X − S X − v ( S Y − R Y ) = R X − σ 0 R Y − v ( S Y − R Y ) . (24) \begin{aligned}
\mathrm{Util}^{\mathrm{syb}}&=R_X-S_X-v(S_Y-R_Y)\\
&=R_X-\sigma_0R_Y-v(S_Y-R_Y). \tag*{(24)}
\end{aligned} Util syb = R X − S X − v ( S Y − R Y ) = R X − σ 0 R Y − v ( S Y − R Y ) . (24)
If v > σ 0 v > \sigma_0 v > σ 0 , using again R X ≤ σ 0 S Y R_X \le\sigma_0 S_Y R X ≤ σ 0 S Y together with S Y − R Y = − Δ Y ≥ 0 S_Y - R_Y = -\Delta_Y \ge0 S Y − R Y = − Δ Y ≥ 0 ,
Util s y b ≤ ( σ 0 − v ) ( S Y − R Y ) ≤ 0 = Util t r . \operatorname{Util}^{\mathrm{syb}} \le(\sigma_0 - v)(S_Y - R_Y) \le0 = \operatorname{Util}^{\mathrm{tr}}. Util syb ≤ ( σ 0 − v ) ( S Y − R Y ) ≤ 0 = Util tr .
Now suppose v ≤ σ 0 v \le\sigma_0 v ≤ σ 0 . Freeze the curve F ~ Y M o t h + R Y \widetilde{F}^{\mathrm{Moth}+R_Y}_Y F Y Moth + R Y and merge the user’s sell-Y Y Y sybils only for purposes of comparison. The UIC guarantee in part (e) of Theorem 11 , with a virtual sell-Y Y Y user of true cost v z vz v z and budget equal to the realized gross sale S Y S_Y S Y , gives
R X − v S Y ≤ ϕ Y ( M Y o t h + R Y ; v , S Y ) . (25) R_X - vS_Y \le\phi_Y(M_Y^{\mathrm{oth}} + R_Y; v, S_Y). \tag*{(25)} R X − v S Y ≤ ϕ Y ( M Y oth + R Y ; v , S Y ) . (25)
By (23) , S Y ≤ q + R Y S_Y \le q + R_Y S Y ≤ q + R Y . Combining (24) , (25) , and Lemma 20 ,
Util s y b ≤ ϕ Y ( M Y o t h + R Y ; v , S Y ) − ( σ 0 − v ) R Y ≤ ϕ Y ( M Y o t h ; v , q ) . \begin{aligned}
\operatorname{Util}^{\mathrm{syb}} &\le\phi_Y(M_Y^{\mathrm{oth}} + R_Y; v, S_Y) - (\sigma_0 - v)R_Y \\
&\le\phi_Y(M_Y^{\mathrm{oth}}; v, q).
\end{aligned} Util syb ≤ ϕ Y ( M Y oth + R Y ; v , S Y ) − ( σ 0 − v ) R Y ≤ ϕ Y ( M Y oth ; v , q ) .
The last quantity equals truthful utility both when truth is dominant, by the VCG marginal-contribution identity, and when truth is minority, by (20) . Thus this attack cannot help.
The sybil profile is sell-X X X dominated. The user’s active sell-Y Y Y sybil identities are now minority identities, so they receive R X = σ 0 S Y R_X = \sigma_0 S_Y R X = σ 0 S Y . The dominant-side payment bound gives R Y ≤ ρ 0 S X R_Y \le\rho_0 S_X R Y ≤ ρ 0 S X , or equivalently S X ≥ σ 0 R Y S_X \ge\sigma_0 R_Y S X ≥ σ 0 R Y . If − Δ Y = S Y − R Y < 0 -\Delta_Y = S_Y - R_Y < 0 − Δ Y = S Y − R Y < 0 , then we also have Δ X = σ 0 S Y − S X ≤ σ 0 ( S Y − R Y ) < 0 \Delta_X = \sigma_0 S_Y - S_X \le\sigma_0(S_Y - R_Y) < 0 Δ X = σ 0 S Y − S X ≤ σ 0 ( S Y − R Y ) < 0 . Hence Equation (2) assigns the attack utility − ∞ -\infty − ∞ . Moreover, if − Δ Y = S Y − R Y > q -\Delta_Y = S_Y - R_Y > q − Δ Y = S Y − R Y > q , the attack also has − ∞ -\infty − ∞ utility. We may therefore restrict finite-utility attacks in this regime to 0 ≤ S Y − R Y ≤ q 0 \le S_Y - R_Y \le q 0 ≤ S Y − R Y ≤ q . Their utility is
Util s y b = σ 0 S Y − S X − v ( S Y − R Y ) ≤ ( σ 0 − v ) ( S Y − R Y ) = ( σ 0 − v ) ⋅ ( − Δ Y ) . (26) \operatorname{Util}^{\mathrm{syb}} = \sigma_0 S_Y - S_X - v(S_Y - R_Y) \le(\sigma_0 - v)(S_Y - R_Y) = (\sigma_0 - v) \cdot(-\Delta_Y). \tag*{(26)} Util syb = σ 0 S Y − S X − v ( S Y − R Y ) ≤ ( σ 0 − v ) ( S Y − R Y ) = ( σ 0 − v ) ⋅ ( − Δ Y ) . (26)
If v > σ 0 v > \sigma_0 v > σ 0 , this is nonpositive and cannot beat truthful utility zero. If v ≤ σ 0 v \le\sigma_0 v ≤ σ 0 and truthful reporting makes sell-Y Y Y the minority side, then − Δ Y ≤ q -\Delta_Y \le q − Δ Y ≤ q makes Equation (27) at most the truthful value ( σ 0 − v ) q (\sigma_0 - v)q ( σ 0 − v ) q .
It remains to consider the case v ≤ σ 0 v \le\sigma_0 v ≤ σ 0 in which truthful reporting makes sell-Y Y Y dominant. Rewrite the user’s utility as
Util s y b = ( σ 0 − v ) ( S Y − ρ 0 S X ) + v ( R Y − ρ 0 S X ) . (27) \operatorname{Util}^{\mathrm{syb}} = (\sigma_0 - v)(S_Y - \rho_0 S_X) + v(R_Y - \rho_0 S_X). \tag*{(27)} Util syb = ( σ 0 − v ) ( S Y − ρ 0 S X ) + v ( R Y − ρ 0 S X ) . (27)
The second term is nonpositive because R Y ≤ ρ 0 S X R_Y \le\rho_0 S_X R Y ≤ ρ 0 S X . Let S X o t h S_X^{\mathrm{oth}} S X oth be the amount of X X X sold, in the sybil outcome, by all other sell-X X X identities. Theorem 18 gives
S X + S X o t h ≥ σ 0 ( D Y o t h + S Y ) . S_X + S_X^{\mathrm{oth}} \ge\sigma_0(D_Y^{\mathrm{oth}} + S_Y). S X + S X oth ≥ σ 0 ( D Y oth + S Y ) .
Given that S X o t h ≤ D X o t h = σ 0 M Y o t h S_X^{\mathrm{oth}} \le D_X^{\mathrm{oth}} = \sigma_0 M_Y^{\mathrm{oth}} S X oth ≤ D X oth = σ 0 M Y oth , we have
S Y − ρ 0 S X ≤ M Y o t h − D Y o t h ≤ ℓ . S_Y - \rho_0 S_X \le M_Y^{\mathrm{oth}} - D_Y^{\mathrm{oth}} \le\ell. S Y − ρ 0 S X ≤ M Y oth − D Y oth ≤ ℓ .
Since σ 0 − v ≥ 0 \sigma_0 - v \ge0 σ 0 − v ≥ 0 , Equation (27) and (21) yield
Util s y b ≤ ( σ 0 − v ) ℓ ≤ Util t r . \operatorname{Util}^{\mathrm{syb}} \le(\sigma_0 - v)\ell\le\operatorname{Util}^{\mathrm{tr}}. Util syb ≤ ( σ 0 − v ) ℓ ≤ Util tr .
Thus no arbitrary finite cross-direction sybil attack benefits a true sell-Y Y Y user under the utility function defined in Equation (2) .
A Real Sell-X User
Fix all reports of other real users and consider one real sell-X user of type ( u , r ) (u,r) ( u , r ) . Let
D Y o t h : = ∑ i other sell-Y v ~ i ≤ σ 0 q ~ i , D X o t h : = ∑ i other sell-X u ~ i ≤ ρ 0 r ~ i , M X o t h : = σ 0 D Y o t h . D_Y^{\mathrm{oth}} := \sum_{\substack{i\ \text{other sell-Y}\\ \tilde{v}_i \le\sigma_0}} \tilde{q}_i,\qquad
D_X^{\mathrm{oth}} := \sum_{\substack{i\ \text{other sell-X}\\ \tilde{u}_i \le\rho_0}} \tilde{r}_i,\qquad
M_X^{\mathrm{oth}} := \sigma_0 D_Y^{\mathrm{oth}}. D Y oth := i other sell-Y v ~ i ≤ σ 0 ∑ q ~ i , D X oth := i other sell-X u ~ i ≤ ρ 0 ∑ r ~ i , M X oth := σ 0 D Y oth .
Thus M X o t h M_X^{\mathrm{oth}} M X oth is the other users’ spot-eligible sell-Y capacity measured in units of X X X . The proof is obtained from the proof for a real sell-Y user by making the substitutions
X ⟷ Y , F ⟷ H , σ 0 ⟷ ρ 0 , ( v , q ) ⟷ ( u , r ) , X \longleftrightarrow Y,\qquad F \longleftrightarrow H,\qquad\sigma_0 \longleftrightarrow\rho_0,\qquad(v,q) \longleftrightarrow(u,r), X ⟷ Y , F ⟷ H , σ 0 ⟷ ρ 0 , ( v , q ) ⟷ ( u , r ) ,
D Y o t h ⟷ D X o t h , M Y o t h ⟷ M X o t h , ϕ Y ( M ; v , q ) ⟷ ϕ X ( M ; u , r ) , D_Y^{\mathrm{oth}} \longleftrightarrow D_X^{\mathrm{oth}},\qquad
M_Y^{\mathrm{oth}} \longleftrightarrow M_X^{\mathrm{oth}},\qquad
\phi_Y(M;v,q) \longleftrightarrow\phi_X(M;u,r), D Y oth ⟷ D X oth , M Y oth ⟷ M X oth , ϕ Y ( M ; v , q ) ⟷ ϕ X ( M ; u , r ) ,
S Y ⟷ S X , R Y ⟷ R X , S X o t h ⟷ S Y o t h , − Δ Y ⟷ − Δ X , S_Y \longleftrightarrow S_X,\qquad
R_Y \longleftrightarrow R_X,\qquad
S_X^{\mathrm{oth}} \longleftrightarrow S_Y^{\mathrm{oth}},\qquad
-\Delta_Y \longleftrightarrow-\Delta_X, S Y ⟷ S X , R Y ⟷ R X , S X oth ⟷ S Y oth , − Δ Y ⟷ − Δ X ,
and replacing the dominant-side curve F ~ Y M \widetilde{F}_Y^M F Y M by H ~ X M \widetilde{H}_X^M H X M .
The only modifications concern boundary classification, because ties are resolved in favor of sell-Y dominance. For a truthful eligible sell-X user, truth is on the minority side when
D X o t h + r ≤ M X o t h , D_X^{\mathrm{oth}} + r \le M_X^{\mathrm{oth}}, D X oth + r ≤ M X oth ,
where equality is included, and its utility is ( ρ 0 − u ) r = ϕ X ( M X o t h ; u , r ) (\rho_0-u)r=\phi_X(M_X^{\mathrm{oth}};u,r) ( ρ 0 − u ) r = ϕ X ( M X oth ; u , r ) . Truth is on the dominant side only when
D X o t h + r > M X o t h , D_X^{\mathrm{oth}} + r > M_X^{\mathrm{oth}}, D X oth + r > M X oth ,
in which case its utility is ϕ X ( M X o t h ; u , r ) \phi_X(M_X^{\mathrm{oth}};u,r) ϕ X ( M X oth ; u , r ) and is at least
( ρ 0 − u ) ( M X o t h − D X o t h ) + . (\rho_0-u)(M_X^{\mathrm{oth}}-D_X^{\mathrm{oth}})_+. ( ρ 0 − u ) ( M X oth − D X oth ) + .
Likewise, a sybil profile is sell-X dominated only under a strict imbalance D Y < ρ 0 D X D_Y<\rho_0D_X D Y < ρ 0 D X . The reverse branch, D Y ≥ ρ 0 D X D_Y\ge\rho_0D_X D Y ≥ ρ 0 D X , includes equality and is sell-Y dominated. Thus, at equality, the user’s spot-eligible sell-X sybils are minority orders and execute fully at the spot rate ρ 0 \rho_0 ρ 0 , while its ineligible sell-X sybils execute zero. With these changes to the weak and strict inequalities, every bound in the sell-Y proof carries over under the substitutions above.
Social Welfare Maximization
Defining natural. We call a deterministic AMM mechanism natural if it satisfies the following properties:
(Drop) Drop ineligible bids. Every ineligible bid receives zero allocation and zero transfer. Thus a sell-X report with u ~ j > ρ 0 \tilde{u}_j>\rho_0 u ~ j > ρ 0 receives ( x j , y j ) = ( 0 , 0 ) (x_j,y_j)=(0,0) ( x j , y j ) = ( 0 , 0 ) , and a sell-Y report with v ~ i > σ 0 \tilde{v}_i>\sigma_0 v ~ i > σ 0 receives ( y i , x i ) = ( 0 , 0 ) (y_i,x_i)=(0,0) ( y i , x i ) = ( 0 , 0 ) .
(NPR) No price reversal. The residual trade with the AMM does not reverse the direction implied by the spot-eligible imbalance. Thus, at a sell-Y-dominated profile the AMM weakly receives Y Y Y , and at a sell-X-dominated profile it weakly receives X X X . Additionally, the final marginal price moves weakly against the dominant side. In particular, if the profile is sell-Y dominated, then
σ e ≤ σ 0 , and ρ e ≥ ρ 0 . \sigma_e \le\sigma_0,\qquad\text{and}\qquad\rho_e \ge\rho_0. σ e ≤ σ 0 , and ρ e ≥ ρ 0 .
If the profile is sell-X X X dominated, then
ρ e ≤ ρ 0 , and σ e ≥ σ 0 . \rho_e \le\rho_0, \qquad\text{and} \qquad\sigma_e \ge\sigma_0. ρ e ≤ ρ 0 , and σ e ≥ σ 0 .
Here σ e \sigma_e σ e and ρ e \rho_e ρ e are the final marginal compensation rates in units of X X X per Y Y Y and Y Y Y per X X X , respectively. At a nondifferentiable point, the inequalities refer to the marginal rate for an additional trade in the relevant dominant direction.
Justification of naturalness. The (Drop) condition stipulates that the mechanism simply ignores ineligible bids. This assumption is justified in Section A, where we prove that no UIC mechanism can achieve Pareto optimality for all bids including ineligible ones. In fact, Section A establishes a stronger impossibility result: even an efficiency notion strictly weaker than Pareto optimality is incompatible with UIC.
(NPR) formalizes the conventional price-impact intuition that aggregate selling pressure on an asset should not cause that asset to appreciate. This is analogous to the classical Walrasian tâtonnement principle that prices adjust in the direction of excess demand [5 ] . (NPR) imposes only this directional requirement and makes no assumption about the magnitude of the resulting price movement.
Lemma 21 (Structure of minority-side execution). Fix a report profile and a deterministic natural mechanism satisfying UIC and Pareto optimality for eligible users. Every executed minority-side order is compensated at the initial spot price. Moreover, every minority-side order whose ask is strictly below the initial spot price exhausts its reported budget.
In particular, at a sell-Y Y Y -dominated profile, define M M M by
σ 0 M = ∑ j ∈ X x j , (28) \sigma_0 M = \sum_{j\in\mathcal{X}} x_j, \tag*{(28)} σ 0 M = j ∈ X ∑ x j , (28) so that σ 0 M \sigma_0M σ 0 M is the total X X X spent by the minority side. The minority side receives exactly M M M units of Y Y Y , and the dominant side spends at least M M M units of Y Y Y :
∑ i ∈ Y y i ≥ M . (29) \sum_{i\in\mathcal{Y}} y_i \ge M. \tag*{(29)} i ∈ Y ∑ y i ≥ M . (29) The symmetric statements hold at a sell-X X X -dominated profile.
Proof. We prove the result for a sell-Y Y Y -dominated profile. Consider an eligible minority-side sell-X X X user j j j . If u ~ j < ρ 0 \tilde{u}_j < \rho_0 u ~ j < ρ 0 and x j < r ~ j x_j < \tilde{r}_j x j < r ~ j , then (NPR) gives ρ e ≥ ρ 0 > u ~ j \rho_e \ge\rho_0 > \tilde{u}_j ρ e ≥ ρ 0 > u ~ j . The user could sell a sufficiently small additional amount of X X X directly to the pool at a marginal rate strictly above its reservation value, contradicting Pareto optimality for eligible users. Hence
x j = r ~ j whenever u ~ j < ρ 0 . (30) x_j = \tilde{r}_j \qquad\text{whenever } \tilde{u}_j < \rho_0. \tag*{(30)} x j = r ~ j whenever u ~ j < ρ 0 . (30)
Fix the other reports and bidder j j j 's reported budget r r r . For an ask t < ρ 0 t < \rho_0 t < ρ 0 , let h ( t ) h(t) h ( t ) denote its compensation in Y Y Y . By (31), every such report sells r r r . UIC applied to any two asks s , t < ρ 0 s,t < \rho_0 s , t < ρ 0 , in both directions, implies h ( s ) = h ( t ) = C h(s)=h(t)=C h ( s ) = h ( t ) = C . A type ( t , r ) (t,r) ( t , r ) can report an ineligible ask and obtain zero by (Drop), so C − t r ≥ 0 C-tr \ge0 C − t r ≥ 0 ; letting t ↑ ρ 0 t \uparrow\rho_0 t ↑ ρ 0 gives C ≥ ρ 0 r C \ge\rho_0r C ≥ ρ 0 r . Conversely, a type ( a , r ) (a,r) ( a , r ) with a > ρ 0 a > \rho_0 a > ρ 0 obtains zero truthfully and can report t < ρ 0 t < \rho_0 t < ρ 0 , so UIC gives 0 ≥ C − a r 0 \ge C-ar 0 ≥ C − a r ; letting a ↓ ρ 0 a \downarrow\rho_0 a ↓ ρ 0 gives C ≤ ρ 0 r C \le\rho_0r C ≤ ρ 0 r . Thus C = ρ 0 r C=\rho_0r C = ρ 0 r . For a boundary report u ~ j = ρ 0 \tilde{u}_j=\rho_0 u ~ j = ρ 0 , UIC relative to an ineligible report gives y j − ρ 0 x j ≥ 0 y_j-\rho_0x_j\ge0 y j − ρ 0 x j ≥ 0 . A type a > ρ 0 a>\rho_0 a > ρ 0 that deviates to this boundary report must obtain utility at most zero, so 0 ≥ y j − a x j 0\ge y_j-ax_j 0 ≥ y j − a x j . Letting a ↓ ρ 0 a\downarrow\rho_0 a ↓ ρ 0 gives the reverse inequality. Consequently,
y j = ρ 0 x j (31) y_j=\rho_0x_j \tag*{(31)} y j = ρ 0 x j (31)
for every eligible minority-side user (and hence for every executed one, by (Drop)). Summing (31) and using ρ 0 = 1 / σ 0 \rho_0=1/\sigma_0 ρ 0 = 1/ σ 0 shows that the minority side receives M M M units of Y Y Y . If y : = ∑ i ∈ Y y i y:=\sum_{i\in\mathcal{Y}}y_i y := ∑ i ∈ Y y i is the dominant side’s total expenditure, token balance leaves y − M y-M y − M units of Y Y Y as the residual input to the AMM. By (NPR) this residual trade is in the dominant direction, so y − M ≥ 0 y-M\ge0 y − M ≥ 0 . This proves (29) . The sell-X X X -dominated case follows by symmetry.
Definition of dominant-side welfare. By Theorem 21, at a sell-Y Y Y -dominated outcome the minority side spends σ 0 M \sigma_0M σ 0 M units of X X X and receives M M M units of Y Y Y , while the dominant side spends some total y ≥ M y\ge M y ≥ M units of Y Y Y . The first M M M units of dominant-side expenditure are crossed with the minority supply, and the remaining y − M y-M y − M units are sent to the pool. We therefore define dominant-side social welfare as the X X X produced by these two sources minus the reported production cost of the dominant-side Y Y Y :
D S W Y : = σ 0 M + F ( y − M ) − ∑ i ∈ Y v ~ i y i , y : = ∑ i ∈ Y y i . (32) \mathrm{DSW}_{Y}:=\sigma_0M+F(y-M)-\sum_{i\in\mathcal{Y}}\tilde{v}_iy_i,\qquad y:=\sum_{i\in\mathcal{Y}}y_i. \tag*{(32)} DSW Y := σ 0 M + F ( y − M ) − i ∈ Y ∑ v ~ i y i , y := i ∈ Y ∑ y i . (32)
For a sell-X X X -dominated outcome, define M M M by ρ 0 M = ∑ i ∈ Y y i \rho_0M=\sum_{i\in\mathcal{Y}}y_i ρ 0 M = ∑ i ∈ Y y i and, writing x : = ∑ j ∈ X x j ≥ M x:=\sum_{j\in\mathcal{X}}x_j\ge M x := ∑ j ∈ X x j ≥ M , define symmetrically
D S W X : = ρ 0 M + H ( x − M ) − ∑ j ∈ X u ~ j x j . \mathrm{DSW}_{X}:=\rho_0M+H(x-M)-\sum_{j\in\mathcal{X}}\tilde{u}_jx_j. DSW X := ρ 0 M + H ( x − M ) − j ∈ X ∑ u ~ j x j .
Ineligible bids make zero contribution by (Drop). The compensation token of the dominant direction is the numeraire; no arbitrary common numeraire is imposed across the two dominance regimes.
Theorem 22 (Welfare maximality among natural mechanisms). Fix a report profile. Among deterministic natural mechanisms satisfying UIC and Pareto optimality for eligible users, our mechanism has the following properties:
(i) every strictly eligible minority-side user obtains the same truthful utility under every mechanism in this class, while every boundary or ineligible minority-side user obtains zero;
(ii) if the profile is sell-Y Y Y dominated, our mechanism maximizes D S W Y \mathrm{DSW}_Y DSW Y ; if it is sell-X X X dominated, our mechanism maximizes D S W X \mathrm{DSW}_X DSW X .
Proof. We prove the claims for a sell-Y Y Y -dominated profile. The sell-X X X -dominated case follows by symmetry.
By Theorem 21, a strictly eligible sell-X X X user j j j sells its full budget and is compensated at the initial price. Its truthful utility is therefore ( ρ 0 − u j ) r j (\rho_0-u_j)r_j ( ρ 0 − u j ) r j . A boundary user has zero utility whether or not it is executed, and an ineligible user has zero utility by (Drop). This proves (i).
Dominant-side welfare. Let
M ∗ : = ρ 0 D X M^*:=\rho_0D_X M ∗ := ρ 0 D X
be the crossing length used by our mechanism. It fully executes every spot-eligible sell-X X X bid, including boundary bids. For another natural mechanism, define M M M as in (28) . The lemma and the reported caps imply M ≤ M ∗ M \le M^{*} M ≤ M ∗ ; the only possible difference is partial execution of bids with ask exactly ρ 0 \rho_{0} ρ 0 .
For purposes of the comparison, extend the expression in (32) to all y ≥ 0 y \ge0 y ≥ 0 by writing
F ~ M ( y ) : = { σ 0 y , 0 ≤ y ≤ M , σ 0 M + F ( y − M ) , y ≥ M . \widetilde{F}^{M}(y) :=
\begin{cases}
\sigma_{0}y, & 0 \le y \le M,\\
\sigma_{0}M + F(y-M), & y \ge M.
\end{cases} F M ( y ) := { σ 0 y , σ 0 M + F ( y − M ) , 0 ≤ y ≤ M , y ≥ M .
On every outcome of a mechanism in the comparison class, the lemma gives y ≥ M y \ge M y ≥ M , so the second branch is precisely the welfare expression already defined in (32) .
We claim that, for every y ≥ 0 y \ge0 y ≥ 0 , the modified compensation curve is nondecreasing in its crossing length:
M ≤ M ∗ ⟹ F ~ M ( y ) ≤ F ~ M ∗ ( y ) . (33) M \le M^{*} \quad\Longrightarrow\quad\widetilde{F}^{M}(y) \le\widetilde{F}^{M^{*}}(y). \tag*{(33)} M ≤ M ∗ ⟹ F M ( y ) ≤ F M ∗ ( y ) . (33)
If y ≤ M y \le M y ≤ M , the two sides are equal to σ 0 y \sigma_{0}y σ 0 y . If M < y ≤ M ∗ M < y \le M^{*} M < y ≤ M ∗ , concavity and F + ′ ( 0 ) = σ 0 F_{+}^{\prime}(0) = \sigma_{0} F + ′ ( 0 ) = σ 0 give
F ( y − M ) ≤ σ 0 ( y − M ) , F(y-M) \le\sigma_{0}(y-M), F ( y − M ) ≤ σ 0 ( y − M ) ,
so the claim follows. If y > M ∗ y > M^{*} y > M ∗ , concavity gives
F ( y − M ) − F ( y − M ∗ ) ≤ σ 0 ( M ∗ − M ) , F(y-M) - F(y-M^{*}) \le\sigma_{0}(M^{*}-M), F ( y − M ) − F ( y − M ∗ ) ≤ σ 0 ( M ∗ − M ) ,
which again proves (33) .
Let ( y i ) (y_i) ( y i ) be the dominant-side allocation of the other mechanism. It is a feasible candidate for our mechanism’s one-sided welfare problem because the reported caps are the same. Our allocation maximizes the one-sided objective with curve F ~ M ∗ \widetilde{F}^{M^{*}} F M ∗ , and (33) therefore gives
DSW Y o u r s ≥ F ~ M ∗ ( ∑ i y i ) − ∑ i v ~ i y i ≥ F ~ M ( ∑ i y i ) − ∑ i v ~ i y i = DSW Y o t h e r . \begin{aligned}
\operatorname{DSW}_{Y}^{\mathrm{ours}} \ge\widetilde{F}^{M^{*}}\left(\sum_i y_i\right) - \sum_i \widetilde{v}_i y_i \\
&\ge\widetilde{F}^{M}\left(\sum_i y_i\right) - \sum_i \widetilde{v}_i y_i = \operatorname{DSW}_{Y}^{\mathrm{other}}.
\end{aligned} DSW Y ours ≥ F M ∗ ( i ∑ y i ) − i ∑ v i y i ≥ F M ( i ∑ y i ) − i ∑ v i y i = DSW Y other .
This proves part (ii). Exchanging X X X with Y Y Y , F F F with H H H , and σ 0 \sigma_{0} σ 0 with ρ 0 \rho_{0} ρ 0 proves both claims for a sell-X X X -dominated profile.
Restrictions on Builder Fee Structure
Our mechanism burns the unused compensation token. A natural alternative is to transfer some of that excess to the block builder and burn only the remainder. In this section, we show that subject to UIC and strategy-proofness for a builder who is simultaneously a user with intrinsic demand, the only possible builder fee structure is to have the residual surplus entirely “burnt”, i.e., redistributed to the community, and pay the builder zero fees. In practice, however, one can remunerate the builder with a constant exogenous block subsidy that is independent of the current batch’s outcomes, e.g., using the community surplus accumulated so far. Such a payment will not affect the game theoretic guarantees achieved by the mechanism.
Our “zero builder fee” impossibility can be viewed as a seller-side analogue of the “zero miner revenue” impossibility in transaction-fee mechanisms; see, for example, Theorem 4.7 of Chung and Shi [19 ] . Our proof techniques are also inspired by their work.
Additional Preliminaries and Notations
Because this is an impossibility result, it is enough to restrict attention to a smaller type and strategy space. Specifically, we consider a finite sell-Y Y Y -only batch. Moreover, since our proof will only need strategies that misreport valuation, we may fix arbitrary budget q ˉ i > 0 \bar{q}_i > 0 q ˉ i > 0 . Thus we effectively consider a single-parameter environment where only the per-unit reservation values are private. Any mechanism that is incentive compatible on the richer type space of the main model must remain incentive compatible on this single-parameter restriction.
Although our earlier feasibility is a deterministic AMM mechanism, our impossibility result in this section holds even for randomized mechanisms. For a report vector v ~ = ( v ~ 1 , … , v ~ n ) \widetilde{\mathbf{v}} = (\widetilde{v}_1, \ldots, \widetilde{v}_n) v = ( v 1 , … , v n ) , let
y ˉ i ( v ~ ) ∈ [ 0 , q ˉ i ] \bar{y}_i(\widetilde{\mathbf{v}}) \in[0,\bar{q}_i] y ˉ i ( v ) ∈ [ 0 , q ˉ i ]
denote the expected amount of Y Y Y sold by user i i i , and let x ˉ i ( v ~ ) \bar{x}_i(\widetilde{\mathbf{v}}) x ˉ i ( v ) denote its expected compensation in X X X . Let
μ ˉ ( v ~ ) ≥ 0 , \bar{\mu}(\widetilde{\mathbf{v}}) \ge0, μ ˉ ( v ) ≥ 0 ,
and β ˉ ( v ~ ) ≥ 0 \bar{\beta}(\widetilde{\mathbf{v}}) \ge0 β ˉ ( v ) ≥ 0 denote the expected builder fee and expected burn amount, respectively. In the above, all expectations are taken over the mechanism’s random coins. Let
Y ˉ ( v ~ ) : = ∑ i y ˉ i ( v ~ ) . \bar{Y}(\widetilde{\mathbf{v}}) := \sum_i \bar{y}_i(\widetilde{\mathbf{v}}). Y ˉ ( v ) := i ∑ y ˉ i ( v ) .
In our impossibility result (Theorem 26 ), we will make use of individual rationality (IR), feasibility, user incentive compatibility (UIC), and strategy-proofness for a builder who is also a user with intrinsic demand. Since we want the impossibility to work even for possibly randomized mechanisms, the UIC and strategy-proofness definitions will be modified to use the expected utility instead. Note that for a builder-as-user, the fees obtained by the builder will be added to its utility. For a feasibility result we would ideally want IR to hold with probability 1. However, for our impossibility proof, we only need IR to hold in the expectation too, that is, x ˉ i − v i y ˉ i ≥ 0 \bar{x}_i-v_i\bar{y}_i \ge0 x ˉ i − v i y ˉ i ≥ 0 . Feasibility requires that the builder fees be entirely funded only from the current batch’s available AMM output. Ex-post feasibility and concavity of F F F imply the following expected accounting constraint:
Fact 24 (Accounting constraint imposed by feasibility). For a possibly randomized AMM mechanism with a concave pricing curve that satisfies feasibility, the following accounting constraint must hold when there are only sell-Y Y Y bids.
∑ i x ˉ i ( v ~ ) + μ ˉ ( v ~ ) + β ˉ ( v ~ ) ≤ F ( Y ˉ ( v ~ ) ) . (34) \sum_i \bar{x}_i(\widetilde{\mathbf{v}}) + \bar{\mu}(\widetilde{\mathbf{v}}) + \bar{\beta}(\widetilde{\mathbf{v}}) \le F\bigl(\bar{Y}(\widetilde{\mathbf{v}})\bigr). \tag*{(34)} i ∑ x ˉ i ( v ) + μ ˉ ( v ) + β ˉ ( v ) ≤ F ( Y ˉ ( v ) ) . (34)
Proof. Feasibility requires that with probability 1, the compensation to all users, the builder’s fees, and the burnt amount are all fully funded by AMM pool’s output. Taking expectation, and applying Jensen’s inequality using the concavity of F F F , we immediately get the stated accounting constraint. □
Throughout, we assume that the mechanism is not aware which identities are owned by the builder.
Proof of Zero Builder Fee
Lemma 25 (Seller payment uniqueness). Fix a sell-Y Y Y user i i i and the reports of all other users. Let y ˉ i ( v ~ i ) \bar{y}_i(\tilde{v}_i) y ˉ i ( v ~ i ) be user i i i ’s expected amount of Y Y Y spent when it reports reservation value v ~ i \tilde{v}_i v ~ i . Suppose two expected compensation rules x ˉ i ( v ~ i ) \bar{x}_i(\tilde{v}_i) x ˉ i ( v ~ i ) and x ˉ i ′ ( v ~ i ) \bar{x}'_i(\tilde{v}_i) x ˉ i ′ ( v ~ i ) both make truthful reporting dominant for every true reservation value v i v_i v i , under utilities x ˉ i ( v ~ i ) − v i y ˉ i ( v ~ i ) \bar{x}_i(\tilde{v}_i)-v_i\bar{y}_i(\tilde{v}_i) x ˉ i ( v ~ i ) − v i y ˉ i ( v ~ i ) and x ˉ i ′ ( v ~ i ) − v i y ˉ i ( v ~ i ) \bar{x}'_i(\tilde{v}_i)-v_i\bar{y}_i(\tilde{v}_i) x ˉ i ′ ( v ~ i ) − v i y ˉ i ( v ~ i ) , respectively. Then x ˉ i ′ ( v ~ i ) − x ˉ i ( v ~ i ) \bar{x}'_i(\tilde{v}_i)-\bar{x}_i(\tilde{v}_i) x ˉ i ′ ( v ~ i ) − x ˉ i ( v ~ i ) is constant in v ~ i \tilde{v}_i v ~ i .
Proof. This is the seller form of the usual single-parameter payment-uniqueness lemma. Dominant-strategy truthfulness implies that y ˉ i ( v ~ i ) \bar{y}_i(\tilde{v}_i) y ˉ i ( v ~ i ) is nonincreasing in v ~ i \tilde{v}_i v ~ i . For the truthful compensation rule x ˉ i \bar{x}_i x ˉ i , the envelope identity [43 , 4 ] (i.e., the unique payment identity of Myerson’s lemma adapted to a seller or procurement setting) gives
x ˉ i ( v i ) − v i y ˉ i ( v i ) = x ˉ i ( 0 ) − ∫ 0 v i y ˉ i ( s ) d s . \bar{x}_i(v_i)-v_i\bar{y}_i(v_i)=\bar{x}_i(0)-\int_{0}^{v_i}\bar{y}_i(s)\,\mathrm{d}s. x ˉ i ( v i ) − v i y ˉ i ( v i ) = x ˉ i ( 0 ) − ∫ 0 v i y ˉ i ( s ) d s .
and hence
x ˉ i ( v i ) = v i y ˉ i ( v i ) + x ˉ i ( 0 ) − ∫ 0 v i y ˉ i ( s ) d s . \bar{x}_i(v_i)=v_i\bar{y}_i(v_i)+\bar{x}_i(0)-\int_{0}^{v_i}\bar{y}_i(s)\,\mathrm{d}s. x ˉ i ( v i ) = v i y ˉ i ( v i ) + x ˉ i ( 0 ) − ∫ 0 v i y ˉ i ( s ) d s .
The same identity holds for x ˉ i ′ \bar{x}'_i x ˉ i ′ with exactly the same spending rule y ˉ i \bar{y}_i y ˉ i . Subtracting the two identities yields
x ˉ i ′ ( v i ) − x ˉ i ( v i ) = x ˉ i ′ ( 0 ) − x ˉ i ( 0 ) , \bar{x}'_i(v_i)-\bar{x}_i(v_i)=\bar{x}'_i(0)-\bar{x}_i(0), x ˉ i ′ ( v i ) − x ˉ i ( v i ) = x ˉ i ′ ( 0 ) − x ˉ i ( 0 ) ,
which is independent of v i v_i v i . The argument applies to expected spending and expected compensation for a randomized mechanism.
Theorem 26 (Zero builder fees). Let F : [ 0 , + ∞ ) → R ≥ 0 F : [0,+\infty) \to\mathbb{R}_{\ge0} F : [ 0 , + ∞ ) → R ≥ 0 be continuous, strictly increasing, and concave, with F ( 0 ) = 0 F(0)=0 F ( 0 ) = 0 , and let σ 0 = F + ′ ( 0 ) ∈ ( 0 , + ∞ ) \sigma_0=F'_+(0)\in(0,+\infty) σ 0 = F + ′ ( 0 ) ∈ ( 0 , + ∞ ) . Consider any possibly randomized mechanism that satisfies individual rationality, feasibility, UIC, and strategy-proofness for a builder-as-user. Then, for every report profile v ~ \tilde{\mathbf{v}} v ~ ,
μ ˉ ( v ~ ) = 0. (35) \bar{\mu}(\tilde{\mathbf{v}})=0. \tag*{(35)} μ ˉ ( v ~ ) = 0. (35) In particular, because the builder fee is nonnegative, zero expectation implies that it is zero with probability 1.
As mentioned, this impossibility uses only sell-Y Y Y profiles and only deviations that misreport one’s valuation. Thus the impossibility continues to hold when allowing profiles in both directions and a broader strategy space, e.g., when users and builders can misreport both their valuation and budget, and when a builder may additionally censor or reorder bids or inject sybil orders.
Proof. (of Theorem 26 .) Fix a user identity i i i and all reports v ~ − i \tilde{\mathbf{v}}_{-i} v ~ − i . For a possible report v ~ i \tilde{v}_i v ~ i of identity i i i , abbreviate y ˉ i ( v ~ − i , v ~ i ) \bar{y}_i(\tilde{\mathbf{v}}_{-i},\tilde{v}_i) y ˉ i ( v ~ − i , v ~ i ) , x ˉ i ( v ~ − i , v ~ i ) \bar{x}_i(\tilde{\mathbf{v}}_{-i},\tilde{v}_i) x ˉ i ( v ~ − i , v ~ i ) , and μ ˉ ( v ~ − i , v ~ i ) \bar{\mu}(\tilde{\mathbf{v}}_{-i},\tilde{v}_i) μ ˉ ( v ~ − i , v ~ i ) by y ˉ i ( v ~ i ) \bar{y}_i(\tilde{v}_i) y ˉ i ( v ~ i ) , x ˉ i ( v ~ i ) \bar{x}_i(\tilde{v}_i) x ˉ i ( v ~ i ) , and μ ˉ ( v ~ i ) \bar{\mu}(\tilde{v}_i) μ ˉ ( v ~ i ) , respectively. By user incentive compatibility, x ˉ i ( v ~ i ) \bar{x}_i(\tilde{v}_i) x ˉ i ( v ~ i ) is a truthful seller compensation rule for spending rule y ˉ i ( v ~ i ) \bar{y}_i(\tilde{v}_i) y ˉ i ( v ~ i ) . Now consider the same numerical bid profile in the admissible role assignment in which identity i i i belongs to the block builder. Strategy-proofness for a builder-as-user says that
x ˉ i ( v ~ i ) + μ ˉ ( v ~ i ) \bar{x}_i(\tilde{v}_i)+\bar{\mu}(\tilde{v}_i) x ˉ i ( v ~ i ) + μ ˉ ( v ~ i )
is also a truthful seller compensation rule for the same spending rule y ˉ i ( v ~ i ) \bar{y}_i(\tilde{v}_i) y ˉ i ( v ~ i ) , because the builder’s total utility from this restricted deviation is
x ˉ i ( v ~ i ) + μ ˉ ( v ~ i ) − v i y ˉ i ( v ~ i ) . \bar{x}_i(\tilde{v}_i)+\bar{\mu}(\tilde{v}_i)-v_i\bar{y}_i(\tilde{v}_i). x ˉ i ( v ~ i ) + μ ˉ ( v ~ i ) − v i y ˉ i ( v ~ i ) .
Lemma 25 therefore implies that
μ ˉ ( v ~ i ) is independent of v ~ i when v ~ − i is fixed. (36) \bar{\mu}(\tilde{v}_i) \text{ is independent of } \tilde{v}_i \text{ when } \tilde{v}_{-i} \text{ is fixed.} \tag*{(36)} μ ˉ ( v ~ i ) is independent of v ~ i when v ~ − i is fixed. (36)
Since strategy-proofness for a builder-as-user applies no matter which identity is builder-owned, (36) holds for every coordinate. Thus expected builder revenue is invariant under changing the bids one coordinate at a time. For every finite profile v ~ \tilde{\mathbf{v}} v ~ ,
μ ˉ ( v ~ ) = μ ˉ ( σ 0 , … , σ 0 ) . (37) \bar{\mu}(\tilde{\mathbf{v}})=\bar{\mu}(\sigma_0,\ldots,\sigma_0). \tag*{(37)} μ ˉ ( v ~ ) = μ ˉ ( σ 0 , … , σ 0 ) . (37)
It remains to evaluate the anchor profile in which every user’s true reservation value and truthful report equal σ 0 \sigma_0 σ 0 . User individual rationality gives, for every i i i ,
x ˉ i ≥ σ 0 y ˉ i . \bar{x}_i \ge\sigma_0\bar{y}_i. x ˉ i ≥ σ 0 y ˉ i .
Summing and writing Y ˉ = ∑ i y ˉ i \bar{Y}=\sum_i\bar{y}_i Y ˉ = ∑ i y ˉ i ,
∑ i x ˉ i ≥ σ 0 Y ˉ . (38) \sum_i\bar{x}_i \ge\sigma_0\bar{Y}. \tag*{(38)} i ∑ x ˉ i ≥ σ 0 Y ˉ . (38)
Concavity, F ( 0 ) = 0 F(0)=0 F ( 0 ) = 0 , and F + ′ ( 0 ) = σ 0 F'_+(0)=\sigma_0 F + ′ ( 0 ) = σ 0 imply the global tangent bound
F ( y ) ≤ σ 0 y for every y ≥ 0. (39) F(y)\le\sigma_0 y \qquad\text{for every } y\ge0. \tag*{(39)} F ( y ) ≤ σ 0 y for every y ≥ 0. (39)
Using the funding constraint (34) and (38) –(39) ,
σ 0 Y ˉ + μ ˉ + β ˉ ≤ ∑ i x ˉ i + μ ˉ + β ˉ ≤ F ( Y ˉ ) ≤ σ 0 Y ˉ . \begin{aligned}
\sigma_0\bar{Y}+\bar{\mu}+\bar{\beta}
&\le\sum_i\bar{x}_i+\bar{\mu}+\bar{\beta}\\
&\le F(\bar{Y})\\
&\le\sigma_0\bar{Y}.
\end{aligned} σ 0 Y ˉ + μ ˉ + β ˉ ≤ i ∑ x ˉ i + μ ˉ + β ˉ ≤ F ( Y ˉ ) ≤ σ 0 Y ˉ .
Hence
μ ˉ + β ˉ ≤ 0. \bar{\mu}+\bar{\beta}\le0. μ ˉ + β ˉ ≤ 0.
Both quantities are nonnegative, so in particular
μ ˉ ( σ 0 , … , σ 0 ) = 0. \bar{\mu}(\sigma_0,\ldots,\sigma_0)=0. μ ˉ ( σ 0 , … , σ 0 ) = 0.
Combining this with (37) proves (35) .
Impossibility with Censorship
For our feasibility result, we assume that the underlying consensus guarantees censorship resilience, and thus the ability to censor is excluded from the builder’s strategy space. In this section, we justify this assumption by proving an impossibility. We show that when the block size is finite and the block builder may censor bids, no AMM mechanism can simultaneously satisfy individual rationality, feasibility, UIC, as well as strategy-proofness for a builder who is simultaneously a user with intrinsic demand. Further, this impossibility holds even for randomized mechanisms. The proofs in this section are inspired by the transaction fee mechanism literature, e.g., see Corollary 4.9 of Chung and Shi [19 ] .
A finite block model allowing censorship. More specifically, let k k k denote the finite block size. The builder is tasked with selecting up to k k k bids from among all outstanding bids and including them in the block in some prescribed order. Then, some trusted on-chain rule makes allocation and compensation decisions based on the included bids and their relative ordering.
A strategic builder-as-user may observe the other users’ bids and then strategically choose which bids to include and how to sequence them. In particular, it may omit any pending bids and may inject and include bids associated with its own sybil identities.
The strategy space of a strategic user remains the same as before. As in § 7 , we assume that the mechanism is unaware which user identities are owned by the builder.
Anonymity. We assume that the AMM mechanism is anonymous: its on-chain rules make allocation and payment decisions based solely on the valuations and budgets reported in the bids, as well as their relative ordering within the block. Any identity-related information (e.g., public keys) is ignored. This anonymity assumption is both desirable and satisfied by real-world AMMs, as well as by the mechanisms proposed in this paper. In particular, anonymity is consistent with the core decentralization principles underlying modern blockchains.
Non-triviality. We call the mechanism non-trivial if there is some block S S S and an identity i ∈ S i \in S i ∈ S whose expected compensation is strictly positive: E [ x i ( S ) ] > 0 \mathbb{E}[x_i(S)] > 0 E [ x i ( S )] > 0 . The expectation is over all randomization of the mechanism.
Theorem 27 (Impossibility with censorship). Assume that the block size is finite. No non-trivial, anonymous AMM mechanism can simultaneously satisfy individual rationality, feasibility, UIC, and strategy-proofness for a builder-as-seller.
Proof. Suppose, toward a contradiction, that the mechanism is non-trivial. Then some block S S S , of size at most k k k , contains a bid j j j with positive expected compensation. Write
T : = E [ x j ( S ) ] > 0 , A : = E [ y j ( S ) ] , T := \mathbb{E}[x_j(S)] > 0, \qquad A := \mathbb{E}[y_j(S)], T := E [ x j ( S )] > 0 , A := E [ y j ( S )] ,
and let q ≥ 0 q \ge0 q ≥ 0 be the public quantity cap of that bid. If q > 0 q > 0 q > 0 , choose
0 < ε < T 2 q . 0 < \varepsilon< \frac{T}{2q}. 0 < ε < 2 q T .
If q = 0 q = 0 q = 0 , choose any ε > 0 \varepsilon> 0 ε > 0 ; the cost of every feasible allocation to an added identity is then zero.
Create many low-ask identities. Construct a pending-bid set containing all identities in S ∖ { j } S \setminus\{j\} S ∖ { j } and N N N additional identities, each with cap q q q , true reservation value ε \varepsilon ε , and truthful ask ε \varepsilon ε . Run the prescribed block-construction strategy on this pool. For each added identity i i i , let Util i \operatorname{Util}_i Util i denote its expected trading utility under truthful behavior; an omitted bid has allocation and compensation zero. Individual rationality gives Util i ≥ 0 \operatorname{Util}_i \ge0 Util i ≥ 0 .
One identity has small truthful utility. Finite block capacity bounds the added identities’ total compensation independently of their number. Indeed, if Q S Q_S Q S is the total budget of the bids in S ∖ { j } S \setminus\{j\} S ∖ { j } , a realized block contains at most k k k bids and hence has total budget at most Q S + k q Q_S + kq Q S + k q . Feasibility, nonnegative builder fee and burn, and monotonicity of F F F therefore give
∑ i = 1 N x i ≤ ∑ h i n c l u d e d x h ≤ F ( Q S + k q ) = : C . (40) \sum_{i=1}^{N} x_i \le\sum_{h\ \mathrm{included}} x_h \le F(Q_S+kq) =: C. \tag*{(40)} i = 1 ∑ N x i ≤ h included ∑ x h ≤ F ( Q S + k q ) =: C . (40)
Since each added identity has nonnegative cost,
∑ i = 1 N Util i = E [ ∑ i = 1 N ( x i − ε y i ) ] ≤ C . \sum_{i=1}^{N} \operatorname{Util}_i = \mathbb{E}\left[\sum_{i=1}^{N}(x_i-\varepsilon y_i)\right] \le C. i = 1 ∑ N Util i = E [ i = 1 ∑ N ( x i − ε y i ) ] ≤ C .
Consequently some identity i ∗ i^* i ∗ satisfies Util i ∗ ≤ C / N \operatorname{Util}_{i^*} \le C/N Util i ∗ ≤ C / N .
Censorship gives that identity a profitable deviation. Now imagine that the unlucky user i ∗ i^* i ∗ belongs to the builder. Its builder fee is zero with probability 1 by Theorem 26 , so the builder’s truthful utility is Util i ∗ \operatorname{Util}_{i^*} Util i ∗ . The builder can deviate by censoring the prescribed block, including S ∖ { j } S \setminus\{j\} S ∖ { j } together with i ∗ i^* i ∗ , and making i ∗ i^* i ∗ submit j j j ’s report. The on-chain rule then sees the same numerical block S S S , with i ∗ i^* i ∗ in place of j j j . Hence the deviation gives the builder expected utility
T − ε A ≥ T − ε q > T 2 , T-\varepsilon A \ge T-\varepsilon q > \frac{T}{2}, T − ε A ≥ T − εq > 2 T ,
again with zero builder fee. Taking N > 2 C / T N > 2C/T N > 2 C / T makes the truthful utility Util i ∗ ≤ C / N < T / 2 \operatorname{Util}_{i^*} \le C/N < T/2 Util i ∗ ≤ C / N < T /2 , contradicting builder-as-seller incentive compatibility. Therefore no block can give any seller positive expected compensation. □ \square □
Acknowledgements
Human intelligence was solely responsible for the new conceptual contributions including the proposal of this new paradigm. The main mechanism and some of its proofs were developed with assistance from ChatGPT 5.6. Other results were first proved with human intelligence and subsequently written up with assistance from ChatGPT 5.6 and Claude Fable 5. The authors carefully reviewed and substantially edited all AI-generated text.
Why Exclude Ineligible Users?
Recall that our Pareto optimality (PO) notion is required to hold only for eligible users whose asks are no higher than the initial spot price. We now explain why we do not aim to achieve efficiency for ineligible users. Specifically, we prove that the requirement of UIC precludes achieving PO for all users, including ineligible ones. Li, Shi, and Zhang [40 ] proved a similar impossibility but their setting requires that the mechanism’s outcome land on the pricing curve without burning (or redistribution) of the surplus. Therefore, their proof cannot be easily adapted to our setting where part of the surplus may be burnt. Our new argument below instead uses the information rents forced by UIC, i.e., the extra utility a user obtains because the mechanism must remain incentive compatible across different private reservation values.
Two-user scenario for the proof. It suffices to consider one sell-Y Y Y user i i i and one sell-X X X user j j j . In the notation of the model, user i i i supplies y i y_i y i units of Y Y Y and receives x i x_i x i units of X X X , while user j j j supplies x j x_j x j units of X X X and receives y j y_j y j units of Y Y Y . Feasibility without an outside subsidy means that there is a signed residual AMM input p p p and nonnegative surplus-disposal amounts B Y B_Y B Y , B X B_X B X such that
y i = y j + p + B Y , x j + F ( p ) = x i + B X . (41) y_i = y_j + p + B_Y,\qquad x_j + F(p) = x_i + B_X. \tag*{(41)} y i = y j + p + B Y , x j + F ( p ) = x i + B X . (41)
Here p p p units of Y Y Y are sent to the AMM and F ( p ) F(p) F ( p ) units of X X X are released. The amounts B Y B_Y B Y and B X B_X B X may be burned or redistributed outside the current batch. In particular, (41) only implies
y i ≥ y j + p , x i ≤ x j + F ( p ) , (42) y_i \ge y_j + p,\qquad x_i \le x_j + F(p), \tag*{(42)} y i ≥ y j + p , x i ≤ x j + F ( p ) , (42)
and does not require the aggregate user outcome itself to lie on the curve. As elsewhere in the paper, the same residual trade determines the final marginal prices
σ e : = F + ′ ( p ) , ρ e : = 1 σ e \sigma_e := F_+'(p),\qquad\rho_e := \frac{1}{\sigma_e} σ e := F + ′ ( p ) , ρ e := σ e 1
Theorem 28 (UIC precludes Pareto optimality for all users). Let F F F be the finite-reserve concave AMM pricing curve defined in § 2.2 . No deterministic AMM mechanism satisfying user individual rationality and the off-curve feasibility condition (41) can simultaneously satisfy user incentive compatibility (UIC) and Pareto optimality for all users, including ineligible users. In fact, the impossibility already holds for two users with fixed, publicly known budgets and with deviations restricted to reservation-value misreports.
Proof. Consider the two-user scenario mentioned above. Specifically, for each v ∈ [ v 0 , v 1 ) v \in[v_0,v_1) v ∈ [ v 0 , v 1 ) , consider a truthful sell-Y user of type ( v , Q ) (v,Q) ( v , Q ) and a truthful sell-X user of type ( u , R ) (u,R) ( u , R ) . Denote their respective allocations and compensations by
( x i ( v ) , y i ( v ) ) and ( x j ( v ) , y j ( v ) ) , \left(x_i(v),y_i(v)\right) \qquad\text{and} \qquad\left(x_j(v),y_j(v)\right), ( x i ( v ) , y i ( v ) ) and ( x j ( v ) , y j ( v ) ) ,
and denote the residual AMM input by p ( v ) p(v) p ( v ) . We next explain how we choose the parameters v 0 v_0 v 0 , v 1 v_1 v 1 , Q Q Q and R R R . Let
0 < v 0 < v 1 < σ 0 , δ : = 1 − v 0 v 1 > 0. 0 < v_0 < v_1 < \sigma_0,\qquad\delta:= 1-\frac{v_0}{v_1}>0. 0 < v 0 < v 1 < σ 0 , δ := 1 − v 1 v 0 > 0.
Define the maximum AMM surplus at per-unit cost v 0 v_0 v 0 by
Γ ( v 0 ) : = sup p ≥ 0 { F ( p ) − v 0 p } . (43) \Gamma(v_0):=\sup_{p\ge0}\{F(p)-v_0p\}. \tag*{(43)} Γ ( v 0 ) := p ≥ 0 sup { F ( p ) − v 0 p } . (43)
Because the pool has finite X X X reserves, F ( p ) < x 0 F(p)<x_0 F ( p ) < x 0 for every p ≥ 0 p\ge0 p ≥ 0 . Consequently Γ ( v 0 ) ≤ x 0 < ∞ \Gamma(v_0)\le x_0<\infty Γ ( v 0 ) ≤ x 0 < ∞ . Choose the sell-X budget R R R large enough that the eventual rent lower bound R δ R\delta R δ exceeds this maximum surplus, and then choose the sell-Y budget Q Q Q large enough that a full sell-Y allocation cannot be funded (to be shown later):
R > Γ ( v 0 ) δ , v 0 Q > R + F ( Q ) . R>\frac{\Gamma(v_0)}{\delta},\qquad v_0Q>R+F(Q). R > δ Γ ( v 0 ) , v 0 Q > R + F ( Q ) .
The second choice is possible by taking Q > ( R + x 0 ) / v 0 Q>(R+x_0)/v_0 Q > ( R + x 0 ) / v 0 . Finally, set
u : = 1 v 1 . u:=\frac{1}{v_1}. u := v 1 1 .
Since v 1 < σ 0 v_1<\sigma_0 v 1 < σ 0 , this choice gives u = 1 / v 1 > 1 / σ 0 = ρ 0 u=1/v_1>1/\sigma_0=\rho_0 u = 1/ v 1 > 1/ σ 0 = ρ 0 . Thus the sell-X user with valuation u u u is ineligible at the initial spot price. Requiring Pareto optimality for this user is precisely what will drive the contradiction.
Finite reserves force the sell-Y user to be underfilled. Suppose, towards a contradiction, that y i ( v ) = Q y_i(v)=Q y i ( v ) = Q . Individual rationality gives
x i ( v ) ≥ v Q ≥ v 0 Q . (44) x_i(v)\ge vQ\ge v_0Q. \tag*{(44)} x i ( v ) ≥ v Q ≥ v 0 Q . (44)
Individual rationality of the sell-X user also gives y j ( v ) ≥ u x j ( v ) ≥ 0 y_j(v)\ge ux_j(v)\ge0 y j ( v ) ≥ u x j ( v ) ≥ 0 . The first identity in (41) therefore implies p ( v ) ≤ y i ( v ) = Q p(v)\le y_i(v)=Q p ( v ) ≤ y i ( v ) = Q . Since x j ( v ) ≤ R x_j(v)\le R x j ( v ) ≤ R and F F F is increasing, the second accounting bound gives
x i ( v ) ≤ x j ( v ) + F ( p ( v ) ) ≤ R + F ( Q ) < v 0 Q , x_i(v)\le x_j(v)+F(p(v))\le R+F(Q)<v_0Q, x i ( v ) ≤ x j ( v ) + F ( p ( v )) ≤ R + F ( Q ) < v 0 Q ,
contradicting (44) . Consequently,
y i ( v ) < Q . y_i(v)<Q. y i ( v ) < Q .
Pareto optimality fully executes the sell-X order. Because the sell-Y user is underfilled, it could profitably sell an additional amount directly to the pool if σ e > v \sigma_e > v σ e > v . Pareto optimality for all users rules this out, and hence
F + ′ ( p ( v ) ) = σ e ≤ v < σ 0 . F_+'(p(v)) = \sigma_e \le v < \sigma_0. F + ′ ( p ( v )) = σ e ≤ v < σ 0 .
Concavity and differentiability at zero imply F + ′ ( p ) ≥ F + ′ ( 0 ) = σ 0 F_+'(p) \ge F_+'(0) = \sigma_0 F + ′ ( p ) ≥ F + ′ ( 0 ) = σ 0 whenever p ≤ 0 p \le0 p ≤ 0 . Hence
p ( v ) > 0. (45) p(v) > 0. \tag*{(45)} p ( v ) > 0. (45)
Moreover,
ρ e = 1 F + ′ ( p ( v ) ) ≥ 1 v > 1 v 1 = u . \rho_e = \frac{1}{F_+'(p(v))} \ge\frac{1}{v} > \frac{1}{v_1} = u. ρ e = F + ′ ( p ( v )) 1 ≥ v 1 > v 1 1 = u .
Thus underfilling the sell-Y Y Y user pushes the marginal compensation in the reverse direction above the sell-X X X user’s ask. If the sell-X X X user were underfilled, the strict inequality ρ e > u \rho_e > u ρ e > u would likewise give it a profitable additional trade with the pool, contrary to Pareto optimality for all users. Therefore
x j ( v ) = R . (46) x_j(v) = R. \tag*{(46)} x j ( v ) = R . (46)
UIC forces a large sell-X compensation. Fix v v v and vary only the sell-X user’s true and reported ask a a a over 0 ≤ a < 1 / v 0 \le a < 1/v 0 ≤ a < 1/ v , while keeping its budget equal to R R R . The preceding underfilling argument does not depend on the numerical sell-X ask. For every such a a a , the same pool-trade condition therefore forces its allocation to equal R R R .
Let y j ( a ) y_j(a) y j ( a ) be its compensation. For any a , b < 1 / v a,b < 1/v a , b < 1/ v , the two pairwise UIC inequalities are
y j ( a ) − a R ≥ y j ( b ) − a R , y j ( b ) − b R ≥ y j ( a ) − b R . y_j(a) - aR \ge y_j(b) - aR,\qquad y_j(b) - bR \ge y_j(a) - bR. y j ( a ) − a R ≥ y j ( b ) − a R , y j ( b ) − b R ≥ y j ( a ) − b R .
Because every ask in this interval receives the same full allocation, these inequalities force the compensation to be constant: y j ( a ) = y j ( b ) y_j(a) = y_j(b) y j ( a ) = y j ( b ) . Individual rationality gives y j ( a ) ≥ a R y_j(a) \ge aR y j ( a ) ≥ a R for every a < 1 / v a < 1/v a < 1/ v ; taking a ↑ 1 / v a \uparrow1/v a ↑ 1/ v shows that this constant is at least R / v R/v R / v . Since the actual ask u = 1 / v 1 u = 1/v_1 u = 1/ v 1 lies in the interval, we obtain
y j ( v ) ≥ R v . (47) y_j(v) \ge\frac{R}{v}. \tag*{(47)} y j ( v ) ≥ v R . (47)
Intuitively, the sell-X X X user must receive at least R / v R/v R / v units of Y Y Y . Those units, together with the positive residual input p ( v ) p(v) p ( v ) sent to the pool, must be supplied by the sell-Y Y Y user. Accordingly, combining (42) , (45) , and (47) gives
y i ( v ) ≥ y j ( v ) + p ( v ) ≥ R v + p ( v ) . (48) y_i(v) \ge y_j(v) + p(v) \ge\frac{R}{v} + p(v). \tag*{(48)} y i ( v ) ≥ y j ( v ) + p ( v ) ≥ v R + p ( v ) . (48)
UIC forces a large sell-Y information rent. Let
U ( v ) : = x i ( v ) − v y i ( v ) U(v) := x_i(v) - vy_i(v) U ( v ) := x i ( v ) − v y i ( v )
be the sell-Y Y Y user’s truthful utility. UIC for a user of true type ( v 0 , Q ) (v_0,Q) ( v 0 , Q ) , comparing truthful reporting with the report ( v , Q ) (v,Q) ( v , Q ) , implies
U ( v 0 ) ≥ x i ( v ) − v 0 y i ( v ) = U ( v ) + ( v − v 0 ) y i ( v ) . U(v_0) \ge x_i(v) - v_0y_i(v)
= U(v) + (v-v_0)y_i(v). U ( v 0 ) ≥ x i ( v ) − v 0 y i ( v ) = U ( v ) + ( v − v 0 ) y i ( v ) .
The low-cost type v 0 v_0 v 0 can mimic type v v v . UIC therefore requires it to retain the cost advantage ( v − v 0 ) y i ( v ) (v-v_0)y_i(v) ( v − v 0 ) y i ( v ) as information rent. Individual rationality gives U ( v ) ≥ 0 U(v) \ge0 U ( v ) ≥ 0 , while (48) gives y i ( v ) ≥ R / v y_i(v) \ge R/v y i ( v ) ≥ R / v . Hence, for every v ∈ ( v 0 , v 1 ) v \in(v_0,v_1) v ∈ ( v 0 , v 1 ) ,
U ( v 0 ) ≥ R ( 1 − v 0 v ) . U(v_0) \ge R\left(1-\frac{v_0}{v}\right). U ( v 0 ) ≥ R ( 1 − v v 0 ) .
Taking the supremum as v ↑ v 1 v \uparrow v_1 v ↑ v 1 yields
U ( v 0 ) ≥ R δ . (49) U(v_0) \ge R\delta. \tag*{(49)} U ( v 0 ) ≥ R δ . (49)
The forced rent exceeds the AMM’s available surplus. Write p 0 : = p ( v 0 ) p_0 := p(v_0) p 0 := p ( v 0 ) and similarly use a subscript 0 for the other outcomes at v 0 v_0 v 0 . From (48) and (49) ,
x i , 0 = v 0 y i , 0 + U ( v 0 ) ≥ v 0 ( R v 0 + p 0 ) + R δ = R + v 0 p 0 + R δ . \begin{aligned}
x_{i,0}=v_0y_{i,0}+U(v_0) \\
&\ge v_0\left(\frac{R}{v_0}+p_0\right)+R\delta\\
&=R+v_0p_0+R\delta.
\end{aligned} x i , 0 = v 0 y i , 0 + U ( v 0 ) ≥ v 0 ( v 0 R + p 0 ) + R δ = R + v 0 p 0 + R δ .
On the other hand, (46) and off-curve feasibility imply
x i , 0 ≤ R + F ( p 0 ) . x_{i,0}\le R+F(p_0). x i , 0 ≤ R + F ( p 0 ) .
The lower bound includes the sell-Y Y Y user’s production cost and its forced information rent, whereas the upper bound is all the X X X available from the sell-X X X user and the AMM. Combining them gives
F ( p 0 ) − v 0 p 0 ≥ R δ > Γ ( v 0 ) , F(p_0)-v_0p_0\ge R\delta>\Gamma(v_0), F ( p 0 ) − v 0 p 0 ≥ R δ > Γ ( v 0 ) ,
whereas p 0 > 0 p_0>0 p 0 > 0 by (45) . This contradicts the definition of Γ ( v 0 ) \Gamma(v_0) Γ ( v 0 ) in (43) . The argument used only single-identity reservation-value UIC with fixed budgets, which is a restriction of the full UIC requirement. The claimed impossibility follows.
Remark 29 (The proof only needs local efficiency). The proof does not use the part of Pareto optimality that rules out Pareto improvements through trades among users. It uses only the requirement that no user can trade directly with the pool to obtain a Pareto improvement. This weaker condition is called local efficiency (LE) [40 ] . If σ e \sigma_e σ e and ρ e = 1 / σ e \rho_e=1/\sigma_e ρ e = 1/ σ e are the final marginal compensation rates, LE requires the following to hold for all users i i i :
y i < q ~ i ⟹ v ~ i ≥ σ e , x j < r ~ j ⟹ u ~ j ≥ ρ e . y_i<\tilde{q}_i \Longrightarrow\tilde{v}_i\ge\sigma_e,\qquad x_j<\tilde{r}_j \Longrightarrow\tilde{u}_j\ge\rho_e. y i < q ~ i ⟹ v ~ i ≥ σ e , x j < r ~ j ⟹ u ~ j ≥ ρ e .
Thus the theorem remains true if Pareto optimality for all users is replaced by LE: UIC is incompatible even with this weaker efficiency requirement.
Necessity of Surplus Redistribution
We now show that surplus burning is essential: without it, no AMM mechanism can simultaneously provide the full set of guarantees achieved by our mechanism—UIC, strategy-proofness for a builder with or without intrinsic demand, and Pareto optimality for eligible users. We stress, however, surplus redistribution is more than a technical device for circumventing this impossibility. As discussed in § 1 , it offers a compelling new paradigm for provably eliminating MEV in two-asset AMM contracts while substantially reducing the negative externalities of today’s highly centralized builder ecosystem [YNZ25].
Li, Shi, and Zhang [40 ] showed that, when surplus burning is prohibited, UIC and Pareto optimality (PO) for all users cannot be achieved simultaneously. However, as shown in Section A, requiring PO for all users is too stringent: the impossibility persists even when surplus burning is allowed. Our goal here is instead to establish the necessity of surplus burning even under the weaker requirement of PO for eligible users only. This distinction calls for a different proof argument described below.
For a concave function, write F − ′ ( z ) F'_{-}(z) F − ′ ( z ) and F + ′ ( z ) F'_{+}(z) F + ′ ( z ) for its left and right derivatives. Both exist at every interior point, and
s < t ⟹ F − ′ ( t ) ≤ F + ′ ( s ) . (50) s < t \implies F'_{-}(t) \le F'_{+}(s). \tag*{(50)} s < t ⟹ F − ′ ( t ) ≤ F + ′ ( s ) . (50)
Theorem 30 (Zero burn is impossible). Let F F F satisfy assumptions (A1)–(A4) of § 2.2 . Suppose that a truthful zero-budget user must receive zero utility, then no deterministic AMM mechanism can simultaneously satisfy individual rationality, feasibility with zero burn, UIC, strategy-proofness for a builder-as-user, and Pareto optimality for eligible bids.
Here zero-burn feasibility means exact token accounting: every token made available by opposite-side orders and the residual AMM trade is paid either to users or to the builder, and the burn amount must be zero.
Proof. Suppose, toward a contradiction, that such a mechanism exists. We use only sell-Y Y Y profiles. The key tension is between marginal and average compensation: Pareto optimality determines who trades by comparing asks with the pool’s marginal compensation, whereas zero burn can force a sole trading user to receive the pool’s entire output. We will exploit the gap between these two rates to make an otherwise excluded user profit by understating its valuation.
By Theorem 26 , strategy-proofness for a builder-as-user, together with IR, feasibility, and UIC, forces the builder fee to be zero on every profile. Since the burn is also zero, a sell-Y Y Y -only outcome with total input Y : = ∑ i y i Y := \sum_i y_i Y := ∑ i y i satisfies the exact accounting identity
∑ i x i = F ( Y ) . (51) \sum_i x_i = F(Y). \tag*{(51)} i ∑ x i = F ( Y ) . (51)
Due to Theorem 10, we have the following:
y i = 0 ⟹ x i = 0 on a sell- Y -only profile . (52) y_i = 0 \implies x_i = 0 \quad\text{on a sell-}Y\text{-only profile}. \tag*{(52)} y i = 0 ⟹ x i = 0 on a sell- Y -only profile . (52)
We first record the allocation restrictions imposed by Pareto optimality: cheaper supply must be used first, and users must have no profitable way to increase or unwind their pool trades. Consider a truthful sell-Y Y Y -only profile consisting of eligible users and put Y = ∑ i y i Y = \sum_i y_i Y = ∑ i y i .
First, if users i i i and j j j have asks v i < v j v_i < v_j v i < v j , and j j j sells a positive amount, then i i i must exhaust its cap. Otherwise, for a sufficiently small ε > 0 \varepsilon> 0 ε > 0 , user i i i can give ε \varepsilon ε units of Y Y Y to user j j j in exchange for r ε r\varepsilon r ε units of X X X , where v i < r < v j v_i < r < v_j v i < r < v j . Choose ε \varepsilon ε small enough that user j j j returns no more than the X X X and Y Y Y involved in its original trade. User i i i ’s utility rises by ( r − v i ) ε (r-v_i)\varepsilon ( r − v i ) ε , and user j j j ’s utility rises by ( v j − r ) ε (v_j-r)\varepsilon ( v j − r ) ε . The pool position and every other user’s outcome are unchanged. This is a Pareto improvement among eligible users. Therefore
v i < v j , y j > 0 ⟹ y i = q i . (53) v_i < v_j,\ y_j > 0 \implies y_i = q_i. \tag*{(53)} v i < v j , y j > 0 ⟹ y i = q i . (53)
Second, any user who sells a positive amount must have ask at most the final left marginal compensation:
y i > 0 ⟹ v i ≤ F − ′ ( Y ) . (54) y_i > 0 \implies v_i \le F'_{-}(Y). \tag*{(54)} y i > 0 ⟹ v i ≤ F − ′ ( Y ) . (54)
Indeed, if v i > F − ′ ( Y ) v_i > F'_-(Y) v i > F − ′ ( Y ) , the user can unwind a sufficiently small amount ϵ \epsilon ϵ of its trade. It returns F ( Y ) − F ( Y − ϵ ) F(Y)-F(Y-\epsilon) F ( Y ) − F ( Y − ϵ ) units of X X X and recovers ϵ \epsilon ϵ units of Y Y Y , increasing its utility by
v i ϵ − ( F ( Y ) − F ( Y − ϵ ) ) > 0. v_i\epsilon-\left(F(Y)-F(Y-\epsilon)\right)>0. v i ϵ − ( F ( Y ) − F ( Y − ϵ ) ) > 0.
Exact accounting is preserved and, for small enough ϵ \epsilon ϵ , the user’s net trade remains in its declared direction. Conversely, an underfilled user must satisfy
y i < q i ⟹ v i ≥ F + ′ ( Y ) , (55) y_i<q_i \quad\Longrightarrow\quad v_i\ge F'_+(Y), \tag*{(55)} y i < q i ⟹ v i ≥ F + ′ ( Y ) , (55)
because otherwise it could sell a sufficiently small additional amount directly to the pool and receive F ( Y + ϵ ) − F ( Y ) F(Y+\epsilon)-F(Y) F ( Y + ϵ ) − F ( Y ) units of X X X .
We now choose the witness types using a strict gap between the marginal compensation at input Q Q Q and the average compensation over the whole trade. There exists Q > 0 Q>0 Q > 0 such that
σ : = F + ′ ( Q ) < F ( Q ) Q . \sigma:=F'_+(Q)<\frac{F(Q)}{Q}. σ := F + ′ ( Q ) < Q F ( Q ) .
To see this, concavity and F ( 0 ) = 0 F(0)=0 F ( 0 ) = 0 always give F + ′ ( Q ) ≤ F ( Q ) / Q F'_+(Q)\le F(Q)/Q F + ′ ( Q ) ≤ F ( Q ) / Q . If equality held for every Q > 0 Q>0 Q > 0 , F F F would be linear with its positive initial slope on [ 0 , + ∞ ) [0,+\infty) [ 0 , + ∞ ) , contradicting the finite upper reserve bound F ( Q ) < x 0 F(Q)<x_0 F ( Q ) < x 0 . Moreover, σ > 0 \sigma>0 σ > 0 : if the right derivative of a concave increasing function vanished at a finite point, the function would be constant thereafter, contrary to strict increasingness.
Choose numbers
0 < v ∗ < σ < v 1 < v 2 < F ( Q ) Q . (56) 0<v^*<\sigma<v_1<v_2<\frac{F(Q)}{Q}. \tag*{(56)} 0 < v ∗ < σ < v 1 < v 2 < Q F ( Q ) . (56)
All three asks are strictly eligible, since concavity gives F ( Q ) / Q ≤ F + ′ ( 0 ) = σ 0 F(Q)/Q\le F'_+(0)=\sigma_0 F ( Q ) / Q ≤ F + ′ ( 0 ) = σ 0 . Consider two users, each with cap Q Q Q : the first user’s true valuation is v 1 v_1 v 1 , and the second user’s true valuation is v 2 v_2 v 2 . Write ( 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 ) for their respective compensations and allocations at the profile under consideration. The second user’s valuation exceeds the marginal compensation σ \sigma σ , but is below the average compensation F ( Q ) / Q F(Q)/Q F ( Q ) / Q . Thus supplying the whole amount Q Q Q would give it positive utility if it received all of F ( Q ) F(Q) F ( Q ) , even though supplying additional units beyond Q Q Q would not be worthwhile at the margin. The ask v ∗ < σ v^*<\sigma v ∗ < σ will be its dishonest report.
We first show that the second user sells zero under truthful reports: the cheaper first user prevents it from obtaining any allocation. If y 2 > 0 y_2>0 y 2 > 0 , then (53) forces y 1 = Q y_1=Q y 1 = Q . Hence the total input satisfies Y > Q Y>Q Y > Q , and (50) and (54) give
v 2 ≤ F − ′ ( Y ) ≤ F + ′ ( Q ) = σ , v_2\le F'_-(Y)\le F'_+(Q)=\sigma, v 2 ≤ F − ′ ( Y ) ≤ F + ′ ( Q ) = σ ,
contrary to v 2 > σ v_2>\sigma v 2 > σ . Thus y 2 = 0 y_2=0 y 2 = 0 , and (52) gives x 2 = 0 x_2=0 x 2 = 0 . The second user’s truthful utility is therefore zero.
Now let the second user deviate only by reporting ask v ∗ v^* v ∗ , keeping its cap equal to Q Q Q . This reverses the priority: the second user now appears cheaper and, as we show next, becomes the sole supplier. The numerical profile ( v 1 , v ∗ ) (v_1,v^*) ( v 1 , v ∗ ) can equally be viewed as a truthful profile, so Pareto optimality applies to its outcome with respect to these reported valuations. If y 1 > 0 y_1>0 y 1 > 0 , priority (53) forces y 2 = Q y_2=Q y 2 = Q . Then Y > Q Y>Q Y > Q , and the executed first user would have to satisfy
v 1 ≤ F − ′ ( Y ) ≤ F + ′ ( Q ) = σ , v_1\le F'_-(Y)\le F'_+(Q)=\sigma, v 1 ≤ F − ′ ( Y ) ≤ F + ′ ( Q ) = σ ,
again a contradiction. Hence y 1 = 0 y_1=0 y 1 = 0 , and (52) gives x 1 = 0 x_1=0 x 1 = 0 .
Finally, the second user must sell its full cap under the deviation. Otherwise Y = y 2 < Q Y = y_2 < Q Y = y 2 < Q , while concavity gives
F ′ ( Y ) ≥ F ′ ( Q ) = σ > v ∗ , F^{\prime}(Y) \ge F^{\prime}(Q) = \sigma> v^*, F ′ ( Y ) ≥ F ′ ( Q ) = σ > v ∗ ,
contradicting the underfilled condition (55) . Therefore y 2 = Q y_2 = Q y 2 = Q . At this point, zero burn is decisive: the builder receives no fee, and the inactive first user receives nothing, so the entire AMM output must go to the second user. Exact accounting (51) forces
x 2 = F ( Q ) . x_2 = F(Q). x 2 = F ( Q ) .
Evaluated at its true valuation v 2 v_2 v 2 , rather than its report v ∗ v^* v ∗ , the second user’s deviating utility is
F ( Q ) − v 2 Q > 0 F(Q) - v_2Q > 0 F ( Q ) − v 2 Q > 0
by (56) , whereas its truthful utility was zero. This contradicts UIC. All reports used in the argument have the same fixed cap, and every ask used in a Pareto comparison is strictly eligible. The claimed impossibility follows.
Remark 31. If builder fees are prohibited, then the impossibility in Theorem 30 holds without assuming strategy-proofness for a builder-as-user. Indeed, the proof uses builder-as-user strategy-proofness only to invoke the zero-builder-fee theorem (Theorem 26 ), which is unnecessary when zero builder fees are imposed by assumption.