Dynamic Pricing in Two-Sided Markets: Learning Barriers and Price Differentiation

arXiv:2602.11691 · cs.GT · Submitted 2026-02-12 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Dynamic Pricing in Two-Sided Markets".

Jane: Here's the gist of the paper. The study investigates online pricing strategies in two-sided markets where a platform repeatedly posts prices to multiple buyers and sellers, observing only binary accept/reject feedback, with objectives focused on either maximizing gains-from-trade (GFT) or profit.

Tom: The analysis considers three natural classes of price-posting mechanisms, ordered by increasing expressiveness: Single-Price Mechanisms (one price to all traders), Two-Price Mechanisms (one price for sellers and one for buyers), and Segmented-Price Mechanisms (traders partitioned into up to two groups with distinct prices per group).

Jane: For profit maximization, an algorithm based on Two-Price Mechanisms achieves an optimal regret of O(n squared T) in the time horizon T, where n is the number of traders.

Tom: For GFT maximization, the achievable regret depends heavily on market size and mechanism expressiveness.

Paper summary: Tom: To recap, this paper "Dynamic Pricing in Two-Sided Markets: Learning Barriers and Price Differentiation" looks at online pricing where a platform repeatedly posts prices to many buyers and sellers, only seeing if they accept or reject the price. The main thrust is analyzing three types of posting mechanisms: Single-Price, Two-Price, and Segmented-Price >

Jane: And they compare what you can achieve for two different goals: maximizing profit versus maximizing the gains from trade. They show that for profit maximization, an algorithm using Two-Price Mechanisms can get a regret of O of n squared log log T in time horizon T >

Lu: But the paper emphasizes that this performance is specific to the mechanism; for instance, a Single-Price approach has a lower bound on regret of Omega of log log T log log log log T if you are just dealing with one seller and two buyers >

Meng: And they also show that in full many-to-many markets, Two-Price Mechanisms lead to linear regret, which is Omega of T >

Lalam: To deal with the gains from trade maximization in those big markets, they introduce Segmented-Price Mechanisms to mitigate the mismatch phenomenon and get an O of n squared log log T plus n cubed regret >

Tom: So for profit maximization, the Two-Price Mechanism is shown to be optimal because it achieves that O of n squared log log T bound >

Jane: But if you want gains from trade, you need more expressive mechanisms when the market gets large, and Segmented-Price Mechanisms help achieve a better regret than what Single-Price can manage >

Lu: The analysis extends this to a contextual setting where costs and values depend on d dimensional features that change every round >

Meng: This means the sellers have private cost vectors theta and buyers have private value vectors beta, and in each round an adversary chooses a product context x that determines the costs c from theta and values v from beta >

Lalam: In this extension, the platform's pay per round depends on whether you're maximizing total collected revenue minus total payments for profit maximization or total surplus generated by executed trades for gains from trade maximization >

Conclusion: Tom: So, looking at the paper "Dynamic Pricing in Two-Sided Markets: Learning Barriers and Price Differentiation" and its authors, I think it boils down to this: dynamic pricing is hard when the market gets big and complex, but we can get better bounds if we use smarter pricing structures >

Jane: The authors are showing that there are clear trade-offs between maximizing pure profit versus maximizing gains from trade depending on how much expressiveness you use in your posting mechanism >

Lu: It suggests that the structural choice of how the platform posts prices is a really important part of finding an efficient learning strategy >

Meng: And for me, it means if we want to deploy this, we need to think about what kind of pricing structure fits our actual business model and how much complexity we can afford >

Lalam: Ultimately, this paper shows that even with context, you can still get polynomial regret bounds on both profit and gains from trade >

Tom: So the big message is that smart design in the way you post prices can actually give you a better learning guarantee in these dynamic online markets >

Yiding Feng, Mengfan Ma, Bo Peng, Zongqi Wan

Hong Kong University of Science and Technology, China · Central China Normal University, China · Shanghai University of Finance and Economics, China · Great Bay University, China

cs.GT

Submitted: 2026-02-12

Updated: 2026-11-16

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 98/100

The gist: The study investigates online pricing strategies in two-sided markets where a platform repeatedly posts prices to multiple buyers and sellers, observing only binary accept/reject feedback…

Key concepts

Two-Price Mechanisms
This mechanism involves the platform setting one specific price for sellers and a different specific price for buyers. This allows the platform to tailor pricing strategies separately for each group of traders, which is key to achieving optimal profit maximization in certain market structures.
Gains-from-Trade (GFT)
GFT measures the total surplus generated by executed trades, calculated as the sum of buyer values minus seller costs. Maximizing GFT focuses on facilitating profitable transactions rather than just maximizing platform revenue.
Contextual Setting
This extension incorporates features where traders' costs and values change based on observed, varying features (like context $x_t$). This means the price a trader accepts or demands is influenced by these dynamic, observable contextual factors in each round.

Terminology

Summary

The study investigates online pricing strategies in two-sided markets where a platform repeatedly posts prices to multiple buyers and sellers, observing only binary accept/reject feedback, with objectives focused on either maximizing gains-from-trade (GFT) or profit. p. 0

Where the paper says it

Searching for Optimal Prices in Two-Sided Markets Yiding Feng∗ Mengfan Ma† Bo Peng‡ Zongqi Wan§ Abstract We study online pricing in two-sided markets where a platform repeatedly posts prices to multiple buyers and sellers, observes only binary accept/reject feedback, and aims to maximize either gains-from-trade (GFT) or profit. We analyze three natural classes of priceposting mechanisms—Single-Price, Two-Price, and Segmented-Price—and characterize the regret achievable under each.

The analysis considers three natural classes of price-posting mechanisms, ordered by increasing expressiveness: Single-Price Mechanisms (one price to all traders), Two-Price Mechanisms (one price for sellers and one for buyers), and Segmented-Price Mechanisms (traders partitioned into up to two groups with distinct prices per group). p. 2
Where the paper says it

The platform observes only the binary accept/reject decisions of each trader and uses this feedback to adapt its pricing strategy in future rounds. To model the platform’s pricing capability, we consider three natural classes of price-posting mechanisms, ordered by increasing expressiveness: • Single-Price Mechanisms, where one price is posted to all traders; • Two-Price Mechanisms, where one price is offered to all sellers and another to all buyers; • Segmented-Price Mechanisms, where sellers and buyers are each partitioned into up to two groups, with a distinct price per group.

For profit maximization, an algorithm based on Two-Price Mechanisms achieves an optimal regret of O(n squared T) in the time horizon T, where n is the number of traders. p. 0

Where the paper says it

We analyze three natural classes of priceposting mechanisms—Single-Price, Two-Price, and Segmented-Price—and characterize the regret achievable under each. For profit maximization, we design an algorithm using Two-Price Mechanisms that achieves O(n 2 log log T) regret, which is optimal in the time horizon T, where n is the number of traders.

For GFT maximization, the achievable regret depends heavily on market size and mechanism expressiveness. p. 0
Where the paper says it

For GFT maximization, the optimal regret depends critically on both market size and mechanism expressiveness. Constant regret is achievable in bilateral trade, but this guarantee breaks down as the market grows: even in a one-seller, two-buyer market, any algorithm using SinglePrice Mechanisms suffers regret at least Ωlog log T log log log log T , and we provide a nearly matching O(log log T) upper bound for general one-to-many markets.

Constant regret is possible in bilateral trade, but this guarantee fails as the market grows; for instance, even in a one-seller, two-buyer market, Single-Price Mechanisms incur a lower bound of omega(T T) regret. p. 0
Where the paper says it

Constant regret is achievable in bilateral trade, but this guarantee breaks down as the market grows: even in a one-seller, two-buyer market, any algorithm using SinglePrice Mechanisms suffers regret at least Ωlog log T log log log log T , and we provide a nearly matching O(log log T) upper bound for general one-to-many markets. In full many-to-many markets, we prove that Two-Price Mechanisms inevitably incur linear regret Ω(T) due to a mismatch phenomenon, wherein inefficient pairings prevent near-optimal trade.

In full many-to-many markets, Two-Price Mechanisms suffer from a mismatch phenomenon leading to linear regret (omega(T)). p. 0
Where the paper says it

Constant regret is achievable in bilateral trade, but this guarantee breaks down as the market grows: even in a one-seller, two-buyer market, any algorithm using SinglePrice Mechanisms suffers regret at least Ωlog log T log log log log T , and we provide a nearly matching O(log log T) upper bound for general one-to-many markets. In full many-to-many markets, we prove that Two-Price Mechanisms inevitably incur linear regret Ω(T) due to a mismatch phenomenon, wherein inefficient pairings prevent near-optimal trade.

Segmented-Price Mechanisms are introduced to mitigate this, achieving O(n squared T + n 3) regret for GFT maximization. p. 0
Where the paper says it

To overcome this barrier, we introduce Segmented-Price Mechanisms, which partition traders into groups and assign distinct prices per group. Using this richer mechanism, we design an algorithm achieving O(n 2 log log T + n 3 ) regret for GFT maximization.

The analysis extends to the contextual setting where traders' costs and values depend linearly on observed d-dimensional features that vary across rounds. In this extension, sellers have private cost vectors theta i in R d and buyers have private value vectors beta j in R d. p. 3

Where the paper says it

In this setting, traders’ private type (i. , seller’s cost and buyer’s value) remains constant across rounds.

In each round t, an adversarially chosen product context x t in R d is revealed, yielding costs c i,t = theta i, x t and values v j,t = beta j, x t. p. 8
Where the paper says it

Each seller i ∈ S can produce at most one unit of a homogeneous product and has a fixed private cost ci ∈ [0, 1] for producing that unit, while each buyer j ∈ B demands at most one unit and has a fixed private value vj ∈ [0, 1] for receiving it. These costs and values are traders’ private information, which are unknown to the learner, and remain constant throughout the T rounds.

The platform's per-round payoff depends on the objective: total collected revenue minus total payments for profit maximization; or total surplus generated by executed trades (sum of buyer values minus seller costs) for GFT maximization.

The paper defines benchmarks: Gft[M] = sum(i,j) in M (v j - c i) and the optimum Gft achievable via optimal matching. p. 3

Where the paper says it

This paper focuses on the more realistic—and challenging— setting in which the platform has no prior knowledge of either side’s types, so learning must occur online. We evaluate performance via regret minimization: for GFT, regret is benchmarked against the first-best GFT, which is achievable under full information using Single-Price Mechanisms; for profit, it is benchmarked against the optimal profit attainable by any Two-Price Mechanism, the simplest mechanism class that yields non-trivial profit.

For profit, the benchmark is Profit within Two-Price Mechanisms, defined as k in [n, m] k times (v(k) - c(k)). p. 9
Where the paper says it

Specifically, given any TwoPrice Mechanism with seller-side price p and buyer-side price q, the induced profit is defined as the difference between the total prices charged to all matched buyers and the total prices paid to all matched sellers, i. , Profit[p, q] = min {|{i ∈ S : ci ≤ p}|, |{j ∈ B : vj ≥ q}|} | {z } number of trading pairs ·(q − p) | {z } profit from each trading pair We define the optimum profit benchmark Profit⋆ (within the class of Two-Price Mechanisms) as the highest profit achievable by any Two-Price Mechanisms.

Regret is measured against these benchmarks. p. 3
Where the paper says it

The notation O ⋆ indicates that the regret bounds are optimal with respect to the time horizon T. All lower bounds expressed using Ω(·) hold against any algorithm that implements the corresponding mechanism class.

In the contextual setting, regret bounds are O(n 2d T + n 2d d) for profit and O(n 2d squared T) for GFT. p. 0

Where the paper says it

Using this richer mechanism, we design an algorithm achieving O(n 2 log log T + n 3 ) regret for GFT maximization. Finally, we extend our results to the contextual setting, where traders’ costs and values depend linearly on observed d-dimensional features that vary across rounds, obtaining regret bounds of O(n 2d log log T + n 2d log d) for profit and O(n 2d 2 log T) for GFT.

The work highlights sharp boundaries between learnable and unlearnable regimes in dynamic pricing, showing that increased pricing expressiveness can overcome fundamental hardness barriers. p. 0
Where the paper says it

Finally, we extend our results to the contextual setting, where traders’ costs and values depend linearly on observed d-dimensional features that vary across rounds, obtaining regret bounds of O(n 2d log log T + n 2d log d) for profit and O(n 2d 2 log T) for GFT. Our work delineates sharp boundaries between learnable and unlearnable regimes in two-sided dynamic pricing and demonstrates how modest increases in pricing expressiveness can circumvent fundamental hardness barriers.

The analysis further details the performance of a specific algorithm, Multi-Scale Steiner Profit Maximization (Algorithm 11), in the contextual two-sided market model for profit maximization. p. 4

Where the paper says it

Building on this idea, we further generalize both the algorithm and its regret guarantee to contextual two-sided markets (see discussion below). 2 GFT Maximization in Two-Sided Market Model We now turn to the problem of maximizing gains-from-trade (GFT) in two-sided market models.

The final bound derived by combining results from Type-1 rounds (O(n 2d d + n 2d T)), Type-2 rounds (O(n 2d d)), and Type-3 rounds (O(n 2d d)) yields a cumulative regret of O(n 2d T + n 2d d). p. 2
Where the paper says it

In each round, the platform interacts with a set of sellers and buyers with private types—costs for sellers and values for buyers—and the platform posts prices to both sides. In the base model, we assume that each trader’s private type remains fixed across rounds (though types may differ across traders).

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Contextual Price Posting for Profit Maximization: The system can implement Multi-Scale Steiner Profit Maximization (Algorithm 11) to achieve O(n 2d log log T) regret in contextual two-sided markets for profit maximization, allowing it to adapt pricing based on round-dependent context vectors.

  2. Robust Two-Segmented Pricing for GFT: The system can use the Balance Two-Segmented Pricing (Algorithm 7) to achieve O(n squared log log T + n 3) regret in gains-from-trade maximization in general two-sided markets, effectively bypassing the linear regret barrier of standard two-price mechanisms.

  3. Ellipsoid Search for Contextual GFT: The system can employ the Ellipsoid Search (Algorithm 10) to achieve O(n 2d squared log T) regret in contextual gains-from-trade maximization by using ellipsoid methods to explore uncertainty sets defined by trader feature vectors and context vectors.

  4. Exploitation of Contextual Information in Pricing: The system can dynamically determine the optimal posted price based on the contextual feature vector xt, as shown in Algorithm 11, specifically by setting prices based on temporary values derived from volume ratios within padded uncertainty sets.

Abstract

We study dynamic pricing for gains-from-trade maximization in two-sided markets. Over T rounds, a platform posts prices to traders with fixed, unknown costs and values and learns from their accept/reject decisions. Under weak budget balance and random matching among accepting traders, we investigate how market composition and pricing flexibility affect the regret achievable by deterministic learning policies. Uniform pricing achieves constant regret in bilateral trade and O(T) regret in one-to-many markets, with both rates remaining order-optimal even when side-specific pricing is allowed. However, side-specific pricing incurs Ω(T) worst-case regret with only three sellers and three buyers. This barrier persists even when a common price achieves the optimum under full information. The difficulty arises from a mismatch phenomenon: less efficient accepting traders can displace more efficient traders, making price exploration costly. We overcome this barrier through segmented pricing, which partitions each side into at most two groups and assigns a price to each group. Our algorithm achieves O(n T + n 2) regret with n traders on each side, which is order-optimal in the horizon. Thus, limited price differentiation within each side restores vanishing average regret even when the platform seeks to maximize gains-from-trade. We also extend our results to contextual markets and show that side-specific pricing suffices for doubly logarithmic regret under contextual profit maximization.

Sources

Related papers