Abstract
We investigate online pricing in two-sided markets where a platform repeatedly posts prices based on binary accept/reject feedback to maximize gains-from-trade (GFT) or profit. We characterize the regret achievable across three mechanism classes: Single-Price, Two-Price, and Segmented-Price. For profit maximization, we design an algorithm using Two-Price Mechanisms that achieves $O(n^2 \log\log T)$ regret, 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 Single-Price Mechanisms suffers regret at least $\Omega\!\big(\frac{\log\log T}{\log\log\log\log T}\big)$, 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 $\Omega(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. 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^2 d \log\log T + n^2 d \log d)$ for profit and $O(n^2 d^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.
Introduction
In modern two-sided marketplaces like Uber, Airbnb, or Temu, a platform acts as a matchmaker between buyers and sellers. A central challenge for these platforms is setting prices that maximize economic outcomes—either the platform's own profit or the total Gains-from-Trade (GFT). However, the platform typically lacks precise information regarding a buyer's "willingness-to-pay" or a seller's "willingness-to-accept." Instead, it must learn these values over time through binary feedback: observing whether a transaction occurs at a given price point.
While dynamic pricing for one-sided markets is well-understood, two-sided markets introduce a complex balancing act. The platform must manage uncertainty on both sides of the trade simultaneously. This paper provides a theoretical framework for this problem, analyzing how the expressiveness of the pricing mechanism affects the platform's ability to minimize regret—the cumulative loss compared to an omniscient strategy over $T$ rounds.
Mechanism Expressiveness and Methodology
The authors categorize pricing strategies into three levels of expressiveness:
- Single-Price: A uniform price applied to all participants.
- Two-Price: One price for all sellers and another for all buyers.
- Segmented-Price: Traders are partitioned into groups, with different prices assigned to each group.
To navigate the trade-off between exploration (learning values) and exploitation (maximizing GFT or profit), the researchers developed several algorithmic strategies. For simple bilateral trade, an Optimistic Binary Search achieves constant regret. In more complex many-to-many markets, they employ a Balancing Search strategy. This approach uses Segmented-Price mechanisms to isolate "known" efficient traders from "uncertain" ones, ensuring that exploration does not compromise overall matching efficiency.
For contextual settings where trader values depend on $d$-dimensional features (e.g., location or time), the authors utilize the Ellipsoid Method and Steiner Polynomials to systematically reduce the volume of uncertainty in high-dimensional space.
The Mismatch Phenomenon
A key conceptual discovery of this work is the mismatch phenomenon. In many-to-many markets, if a platform is restricted to only two prices (one for buyers, one for sellers), it may inadvertently match a high-value buyer with a high-cost seller, even if a lower-cost seller was available.
This mismatch creates a persistent loss of GFT in every round, leading to linear regret—meaning the algorithm never converges to an optimal state. Crucially, the authors prove this is not a failure of the learning algorithm itself, but a fundamental limitation of the Two-Price mechanism. By increasing expressiveness to Segmented-Price mechanisms (using as few as four prices), the platform can prevent these inefficient pairings and restore "learnability."
Summary of Regret Bounds
The paper establishes a clear hierarchy of regret bounds based on the market setting and the objective. Notably, profit maximization is found to be more robust than GFT maximization; the platform's margin acts as a buffer, allowing for low regret even with simpler Two-Price mechanisms.
As shown in the table above, GFT maximization in many-to-many markets requires Segmented-Price mechanisms to avoid the $\Omega(T)$ regret trap. In contrast, profit maximization achieves $O(n^2 \log \log T)$ regret using Two-Price mechanisms across all non-contextual market types.
Conclusion and Future Directions
This research delineates the boundaries of what is learnable in two-sided markets. It demonstrates that while simple pricing schemes may suffice for profit, maximizing social welfare (GFT) in large markets necessitates more expressive, segmented pricing to overcome the mismatch phenomenon.
Future work may address several remaining challenges:
- Fluid Populations: Extending the model to settings where the set of traders changes over time rather than remaining fixed.
- Non-linear Contexts: Moving beyond linear dependencies in contextual pricing to explore kernelized or non-parametric models.
- Strategic Behavior: Accounting for participants who might strategically reject prices to influence the platform's future pricing decisions, requiring the integration of long-term incentive compatibility.
Summary updated