Contextual Online Bilateral Trade Part of this work was done while Federico Fusco, Stefano Leonardi, and Matteo Russo were visiting Anupam Gupta at New York University. The work of RC and AG was supported in part by NSF awards CCF-2422926 and CCF-2608359. The work of FF and SL was supported in part by the MUR PRIN grant 2022EKNE5K and the FAIR (Future Artificial Intelligence Research) project PE0000013, funded by the NextGenerationEU program within the PNRR-PE-AI scheme (M4C2, investment 1.3, line on Artificial Intelligence) Romain Cosson, Federico Fusco, Anupam Gupta, Stefano Leonardi, Renato Paes Leme, Matteo Russo Abstract We study repeated bilateral trade when the valuations of the sellers and the buyers are contextual. More precisely, the agents’ valuations are given by the inner product of a context vector with two unknown d d -dimensional vectors—one for the buyers and one for the sellers. At each time step t t , the learner receives a context and posts two prices, one for the seller and one for the buyer, and the trade happens if both agents accept their price. We study two objectives for this problem, gain from trade and profit, proving no-regret with respect to a surprisingly strong benchmark: the best omniscient dynamic strategy. In the natural scenario where the learner observes separately whether the agents accept their price—the so-called two-bit feedback—we design algorithms that achieve O ⁡ ( d ​ log ⁡ d ) O(d\log d) regret for gain from trade, and O ⁡ ( d ​ log ⁡ log ​ T + d ​ log ⁡ d ) O(d\log\log T+d\log d) regret for profit maximization. Both results are tight, up to the log ⁡ ( d ) \log(d) factor, and implement per-step budget balance, meaning that the learner never incurs negative profit. In the less informative one-bit feedback model, the learner only observes whether a trade happens or not. For this scenario, we show that the tight two-bit regret regimes are still attainable, at the cost of allowing the learner to possibly incur a small negative profit of order O ⁡ ( d ​ log ⁡ d ) O(d\log d) , which is notably independent of the time horizon. As a final set of results, we investigate the combination of one-bit feedback and per-step budget balance. There, we design an algorithm for gain from trade that suffers regret independent of the time horizon, but exponential in the dimension d d . For profit maximization, we maintain this exponential dependence on the dimension, which gets multiplied by a log ⁡ T \log T factor. 1 Introduction Online pricing is a well-studied problem at the intersection of theoretical computer science, machine learning, and economics ( 25 ; 24 ; 30 ) that dates back to the seminal papers by 20 and 5 . The task consists of finding the right pricing rule for certain types of goods by repeatedly interacting with prospective buyers and observing their reactions to the prices posted. A natural extension consists in studying the situation where the mechanism designer does not directly possess the goods to trade, but acts as an intermediary between demand and supply. While the offline version of this bilateral trade problem dates back to classic works of 31 and 28 , its online version has received a rapidly growing interest within the computer science community ( 7 ; 8 ; 2 ; 4 ; 26 ) . Indeed, finding the right balance between sellers and buyers gives rise to new and exciting challenges that qualitatively separate one-sided pricing and bilateral trade. In this work, we investigate bilateral trade from an online learning perspective, assuming that sellers’ and buyers’ valuations are parameterized as functions of context vectors ( 16 ) . Consider the following scenario, where an internet platform repeatedly intermediates between supply and demand in a certain market (e.g., ride-sharing, e-commerce, or ads). At each time step t , a new seller joins the platform, interested in selling a certain good; at the same time, an interested buyer arrives, and the platform observes their features summarized in a d -dimensional context vector x_{t} . The agents’ private valuations for the good for sale are then given by the public features, averaged by unknown but fixed weights . Formally, we assume that there are two unknown vectors s and b in \mathbb{R}^{d} that represent the relative importance of the various features, and that the agents’ valuations s_{t}=\langle s,x_{t}\rangle and b_{t}=\langle b,x_{t}\rangle are given by the scalar product of these two “ground truths” and the public context. Given the context x_{t} , the platform proposes two prices, p_{t} to the seller and q_{t} to the buyer, and the trade occurs if and only if both agents accept their prices. From a learning perspective, the platform’s goal is to design a pricing policy that takes as input the context at time t and computes the right prices based on agents’ past behavior. In this work, we consider the two most natural performance objectives for this problem: economic efficiency , measured in terms of the gain from trade, and profit . • The gain from trade equals the difference b_{t}-s_{t} if the trade happens, and zero otherwise. • The profit is simply the difference between the price paid by the buyer and that paid to the seller, q_{t}-p_{t} if the trade happens, and zero otherwise. At a high level, the gain from trade is maximized as soon as the learner posts two prices contained in the interval [s_{t},b_{t}] , while to extract good profit, the prices should also be “close” to the corresponding valuations. Our goal is to design learning algorithms for these two problems that exhibit small regret with respect to an ambitious benchmark: the best omniscient pricing strategy that knows s and b in advance. Notably, there exists a strategy that is optimal for both efficiency and profit maximization, which consists of posting p_{t}=s_{t} and q_{t}=b_{t} when s_{t}\leq b_{t} . Therefore, the two metrics share the same benchmark: \sum_{t}(b_{t}-s_{t})_{+} , where (\cdot)_{+} denotes the positive part. Following the literature (e.g., 7 , and follow-ups) , we consider two realistic feedback models for repeated bilateral trade: one- and two-bit feedback. • two-bit : The learner observes the willingness to accept their prices for both agents. • one-bit : The learner only observes whether the trade happened or not. These two models are motivated by practical considerations. The two-bit setting models the situation in which the learner communicates prices to the agents and observes whether each agent individually agrees to trade. Conversely, in the one-bit setting, the learner does not receive the disaggregated information on who rejected its proposed price. Furthermore these two feedback structures exhibit a desirable property that characterizes take-it-or-leave-it prices: agents communicate only a single bit of information to the platform, without revealing their private information. Beyond the non-trivial interplay of the two agents’ valuations in designing good pricing policies, bilateral trade exhibits a qualitative difference with respect to simple (one-sided) pricing: the requirement for the mechanism designer not to run into a deficit to make the trade happen. This is formalized by the budget-balance property ( 28 ) , which prescribes some constraint on how much the learner can subsidize the market (i.e., incur negative profit). 1.1 Our Results We present here our results; we also refer to Table 1 for a visual summary. Two-bit Feedback. In the two-bit feedback model, we have the following results: • We construct an efficiency-maximizing algorithm that suffers O(d\log d) regret ( Theorem 4.2 ). Our rate removes the dependence on T and improves on the dependence on d over the previous known bound of \tilde{O}(d^{2}\log T) 16 ; this is only a logarithmic (in d ) factor from the lower bound of \Omega(d) ( Proposition 4.3 ). • We construct a profit-maximizing algorithm that suffers O(d\log\log T+d\log d) regret ( Theorem 5.3 ). We show that the doubly-logarithmic dependence in T is essentially tight, by adapting ideas from 20 to get lower bound of \Omega(d\log\log\nicefrac{{T}}{{d}}) ( 25 ; see also Proposition 5.4 ). The above algorithms are deterministic and per-round budget balanced ( 7 , and follow-ups) : they only post prices p_{t}\leq q_{t} , ensuring that the per-round profit is non-negative. One-bit Feedback. In the one-bit feedback model, we present two sets of results, for different notions of budget balance. Our first set of results is when we allow ourselves the flexibility of posting prices p_{t}>q_{t} : • We adapt the two-bit feedback algorithms for both gain-from-trade and profit to work in the one-bit feedback model, at the expense of slightly violating per-round budget balance. • In particular, we recover the two-bit regret rates, with an overall negative profit 1 1 1 This is referred to as “budget violation” in the recent work by 26 . of order O(d\log d) ( Theorems 4.4 and 5.5 ). Notably, this term is independent of the time horizon. We then consider per-round budget balance (i.e., where we post prices p_{t}\leq q_{t} ), and design randomized learning algorithms enforcing such property with the following regret rates: • We construct an efficiency-maximizing algorithm that exhibits a regret independent of T of order O(d6^{d}) ( Theorem 4.8 ). • We construct a profit-maximizing algorithm with regret that depends logarithmically on T , of order O(d6^{d}\log T) ( Theorem 5.6 ). Two-bit / BB One-bit / non-BB One-bit / BB GFT \tilde{\Theta}(d) \tilde{\Theta}(d) O(d6^{d}) Profit \tilde{\Theta}(d\log\log T) \tilde{\Theta}(d\log\log T) O(d6^{d}\log T) Table 1 : Summary of our results. The \tilde{\Theta} hides factors that are logarithmic in the dimension. The results in the middle column hold at the expense of an overall negative profit of order O(d\log d) . BB stands for (per-round) budget balance. GFT stands for gain from trade. While explicitly requiring budget balance is crucial for efficiency maximization ( 28 ) (we do not want the learner to subsidize the market), it is less prominent for profit maximization, where the learner’s goal of accruing profit is naturally aligned with the budget balance property. In any case, budget balance is a desirable and natural property also for a profit-maximizing algorithm, and we investigate its impact on both metrics for completeness. Overall, it is remarkable that achieving such a small regret rate (even time-independent for GFT ) against the best dynamic prices is possible, in a non-stationary (although structured) environment. Comparison with previous work. While we are the first to study profit maximization, efficiency maximization in contextual bilateral trade has been introduced by 16 . They provide an \tilde{O}(d^{2}\log T) regret result for two-bit feedback, which we improve to a nearly-tight bound of O(d\log d) , removing the dependence on T and a \tilde{\Theta}(d) factor. 16 also investigate one-bit feedback, constructing algorithms that violate per-round budget balance, but have overall non-negative profit (This is called the global budget balance condition in 4 ). However, such results are instance-dependent and exhibit regret rates that are polynomial in T. In contrast, we either allow for (extremely) small negative profit and obtain tight regret rates, or maintain per-round budget balance, at the cost of worse dependence on the dimension d . Future Directions. We provide a fairly complete understanding of contextual bilateral trade under different feedback models and budget balance constraints. We mention two open directions for future works. (i) Characterizing the “budget vs. regret” trade off for one-bit feedback algorithms: given a violation budget B=B(d,T) , what is the minimax regret rate achievable with one-bit feedback and allowing for budget violation B (similarly to what has been recently done for adversarial bilateral trade in 26 )? (ii) Investigating contextual models that allow noisy or imprecise feedback. While more natural in applications, these models may not allow for sublinear regret against the best omniscient pricing strategy, so that weaker benchmarks (e.g., “best-fixed-strategy”) may need to be considered, likely with polynomial regret rates (as in 16 ). 1.2 Technical Challenges and Our Approach The algorithmic problem we face has a clean geometric interpretation: we want to s,b\in\mathbb{R}^{d} using special types of probes: given context x\in\mathbb{R}^{d} , we can post two prices p and q , and observes the outcome of the trade—whether \langle s,x\rangle\leq p and \langle b,x\rangle\geq p . E.g., if the seller accepts its price, but the trade fails because the buyer refuses q , we know that s lies in the half-space \{\tilde{s}\mid\langle\tilde{s},x\rangle\geq p\} and b\in\{\tilde{b}\mid\langle\tilde{b},x\rangle\leq q\} . The learning algorithm can then maintain, for each agent, a “confidence region” defined by the intersections of these half-spaces, given the feedback thus far (see also Figure 1 .) Potentials and regret. A good algorithm for contextual bilateral trade must find the right balance between narrowing these confidence regions, and suffering as little regret as possible. To capture this, it is natural to define a notion of “potential” which quantifies such delicate trade-off. In particular, our starting point is the family of potential functions based on Steiner polynomials introduced by 25 . For the bilateral trade problem, we need to consider two potentials, one corresponding to the seller’s confidence region, and another to the buyer. Crucially, we cannot handle the two separately: (i) The prices must respect budget balance, so the choice of price p restricts the values that q can take, and (ii) both the gain-from-trade, and the profit depend on both agents accepting their price. E.g., a good price for the seller may still incur constant regret if the buyer rejects the trade. To strike the right balance, we consider projections of the confidence regions onto the current context: if the two projections are disjoint, we can consider the two agents separately; otherwise, we focus on the agents corresponding to larger projection (i.e., with greater uncertainty along the current context), and use the length of its projection as a proxy for the incurred regret. Ambiguity in one-bit feedback. Updating the confidence regions for the buyer and seller separately is only feasible if we have explicit feedback from both agents. In the one-bit setting, a “no-trade” outcome is ambiguous: the learner cannot discern whether the buyer’s price was too high or the seller’s price was too low (or both). Indeed, using this feedback directly gives us non-convex uncertainty regions, which are difficult to handle. To overcome this ambiguity, we give two different solutions, each characterized a different notion of budget balance. In the first set of results, we show how to “simulate” two-bit feedback by posting a “safe” price for at least one of the two agents; i.e., a price that will surely be accepted. To do this, the learner may post a price to the buyer which is below that for the seller, thereby violating budget balance; hence, we need to carefully bound the negative profit incurred. In the second set of results which handle this ambiguity without violating the budget balance, we update the confidence regions only when a trade successfully occurs, as this is the only situation where the agents’ hidden bits are unambiguous. However, this creates a new problem: discarding updates from no-trade rounds breaks the analysis used in two-bit algorithms (notably, the two-bit profit-maximizing algorithm typically relies on decreasing the potential doubly exponentially when no trade is observed). To resolve this, we introduce a novel randomized pricing strategy. We demonstrate that the algorithm incurs constant expected regret between periods of successful trade. This allows us to “charge” the regret accumulated during no-trade steps to the time steps where a trade occurs and the potential decreases. Because the prices inducing this potential decrease are randomized, they result in a slower reduction of potentials (as opposed to the deterministic ones allowed in the two-bit feedback), yielding a looser dependence on the dimension. 1.3 Related Work Our work is at the intersection of three main lines of research: online contextual pricing, the study of efficiency and profit maximization in bilateral trade, and its online learning version. Online Contextual Pricing. Our setting generalizes the (one-sided) contextual pricing problem introduced by 1 . A sequence of papers ( 10 ; 23 ; 25 ) introduced techniques from convex geometry to obtain increasingly better bounds for this problem; the state of the art is the O(d\log\log T) algorithm in 25 , which is essentially tight ( 20 ; 25 ) . This problem has also been studied under stochastic noise models ( 18 ; 19 ; 29 ; 32 ; 33 ) , adversarial noise models ( 21 ; 22 ) and different assumptions on the valuation ( 27 ) . (Bayesian) Bilateral Trade. In the Bayesian Bilateral Trade problem, the agents’ private valuations are drawn from some known distributions, and the goal is to design trading mechanisms that are robust to the strategic behavior of the agents. The most studied objective is efficiency maximization, measured in terms of the multiplicative gap between the social welfare or gain from trade achieved and the best possible attainable ( 11 ; 6 ; 15 ; 13 , e.g.,) . While social welfare and gain from trade are equivalent in a regret-minimization setting (social welfare is simply gain from trade plus seller’s valuation), obtaining a multiplicative approximation for the latter turned out to be far more challenging. The structure of the profit-maximizing mechanism was already well understood in the classical paper by 28 , and recently there has been a systematic study of the profit-efficiency trade-off attainable with truthful mechanisms ( 17 ) . Online Learning and Bilateral Trade. A long line of research has investigated bilateral trade from the online learning perspective. The main difference with our setting is that, in those settings, the valuations are generated by an adversary (either i.i.d. stochastic, \sigma -smooth, or adversarial), without a notion of “context”. The regret is then measured with respect to the best fixed price in hindsight (as opposed to the best dynamic pricing policy), and the rates achievable are typically polynomial in T . These differences effectively change the nature of the problem (and the techniques one may use): while in our problem we are trying to locate the (s,b) pair, in online learning the goal is more on “hedging” between all possible prices to be competitive with the one that performs better on adversarial or stochastic inputs. For gain-from-trade maximization, tight regret rates are known for various combinations of feedback models, data-generation assumptions, and versions of budget balance constraints ( 7 ; 8 ; 2 ; 4 ; 26 ) . We also mention works generalizing the study of bilateral trade to to settings with more than one seller and one buyer at each time step ( 3 ) , or to the convergence of natural pricing behaviors ( 12 ) . For profit maximization, a recent paper has investigated the online learnability of profit-maximizing mechanisms beyond fixed-price ( 14 ) . Independent and concurrent work. In an independent and concurrent work, 9 study another contextual model for bilateral trade, where the functions mapping contexts to valuations are Lipschitz. While their model is more general than ours, none of our results is subsumed by theirs: they prove regret bounds which exhibit polynomial dependence in the time horizon T , which are tight for general Lipschitz functions, but not for the linear case we study. Given the nature of their rates, they focus on the case where the time horizon is way larger than the dimension d of the problem, i.e. T\gg 2^{d} . Finally, they only investigate gain-from-trade maximization, and not profit. 2 Model and Preliminaries In contextual bilateral trade, a learner repeatedly interacts with a sequence of seller-buyer pairs with the goal of maximizing either the economic efficiency, measured in terms of the gain from trade, or its own profit. The learning protocol is as follows: At each time t=1,\dots,T , the learner observes a context x_{t} in the unit ball \mathbb{B}=\{w\in\mathbb{R}^{d}\mid\|w\|_{2}\leq 1\} and posts two prices, p_{t} to the seller and q_{t} to the buyer. The trade happens if and only if both agents accept their prices, i.e., if p_{t} is at least the seller’s valuation s_{t} , and q_{t} is at most the buyer’s valuation b_{t} . The learner then observes feedback that depends on the posted prices and the agents’ valuations. We assume that s_{t} and b_{t} follow a linear structure 2 2 2 Throughout the paper, we present our results in terms of linear functions, but the model generalizes to any parameterized function of the type f(x)=\langle w,\phi(x)\rangle for an arbitrary transformation of the context vectors. For example, polynomials of degree k can be written as linear functions of \phi(x)=(\prod_{i}x_{i}^{s_{i}})_{s\in\mathbb{Z}_{+}^{d};\|s\|_{1}\leq k} . Thus, our bounds extend to polynomials of degree k , replacing d with O(d^{k}) . , namely that there exist two vectors s,b\in\mathbb{B} fixed but unknown to the learner such that s_{t}=\langle s,x_{t}\rangle , and b_{t}=\langle b,x_{t}\rangle . We study two feedback models: (i) two bits, where the learner observes (\mathbbm{1}\left\{s_{t}\leq p_{t}\right\},\mathbbm{1}\left\{q_{t}\leq b_{t}\right\}) , and (ii) one bit, where it only gets \mathbbm{1}\left\{s_{t}\leq p_{t}\right\}\cdot\mathbbm{1}\left\{q_{t}\leq b_{t}\right\} . In the former model, the learner has access to the relative position of both agents’ valuations and their posted prices, while in the latter, it only observes whether the trade happened. We consider the gain from trade and profit objectives for the learner, as introduced in Section 1 . At time t , we have (in explicit form): \displaystyle\textup{{GFT}}_{t}(p_{t},q_{t}) \displaystyle=\langle b-s,x_{t}\rangle\cdot\mathbbm{1}\left\{\langle s,x_{t}\rangle\leq p_{t}\right\}\cdot\mathbbm{1}\left\{q_{t}\leq\langle b,x_{t}\rangle\right\} \displaystyle\textup{{Profit}}_{t}(p_{t},q_{t}) \displaystyle=(q_{t}-p_{t})\cdot\mathbbm{1}\left\{\langle s,x_{t}\rangle\leq p_{t}\right\}\cdot\mathbbm{1}\left\{q_{t}\leq\langle b,x_{t}\rangle\right\}. Observation 2.1 . Given the structure of the agents’ valuations and the definitions of gain from trade and profit, we can assume without loss of generality that the contexts x_{t} have unitary norm. We can also consider other norms beyond the \ell_{2} one, for instance, we may also assume x_{t},s, and b bounded according to other norms (e.g., \|x_{t}\|_{\infty}\leq 1 and \|s\|_{1},\|b\|_{1}\leq 1 ), and the results do not change significantly, as long as profit and gain from trade remain bounded. We measure the performance of learning algorithms in terms of their regret with respect to the optimal pricing policy in hindsight. Given a possibly randomized efficiency-maximizing algorithm \mathcal{A} , and an instance \mathcal{I} of the problem, we define the regret of \mathcal{A} against \mathcal{I} : R_{T}(\mathcal{A},\mathcal{I})=\sum_{t=1}^{T}(b_{t}-s_{t})_{+}-\sum_{t=1}^{T}\textup{{GFT}}_{t}(p_{t},q_{t}), where the algorithm posts prices p_{t} and q_{t} , and the instance is characterized by the fixed vectors (s,b) , and an arbitrary sequence of contexts. The regret for profit-maximizing algorithms is analogous, with \textup{{Profit}}_{t} instead of \textup{{GFT}}_{t} . We want a learning algorithm with small worst-case regret: R_{T}(\mathcal{A})=\sup_{\mathcal{I}}\mathbb{E}\left[R_{T}(\mathcal{A},\mathcal{I})\right] , where the expectation is with respect to the randomness of the algorithm; note, we consider an oblivious adversary, which selects \mathcal{I} a priori. \textup{{GFT}}_{t} and \textup{{Profit}}_{t} map to [-2,2] , so the typical goal is to obtain regret that is sublinear in the time horizon T , which implies that the performance of the learning algorithm converges on average to the benchmark. Budget Balance. We consider two notions of budget balance: a per-step notion, where p_{t}\leq q_{t} for every t , and a weaker one, where we require that the overall negative profit is small. In our results (see Theorems 4.4 and 5.5 ) we enforce that \sum_{t=1}^{T}\max\{0,-\textup{{Profit}}_{t}(p_{t},q_{t})\}\in O(d\log d). We note that the latter requirement is aligned with the notion of “budget violation” as in 26 , while it is orthogonal to the global budget balance condition ( 4 ; 16 ) , where it is required that \sum_{t=1}^{T}\textup{{Profit}}_{t}(p_{t},q_{t})\geq 0 . We remark that per-step budget balance is strictly stronger than all other notions. Steiner Potentials. A crucial ingredient in our learning algorithms is provided by the Steiner Potentials ( 25 ) , inspired to the notion of Steiner Polynomials from convex geometry. Given a generic convex set K , the Steiner polynomial at scale z\in\mathbb{R}_{+} is defined as the volume of the set K+z\mathbb{B} , where the sum is to be intended according to Minkowski: K+z\mathbb{B}=\{y+zw\mid y\in K,w\in\mathbb{B}\} . Confidence Regions. All our algorithms maintain two confidence regions: S_{t} for the seller and B_{t} for the buyer, and update them according to the feedback received. These regions are initialized to \mathbb{B} , and are progressively updated according to hyperplanes orthogonal to the contexts. Formally, if at time t the seller receives price p_{t} and the algorithm observes \mathbbm{1}\left\{s_{t}\leq p_{t}\right\} , then S_{t+1} is: S_{t+1}=\begin{cases}\{v\in S_{t}|\langle v,x_{t}\rangle\geq p_{t}\}&\text{if the seller refuses $p_{t}$}\\ \{v\in S_{t}|\langle v,x_{t}\rangle\leq p_{t}\}&\text{if the seller accepts $p_{t}$}\end{cases} x_{t} S_{t} s \underline{s}_{t} \bar{s}_{t} s_{t} \proj(S_{t},x_{t}) B_{t} b \underline{b}_{t} \bar{b}_{t} b_{t} \proj(B_{t},x_{t}) Figure 1 : Illustration of seller and buyer conference regions and projections. The buyer set B_{t} is updated similarly, but with flipped signs. All our algorithms only update the confidence regions when there is no ambiguity on \mathbbm{1}\left\{s_{t}\leq p_{t}\right\} and \mathbbm{1}\left\{q_{t}\leq b_{t}\right\} . By construction, the confidence regions are convex and compact, therefore the sets \proj(S_{t},x_{t})=\{\langle v,x_{t}\rangle\mid v\in S_{t}\} and \proj(B_{t},x_{t})=\{\langle v,x_{t}\rangle\mid v\in B_{t}\} 3 3 3 The intervals \proj(S_{t},x_{t}) and \proj(B_{t},x_{t}) are indeed the projections of S_{t} and B_{t} along the direction of x_{t} . are closed and bounded intervals. Formally, let \underline{s}_{t}=\min\{\langle v,x_{t}\rangle|v\in S_{t}\},\overline{s}_{t}=\max\{\langle v,x_{t}\rangle|v\in S_{t}\} (and analogously for the buyer), then \proj(S_{t},x_{t})=[\underline{s}_{t},\overline{s}_{t}] , and \proj(B_{t},x_{t})=[\underline{b}_{t},\overline{b}_{t}] whose length we call width: The width of a convex set K along direction x is \width(K,x)=\max_{v_{1}\in K}\langle v_{1},x\rangle-\min_{v_{2}\in K}\langle v_{2},x\rangle. We refer to Figure 1 for visualization. 3 Context-free Bilateral Trade We start by presenting the (simpler) context-free setting (where each s_{t}=s and b_{t}=b for some fixed but unknown values s,b\in[0,1] with s\leq b ), in the one-bit feedback. While these algorithms don’t require all the geometric machinery necessary in higher dimensions, they illustrate some of the difficulties that arise in bilateral trade that didn’t exist one-sided pricing, and allow us to explain some building blocks used in subsequent algorithms. We first give an efficiency-maximizing algorithm, and then extend it to a profit-maximizing algorithm. 3.1 Efficiency maximization For gain-from-trade maximization, we describe how to locate a price p such that s\leq p\leq b , while suffering at most O(1) regret. The main idea here is clean: the algorithm posts a fixed “dyadic” schedule of prices \nicefrac{{1}}{{2}},\nicefrac{{1}}{{4}},\nicefrac{{3}}{{4}},\nicefrac{{1}}{{8}},\nicefrac{{3}}{{8}},\nicefrac{{5}}{{8}},\nicefrac{{7}}{{8}},\ldots , until a trade is observed. Formally, if t\in[2^{i},2^{i+1}) and the learner has not observed a trade so far, it posts p_{t}=\nicefrac{{(1+2(t-2^{i}))}}{{2^{i+1}}} . Once a “good” p is found, the algorithm keeps posting it indefinitely, and suffers no additional regret. The main observation is that each price rejection shows that (s,b) does not lie in some rectangle (indicated by the shaded regions in Figure 2 )—e.g., if price \nicefrac{{1}}{{2}} is rejected, then (s,b)\notin[0,\nicefrac{{1}}{{2}}]\times[\nicefrac{{1}}{{2}},1] . Crucially, rejections also provide information of the length of [s,b] . If \nicefrac{{1}}{{2}} is rejected, then b-s\leq\nicefrac{{1}}{{2}} ; if both \nicefrac{{1}}{{4}},\nicefrac{{3}}{{4}} are also rejected, we know that b-s\leq\nicefrac{{1}}{{4}} , etc. In general, if the first 2^{k}-1 prices are rejected, we conclude that b-s\leq\nicefrac{{1}}{{2^{k}}} , so that the total regret up to that point is (2^{k}-1)\cdot(b-s)\in O(1) . Random Prices. There is an intriguing alternate way of simulating the dyadic search algorithm via randomization: post random prices drawn uniformly and independently in [0,1] until a trade is observed, then play that price for the rest of the time horizon. The number of price rejections is a geometric random variable with parameter {(b-s)} , so that the expected number of rejections is \nicefrac{{1}}{{(b-s)}} , for an overall expected regret of 1 . In our contextual algorithms, we use both a “dyadic-like” structured approach, as well as the randomized one. \nicefrac{{1}}{{2}} \nicefrac{{1}}{{4}} \nicefrac{{3}}{{4}} \nicefrac{{1}}{{8}} \nicefrac{{3}}{{8}} \nicefrac{{5}}{{8}} \nicefrac{{7}}{{8}} Figure 2 : Visualization of the context-free dyadic search. x -axis corresponds to seller, y -axis to buyer. 3.2 Profit maximization For profit-maximization, we give an algorithm that suffers O(\log\log T) regret. In this case, staying with the first accepted price is not enough—we also want the prices (p_{t},q_{t}) to quickly approach (s,b) . The algorithm runs in two steps. First, it performs the dyadic search used for efficiency maximization, suffering at most O(1) regret. Once it observes a trade for some price p , then we have identified a “nice” square Q=[p-\varepsilon,p]\times[p,p+\varepsilon] with (s,b)\in Q —specifically, if p_{t}=\nicefrac{{(1+2(t-2^{i}))}}{{2^{i+1}}} is accepted then (s,b)\in Q=[p-2^{-i-1},p]\times[p,p+2^{-i-1}] . At this point, the algorithm moves to its second step, and recursively zooms to explore the square Q and locate (s,b) . This zooming is recursively performed via a two-dimensional version of the quadratic search algorithm, inspired by 20 . Given a generic square Q^{i} of side \varepsilon_{i} , whose bottom-right corner is (s^{i},b^{i}) , the algorithm casts a uniform \varepsilon_{i+1}=\varepsilon_{i}^{2} grid inside it and starts offering prices s^{i} , s^{i}-\varepsilon_{i+1},s^{i}-2\varepsilon_{i+1},\dots to the seller, while keeping b^{i} to the buyer. As soon as the seller refuses, we can identify a vertical strip of width \varepsilon_{i+1} that contains (s,b) (see Figure 3(a) ). We can perform the same operation for the buyer, while keeping fixed the seller price to s^{i} , identifying now a horizontal strip of height \varepsilon_{i+1} . Now (s,b) belongs to the intersection of these two stripes, i.e., a square of side \varepsilon_{i+1} , into which we recuse (see Figure 3(b) ). The recursion can stop as soon as the side of the square Q^{i} drops below \nicefrac{{1}}{{T}} (as this is enough to obtain the target profit, with a constant overall error), i.e., after O(\log\log T) phases. For the regret analysis, observe that the algorithm issues O(\nicefrac{{1}}{{\varepsilon_{i}}}) prices in each phase. When the trade happens, the regret suffered is O(\varepsilon_{i}) since the side of Q^{i} (and thus the error in estimating the target profit) is of that order. In the two steps where the trade does not happen, the regret is constant. Overall, the regret in the generic phase i is constant. Since there are at most O(\log\log T) such phases, this implies that the overall regret is O(\log\log T) . Q^{i} \varepsilon_{i+1} \varepsilon_{i} (s^{i},b^{i}) (a) Seller’s price discovery in phase i Q^{i} \varepsilon_{i+1} \varepsilon_{i} Q^{i+1} (s^{i},b^{i}) (b) Buyer’s price discovery in phase i Figure 3 : Illustration of the quadratic search step: In phase i , we operate within a square Q^{i} of side \varepsilon_{i} . (a) We fix the buyer’s price to b^{i} , then test decreasing seller prices starting from s^{i} . The vertical dashed line indicates the first refused seller price. (b) We then fix the seller’s price to s^{i} , then test increasing buyer prices starting from b^{i} . The horizontal dashed line indicates the first refused buyer’s price. These two tests identify a new square Q^{i+1} of side \varepsilon_{i+1} , where the algorithm is called recursively. 4 The Contextual Case: Efficiency Maximization We move on to the contextual case, and present the three algorithms for efficiency maximization; recall that the efficiency is measured in terms of the cumulative gain from trade. In Section 4.1 , we present the algorithm for two-bit feedback and prove its optimality, then in Section 4.2 we illustrate how to adapt it to one-bit feedback with a minimal budget-balance violation. Finally, Section 4.3 is devoted to presenting the randomized one-bit algorithm that enforces per-round budget balance. 4.1 Efficiency Maximization with Two-Bit Feedback The algorithm 4 4 4 We refer to Algorithm 1 in Appendix A for the pseudocode. for efficiency maximization with two-bit feedback maintains the two confidence regions S_{t} and B_{t} and uses an auxiliary family of potentials \vol(S_{t}+z_{i}\mathbb{B}) and \vol(B_{t}+z_{i}\mathbb{B}) , for z_{i}=\nicefrac{{2^{-i}}}{{(8d)}} and integers i . At each time step, the algorithm decides what to do according to the widths ( \width(S_{t},x_{t}) and \width(B_{t},x_{t}) ) of the confidence regions along x_{t} . It considers three cases: (i) if the intervals \proj(S_{t},x_{t}) and \proj(B_{t},x_{t}) are disjoint, then it posts the seller safe price p_{t}=\overline{s}_{t} to both agents (see Figure 4(a) ) (ii) if \width(S_{t},x_{t})\geq\width(B_{t},x_{t}) , then it posts to both agents the price p_{t} which solves \vol(\{v\in S_{t}+z_{i_{t}}\mathbb{B}\mid\langle v,x_{t}\rangle\leq p_{t}\})=\tfrac{1}{2}\vol(S_{t}+z_{i_{t}}\mathbb{B}), (1) where i_{t} is the largest index such that \width(x_{t},S_{t})\leq 2^{-i} (see Figure 4(b) ); (iii) otherwise, it posts to both agents the price p_{t} which solves \vol(\{v\in B_{t}+z_{i_{t}}\mathbb{B}\mid\langle v,x_{t}\rangle\geq p_{t}\})=\tfrac{1}{2}\vol(B_{t}+z_{i_{t}}\mathbb{B}), (2) where i_{t} is the largest index such that \width(x_{t},B_{t})\leq 2^{-i} . The prices defined in Equations 1 and 2 are called balanced, as they reduce the corresponding potential by a constant factor, regardless of the feedback . If at time t the algorithm posts a balanced price, i_{t} defined above is called the index at time step t . Before proving the regret guarantees of our algorithm, we state a lemma formalizing the decrease in potential due to balanced prices. It is an adaptation of Lemma 2.1 in 25 , and is re-proved for completeness in Appendix C . x_{t} S_{t} B_{t} \proj(S_{t},x_{t}) \proj(B_{t},x_{t}) p_{t} (a) Well Separated Regions x_{t} S_{t} B_{t} \proj(S_{t},x_{t}) \proj(B_{t},x_{t}) p_{t} (b) Seller Dominating - Two Bits x_{t} S_{t} B_{t} \proj(S_{t},x_{t}) \proj(B_{t},x_{t}) p_{t} q_{t} (c) Seller Dominating - One Bit Figure 4 : Visualization of the efficiency maximization algorithms. Lemma 4.1 (Balanced Prices) . If the algorithm posts a balanced price for the seller, then \vol(S_{t+1}+z_{i_{t}}\mathbb{B})\leq\tfrac{3}{4}\vol(S_{t}+z_{i_{t}}\mathbb{B}). If instead it posts a balanced price for the buyer, then \vol(B_{t+1}+z_{i_{t}}\mathbb{B})\leq\tfrac{3}{4}\vol(B_{t}+z_{i_{t}}\mathbb{B}). Theorem 4.2 . Consider the contextual bilateral trade problem in the two-bit feedback model. There exists an efficiency-maximizing algorithm that achieves regret O(d\log d) and enforces per-round budget balance. Proof. The algorithm always posts the same price to both agents, so it naturally respects per-round budget balance. Moreover, it never incurs a negative gain from trade as a trade may occur only if s_{t}\leq p_{t}\leq b_{t} (and thus b_{t}\geq s_{t} ). We can then discard from the analysis all time steps in which s_{t}>b_{t} , as they do not induce positive gain from trade for the algorithm or the benchmark. Consider now the “well-separated” time steps, where \proj(S_{t},x_{t})\cap\proj(B_{t},x_{t})=\emptyset , they always result in a trade as both agents accept and the algorithm suffers zero regret: s_{t}=\langle x_{t},s\rangle\leq\overline{s}_{t}=p_{t}<\underline{b}_{t}\leq\langle b,x_{t}\rangle=b_{t}. We are left with analyzing the regret incurred by the algorithm in the seller/buyer dominating cases. The crucial observation is that every time we post a balanced price corresponding to some index i_{t} , either \vol(S_{t}+z_{i_{t}}\mathbb{B}) or \vol(B_{t}+z_{i_{t}}\mathbb{B}) decreases by a constant factor ( Lemma 4.1 ). Both confidence regions are never empty, so that all potentials are always at least \vol(z_{i}\mathbb{B})=z_{i}^{d}\vol(\mathbb{B}) , while they are at most \vol((z_{i}+1)\mathbb{B})\leq\vol(3\mathbb{B})=3^{d}\vol(\mathbb{B}) by definition. Denoting by n^{S}_{i} the number of times that the index i is selected in a seller-dominating balanced case, we have the following inequality: \left(\tfrac{3}{4}\right)^{n^{S}_{i}}3^{d}\vol(\mathbb{B})\geq z_{i}^{d}\vol(\mathbb{B})\quad\implies\quad n_{i}^{S}\leq\frac{d\log\nicefrac{{3}}{{z_{i}}}}{\log\nicefrac{{4}}{{3}}}\leq 3d\log\nicefrac{{3}}{{z_{i}}}. The same bound holds for the number of times that index i is selected in a buyer-dominating balanced case. All in all, the algorithm does not pick any index i more than 6d\log(\nicefrac 3{z_{i}}) times. Consider now the regret suffered in a generic step when index i is chosen, either because of the buyer or of the seller. Since the two intervals have a non-empty intersection, and the longest one has length at most 2^{-i} , we can conclude that the gain from trade of the benchmark is at most 2\cdot 2^{-i} , which provides an upper bound on the regret suffered. Combining these ingredients, we can conclude that the overall regret is at most \sum_{i=-1}^{\infty}12\cdot 2^{-i}d\log(\nicefrac 3{z_i})\leq 12d\sum_{i=-1}^{\infty}\frac{1}{2^{i}}(\log(24d)+i\log(2))\in O(d\log d), (3) where the first inequality follows from the definition of z_{i} as \nicefrac{{2^{-i}}}{{(8d)}} . ∎ We complement this positive result with a lower bound, showing that the above result is essentially tight, up to a \log d factor. The lower bound construction is based on the simple observation that any learning algorithm cannot avoid suffering constant regret along one of the d directions, and its proof is deferred to Appendix C . Proposition 4.3 . Consider the contextual bilateral trade problem in the two-bit feedback model. Any efficiency-maximizing algorithm that enforces per-round budget balance suffers regret \Omega(d) . 4.2 Efficiency Maximization with One-Bit Feedback With a simple tweak, we can apply the previous algorithm (for efficiency maximization with two-bit feedback) to the one-bit feedback setting: whenever there may be ambiguity in the feedback observed by the learner, we post a safe price to one of the two agents, to disambiguate the feedback. In the well-separated case, there is no ambiguity, as both agents always accept the posted price (or \underline{s}_{t}\geq\overline{b}_{t} and the trade clearly cannot happen, in which case we do not update anything). For the other two cases, we post a safe price to the dominated agent: if the width of S_{t} is larger than that of B_{t} , then we post the seller-balanced price to the seller, and a safe price to the buyer (i.e., the smallest value \underline{b}_{t} in \proj(B_{t},x_{t}) see Figure 4(c) ), similarly, if the buyer’s width dominates the seller’s, then the algorithm post the buyer-balanced price to the buyer, and a safe price to the seller (i.e., the largest value \overline{s}_{t} in \proj(S_{t},x_{t}) ). This simple modification is enough to obtain the following result. Theorem 4.4 . Consider the contextual bilateral trade problem in the one-bit feedback model. There exists an efficiency-maximizing algorithm that achieves regret O(d\log d) and whose negative profit is at most O(d\log d) . Proof. First, note that the algorithm is well-defined, as it always posts a safe price to one of the two agents so that one-bit feedback is enough to update both confidence regions correctly. Moreover, the potential argument is not affected, as it depends on the balanced prices the algorithm still posts. This means that the bound proved in Theorem 4.2 on the number of times that a given index i is chosen holds, and this is at most O(d\log(\nicefrac 1{z_i})) . We want that (i) the gain from trade of the algorithm does not deteriorate too much and (ii) the overall negative profit is at most O(d\log d). We start considering the gain from trade. The only difference with the analysis of the two-bit case lies in the fact that the algorithm now may incur negative gain from trade when posting prices that are not budget balanced. However, such negative regret is at most of order 2^{-i} (for the index i in that step) because both prices lie in the interval with the largest length. All in all, the extra-regret incurred by the one-bit algorithm is bounded as in Equation 3 . Similarly, the algorithm may suffer negative profit only when it posts two non-budget-balanced prices. This happens only when \proj(S_{t},x_{t}) and \proj(B_{t},x_{t}) have a non-empty intersection, with the two prices being at most 2^{-i} far apart, where i is the index selected in the given time step. The O(d\log d) bound on the negative profit follows by the same analysis as in Equation 3 . ∎ 4.3 Efficiency Maximization with One-Bit Feedback and Per-Round Budget Balance We move to efficiency-maximization under one-bit feedback and per-round budget balance. Our algorithm posts the same price p_{t} to both agents and updates confidence regions S_{t} and B_{t} , only when there is no ambiguity in the (one-bit) feedback. At each time step t , the algorithm computes the intervals \proj(S_{t},x_{t}) and \proj(B_{t},x_{t}) and considers the following three cases: • Well-separated case: if the two intervals are disjoint, then it posts a “safe” price for the seller, i.e., \overline{s}_{t} , the largest value in \proj(S_{t},x_{t}) ; • Weak overlap case: let p_{t} be the middle-point of the larger interval, if it is accepted for sure by the other agent, then the algorithm posts it, middle price ; • Strong overlap case: when neither of the two previous cases apply, the algorithm posts a price uniformly at random in \proj(S_{t},x_{t})\cup\proj(B_{t},x_{t}) , uniform price . A pseudocode description of the algorithm is available in Algorithm 2 , in Appendix A . Note that, unlike the other algorithms for efficiency maximization, Algorithm 2 is defined without explicitly relying on Steiner Potentials; nonetheless, they remain a crucial tool in the analysis. In the rest of this section, we argue that this one-bit algorithm suffers a regret that is independent of the time horizon. For this purpose, we present a geometric result, Lemma 4.5 , whose proof is deferred to Appendix C . Lemma 4.5 . Consider any convex set K\subseteq\mathbb{R}^{d} , direction x\in\mathbb{B} , and hyperplane h orthogonal to x . Let H be any half-space induced by h , such that \proj(x,H) contains an \alpha\in[0,1] fraction of \proj(x,K) . For any z\leq\alpha\width(K,x) , we have the following inequality: \vol((K\setminus H)+z\mathbb{B})\leq\left(1-\left(\frac{\alpha}{1+2\alpha}\right)^{d}\right)\cdot\vol(K+z\mathbb{B}). We now present two direct applications of Lemma 4.5 in Lemma 4.6 and Lemma 4.7 . Lemma 4.6 (Weak overlap case) . In the weak overlap case, if the algorithm posts the middle point of the seller, then \vol(S_{t+1}+z\mathbb{B})\leq(1-4^{-d})\vol(S_{t}+z\mathbb{B}),\quad\forall z\text{ such that }z\leq\nicefrac{{1}}{{2}}\width(S_{t},x_{t}). If the algorithm posts the middle point of the buyer, then: \vol(B_{t+1}+z\mathbb{B})\leq(1-4^{-d})\vol(B_{t}+z\mathbb{B}),\quad\forall z\text{ such that }z\leq\nicefrac{{1}}{{2}}\width(B_{t},x_{t}). Proof. Without loss of generality, we assume that the seller has the larger width, so that the algorithm posts the middle point of \proj(S_{t},x_{t}) as price, and that such price is smaller than \underline{b}_{t} . By design, the buyer is sure to accept the middle price of the seller, thus the feedback received by the algorithm allows to reconstruct whether the seller accepts or not. We can then apply Lemma 4.5 with \alpha=\nicefrac{{1}}{{2}} to conclude the proof. ∎ Lemma 4.7 (Strong overlap case) . In the strong overlap case, if both agents accept price p_{t} , then at least one of the following two inequalities is verified: \begin{cases}\vol(S_{t+1}+z\mathbb{B})\leq(1-6^{-d})\vol(S_{t}+z\mathbb{B}),\quad&\forall z\text{ such that }z\leq\nicefrac{{1}}{{4}}\width(S_{t},x_{t})\\ \vol(B_{t+1}+z\mathbb{B})\leq(1-6^{-d})\vol(B_{t}+z\mathbb{B}),\quad&\forall z\text{ such that }z\leq\nicefrac{{1}}{{4}}\width(B_{t},x_{t})\end{cases}. Proof. Assume, towards contradiction, that the statement is not true, then there exists a price p_{t} that (i) results in a trade, (ii) belongs to the leftmost quarter of the [\underline{b}_{t},\overline{b}_{t}] segment and (iii) belongs to the rightmost quarter of the [\underline{s}_{t},\overline{s}_{t}] segment. Note, the properties (ii) and (iii) are required, otherwise we could apply Lemma 4.5 with \alpha=\nicefrac{{1}}{{4}} . Consider the case that the seller’s width is larger than the buyer’s one, then the existence of p satisfying (i) and (iii) implies that the middle point of [\underline{s}_{t},\overline{s}_{t}] is smaller than \underline{b}_{t} . This is because \nicefrac{{(\overline{s}_{t}-\underline{s}_{t})}}{{2}}=\overline{s}_{t}-\nicefrac{{(\overline{s}_{t}+\underline{s}_{t})}}{{2}}=(\overline{s}_{t}-p)+(p-\underline{b}_{t})+(\underline{b}_{t}-\nicefrac{{(\overline{s}_{t}+\underline{s}_{t})}}{{2}}) gives (\underline{b}_{t}-\nicefrac{{(\overline{s}_{t}+\underline{s}_{t})}}{{2}})\geq 0 using (\overline{s}_{t}-p)\leq\nicefrac{{(\overline{s}_{t}-\underline{s}_{t})}}{{4}} and (p-\underline{b}_{t})\leq\nicefrac{{(\overline{s}_{t}-\underline{s}_{t})}}{{4}} . But this is a contradiction, because we would then be in the weak overlap case. The case where the buyer’s width dominates the seller’s is analogous. ∎ We are now ready to prove the main theorem of this section. Theorem 4.8 . Consider the contextual bilateral trade problem in the one-bit feedback model. There exists an efficiency-maximizing algorithm that achieves regret O(d6^{d}) and enforces per-round budget balance. Proof. It is clear that Algorithm 2 enforces per-round budget balance, as it always posts the same price to the buyer and to the seller, and is well defined, as it only updates the confidence regions when there is no ambiguity. We then tackle bounding the regret rate. Fix any problem instance \mathcal{I} , we introduce two auxiliary functions: a potential P(t) , which is a function of the state of the algorithm at time t and defined formally later, and the cumulative regret R(t) suffered against \mathcal{I} suffered by the algorithm up to time t , excluded. We omit the dependence on the instance \mathcal{I} , but it is clear that our goal is to bound \mathbb{E}\left[R(T+1)\right] (with a slight abuse of notation). The main ingredient in our analysis is the following inequality, which we shall show at all times t\geq 1 : \mathbb{E}_{t}[R(t+1)+P(t+1)]\leq R(t)+P(t), (4) where \mathbb{E}_{t}[\cdot] is the expectation conditioned on values taken by p_{1},\dots,p_{t-1} (so the randomness in the left-hand side of Equation 4 is on p_{t} ). A direct induction on Equation 4 then yields the regret bound at all times t , \mathbb{E}\left[R(t)\right]\leq P(0). In formal terms, Equation ( 4 ) says that P(t)+R(t) is a super-martingale relative to the filtration (\mathcal{F}_{t})_{t\in[T+1]} , where \mathcal{F}_{t} is the sigma-algebra used used to generate (p_{1},\dots,p_{t-1} ). In this terminology, \mathbb{E}_{t}[R(t+1)+P(t+1)] , also denoted \mathbb{E}[R(t+1)+P(t+1)|\mathcal{F}_{t}] , is an \mathcal{F}_{t} -measurable random variable, just like R(t)+P(t) . Similarly, we denote with \mathbb{P}_{t} the probability conditioned on \mathcal{F}_{t} . Thus, the inequality in Equation ( 4 ) is an inequality between \mathcal{F}_{t} -measurable random variables. We introduce the potential P that we use in this proof. Let z_{i}=2^{-i} , we have P(t)=64\cdot 6^{d}\sum_{i\geq 0}z_{i}\left[\log\left(\frac{\vol(B_{t}+z_{i}\mathbb{B})}{z_{i}^{d}\text{Vol}(\mathbb{B})}\right)+\log\left(\frac{\vol(S_{t}+z_{i}\mathbb{B})}{z_{i}^{d}\text{Vol}(\mathbb{B})}\right)\right]. (5) The non-negativity of such potential immediately follows from the fact that, at all times, B_{t}\neq\emptyset and S_{t}\neq\emptyset . Also, using that \forall i:\vol(\mathbb{B}+z_{i}\mathbb{B})\leq\vol(2\mathbb{B})=2^{d}\vol(\mathbb{B}) , we get, P(0)\leq 128\cdot 6^{d}\sum_{i\geq 0}z_{i}\log\left(\frac{2^{d}}{z_{i}^{d}}\right)\in O(d6^{d}), which corresponds to the desired regret guarantee. Thus, to complete the proof, it suffices to show that Equation ( 4 ) is true at all times for the potential introduced in Equation 5 . To do so, it is useful to notice that all the terms in the definition of P(t) are non-increasing, so that it suffices to show that the decrease of one of these terms outweighs the increase in the regret. Well-separated case. In the well-separated case, the algorithm suffers no regret, i.e., R(t+1)=R(t) . Equation ( 4 ) thus follows immediately from the monotonicity of P(t) . Weak overlap case. In the weak overlap case, notice that R(t+1)-R(t)\leq 2w , where w=\max\{\width(S_{t},x_{t}),\width(B_{t},x_{t})\} . Suppose, without loss of generality, that \width(S_{t},x_{t})\geq\width(B_{t},x_{t}) , so that p_{t} is the middle point of \proj(S_{t},x_{t}) and is always accepted by the buyer. In this case, denoting by i the smallest integer such that z_{i}\leq\nicefrac{{1}}{{2}}\width(S_{t},x_{t}) , and applying Lemma 4.6 , we have \vol(S_{t+1}+z_{i}\mathbb{B})\leq(1-4^{-d})\vol(S_{t}+z_{i}\mathbb{B}) . Therefore, \displaystyle P(t+1)-P(t) \displaystyle\leq 64\cdot 6^{d}z_{i}\log(1-4^{-d}) \displaystyle\leq-2w, where we used \forall x\in(0,1]:\log(1-x)\leq-x , and 4z_{i}\geq w , by definition of i . Strong overlap Case. In the strong overlap case, the increase in the regret satisfies R(t+1)-R(t)\leq\langle b-s,x_{t}\rangle^{+} , and the probability that the price selected uniformly at random in \proj(S_{t},x_{t})\cup\proj(B_{t},x_{t}) is accepted satisfies 5 5 5 With \mathbb{P}_{t} we denote the conditional probability with respect to the filtration \mathcal{F}_{t} . \mathbb{P}_{t}[p_{t}~\text{accepted}]\geq\frac{\langle b-s,x_{t}\rangle^{+}}{2w}. Thus, in order to prove Equation ( 4 ), in light of the observation that for the non-increasing potential, \mathbb{E}_{t}[P(t+1)-P(t)]\leq\mathbb{E}_{t}[P(t+1)-P(t)|p_{t}~\text{accepted}]\cdot\mathbb{P}_{t}[p_{t}~\text{accepted}], it suffices to show the following bound on the conditional expectation \mathbb{E}_{t}[P(t+1)-P(t)|p_{t}~\text{accepted}]\leq-2w. We will show the stronger claim that P(t+1)-P(t)\leq-2w in all cases where p_{t} is accepted. For this, we consider two sub-cases. Sub-case 1: \width(B_{t},x_{t}) and \width(S_{t},x_{t}) are within a factor 4 . Denote by i the smallest integer such that z_{i}\leq\nicefrac{{1}}{{16}}\cdot w so that z_{i}\leq\nicefrac{{1}}{{4}}\min\{\width(B_{t},x_{t}),\width(S_{t},x_{t})\} . By Lemma 4.7 , if the price is accepted, then at least one of the following two inequalities is verified: \begin{cases}\vol(S_{t+1}+z\mathbb{B})\leq(1-6^{-d})\vol(S_{t}+z\mathbb{B}),\quad&\forall z\text{ such that }z\leq\nicefrac{{1}}{{4}}\width(S_{t},x_{t})\\ \vol(B_{t+1}+z\mathbb{B})\leq(1-6^{-d})\vol(B_{t}+z\mathbb{B}),\quad&\forall z\text{ such that }z\leq\nicefrac{{1}}{{4}}\width(B_{t},x_{t})\end{cases} Therefore, the quantity Q(t) defined by Q(t)=64\cdot 6^{d}\cdot z_{i}\left(\log\left(\frac{\vol(B_{t}+z_{i}\mathbb{B})}{z_{i}^{d}\text{Vol}(\mathbb{B})}\right)+\log\left(\frac{\vol(S_{t}+z_{i}\mathbb{B})}{z_{i}^{d}\text{Vol}(\mathbb{B})}\right)\right), satisfies, Q(t+1)-Q(t)\leq 64\cdot 6^{d}\cdot z_{i}\log(1-6^{-d})\leq-2w, where we used \forall x\in(0,1]:\log(1-x)\leq-x , and 32\cdot z_{i}\geq w . Observing that P(t+1)-P(t)\leq Q(t+1)-Q(t) , we have completed the analysis of this sub-case. Sub-case 2: \width(B_{t},x_{t})\geq 4\width(S_{t},x_{t}) or \width(S_{t},x_{t})\geq 4\width(B_{t},x_{t}) . We assume without loss of generality that \width(B_{t},x_{t})\geq 4\width(S_{t},x_{t}) and we treat the other case analogously. Notice that an accepted price must belong to the last three-quarters of B_{t} , so that, taking i the smallest integer such that z_{i}\leq\nicefrac{{1}}{{4}}w , and applying Lemma 4.5 with \alpha=\nicefrac{{1}}{{4}} , we get, \vol(B_{t+1}+z_{i}\mathbb{B})\leq(1-6^{-d})\vol(B_{t}+z_{i}\mathbb{B}). Thus, if the price is accepted, the contribution of the above term to the decrease of the potential gives, P(t+1)-P(t)\leq 64\cdot 6^{d}\cdot z_{i}\log(1-6^{-d})\leq-2w, where we used \forall x\in(0,1]:\log(1-x)\leq-x , and 8\cdot z_{i}\geq w . ∎ 5 The Contextual Case: Profit Maximization In this section, we present our algorithms for profit maximization. We present our near-optimal results for two-bit feedback in Section 5.1 , and then adapt it to one-bit feedback in Section 5.2 . Finally, we give the one-bit algorithm with per-round budget balance in Section 5.3 . 5.1 Profit Maximization with Two-Bit Feedback We now build on the recursive zooming idea from Section 3.2 , combined with the efficiency-maximization from Section 4.1 , to get our profit maximization algorithm for two-bit feedback. We report here a high-level description, while the pseudocode is reported in Appendix B as Algorithm 3 . The algorithm maintains the confidence regions S_{t} and B_{t} and a family of Steiner Potentials for scales z_{i}=\tfrac{2^{-3\cdot 2^{i}}}{16d} . Every time a new context x_{t} arrives, it proceeds by cases, according to the widths of S_{t} and B_{t} . (i) If both widths are smaller than \nicefrac{{1}}{{T}} , then the error in estimating the actual valuations is sufficiently small, so the algorithm posts safe prices to both agents. (ii) If \width(S_{t},x_{t})\geq\width(B_{t},x_{t}) , then the algorithm posts a safe price for the buyer, and m^{S}_{t}+z_{i_{t}} to the seller, where i_{t} is the largest index such that the width of S_{t} is upper bounded by 2^{-2^{i_{t}}} and m^{S}_{t} solves \vol(\{v\in S_{t}+z_{i_{t}}\mathbb{B}\mid\langle v,x_{t}\rangle\geq m^{S}_{t}\})=2^{-2^{{i_{t}}-1}}\vol(S_{t}+z_{i_{t}}\mathbb{B}). (6) We are left with the last case (iii), where the width of the buyer dominates that of the seller, and it is larger than \nicefrac{{1}}{{T}} . There, the algorithm posts the safe price to the seller, and m^{B}_{t}-z_{i_{t}} to the buyer, where i_{t} is the largest index such that the width of B_{t} is upper bounded by 2^{-2^{i}} , and m^{B}_{t} solves the following equality: \vol(\{v\in B_{t}+z_{i_{t}}\mathbb{B}\mid\langle v,x_{t}\rangle\leq m^{B}_{t}\})=2^{-2^{{i_{t}}-1}}\vol(B_{t}+z_{i_{t}}\mathbb{B}). (7) We call the prices induced by solving Equations 6 and 7 as unbalanced prices. In all three cases, the price for the seller may be larger than that for the buyer. If this happens, the algorithm maintains per-round budget balance by actually posting to both agents the unbalanced price, or any price in case (i) when no unbalanced price is used. Unbalanced prices share the desirable property of drastically reducing the corresponding potential when rejected, while they reduce it by a smaller factor when they are accepted. We formalize this fact in the following two lemmata, adapted from 25 , and whose proofs are deferred to Appendix D . Lemma 5.1 . (Refusing Unbalanced Prices) If \width(x_{t},S_{t})\geq\nicefrac{{1}}{{T}} and the seller refuses m^{S}_{t}+z_{i_{t}} , then \vol(S_{t+1}+z_{i_{t}}\mathbb{B})\leq 2^{-2^{i_{t}-1}}\vol(S_{t}+z_{i_{t}}\mathbb{B}). Similarly, if \width(x_{t},B_{t})\geq\nicefrac{{1}}{{T}} and the buyer refuses price m^{B}_{t}-z_{i_{t}} , then \vol(B_{t+1}+z_{i_{t}}\mathbb{B})\leq 2^{-2^{i_{t}-1}}\vol(B_{t}+z_{i_{t}}\mathbb{B}). Lemma 5.2 . (Accepting Unbalanced Prices) If \width(x_{t},S_{t})\geq\nicefrac{{1}}{{T}} , and the seller accepts price m^{S}_{t}+z_{i_{t}} , then \vol(S_{t+1}+z_{i_{t}}\mathbb{B})\leq\left(1-\frac{1}{10\cdot 2^{2^{(i_{t}-1)}}}\right)\vol(S_{t}+z_{i_{t}}\mathbb{B}). Similarly, if \width(x_{t},B_{t})\geq\nicefrac{{1}}{{T}} , and the buyer accepts price m^{B}_{t}-z_{i_{t}} , then \vol(B_{t+1}+z_{i_{t}}\mathbb{B})\leq\left(1-\frac{1}{10\cdot 2^{2^{(i_{t}-1)}}}\right)\vol(B_{t}+z_{i_{t}}\mathbb{B}). We have all the ingredients to prove the regret guarantees of the two-bit algorithm. Theorem 5.3 . Consider the contextual bilateral trade problem in the two-bit feedback model. There exists a profit-maximizing algorithm that achieves regret O(d\log\log T+d\log d) and enforces per-round budget balance. Proof. Algorithm 3 respects per-round budget balance since it always posts a lower price to the seller than it does to the buyer. Moreover, we can ignore from the analysis all time steps in which s_{t}>b_{t} , as they do not influence the profit of the algorithm and the benchmark. Likewise, we can disregard all time steps such that \max\{\width(S_{t},x_{t}),\width(B_{t},x_{t})\}\leq\nicefrac{{1}}{{T}} since they contribute O(1) to the overall regret. We now analyze the regret incurred by the algorithm in the seller/buyer dominating cases. Consider the seller dominating case, as the buyer dominating case proceeds identically, but with signs flipped. We have two subcases: If m^{S}_{t}+z_{i_{t}}<\langle s,x_{t}\rangle , so that the seller refuses this price, the loss in profit is at most 1 , and, by Lemma 5.1 , \vol(S_{t+1}+z_{i_{t}}\mathbb{B})\leq 2^{-2^{i_{t}-1}}\vol(S_{t}+z_{i_{t}}\mathbb{B}). Then, identically to the proof of Theorem 4.2 , we know that z_{i}^{d}\vol(\mathbb{B})\leq\vol(S_{t}+z_{i}\mathbb{B})\leq 3^{d}\vol(\mathbb{B}) for all i , then the seller cannot refuse a price corresponding to index i more than n_{i}^{S,\textsf{ref}}\leq\frac{d\log\nicefrac{{3}}{{z_{i}}}}{2^{i-1}}=6d+\frac{d\log 48d}{2^{i-1}}. Conversely, if m^{S}_{t}+z_{i_{t}}\geq\langle s,x_{t}\rangle , so that the seller accepts this price, the loss in profit is much smaller than in the case of refusal, namely at most 2\cdot 2^{-2^{i_{t}}} . Also, by Lemma 5.2 , \vol(S_{t+1}+z_{i_{t}}\mathbb{B})\leq\left(1-\frac{1}{10\cdot 2^{2^{{(i_{t}-1)}}}}\right)\vol(S_{t}+z_{i_{t}}\mathbb{B}). Then, as above, the seller cannot accept a price corresponding to index i more than \displaystyle n_{i}^{S,\textsf{acc}} \displaystyle\leq\frac{d\log\nicefrac{{z_{i}}}{{3}}}{\log\left(1-\frac{1}{10\cdot 2^{2^{(i-1)}}}\right)} \displaystyle\leq 10d2^{2^{(i-1)}}\log(48d\cdot 2^{3 \cdot 2^{i}}) (as \log(1+r)\leq r for r>-1 ) \displaystyle\leq 10d2^{2^{(i-1)}}(\log(48d)+3\cdot 2^{i}). Finally, note that i_{t}\leq 2\log\log T , and hence, the accrued regret is at most \displaystyle\sum_{i=0}^{2\log\log T}\left(n_{i}^{S,\textsf{ref}}+n_{i}^{S,\textsf{acc}}\cdot 2^{-2^{i}}\right) \displaystyle\leq\sum_{i=0}^{2\log\log T}\left[6d+\frac{d\log 48d}{2^{i-1}}+10d2^{2^{{-(i-1)}}}(\log(48d)+3\cdot 2^{i})\right] \displaystyle\in O(d\log\log T+d\log d). (8) We can perform a similar analysis for the time steps where the buyer’s width dominates the seller’s, thus concluding the proof. ∎ The positive result for profit maximization with two-bit feedback is essentially tight, given the lower bound for one-sided pricing from 20 , which we can “amplify” using the d directions (Proof deferred to Appendix D ). Proposition 5.4 . Consider the contextual bilateral trade problem in the two-bit feedback model. Any profit-maximizing algorithm suffers regret \Omega(d\log\log\nicefrac{{T}}{{d}}) . 5.2 Profit Maximization with One-Bit Feedback We present how to modify the two-bit algorithm to work with only one bit of feedback. As in the efficiency maximization case, we only update the confidence regions when there is no ambiguity in the feedback, i.e., when one of the two agents is proposed a safe price. The tweak is fairly simple. When the two intervals \proj(S_{t},x_{t}) and \proj(B_{t},x_{t}) do not intersect, or have both widths smaller than \nicefrac{{1}}{{T}} , the one-bit algorithm behaves exactly as the two-bit one: At least one of the two agents receives a safe price in such a case, and therefore there is no ambiguity (or \underline{s}_{t}>\overline{b}_{t} , in which case the trade cannot happen and no confidence region is updated). If \proj(S_{t},x_{t}) and \proj(B_{t},x_{t}) intersect, and the width is large enough, then the two-bit algorithm posts an unbalanced price to the agent with the largest width, and a safe price to the other , to avoid ambiguity. Note that the two-bit feedback algorithm does something similar but caps the other agent’s price to prevent violating the per-round budget balance. As we formally argue in the following theorem, we can remove this cap without incurring more than O(d\log d) negative profit. Theorem 5.5 . Consider the contextual bilateral trade problem in the one-bit feedback model. There exists a profit-maximizing algorithm that achieves regret O(d\log\log T+d\log d) and whose negative profit is at most O(d\log d) . Proof. The analysis of the two-bit feedback carries exactly as it is, with the sole difference that we need to account for the negative profit incurred when posting non-budget-balanced prices. This happens only when the intersection of \proj(S_{t},x_{t}) and \proj(B_{t},x_{t}) is non-empty, for a negative profit of order O(2^{2^{-i}}) , where i is the index corresponding to the largest width. Therefore, we can upper bound the negative profit as in Equation 8 , with the only difference that when we upper bound the negative profit with 2^{2^{-i}} , for an overall bound of O(d\log d) . ∎ 5.3 Profit Maximization with One-Bit Feedback and Per-Round Budget Balance We finally consider contextual profit-maximization under one-bit feedback and per-round budget balance and study Algorithm 4 whose pseudocode is given in Appendix B . Like the one-bit efficiency-maximizing algorithm analyzed in Section 4.3 , Algorithm 4 only updates the confidence regions S_{t} and B_{t} when there is no ambiguity in the (one-bit) feedback. At each time step t , the algorithm computes the intervals \proj(S_{t},x_{t}) and \proj(B_{t},x_{t}) and considers the following three cases: • Small widths case: if the two intervals have width less than 1/T , then it posts a “safe” price for the seller, i.e., p_{t}\leftarrow\overline{s}_{t} , and a “nearly safe” price for the buyer, i.e., q_{t}\leftarrow\max\{\overline{s}_{t},\underline{b}_{t}\} ( Figure 5(a) ); • Weak overlap case: let p_{t} be the middle-point of the larger interval, if it is accepted for sure by the other agent, then the algorithm posts it, middle price ( Figure 5(b) ); • Strong overlap case: when neither of the two previous cases apply, the algorithm posts a price uniformly at random in [-1,1] , uniform price ( Figure 5(c) ). Informally, the small widths case replaces the well-separated case of the efficiency-maximizing algorithm. The idea is that, while separation of \proj(B_{t},x_{t}) and \proj(S_{t},x_{t}) suffices to get full efficiency at round t , it does not suffice to extract a good profit at round t . Instead, in the small widths case, we can choose p_{t} and q_{t} so that the regret in the profit does not exceed 2/T . The main result of this section is that Algorithm 4 achieves a regret of at most O(d6^{d}\log T) . In the proof of this result, we will use several lemmas and notations introduced in Section 4.3 , which we refer the reader to. x_{t} S_{t} B_{t} p_{t} q_{t} (a) Small widths case x_{t} S_{t} B_{t} p_{t} (b) Weak overlap (middle price) x_{t} S_{t} B_{t} p_{t} (c) Strong overlap (random price) Figure 5 : Visualization of the profit-maximizing algorithm with one-bit feedback and per-round budget balance. Theorem 5.6 . Consider the contextual bilateral trade problem in the one-bit feedback model. There exists a profit-maximizing algorithm that achieves regret O(d6^{d}\log T) and enforces per-round budget balance. Proof. Consider the following potential, in which z=\nicefrac{{1}}{{16T}} , P(t)=2\cdot 6^{d}\left[\log\left(\frac{\vol(B_{t}+z\mathbb{B})}{z^{d}\vol(\mathbb{B})}\right)+\log\left(\frac{\vol(S_{t}+z\mathbb{B})}{z^{d}\vol(\mathbb{B})}\right)\right]+2\frac{T-t}{T}. (9) The potential satisfies that \forall t:P(t)\geq 0 and as well as, P(0)\leq 6^{d}\cdot 4\cdot d\log(2/z)+2\in O(d6^{d}\log T), where we used \vol(B_{t}+z\mathbb{B})\leq 2^{d}\vol(\mathbb{B}) . As in the proof of Theorem 4.8 , we aim to show that the following equation is always satisfied, where R(t+1) denotes the regret of the algorithm after the t -th bid, and where \mathbb{E}_{t}[\cdot] is the expectation conditioned on values taken by p_{1},\dots,p_{t-1} , \mathbb{E}_{t}[R(t+1)+P(t+1)]\leq R(t)+P(t). (10) Equation ( 10 ) directly implies by induction \forall t:R(t)\leq P(0) and thus the desired result. We refer to the proof of Theorem 4.8 for more details on the formalism behind Equation ( 10 ), and we turn to showing that Equation ( 10 ) holds with the potential defined in ( 9 ). We do the following case-disjunction. Small widths case. If the width of both intervals \proj(S_{t},x_{t}) and \proj(B_{t},x_{t}) is less than \nicefrac{{1}}{{T}} , the algorithm posts a safe price for the seller p_{t}=\overline{s}_{t} , and posts price q_{t}=\max\{p_{t},\underline{b}_{t}\} for the buyer. We argue that in this case, the regret is at most 2/T . First, if \overline{s}_{t}\leq\underline{b}_{t} , then q_{t}=\underline{b}_{t} and the trade is accepted with a regret of (b_{t}-s_{t})^{+}-(\overline{s}_{t}-\underline{b}_{t})^{+}=(b_{t}-\underline{b}_{t})+(\overline{s}_{t}-s_{t})\leq\nicefrac{{2}}{{T}} . Second, if \overline{s}_{t}\geq\underline{b}_{t} and b_{t}\geq\overline{s}_{t} the trade is accepted because q_{t}=\overline{s}_{t} , but it generates zero profit since p_{t}=q_{t} . The regret is (b_{t}-s_{t})^{+}=b_{t}-s_{t}=(b_{t}-\overline{s}_{t})+(\overline{s}_{t}-s_{t})\leq(b_{t}-\underline{b}_{t})+(\overline{s}_{t}-s_{t})\leq\nicefrac{{2}}{{T}} . Third, if \overline{s}_{t}\geq\underline{b}_{t} and b_{t}\leq\overline{s}_{t} , the trade is rejected and the regret is (b_{t}-s_{t})^{+}\leq(\overline{s}_{t}-s_{t})^{+}\leq 1/T . Thus, the increase in the regret satisfies R(t+1)-R(t)\leq\nicefrac{{2}}{{T}} . The last term of the potential definition in ( 9 ) implies that P(t+1)-P(t)\leq-\nicefrac{{2}}{{T}} , which completes the proof of Equation ( 10 ). Weak overlap case. In the weak overlap case, assume, without loss of generality, that the width of the seller is larger, so that \frac{\overline{s}_{t}+\underline{s}_{t}}{2}\leq\underline{b}_{t} . We naively bound the increase in regret by R(t+1)-R(t)\leq 2 . Since we have that z\leq\width(S_{t})/2 , we apply Lemma 4.6 to obtain that \vol(S_{t+1}+z\mathbb{B})\leq(1-4^{-d})\vol(S_{t}+z\mathbb{B}). Therefore, taking the logarithm, we get P(t+1)-P(t)\leq 2\cdot 6^{d}\log(1-4^{-d})\leq-2, where we used \log(1-x)\leq-x , which implies ( 10 ). Strong overlap case. In the case of a strong overlap, we bound the increase of the regret by R(t+1)-R(t)\leq(b^{T}x_{t}-s^{T}x_{t})^{+} . We then note that the probability that the price selected uniformly at random in [-1,1] is accepted satisfies \mathbb{P}_{t}[p_{t}~\text{accepted}]\geq(b^{T}x_{t}-s^{T}x_{t})^{+}/2. Thus, to prove Equation ( 10 ), it suffices to show the following bound on the conditional expectation \mathbb{E}_{t}[P(t+1)-P(t)|p_{t}~\text{accepted}]\leq-2. We will show the stronger claim, that for any event in which the price is accepted, the bound P(t+1)-P(t)\leq-2 applies. For this, we consider two sub-cases. Sub-case 1: \width(B_{t},x_{t}) and \width(S_{t},x_{t}) are within a factor 4 . In this case, since at least one of the two quantities is greater than \nicefrac{{1}}{{T}} , we have that \nicefrac{{1}}{{16T}}=z\leq\nicefrac{{1}}{{4}}\min\{\width(B_{t},x_{t}),\width(S_{t},x_{t})\} . By Lemma 4.7 , when the price is accepted, at least one of the following two inequalities is verified: \begin{cases}\vol(S_{t+1}+z\mathbb{B})\leq(1-6^{-d})\vol(S_{t}+z\mathbb{B}),\quad&\forall z\text{ such that }z\leq\nicefrac{{1}}{{4}}\width(S_{t},x_{t})\\ \vol(B_{t+1}+z\mathbb{B})\leq(1-6^{-d})\vol(B_{t}+z\mathbb{B}),\quad&\forall z\text{ such that }z\leq\nicefrac{{1}}{{4}}\width(B_{t},x_{t})\end{cases} Therefore, the potential, which uses z=\nicefrac{{1}}{{16T}} , satisfies P(t+1)-P(t)\leq 2\cdot 6^{d}\cdot\log(1-6^{-d})\leq-2, where we used \forall x\in(0,1]:\log(1-x)\leq-x , completing the analysis of this sub-case. Sub-case 2: \width(B_{t},x_{t})\geq 4\width(S_{t},x_{t}) or \width(S_{t},x_{t})\geq 4\width(B_{t},x_{t}) . We assume without loss of generality that \width(B_{t},x_{t})\geq 4\width(S_{t},x_{t}) and we treat the other case analogously. Notice that, in this case, an accepted price must belong to the last three-quarters of B_{t} , and that z\leq\nicefrac{{1}}{{4}}\width(B_{t},x_{t}) so that, applying Lemma 4.5 with \alpha=\nicefrac{{1}}{{4}} , we get, \vol(B_{t+1}+z\mathbb{B})\leq(1-6^{-d})\vol(B_{t}+z\mathbb{B}). Thus, the decrease in the potential satisfies P(t+1)-P(t)\leq 2\cdot 6^{d}\log(1-6^{-d})\leq-2, where we used \forall x\in(0,1]:\log(1-x)\leq-x . ∎ Appendix Appendix A Pseudocodes for efficiency maximization Algorithm 1 Efficiency Maximization with Two-Bit Feedback 1: S_{1},B_{1}\leftarrow\mathbb{B} , z_{i}=\nicefrac{{2^{-i}}}{{8d}} for all i \triangleright Initial confidence sets and scale parameters 2: for t=1,\dots,T do 3: The adversary reveals the context x_{t} 4: let i_{t} be the largest index i such that \max\{\width(S_{t},x_{t}),\width(B_{t},x_{t})\}\leq 2^{-i} 5: if \proj(S_{t},x_{t})\cap\proj(B_{t},x_{t})=\emptyset then \triangleright Well-separated 6: p_{t}\leftarrow\overline{s}_{t} 7: else if \width(S_{t},x_{t})\geq\width(B_{t},x_{t}) then \triangleright Seller Dominating 8: p_{t}\leftarrow the solution of \vol(\{v\in S_{t}+z_{i_{t}}\mathbb{B}\mid\langle v,x_{t}\rangle\leq p_{t}\})=\tfrac{1}{2}\vol(S_{t}+z_{i_{t}}\mathbb{B}) 9: else \triangleright Buyer Dominating 10: p_{t}\leftarrow the solution of \vol(\{v\in B_{t}+z_{i_{t}}\mathbb{B}\mid\langle v,x_{t}\rangle\geq p_{t}\})=\tfrac{1}{2}\vol(B_{t}+z_{i_{t}}\mathbb{B}) 11: Post price p_{t} , and update S_{t} and B_{t} according to \mathbbm{1}\left\{\langle s,x_{t}\rangle\leq p_{t}\right\} and \mathbbm{1}\left\{\langle b,x_{t}\rangle\geq p_{t}\right\} Algorithm 2 Efficiency Maximization with One-Bit Feedback and Per-Round Budget Balance 1: S_{1},B_{1}\leftarrow\mathbb{B} \triangleright Initial confidence sets 2: for t=1,\dots,T do 3: The adversary reveals the context x_{t} 4: if \overline{s}_{t}\leq\underline{b}_{t} then \triangleright Well-separated 5: p_{t}\leftarrow\overline{s}_{t} 6: else if \width(S_{t},x_{t})\geq\width(B_{t},x_{t}) and \nicefrac{{(\underline{s}_{t}+\overline{s}_{t})}}{{2}}\leq\underline{b}_{t} then \triangleright Weak overlap 7: p_{t}\leftarrow\nicefrac{{(\underline{s}_{t}+\overline{s}_{t})}}{{2}} 8: else if \width(B_{t},x_{t})\geq\width(S_{t},x_{t}) and \nicefrac{{(\underline{b}_{t}+\overline{b}_{t})}}{{2}}\geq\overline{s}_{t} then \triangleright Weak overlap 9: p_{t}\leftarrow\nicefrac{{(\underline{b}_{t}+\overline{b}_{t})}}{{2}} 10: else \triangleright Strong overlap 11: p_{t}\leftarrow a price drawn u.a.r. in \proj(S_{t},x_{t})\cup\proj(B_{t},x_{t}) 12: Post price p_{t} , and update S_{t} and B_{t} if there is no ambiguity in the feedback Appendix B Pseudocodes for profit maximization Algorithm 3 Profit Maximization with Two-Bit Feedback 1: S_{1},B_{1}\leftarrow\mathbb{B} , z_{i}=\nicefrac{{2^{-3\cdot 2^{i}}}}{{16d}} for all i \triangleright Initial confidence sets and scale parameters 2: for t=1,\dots,T do 3: The adversary reveals the context x_{t} 4: let i_{t} be the largest index such that \max\{\width(S_{t},x_{t}),\width(B_{t},x_{t})\}\leq 2^{-2^{i_{t}}} 5: if \max\{\width(S_{t},x_{t}),\width(B_{t},x_{t})\}\leq\nicefrac{{1}}{{T}} then 6: p_{t}\leftarrow\overline{s}_{t} , q_{t}\leftarrow\max\{p_{t},\underline{b}_{t}\} 7: else if \width(S_{t},x_{t})\geq\width(B_{t},x_{t}) then \triangleright Seller Dominating case 8: m^{S}_{t} solves \vol(\{v\in S_{t}+z_{i_{t}}\mathbb{B}\mid\langle v,x_{t}\rangle\geq m^{S}_{t}\})=2^{-2^{{i_{t}}-1}}\vol(S_{t}+z_{i_{t}}\mathbb{B}) 9: p_{t}\leftarrow m^{S}_{t}+z_{i_{t}} , q_{t}\leftarrow\max\{p_{t},\underline{b}_{t}\} 10: else \triangleright Buyer Dominating case 11: m^{B}_{t} solves \vol(\{v\in B_{t}+z_{i_{t}}\mathbb{B}\mid\langle v,x_{t}\rangle\leq m^{B}_{t}\})=2^{-2^{{i_{t}}-1}}\vol(B_{t}+z_{i_{t}}\mathbb{B}) 12: q_{t}\leftarrow m^{B}_{t}-z_{i_{t}} , p_{t}\leftarrow\min\{q_{t},\overline{s}_{t}\} 13: Post price p_{t} to the seller and q_{t} to the buyer 14: Update S_{t} and B_{t} according to \mathbbm{1}\left\{\langle s,x_{t}\rangle\leq p_{t}\right\} and \mathbbm{1}\left\{\langle b,x_{t}\rangle\geq q_{t}\right\} Algorithm 4 Profit Maximization with One-Bit Feedback and Per-Round Budget Balance 1: S_{1},B_{1}\leftarrow\mathbb{B} \triangleright Initial confidence sets 2: for t=1,\dots,T do 3: The adversary reveals the context x_{t} 4: if \max\{\width(S_{t},x_{t}),\width(B_{t},x_{t})\}\leq\nicefrac{{1}}{{T}} then \triangleright Small widths 5: p_{t}\leftarrow\overline{s}_{t} , q_{t}\leftarrow\max\{p_{t},\underline{b}_{t}\} 6: else if \width(S_{t},x_{t})\geq\width(B_{t},x_{t}) and \nicefrac{{(\underline{s}_{t}+\overline{s}_{t})}}{{2}}\leq\underline{b}_{t} then \triangleright Weak overlap 7: p_{t}\leftarrow\nicefrac{{(\underline{s}_{t}+\overline{s}_{t})}}{{2}} , q_{t}\leftarrow p_{t} 8: else if \width(B_{t},x_{t})\geq\width(S_{t},x_{t}) and \nicefrac{{(\underline{b}_{t}+\overline{b}_{t})}}{{2}}\geq\overline{s}_{t} then \triangleright Weak overlap 9: q_{t}\leftarrow\nicefrac{{(\underline{b}_{t}+\overline{b}_{t})}}{{2}} , p_{t}\leftarrow p_{t} 10: else \triangleright Strong overlap 11: Let u_{t} be a price drawn u.a.r. in [-1,1] 12: p_{t}\leftarrow u_{t} , q_{t}\leftarrow u_{t} 13: Post price p_{t} to the seller and q_{t} to the buyer 14: Update S_{t} and B_{t} if there is no ambiguity in the feedback Appendix C Omitted Content from Section 4 See 4.1 x_{t} 2^{-i_{t}-1} p_{t} \Gamma_{t}^{\text{left}} \Gamma_{t}^{\text{right}} x_{t} u^{\text{left}} u^{\text{right}} Figure 6 : Illustration for the proof of Lemma 4.1 : The blue opaque body is S_{t}+z_{i_{t}}\mathbb{B} and the black solid contoured one is S_{t} . In faded red, the cones encapsulating the convex body. The solid red vertical line is the largest cross-section of (d-1) -dimensional volume \nu . Proof. We prove the statement concerning an accepted seller price, the other three cases are analogous (see Figure 6 for an illustration). The seller’s confidence region at time t+1 reads S_{t+1}=\{v\in S_{t}\mid\langle x_{t},v\rangle\leq p_{t}\}. Consider the subset of S_{t+1}+z_{i_{t}}\mathbb{B} intersected with the half-space \{v:\langle x_{t},v\rangle\leq p_{t}\} . By definition of p_{t} , and the fact that the seller accepts the price, we have that \vol(\{v\in S_{t+1}+z_{i_{t}}\mathbb{B}\mid\langle v,x_{t}\rangle\leq p_{t}\})\leq\vol(\{v\in S_{t}+z_{i_{t}}\mathbb{B}\mid\langle v,x_{t}\rangle\leq p_{t}\})=\tfrac{1}{2}\vol(S_{t}+z_{i_{t}}\mathbb{B}). (11) Consider now the family of all cross-sections of S_{t}+z_{i_{t}}\mathbb{B} orthogonal to direction x_{t} that are at distance at most z_{i} from the subspace \{v:\langle x_{t},v\rangle=p_{t}\} , and denote with \nu the (d-1) -dimensional volume of the largest such cross-section. The set \{v\in S_{t+1}+z_{i_{t}}\mathbb{B}\mid\langle v,x_{t}\rangle\geq p_{t}\} is contained in a cylinder of width z_{i} and of cross-section \nu , therefore: \vol(\{v\in S_{t+1}+z_{i_{t}}\mathbb{B}\mid\langle v,x_{t}\rangle\geq p_{t}\})\leq\nu z_{i_{t}}. (12) Combining Equation 11 with Equation 12 , we thus have that \vol(S_{t+1}+z_{i_{t}}\mathbb{B})\leq\tfrac{1}{2}\vol(S_{t}+z_{i_{t}}\mathbb{B})+\nu z_{i_{t}}. Therefore, to conclude the proof, it suffices to show that \nu z_{i_{t}}\leq\tfrac{1}{4}\vol(S_{t}+z_{i_{t}}\mathbb{B}) . Denote with u^{\text{left}}_{t} and u^{\text{right}}_{t} the extremes of S_{t}+z_{i_{t}}\mathbb{B} along direction x_{t} ; we introduce an orientation “left” and “right”, in the sense that u^{\text{left}}_{t} is the point corresponding to the smallest value of \langle v,s\rangle for v\in S_{t+1}+z_{i_{t}}\mathbb{B} , while u^{\text{right}}_{t} corresponds to the largest. We then consider the cone \Gamma^{\text{left}}_{t} (resp. \Gamma^{\text{right}}_{t} ) formed by taking the convex hull of the largest cross-section of (d-1) -dimension \nu and u^{\text{left}}_{t} (resp. u^{\text{right}}_{t} ). Since the distance of u^{\text{left}}_{t} and u^{\text{right}}_{t} along direction x_{t} is at least 2^{-i_{t}-1} , and since z_{i_{t}}=\nicefrac{{2^{-i_{t}}}}{{8d}} , applying C.2 , we can conclude with \vol(S_{t}+z_{i_{t}}\mathbb{B})\geq\vol(\Gamma^{\text{left}}_{t})+\vol(\Gamma^{\text{right}}_{t})\geq\frac{2^{-i_{t}-1}\nu}{d}=4\nu z_{i_{t}}. ∎ See 4.3 Proof. We prove this lower bound via Yao’s Principle, by constructing a randomized instance such that any deterministic algorithm suffers, in expectation, the desired regret rate \Omega(d) . Consider an instance where the contexts are just the canonical basis vectors, arriving one after the other e_{1},e_{2},\dots,e_{d} . The instance can be arbitrarily long, but we only need these first d contexts. We construct s and b independently per coordinate. Namely, for each coordinate j\in\{1,\ldots,d\} : (s_{j},b_{j})=\begin{cases}(0,\nicefrac{{1}}{{3}}),\text{ w.p. }\nicefrac{{1}}{{2}}\\ (\nicefrac{{2}}{{3}},1),\text{ w.p. }\nicefrac{{1}}{{2}}\end{cases}. We note that, since every new context is not spanned by the previous ones and (s_{j},b_{j}) are determined independently per coordinate, the information provided by context e_{j} is of no use to the algorithm for the successive contexts e_{i} for i>j . Consider now any learning algorithm, the problem faced at each new context is independent from the past observation, in particular for any price p_{t} it posts, it either observes a trade with probability \nicefrac{{1}}{{2}} (i.e., by posting prices in [0,\nicefrac{{1}}{{3}}]\cup[\nicefrac{{2}}{{3}},1] ) or it cannot observes a trade (for p_{t}\in(\nicefrac{{1}}{{3}},\nicefrac{{2}}{{3}}) ). Overall, its expected gain from trade is at most \nicefrac{{d}}{{6}} . Conversely, the benchmark attains a gain from trade of \nicefrac{{d}}{{3}} , as it always picks the right price between \nicefrac{{1}}{{3}} and \nicefrac{{2}}{{3}} for a per-round gain from trade of \nicefrac{{1}}{{3}} . This concludes the proof. ∎ See 4.5 We first establish the following (arguably folklore) facts: Fact C.1 . Consider a body K\in\mathbb{R}^{d} whose intrinsic d -dimensional volume is denoted by \vol(K) . Then, the body K^{\prime}=\gamma K scaled by some positive scalar \gamma>0 has volume \gamma^{d}\cdot\vol(K) . Proof. We know that, for an injective, continuously differentiable map f:U\to\mathbb{R}^{d} , it holds that \int_{f(U)}g(y)dy=\int_{U}g(f(x))\cdot|\det(Df(x))|dx, where \det(Df) is the Jacobian determinant. We let f(x)=\gamma x so that Df(x)=\gamma I_{d} , and hence, the above becomes \vol(\gamma K)=\int_{K}|\det(\gamma I_d)|dx=\gamma^{d}\cdot\int_{K}1dx=\gamma^{d}\cdot\vol(K), as desired. ∎ Fact C.2 . Consider a d -dimensional cone \Gamma , defined as the convex hull of a d-1 -dimensional convex set \Psi_{d-1} called the base, and a point q called the apex, at distance \ell from the subspace that supports \Psi_{d-1} . Its volume satisfies \vol(\Gamma)=\frac{\ell}{d}\cdot\vol(\Psi_{d-1}), where \vol(\Psi_{d-1}) is to be intended in dimension (d-1) . Proof. Any cross-section of the cone taken by a hyperplane parallel to the base at a distance x from the apex q (with 0\leq x\leq\ell ) is a scaled copy of \Psi_{d-1} with scaling factor \nicefrac{{x}}{{\ell}} . Thus, the (d-1) -volume of this slice is \vol\left(\frac{x}{\ell}\cdot\Psi_{d-1}\right)=\left(\frac{x}{\ell}\right)^{d-1}\cdot\vol(\Psi_{d-1}), by C.1 . We integrate over x from 0 to \ell to obtain a total volume of \vol(\Gamma)=\int_{0}^{\ell}\left(\frac{x}{\ell}\right)^{d-1}\vol(\Psi_{d-1})\,dx=\vol(\Psi_{d-1})\cdot\ell^{-d+1}\int_{0}^{\ell}x^{d-1}dx=\frac{\ell}{d}\cdot\vol(\Psi_{d-1}). This establishes the statement. ∎ x z H z \alpha\ell (1-\alpha)\ell u^{\text{left}} u^{\prime} u^{\text{right}} \alpha\ell z u^{\text{left}} u^{\prime} u^{\text{right}} Figure 7 : Illustration for the proof of Lemma 4.5 . Proof of Lemma 4.5 . We denote by \ell=\width(K,x) , the length of the segment \proj(x,K) . Without loss of generality, we assume that H is of the form H=\{y\in\mathbb{R}^{d}:\langle x,y\rangle\leq\lambda\} , where x is the vector normal to h , and that the convex set K is closed and bounded. The notations introduced in the proof are illustrated in Figure 7 . We denote by u^{\text{left}} (resp. u^{\text{right}} ) a minimizer (resp. maximizer) of :u\rightarrow\langle u,x\rangle in K+z\mathbb{B} . Note that we must have \langle u^{\text{right}}-u^{\text{left}},x\rangle=\ell+2z . We also define the point u^{\prime} in the segment [u^{\text{left}},u^{\text{right}}] satisfying \langle u^{\prime}-u^{\text{left}},x\rangle=\alpha\ell . We denote by h^{\prime} the hyperplane orthogonal to x passing through u^{\prime} , and by H^{\prime} the corresponding half-space that contains u^{\text{left}} (note that H^{\prime}\subset H ). We partition K+z\mathbb{B} into two convex pieces according to h^{\prime} , we denote by L the part containing u^{\text{left}} (i.e., L=(K+z\mathbb{B})\cap H^{\prime} ), and by R the part containing u^{\text{right}} (i.e., R=(K+z\mathbb{B})\setminus H^{\prime} ). Observing that K\setminus H+z\mathbb{B}\subset R and that \vol(K+z\mathbb{B})=\vol(L)+\vol(R) , we can write \frac{\vol(K+z\mathbb{B})}{\vol(K\setminus H+z\mathbb{B})}\geq\frac{\vol(K+z\mathbb{B})}{\vol(R)}=1+\frac{\vol(L)}{\vol(R)}. Our goal is thus now to lower bound the numerator \vol(L) , and upper bound the denominator \vol(R) . To that end, consider the cone \Gamma generated as the convex hull of the base (K+z\mathbb{B})\cap h^{\prime} and the apex u^{\text{left}} . By convexity of L , we must have \Gamma\subset L , and thus \vol(\Gamma)\leq\vol(L) . Now further observe that, by convexity of K+z\mathbb{B} , R must be contained in \Gamma^{+}\setminus\Gamma , where \Gamma^{+} is a rescaled copy of \Gamma with rescale factor \nicefrac{{\ell+2z}}{{\alpha\ell}} . This implies that \vol(R)\leq((\nicefrac{{\ell+2z}}{{\alpha\ell}})^{d}-1)\vol(\Gamma) , which gives, \frac{\vol(K+z\mathbb{B})}{\vol(K\setminus H+z\mathbb{B})}\geq 1+\frac{1}{(\nicefrac{{\ell+2z}}{{\alpha\ell}})^{d}-1}=\frac{1}{1-\left(\frac{\alpha\ell}{\ell+2z}\right)^{d}}\geq\frac{1}{1-\left(\frac{\alpha}{1+2\alpha}\right)^{d}} since z\leq\alpha\ell . This concludes the proof. ∎ Appendix D Omitted Content from Section 5 See 5.1 Proof. Let us focus on the seller, as the proof for the buyer is identical, but with the signs flipped. Since the seller refuses the price, we know that \{v\in S_{t}+z_{i}\mathbb{B}\mid\langle v,x_{t}\rangle