Abstract
We study the role of contextual information in the online learning problem ofbrokerage between traders. In this sequential problem, at each time step, twotraders arrive with secret valuations about an asset they wish to trade. Thelearner (a broker) suggests a trading (or brokerage) price based on contextualdata about the asset and the market conditions. Then, the traders reveal theirwillingness to buy or sell based on whether their valuations are higher orlower than the brokerage price. A trade occurs if one of the two tradersdecides to buy and the other to sell, i.e., if the broker's proposed pricefalls between the smallest and the largest of their two valuations. We designalgorithms for this problem and prove optimal theoretical regret guaranteesunder various standard assumptions.