# Mechanism Design for Automated Market Makers

T-H. Hubert Chan Ke Wu Elaine Shi Author ordering is randomized.

Blockchains have popularized automated market makers (AMMs). An AMM exchange
is an application running on a blockchain which maintains a pool of crypto-
assets and automatically trades assets with users governed by some pricing
function that prices the assets based on their relative demand/supply. AMMs
have created an important challenge commonly known as the Miner Extractable
Value (MEV). In particular, the miners who control the contents and ordering
of transactions in a block can extract value by front-running and back-running
users’ transactions, leading to arbitrage opportunities that guarantee them
risk-free returns. Not only does MEV harm ordinary users, but more
importantly, the existence of MEV opportunities has encouraged miners to
auction off favorable positions in the block to users and arbitragers alike,
thus leading to a (typically more centralized) off-chain eco-system that
significantly deviates from the desired equilibrium of the infrastructure
layer originally envisioned by the blockchain’s designer.

In this paper, we consider how to design AMM mechanisms that eliminate MEV
opportunities. Specifically, we propose a new AMM mechanism that processes all
transactions contained within a block in a batch. We show that our new
mechanism satisfies two tiers of guarantees. First, for legacy blockchains
where each block is proposed by a single (possibly rotating) miner, we prove
that our mechanism satisfies arbitrage resilience, i.e., a miner cannot gain
risk-free profit. Moreover, we also guarantee fair treatment among all
transactions within the same block, such that the miner is unable to sell off
favorable positions in the block to users or arbitragers. Second, for
blockchains where the block proposal process is decentralized and offers
sequencing-fairness, we prove a stronger notion called incentive compatibility
— roughly speaking, we guarantee that any individual user’s best response is
to follow the honest strategy.

##  1 Introduction

Blockchains have popularized decentralized finance, also called DeFi. One main
application of DeFi is automatic market makers (AMMs) [BCL21] based
Decentralized Exchanges (DEX). For example, the top six AMMs including
Uniswap, Balancer, and others, hold in aggregate 15 billion USD worth of
crypto-assets as of March 2021 [XPCF23]. A typical AMM exchange maintains a
pool of capital called the “liquidity pool” with two crypto-assets $X$ and
$Y$. A smart contract defines the rules by which users can trade assets with
the pool. For example, one commonly adopted rule is a constant-product
potential function defined as follows. Let ${\sf Pool}(x,y)$ denote the pool’s
state where $x\geq 0$ and $y\geq 0$ represent the units of $X$ and $Y$ held by
the pool, respectively. A constant product potential requires that $x\cdot
y=C$ for some constant $C>0$. This means that if a user buys $\delta x$ amount
of $X$ from the pool, it needs to pay $-\delta y$ amount of $Y$ such that
$(x-\delta x)(y-\delta y)=C$.

DeFi applications such as AMMs have introduced opportunities for miners to
profit, often in a risk-free manner, by front-running and/or back-running the
users’ transactions, a phenomenon often referred to as Miner Extractable Value
(MEV). Despite the decentralized nature of blockchains, in today’s mainstream
consensus protocols, the block proposal process is actually somewhat
centralized. Specifically, for each block, a single selected miner can
unilaterally decide which transactions go into the block, and the sequencing
among them. By exploiting this capability, they can profit, and often in a
risk-free manner. For example, in a sandwich attack [QZG22, XPCF23, KDC22,
ZQT+21], the miner identifies a victim user who wants to purchase some crypto
asset $X$ at a maximum price of $r$, and inserts a pair of ${\sf Buy}(X)$ and
${\sf Sell}(X)$ transactions immediately before and after the victim’s
transaction, respectively. Since the price of $X$ goes up with more units
bought from the pool, it is possible for the miner to buy low through the
front-running transaction, causing the user to buy at the worst possible price
$r$, and then sell high through the back-running transaction. Besides the
simple sandwich attack, more sophisticated arbitrage opportunities also abound
[ZQC+21, KDC22, QZG22].

MEV is widely acknowledged as one of the most important challenges for
blockchain projects today, due to the following reasons. First, since MEV is
exploited at the expense of users, it effectively increases ordinary users’
barrier of entry to DeFi applications. Second, it is widely believed that MEV
hurts the stability and security of the underlying consensus protocol [CKWN16,
ZQG21, ZQT+21, QZG22]. Specifically, miners may be incentivized to fork the
blockchain if forking can potentially bring them much higher MEV than the
block rewards. Third, the unequal power of the miner in deciding the block
contents and sequencing has resulted in an off-chain economy institutionalized
by projects like Flashbots, allowing miners to auction off 1) the ability to
front-run/back-run transactions to searchers who specialize in identifying
arbitrage opportunities, and 2) the ability to be protected from
frontrunning/backrunning to ordinary users. Such private off-chain contracts
have led to a centralizing effect in the underlying layer 1 (i.e., the
consensus layer), effectively causing the de facto layer 1 [GPR23] to deviate
significantly from the one originally envisioned by the blockchain’s designer,
and its equilibrium behavior is not understood.

###  1.1 Our Results and Contributions

#### A mechanism design approach towards mitigating MEV.

In this paper, we initiate a mechanism design approach towards mitigating the
MEV problem. Like the mechanism design literature, our philosophy is to design
the underlying mechanism such that it removes MEV opportunities and provides
incentive compatibility by construction. We design 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 an order specifying how much of $X$ (or $Y$) they want to
buy (or 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 ${\sf Pool}(x_{0},y_{0})$ and end state ${\sf Pool}(x_{1},y_{1})$ is
guaranteed to satisfy some “natural” potential function $\Phi$ (e.g., the
constant-product function mentioned above).

Our mechanism offers two levels of guarantees depending on whether the
underlying consensus’s block proposal is controlled by a single block producer
or decentralized:

  1. 1.

Arbitrage free in the presence of a centralized block producer: When the block
proposal process is controlled by a single miner (e.g., mainstream consensus
protocols today), our mechanism guarantees arbitrage resilience, i.e., 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$.

Moreover, we can guarantee a suitable notion of fair treatment, i.e., the
mechanism does not make use of the sequencing of transactions within the same
block. In other words, the mechanism does not create opportunities for miners
to auction off favorable positions in the block to arbitragers and users.

  2. 2.

Incentive compatibility in the presence of a decentralized block producer:
When the block proposal process is decentralized and offers a suitable notion
of sequencing fairness, our mechanism not only achieves arbitrage resilience,
but also guarantees incentive compatibility. Specifically, incentive
compatibility 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. Our incentive compatibility
guarantees hold even when a strategic user can inject orders into the order
stream after having observed orders that have been posted so far, as long as
it cannot censor honest users’ orders or subvert the sequencing fairness.

Technically, incentive compatibility is a strictly stronger notion than
arbitrage resilience, since an arbitrager (e.g., user or miner) can be viewed
as a special user with zero true demand, and incentive compatibility
guarantees that such an arbitrager cannot make profit by taking advantage of
others. One way to interpret our result is that we guarantee arbitrage
resilience under a broader strategy space (even when the arbitrager has
unilateral control of block creation); and under a more restricted strategy
space, we guarantee the stronger notion of incentive compatibility.

#### Conceptual contributions.

Our work is among the very first to adopt a mechanism design
approach/philosophy towards mitigating MEV. We put forth new modeling and
definitions, which capture a mechanism design problem of a decentralized
nature. In particular, in comparison with the classical mechanism design
literature, our mechanism 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. Our
new model and definitions naturally give rise to many interesting open
questions which we discuss in Section 1.3.

#### Limitations.

Since our work is one of the initial explorations of mechanism design for
decentralized finance, as expected, we do not promise to addresss the broad
range of complex MEV problems that we see today. Specifically, the scope of
the present paper is restricted to how eliminate MEV and incentivize truthful
behavior in a standalone two-asset AMM mechanism. How to address cross-
mechanism MEV, how to have game-theoretic properties that compose across
multiple instances, and how to extend our results to more applications (e.g.,
multi-asset AMMs, DeFi lending applications) are left as open questions for
future work. Despite these limitations, we believe that our effort is a small
but nonetheless valuable step forward towards formulating a mathematical
foundation for decentralized mechanism design, and particularly through the
lens of a mechanism designer. It is also worth mentioning that other subfields
of decentralized mechanism design (e.g., the transaction fee mechanism
literature [Rou21, CS23, SCW23]) are also similarly in a nascent state.
Likewise, the initial foundational works [Rou21, CS23, SCW23] in these areas
also made similar simplifying assumptions to make progress, e.g., they also
start by exploring standalone setting and leaving compositional guarantees and
cross-block strategies to future work.

###  1.2 Comparison with Related Work

#### Comparison with most closely related work.

The prior work of Ferreira and Parkes [FP23] recently proposed an approach
called verifiable sequencing rules. In particular, they propose that the block
proposer must be subject to a set of verifiable rules when constructing the
block. However, their work does not eliminate arbitrage, and still allows the
miner to make risk-free profit. The only provide a weaker type of guarantee,
that is, if the miner profited from arbitrage, the user has some price
guarantee. Similarly, their work does not provide incentive compatibility
guarantees (even when the miner is not strategic and trusted to behave
honestly), and users may be incentivized to bid untruthfully.

#### Batch clearing at the same price.

The concurrent and independent work of Canidio and Fritsch [CF23, CF24]
suggested batch-clearing at a uniform price and using a different pricing
function than Uniswap’s constant-product function. Their approach also
satisfies arbitrage resilience; but it suffers from two drawbacks: 1) their
mechanism does not satisfy the same efficiency as ours: there might be orders
that can be still executed but the mechanism may choose not to execute them;
and 2) their approach does not guarantee incentive compatibility even when the
miner is not strategic and trusted to behaves honestly. We stress that batch
clearning at the same price itself does not automatically guarantee incentive
compatibility. Since everyone is reporting a different value and quantity, it
depends on which subset orders are cleared. In fact, Canidio and Fritsch
[CF23, CF24] do not fully specify which set of orders to clear. The prior work
of Ramseyer et al. [RGGM23] also considered batch exchanges that clear at a
uniform price. Like Canidio and Fritsch [CF23, CF24], their work provides no
incentive compatibility guarantees (even when the miner is fully trusted).

#### Related works that do not address MEV.

Milionis, Moallemi, and Roughgarden [MMR23] 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.

#### Understanding the impact of MEV.

A line of works have empirically or theoretically investigated the
profitability or impact of MEV [BDKJ23, KDC22, BCLL22, QZG22, ZQC+21, Zus,
QZLG21, AEC21].

#### Empirical approaches towards mitigating MEV.

Another line of work suggest that the users can take action to mitigate MEV,
either by setting their slippage limits more cleverly [ZQG21], or by
exploiting arbitrage opportunities themselves to lower their transactional
costs [HW22]. There are also various blog posts on online forums that suggest
alternative designs [Leu, Jos]. 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 [esp, dec, KZGJ20, KDK22, KDL+21], or
encrypted mempools [Dra, BO22]. 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 [KZGJ20, KDK22, KDL+21]111Sequencing
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 incentive compatible DeFi mechanisms.

In this sense, our work is among the first to mathematically articulate how to
rely on “sequencing fairness” to achieve incentive compability by
construction.

#### Other related works.

There is a recent line of work on transaction fee mechanism (TFM) design
[Rou21, CS23, SCW23]. 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 [BGR23] 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
incentive compatibility by construction.

###  1.3 Open Questions

Our new model and definitions give rise to many interesting open problems. One
interesting question is how to extend our results to AMMs with multiple
assets. Another interesting question is whether it is possible to achieve the
stronger notion of incentive compatibility without relying on sequencing
fairness. Just like earlier works such as the recent work of Ferrerira and
Parkes [FP23], our work focuses on the stand-alone setting, and we currently
do not provide compositional guarantees. Therefore, understanding how to
achieve compositional guarantees across multiple blocks and multiple AMM
contracts is an interesting open direction. It is interesting to note that
cross-block strategies may not be risk-free, since the same miner is not
guaranteed to mine all blocks in the future. Currently, our model assumes that
all the orders are submitted in the clear, and we thus define incentive
compatibility in the ex post setting. A future direction is to understand how
to define and achieve incentive compatibility in an MPC-assisted model [SCW23]
or an “encrypted mempool” [Dra, BO22] model where transactions are submitted
in encrypted or committed format.

##  2 Definitions

###  2.1 Swap Mechanism for AMMs

A swap mechanism for a pair of assets $(X,Y)$ has a state (also called the
pool state) denoted ${\sf Pool}(x,y)$ where $x$ and $y$ are non-negative
values that represent the amount of each asset currently held by the
mechanism. A user can submit an order to trade with the mechanism in two ways:
either buy $X$ and pay in $Y$, or buy $Y$ and pay in $X$. Suppose the user
buys $\delta x$ units of $X$ and pays $\delta y$ units of $Y$, then the
updated state after the trade will become ${\sf Pool}(x-\delta x,y+\delta y)$.

#### Order.

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

  * •

$t\in\\{{\sf Buy}(X),{\sf Buy}(Y),{\sf Sell}(X),{\sf Sell}(Y)\\}$ is the type
of the order indicating that the user wants to buy or sell and which asset;

  * •

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

  * •

$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 ${\sf Buy}(X)$, then the user is willing to pay at most $r$ units of $Y$
for each unit of $X$; if the type is ${\sf Sell}(Y)$, then $1/r$ is the
minimum asking price in $X$ for each unit of $Y$.

  * •

$\alpha$ is an arbitrary string denoting any additional auxiliary information.

Note that given an order of the form (${\sf Sell}(Y)$, $v$, $r$, _)222Here,
the ignore symbol $\\_$ 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 ${\sf
Buy}(X)$ or ${\sf Sell}(X)$, we say that $X$ is the primary asset of the
order.

#### Swap mechanism.

A possibly randomized (partial fulfillment) swap mechanism should define the
following rules:

  * •

Honest strategy. Given a user’s private type $T$, the initial state ${\sf
Pool}(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$.

  * •

Allocation rule. The allocation rule receives as input an initial state ${\sf
Pool}(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 ${\sf Buy}(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
${\sf Sell}(Y)$ order, the user obtains $v^{\prime}/r$ units of $X$ for the
$v^{\prime}$ units of $Y$ sold. We require that for a ${\sf Buy}(X)/{\sf
Sell}(Y)$ order, $r^{\prime}\geq r$; and for a ${\sf Buy}(Y)/{\sf Sell}(X)$
order, $1/r^{\prime}\geq 1/r$.

#### Invariant on pool state.

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

#### Potential function.

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

$\Phi(x,y)=\Phi(x^{\prime},y^{\prime}).$

In practice, the most widely adopted approach is a constant-product market
maker where $\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:

$(x-\delta x)(y-\delta y)=xy.$

#### Assumptions on the potential function.

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

###  2.2 Arbitrage Resilience

Arbitrage resilience means that an arbitrager has no strategy such that it
gets a net gain in one asset without any loss in the other.

######  Definition 2.1 (Arbitrage resilience).

We say that a mechanism satisfies arbitrage resilience iff given any initial
pool state, any input vector of orders, with probability $1$, the following
must hold: there does not exist a subset of orders whose joint outcomes result
in $\delta x\geq 0$ net gain in $X$ and $\delta y\geq 0$ net gain in $Y$, such
that at least one of $\delta x$ and $\delta y$ is strictly greater than $0$.

The definition above is consistent with Ferreira and Parkes [FP23]’s notion of
no risk-free return, although their scheme cannot guarantee no risk-free
return (i.e., arbitrary resilience), whereas ours does.

######  Remark 2.2.

The above definition of arbitrage resilience inherently implies that an
arbitrager (e.g., block producer) cannot make risk-free profit even when it
can 1) fully control the block contents; 2) control the sequencing of orders
within the block; 3) inject its own orders; and 4) drop others’ orders.

###  2.3 Time-of-Arrival Model

We introduce a time-of-arrival model that captures the scenario when the
underlying consensus layer has a decentralized block proposal process that
provides sequencing fairness [KZGJ20, KDK22, KDL+21]. Specifically, we assume
that the proposed block promises to sequence the transactions according to
their arrival order.

More specifically, we assume that a user’s intrinsic type is of the form
$(t,v,r,\alpha)$ where $(t,v,r)$ denotes the user’s true valuation and budget,
and $\alpha$ denotes the user’s arrival time — a smaller $\alpha$ means that
the user arrives earlier.

#### Strategy space.

Given its intrinsic type $(t,v,r,\alpha)$, a strategic user is allowed to post
zero or multiple bids of the form $(\\_,\\_,\\_,\alpha^{\prime})$ where
$\alpha^{\prime}\geq\alpha$. In other words, a strategic user is allowed to
delay the posting of its order, but it cannot post orders into the past.
Similarly, in this model, a strategic user also cannot censor honest users’
orders.

######  Remark 2.3 (Why the time-of-arrival model does not trivialize the
problem).

Jumping ahead, our incentive compatibility notions are in the ex-post setting,
i.e., incentive compatibility is guaranteed even when a strategic player may
post orders that depend on all other users’ orders. In this sense, our time-
of-arrival model captures a possible rushing attack: a strategic user with a
faster network link can submit an order after seeing others’ orders, and its
order may still arrive earlier than the dependent ones. In other words, the
field $\alpha$ should be viewed as the time the order actually arrives, not
when the order was initially submitted to the network.

###  2.4 Incentive Compatibility

#### Partial ordering among outcomes.

To define incentive compatibility, 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=({\sf Buy}(X),v,r,\\_)$.
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})\preceq_{T}(\delta x_{1},\delta y_{1})$, if one of the
following is true:

  * •

$\delta x_{0}\leq\delta x_{1}$, $\delta y_{0}\leq\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})$.

  * •

$\delta x_{0}\leq\delta x_{1}\leq v$ (or $q\leq\delta x_{1}\leq\delta x_{0}$),
and $r(\delta x_{1}-\delta x_{0})\geq\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.

The reason why we define only a partial ordering and allow some outcomes to be
incomparable is because a strategic user (e.g., whose intrinsic demand is to
buy up to $v$ units of $X$) can act arbitrarily, which may cause its net gain
$\delta x$ in $X$ to be either negative, or greater than the intrinsic demand
$v$. We allow some of these outcomes to be incomparable. For example, suppose
relative to $(\delta x_{0},\delta y_{0})$, the latter outcome $(\delta
x_{1},\delta y_{1})$ buys some extra units at a margial price better than the
specified rate $r$, but it overshoots the intrinsic demand, then these two
outcomes are incomparable.

Finally, the case for other types including ${\sf Buy}(Y)$, ${\sf Sell}(X)$,
and ${\sf Sell}(Y)$ types, a partial ordering can be symmetrically defined —
we give the full definition of the partial ordering in Appendix A.

#### Incentive compatibility.

Since in our paper, we consider deterministic mechanisms, we will define
incentive compatibility 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 ${\sf
out}^{u}(x_{0},y_{0},{\bf b})$ to denote the outcome of user $u$ when the
mechanism is executed over initial pool state ${\sf Pool}(x_{0},y_{0})$, and a
vector of orders ${\bf b}$.

######  Definition 2.4 (Incentive compatibility).

Given a deterministic swap mechanism, we say that it satisfies incentive
compatibility (w.r.t. some partial ordering relation $\preceq_{T}$), iff for
any initial pool state ${\sf Pool}(x_{0},y_{0})$, for any vector of orders
${\bf b}_{-u}$ belonging to all other users except $u$, for any intrinsic type
$T$ of the strategic user $u$, for any possible strategic order vector ${\bf
b^{\prime}}$ of the user $u$, either ${\sf out}^{u}(x_{0},y_{0},{\bf
b}_{-u},HS(T))\succeq_{T}{\sf out}^{u}(x_{0},y_{0},{\bf b}_{-u},{\bf
b}^{\prime})$ or ${\sf out}^{u}(x_{0},y_{0},{\bf b}_{-u},HS(T))$ and ${\sf
out}^{u}(x_{0},y_{0},{\bf b}_{-u},{\bf b}^{\prime})$ are incomparable w.r.t.
$\preceq_{T}$.

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

Our swap mechanism Input: A current pool state ${\sf Pool}(x_{0},y_{0})$, and
a vector of orders ${\bf b}$. Since the mechanism does not make use of the
auxiliary information field, we simply assume each order is a tuple of the
form $(t,v,r)$. Mechanism: 1. Let $r_{0}:=r(x_{0},y_{0})$ be the initial
exchange rate. Ignore all ${\sf Buy}(X)/{\sf Sell}(Y)$ orders whose specified
rate $r<r_{0}$, and ignore all ${\sf Buy}(Y)/{\sf Sell}(X)$ orders whose
specified rate $r>r_{0}$. Let ${\bf b}^{\prime}$ be the remaining orders. 2.
Let $\sigma=\sum_{(t,v,r)\in{\bf b}^{\prime}}\beta(t,v,r)$ where
$\beta(t,v,r)=\begin{cases}v&\text{ if }t={\sf Buy}(X)\\\ -v&\text{ if }t={\sf
Sell}(X)\\\ -v/r_{0}&\text{ if }t={\sf Buy}(Y)\\\ v/r_{0}&\text{ if }t={\sf
Sell}(Y)\end{cases}$ We call $\sigma\geq 0$ the ${\sf Buy}(X)/{\sf
Sell}(Y)$-dominant case, and $\sigma<0$ the ${\sf Buy}(Y)/{\sf
Sell}(X)$-dominant case. 3. The ${\sf Buy}(X)/{\sf Sell}(Y)$-dominant case:
(a) Sort ${\bf b}^{\prime}$ such that all the ${\sf Buy}(Y)$ orders appear in
front of the ${\sf Buy}(X)$ orders. Write the resulting list of orders as
$\\{(t_{i},v_{i},r_{i})\\}_{i\in[n^{\prime}]}$. (b) Henceforth we assume that
there exists an index $j\in[n^{\prime}]$ such that
$\sum_{i=1}^{j}\beta(t_{i},v_{i},r_{i})=0$. If not, we can find the smallest
index $j\in[n^{\prime}]$ such that $\sum_{i=1}^{j}\beta(t_{i},v_{i},r_{i})>0$,
and split the $j$-th order into two orders $(t_{j},v_{j,0},r_{j})$ and
$(t_{j},v_{j,1},r_{j})$, resulting in a new list with $n^{\prime}+1$ orders,
such that $v_{j,0}+v_{j,1}=v_{j}$, and moreover, index $j$ of the new list
satisfies this condition. (c) Phase 1: Fully execute the first $j$ orders at
the initial rate $r_{0}$.  (d) Phase 2: For each $i\geq j+1$ in sequence,
fulfill as much of the $i$-th remaining order as possible, that is, pick the
largest $v\leq v_{i}$ such that subject to the constant-function market maker
$\Phi$, the new market rate $r\leq r_{i}$ if $v$ units are to be executed;
execute $v$ units of the $i$-th order.  4. The ${\sf Buy}(Y)/{\sf
Sell}(X)$-dominant case is symmetric and we describe it below for
completeness. (a) Sort ${\bf b}^{\prime}$ such that all the ${\sf Buy}(Y)$
orders appear after the ${\sf Buy}(X)$ orders. Write the resulting list of
orders as $\\{(t_{i},v_{i},r_{i})\\}_{i\in[n^{\prime}]}$. (b) Henceforth we
assume that there exists an index $j\in[n^{\prime}]$ such that
$\sum_{i=1}^{j}\beta(t_{i},v_{i},r_{i})=0$. If not, we can find the smallest
index $j\in[n^{\prime}]$ such that
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}-}\sum_{i=1}^{j}\beta(t_{i},v_{i},r_{i})>0$,
and split the $j$-th order into two orders $(t_{j},v_{j,0},r_{j})$ and
$(t_{j},v_{j,1},r_{j})$, resulting in a new list with $n^{\prime}+1$ orders,
such that $v_{j,0}+v_{j,1}=v_{j}$, and moreover, index $j$ of the new list
satisfies this condition. (c) Phase 1: Fully execute the first $j$ orders at
the initial rate $r_{0}$. (d) Phase 2: For $i\geq j+1$ in sequence, fulfill as
much of the $i$-th remaining order as possible, that is, pick the largest
$v\leq v_{i}$ such that subject to the constant-function market maker $\Phi$,
the new market exchange rate
$r{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\geq}r_{i}$
if $v$ units are to be executed; execute $v$ units of the $i$-th order. Figure
1: Our swap mechanism

##  3 Our Swap Mechanism

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

######  Definition 3.1 (Market exchange rate).

Given a pool state ${\sf Pool}(x,y)$, the current market exchange rate is
defined as

$r(x,y)=\frac{\partial\Phi/\partial x}{\partial\Phi/\partial y}(x,y).$

Intuitively, it means that to buy an infinitesimally small $dx$ amount of $X$,
we need to pay $r(x,y)\cdot dx$ units of $y$.

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.

###  3.1 Construction

Our swap mechanism has two phases. In phase 1 (line 3c and 4c), the mechanism
matches ${\sf Buy}(X)$ orders with ${\sf Buy}(Y)$ orders, and (partially)
executes them at the initial rate $r_{0}$, such that at the end, there is no
change to the initial pool state ${\sf Pool}(x_{0},y_{0})$. Phase 2 (line 3d
and 4d) is a ${\sf Buy}(X)$-only phase, in which a sequence of ${\sf Buy}(X)$
orders (or ${\sf Buy}(Y)$ orders) are (partially) executed one by one. In
phase 2, when the mechanism attempts to execute an order, it will execute as
much as possible until either the demand has been fulfilled, or the new market
price has reached the asking price. The details of the mechanism are described
in Figure 1.

In the sorting steps (Lines 3a and 4a), we may need to break ties among
identical orders. We suggest two approaches for tie-breaking:

  * •

In the presence of a centralized block proposer (i.e., when the arbitrager can
be in full control of block creation), we suggest random tie-breaking. Note
that the random tie-breaking is enforced by the mechanism (i.e., the smart
contract). This ensures that the miner or block producer cannot auction off
favorable positions in the block to arbitragers or users.

  * •

If the block proposal process is decentralized ensures sequencing fairness, we
suggest tie-breaking according to the time of arrival. Section 3.3 and Section
4 show that this approach allows us to achieve incentive compatibility in the
time-of-arrival model.

###  3.2 Proof of Arbitrage Resilience

We now prove that our swap mechanism satisfies arbitrage resilience regardless
of how ties are broken in Lines 3a and 4a. As mentioned earlier, the arbitrage
resilience property holds even when the arbitrager is in full control of block
creation, can drop or inject orders, and can control the sequencing of orders
within the block.

######  Theorem 3.2 (Arbitrage resilience).

The swap mechanism in Figure 1 satisfies arbitrage resilience. In particular,
this holds no matter how ties are broken in Lines 3a and 4a.

###### Proof.

We prove it for the ${\sf Buy}(X)/{\sf Sell}(Y)$-dominant case, since the
${\sf Buy}(Y)/{\sf Sell}(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 ${\sf Pool}(x_{0},y_{0})$. In phase 2, it executes only
${\sf Buy}(X)/{\sf Sell}(Y)$ orders. Due to increasing marginal cost (4.1), in
Phase 2, all the (partially) executed ${\sf Buy}(X)/{\sf Sell}(Y)$ orders
enjoy a rate that is at least $r_{0}$. Therefore, all the (partially) executed
${\sf Buy}(Y)/{\sf Sell}(X)$ orders enjoy a rate of $r_{0}$, and all the
(partially) executed ${\sf Buy}(X)/{\sf Sell}(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. ∎

###  3.3 A Refinement of the Mechanism for the Time-of-Arrival Model

In the time-of-arrival model, we consider the mechanism described in Figure 1
with the following refinements — for this variant we can additionally prove
incentive compatibility (see Section 4).

  * •

We require the sorting in Lines 3a and 4a to be stable, that is, in the sorted
outcome, the relative ordering among all identical ${\sf Buy}(Y)$ orders must
respect the arrival order; the same holds for all ${\sf Buy}(X)$ orders.

  * •

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

######  Theorem 3.3 (Incentive compatibility in the time-of-arrival model).

Suppose $\Phi$ is concave, increasing, and differentiable. In the time-of-
arrival model, the above refined swap mechanism satisfies incentive
compatibility (see Definition 2.4).

The proof of Theorem 3.3 is provided in Section 4.

##  4 Proof of Incentive Compatibility

###  4.1 Useful Facts

We first prove a few useful facts.

######  Fact 4.1 (Increasing marginal cost).

Suppose that $\Phi$ is increasing, differentiable, and concave. Given two pool
states ${\sf Pool}(x,y),{\sf Pool}(x^{\prime},y^{\prime})$ such that
$\Phi(x,y)=\Phi(x^{\prime},y^{\prime})$, and $x^{\prime}\leq x$, it must be
that $r(x,y)\leq r(x^{\prime},y^{\prime})$. In other words, the price of $X$
goes up if the pool has less supply of $X$.

###### Proof.

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

######  Fact 4.2 (No free lunch).

Suppose $(\delta x,\delta y)$ is the outcome resulting from the execution of a
single order in the swap mechanism in Figure 1. If at least one of $\delta x$
and $\delta y$ is non-zero, then $\delta x\cdot\delta y<0$.

###  4.2 Incentive Compatibility Proof

We now prove Theorem 3.3. Our mechanism is deterministic, so a deterministic
strategy yields a deterministic outcome. Recall that a user has a partial
ordering among the outcomes. Henceforth, if two outcomes satisfy
$(v_{1},r_{1})\succeq(v_{2},r_{2})$, we say that $(v_{1},r_{1})$ is at least
as good as $(v_{2},r_{2})$.

Suppose that the strategic user $u$’s type is
$(t^{*},v^{*},r^{*},\alpha^{*})$, its strategic order vector is ${\bf
b}_{u}:=\\{(t_{j},v_{j},r_{j},\alpha_{j})\\}_{j}$, the initial state is ${\sf
Pool}(x_{0},y_{0})$, and the order vector from all other users is ${\bf
b}_{-u}$.

######  Fact 4.3.

Given the initial state ${\sf Pool}(x_{0},y_{0})$, the order vector from other
users ${\bf b}_{-u}$, and a strategic order vector ${\bf
b}_{u}:=\\{(t_{j},v_{j},r_{j},\alpha_{j})\\}_{j}$, there exists an alternative
strategic vector ${\bf b}^{\prime}_{u}$ which contains only ${\sf Buy}(X)$ and
${\sf Sell}(X)$-type (or ${\sf Buy}(Y)$ and ${\sf Sell}(Y)$-type) order, such
that the outcome of ${\bf b}^{\prime}_{u}$ is the same as the outcome of ${\bf
b}_{u}$.

###### Proof.

Since the mechanism is deterministic, given the initial state ${\sf
Pool}(x_{0},y_{0})$, order vector from all other users ${\bf b}_{-u}$, and the
strategic order vector ${\bf b}_{u}$, one can compute the whole order
execution trace of the mechanism. For an order $b=({\sf
Sell}(Y),v_{j},r_{j},\alpha_{j})$ in ${\bf b}_{u}$, if it is not executed,
then it can be replaced with a $({\sf Buy}(X),0,r_{j},\alpha_{j})$. If it is
partially fulfilled, let $(x_{\rm start},x_{\rm end})$ denote the amount of
asset $X$ in the pool right before and right after $b$ is executed,
respectively. Let $r_{\rm end}$ denote the market exchange rate at $x_{\rm
end}$. Then $b$ can be replaced with an order $({\sf Buy}(X),x_{\rm
start}-x_{\rm end},r_{\rm end},\alpha_{j})$, without changing the outcome.
Similarly, we can replace a ${\sf Buy}(Y)$-type order with a ${\sf
Sell}(X)$-type order without changing the outcome. The fact thus follows. ∎

######  Lemma 4.4.

Suppose $\Phi$ is concave, increasing, and differentiable. For any strategic
order vector ${\bf b}_{u}$, there exists a single order $b^{\prime}_{u}$ such
that 1) $b^{\prime}_{u}$ results in an outcome at least as good as ${\bf
b}_{u}$; 2) the arrival time used in $b^{\prime}_{u}$ is no earlier than the
earliest arrival time in ${\bf b}_{u}$; and 3) either
$b^{\prime}_{u}=(\\_,0,\\_,\\_)$ or $b^{\prime}_{u}$ would be completely
fulfilled under ${\sf Pool}(x_{0},y_{0})$ and ${\bf b}_{-u}$.

###### Proof.

To prove this lemma, we first show that we can coalesce all the ${\sf
Buy}(X)/{\sf Sell}(Y)$-type orders into one, and all the ${\sf Sell}(X)/{\sf
Buy}(Y)$-type orders into one, as stated in the following claim.

######  Claim 4.5.

Suppose $\Phi$ is concave, increasing, and differentiable. For any strategic
order vector ${\bf b}_{u}$, if it contains both ${\sf Buy}(X)/{\sf
Sell}(Y)$-type and ${\sf Sell}(X)/{\sf Buy}(Y)$-type orders, there exists
another order vector ${\bf b}^{\prime}_{u}$ which contains a single ${\sf
Buy}(X)/{\sf Sell}(Y)$-type order and a single ${\sf Sell}(X)/{\sf
Buy}(Y)$-type order such that 1) ${\bf b}^{\prime}_{u}$ results in an outcome
at least as good as ${\bf b}_{u}$; 2) the arrival times used in ${\bf
b^{\prime}}_{u}$ are no earlier than the earliest arrival time in ${\bf
b}_{u}$; and 3) an order in ${\bf b}^{\prime}_{u}$ is either of the form
$(\\_,0,\\_,\\_)$ or it would be completely fulfilled under ${\sf
Pool}(x_{0},y_{0})$ and ${\bf b}_{-u}$.

###### Proof.

According to 4.3, we can assume that ${\bf b}_{u}$ contains only ${\sf
Buy}(X)$ and ${\sf Sell}(X)$-type orders. Let ${\bf b}_{\sf Sell}$ and ${\bf
b}_{\sf Buy}$ denote the vector of ${\sf Sell}(X)$-type and ${\sf
Buy}(X)$-type orders in ${\bf b}_{u}$, respectively. Without loss of
generality, assume that given ${\bf b}_{-u}$ and ${\bf b}_{u}$, we have the
${\sf Buy}(X)$/${\sf Sell}(Y)$-dominant case, (the ${\sf Buy}(Y)$/${\sf
Sell}(X)$-dominant case is symmetric).

For the ${\sf Buy}(X)$/${\sf Sell}(Y)$-dominant case, all ${\sf Sell}(X)$-type
orders in ${\bf b}_{\sf Sell}$ will be executed at the initial exchange rate
$r_{0}$. Therefore, consider an order $b=({\sf Sell}(X),v,r,\alpha)$, where
$v$ denotes the total units of orders in ${\bf b}_{\rm Sell}$, $r$ is the
minimum asking rate in ${\bf b}_{\rm Sell}$, and $\alpha$ is the earliest
arrival time in ${\bf b}_{u}$. Then a strategic order vector $({\bf b}_{\rm
Buy},b)$ results in the same outcome as ${\bf b}_{u}$.

Now consider an order $b^{\prime}=({\sf
Buy}(X),v^{\prime},r^{\prime},\alpha^{\prime})$, where $v^{\prime}$ is the
total units of order executed in ${\bf b}_{\rm Buy}$, $r^{\prime}$ is the
maximum asking rate in ${\bf b}_{\rm Buy}$, and $\alpha^{\prime}$ is the
earliest arrival time of the order in ${\bf b}_{\rm Buy}$ that is partially
fulfilled. Let ${\bf b}^{\prime}_{u}=(b^{\prime},b)$. Compared to the units
executed in ${\bf b}_{\rm 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 ${\bf b}_{\rm Buy}$.
Therefore, all units in $b^{\prime}$ will be executed. Moreover, by the
increasing marginal cost (4.1), the exchange rate for $b^{\prime}$ is no more
than the average exchange rate for all orders in ${\bf b}_{\rm Buy}$. This
means that ${\bf b}^{\prime}_{u}$ results in an outcome that is at least as
good as $({\bf b}_{\rm Buy},b)$ according to the partial ordering. By the
transitivity, ${\bf b}^{\prime}_{u}$ results in an outcome that is at least as
good as ${\bf b}_{u}$. ∎

Next, we show that for any order vector ${\bf b}_{u}$ that contains a single
${\sf Buy}(X)/{\sf Sell}(Y)$-type order and a single ${\sf Sell}(X)/{\sf
Buy}(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.

######  Claim 4.6.

Suppose $\Phi$ is concave, increasing, and differentiable. For any order
vector ${\bf b}_{u}$ that contains a single ${\sf Buy}(X)/{\sf Sell}(Y)$-type
order and a single ${\sf Sell}(X)/{\sf Buy}(Y)$-type, there exists a single
order $b^{\prime}_{u}$ such that 1) $b^{\prime}_{u}$ results in an outcome at
least as good as ${\bf b}_{u}$; 2) the arrival time in $b^{\prime}_{u}$ is no
earlier than the earliest arrival time in ${\bf b}_{u}$; and 3)
${b}^{\prime}_{u}$ is either of the form $(\\_,0,\\_,\\_)$ or it would be
completely fulfilled under ${\sf Pool}(x_{0},y_{0})$ and ${\bf b}_{-u}$.

###### Proof.

Because of 4.3, we assume that the strategic order vector ${\bf b}_{u}$
contains a single ${\sf Buy}(X)$-type order $({\sf
Buy}(X),v_{b},r_{b},\alpha_{b})$ and a single ${\sf Sell}(X)$-type order
$({\sf Sell}(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
$r_{b}<r_{0}$ or $r_{s}>r_{0}$, then the result also follows trivially.
henceforth, $r_{b}\geq r_{0}$ and $r_{s}\leq r_{0}$.

We prove it assuming the ${\sf Buy}(X)$/${\sf Sell}(Y)$-dominant case case
under the strategic order vector ${\bf b}_{u}$, since the argument for the
${\sf Buy}(Y)$/${\sf Sell}(X)$-dominant case is symmetric. For the ${\sf
Buy}(X)$/${\sf Sell}(Y)$-dominant case, if it were possible to execute all
orders at $r_{0}$, then there is more demand in terms of only ${\sf
Buy}(X)/{\sf Sell}(Y)$ than ${\sf Sell}(X)/{\sf Buy}(Y)$. In this case, Phase
1 executes all ${\sf Sell}(X)/{\sf Buy}(Y)$ orders at $r_{0}$, and Phase 2
executes only ${\sf Buy}(X)/{\sf Sell}(Y)$ orders.

#### Case $v_{s}\geq v_{b}$:

Under the original ${\bf b}_{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 ${\bf b}_{u}$ with a single order
$b^{\prime}_{u}=({\sf Sell}(X),v_{s}-v_{b},r_{s},\alpha_{s})$. Under
$b^{\prime}_{u}$, it is still the case that all ${\sf Sell}(X)$ orders are
completely executed at $r_{0}$.

Hence, we can decompose the original ${\bf b}_{u}$ equivalently into the
following steps: (i) first execute $b^{\prime}_{u}$; (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^{\prime}_{u}$ is at
least as good as ${\bf b}_{u}$.

#### Case $v_{s}<v_{b}$:

Consider the original ${\bf b}_{u}$ which consists of $({\sf
Sell}(X),v_{s},r_{s},\alpha_{s})$ and $({\sf Buy}(X),v_{b},r_{b},\alpha_{b})$.
We will analyze what happens when we replace these two orders with a single
order $b^{\prime}_{u}=({\sf Buy}(X),v_{b}-v_{s},r_{b},\alpha_{b})$. Suppose in
Phase 1 of the execution with ${\bf b}_{u}$, user $u$ sells $v_{s}$ units of
$X$ and buys $v^{\prime}\leq v_{b}$ units of $X$ at rate $r_{0}$. We separate
the rest of the proof into two cases.

  1. 1.

Case $v^{\prime}\geq v_{s}$. For the execution with ${\bf b}_{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^{\prime}_{u}$ can be viewed as follows: In Phase 1’,
$v^{\prime}-v_{s}$ units of ${\sf Buy}(X)$ will be executed at rate $r_{0}$.
Then in Phase 2’, the mechanism executes the rest $v_{b}-v^{\prime}$ units in
$b^{\prime}_{u}$ starting at rate $r_{0}$.

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

  2. 2.

Case $v^{\prime}<v_{s}$. We will view the execution of the orders $({\sf
Sell}(X),v_{s},r_{s},\alpha_{s})$ and $({\sf Buy}(X),v_{b},r_{b},\alpha_{b})$
as follows.

     * •

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.

     * •

Phase 2a: Some non-negative amount of ${\sf Buy}(X)$/${\sf Sell}(Y)$ orders
from other users are executed at a starting market rate of $r_{0}$, let
$v_{\rm other}\geq 0$ be the units of $X$ purchased. Note that if
$v^{\prime}>0$, then $v_{\rm other}=0$.

At the end of this phase, the market rate $r_{1}\geq r_{0}$ by increasing
marginal cost.

     * •

Phase 2b: Starting at rate $r_{1}\geq r_{0}$, user $u$ buys $v_{s}-v^{\prime}$
units of $X$, which changes the market rate to $r_{2}\geq r_{1}$.

     * •

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^{\prime}_{u}$ can be viewed as the following:

     * •

Phase 1’: The ${\sf Buy}(X)/{\sf Sell}(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.

     * •

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}$.

     * •

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_{\rm other}$ units of $X$ can be fulfilled. The ending market rate must be
at least $r_{1}$.

     * •

Phase 2c’: The mechanism attempts to execute $b^{\prime}_{u}$. Observe that
the total units of $X$ fulfilled in the original Phase 2a, 2b, and 2c is
$v_{\rm 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_{\rm
other}+v_{b}-v_{s}=v_{\rm other}+v_{b}-v^{\prime}$. Therefore, it must be that
all of $b^{\prime}_{u}$ can be fulfilled and the ending market rate is at most
$r_{3}\leq r_{b}$.

Henceforth, we use the notation ${\sf Pay}(\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

${\sf Pay}(\text{Phase 1})+{\sf Pay}(\text{Phase 2b})\geq 0,\quad{\sf
Pay}(\text{Phase 2c})\geq{\sf Pay}(\text{Phase 2c'}).$

Therefore,

${\sf Pay}(\text{Phase 1})+{\sf Pay}(\text{Phase 2b})+{\sf Pay}(\text{Phase
2c})\geq{\sf Pay}(\text{Phase 2c'}).$

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

∎

Lemma 4.4 follows by combining 4.5 and 4.6. ∎

######  Lemma 4.7.

Suppose $\Phi$ is concave, increasing, and differentiable. Given any initial
state ${\sf Pool}(x_{0},y_{0})$, any order vector ${\bf b}_{-u}$, any true
arrival time $\alpha^{*}$ of user $u$, given an order $b^{\prime}_{u}$ with an
arrival time later than $\alpha^{*}$, there exists another order $b_{u}$ with
an arrival time exactly $\alpha^{*}$, and moreover, user $u$’s outcome under
$b_{u}$ is at least as good as its outcome under $b^{\prime}_{u}$, and $b_{u}$
is either completely executed or of the form $(\\_,0,\\_,\\_)$.

###### Proof.

Due to 4.3, we may assume that $b_{u}$ is either a ${\sf Buy}(X)$ or ${\sf
Sell}(X)$ order. We prove it for a ${\sf Buy}(X)$ order, since the case for a
${\sf Sell}(X)$ order is symmetric. Let $v$ be the amount of $X$ bought by
$b^{\prime}_{u}$. We shall assume that $v>0$ since the case $v=0$ is trivial.
Consider an order $b_{u}=({\sf Buy}(X),v,+\infty,\alpha^{*})$. Clearly,
$b_{u}$ will buy $v$ units of $X$.

We consider the following cases:

  * •

$b_{u}$ buys $v_{0}>0$ units at $r_{0}$ in Phase 1, and then buys $v_{1}\geq
0$ units in Phase 2 at a starting rate of $r_{0}$ and an ending rate of
$r_{1}\geq r_{0}$. In this case, by delaying the arrival time,
$b^{\prime}_{u}$ can buy at most $v^{\prime}_{0}\leq v_{0}$ units in Phase 1
at $r_{0}$, and it needs to buy $v-v^{\prime}_{0}\geq v_{1}$ in Phase 2.
Therefore, for $b^{\prime}_{u}$, 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^{\prime}_{u}$.

  * •

$b_{u}$ buys all $v$ units in Phase 2. Since $b^{\prime}_{u}$ delayed the
arrival, the order can be considered no earlier than $b_{u}$. Thus, before the
mechanism tries to execute $b^{\prime}_{u}$ 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^{\prime}_{u}$ will have an average price no better than
$b_{u}$.

∎

Due to Lemmas 4.4 and 4.7, it suffices to consider strategies that submit a
single order, declare the true arrival time $\alpha^{*}$, and moreover, either
the order has a $0$ amount or it will be completely executed under ${\sf
Pool}(x_{0},y_{0})$ and ${\bf b}_{-u}$ — henceforth, we call such strategies
as admissible, single-order strategies. We can complete the proof of Theorem
3.3 by showing the following lemma.

######  Lemma 4.8.

Suppose $\Phi$ is concave, increasing, and differentiable. For any admissible
and single-order strategy $S$, the honest strategy results in an outcome that
is at least as good as or incomparable to strategy $S$.

###### Proof.

We prove it for the case when user $u$’s type is either $({\sf
Buy}(X),v^{*},r^{*},\alpha^{*})$ or $({\sf Sell}(X),v^{*},r^{*},\alpha^{*})$.
The case for ${\sf Buy}(Y)$/${\sf Sell}(Y)$ is symmetric. Given two outcomes
${\sf out}_{0}=(\delta x_{0},\delta y_{0})$ and ${\sf out}_{1}=(\delta
x_{1},\delta y_{1})$ and a true demand $\delta x^{*}$ for $X$, we say that
they are on the same side of the goal $\delta x^{*}$ iff $(\delta x_{0}-\delta
x^{*})\cdot(\delta x_{1}-\delta x^{*})\geq 0$. We say that ${\sf out}_{0}$ is
at least as close as ${\sf out}_{1}$ towards the goal iff $|\delta
x_{0}-\delta x^{*}|\leq|\delta x_{1}-\delta x^{*}|$, and we say that ${\sf
out}_{0}$ is closer to the goal than ${\sf out}_{1}$ iff $|\delta x_{0}-\delta
x^{*}|<|\delta x_{1}-\delta x^{*}|$.

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 $(\delta x_{0}-\delta x_{1})\cdot(\delta
y_{1}-\delta y_{0})<0$, then $(\delta x_{1},\delta y_{1})\nsucceq(\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^{*}\cdot(\delta x_{0}-\delta x_{1})$, then $(\delta
x_{0},\delta y_{0})\nsucceq(\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}\geq r^{*}\cdot(\delta x_{0}-\delta
x_{1})$, then $(\delta x_{0},\delta y_{0})\nsucceq(\delta x_{1},\delta
y_{1})$.

Due to 4.3, we may assume that the strategic order must be of the type ${\sf
Buy}(X)$ or ${\sf Sell}(X)$. Further, as shown in the following fact, we can
in fact assume that the strategic order adopts the true time of arrival
$\alpha^{*}$, 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.

#### Case 1:

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 ${\sf
Buy}(X)$, it submits a single ${\sf Sell}(X)$ order; or vice versa. It must be
that $\delta x\cdot\delta x^{\prime}\leq 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 (4.2), at least one of the inequalities
$\delta x\cdot\delta y\leq 0$ and $\delta x^{\prime}\cdot\delta y^{\prime}\leq
0$ must be strict; moreover, when an equality holds, both arguments of the
product must be zero. Because $\delta x\cdot\delta x^{\prime}\leq 0$, this
implies that $(\delta x-\delta x^{\prime})(\delta y-\delta y^{\prime})<0$; by
the above rule R1, the honest outcome is at least as good as or incomparable
the strategic one.

#### Case 2:

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.

  * •

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\neq\delta x^{\prime}$.

  * •

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.

  * •

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., $|\delta x|<|\delta x^{\prime}|\leq|\delta x^{*}|=v^{*}$.

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^{*}$. In the case of ${\sf Buy}(X)$, this is strictly
larger than $r^{*}$; in the case of ${\sf Sell}(X)$, this is strictly less
than $r^{*}$.

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^{*}$ 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.

  * •

Case 2d: The honest outcome and the strategic outcome are on different sides
of the goal, i.e., $|\delta x|<|\delta x^{*}|=v^{*}<|\delta x^{\prime}|$.

In this case, $\delta x\neq 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^{*}$.

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^{*}$ in the strategic outcome. By
rule R3, the strategic outcome cannot be at least as good as the honest
outcome.

∎

## Acknowledgments

This work is in part supported by NSF awards 2212746, 2044679, 1704788, a Pac
kard Fellowship, a generous gift from the late Nikolai Mushegian, a gift from
Google, and an ACE center grant from Algorand Foundation.

## References

  * [AEC21] Guillermo Angeris, Alex Evans, and Tarun Chitra.  A note on bundle profit maximization, 2021.
  * [BCL21] Massimo Bartoletti, James Hsin-yu Chiang, and Alberto Lluch-Lafuente.  A theory of automated market makers in defi.  CoRR, 2021.
  * [BCLL22] Massimo Bartoletti, James Hsin-yu Chiang, and Alberto Lluch Lafuente.  Maximizing extractable value from automated market makers.  In Financial Cryptography and Data Security: 26th International Conference, FC 2022, Grenada, May 2–6, 2022, Revised Selected Papers, 2022\.
  * [BDKJ23] Kushal Babel, Philip Daian, Mahimna Kelkar, and Ari Juels.  Clockwork finance: Automated analysis of economic security in smart contracts.  In IEEE Symposium on Security and Privacy, 2023.
  * [BGR23] Maryam Bahrani, Pranav Garimidi, and Tim Roughgarden.  Transaction fee mechanism design with active block producers, 2023.
  * [BO22] Joseph Bebel and Dev Ojha.  Ferveo: Threshold decryption for mempool privacy in BFT networks.  Cryptology ePrint Archive, Paper 2022/898, 2022.  https://eprint.iacr.org/2022/898.
  * [CF23] Andrea Canidio and Robin Fritsch.  Batching trades on automated market makers.  In AFT, 2023.
  * [CF24] Andrea Canidio and Robin Fritsch.  Arbitrageurs’ profits, lvr, and sandwich attacks: batch trading as an amm design response.  2024\.
  * [CKWN16] Miles Carlsten, Harry Kalodner, S. Matthew Weinberg, and Arvind Narayanan.  On the instability of bitcoin without the block reward.  In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, 2016.
  * [CS23] Hao Chung and Elaine Shi.  Foundations of transaction fee mechanism design.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3856–3899. SIAM, 2023.
  * [dec] Challenging periods reimagined: The key role of sequencer decentralization.  https://ethresear.ch/t/challenging-periods-reimagined-the-key-role-of-sequencer-decentralization/15110.
  * [Dra] Justin Drake.  Encrypted mempools.  https://www.youtube.com/watch?v=XRM0CpGY3sw.
  * [esp] The espresso sequencer.  https://hackmd.io/@EspressoSystems/EspressoSequencer.
  * [FP23] Matheus Venturyne Xavier Ferreira and David C. Parkes.  Credible decentralized exchange design via verifiable sequencing rules.  In STOC, 2023.
  * [GPR23] Tivas Gupta, Mallesh M Pai, and Max Resnick.  The centralizing effects of private order flow on proposer-builder separation, 2023.
  * [HW22] Lioba Heimbach and Roger Wattenhofer.  Eliminating sandwich attacks with the help of game theory.  In Proceedings of the 2022 ACM on Asia Conference on Computer and Communications Security, 2022.
  * [Jos] Josojo.  Mev capturing amm (mcamm).  https://ethresear.ch/t/mev-capturing-amm-mcamm/13336.
  * [KDC22] Kshitij Kulkarni, Theo Diamandis, and Tarun Chitra.  Towards a theory of maximal extractable value I: constant function market makers.  CoRR, abs/2207.11835, 2022.
  * [KDK22] Mahimna Kelkar, Soubhik Deb, and Sreeram Kannan.  Order-fair consensus in the permissionless setting.  In APKC ’22: Proceedings of the 9th ACM on ASIA Public-Key Cryptography Workshop, 2022.
  * [KDL+21] Mahimna Kelkar, Soubhik Deb, Sishan Long, Ari Juels, and Sreeram Kannan.  Themis: Fast, strong order-fairness in byzantine consensus.  2021\.
  * [KZGJ20] Mahimna Kelkar, Fan Zhang, Steven Goldfeder, and Ari Juels.  Order-fairness for byzantine consensus.  In CRYPTO, page 451–480, 2020.
  * [Leu] F. Leupold.  Cow native amms (aka surplus capturing amms with single price clearing).  https://forum.cow.fi/t/cow-native-amms-aka-surplus-capturing-amms-with-single-price-clearing/1219/1.
  * [MMR23] Jason Milionis, Ciamac C. Moallemi, and Tim Roughgarden.  A myersonian framework for optimal liquidity provision in automated market makers.  CoRR, abs/2303.00208, 2023.
  * [QZG22] Kaihua Qin, Liyi Zhou, and Arthur Gervais.  Quantifying blockchain extractable value: How dark is the forest?  In 43rd IEEE Symposium on Security and Privacy, SP, 2022.
  * [QZLG21] Kaihua Qin, Liyi Zhou, Benjamin Livshits, and Arthur Gervais.  Attacking the defi ecosystem with flash loans for fun and profit.  In Financial Cryptography and Data Security: 25th International Conference, FC 2021, Virtual Event, March 1–5, 2021, Revised Selected Papers, Part I, 2021.
  * [RGGM23] Geoffrey Ramseyer, Mohak Goyal, Ashish Goel, and David Mazières.  Augmenting batch exchanges with constant function market makers, 2023\.
  * [Rou21] Tim Roughgarden.  Transaction fee mechanism design.  In EC, 2021.
  * [SCW23] Elaine Shi, Hao Chung, and Ke Wu.  What can cryptography do for decentralized mechanism design?  In ITCS, volume 251 of LIPIcs, pages 97:1–97:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
  * [XPCF23] Jiahua Xu, Krzysztof Paruch, Simon Cousaert, and Yebo Feng.  Sok: Decentralized exchanges (dex) with automated market maker (amm) protocols.  55(11), 2023.
  * [ZQC+21] Liyi Zhou, Kaihua Qin, Antoine Cully, Benjamin Livshits, and Arthur Gervais.  On the just-in-time discovery of profit-generating transactions in defi protocols.  In IEEE Symposium on Security and Privacy, SP, 2021.
  * [ZQG21] Liyi Zhou, Kaihua Qin, and Arthur Gervais.  A2MM: mitigating frontrunning, transaction reordering and consensus instability in decentralized exchanges.  CoRR, abs/2106.07371, 2021.
  * [ZQT+21] Liyi Zhou, Kaihua Qin, Christof Ferreira Torres, Duc Viet Le, and Arthur Gervais.  High-frequency trading on decentralized on-chain exchanges.  In IEEE Symposium on Security and Privacy, 2021.
  * [Zus] Patrick Zust.  Analyzing and preventing sandwich attacks in ethereum.  Bachelor’s thesis.

##  Appendix A Full Definition: Partial Ordering of Outcomes

We first define a most natural partial ordering among a user’s outcomes. We do
not directly define a total ordering since some outcomes may not be directly
comparable without extra information. Intuitively, suppose that a user’s type
is $({\sf Buy}(X),v,r,\\_)$, the natural partial ordering says that 1) up to
receiving at most $v$ units of $X$, every extra unit of $X$ received at a
marginal price better than $r$ is desirable; 2) every excessive unit (i.e.,
more than the $v$ amount) of $X$ received at a marginal price of more than $r$
is undesirable; 3) every unit of $X$ short-sold at a price less than $r$ is
undesirable; and 4) if the net gain in $X$ is the same in two outcomes, then
the outcome where a lower price is paid is more desirable.

#### Example.

For example, imagine that a user wants to buy $7$ units of $X$ at a desired
maximum price of $20$ — the case for sell is symmetric.

  1. 1.

Consider the following two outcomes: 1) the user gains $5$ units of $X$ at an
average price of $10$; and 2) the user gains $6$ units of $X$ at an average
price of $11$. In both cases, the order is not completely fulfilled. The
second outcome is better for the user since it can be viewed as first
achieving the first outcome and then paying $16$ for an extra unit, which is
less than the ask $20$.

  2. 2.

Now, consider the following two outcomes: 1) the $7$ units are completely
fulfilled at an average price of $10$; and 2) the user obtains $8$ units of
$X$ at an average price of $12$. The second outcome can occur if the user is
strategic and does not honestly report its desired amount or price. The first
outcome is better for the user, since the second outcome can be viewed as
achieving the first outcome and then purchasing an extra unit at a marginal
price of $12\cdot 8-7\cdot 10=26$, which is higher than the ask $20$.

  3. 3.

Finally, consider the following two outcomes 1) the $7$ units are completely
fulfilled at an average price of $10$; and 2) the user obtains $8$ units of
$X$ at an average price of $11$. The second outcome can be viewed as achieving
the first outcome and additionally purchasing an extra unit at a price of
$11\cdot 8-7\cdot 10=18$. In this case, the two outcomes are incomparable
unless we can quantify the utility the user gains from the extra unit that it
did not plan for initially.

We now formally define this natural partial ordering.

#### A natural partial ordering.

We use a tuple $T=(t,v,r,\alpha)$ to represent the type of a user, where
$(t,v,r)$ denotes the user’s true demand and valuation, and $\alpha$ denotes
any auxiliary information. For example, suppose $T=({\sf Buy}(X),v,r,\\_)$, it
means the user wants to obtain $v$ units of $X$ at an exchange rate of $r$ or
better.

To define the natural partial ordering, we will focus on the case of ${\sf
Buy}(X)$/${\sf Sell}(X)$ orders; and the case for ${\sf Buy}(Y)$/${\sf
Sell}(Y)$ orders are symmetric, except that we replace the usage of the rate
$r$ with $1/r$. Based on a user’s type $T=(t,v,r,\\_)$, we can represent the
user’s true demand as $(\delta x,r)$ where

$\delta x=\begin{cases}v&\text{ if $t={\sf Buy}(X)$}\\\ -v&\text{ if $t={\sf
Sell}(X)$}\end{cases}$

We can use a pair $(\delta x_{0},\delta y_{0})$ to denote the outcome, meaning
that the user has a net gain of $\delta x_{0}$ in $X$, and it has a net gain
of $\delta y_{0}$ in $Y$. If $\delta x_{0}$ or $\delta y_{0}$ is negative, it
means that the user has a net loss in $X$ or $Y$. Next, we give the rules for
the partial ordering $\preceq_{T}$. When the context is clear, we may omit the
subscript $T$. Given two outcomes $(\delta x_{0},\delta y_{0})$ and $(\delta
x_{1},\delta y_{1})$ and the true demand $(\delta x,r)$, we define the
following partial ordering between $(\delta x_{0},\delta x_{0})$ and $(\delta
x_{1},\delta y_{1})$:

  1. 1.

If $\delta x_{0}\geq\delta x_{1}$ and $\delta y_{0}\geq\delta y_{1}$, then
$(\delta x_{0},\delta y_{0})\succeq_{T}(\delta x_{1},\delta y_{1})$.

  2. 2.

If $\delta x_{0}\cdot(\delta x_{0}-\delta x)\leq 0$, $\delta x_{1}\cdot(\delta
x_{1}-\delta x)\leq 0$, and $r\delta x_{0}+\delta x_{1}\geq 0$, then we say
that $(\delta x_{0},\delta y_{0})\succeq_{T}(\delta x_{1},\delta y_{1})$.

  3. 3.

If $(\delta x_{0}-\delta x)(\delta x_{1}-\delta x)\geq 0$, $|\delta
x_{0}-\delta x|\leq|\delta x_{1}-\delta x|$, and $\delta y_{1}-\delta
y_{0}\leq r\cdot(\delta x_{0}-\delta x_{1})$, then $(\delta x_{0},\delta
y_{0})\succeq_{T}(\delta x_{1},\delta y_{1})$.

  4. 4.

Finally, the transitivity rule holds, that is, if there exists an intermediate
outcome $(\delta x^{\prime},\delta y^{\prime})$ such that $(\delta
x_{1},\delta x_{1})\succeq_{T}(\delta x^{\prime},\delta y^{\prime})$ and
$(\delta x^{\prime},\delta y^{\prime})\succeq_{T}(\delta x_{0},\delta y_{0})$,
then it holds that $(\delta x_{1},\delta y_{1})\succeq_{T}(\delta x_{0},\delta
y_{0})$.

In particular, the first rule roughly says a user always prefers an outcome in
which it gains at least as much in either asset. The second rule can be
interpreted as follows: the pre-conditions $\delta x_{0}\cdot(\delta
x_{0}-\delta x)\leq 0$ and $\delta x_{1}\cdot(\delta x_{1}-\delta x)\leq 0$
mean that we have satisfied part of the demand (i.e., between $0$ and the
entirety of the demand). The rule says that if this is the case, then the
partial ordering is decided by the natural utility function $r\delta
x_{0}+\delta y_{0}$. The third rule can be interpreted as follows: the part
$(\delta x_{0}-\delta x)(\delta x_{1}-\delta x)\geq 0$ means that $\delta
x_{0}$ and $\delta x_{1}$ are on the same side of $\delta x$, the part
$|\delta x_{0}-\delta x|\leq|\delta x_{1}-\delta x|$ means that $\delta x_{0}$
is closer to the goal $\delta x$ than $\delta x_{1}$. The entire third rule
says that if relative to $(\delta x_{1},\delta y_{1})$, the outcome $(\delta
x_{0},\delta y_{0})$ makes progress towards satisfying the goal while enjoying
a marginal price of $r$ or better (where better means sell high or buy low),
then $(\delta x_{0},\delta y_{0})\succeq_{T}(\delta x_{1},\delta y_{1})$.
Conversely, if relative to $(\delta x_{0},\delta y_{0})$, the outcome $(\delta
x_{1},\delta y_{1})$ goes in the opposite direction of satisfying the goal,
while suffering from a marginal price of $r$ or worse, then $(\delta
x_{1},\delta y_{1})\preceq_{T}(\delta x_{0},\delta y_{0})$. The last rule is
the standard transitivity rule for any partial ordering relation.

We can mechanically verify that all of the above rules are internally
consistent.

##  Appendix B No Short-Selling Variant

In this section, we consider a variant of our scheme with the following
modifications:

  1. 1.

The mechanism checks the balance of a user (in either asset) and ensures that
the user’s account balance does not go negative. In other words, no user is
allowed to short-sell;

  2. 2.

Suppose the user’s belief of the rate $r^{\prime}$ is greater than the market
rate $r$, then the user’s honest strategy would be to sell as much $Y$ as
possible as long as the market rate stays below $r^{\prime}$; and vice versa.

For this no-short-selling variant, it is natural to define a total ordering
among outcomes. Specifically, for a user whose belief of the rate is
$r^{\prime}$, given a position of $(x,y)$, i.e., when it holds $x$ units of
$X$ and $y$ units of $Y$, then the value of the position can be calculated as
$r^{\prime}x+y$. It is easy to verify that this total ordering is a refinement
of the partial ordering defined in Appendix A. We shall prove that our
incentive compatibility guarantee holds with respect to this natural total
ordering. Specifically, since no outcomes are incomparable under a total
ordering, incentive compatibility (Definition 2.4) now simply means that the
honest strategy maximizes a user’s utility.

###  B.1 Definition

We first make a slight modification to the syntax of the swap mechanism.

#### Partial fulfillment swap mechanism without short-selling.

Recall that every user has a position ${\sf Pos}(x,y)$ that denotes its
balance in $X$ and $Y$, and we require that $x\geq 0,y\geq 0$.

Partial fulfillment swap mechanism without short-selling is defined similarly
as the partial fulfillment mechanism of Section 2, except with the following
modifications. We now additionally assume that the mechanism’s allocation rule
has an extra input which is the current positions of all users. Further, each
user has a unique identifier that is included in the $\alpha$ field of the
order, such that the mechanism can see who submitted the order. Note that
there can be multiple orders coming from the same user. The mechanism is
required to produce an outcome such that no user’s ending position is negative
in either $X$ or $Y$.

For our incentive compatibility properties defined earlier, we require the
same properties to hold no matter what the users’ initial positions are.

Our swap mechanism: variant with no short-selling Input: A current pool state
${\sf Pool}(x_{0},y_{0})$, and a vector of orders ${\bf b}$, and all users’
initial positions. Mechanism: 1. Let $r_{0}:=r(x_{0},y_{0})$ be the initial
rate. Ignore all ${\sf Buy}(X)$/${\sf Sell}(Y)$ orders whose specified rate
$r<r_{0}$, and ignore all ${\sf Buy}(Y)$/${\sf Sell}(X)$ orders whose
specified rate $r>r_{0}$. Let ${\bf b}^{\prime}$ be the remaining orders. 2.
Attempt to safe-execute all orders in ${\bf b^{\prime}}$ at rate $r_{0}$
(without actually executing them): if the sum of the net gain in $X$ of all
users is non-negative, we call it the ${\sf Buy}(X)/{\sf Sell}(Y)$ case;
otherwise we call it the ${\sf Buy}(Y)/{\sf Sell}(X)$ case. 3. The ${\sf
Buy}(X)$/${\sf Sell}(Y)$-dominant case: (a) Sort ${\bf b}^{\prime}$ such that
all the ${\sf Sell}(X)$ and ${\sf Buy}(Y)$ orders appear in front of the ${\sf
Sell}(Y)$ and ${\sf Buy}(X)$ orders. Write the resulting list of orders as
$\\{(t_{i},v_{i},r_{i},({u}_{i},\\_))\\}_{i\in[n^{\prime}]}$. (b) Attempt to
safe-execute orders in
$\\{(t_{i},v_{i},r_{i},({u}_{i},\\_))\\}_{i\in[n^{\prime}]}$ sequentially
(without actually executing them), let $\beta_{i}$ denote the net gain in $X$
contributed by the $i$-th order. (c) Henceforth we assume that there exists an
index $j\in[n^{\prime}]$ such that $\sum_{i=1}^{j}\beta_{i}=0$. If not, we can
find the smallest index $j\in[n^{\prime}]$ such that
$\sum_{i=1}^{j}\beta_{i}>0$, and split the $j$-th order into two orders
$(t_{j},v_{j,0},r_{j},({u}_{i},\\_))$ and
$(t_{j},v_{j,1},r_{j},({u}_{i},\\_))$, resulting in a new list with
$n^{\prime}+1$ orders, such that $v_{j,0}+v_{j,1}=v_{j}$, and moreover, index
$j$ of the new list satisfies this condition. (d) Phase 1: Safe-execute the
first $j$ orders at rate $r_{0}$. (e) Phase 2: Safe-execute each remaining
order $i\geq j+1$ in sequence. 4. The ${\sf Buy}(Y)$/${\sf Sell}(X)$-dominant
case is symmetric. Figure 2: Our swap mechanism: variant without short-selling

###  B.2 A Swap Mechanism Without Short-Selling

We now describe a variant of our earlier mechanism but now providing an
additional guarantee of no short-selling. Basically, the new mechanism is
almost the same as the old one, except that during the execution, the
mechanism always ensures that after (partially) executing every order, the
corresponding user’s position is non-negative in both $X$ and $Y$.

Henceforth, we can use the notation $(t,v,r,({u},\alpha))$ to denote an order
where $t$, $v$, and $r$ are the same as before, ${u}$ denotes the user’s
pseudonym, and $\alpha$ denotes any arbitrary auxiliary information. To
precisely capture no short-selling, we define the notion of safe-execute
below:

  1. 1.

Safe-execute in Phase 1: Do the following based on the type of the order:

     * •

$({\sf Buy}(X),v,r,(u,\\_))$: Pick the maximum possible $v^{\prime}\leq v$
such that buying $v^{\prime}$ units of $X$ will not cause user $u$’s balance
in $Y$ to go negative; and let the user $u$ buy $v^{\prime}$ units of $X$ at a
fixed rate $r_{0}$.

     * •

$({\sf Sell}(X),v,r,(u,\\_))$: Pick the maximum $v^{\prime}\leq v$ such that
selling $v^{\prime}$ units of $X$ will not cause user $u$’s balance in $X$ to
go negative; and let the user $u$ sell $v^{\prime}$ units of $X$ at a fixed
rate $r_{0}$.

     * •

$({\sf Buy}(Y),v,r,(u,\\_))$ or $({\sf Sell}(Y),v,r,(u,\\_))$: symmetric
except that we now use $1/r$ in place of $r$.

  2. 2.

Safe-execute in Phase 2: Do the following based on the type of the order,
where $r_{\rm cur}$ denotes the market rate before the order is executed:

     * •

$({\sf Buy}(X),v,r,(u,\\_))$: Pick the maximum $v^{\prime}\leq v$ such that if
the user $u$ bought $v^{\prime}$ amount of $X$ at a starting rate of $r_{\rm
cur}$, then 1) the ending rate $r_{\rm end}\leq r$; and 2) user $u$’s balance
in $Y$ will not go negative. Let the user $u$ buy $v^{\prime}$ amount of $X$
at the starting market rate $r_{\rm cur}$.

     * •

$({\sf Sell}(X),v,r,(u,\\_))$: Pick the maximum $v^{\prime}\leq v$ such that
if the user $u$ sold $v^{\prime}$ amount of $X$ at a starting rate of $r_{\rm
cur}$, then 1) the ending rate $r_{\rm end}\geq r$; and 2) user $u$’s balance
in $X$ will not go negative.

     * •

$({\sf Buy}(Y),v,r,(u,\\_))$ or $({\sf Sell}(Y),v,r,(u,\\_))$: symmetric
except that we now use $1/r$ in place of $r$.

######  Theorem B.1 (Arbitrage resilience).

The swap mechanism in Figure 2 satisfies arbitrage resilience. In particular,
this holds no matter how ties are broken during the sorting step.

###### Proof.

The proof is the same as that of Theorem 3.2. We explain it for the ${\sf
Buy}(X)$/${\sf Sell}(Y)$-dominant case, since the ${\sf Buy}(Y)$/${\sf
Sell}(X)$-dominant case is symmetric. The mechanism executes in the following
way: 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 ${\sf
Pool}(x_{0},y_{0})$. In phase 2, it executes only ${\sf Buy}(X)/{\sf Sell}(Y)$
orders, which enjoy rate that is $r_{0}$ or greater, due to increasing
marginal cost (4.1). Therefore, for any subset of orders, it cannot be the
case that there is a net gain in one asset without any loss in the other. ∎

#### Refined swap mechanism with no short-selling in the time-of-arrival
model.

In the time-of-arrival model, we consider the mechanism described in Figure 1
with the following refinements:

  * •

The sorting step in Line 3a will break ties using arrival order.

  * •

A user’s honest strategy is defined as follows: $HS(t,v,r,\alpha)$ simply
outputs a single order $(t,v,r,\alpha)$, where $t$ is either ${\sf Sell}(X)$
or ${\sf Sell}(Y)$, and $v$ is the amount of $X$ or $Y$ held by the user,
respectively.

######  Theorem B.2.

Suppose $\Phi$ is concave, increasing, and differentiable. In the time-of-
arrival model, the above refined swap mechanism in Figure 2 satisfies
incentive compatibility w.r.t. the total ordering.

###  B.3 Proof of Incentive Compatibility

Observe that for the mechanism in Figure 2, the facts of increasing marginal
cost (4.1), no free lunch (4.2), and 4.3 still hold. Since the total ordering
is a refinement of the partial ordering, by the same proof as in Lemma 4.4 and
Lemma 4.7, we have the following result:

######  Lemma B.3.

Suppose $\Phi$ is concave, increasing, and differentiable. Given any initial
state ${\sf Pool}(x_{0},y_{0})$ and order vector ${\bf b}_{-u}$, for any
strategic order vector ${\bf b}_{u}$ of user $u$, there exists a single order
$b^{\prime}_{u}$ such that 1) $b^{\prime}_{u}$ results in an outcome at least
as good as ${\bf b}_{u}$ w.r.t. the total ordering; 2) the arrival time used
in $b^{\prime}_{u}$ is the true arrival time $\alpha^{*}$ of user $u$; and 3)
either $b^{\prime}_{u}=(\\_,0,\\_,\\_)$ or $b^{\prime}_{u}$ would be
completely safe-executed under ${\sf Pool}(x_{0},y_{0})$ and ${\bf b}_{-u}$.

###### Proof.

By the same proof of Lemma 4.4 and Lemma 4.7. Suppose the joint outcome of
${\bf b}_{u}$ is $(\delta x,\delta y_{0})$. Throughout the proof, the
strategic order vector ${\bf b}_{u}$ is replaced with a single order
$b^{\prime}_{u}$ that can be fully secure-executed and results in an outcome
$(\delta x,\delta y_{1})$. Since $\delta y_{1}\geq\delta y_{0}$ by the same
proof, the outcome of $b^{\prime}_{u}$ is at least as good as ${\bf b}_{u}$
w.r.t. the total ordering. ∎

Thus, it suffices to consider strategies that submit a single order, declare
the true arrival time $\alpha^{*}$, and moreover, either the order has a $0$
amount or it will be completely executed under ${\sf Pool}(x_{0},y_{0})$ and
${\bf b}_{-u}$. Henceforth, we call such strategies as admissible, single-
order strategies. The proof of Theorem B.2 can be completed by showing the
following lemma.

######  Lemma B.4.

Suppose $\Phi$ is concave, increasing, and differentiable. For any admissible
and single-order strategy $S$, the honest strategy results in an outcome that
is at least as good as strategy $S$.

###### Proof.

The structure of the proof is similar to Lemma 4.8. However, since the
original partial order is refined to a total order, some pair of incomparable
outcomes in the previous proof will now become comparable. We prove it for the
case when user $u$’s type is $({\sf Sell}(X),v^{*},r^{*},\alpha^{*})$. The
case for ${\sf Sell}(Y)$ is symmetric.

Due to Lemma B.3 and 4.3, we may assume that the strategic order must be of
the type either ${\sf Buy}(X)$ or ${\sf Sell}(X)$, with a true time of arrival
$\alpha^{*}$. Henceforth, let $(\delta x,\delta y)$ and $(\delta
x^{\prime},\delta y^{\prime})$ denote the honest and strategic outcomes,
respectively.

#### Case 1:

Suppose the strategic order is of the type ${\sf Buy}(X)$. Observe that the
honest order will always generate an outcome $(\delta x,\delta y)$ such that
$r^{*}\cdot\delta x+\delta y\geq 0$. Hence, it suffices to argue that the
outcome $(\delta x^{\prime},\delta y^{\prime})$ generated by any ${\sf
Buy}(X)$ must have $r^{*}\cdot\delta x^{\prime}+\delta y^{\prime}\leq 0$. Note
that $\delta x^{\prime}\geq 0$, we have $\delta y^{\prime}\leq 0$ because of
no free lunch fact (4.2).

Since the user’s true type is ${\sf Sell}(X)$, it means the initial market
rate $r_{0}$ satisfies $r^{*}\leq r_{0}$. Observe that in our mechanism, a
${\sf Buy}(X)$-type order can only be executed at a rate $r_{0}$ or larger.
This means that $-\delta y^{\prime}\geq r_{0}\cdot\delta x^{\prime}$. Thus, it
must be that $r^{*}\cdot\delta x^{\prime}+\delta y^{\prime}\leq 0$ since
$r^{*}\leq r_{0}$.

Therefore, we can conclude that the honest outcome is at least as good as the
strategic outcome.

#### Case 2:

The strategic order is in the same direction of ${\sf Sell}(X)$. Because of
4.3, we may assume that the strategic order is also of type ${\sf Sell}(X)$.
Since the mechanism guarantees no short-selling, for any strategic ${\sf
Sell}(X)$ order, it must be that $\delta x^{\prime}\geq-v^{*}$ and $\delta
x\geq-v^{*}$. We consider the following cases.

  * •

Case 2a: $0\geq\delta x^{\prime}\geq\delta x$. Since the strategic order
declares the same arrival time as the honest one by its admissibility, if the
orders from both strategies get safe-executed for a non-zero amount, both
executions will start at the same market exchange rate.

Therefore, for selling the initial $|\delta x^{\prime}|$ units of $X$, the two
strategies are equivalent. The honest strategy sells an additional $|\delta
x-\delta x^{\prime}|$ units of $X$ at rates of at least $r^{*}$, i.e., $\delta
y-\delta y^{\prime}\geq r^{*}\cdot(\delta x^{\prime}-\delta x)$. This means
that $r^{*}\cdot\delta x+\delta y=(r^{*}\cdot\delta x^{\prime}+\delta
y^{\prime})+r^{*}\cdot(\delta x-\delta x^{\prime})+(\delta y-\delta
y^{\prime})\geq r^{*}\cdot\delta x^{\prime}+\delta y^{\prime}$. This implies
that the honest outcome is at least as good as the strategic outcome.

  * •

Case 2b: $0\geq\delta x>\delta x^{\prime}$. Because of no short selling, the
strategic outcome must also satisfy $\delta x^{\prime}\geq-v^{*}$.

In this case, the honest outcome has not reached the goal $-v^{*}$. Under the
honest strategy, after user $u$’s order has been safe-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 less than
$r^{*}$.

Hence, for the strategic order, the difference of $|\delta x^{\prime}-\delta
x|>0$ units must be traded at an average rate strictly worse less than
$r^{*}$, i.e., $\delta y^{\prime}-\delta y<r^{*}\cdot(\delta x-\delta
x^{\prime})$. In other words, $r^{*}\cdot(\delta x^{\prime}-\delta x)+(\delta
y^{\prime}-\delta y)<0$, i.e., the strategic outcome is strictly worse than
the honest outcome.

∎