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