Mechanism Design for Automated Market Makers

Applying the philosophy of mechanism design at the application layer, we want to design an AMM mechanism that removes MEV opportunities and provides strategy proofness by construction.

We devise a new AMM mechanism (to be executed as a smart contract on chain) with the following abstraction. In our mechanism, the pool holds two crypto-assets $X$ and $Y$. A user can trade with the pool by posting a buy/sell order specifying how much of $X$ (or $Y$) they want to buy/sell, and their worst acceptable exchange rate. When a new block arrives, the mechanism takes the block of orders as input, and applies an allocation rule to all orders contained within the block. The allocation rule decides which orders are partially or completely satisfied, and at what price. The mechanism maintains the following invariant: the pool’s beginning state denoted $\mathrm{𝖯𝗈𝗈𝗅}(x_0,y_0)$ and end state $\mathrm{𝖯𝗈𝗈𝗅}(x_1,y_1)$ is guaranteed to satisfy some “natural” potential function $\mathrm{\Phi }$ (e.g., the constant-product function mentioned above).

Our mechanism offers two tiers of guarantees depending on whether the properties of the underlying consensus. Specifically, we consider two models: 1) the plain model, capturing today’s mainstream consensus protocols where for any particular block, the inclusion and sequencing of transactions are determined by a single, possibly strategic block producer; and 2) the weak fair-sequencing model, intended to capture a new generation of consensus protocols that offer sequencing fairness guarantees [2, 10, 36, 34, 35], e.g., through a decentralized sequencer. Our mechanism achieves the following desirable, two-tier properties:

1. 1.

   Arbitrage free in the plain model. We guarantee that no arbitrager (e.g., user, block producer, or any intermediary) can gain risk-free profit, even when the arbitrager (e.g., block producer) has unilateral control over the block contents and transaction sequencing. Here, risk-free profit happens when an arbitrager can gain in one asset without losing in another with probability $1$.

2. 2.

   Strategy proofness in the weak fair-sequencing model. In the weak fair-sequencing model, our mechanism not only achieves arbitrage resilience, but also guarantees strategy proofness. Specifically, strategy proofness means that users are incentivized to report their true demand and true belief of the relative value of the two crypto-assets, and no strategic behavior allows a user to gain. Later, we prove that strategy proofness is a strictly stronger notion than arbitrage resilience (Fact 1).

Our weak fair-sequencing model is meant to capture a decentralized sequencer that sequences the orders based on their arrival times (importantly, not based on the orders’ submission time). While this model places additional constraints on the strategy space in comparison with the plain model, it does not prevent front-running and thus does not trivialize the mechanism design problem. Notably, in this model, a strategic user or miner can still wait for a victim to submit its order, and then immediately submit a dependent order. The strategic order can even front-run the victim’s order if the strategic user’s network is faster, similar to a rushing attack in the cryptography literature [20, 19].

Our work is also among the first to formally articulate, from a mechanism designer’s perspective, how extra properties at the consensus level lend to the design of strategy-proof mechanisms at the smart contract layer.

We put forth new modeling and definitions, which capture a mechanism design problem of a decentralized nature. In comparison with the classical mechanism design literature, our model and strategy spaces capture the “permissionless” nature of blockchains. Specifically, a strategic player may not only report its valuation/demand untruthfully, but also inject fake orders or post multiple orders. Such strategies are possible because the mechanism does not have a-priori knowledge of the number or the identities of the bidders. Compared to closely related works, our model circumvents the strong impossibilities shown by Ferreira and Parkes [30], because we relax some unrealistic restrictions they impose – see Section 1.2 for more details. Therefore, we believe that our model is better suited for capturing real-world mechanism design at the smart contract layer, particularly for AMMs. Our new model and definitions naturally give rise to many interesting open questions which we discuss in Section 1.3.

Ferreira and Parkes [30] showed that in an overly pessimistic model as explained below, achieving arbitrage resilience is impossible, let alone strategy proofness. However, their impossibility result holds only in an overly stringent model that does not reflect the real-life design space. Specifically, when interpreted in our new framework, their impossibility holds only if the AMM mechanism has to respect the following specific structure: sort the incoming orders according to some rules (called “verifiable sequencing rules” in their paper), and run a legacy AMM contract that processes the sorted orders sequentially, such that the constant potential function must be maintained after executing each order. In comparison, in our model, the constant potential function only needs to be maintained at the end of processing the entire batch. Because of their strong impossibility result, Ferreira and Parkes [30] showed how to achieve a weaker guarantee in their model, that is, if the miner made risk-free profit, then the user should enjoy a price that is at least as good as if its order were the only one in the block.

Li et al. [39] inherit the same model as Ferreira and Parkes [30], and they study what is the profit-maximizing strategy for the miner and the implications for the users when the miner adopts the optimal strategy. Like Ferreira and Parkes [30], they adopt an overly restrictive model which requires them to give up on achieving arbitrage resilience, let alone strategy proofness.

One of the contributions we make is exactly to recognize why the existing models are too stringent and unrealistic, and suggest a better model for the study of MEV-resilient mechanism design.

A line of works explored the idea of batch clearing at uniform price. We stress that batch clearing at uniform price [21, 22, 1] does not automatically guarantee strategy proofness. For example, suppose there are many eligible orders and the mechanism can clear only a subset of them. If the mechanism selects the subset based on the declared valuation, then a strategic user can lie about its valuation to get selected.

The concurrent and independent work of Canidio and Fritsch [21, 22] suggested batch-clearing at a uniform price and using a different potential function than Uniswap’s constant-product function. Their approach satisfies arbitrage resilience, but it does not satisfy strategy proofness even when the miner is trusted to behave honestly, for the reason stated above. In fact, Canidio and Fritsch [21, 22] does not even fully specify which subset of orders to clear when there are many eligible candidates. The work of Zhang et al. [48] also observed that batch clearing alone does not imply strategy proofness. In fact, they investigated the optimal strategy under batch clearing. The prior work of Ramseyer et al. [43] also considered batch exchanges that clear at a uniform price. Like Canidio and Fritsch [21, 22], their work does not provide strategy proofness, even when the miner is fully trusted. Besides batch trading at uniform pricing, other forms of batch trading [23] have also been considered, but they also do not satisfy our notion of strategy proofness.

Milionis, Moallemi, and Roughgarden [40] consider how to design the demand curve for a market maker to maximize profit and meanwhile incentivize truthful reporting. Their work is of a completely different nature than ours, since they do not aim to address the problem of MEV. Specifically, they consider a simple model where users directly submit orders to the market maker. They do not consider any arbitrage strategy where users or miners try to front-run or back-run others’ orders to make profit.

Bartoletti et al. [15] studied the miner’s optimal MEV strategy under transaction reordering. Their work also does not provide a solution to mitigate or address MEV.

A line of works have empirically or theoretically investigated the profitability or impact of MEV [12, 37, 16, 41, 49, 52, 42, 11].

Another line of work suggest that the users themselves take action to mitigate MEV, either by setting their slippage limits more cleverly [50], or by exploiting arbitrage opportunities themselves to lower their transactional costs [32]. There are also various blog posts on online forums that suggest alternative designs [38, 33]. However, these works are empirical and do not lend to the theoretical understanding of the equilibrium behavior of the eco-system.

Both academic research and real-world blockchain projects have made an effort to build decentralized sequencers [2, 10, 36, 34, 35], or encrypted mempools [29, 17]. The former approach removes the ability for a single block proposer to decide the block contents and sequencing, and achieves some form of sequencing fairness [36, 34, 35]⁴⁴4Sequencing fairness is also commonly referred to as “order fairness”. In this paper, we use the term “sequencing fairness” to avoid collision with the usage of “order” to mean a trade proposal.. The latter approach allows users to submit transactions in committed or encrypted format, which makes it harder for miners to front-run and back-run transactions. However, from a mechanism design perspective, we still lack mathematical understanding to what extent these new consensus/cryptographic abstractions can help us mitigate MEV and achieve strategy-proof DeFi mechanisms. In this sense, our work is among the first to mathematically articulate how to rely on “sequencing fairness” to achieve strategy-proofness by construction.

A line of works [2, 10, 36, 34, 35] have studied how to achieve order fairness in consensus. Numerous blockchain projects are also building decentralized sequencers [3, 4, 5, 6, 7, 8] which can be one approach for achieving sequencing fairness. Some works [28, 9] have also pointed out the price of sequencing fairness such as loss in welfare. Improving the underlying mechanisms for achieving sequencing fairness is outside the scope of this paper. We also leave it as future work to study how to optimize social welfare under strategy proofness.

There is a recent line of work on transaction fee mechanism (TFM) design [44, 26, 45]. This line of work aims to design mechanisms such that users, miners, and user-miner coalitions are incentivized to behave honestly. However, the current modeling approach of this line of work captures only the utilities at the consensus layer. They cannot capture ordering and application-level MEV. The recent work of Bahrani et al. [13] showed strong impossibility results for fully solving this problem at the TFM-layer alone. In this sense, our work complements the line of work on TFM design by taking an application-level (i.e., smart-contract-level) approach towards achieving strategy proofness by construction.

Each order is of the form $(t,v,r,\alpha )$ where

• $\mathrm{■}$

  $t\in \{\mathrm{𝖡𝗎𝗒}(X),\mathrm{𝖡𝗎𝗒}(Y),\mathrm{𝖲𝖾𝗅𝗅}(X),\mathrm{𝖲𝖾𝗅𝗅}(Y)\}$ is the type of the order indicating that the user wants to buy or sell and which asset;

• $\mathrm{■}$

  $v$ is a non-negative value that denotes the maximum amount of the user wants to buy or sell;

• $\mathrm{■}$

  $r$ denotes the user’s acceptable exchange rate, i.e., the user believes that each unit of $X$ is worth $r$ units of $Y$. For example, if the order is of type $\mathrm{𝖡𝗎𝗒}(X)$, then the user is willing to pay at most $r$ units of $Y$ for each unit of $X$; if the type is $\mathrm{𝖲𝖾𝗅𝗅}(Y)$, then $1/r$ is the minimum asking price in $X$ for each unit of $Y$.

• $\mathrm{■}$

  $\alpha$ is an arbitrary string denoting any additional auxiliary information, e.g., the submitter’s identity, timestamping information, position in the block, and so on.

Note that given an order of the form ($\mathrm{𝖲𝖾𝗅𝗅}(Y)$, $v$, $r$, _)⁵⁵5Here, the ignore symbol $\mathrm{\_}$ means that we are ignoring the content of this field in the current context., another way to view it is that the user wants to buy $X$; it is willing to pay at most $r$ units of $Y$ for each unit of $X$; moreover, it wants to buy as many units of $X$ as possible subject to a capital of $v$ units of $Y$. Henceforth, for an order of the type $\mathrm{𝖡𝗎𝗒}(X)$ or $\mathrm{𝖲𝖾𝗅𝗅}(X)$, we say that $X$ is the primary asset of the order.

A possibly randomized (partial fulfillment) swap mechanism should define the following rules⁶⁶6In Section 5, we pose the open question of how to achieve strategy proofness for all-or-nothing fulfillment mechanisms.:

• $\mathrm{■}$

  Honest strategy. Given a user’s private type $T$, the initial state $\mathrm{𝖯𝗈𝗈𝗅}(x,y)$, the honest strategy, often denoted $HS(x,y,T)$, outputs a vector of orders the user should submit. A user’s private type $T$ can contain information such as how many units of $X$ and $Y$ it currently holds, and the user’s private valuation of the exchange rate between $X$ and $Y$.

• $\mathrm{■}$

  Allocation rule. The allocation rule receives as input an initial state $\mathrm{𝖯𝗈𝗈𝗅}(x,y)$, a list of orders, and for each order $(t,v,r,\alpha )$, it outputs the following:

  • –

    the amount $v^{\prime }\in [0,v]$ of primary asset that has been fulfilled – note that the fulfillment can be partial;

  • –

    an average exchange rate $r^{\prime }>0$ at which the order was fulfilled. For a $\mathrm{𝖡𝗎𝗒}(X)$ order, it means that the user pays $v^{\prime }\cdot r^{\prime }$ units of $Y$ in exchange for $v^{\prime }$ units of $X$. For a $\mathrm{𝖲𝖾𝗅𝗅}(Y)$ order, the user obtains $v^{\prime }/r^{\prime }$ units of $X$ for the $v^{\prime }$ units of $Y$ sold. We require that for a $\mathrm{𝖡𝗎𝗒}(X)/\mathrm{𝖲𝖾𝗅𝗅}(Y)$ order, $r^{\prime }\le r$, i.e., the purchase price cannot be higher than the specified maximum rate $r$; and for a $\mathrm{𝖡𝗎𝗒}(Y)/\mathrm{𝖲𝖾𝗅𝗅}(X)$ order, $1/r^{\prime }\le 1/r$.

In a real-world instantiation, the pool state is recorded on the blockchain, and the allocation rule is executed on the blockchain (e.g., in the form of a smart contract).

We consider swap mechanisms that satisfy the following invariant on pool state. Given some initial state $\mathrm{𝖯𝗈𝗈𝗅}(x,y)$, and the outcome output by the allocation rule, one can uniquely determine the ending state $\mathrm{𝖯𝗈𝗈𝗅}(x^{\prime },y^{\prime })$. We require that initial and ending pool state must satisfy some constant potential function, that is, $\mathrm{\Phi }(x^{\prime },y^{\prime })=\mathrm{\Phi }(x,y)$. We define potential function and requirements on the potential function below.

We consider swap mechanisms that respect a constant potential function $\mathrm{\Phi }(\cdot ,\cdot )$. Specifically, suppose the pool’s initial state is $\mathrm{𝖯𝗈𝗈𝗅}(x,y)$, and changes to $\mathrm{𝖯𝗈𝗈𝗅}(x^{\prime },y^{\prime })$ after the mechanism processes a batch of orders. Then, it must be that

In practice, the most widely adopted approach is a constant-product market maker where $\mathrm{\Phi }(x,y)=x\cdot y$. In other words, suppose the initial pool state is $(x,y)$ and some user buys $\delta x$ amount of $X$, then it must pay $-\delta y$ units of $Y$ where $\delta y$ can be calculated by solving the following equation:

We assume the standard assumption that the potential function $\mathrm{\Phi }(\cdot ,\cdot )$ is increasing, differentiable, and concave.

In our swap mechanism, we will make use of the notion of a market exchange rate, as defined below.

Throughout this paper, whenever we say rate, it always means how much $y$ one has to pay per unit of $x$ rather than the other way around.

In the plain model, we assume that a strategy user or miner with intrinsic type $(t,v,r,\alpha )$ may engage in the following strategies:

• $\mathrm{■}$

  Post zero or multiple arbitrary orders which may or may not reflect its intrinsic type – this captures strategies that involve misreporting valuation and demand, as well as posting of fake orders;

• $\mathrm{■}$

  Censor honest users’ orders – this captures a strategic miner’s ability to exclude certain orders from the assembled block;

• $\mathrm{■}$

  Arbitrarily misrepresent its own auxiliary information field $\alpha$, or even modify the $\alpha$ field of honest users’ orders – meant to capture the ability of a miner to decide the sequencing of the transactions within a block, where the arrival-time and position information may be generically captured by the auxiliary information field $\alpha$.

• $\mathrm{■}$

  Decide its strategy after having observed honest users’ orders.

The coalition of a miner with 0 demand and a user with some positive demand as captured by its type $(t,v>0,r,\alpha )$ can simply be viewed as a single strategic player with type $(t,v>0,r,\alpha )$.

We consider the following strategy space in the weak fair-sequencing model:

• $\mathrm{■}$

  A strategic user or miner with intrinsic type $(t,v,r,\alpha )$ is allowed to post zero or multiple bids of the form $(\mathrm{\_},\mathrm{\_},\mathrm{\_},{\alpha }^{\prime })$ as long as ${\alpha }^{\prime }\ge \alpha$. This captures misreporting valuation and demand, posting fake orders, as well as delaying the posting of ones’ orders.

• $\mathrm{■}$

  The strategic user or miner can decide its strategy after observing honest users’ orders.

Compared to the plain model, the weak fair-sequencing model imposes some restrictions on the strategy space. Specifically, in the plain model, a strategic user or miner can arbitrarily modify the $\alpha$ field of its own order or even others’ orders, and a strategic miner may censor honest users’ orders. In the weak fair-sequencing model, a strategic user or miner can no longer under-report its $\alpha$, cannot modify honest users’ $\alpha$, and cannot censor honest users’ orders, because the sequencing of the transactions is determined by the underlying decentralized sequencer.

Importantly, despite these constraints on the strategy space, the weak fair-sequencing model still permits front-running-style attacks as mentioned earlier, and thus mechanism design remains non-trivial even under the slightly restricted strategy space.

To define strategy proofness, we first need to define a ranking system that expresses a user’s preference among different outcomes.

We can use a pair $(\delta x,\delta y)$ to denote the outcome, meaning that the user has a net gain of $\delta x$ in $X$, and it has a net gain of $\delta y$ in $Y$ (where a net loss is captured as negative gain). Consider two outcomes $(\delta x_0,\delta y_0)$ and $(\delta x_1,\delta y_1)$, and suppose that the user’s intrinsic type is $T=(\mathrm{𝖡𝗎𝗒}(X),v,r,\mathrm{\_})$. Naturally, for such a user, outcome $(\delta x_1,\delta y_1)$ is at least as good as $(\delta x_0,\delta y_0)$, henceforth denoted $(\delta x_0,\delta y_0){⪯}_T(\delta x_1,\delta y_1)$, if one of the following is true:

• $\mathrm{■}$

  $\delta x_0\le \delta x_1$, $\delta y_0\le \delta y_1$. In other words, relative to $(\delta x_0,\delta y_0)$, the user gains no less in either asset in the latter outcome $(\delta x_1,\delta y_1)$.

• $\mathrm{■}$

  $\delta x_0\le \delta x_1\le v$ (or $q\le \delta x_1\le \delta x_0$), and $r(\delta x_1-\delta x_0)\ge \delta y_0-\delta y_1$. In other words, the latter outcome $(\delta x_1,\delta y_1)$ is closer to satisfying the demand $v$, and moreover, the user paid at most $r$ marginal price for each extra unit of $X$ in the latter outcome.

Since in our paper, we consider deterministic mechanisms, we will define strategy proofness only for a deterministic mechanism. Note that the definition can easily be extended to randomized mechanism using suitable notions of stochastic dominance.

In the definition below, we use $HS(T)$ to denote the honest strategy of a user with intrinsic type $T$ – for a direct-revelation mechanism, the honest strategy is simply to reveal the user’s true type. Further, we use ${\mathrm{𝗈𝗎𝗍}}^u(x_0,y_0,𝐛)$ to denote the outcome of user $u$ when the mechanism is executed over initial pool state $\mathrm{𝖯𝗈𝗈𝗅}(x_0,y_0)$, and a vector of orders $𝐛$.

More intuitively, the definition says that no strategic play can result in a strictly better outcome than the honest strategy.

The fact below shows that strategy proofness implies arbitrage resilience.

We can prove the contra-positive, that is, a mechanism that is not arbitrage free cannot be strategy proof. Suppose that the mechanism is not arbitrage free. This means that there exists a list of orders $S={\{(t_i,v_i,r_i,{\alpha }_i)\}}_i$ such that under honest execution, a subset of the orders $S^{\prime }\subseteq S$ will enjoy $\delta x\ge 0$ and $\delta y\ge 0$, and at least one of the two is strictly positive. Now imagine that there is a world that consists of the orders $S\backslash S^{\prime }$. In this case, a strategic user or miner with 0 demand can inject a set of fake orders $S^{\prime }$, and clearly this strategic behavior has positive gain, thus violating strategy proofness. Note that this strategy works even in the weak fair-sequencing model, as long as the strategic user’s inherent arrival time $\alpha$ is no larger than the orders in $S^{\prime }$. $◀$

Since our plain-model mechanism gives an example that satisfies arbitrage resilience but not strategy proof, we conclude that strategy proofness is strictly stronger than arbitrage resilience. Specifically, at the beginning of Section 3.3, we explain why we cannot achieve strategy proof in the plain model. The strategies presented in this section also help to illustrate why the stronger notion of strategy proofness is more desirable.

We prove it for the $\mathrm{𝖡𝗎𝗒}(X)/\mathrm{𝖲𝖾𝗅𝗅}(Y)$-dominant case, since the $\mathrm{𝖡𝗎𝗒}(Y)/\mathrm{𝖲𝖾𝗅𝗅}(X)$-dominant case is symmetric. The mechanism essentially does the following. In phase 1, it (partially) executes a set of orders all at the initial rate $r_0$, such that there is no change to the initial pool state $\mathrm{𝖯𝗈𝗈𝗅}(x_0,y_0)$. In phase 2, it executes only $\mathrm{𝖡𝗎𝗒}(X)/\mathrm{𝖲𝖾𝗅𝗅}(Y)$ orders. Due to increasing marginal cost (Fact 2), in Phase 2, all the (partially) executed $\mathrm{𝖡𝗎𝗒}(X)/\mathrm{𝖲𝖾𝗅𝗅}(Y)$ orders enjoy a rate that is at least $r_0$. Therefore, all the (partially) executed $\mathrm{𝖡𝗎𝗒}(Y)/\mathrm{𝖲𝖾𝗅𝗅}(X)$ orders enjoy a rate of $r_0$, and all the (partially) executed $\mathrm{𝖡𝗎𝗒}(X)/\mathrm{𝖲𝖾𝗅𝗅}(Y)$ orders enjoy a rate that is $r_0$ or greater. Thus, it cannot be the case that there is a net gain in one asset without any loss in the other. $◀$

As mentioned, our swap mechanism in Figure 1 does not fully specify how to break ties in the sorting steps of in Lines 3a and 4a. Moreover, our arbitrage resilience property does not care how the tie-breaking is done.

However, if we are not careful about the tie-breaking the resulting mechanism may not satisfy strategy proofness. For example, imagine that the tie-breaking is based on the $\alpha$ field of the order, which encodes the time at which the order is submitted. In this case, a strategic miner or user can simply make its own order have a small $\alpha$ to enjoy a better price, rather than truthfully reporting $\alpha$.

In the weak fair-sequencing model, the arrival order $\alpha$ is decided by an underlying consensus protocol that provides some form of sequencing fairness. In other words, the consensus protocol itself records the approximate time at which each order is first seen. In practice, this arrival time is dependent on when the user submits the its order to the network, and its network delay. A sequencing-fair consensus protocol cannot prevent a user (or miner) from delaying the submission of its order. It also cannot prevent a strategic user with an extremely fast network from front-running a victim’s order. Specifically, the strategic user can still observe what the victim submits, and then immediately submits a dependent order. If the strategic user’s network is faster than the victim’s, the strategic order may have an earlier arrival time than the victim’s order! However, sequencing fairness from the consensus does tie the hands of strategic players in the following weak manner (hence the name “weak sequencing fair”): if a strategic user’s order is generated at time $\alpha$, it cannot pretend that the order was generated at even if it has an extremely fast network with a delay of $0$.

We can refine the mechanism in Figure 1 as follows to achieve strategy proofness in the weak fair-sequencing model (see also Section 4):

• For tie-breaking in the sorting steps (Lines 3a and 4a), we now require that the sorting be stable, that is, in the sorted outcome, the relative ordering among all identical $\mathrm{𝖡𝗎𝗒}(Y)$ orders must respect the arrival order encoded in the $\alpha$ field; the same holds for all $\mathrm{𝖡𝗎𝗒}(X)$ orders.

We will assume that a user’s honest strategy is to honestly report its type including the $\alpha$ field, that is, $HS(t,v,r,\alpha )$ simply outputs a single order $(t,v,r,\alpha )$.

The proof of Theorem 3.2 is provided in Section 4.

Suppose $\mathrm{\Phi }(x,y)=C$. Since $\mathrm{\Phi }$ is increasing, by Lemma B.1 of [30], the potential function $\mathrm{\Phi }$ defines a bijective decreasing function $h(\cdot )$ such that $\mathrm{\Phi }(z,h(z))=C$. Moreover, since $\mathrm{\Phi }$ is concave, the induced function $h(\cdot )$ is convex (Lemma B.2 of [30]). Observe that $\mathrm{\Phi }$ is differentiable, so $r(x,y)=-h^{\prime }(x)$. Therefore, $r(x,y)\le r(x^{\prime },y^{\prime })$ for $x^{\prime }\le x$ by the convexity of $h$. $◀$

Since the mechanism is deterministic, given the initial state $\mathrm{𝖯𝗈𝗈𝗅}(x_0,y_0)$, order vector from all other users ${𝐛}_{-u}$, and the strategic order vector ${𝐛}_u$, one can compute the whole order execution trace of the mechanism. For an order $b=(\mathrm{𝖲𝖾𝗅𝗅}(Y),v_j,r_j,{\alpha }_j)$ in ${𝐛}_u$, if it is not executed, then it can be replaced with a $(\mathrm{𝖡𝗎𝗒}(X),0,r_j,{\alpha }_j)$. If it is partially fulfilled, let $(x_{\mathrm{start}},x_{\mathrm{end}})$ denote the amount of asset $X$ in the pool right before and right after $b$ is executed, respectively. Let $r_{\mathrm{end}}$ denote the market exchange rate at $x_{\mathrm{end}}$. Then $b$ can be replaced with an order $(\mathrm{𝖡𝗎𝗒}(X),x_{\mathrm{start}}-x_{\mathrm{end}},r_{\mathrm{end}},{\alpha }_j)$, without changing the outcome. Similarly, we can replace a $\mathrm{𝖡𝗎𝗒}(Y)$-type order with a $\mathrm{𝖲𝖾𝗅𝗅}(X)$-type order without changing the outcome. The fact thus follows. $◀$

To prove this lemma, we first show that we can coalesce all the $\mathrm{𝖡𝗎𝗒}(X)/\mathrm{𝖲𝖾𝗅𝗅}(Y)$-type orders into one, and all the $\mathrm{𝖲𝖾𝗅𝗅}(X)/\mathrm{𝖡𝗎𝗒}(Y)$-type orders into one, as stated in the following claim.

According to Fact 4, we can assume that ${𝐛}_u$ contains only $\mathrm{𝖡𝗎𝗒}(X)$ and $\mathrm{𝖲𝖾𝗅𝗅}(X)$-type orders. Let ${𝐛}_{\mathrm{𝖲𝖾𝗅𝗅}}$ and ${𝐛}_{\mathrm{𝖡𝗎𝗒}}$ denote the vector of $\mathrm{𝖲𝖾𝗅𝗅}(X)$-type and $\mathrm{𝖡𝗎𝗒}(X)$-type orders in ${𝐛}_u$, respectively. Without loss of generality, assume that given ${𝐛}_{-u}$ and ${𝐛}_u$, we have the $\mathrm{𝖡𝗎𝗒}(X)$/$\mathrm{𝖲𝖾𝗅𝗅}(Y)$-dominant case, (the $\mathrm{𝖡𝗎𝗒}(Y)$/$\mathrm{𝖲𝖾𝗅𝗅}(X)$-dominant case is symmetric).

For the $\mathrm{𝖡𝗎𝗒}(X)$/$\mathrm{𝖲𝖾𝗅𝗅}(Y)$-dominant case, all $\mathrm{𝖲𝖾𝗅𝗅}(X)$-type orders in ${𝐛}_{\mathrm{𝖲𝖾𝗅𝗅}}$ will be executed at the initial exchange rate $r_0$. Therefore, consider an order $b=(\mathrm{𝖲𝖾𝗅𝗅}(X),v,r,\alpha )$, where $v$ denotes the total units of orders in ${𝐛}_{\mathrm{Sell}}$, $r$ is the minimum asking rate in ${𝐛}_{\mathrm{Sell}}$, and $\alpha$ is the earliest arrival time in ${𝐛}_u$. Then a strategic order vector $({𝐛}_{\mathrm{Buy}},b)$ results in the same outcome as ${𝐛}_u$.

Now consider an order $b^{\prime }=(\mathrm{𝖡𝗎𝗒}(X),v^{\prime },r^{\prime },{\alpha }^{\prime })$, where $v^{\prime }$ is the total units of order executed in ${𝐛}_{\mathrm{Buy}}$, $r^{\prime }$ is the maximum asking rate in ${𝐛}_{\mathrm{Buy}}$, and ${\alpha }^{\prime }$ is the earliest arrival time of the order in ${𝐛}_{\mathrm{Buy}}$ that is partially fulfilled. Let ${𝐛}_u^{\prime }=(b^{\prime },b)$. Compared to the units executed in ${𝐛}_{\mathrm{Buy}}$, the units executed in $b^{\prime }$ have an earlier or the same arrival time. In addition, the asking rate $r^{\prime }$ in $b^{\prime }$ is larger than or equal to that in ${𝐛}_{\mathrm{Buy}}$. Therefore, all units in $b^{\prime }$ will be executed. Moreover, by the increasing marginal cost (Fact 2), the exchange rate for $b^{\prime }$ is no more than the average exchange rate for all orders in ${𝐛}_{\mathrm{Buy}}$. This means that ${𝐛}_u^{\prime }$ results in an outcome that is at least as good as $({𝐛}_{\mathrm{Buy}},b)$ according to the partial ordering. By the transitivity, ${𝐛}_u^{\prime }$ results in an outcome that is at least as good as ${𝐛}_u$. $\mathrm{⊲}$

Next, we show that for any order vector ${𝐛}_u$ that contains a single $\mathrm{𝖡𝗎𝗒}(X)/\mathrm{𝖲𝖾𝗅𝗅}(Y)$-type order and a single $\mathrm{𝖲𝖾𝗅𝗅}(X)/\mathrm{𝖡𝗎𝗒}(Y)$-type order, we can remove the part that “cancels off”, and substitute it with a single order. This is formally stated in the following claim.

Because of Fact 4, we assume that the strategic order vector ${𝐛}_u$ contains a single $\mathrm{𝖡𝗎𝗒}(X)$-type order $(\mathrm{𝖡𝗎𝗒}(X),v_b,r_b,{\alpha }_b)$ and a single $\mathrm{𝖲𝖾𝗅𝗅}(X)$-type order $(\mathrm{𝖲𝖾𝗅𝗅}(X),v_s,r_s,{\alpha }_s)$. By our assumption, both orders are fully executed. If either $v_b$ or $v_s$ is zero, the result follows trivially; henceforth, we assume that both are non-zero. Similarly, if either or $r_s>r_0$, then the result also follows trivially. henceforth, $r_b\ge r_0$ and $r_s\le r_0$.

We prove it assuming the $\mathrm{𝖡𝗎𝗒}(X)$/$\mathrm{𝖲𝖾𝗅𝗅}(Y)$-dominant case case under the strategic order vector ${𝐛}_u$, since the argument for the $\mathrm{𝖡𝗎𝗒}(Y)$/$\mathrm{𝖲𝖾𝗅𝗅}(X)$-dominant case is symmetric. For the $\mathrm{𝖡𝗎𝗒}(X)$/$\mathrm{𝖲𝖾𝗅𝗅}(Y)$-dominant case, if it were possible to execute all orders at $r_0$, then there is more demand in terms of only $\mathrm{𝖡𝗎𝗒}(X)/\mathrm{𝖲𝖾𝗅𝗅}(Y)$ than $\mathrm{𝖲𝖾𝗅𝗅}(X)/\mathrm{𝖡𝗎𝗒}(Y)$. In this case, Phase 1 executes all $\mathrm{𝖲𝖾𝗅𝗅}(X)/\mathrm{𝖡𝗎𝗒}(Y)$ orders at $r_0$, and Phase 2 executes only $\mathrm{𝖡𝗎𝗒}(X)/\mathrm{𝖲𝖾𝗅𝗅}(Y)$ orders.

Under the original ${𝐛}_u$, the user would sell $v_s$ units of $X$ at $r_0$ and would buy $v_b$ units of $X$ at a rate of $r_0$ or greater. Now, suppose we replace ${𝐛}_u$ with a single order $b_u^{\prime }=(\mathrm{𝖲𝖾𝗅𝗅}(X),v_s-v_b,r_s,{\alpha }_s)$. Under $b_u^{\prime }$, it is still the case that all $\mathrm{𝖲𝖾𝗅𝗅}(X)$ orders are completely executed at $r_0$.

Hence, we can decompose the original ${𝐛}_u$ equivalently into the following steps: (i) first execute $b_u^{\prime }$; (ii) sell $v_b$ units at rate $r_0$; (iii) buy back $v_b$ units at rate $r_0$ or greater. Since steps (ii) and (iii) together will incur a non-negative loss in $Y$ (but create no change in $X$), user $u$’s outcome under $b_u^{\prime }$ is at least as good as ${𝐛}_u$.

Consider the original ${𝐛}_u$ which consists of $(\mathrm{𝖲𝖾𝗅𝗅}(X),v_s,r_s,{\alpha }_s)$ and $(\mathrm{𝖡𝗎𝗒}(X),v_b,r_b,{\alpha }_b)$. We will analyze what happens when we replace these two orders with a single order $b_u^{\prime }=(\mathrm{𝖡𝗎𝗒}(X),v_b-v_s,r_b,{\alpha }_b)$. Suppose in Phase 1 of the execution with ${𝐛}_u$, user $u$ sells $v_s$ units of $X$ and buys $v^{\prime }\le v_b$ units of $X$ at rate $r_0$. We separate the rest of the proof into two cases.

1. 1.

   Case $v^{\mathbf{\prime }}\mathbf{\ge }{v}_s$. For the execution with ${𝐛}_u$: In Phase 1, the net effect is to buy $v^{\prime }-v_s$ units of $X$ at rate $r_0$. In Phase 2, the user $u$ buys the remaining $v_b-v^{\prime }$ units starting at rate $r_0$.

   The execution with $b_u^{\prime }$ can be viewed as follows: In Phase 1’, $v^{\prime }-v_s$ units of $\mathrm{𝖡𝗎𝗒}(X)$ will be executed at rate $r_0$. Then in Phase 2’, the mechanism executes the rest $v_b-v^{\prime }$ units in $b_u^{\prime }$ starting at rate $r_0$.

   Hence, the two scenarios are equivalent, and the two outcomes are the same.

2. 2.

   Case . We will view the execution of the orders $(\mathrm{𝖲𝖾𝗅𝗅}(X),v_s,r_s,{\alpha }_s)$ and $(\mathrm{𝖡𝗎𝗒}(X),v_b,r_b,{\alpha }_b)$ as follows.

   • $\mathrm{■}$

     Phase 1: User $u$ sells $v_s$ units of $X$ and buy $v^{\prime }$ units of $X$ at a rate of $r_0$, and it gains $(v_s-v^{\prime })\cdot r_0$ units of $Y$ in return.

   • $\mathrm{■}$

     Phase 2a: Some non-negative amount of $\mathrm{𝖡𝗎𝗒}(X)$/$\mathrm{𝖲𝖾𝗅𝗅}(Y)$ orders from other users are executed at a starting market rate of $r_0$, let $v_{\mathrm{other}}\ge 0$ be the units of $X$ purchased. Note that if $v^{\prime }>0$, then $v_{\mathrm{other}}=0$.

     At the end of this phase, the market rate $r_1\ge r_0$ by increasing marginal cost.

   • $\mathrm{■}$

     Phase 2b: Starting at rate $r_1\ge r_0$, user $u$ buys $v_s-v^{\prime }$ units of $X$, which changes the market rate to $r_2\ge r_1$.

   • $\mathrm{■}$

     Phase 2c: Starting at rate $r_2$, the user buys $(v_b-v_s)$ units of $X$, changing the market rate to $r_3$.

   The new execution involving $b_u^{\prime }$ can be viewed as the following:

   • $\mathrm{■}$

     Phase 1’: The $\mathrm{𝖡𝗎𝗒}(X)/\mathrm{𝖲𝖾𝗅𝗅}(Y)$ orders of other users executed in the original Phase 1 cannot all be executed in the new Phase 1. In particular, the last $v_s-v^{\prime }$ units of $X$ cannot be fulfilled in Phase 1’, and will be pushed to Phase 2a’ – henceforth, we call this portion the residual.

   • $\mathrm{■}$

     Phase 2a’: The mechanism attempts to execute the residual from Phase 1’ at a starting rate of $r_0$. The amount fulfilled must be at most $v_s-v^{\prime }$.

   • $\mathrm{■}$

     Phase 2b’: The mechanism attempts to execute the (partial) orders originally considered in Phase 2a, at a starting price that is at least $r_0$. At most $v_{\mathrm{other}}$ units of $X$ can be fulfilled. The ending market rate must be at least $r_1$.

   • $\mathrm{■}$

     Phase 2c’: The mechanism attempts to execute $b_u^{\prime }$. Observe that the total units of $X$ fulfilled in the original Phase 2a, 2b, and 2c is $v_{\mathrm{other}}+v_b-v^{\prime }$, and the total units of $X$ fulfilled in the new Phase 2a’, 2b’, and 2c’ is at most $(v_s-v^{\prime })+v_{\mathrm{other}}+v_b-v_s=v_{\mathrm{other}}+v_b-v^{\prime }$. Therefore, it must be that all of $b_u^{\prime }$ can be fulfilled and the ending market rate is at most $r_3\le r_b$.

   Henceforth, we use the notation $\mathrm{𝖯𝖺𝗒}(\text{Phase *})$ to denote user $u$’s payment in terms of $Y$ in some phase. When the pay is negative, it means a gain in $Y$. Observe that

   $$\mathrm{𝖯𝖺𝗒}(\text{Phase 1})+\mathrm{𝖯𝖺𝗒}(\text{Phase 2b})\ge 0,\mathrm{𝖯𝖺𝗒}(\text{Phase 2c})\ge \mathrm{𝖯𝖺𝗒}(\text{Phase 2c’}).$$

   Therefore,

   $$\mathrm{𝖯𝖺𝗒}(\text{Phase 1})+\mathrm{𝖯𝖺𝗒}(\text{Phase 2b})+\mathrm{𝖯𝖺𝗒}(\text{Phase 2c})\ge \mathrm{𝖯𝖺𝗒}(\text{Phase 2c’}).$$

   Observe that in the above, the left-hand side represents $u$’s total payment in $Y$ under the original ${𝐛}_u^{\prime }$, and the right-hand side represents $u$’s total payment in $Y$ under the new $b_u^{\prime }$.

$\mathrm{⊲}$

Lemma 4.1 follows by combining ˜4.2 and ˜4.3. $◀$

Due to Fact 4, we may assume that $b_u$ is either a $\mathrm{𝖡𝗎𝗒}(X)$ or $\mathrm{𝖲𝖾𝗅𝗅}(X)$ order. We prove it for a $\mathrm{𝖡𝗎𝗒}(X)$ order, since the case for a $\mathrm{𝖲𝖾𝗅𝗅}(X)$ order is symmetric. Let $v$ be the amount of $X$ bought by $b_u^{\prime }$. We shall assume that $v>0$ since the case $v=0$ is trivial. Consider an order $b_u=(\mathrm{𝖡𝗎𝗒}(X),v,+\mathrm{\infty },{\alpha }^{\ast })$. Clearly, $b_u$ will buy $v$ units of $X$.

We consider the following cases:

• $\mathrm{■}$

  $b_u$ buys $v_0>0$ units at $r_0$ in Phase 1, and then buys $v_1\ge 0$ units in Phase 2 at a starting rate of $r_0$ and an ending rate of $r_1\ge r_0$. In this case, by delaying the arrival time, $b_u^{\prime }$ can buy at most $v_0^{\prime }\le v_0$ units in Phase 1 at $r_0$, and it needs to buy $v-v_0^{\prime }\ge v_1$ in Phase 2. Therefore, for $b_u^{\prime }$, the starting rate in Phase 2 is $r_0$, and the ending rate must be at least $r_1$. Therefore, the average price paid per unit in $b_u$ is no worse than the average price paid per unit in $b_u^{\prime }$.

• $\mathrm{■}$

  $b_u$ buys all $v$ units in Phase 2. Since $b_u^{\prime }$ delayed the arrival, the order can be considered no earlier than $b_u$. Thus, before the mechanism tries to execute $b_u^{\prime }$ at least as many units of $X$ will have been bought (by all users) as when the mechanism tries to execute $b_u$. This means $b_u^{\prime }$ will have an average price no better than $b_u$.

$◀$

Due to Lemmas 4.1 and 4.4, it suffices to consider strategies that submit a single order, declare the true arrival time ${\alpha }^{\ast }$, and moreover, either the order has a $0$ amount or it will be completely executed under $\mathrm{𝖯𝗈𝗈𝗅}(x_0,y_0)$ and ${𝐛}_{-u}$ – henceforth, we call such strategies as admissible, single-order strategies. We can complete the proof of Theorem 3.2 by showing the following lemma.

Below we complete the proof of Lemma 4.5.

We prove it for the case when user $u$’s type is either $(\mathrm{𝖡𝗎𝗒}(X),v^{\ast },r^{\ast },{\alpha }^{\ast })$ or $(\mathrm{𝖲𝖾𝗅𝗅}(X),v^{\ast },r^{\ast },{\alpha }^{\ast })$. The case for $\mathrm{𝖡𝗎𝗒}(Y)$/$\mathrm{𝖲𝖾𝗅𝗅}(Y)$ is symmetric. Given two outcomes ${\mathrm{𝗈𝗎𝗍}}_0=(\delta x_0,\delta y_0)$ and ${\mathrm{𝗈𝗎𝗍}}_1=(\delta x_1,\delta y_1)$ and a true demand $\delta x^{\ast }$ for $X$, we say that they are on the same side of the goal $\delta x^{\ast }$ iff $(\delta x_0-\delta x^{\ast })\cdot (\delta x_1-\delta x^{\ast })\ge 0$. We say that ${\mathrm{𝗈𝗎𝗍}}_0$ is at least as close as ${\mathrm{𝗈𝗎𝗍}}_1$ towards the goal iff $|\delta x_0-\delta x^{\ast }|\le |\delta x_1-\delta x^{\ast }|$, and we say that ${\mathrm{𝗈𝗎𝗍}}_0$ is closer to the goal than ${\mathrm{𝗈𝗎𝗍}}_1$ iff .

Our natural partial ordering relation implies the following:

1. R1.

   Suppose $(\delta x_0,\delta y_0)$ and $(\delta x_1,\delta y_1)$ are on the same side of the goal, and $\delta x_0$ is at least as close as $\delta x_1$ towards the goal. Moreover, if , then $(\delta x_1,\delta y_1)⋡(\delta x_0,\delta y_0)$.

2. R2.

   If $\delta x_0$ and $\delta x_1$ are on the same side of the goal, $\delta x_0$ is closer than $\delta x_1$ to the goal, and moreover, $\delta y_1-\delta y_0>r^{\ast }\cdot (\delta x_0-\delta x_1)$, then $(\delta x_0,\delta y_0)⋡(\delta x_1,\delta y_1)$.

3. R3.

   If $\delta x_0$ and $\delta x_1$ are on different sides of the goal, and moreover, $\delta y_1-\delta y_0\ge r^{\ast }\cdot (\delta x_0-\delta x_1)$, then $(\delta x_0,\delta y_0)⋡(\delta x_1,\delta y_1)$.

Due to Fact 4, we may assume that the strategic order must be of the type $\mathrm{𝖡𝗎𝗒}(X)$ or $\mathrm{𝖲𝖾𝗅𝗅}(X)$. Further, as shown in the following fact, we can in fact assume that the strategic order adopts the true time of arrival ${\alpha }^{\ast }$, i.e., declaring a later time never helps.

Henceforth, let $(\delta x,\delta y)$ and $(\delta x^{\prime },\delta y^{\prime })$ denote the honest and strategic outcomes, respectively.

Either user $u$ has a true demand of 0 units, or the strategic order is opposite the direction of its true demand, i.e., if its type is $\mathrm{𝖡𝗎𝗒}(X)$, it submits a single $\mathrm{𝖲𝖾𝗅𝗅}(X)$ order; or vice versa. It must be that $\delta x\cdot \delta x^{\prime }\le 0$. Further, the honest outcome and strategic outcome must be on the same side of the true demand, and the honest outcome is at least as close to the goal as the strategic outcome. Our mechanism guarantees that either (i) $\delta x=\delta x^{\prime }=0$, or (ii) at least one of $\delta x^{\prime }$ and $\delta x^{\prime }$ is non-zero. In case (i), $\delta y=\delta y^{\prime }=0$, and the the two outcomes are the same.

In case (ii), because of no free lunch (Fact 3), at least one of the inequalities $\delta x\cdot \delta y\le 0$ and $\delta x^{\prime }\cdot \delta y^{\prime }\le 0$ must be strict; moreover, when an equality holds, both arguments of the product must be zero. Because $\delta x\cdot \delta x^{\prime }\le 0$, this implies that ; by the above rule R1, the honest outcome is at least as good as or incomparable the strategic one.

The user $u$ has a non-zero amount of true demand, and moreover, the strategic order is in the same direction of the true demand. We consider the following cases.

• $\mathrm{■}$

  Case 2a: $\delta x=\delta x^{\prime }$. By admissibility, the strategic order declares the same arrival time as the honest one; hence, if the orders from both strategies get executed for a non-zero amount, both execution will start at the same market exchange rate. Hence, it must be the case that $(\delta x,\delta y)=(\delta x^{\prime },\delta y^{\prime })$.

  Henceforth, we assume that $\delta x\ne \delta x^{\prime }$.

• $\mathrm{■}$

  Case 2b: The honest outcome and the strategic outcome are on the same side of the goal, and the honest outcome closer to the goal than the strategic outcome; this case includes the scenario that the honest outcome is exactly at the goal. Since we can assume that the strategic order has the same arrival time as the honest order, the difference of $|\delta x-\delta x^{\prime }|$ units are traded at a marginal price at least as good as $r$ in the honest outcome. Due to the third rule of the natural partial ordering, the honest outcome is at least as good as the stategic one.

• $\mathrm{■}$

  Case 2c: The honest outcome and the strategic outcome are on the same side of the goal, and the strategic outcome is closer to the goal than the honest outcome, i.e., .

  This means that the honest outcome has not reached the goal of user $u$. Under the honest strategy, after user $u$’s order has been executed (or attempted to be executed), the state of the market is such that if a further non-zero portion of the order is executed, this portion will incur an average rate of strictly worse than $r^{\ast }$. In the case of $\mathrm{𝖡𝗎𝗒}(X)$, this is strictly larger than $r^{\ast }$; in the case of $\mathrm{𝖲𝖾𝗅𝗅}(X)$, this is strictly less than $r^{\ast }$.

  Since the strategic order declares the same arrival time as the honest order, the difference of $|\delta x^{\prime }-\delta x|>0$ units must be traded at an average rate strictly worse than than $r^{\ast }$ in the strategic outcome. By rule R2, the strategic outcome is not at least as good as the honest outcome. However, because of no free lunch, the two outcomes are actually incomparable.

• $\mathrm{■}$

  Case 2d: The honest outcome and the strategic outcome are on different sides of the goal, i.e., .

  In this case, $\delta x\ne 0$. Similar to case 2c, under the honest strategy, after user $u$’s order has been executed, the state of the market is such that if a further non-zero portion of the order is executed, this portion will incur an average rate of strictly worse than $r^{\ast }$.

  Because the strategic order declares the same arrival time as the honest one, the difference of $|\delta x^{\prime }-\delta x|$ units must be traded at an average rate of strictly worse than than $r^{\ast }$ in the strategic outcome. By rule R3, the strategic outcome cannot be at least as good as the honest outcome.

$◀$