CS Paper Radar

Uniform-Price Mechanism Design for Automated Market Makers

Zhike Peng

cs.GT ·submitted 2026-10-16 14:40 UTC · v1
published

Abstract

Automated market makers (AMMs) are central to decentralized exchanges, but their reserve curves make mechanism design different from classical double auctions. We study a batch double auction with buyers, sellers, and a liquidity-nondecreasing AMM: post-trade reserves must have weakly larger product than the initial reserves. Each user has two-dimensional private information: a unit value and a demand or supply quantity. User trades clear at one uniform price subject to AMM feasibility. The objective is user-side trading volume, benchmarked against the optimal feasible individually rational (IR) uniform-price allocation. We give a randomized uniform-price mechanism based on binary quantity buckets. It randomly chooses one of three clearing modes: peer-to-peer matching, AMM sales to buyers, and seller sales to the AMM. Every deterministic realization of the mechanism is ex-post feasible and satisfies IR and weak quantity incentive compatibility: conditional on any quantity report, truthful unit-value reporting is dominant whenever it gives a non-negative utility, no unit-value deviation gives a positive utility if the truthful one doesn't, and users cannot benefit by under-reporting the quantity together with their truthful unit value. Let $V^\ast$ be the optimal feasible IR uniform-price volume without incentive constraints, and let $γ=\bar q/\underline q$, where $\bar q$ and $\underline q$ are the quantity-domain bounds. For $γ\ge1$, the mechanism achieves an expected trading volume of $ Ω(1/(1+\logγ)^2)V^\ast - O(\bar q). $ We also show that full incentive compatibility over the two-dimensional type space forces a worst-case approximation ratio of $O(1/γ)$ at every prescribed initial reserve ratio, even when both AMM reserves are scaled by an arbitrarily large common factor and the optimal volume $V^\ast$ is arbitrarily large relative to $\bar q$.

Comment
22 pages. Full version of a paper accepted at IJTCS-FAW 2026

Closest papers

Nearest neighbours by meaning across the whole index.

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

cs.DC cs.CRcs.GT ·2026-11-06 ·William Diamond, Fatima Elsheimy, Dahlia Malkhi, Geoff Ramseyer, Srivatsan Sridhar
similarity 0.70
Abstract

Decentralized exchanges typically give traders no execution guarantee until a block is finalized. In the meantime, external prices move, traders strategically delay submission, and block producers can influence inclusion and ordering. We introduce FirstSwap, a DEX built on a constant-function market maker pricing curve that gives traders an early pre-approval before consensus, guaranteeing inclusion and execution within their submitted price limit, with final ordering determined by limit prices rather than by a block producer. We demonstrate the benefits of trade pre-approvals in an economic model combining auction theory with CEX-DEX arbitrage. When the CEX price changes gradually, FirstSwap rewards earlier traders with better prices, discouraging strategic delay and yielding higher social welfare and gains to AMM liquidity providers than a batch auction. When the CEX price jumps abruptly, FirstSwap yields higher welfare and smaller AMM losses than fair ordering. The central challenge is delivering fast trade pre-approvals without consensus. We introduce a decentralized, scaled admissibility protocol under which each validator reserves only a fraction of the available liquidity at every price. A trader obtains approval in a single round of messages with a quorum of validators. Somewhat surprisingly, despite Byzantine validators who may approve trades arbitrarily, we show that all quorum-certified trades are jointly admissible and execute within their limits. Our protocol extends naturally to a setting where buy and sell orders can be pre-approved against each other before a block is finalized.

0.19

Optimal Multi-Item Auctions with I.I.D. Values

cs.GT ·2026-10-08 ·Boyu Liu, Zhengyang Liu, Zihe Wang
similarity 0.68
Abstract · 51 pages, 1 table

We study revenue-maximizing multi-item auctions under dominant-strategy incentive compatibility (DSIC) and ex-post individual rationality. Buyers have additive valuations, and all item values are independent draws from a common finite distribution. For every two-point distribution and arbitrary numbers of buyers and items, we give an explicit deterministic mechanism that is optimal among all randomized mechanisms satisfying these requirements, together with a polynomial-time algorithm for computing the optimal expected revenue. For general finite-support distributions, computing the exact optimal revenue is $\#\mathrm P$-hard, both for a single buyer with an arbitrary number of items and for two items with an arbitrary number of buyers. For a single buyer, we also establish hardness of computing an optimal mechanism. Building on prior work, we also obtain exact and approximate algorithms under different parameter restrictions. Exact polynomial-time optimization is possible whenever any two of the buyer count, item count, and support size are fixed. When only the item count is fixed, a polynomial-time approximation scheme constructs a mechanism with expected revenue at least a $1-\varepsilon$ fraction of the optimum for every fixed $0<\varepsilon<1$. All these algorithms satisfy DSIC and ex-post individual rationality.

0.21

Tight Liquid Welfare Guarantees for Auctions with Budgets via LP Duality

cs.GT ·2026-09-30 ·Twan Kroll, Guido Schäfer, Artem Tsikiridis
theory similarity 0.68
Abstract

We study the efficiency of auctions with budget-constrained bidders and derive tight price of anarchy (PoA) bounds for coarse correlated equilibria (CCE). To this end, we develop a general framework that reduces proving PoA guarantees to finding feasible solutions to the dual of a linear program. The LP is formulated over a small number of per-bidder equilibrium statistics, incorporates constraints implied by the auction setting and equilibrium behavior, and captures a novel smoothness notion tailored to budget-constrained environments; we provide a reduction from classical smoothness to this new notion. Our approach enables simple and tight PoA analyses across a broad range of auction formats. Using our framework, we obtain tight liquid welfare guarantees for simultaneous first-price, second-price, and all-pay auctions, simultaneous auctions with restricted uniform bidding interfaces, discriminatory and uniform price multi-unit auctions, and generalized first-price position auctions. Beyond budget-constrained settings, we derive new lower bounds for the budget-free uniform price auction and generalized second-price auction; in particular, our lower bound for the uniform price auction matches the upper bound of $3.146$ by de Keijzer et al. (2013).

0.16

Otter: A Provably MEV-Resilient Automated Market Maker via Surplus Redistribution

cs.GT ·2026-09-03 ·Elaine Shi, Mengqian Zhang, Hao Chung, Yuhao Li
similarity 0.68
Abstract · Abstract shortened to comply with arXiv's character limit

Miner extractable value (MEV) in automated market makers allows block builders to profit from transaction ordering and injected trades, imposing costs on users and contributing to builder centralization. We introduce Otter (Optimal Truthful Trading with Excess Redistribution), a two-asset batch AMM that achieves provable MEV resilience when the consensus layer provides censorship resilience and block space is uncongested. Otter makes truthful behavior a dominant strategy for both users and builders. Consequently, a builder cannot profit from strategic deviations, including reordering bids or injecting sybil bids, even when the builder is itself a trader with intrinsic value. Moreover, we show that Otter maximizes social welfare, in a strong sense, within a natural class of mechanisms satisfying the desired game-theoretic properties. To achieve these guarantees, we introduce a new paradigm called surplus redistribution, which provably prevents residual surplus from being captured as MEV by redirecting it to the broader community. Specifically, the pool's output tokens need not be distributed entirely among users in the current batch. Instead, residual surplus may be transferred to a smart contract governed by the decentralized community. The accumulated surplus can be used to benefit community members --- for example, by subsidizing transaction fees, rewarding liquidity providers, or returning assets to the pool. Our approach relies on the underlying consensus layer to provide censorship resilience. We motivate its necessity through an impossibility result showing that the desired game-theoretic guarantees become unattainable when the builder is additionally allowed to censor transactions. Thus, our results also provide a mathematically formal demonstration of how consensus-level security guarantees can fundamentally expand what is achievable at the application layer.

0.47

Generalized Prophet Inequalities for Online Auctions

cs.GT ·2026-09-30 ·Twan Kroll, Rebecca Reiffenhäuser
similarity 0.67
Abstract

Prophet Inequalities for online auctions, as many classical auction settings, traditionally consider agents who strive to maximize quasi-linear utility, i.e. their obtained value minus the price paid. This simplified view of the agents' objectives does not capture real-world settings where agents are almost always constrained by budgets, and can have different objectives altogether (e.g., very prominently, value maximizers in autobidding). We generalize classic prophet inequality auction settings to accommodate unknown, varying types of agent objectives and budgets, modeling them as stochastic input similar to the traditional valuation distributions. In this new model, we analyze (anonymous) posted-price mechanisms, one main category of which are the balanced prices central to many auction results in the prophet inequality model. We demonstrate both the resilience and limits of balanced price mechanisms for generalized prophet inequalities with stochastic agent objectives, budgets and valuations: our generalization of the balanced prices framework incorporates budget constraints and mixed objectives. We show constant competitive ratios for some the most central settings, spanning all the way up to agents with subadditive valuation functions. On the way, we establish trade-offs between competitive ratio and agents' price-sensitivity, and give a general reduction from the budgeted setting to budget-free value maximizers.

0.17

Two-sided Market Design Meets Autobidding

cs.GT ·2026-09-30 ·Yang Cai, Christopher Liaw, Aranyak Mehta, Xizhi Tan, Mingfei Zhao
publishedtheory similarity 0.67
Abstract · To appear in the 22nd Conference on Web and Internet Economics (WINE2026)

Autobidding has become a dominant paradigm in online advertising by enabling advertisers to set high-level goals while algorithms handle real-time bid optimization. A prominent example is the Return-on-Spend (RoS) value maximizer, which maximizes total value subject to an aggregate value-per-spend constraint. While most work on mechanism design for autobidders focuses on one-sided markets, many real-world platforms involve strategic behavior on both sides. We initiate the study of two-sided markets with autobidders. We first establish a stark negative result: for the challenging objective of liquid gains from trade (LGFT) in the prior-free setting, broad classes of utility-truthful, budget-balanced mechanisms have unbounded Price of Anarchy (PoA) once value-maximizing agents are present, even in double-auction environments. We then give two positive results. In the prior-free repeated double-auction setting, McAfee's Trade Reduction mechanism has unbounded PoA for LGFT but achieves constant PoA for liquid welfare under RoS bidding, showing that off-the-shelf mechanisms retain meaningful welfare guarantees. With distributional information regarding the private costs and values, we design a two-sided mechanism that is incentive compatible for each agent under its corresponding objective, individually rational, ex-ante weakly budget balanced, and achieves first-best liquid welfare, equivalently optimal LGFT, whenever at least one side of the market consists of RoS value maximizers. This result applies to matching markets with general downward-closed feasibility constraints. It contrasts sharply with the Myerson--Satterthwaite impossibility theorem~\citep{MS83}, which rules out first-best efficiency with incentive compatibility, individual rationality, and budget balance even in bilateral trade when both the buyer and the seller are quasi-linear utility maximizers.

0.32

Balanced Posted Prices in Stationary Two-Sided Markets

cs.GT ·2026-10-22 ·Ilan Reuven Cohen
benchmark similarity 0.67
Abstract · 30 pages

We study an intermediary that buys nonperishing items from arriving sellers and sells them to arriving buyers, subject to limited storage. Sellers and buyers arrive according to independent Poisson processes. The intermediary pays and charges the same fixed item prices, aiming to maximize long-run gains from trade: buyer value minus seller cost. Our benchmark may choose allocations directly, has unlimited storage, and must purchase each unit before allocating it. Its optimal long-run gain rate equals the value of a linear program of average purchase and allocation rates, with or without knowledge of future arrivals. For buyers whose bundle values are maxima of nonnegative additive valuations (XOS), we compute static common prices that guarantee half of this benchmark for arbitrary finite item capacities, even one storage slot per item, regardless of how ties are resolved without using future arrivals. The prices are computable in polynomial time using demand and supporting-value queries. The construction equalizes itemwise lower bounds on buyer and seller contributions to gains from trade, accounting for procurement costs. We call this contribution balance. As a single-item foundation, we also equalize the rates of purchases and sales selected by the price, before checking inventory availability. We call this rate balance. For capacity $C$, it yields the tight guarantee $C/(C+1)$. The two principles parallel proofs of the classical prophet inequality based on half the expected benchmark and on a median threshold, adapting these balancing ideas to recurring two-sided markets with limited inventory.

0.13

Payment Design under Belief Disagreement: Rent Placement, Bid Resolution, and Auction Choice

cs.GT econ.THmath.OC ·2026-10-05 ·Lijian Lu, Ce Zhang
similarity 0.66
Abstract

When auction bidders misperceive their rivals, a seller can change not only the amount of information rent but also the states in which it is delivered. We ask when this payment-design opportunity survives a finite bidding interface, nonnegative-payment restrictions, and comparison with conventional auctions under the same beliefs. We formulate payment design as a linear program in nonnegative bidder rents. A single state can safely carry a report's rent when it is both cheapest for its intended type and least attractive to potential mimics. We characterize this alignment, bound the cost of a restricted payment architecture when alignment is imperfect, and use shadow prices when the rankings conflict. Own-type projection yields a unique optimal expected-payment rule for a fixed allocation. Contiguous bid bands implement truthful reporting at every value, but create pooling losses and within-band surplus. Under a separate smooth-belief model, feasible truthful rules and revenue upper bounds support comparisons with a first-price equilibrium under the same beliefs. A calibration using 1,000 eBay proof-set auction records illustrates a partition-dependent reversal: first price dominates all exactly truthful, no-subsidy rules on ten equal-probability bands in one scenario, while a richer contingent rule on ten equal-dollar bands outperforms it. An operator should choose interface resolution, payment dependence, and integrity tolerances jointly. Validate the probabilities that support incentives, compare formats under the same beliefs, and distinguish redesign from deployment. Any receipt advantage must cover implementation costs before it can imply a profit advantage.

0.20