Abstract This paper addresses the fundamental economic problem of maximizing an intermediary's profit in a two-sided market consisting of multiple buyers and sellers. We introduce a general reduction framework that transforms profit-maximizing mechanisms from production-cost markets (where costs are known) to two-sided markets (where costs are private). By identifying cost-monotonicity as a critical requirement, we develop the first mechanism to achieve a constant-factor (8-approximation) of the optimal broker profit in complex settings where buyers have additive valuations. This work bridges the gap between one-sided auction theory and the more complex dynamics of brokered exchanges.
1. Introduction
In a two-sided market—exemplified by platforms like used-car marketplaces or antique auction houses—a broker acts as a middleman, purchasing items from sellers and reselling them to buyers. The broker’s objective is to maximize the spread between the total payments received from buyers and the total payments made to sellers.
The primary challenge in this setting is information asymmetry. Sellers possess private "reserve" values for their items, while buyers have private "valuation" functions for bundles of items. To maximize profit, the broker must design a mechanism that is Dominant-Strategy Incentive Compatible (DSIC), ensuring that every participant’s optimal strategy is to report their true value. While one-sided auction theory is well-established, two-sided markets are notoriously difficult because the broker must simultaneously elicit truthful information from both sides while maintaining a profitable margin.
2. Theoretical Framework: The Cost-Monotone Reduction
The paper’s core methodology relies on bridging the gap between two-sided markets and "production-cost markets," where the broker produces items at a publicly known cost. The authors prove that any mechanism for a production-cost market that is cost-monotone can be converted into a mechanism for a two-sided market using a "black-box" approach.
Cost-monotonicity implies that the probability of selling an item does not increase if its production cost increases. In this reduction, the sellers' virtual values—a concept from Myersonian auction theory—are treated as the "costs." This allows researchers to leverage existing one-sided auction literature to solve the more complex two-sided problem without reinventing the underlying incentive structures.
3. Mechanism Design for Additive Valuations
For the specific case where buyers have additive valuations (where the value of a bundle is the sum of the values of individual items), the authors construct a hybrid mechanism, $M_A$. This mechanism strategically chooses between two sub-mechanisms to maximize the expected profit:
- $M_{IT}$ (Item-wise): This sub-mechanism runs separate optimal auctions for each individual item.
- $M_{BVCG}$ (Bundling VCG): This is a "Bundling Vickrey-Clarke-Groves" mechanism that utilizes per-item reserve prices and per-agent entry fees to extract profit from the buyers' collective valuations.
By balancing these two approaches, the broker can capture profit from both high-value individual items and the aggregate demand of the buyer pool.
4. Key Results
The paper establishes two landmark theoretical results:
- Theorem 1 (The Reduction): Any cost-monotone, $\alpha$-approximate DSIC mechanism for production-cost markets can be converted into an $\alpha$-approximate DSIC mechanism for two-sided markets.
- Theorem 3 (The 8-Approximation): For buyers with additive valuations, the authors provide a specific DSIC mechanism that guarantees at least 12.5% (1/8) of the maximum possible expected profit. This represents the first constant-approximation result for this general multi-parameter setting.
5. Discussion and Future Work
While the 8-approximation is a significant theoretical milestone, the constant factor remains relatively large, suggesting room for optimization. Furthermore, while the reduction framework is general, the specific 8-approximation result is currently limited to additive valuations. Extending these guarantees to other valuation types—such as unit-demand or sub-additive valuations—remains a challenging open problem.
Finally, while the mechanisms are "simple" in a game-theoretic sense (DSIC), the computational overhead of calculating entry fees and virtual values in high-dimensional valuation spaces warrants further investigation for practical implementation in real-time market environments.
Reference: Chen, J., Li, B., & Li, Y. (2019). Approximately Maximizing the Broker’s Profit in a Two-sided Market. arXiv preprint arXiv:1905.09347v1.
Summary updated