CS Paper Radar

The Limits of Price Discrimination When the Market Is Unknown

Irfan Tekdir

cs.GT econ.TH ·submitted 2026-10-21 20:13 UTC · v2

Abstract

Bergemann, Brooks, and Morris (2015) characterize the consumer and producer surplus pairs that segmentation can produce when the distribution of values is known. I fix only the set of possible values and characterize the pairs that some market and some segmentation can produce. They form a convex polygon. Its outer edge is the largest efficient surplus a market can have when its uniform-price profit is capped, net of that profit, and truncated equal-revenue markets attain it. At the values no segmentation is needed; strictly between two values, reaching the frontier requires splitting a market into two extremal markets. With a continuum of values up to $\bar{v}$, consumer surplus is at most $π\ln(\bar{v}/π)$ when producer surplus (the seller's profit) is $π$, this bound is reached without segmentation, and no market gives consumers more than $\bar{v}/e$.

Comment
15 pages, 3 figures

Closest papers

Nearest neighbours by meaning across the whole index.

The Welfare Limits of Market Segmentation with Captive Consumers

cs.GT econ.TH ·2026-10-29 ·Irfan Tekdir
similarity 0.76
Abstract · 25 pages, 5 figures

In a duopoly with captive and contested consumers, I characterize every pair of consumer and producer surplus that can arise under some market composition and some public segmentation, and construct a market that produces each pair. The set is lens-shaped. At any level of industry profit, consumers do worst when captive and contested consumers are perfectly separated and best in an unsegmented market in which the two firms have equally many captives. A market with unequal captive bases and some contested consumers cannot reach this upper frontier under any segmentation. Between Bertrand competition and monopoly, the frontier itself lies strictly below what consumers would get if everyone paid a single deterministic price yielding the same profit. Firms must randomize, and with downward-sloping demand the resulting price dispersion lowers consumer surplus.

0.19

Two-Sided Screening in Quality-Differentiated Markets

cs.GT ·2026-11-04 ·Yaohao Liu, Mengfan Ma, Mingyu Xiao
similarity 0.59
Abstract

Motivated by digital marketplaces such as Uber and Airbnb, we study how a two-sided platform designs a menu of qualities, consumer prices, and provider wages. Consumers and providers self-select according to their private values and costs, so the platform must design its menu to attract consumers while inducing enough supply to meet their demand. We study this coordination problem over a continuous quality space, requiring supply to cover demand at every quality threshold. We formulate menu design as an optimization over trading distributions, which specify how much trade occurs at or above each quality. Through convexification of the technological cost function, we characterize the profit- and welfare-optimal trading distributions. This characterization shows how production technology alone can reduce menu size without sacrificing optimal profit or welfare, regardless of the type distributions, and determines when optimal menus can be finite. We then show that profit maximization can be highly efficient: under monotone hazard rate conditions on both sides, a profit-optimal menu achieves at least $1/(e-1)$ of optimal social welfare. We next consider the practical setting in which the menu size is restricted to a prescribed number of offers. We establish how the restricted menu approximates the unrestricted optimum in profit. We develop an algorithm that computes a menu within this size limit in polynomial time. The computed menu simultaneously approximates the unrestricted optimal profit and social welfare with additive error.

0.28

RARE: Response-Aware Rational Equilibrium in Budget-Constrained Pricing Games

cs.GT ·2026-10-28 ·Bhaskar Ray Chaudhury, Jugal Garg, Xin Huang, Eklavya Sharma
theory similarity 0.56
Abstract · Changes in v2: improved title, exposition, and bibliography

We study a pricing game in markets with budget-constrained buyers, where each seller offers a single good and sets its price. We consider both non-rivalrous goods, such as datasets, and rivalrous goods, such as physical goods. For non-rivalrous goods, each buyer chooses a utility-maximizing bundle within her budget. For rivalrous goods, an allocation rule selects a Pareto-optimal allocation subject to the buyers' budgets and the goods' supply constraints. Pure Nash equilibria often fail to exist in this game. A key reason is that Nash equilibrium assumes that the other sellers keep their prices fixed when one seller deviates. In practice, however, sellers harmed by a price change may respond, for example, by matching the new price. We propose a new equilibrium notion called Response-Aware Rational Equilibrium (RARE). At a RARE, every deviation by a seller can be deterred by a response from the other sellers, in which no responder earns less than she did right after the deviation. Every Nash equilibrium is a RARE. Assuming that the allocation rule is continuous in prices, we show that a RARE always exists for rivalrous goods, and for non-rivalrous goods when buyers have equal budgets. Moreover, the RARE that we construct extracts the buyers' entire budget. For non-rivalrous goods with unequal budgets, we show that an approximate RARE exists, where a deviating seller can increase her revenue by a factor equal to the ratio of the average budget to the minimum budget. We also study a natural dynamic in which sellers repeatedly raise their prices to earn the revenue that they could guarantee themselves by deviating. We show that, in the settings where we prove exact existence, this dynamic reaches a RARE with additive error $δ$ within $\lfloor B/δ\rfloor$ rounds, where $B$ is the buyers' total budget. This paper's main results have been formally verified in Lean 4.

0.24

A Constant-Factor Approximation to Multidimensional Consumer Utility

cs.GT ·2026-10-07 ·Kira Goldner, Taylor Lundy, Thodoris Tsilivis
theory similarity 0.56
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.51

Improved Revenue Guarantees for Selling Separately and Bundling

cs.GT ·2026-09-24 ·Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta +2 more
theory similarity 0.56
Abstract

We study how much revenue a seller can lose by restricting attention to selling separately or grand bundling, in the setting of a single additive buyer with independent item values. Although revenue-optimal mechanisms can require lotteries and infinite menus, Babaioff, Immorlica, Lucier, and Weinberg showed that the better of these two simple formats always achieves a constant fraction of optimal revenue. We prove that $\mathrm{OPT} \le 3.52 \max\{\mathrm{SREV}, \mathrm{BREV}\}$, where $\mathrm{SREV}$ and $\mathrm{BREV}$ are the optimal revenues from selling separately and grand bundling, respectively. This improves the previous best-known approximation factor of $5.2$ due to Ma and Simchi-Levi and narrows the gap to the known lower bound of $2$.

0.38

Cardinality-Constrained Randomized Assortments with Balanced Market Share

cs.GT ·2026-09-18 ·Xiaotie Deng, Hanyu Li, Chenghua Liu
similarity 0.55
Abstract

Assortment optimization asks a seller which of $n$ products to display to each customer. Under the multinomial-logit (MNL) model, a revenue-maximizing policy may concentrate most purchases on only a few products. Balanced market share (BMS) limits this disparity by requiring every product to receive either zero aggregate sales or at least an $α$-fraction of the largest product's sales. We study randomized BMS under a per-assortment cardinality constraint: every displayed assortment contains at most $K$ products, although the seller may rotate a larger catalog across customers. This couples per-realization feasibility with aggregate balance over an exponential policy space. We resolve the model on all three algorithmic fronts. First, reweighting assortments by their MNL denominators turns the cardinality restriction into a single uniform-matroid rank inequality, yielding an exact compact sales-space formulation in which every feasible sales vector can be implemented by a policy supported on $O(n)$ assortments. Second, deciding whether there exists a feasible policy attaining a given revenue target is NP-complete even for $α=1$ and $K=2$, whereas optimization is polynomial-time solvable once the set of products with positive sales is prescribed. Third, despite this hardness, BMS confines all positive sales to one multiplicative band, and a geometric scale search combined with a standard multiple-choice-knapsack dynamic program yields an FPTAS. For every $\varepsilon\in(0,1)$, it achieves at least a $(1-\varepsilon)$ fraction of the optimal expected revenue, preserves BMS and per-assortment cardinality exactly, and outputs a rational policy supported on $O(n)$ assortments.

0.19

Learning to Price with Persuasion

cs.GT cs.LGecon.TH ·2026-08-17 ·Maria-Florina Balcan, Tejas Pagare, Karan Singh
similarity 0.55
Abstract · 29 Pages, 1 Table

Motivated by modern marketplaces, where the platform or the seller routinely gathers detailed user profiles, we study a novel learning theoretic model that simultaneously involves information and mechanism design. Specifically, we consider the economic setting recently introduced by Bergemann et al. (2022), where in addition to the menu of quality-price pairs, the seller offers information on the value of the match between product quality and buyer's taste via a signaling scheme. We relax the assumption that the seller knows the buyers' belief about the distribution of tastes and study the sample requirements of designing a revenue maximizing scheme. We consider both the batch setting where we have access to data from a set of i.i.d. buyers and an online demand query model where we observe the buyers' behaviors to seller's schemes. Despite the apparent non-convexity of the problem, we also give the first FPTAS to compute a scheme that maximizes the revenue within an arbitrarily small additive loss, which was left open by Bergemann et al. (2022). Overall, this brings a new learning perspective in asymmetric economic settings where buyers and sellers know different types of information.

0.17

A Unified Framework for Assortment Optimization and Matching under MNL Choice

cs.GT math.OC ·2026-10-26 ·Omar El Housni, Ulysse Hennebelle
benchmark similarity 0.54
Abstract

We develop a unified framework for assortment optimization and matching under multinomial logit (MNL) choice, yielding simple algorithms and analyses across a broad class of problems. The framework centers on a single-customer assortment problem in which the firm commits to eligible products before their independent availabilities are revealed. A simple threshold policy achieves a tight $1/2$ guarantee against a benchmark that selects its assortment after observing availability and may control dependence subject to the same marginal probability bounds. This guarantee accommodates cardinality constraints and adversarial removal of excess available products. Combined with problem-specific linear programming relaxations, the framework yields $1/2$ guarantees for standard two-sided assortment optimization, customization under mixtures of MNL models, ride-hailing notifications, multi-round broadcast matching, and MNL prophet inequalities, and a $1/4$ guarantee for fully static two-sided assortment optimization. Across these applications, we improve approximation factors, extend guarantees to more general revenues and cardinality constraints, and retain existing factors against stronger benchmarks.

0.05