Dynamic Pricing in Two-Sided Markets: Learning Barriers and Price Differentiation
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 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 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.Where the paper says it
Where the paper says it
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 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 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 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 In this setting, traders’ private type
(i. , seller’s cost and buyer’s value) remains constant across rounds. 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.Where the paper says it
Where the paper says it
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 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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. 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).Where the paper says it
Where the paper says it
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
-
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.
-
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.
-
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.
-
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
- Tight Regret Bounds for Fixed-Price Bilateral Trade
- Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade
- Tight Regret Bounds for Bilateral Trade under Semi Feedback
- Online Two-Sided Markets: Many Buyers Enhance Learning
Related papers
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments