Repeated Bilateral Trade: The Quest for Fairness
For platforms seeking fair surplus division in repeated bilateral trade, this work provides the first optimal learning rates for a family of fair-gain objectives, addressing a gap in prior work focused solely on efficiency or Rawlsian fairness.
The paper studies repeated bilateral trade with fairness objectives, proposing a family of fair-gain objectives that interpolate between Rawlsian and Nash bargaining. It provides matching sample-complexity and regret bounds for learning these objectives under unknown i.i.d. valuations.
We study repeated bilateral trade from a fairness perspective. At each round, a fresh seller-buyer pair arrives, and the platform posts a price before observing the traders' valuations. Trade occurs only if both agents accept the price. Rather than maximizing only the gain from trade, we consider platforms that seek balanced divisions of the generated surplus. We show that natural fairness desiderata lead to a one-parameter Rawls-to-Nash family of fair-gain objectives, obtained by aggregating the seller's and buyer's net gains through nonpositive Hölder means. Unlike the standard gain-from-trade objective and the Rawlsian fair-gain objective studied in prior work, our proposed objectives induce a new statistical structure in which expected rewards are recovered from threshold feedback through a two-dimensional singular-kernel integral identity. This leads to a nonstandard pure-exploration problem whose natural estimators are rectangular double sums with row-column dependence and singular weights. Assuming independent i.i.d. seller and buyer valuation sequences with arbitrary unknown marginals, we characterize the optimal learning rates for the whole Rawls-to-Nash family of fair-gain objectives, giving matching fixed-confidence sample-complexity and regret bounds up to polylogarithmic factors.