TL;DR
This paper introduces a generalized "Rawls-to-Nash" family of fairness objectives for repeated bilateral trade, balancing market efficiency with equitable surplus division between buyers and sellers. Operating under highly restrictive threshold feedback (only observing binary accept/reject decisions), the authors design a universal exploration strategy that achieves optimal learning rates and matching $\tilde{O}(T^{2/3})$ minimax regret bounds.
What Problem Does This Paper Address?
Online bilateral trade studies how an intermediary platform can learn to price goods over repeated interactions with incoming streams of sellers and buyers. Traditionally, platforms optimize solely for efficiency—maximizing the total "gain from trade" (the generated surplus). However, efficiency metrics are blind to how this surplus is divided; a posted price could exploit one side entirely while yielding the same total gain.
While prior work explored a Rawlsian (max-min) fairness objective to protect the worst-off agent, this paper addresses the lack of a unified framework for a continuous spectrum of fairness criteria. Crucially, the platform faces a severe observability barrier: it never observes the actual valuations of the traders, only binary "accept/reject" threshold decisions based on the posted price.
Methods
The authors tackle this problem through a combination of axiomatic economics and non-standard online learning techniques:
- Axiomatic Fairness Framework: They prove that any fair-gain objective satisfying three basic structural desiderata (equal-gain equivalence, scale covariance, and zero fairness for one-takes-all splits) must belong to the family of nonpositive Hölder means. This parameterizes a continuous spectrum from Rawlsian max-min fairness ($\lambda \to -\infty$) to Nash geometric-mean fairness ($\lambda = 0$).
- Kernel Reconstruction Lemma: To circumvent unobservable rewards, the authors derive a two-dimensional integral identity using a singular kernel $H_\lambda$. This allows the expected fair-gain objective to be reconstructed purely from observable threshold feedback (the seller's CDF and the buyer's survival function).
- Universal Exploration & Truncated Estimators: They propose a $\lambda$-agnostic exploration protocol (Algorithm 2) that samples prices on a randomized grid. To handle the row-column dependence and prevent infinite variance from the singular kernel near boundaries, they introduce a truncated rectangular estimator.
- $\lambda$-Free Recommender: The algorithm dynamically switches between a finite-$\lambda$ estimator and a Rawlsian proxy depending on whether $1-\lambda \le \sqrt{n}$, effectively eliminating harmful mathematical dependencies on the fairness parameter.
- Rectangular McDiarmid Inequality: As a core technical tool, the authors develop a novel concentration inequality for row-column dependent double sums, which is broadly applicable to problems involving recombined independent populations.
The complex interplay and dependencies of these theoretical components are mapped out by the authors in their proof-dependency graph:
Datasets
Not discussed in the paper. The work is purely theoretical, utilizing rigorous mathematical proofs and synthetic adversarial environments to establish matching upper and lower bounds.
Key Insights and Ideas
- The Rawls-to-Nash Continuum: Fairness does not have to be a single rigid choice. Nonpositive Hölder means elegantly bridge the gap between protecting the worst-off participant (Rawls) and maximizing product-based social welfare (Nash).
- The Necessity of Independence: Reconstructing rewards from binary feedback requires a 2D singular kernel. This mathematical structure reveals that independence between buyer and seller valuations within each round is a fundamental learnability threshold; if valuations are arbitrarily dependent, the problem becomes completely unlearnable.
- Agnosticism via Switching: By using the Rawlsian estimator as a proxy when $\lambda$ is highly negative, the platform can make optimal recommendations without needing to know or fine-tune for the exact fairness level during the data-collection phase.
Key Results
The paper establishes tight minimax optimal rates for the entire Rawls-to-Nash family under independent valuation streams:
- Optimal Pure Exploration: For both fixed and uniform-in-fairness settings, the algorithm achieves a Probably Approximately Correct (PAC) sample complexity of $\tilde{O}(\epsilon^{-2})$, matching the proven information-theoretic lower bound up to polylogarithmic factors.
- Optimal Regret Minimization: When turned into an Explore-Then-Commit (ETC) strategy, the algorithm yields an expected regret bound of $\tilde{O}(T^{2/3})$, which is proven to be minimax-optimal.
- The Cost of Dependence: Theorem 10 proves that if the independence assumption between seller and buyer valuations within a round is dropped, any pricing policy will suffer linear regret $\Omega(T)$, confirming that independence is a strict requirement for learnability in this protocol.
Limitations and Future Work
- Mechanism Constraints: The current analysis is strictly limited to a single posted price mechanism per round.
- Independence Assumption: While the authors prove that independence is necessary under the current protocol, future work could explore richer market mechanisms (such as double auctions, bargaining protocols, or budget-balanced mechanisms) that might provide additional feedback or relax this assumption.
- Constant Optimization: The logarithmic factors and large universal constants (e.g., $C_{unif} = 864000$ in Theorem 6) are conservative and leave room for tighter optimization.
Summary updated