Contextual Search and Bilateral Trade with a Trace-Square-Root Potential
Organizations: Computer Science Department, New York University, NYC, United States. · Department of Computer, Control, and Management Engineering, Sapienza University, Rome, Italy. · Google Research, NYC, United States. · EPFL, Lausanne, Switzerland.
Abstract
We present a unified potential method for contextual search and bilateral trade with one-bit feedback and obtain order-tight algorithms for both problems. Our framework starts from a Bayesian perspective in which the unknown target (for contextual search) and the unknown pair of valuations (for bilateral trade) are sampled from a known prior distribution. In that model, the decision maker bases its prediction on the posterior distribution, obtained by conditioning on feedback received in previous rounds. For Bayesian contextual search, we present an algorithm with a total loss bounded by , where is the covariance matrix of the target's prior; and for contextual bilateral trade, our algorithm's regret is bounded by , where and are the covariance matrices of the seller's and buyer's valuations. We then use ideas from this Bayesian setting and adapt a ``dual'' of this trace-square-root potential to the classical worst-case setting, where the target and valuations are chosen adversarially from the unit Euclidean ball. For both contextual search and bilateral trade, we obtain tight -regret algorithms. These results match the existing lower bounds up to a constant factor and improve on the previous guarantees of for contextual search and of for bilateral trade.
Figures & tables
| Result | Contextual search | Bilateral trade |
| Standard lower bound [ 16 , 9 ] | ||
| Paes Leme and Schneider [ 19 ] | — | |
| Liu, Paes Leme, and Schneider [ 16 ] | — | |
| Cosson et al. [ 9 ] | — | |
| This paper (Thms. 2.4 and 3.4 ) | (Alg. 2 ) | (Alg. 4 ) |
| Result | Contextual search | Bilateral trade |
|---|---|---|
| This paper (Thms. 2.1 and 3.2 ) | (Alg. 1 ) | (Alg. 3 ) |
| (8) |
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.