Online Bilateral Trade With Minimal Feedback: Don’t Waste Seller’s Time
algorithm designasynchronous mechanismbilateral trade mechanismsbounded densitiesbuyer-seller interactioncensored feedbackdistributional conditionsfeedback efficiencyfixed price comparisonindependent valuationsonline learningoptimal ratesregret minimizationtrade acceptancetwo-bit feedback models
Online learning algorithms for designing optimal bilateral trade mechanisms have recently received significant attention. This paper addresses a key inefficiency in prior two-bit feedback models, which synchronously query both the buyer and the seller for their willingness to trade. This approach is inherently inefficient as it offers a trade to the seller even if the buyer rejects the offer. We propose an asynchronous mechanism that queries the seller only if the buyer has already accepted the offer. Consequently, the mechanism receives one bit of feedback from the buyer and a "censored" bit from the seller