Approximately Maximizing the Broker's Profit in a Two-sided Market

Jing Chen, Bo Li, Yingkai Li

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

Abstract

We study how to maximize the broker's (expected) profit in a two-sided market, where she buys items from a set of sellers and resells them to a set of buyers. Each seller has a single item to sell and holds a private value on her item, and each buyer has a valuation function over the bundles of the sellers' items. We consider the Bayesian setting where the agents' values/valuations are independently drawn from prior distributions, and aim at designing dominant-strategy incentive-compatible (DSIC) mechanisms that are approximately optimal. Production-cost markets, where each item has a publicly-known cost to be produced, provide a platform for us to study two-sided markets. Briefly, we show how to covert a mechanism for production-cost markets into a mechanism for the broker, whenever the former satisfies cost-monotonicity. This reduction holds even when buyers have general combinatorial valuation functions. When the buyers' valuations are additive, we generalize an existing mechanism to production-cost markets in an approximation-preserving way. We then show that the resulting mechanism is cost-monotone and thus can be converted into an 8-approximation mechanism for two-sided markets.
BibTeX
@inproceedings{chen2019approximately,
  author = {Jing Chen and Bo Li and Yingkai Li},
  title = {{Approximately Maximizing the Broker's Profit in a Two-sided Market}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/22},
}
Figure