Fair Online Bilateral Trade

François Bachoc, Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni

This paper tackles a fundamental tension in online marketplaces: the trade-off between maximizing total social welfare and ensuring a fair split of the "surplus" between buyers and sellers. By introducing the concept of "fair gain from trade" (FGFT), the authors provide a complete theoretical characterization of how hard it is to learn optimal fair prices. They prove that while fairness is harder to achieve than simple welfare maximization, it is possible with the right algorithmic approach.

The Challenge of Fair Pricing

In a standard online bilateral trade model, a platform matches a buyer and a seller, both of whom have private valuations for a good. The platform suggests a price; if the price falls between the seller's minimum and the buyer's maximum, a trade occurs.

Traditionally, platforms aim to maximize the Gain From Trade (GFT)—the sum of the buyer's and seller's utilities. However, this can be highly unfair. For example, if a seller values an item at $10 and a buyer at $100, a price of $11 generates $90 of total gain but is highly asymmetric: the seller gets $1, while the buyer gets $89. Such lopsided deals can discourage long-term platform participation.

To address this, the authors propose maximizing the Fair Gain From Trade (FGFT), defined as the minimum of the two utilities. Inspired by the Rawlsian "max-min" rule, this objective forces the platform to find prices as close to the midpoint of the valuations as possible. The primary challenge is that the platform doesn't know the true valuations; it only receives "two-bit feedback" (i.e., whether the seller accepted and whether the buyer accepted).

Algorithmic Approaches

The paper provides new algorithms and proves their performance limits (regret bounds) under different conditions:

  • The Convolution Lemma: The paper's core theoretical innovation proves that the expected fair gain can be expressed as a convolution of the probability distributions of the seller's and buyer's valuations. This allows the algorithm to estimate the reward function even without direct observation.
  • Convolution Pricing: Designed for the stochastic setting where valuations are independent. It uses a uniform grid of prices to gather data, then applies a discrete convolution to estimate the best fair price.
  • Double Binary Search: For the deterministic case (where valuations are fixed but unknown), this algorithm performs two separate binary searches to "bracket" the seller's and buyer's valuations, eventually converging on the optimal midpoint.

Key Insights

  • Efficiency $\neq$ Fairness: Standard "no-regret" algorithms designed to maximize total gain can fail miserably at being fair, often suffering linear regret (meaning they never stop making significant errors).
  • The Independence Requirement: In the stochastic setting, if the buyer's and seller's valuations are correlated, it is mathematically impossible to learn the fair price with only two-bit feedback. Valuations must be independent to achieve sublinear regret.
  • Information is Costly: In the deterministic case, maximizing total gain is "easy" (constant regret), but maximizing fair gain is "hard" ($\Theta(\ln T)$ regret). The platform must intentionally post suboptimal prices just to gather enough information to find the fair midpoint.

Regret Bounds and Results

The paper provides a complete map of the "regret regimes"—essentially how much utility is lost while the algorithm is learning.

Key findings from the analysis include:

  • Deterministic: Learning is relatively fast, with regret growing only logarithmically ($\Theta(\ln T)$).
  • Stochastic (Independent): Learning is slower ($\tilde{\Theta}(T^{2/3})$), representing the cost of dealing with random fluctuations and limited feedback. This rate is a classic signature of "partial monitoring" problems, where the learner must balance earning rewards with taking "revealing" actions.
  • Full Feedback: If the platform can see the true valuations after each round, the problem becomes much easier, reaching the standard $\sqrt{T}$ rate seen in many other machine learning problems.

Limitations and Future Directions

The $\tilde{\Theta}(T^{2/3})$ result relies heavily on the assumption that buyer and seller valuations are independent. In many real-world markets, valuations are likely correlated (e.g., both parties are influenced by the same macroeconomic trends). Furthermore, the current model assumes valuations are drawn from a fixed distribution. Future work could explore "contextual" bilateral trade, where valuations depend on external features like time or user profiles, or extend the model to large-scale matching markets with many buyers and sellers.

Summary updated

Abstract

In online bilateral trade, a platform posts prices to incoming pairs of buyers and sellers that have private valuations for a certain good. If the price is lower than the buyers' valuation and higher than the sellers' valuation, then a trade takes place. Previous work focused on the platform perspective, with the goal of setting prices maximizing the *gain from trade* (the sum of sellers' and buyers' utilities). Gain from trade is, however, potentially unfair to traders, as they may receive highly uneven shares of the total utility. In this work we enforce fairness by rewarding the platform with the _fair gain from trade_, defined as the minimum between sellers' and buyers' utilities. After showing that any no-regret learning algorithm designed to maximize the sum of the utilities may fail badly with fair gain from trade, we present our main contribution: a complete characterization of the regret regimes for fair gain from trade when, after each interaction, the platform only learns whether each trader accepted the current price. Specifically, we prove the following regret bounds: $\Theta(\ln T)$ in the deterministic setting, $\Omega(T)$ in the stochastic setting, and $\tilde{\Theta}(T^{2/3})$ in the stochastic setting when sellers' and buyers' valuations are independent of each other. We conclude by providing tight regret bounds when, after each interaction, the platform is allowed to observe the true traders' valuations.
BibTeX
@inproceedings{bachoc2024fair,
  author = {François Bachoc and Nicolò Cesa-Bianchi and Tommaso Cesari and Roberto Colomboni},
  title = {{Fair Online Bilateral Trade}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=I90ypQpLgL},
}
Figure