Nonparametric Contextual Online Bilateral Trade
This work addresses market design challenges for online platforms by enabling efficient trade facilitation without subsidies or profit, though it is incremental by extending prior linear models to nonparametric ones.
The paper tackles the problem of contextual online bilateral trade in a nonparametric setting, where buyer and seller valuations are arbitrary Lipschitz functions of context, and achieves a regret bound of ̃O(T^{(d-1)/d}) under one-bit feedback and strong budget balance constraints.
We study the problem of contextual online bilateral trade. At each round, the learner faces a seller-buyer pair and must propose a trade price without observing their private valuations for the item being sold. The goal of the learner is to post prices to facilitate trades between the two parties. Before posting a price, the learner observes a $d$-dimensional context vector that influences the agent's valuations. Prior work in the contextual setting has focused on linear models. In this work, we tackle a general nonparametric setting in which the buyer's and seller's valuations behave according to arbitrary Lipschitz functions of the context. We design an algorithm that leverages contextual information through a hierarchical tree construction and guarantees regret $\widetilde{O}(T^{{(d-1)}/d})$. Remarkably, our algorithm operates under two stringent features of the setting: (1) one-bit feedback, where the learner only observes whether a trade occurred or not, and (2) strong budget balance, where the learner cannot subsidize or profit from the market participants. We further provide a matching lower bound in the full-feedback setting, demonstrating the tightness of our regret bound.