CS Paper Radar

Balanced Posted Prices in Stationary Two-Sided Markets

Ilan Reuven Cohen

cs.GT ·submitted 2026-10-22 12:10 UTC · v1
benchmark

Abstract

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.

Comment
30 pages

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.GT ·2026-10-08 ·Boyu Liu, Zhengyang Liu, Zihe Wang
similarity 0.69
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

A Constant-Factor Approximation to Multidimensional Consumer Utility

cs.GT ·2026-10-07 ·Kira Goldner, Taylor Lundy, Thodoris Tsilivis
theory similarity 0.68
Abstract · 40 pages, including appendices

Motivated by social services where consumers pay with non-transferable ordeals, we study mechanisms that maximize consumer utility for multiple unit-demand buyers and heterogeneous items whose values are drawn independently from known prior distributions. Prior work in utility maximization approximates social welfare and shows that the gap between optimal utility and social welfare is logarithmic. We resolve the question of whether simple mechanisms can guarantee a constant-factor approximation to optimal utility itself. Our mechanisms achieve a $(5.67+\varepsilon)$-approximation for general independent values, improving to $2e/(e-1)<3.164$ when values are i.i.d. Each buyer chooses their favorite option from posted item prices or free item lotteries, and contention resolution determines which buyers' requests are served; this is BIC, ex-post individually rational, and computable in polynomial time. Our main technical contribution is a general upper bound on the optimal ex-ante-constrained utility that separates the contributions captured by posted prices and free lotteries. These results establish a utility counterpart to the theory of simple, approximately revenue-optimal mechanisms.

0.49

Uniform-Price Mechanism Design for Automated Market Makers

cs.GT ·2026-10-16 ·Zhike Peng
published similarity 0.67
Abstract · 22 pages. Full version of a paper accepted at IJTCS-FAW 2026

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

0.36

Unit-Demand Pricing for Min-Buying Customers

cs.GT econ.TH ·2026-10-12 ·Titing Cui, Michael Hamilton, Jourdain Lamperski, Kasra Tari
similarity 0.66
Abstract

We study the unit-demand pricing problem under \textit{min-buying} behavior, where customers purchase the lowest-priced item that yields non-negative utility. In contrast to the quasi-linear model, we show that uniform pricing becomes substantially more effective under min-buying. First, we study symmetric environments. We show that for min-buying customers with independent and identically distributed valuations, a uniform price across items is optimal. We then extend this optimality result to all valuations drawn from exchangeable and affiliated distributions. However, uniform pricing is not optimal in all symmetric environments: for min-buying customers we construct an exchangeable and non-affiliated valuation distribution for which the gap between uniform pricing and optimal item pricing is logarithmic in the number of items. This gap is tight and matches the worst-case gap in the quasi-linear setting. Next, we consider asymmetric environments in which valuations are independent but not identically distributed. When these valuations are regular and customers are min-buying, we show that a uniform price guarantees approximately 69.86\% of the optimal item-pricing revenue and this is tight. Overall, our results highlight that the value of non-uniform pricing substantially diminishes, and often disappears entirely, under more conservative demand models in which customers engage in satisficing behaviors such as min-buying.

0.16

An $O(n\log n)$ Algorithm for Uncapacitated Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Arbitrary Prices

cs.CE ·2026-11-17 ·Kleitos Papadopoulos
similarity 0.66
Abstract

We study the finite-horizon, uncapacitated single-item lot-sizing problem with no fixed setup cost, a stationary threshold $Q > 0$ for an all-units quantity discount, arbitrary time-varying regular and discounted unit prices, and nonnegative linear holding costs. Order quantities and inventories may be either continuous or integral, and neither backlogging nor free disposal is allowed. Because unit prices may rise and fall arbitrarily over time, an optimal physical schedule may engage in speculative forward buying: positive orders can occur when incoming stock already exceeds current demand, and physical inventory carried across periods can grow proportionally to total horizon demand rather than remaining bounded by a multiple of $Q$. We give an exact $O(n\log n)$-time algorithm that computes the minimum total cost with free terminal inventory, together with the optimal cost for every horizon prefix constrained to end with zero inventory, using $O(n)$ working space under unit-cost exact arithmetic. Value computation operates online in a single forward pass without lookahead. With persistent frontier snapshots and a linear-time retroactive order-aggregation pass, an optimal physical ordering schedule is recovered in $O(n\log n)$ time and $O(n\log n)$ space.

0.28

Fair Allocation with Optional Selling

cs.GT econ.TH ·2026-08-25 ·Uriel Feige, Yotam Gafni
similarity 0.65
Abstract

We consider fair allocation of indivisible goods in a setting in which agents have subjective valuation functions over the set of goods, and in addition, goods may be sold at given market prices. In this setting, a fair allocation involves {deciding which goods to sell, how to allocate the unsold goods, and how to divide the money received from the sold goods.} We adapt to this setting the definitions of share-based fairness notions, such as the maximin share (MMS) and the truncated proportional share (TPS), and comparison-based fairness notions such as EF1 and EFX (which we adapt to SEF1 and SEFX). We show the following results when the utility of each agent is additive both over goods and over money. With two agents, there are allocations that are simultaneously MMS and SEFX. With three agents, there are instances in which no allocation gives every agent more than $\frac{11}{12}$-MMS. With any number of agents, there are $\frac{2}{3}$-MMS allocations. There also are allocations that are simultaneously SEFX and $\frac{n}{2n-1}$-TPS. This latter ratio is best possible, even without the SEFX requirement.

0.32

Finding Competitive Equilibria in Online Marketplaces with Platform Fees, Taxes, and Subsidies

cs.GT econ.TH ·2026-10-29 ·Taihei Oki, Ryosuke Sato
similarity 0.65
Abstract

We study equilibrium computation in multi-unit trading networks with valuations satisfying generalized full substitutes and agent- and transaction-specific piecewise-linear transfer functions. These transfers model platform fees, taxes, subsidies, and membership discounts in online marketplaces. Our ascending procedure raises prices at different rates and reaches the minimum equilibrium price vector in finitely many iterations, each implementable in strongly polynomial time under our oracle and arithmetic models. An equilibrium allocation can then be recovered efficiently. The method extends primal-dual techniques developed for ascending auctions to handle complementarities between purchases and sales through a submodular flow formulation. In single-seller markets with substitutes and complements, our framework also extends the double-track auctions of Sun and Yang (2009) and Shioura and Yang (2015) to bidder- and good-specific transfers.

0.16

Exact MMS Allocations under Personalized Bivalued Valuations: Goods and Chores

cs.GT cs.DS ·2026-08-16 ·Yuhao Zhang
benchmarktheory similarity 0.65
Abstract

The maximin share (MMS) is a central fairness benchmark for allocating indivisible goods and chores. We study additive valuations in the personalized bivalued setting, where each agent assigns one of two agent-specific values to every item. Whether exact MMS allocations always exist in this setting has remained a major open question, as highlighted by Ebadian, Peters, and Shah and by Garg, Huang, and Segal-Halevi. We answer this question affirmatively: we prove that exact MMS allocations always exist for both goods and chores and can be computed in polynomial time. Our proof combines a quota-based reformulation with an envelope relaxation, a sparse extreme-point construction, and flow-based rounding that controls the total rounding loss.

0.40