Online Two-Sided Markets: Many Buyers Enhance Learning

We study a repeated trading problem in which a mechanism designer facilitates trade between a single seller and multiple buyers. Our model generalizes the classic bilateral trade setting to a multi-buyer environment. Specifically, the mechanism designer runs a second-price auction among the buyers -- extending the fixed-price mechanism used in bilateral trade -- before proposing a price to the seller. While this setting introduces new challenges compared to bilateral trade, it also provides an informational advantage. Indeed, the presence of multiple buyers enhances competition, inducing them to reveal their valuations in order to win the auction. However, as in bilateral trade, the seller faces a binary decision: whether to accept the proposed price or not. We show that this asymmetric feedback, which is more informative than in bilateral trade, allows us to break some lower bounds on regret minimization with a single buyer. In particular, we provide a tilde O(T2/3) regret upper bound with respect to an optimal strong budget-balanced mechanism, without any assumptions on the distribution of valuations. Our main tool for achieving this result is the design of an adaptive grid that approximates the optimal gain from trade across the continuum of possible mechanisms. Furthermore, we attain the same regret bound with respect to an optimal global budget-balanced mechanism, under two possible conditions: (i) buyers' and seller's valuations are independent, or (ii) valuations are drawn from a distribution with bounded density. In doing so, we provide some novel technical results on constrained MABs with feedback graphs, which may be of independent interest.