CS Paper Radar

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

Taihei Oki, Ryosuke Sato

cs.GT econ.TH ·submitted 2026-10-29 17:56 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Balanced Posted Prices in Stationary Two-Sided Markets

cs.GT ·2026-10-22 ·Ilan Reuven Cohen
benchmark similarity 0.65
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

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

Auction-based allocation of routes in capacity-constrained networks

cs.GT econ.THecon.GN ·2026-10-14 ·Gergely Csáji, Dávid Csercsik
similarity 0.64
Abstract

We study the route-set allocation problem between end nodes in capacity-constrained flow networks with transfer costs. We introduce an origin--destination (OD) bidding language, in which a participant bids for bounded conic combinations of inlet--outlet--quantity licences and the mechanism performs the routing through a network-flow optimising winner-determination problem. We then study payment rules for the OD mechanism. Under a restricted model with openly and uniformly priced sources and bidders who are indifferent to the source of the gas, the Vickrey--Clarke--Groves (VCG) payment is core-stable; the key structural fact is that in this regime some optimal aggregate flows never use a physical pipe in both directions, so the winner-determination problem reduces to a single-commodity network flow whose value is submodular in the set of active bidders. If source access is allowed to depend on the individual consumer -- a realistic feature, e.g. when gas deals are embedded in bilateral political bargaining -- the reduction fails and VCG payments may lie strictly outside the core. For this general model we propose a dual (nodal) pricing rule derived from the shadow prices of the flow-conservation constraints, and prove it is always core-stable, at the cost of dominant-strategy incentive compatibility. Illustrative examples accompany each result.

0.26

GSP Autobidding Equilibria with Few Advertisers or Slots

cs.GT ·2026-10-21 ·Yiyang Huang, Zhengyang Liu, Yonglei Yan, Zihe Wang
theory similarity 0.64
Abstract · 1 figure, 1 table, 4 algorithms

In sponsored-shopping auctions, one advertiser may win several positions, and a product that is never displayed may determine the prices of several winners. Under generalized second-price (GSP) pricing without self-pricing, these interactions couple allocation and payment through a single global ranking. We prove that exact autobidding equilibria under budget and return-on-investment (ROI) constraints can be computed in polynomial time whenever either the number $n$ of advertisers or the number $K$ of display slots is fixed. Our algorithms rely on two structural reductions. With few advertisers, the payment polytopes of tied bid layers combine by a Minkowski sum, giving a fixed-dimensional representation of exponentially many rankings. With few slots, budget equilibria admit threshold recovery and an exact submodular description of attainable payments at the display boundary. For ROI, we prove that every group-consecutive equilibrium has a representative with at most $K+2$ nonunit multipliers, preserving the item and price in every displayed slot. In each case, the reduction leads to polynomially many systems of polynomial equations and inequalities in bounded dimension. The algorithms compute exact multipliers and explicit distributions over valid group-consecutive rankings, with support at most $n+1$; for ROI with few slots, this improves to $\min\{n+1,K+3\}$.

0.07

Solving the Arctic Product-Mix Auction

cs.GT econ.TH ·2026-09-28 ·Elizabeth Baldwin, Paul Klemperer, Edwin Lock
similarity 0.64
Abstract

Arctic product-mix auctions allow budget-constrained bidders to express preferences over multiple substitute goods. We give the first strongly polynomial algorithm to find the competitive equilibria when the auctioneer has separable convex piecewise-linear costs. It combines a strongly polynomial reduction to the costless Arctic auction with an existing strongly polynomial algorithm for costless Arctic auctions. We also give a polynomial-time Turing reduction from costless Arctic auctions to linear Fisher markets, and a strongly polynomial many-to-one reduction to linear Arrow-Debreu exchange markets. If a good is sold in positive quantity in two competitive equilibria, its price is the same in both.

0.32

FIXP-Completeness in Second-Price Auctions

cs.GT cs.CC ·2026-10-31 ·Nobutaka Shimizu
theory similarity 0.63
Abstract

Computing equilibria is a fundamental algorithmic problem in game theory and economics. Although general frameworks are available for proving membership in FIXP, the class capturing exact fixed-point computation, establishing FIXP-completeness often remains challenging. We prove FIXP-completeness of exact equilibrium computation in three second-price auction models: (1). pacing with return-on-investment constraints, with multiplier cap $1+δ$ for every fixed rational $δ>0$ [Filos-Ratsikas, Hansen, Høgh, and Hollender (2024)]; (2). budget-constrained generalized second-price sponsored shopping [Hansen, Li, and Nie (2026)]; (3). budget-constrained throttling [Liu (2026)]. These results resolve open questions on the exact complexity of automated bidding. Our technical ingredient is a FIXP-complete generalized-circuit problem using only clipped affine gates and the reciprocal $x\mapsto1/(1+τx)$, for any fixed positive rational $τ$. This gate basis provides a common framework for the three auction reductions: simulating these gates in each model establishes FIXP-hardness without directly implementing multiplication or squaring.

0.15

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

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

Pacing Equilibria in Abstract Mechanisms

cs.GT ·2026-09-23 ·Salam Afiouni, Christian Kroer
benchmarktheory similarity 0.63
Abstract

Digital platforms increasingly rely on automated budget-management systems to regulate participation across allocation opportunities. A common tool is multiplicative pacing, which scales buyers' bids so that campaign-level budgets are spent gradually. Although pacing is operationally simple, its aggregate behavior depends on the underlying mechanism. In first-price single-item auction markets, pacing enjoys strong structural and computational properties that often fail in second-price auctions. It is unclear whether these properties extend to richer platform mechanisms. We develop a unified theory of pacing equilibria across a hierarchy of mechanisms. We first show that, even in first-price position auctions, the market-equilibrium interpretation of the single-item benchmark can fail. We then identify bid-maximizing pay-your-bid mechanisms as a broad class in which pacing equilibria exist, are unique, and admit an Eisenberg-Gale-type convex-program characterization. This implies efficient computation, Pareto-efficiency, and liquid-welfare guarantees, enabling pacing integration into large-scale optimization-based allocation routines. Finally, for abstract mechanisms satisfying a payment monotonicity condition, we prove equilibrium existence by smoothing discontinuities. With additional conditions and appropriate tie-breaking, we obtain uniqueness, revenue maximality among budget-feasible pacing vectors, and shill-proof implementability, and provide convergent budget-adjustment dynamics for approximate equilibria. Overall, many favorable properties of first-price pacing extend beyond single-item auctions under appropriate mechanism-level conditions.

0.29