Introduction
We study parameter search problems in settings where decision makers receive only limited feedback. For example, a pricing algorithm sees the features of the customer, quotes a price for a product described by a feature vector and learns only whether the customer bought it. An idealized dosing procedure receives patient features and learns only whether the dose was too low or too high. A broker quotes prices to both a buyer and a seller, and learns only whether they traded. In each case, there is a vector hidden from the learner, and at each step, the observed features provide a “context”: together, the hidden vector and the context determine a target value that the learner tries to match. In this paper, we study two classical problems at the intersection of theoretical computer science and economics that are inspired by such situations: contextual search and contextual bilateral trade .
Contextual search. The basic problem in this setting is contextual search , where the target is an unknown vector z ∈ R d z \in\mathbb{R}^{d} z ∈ R d . In round t t t , an adversary reveals the context vector x t x_t x t with ∥ x t ∥ 2 ≤ 1 \lVert x_t\rVert_2 \le1 ∥ x t ∥ 2 ≤ 1 . The two together define the target value x t T z x_t^{\mathsf{T}}z x t T z —this is unknown to the learner, since z z z is unknown. The learner does observe x t x_t x t , then proposes a price p t p_t p t and incurs symmetric loss ℓ t = ∣ x t T z − p t ∣ \ell_t = \lvert x_t^{\mathsf{T}}z - p_t\rvert ℓ t = ∣ x t T z − p t ∣ . The learner observes neither the target value nor the loss incurred, but only the one-bit feedback sign ( x t T z − p t ) \operatorname{sign}(x_t^{\mathsf{T}}z-p_t) sign ( x t T z − p t ) —i.e., whether the price was too high or too low. Using this information, the learner aims to bound its total loss ∑ t = 1 T E [ ℓ t ] \sum_{t=1}^{T} \mathbb{E}[\ell_t] ∑ t = 1 T E [ ℓ t ] (also called the “regret”) independently of T T T . The problem of contextual search arose from feature-based pricing and auctions [15 , 9 , 17 ] . It is useful to note that, for d = 1 d = 1 d = 1 , the problem reduces to binary search, but higher-dimensional versions become much more challenging. Indeed, a series of works has studied this problem, and the state of the art is an O ( d log d ) O(d\log d) O ( d log d ) -competitive algorithm [16 ] . However, the lower bound was only Ω ( d ) \Omega(\sqrt{d}) Ω ( d ) : can we close this gap?
Contextual bilateral trade. An extension of contextual search is bilateral trade , where the learner is a broker who intermediates between a seller and a buyer with hidden vectors s , b ∈ R d s,b \in\mathbb{R}^{d} s , b ∈ R d . In round t t t , an adversary reveals a context vector x t x_t x t with ∥ x t ∥ 2 ≤ 1 \lVert x_t\rVert_2 \le1 ∥ x t ∥ 2 ≤ 1 corresponding to valuations x t T s x_t^{\mathsf{T}}s x t T s for the seller and x t T b x_t^{\mathsf{T}}b x t T b for the buyer—these are unknown to the broker, who does not see s , b s,b s , b . The broker then proposes a price p t p_t p t and observes whether both agents are willing to trade at that price, i.e., if x t T s ≤ p t ≤ x t T b x_t^{\mathsf{T}}s \le p_t \le x_t^{\mathsf{T}}b x t T s ≤ p t ≤ x t T b . Note that, given the feedback structure, a failed trade does not identify which agent refused. The broker aims to maximize gain from trade, defined as ∑ ( x t T b − x t T s ) + \sum(x_t^{\mathsf{T}}b-x_t^{\mathsf{T}}s)_+ ∑ ( x t T b − x t T s ) + , where the sum is taken over all rounds t t t in which the trade took place, or equivalently, to minimize the total loss ∑ t = 1 T E [ ℓ t ] \sum_{t=1}^{T}\mathbb{E}[\ell_t] ∑ t = 1 T E [ ℓ t ] , which is the total gain from trade it failed to realize. The model was introduced by Gaucher et al. [GBC⁺25], building on the online bilateral trade framework of Cesa-Bianchi et al. [CBC⁺21, CCC⁺24]. The gaps left by the literature are much larger in this setting: the only upper bound for this one-bit feedback model is O ( d δ b ) O(d\delta^b) O ( d δ b ) [CFG⁺26], and the lower bound is again Ω ( d ) \Omega(\sqrt{d}) Ω ( d ) , leaving a huge gap: can we close it?
Results
In this work, we give tight results for both these problems: we show that both problems admit O ( d ) O(\sqrt{d}) O ( d ) -regret algorithms, which are tight by the lower bounds mentioned above. In addition to giving tight results, however, our work showcases the use of a potential function—the square-root trace potential —which is the central tool in both analyses. Moreover, we also present results for the Bayesian setting (where z z z , s s s , and b b b are drawn from known prior distributions), which inspire our algorithms for the adversarial setting.
Worst-case guarantees. For worst-case guarantees, the unknown target z ∈ R d z \in\mathbb{R}^d z ∈ R d and the valuation vectors s , b ∈ R d s,b \in\mathbb{R}^d s , b ∈ R d are assumed to be selected from the Euclidean unit ball by the adversary. The adversary knows the learner’s algorithm, but not the random bits it uses. This is the main point of view taken in prior works on both contextual search and bilateral trade. We obtain horizon-independent O ( d ) O(\sqrt{d}) O ( d ) expected-loss bounds for both problems, matching the existing lower bounds up to constant factors. Table 1 summarizes our worst-case guarantees and compares them with prior work for contextual search and bilateral trade.
Table 1. Worst-case guarantees for unit-norm contexts and hidden vectors.
Bayesian guarantees. For Bayesian guarantees, we assume that the unknown vectors z , s , b ∈ R d z,s,b \in\mathbb{R}^d z , s , b ∈ R d are sampled from a known prior distribution with finite second moments. This point of view deviates from the existing literature but is particularly illuminating: it yields simpler algorithms and a first potential function, based on posterior covariance, that will guide the adversarial analysis. For known priors with finite second moments, our bounds depend only on the prior covariance matrices and hold at every horizon (Table 2 ).
Table 2. Bayesian rates for unit-norm contexts and priors with finite second moments. Σ \Sigma Σ is the prior covariance in contextual search, and Σ S , Σ B \Sigma_S,\Sigma_B Σ S , Σ B are the seller’s and buyer’s marginal prior covariances in bilateral trade.
Our worst-case guarantees and our Bayesian guarantees are clearly related, since Tr Σ = O ( d ) \operatorname{Tr}\sqrt{\Sigma}=O(\sqrt{d}) Tr Σ = O ( d ) when Σ \Sigma Σ is the covariance matrix associated with the uniform distribution in the Euclidean ball. Yet neither directly implies the other: in particular, the Bayesian setting allows for distributions with unbounded support or with skewed covariance matrices, such as Gaussian distributions. Thus, the Bayesian setting is not merely an intermediate conceptual step toward worst-case competitive guarantees, but is of independent interest.
Our Techniques
We now outline the intuition behind our algorithms and the essential ingredients of their analysis.
Our Algorithms
In the Bayesian setting, the learner is given a prior distribution on the hidden parameters: the vector z z z for contextual search, or the pair ( b , s ) (b,s) ( b , s ) for contextual bilateral trade. Using this, at any time t t t , the learner has access to the posterior distribution of the unknown parameters z z z or $s,b conditioned on all the past observations. Our Bayesian algorithms (Algorithms 1 and 3) compute a proposed price p t p_t p t based only on that posterior distribution and on the context vector x t x_t x t ; then they update the posterior distribution with the corresponding feedback. Our Bayesian algorithm for contextual search (Algorithm 1) is remarkably simple: it posts prices μ t ± σ t / 2 \mu_t \pm\sigma_t/2 μ t ± σ t /2 , where μ t \mu_t μ t is the posterior mean of x t T z x_t^\mathsf{T}z x t T z , and σ t \sigma_t σ t is the posterior standard deviation of x t T z x_t^\mathsf{T}z x t T z . The bilateral trade algorithm (Algorithm 3) similarly uses the posterior, now of the two projected values x t T s x_t^\mathsf{T}s x t T s and x t T b x_t^\mathsf{T}b x t T b , and posts a common price to both agents. This price is chosen to balance trading and learning, allowing us to bound total regret by the learner’s initial uncertainty (Lemma 3.1).
In the worst-case setting, the learner has no posterior distribution on the unknown parameters, so it maintains a suitable “proxy” for the potential used in the Bayesian analysis. For contextual search, it maintains two parameters, a vector m t ∈ R d m_t \in\mathbb{R}^d m t ∈ R d and a matrix R t ∈ R d × d R_t \in\mathbb{R}^{d \times d} R t ∈ R d × d , which we call the posterior mean proxy and the posterior square-root covariance proxy . Informally, these parameters can be interpreted as an estimate of the unknown parameter (for m t m_t m t ) and a measure of uncertainty in that estimate in all directions (for R t R_t R t ). Importantly, we do not maintain explicit uncertainty sets as in previous work—in particular, the unknown parameter need not lie within the ellipsoid m t + R t B d m_t + R_t B_d m t + R t B d , where B d B_d B d is the unit Euclidean ball (as, e.g., in the ellipsoid method). Instead, our proofs directly show that the per-step regret can be charged to the decrease in a certain potential. From this perspective, the worst-case contextual search algorithm (Algorithm 2) posts prices m t ± r t / 2 m_t \pm r_t/2 m t ± r t /2 , where m t = x t T m t m_t = x_t^\mathsf{T}m_t m t = x t T m t , and r t = ∥ R t x t ∥ 2 r_t = \lVert R_t x_t\rVert_2 r t = ∥ R t x t ∥ 2 —a rule remarkably similar to the Bayesian rule in Algorithm 1. For bilateral trade (Algorithm 4), m t ∈ R 2 d m_t \in\mathbb{R}^{2d} m t ∈ R 2 d stores separate d d d -dimensional mean proxies for the seller and buyer, and the matrix R t ∈ R 2 d × 2 d R_t \in\mathbb{R}^{2d \times2d} R t ∈ R 2 d × 2 d is block diagonal, with one d × d d \times d d × d block for each agent’s square-root covariance proxy. The algorithm samples a common price and two possible successor states from a finite lottery, then keeps the successor selected by the trade bit. Whereas contextual search admits explicit state updates, here we apply the minimax theorem to guarantee the existence of a single lottery that works for every possible hidden pair of buyer and seller.
Although the focus of the paper is not on computational complexity, we note that our worst-case contextual search algorithm (Algorithm 2) uses O ( d 2 ) O(d^2) O ( d 2 ) memory throughout the execution and performs only O ( d 2 ) O(d^2) O ( d 2 ) operations per round, making it significantly more practical than previous approaches for contextual search that rely on costly geometric routines such as computing intrinsic volumes or barycenters of high-dimensional convex bodies [19 , 16 ] .
Analyses via the Trace-Sqrt Potential
We bound the regret of all our algorithms via a potential-based analysis, using a pair of potential functions we feel may be useful in other contexts. It will be illuminating to start with the Bayesian problem for contextual search. Here we have a random vector z ∈ R d z \in\mathbb{R}^d z ∈ R d with finite second moment; this represents the hidden vector that a learner does not know; however, we do know the distribution from which z z z is drawn, and hence know its mean μ = E [ z ] \mu= \mathbb{E}[z] μ = E [ z ] and covariance Σ = Cov ( z ) ⪰ 0 \Sigma= \operatorname{Cov}(z) \succeq0 Σ = Cov ( z ) ⪰ 0 . In order to quantify the uncertainty about z z z , we use the trace-sqrt potential of the covariance:
Ψ ( Σ ) = Tr Σ = ∑ i = 1 d σ i , (1) \Psi(\Sigma) = \operatorname{Tr}\sqrt{\Sigma} = \sum_{i=1}^{d} \sigma_i, \tag*{(1)} Ψ ( Σ ) = Tr Σ = i = 1 ∑ d σ i , (1)
where σ i = λ i \sigma_i = \sqrt{\lambda_i} σ i = λ i is the square root of the i i i -th eigenvalue of Σ \Sigma Σ , commonly called the i i i -th semiaxis length; see Figure 1 for an illustration. The figure highlights a key point: the potential naturally captures a notion of “distance” and “spread”, as opposed to other potentials (like the logarithm of the volume) which would need various tricks to relate regret to the reduction in the volume, incurring losses along the way.
Figure 1. The covariance ellipsoid associated with Σ \Sigma Σ . Geometrically, the trace-square-root potential Ψ = σ 1 + σ 2 \Psi= \sigma_1 + \sigma_2 Ψ = σ 1 + σ 2 equals the 1-dimensional intrinsic volume (i.e., half the perimeter) of the smallest enclosing box of the ellipsoid, divided by 2. This perspective relates our potential to early geometric approaches to contextual search [19 ] , which relied on intrinsic volumes.
Whatever the learner observes next — the feedback from a round, a new context, or any other information revealed about z z z — is a signal : a random variable Y Y Y defined jointly with z z z . After observing Y Y Y , the remaining uncertainty is described by z ∣ Y z \mid Y z ∣ Y ; let the new covariance matrix be Σ Y \Sigma_Y Σ Y . This means the potential moves from Ψ ( Σ ) \Psi(\Sigma) Ψ ( Σ ) to Ψ ( Σ Y ) \Psi(\Sigma_Y) Ψ ( Σ Y ) .
The effect of signals on the potential. The first important observation is this: For any signal Y Y Y , the law of total covariance (which states that the total covariance equals the expected posterior covariance plus the covariance of the posterior mean) gives
Cov ( z ) ⪰ E [ Cov ( z ∣ Y ) ] . (2) \operatorname{Cov}(z) \succeq\mathbb{E}[\operatorname{Cov}(z \mid Y)] . \tag*{(2)} Cov ( z ) ⪰ E [ Cov ( z ∣ Y )] . (2)
Now, the monotonicity and concavity of the operator A ↦ A A \mapsto\sqrt{A} A ↦ A on the positive-semidefinite cone (see, e.g., Example 3.48 in [5 ] ) allow us to infer that the potential is monotone in the Löwner order. This, combined with (2), means that
Ψ ( Σ ) ≥ E [ Ψ ( Σ Y ) ] (3) \Psi(\Sigma) \ge\mathbb{E}[\Psi(\Sigma_Y)] \tag*{(3)} Ψ ( Σ ) ≥ E [ Ψ ( Σ Y )] (3)
and hence the potential is non-increasing in expectation. Of course, this expected decrease is not good enough—we need the potential decrease to pay for our regret.
Potential drops versus directional uncertainty. The key ingredient in relating the potential drop to our regret is the following claim, which is a strengthening of the matrix square-root function’s monotonicity and concavity:
Lemma 1.1 (Gap Function). For any vector x ∈ R d x \in\mathbb{R}^d x ∈ R d with ∥ x ∥ ≤ 1 \lVert x\rVert\le1 ∥ x ∥ ≤ 1 , the “gap” function
g x ( A ) = Tr A − x ⊤ A x g_x(A) = \operatorname{Tr}\sqrt{A} - \sqrt{x^\top A x} g x ( A ) = Tr A − x ⊤ A x is monotone and concave on the positive-semidefinite cone.
We defer the proof to Lemma B.1 in Appendix B, but let us just mention that it follows by writing g x g_x g x as the infimum of a family of affine functions:
2 g x ( A ) = inf R ≻ 0 { Tr R − ∥ R x ∥ 2 + Tr [ ( R − 1 − x x ⊤ ∥ R x ∥ 2 ) A ] } . (4) 2g_x(A) = \inf_{R \succ0} \left\{ \operatorname{Tr} R - \lVert Rx\rVert_2 + \operatorname{Tr}\left[\left(R^{-1} - \frac{xx^\top}{\lVert Rx\rVert_2}\right)A\right] \right\}. \tag*{(4)} 2 g x ( A ) = R ≻ 0 inf { Tr R − ∥ R x ∥ 2 + Tr [ ( R − 1 − ∥ R x ∥ 2 x x ⊤ ) A ] } . (4)
where x x ⊤ / ∥ R x ∥ 2 = 0 xx^\top/\|Rx\|_2=0 x x ⊤ /∥ R x ∥ 2 = 0 when x = 0 x=0 x = 0 . (Somewhat surprisingly, we will return to this expression in a moment!) Now the potential drop can be bounded below by the decrease in the directional standard deviation, using (2) , Lemma 1.1 , and Jensen’s inequality:
Lemma 1.2 (Potential decrease lemma). Let z ∈ R d z \in\mathbb{R}^{d} z ∈ R d be a random vector with finite second moment and covariance matrix Σ ⪰ 0 \Sigma\succeq0 Σ ⪰ 0 , and let Y Y Y be any jointly defined random variable. Fix x ∈ R d x \in\mathbb{R}^{d} x ∈ R d with ∥ x ∥ 2 ≤ 1 \|x\|_2 \le1 ∥ x ∥ 2 ≤ 1 . Then
Tr ( Σ ) − E [ Tr ( Σ Y ) ] ⏟ expected potential drop ≥ x ⊤ Σ x − E [ x ⊤ Σ Y x ] ⏟ drop in directional std. dev. (5) \underbrace{\operatorname{Tr}(\sqrt{\Sigma})-\mathbb{E}\left[\operatorname{Tr}(\sqrt{\Sigma_Y})\right]}_{\text{expected potential drop}}
\geq
\underbrace{\sqrt{x^\top\Sigma x}-\mathbb{E}\left[\sqrt{x^\top\Sigma_Yx}\right]}_{\text{drop in directional std. dev.}} \tag*{(5)} expected potential drop Tr ( Σ ) − E [ Tr ( Σ Y ) ] ≥ drop in directional std. dev. x ⊤ Σ x − E [ x ⊤ Σ Y x ] (5)
To get intuition for the quantity on the right-hand side, define the “uncertainty” along a specific direction x x x (which should be thought of as the context vector) by the “directional” standard deviation sd x ( z ) = x ⊤ Σ x \operatorname{sd}_x(z)=\sqrt{x^\top\Sigma x} sd x ( z ) = x ⊤ Σ x . So the right-hand side of (5) is indeed the drop in the standard deviation in the direction of the context vector. In a very concrete sense, this reduces the high-dimensional object (related to Σ \Sigma Σ ) to a one-dimensional object (the reduction in standard deviation of a scalar random variable).
The Bayesian analysis. All that remains is to relate the loss incurred by our algorithm to this drop. Indeed, we show precisely this for our Bayesian contextual search algorithm: if the context vector is x t x_t x t , then our algorithm’s expected regret is at most a constant times the drop in standard deviation (see the proof of Theorem 2.1 ). Using the above inequalities and summing over all time steps, we get that the expected total regret is at most a constant times the expected total drop in potential Ψ \Psi Ψ . Since the potential is non-negative, this is at most the same constant times the initial potential, which is Tr Σ \operatorname{Tr}\sqrt{\Sigma} Tr Σ . This completes the Bayesian proof.
For contextual bilateral trade, our potential is the sum of two trace-sqrt potentials—one for each of the unknown buyer and seller vectors, Ψ t r = Tr Σ B + Tr Σ S \Psi_{\mathrm{tr}}=\operatorname{Tr}\sqrt{\Sigma_B}+\operatorname{Tr}\sqrt{\Sigma_S} Ψ tr = Tr Σ B + Tr Σ S —and we bound the lost gain from trade analogously.
Moving to the adversarial problem. Since the Bayesian problem has regret O ( d ) O(\sqrt{d}) O ( d ) , it is tempting to use the minimax theorem to infer the existence of an algorithm for the adversarial case. We take a slightly different route for contextual search. We go back to the proof of Lemma 1.1 , where we wrote g x ( Σ ) g_x(\Sigma) g x ( Σ ) as the infimum of affine functions in (4) . A similar proof shows that
2 Tr Σ = inf m ∈ R d , R ≻ 0 E [ Tr R + ( z − m ) ⊤ R − 1 ( z − m ) ] ⏟ (6) 2\operatorname{Tr}\sqrt{\Sigma}
=
\underbrace{\inf_{m\in\mathbb{R}^{d},\,R\succ0}\mathbb{E}\left[\operatorname{Tr}R+(z-m)^\top R^{-1}(z-m)\right]}_{} \tag*{(6)} 2 Tr Σ = m ∈ R d , R ≻ 0 inf E [ Tr R + ( z − m ) ⊤ R − 1 ( z − m ) ] (6)
The function Ψ \Psi Ψ on the left was our Bayesian potential, whereas Φ \Phi Φ on the right is what we use as our potential for the adversarial problem—the potentials for the “dual” Bayesian/adversarial problems are duals to each other!
We then show that our algorithm, which captures its uncertainty about z z z (which is now an adversarially chosen quantity) using the posterior “proxy mean” m t m_t m t and “proxy covariance” matrix R t 2 R_t^2 R t 2 , satisfies
expected cost of the algorithm at any time ≤ O ( 1 ) ⋅ expected change in Φ . \text{expected cost of the algorithm at any time}\quad\leq\quad O(1)\cdot\text{expected change in }\Phi. expected cost of the algorithm at any time ≤ O ( 1 ) ⋅ expected change in Φ.
For bilateral trade, we again sum the seller’s and buyer’s quadratic potentials. While in contextual search we can achieve the displayed bound through an explicit state update, in bilateral trade, a one-round minimax argument (Lemma 3.3) instead guarantees a finite lottery of prices and successor states satisfying the bound for every hidden pair, up to arbitrarily small slack.
Related Work
Contextual search was introduced as a multidimensional generalization of binary search [19 ] , providing a common framework for earlier contextual pricing problems at the interface of computer science and economics [15 , 1 , 9 , 14 ] . Most existing approaches to contextual search are inspired by cutting-plane methods in optimization, where the algorithm maintains a polytope of feasible targets that shrinks as the learner acquires information (in each round, a half-space of targets is incompatible with the feedback received). Since computing a candidate price based on the barycenter or Steiner point of the feasible polytope is insufficient [16 ] , [19 ] relied on tools from integral geometry. The loss bound was improved to O ( d log d ) O(d \log d) O ( d log d ) in [16 ] , by posting a price corresponding to the barycenter of an augmented version of the feasible polytope.
Our proxy covariance matrix approach is reminiscent of ellipsoid methods in optimization, which maintain a quadratic approximation of the feasible region [24 , 21 ] . Ellipsoid methods have previously been applied to contextual search, e.g., in [9 , 17 , 12 , 10 ] . A key novelty of our approach is that our proxy ellipsoid (or constant-factor dilatation of it) does not contain the feasible region. In fact, it expands in rounds where it receives “exterior” feedback! Of course, on average over several rounds, our proxy ellipsoid concentrates on the target parameters.
Related work on contextual search has also explored other loss functions, such as the pricing loss , which measures the revenue shortfall relative to knowing the buyer’s valuation, for which [16 ] obtain O ( d log log T + d log d ) O(d \log\log T + d \log d) O ( d log log T + d log d ) regret. Another criterion counts predictions whose error exceeds a prescribed tolerance ϵ \epsilon ϵ ; for this criterion, [17 ] give an algorithm making at most O ( d log ( d / ϵ ) ) O(d \log(d/\epsilon)) O ( d log ( d / ϵ )) errors.
The geometric viewpoint also connects contextual search to inverse optimization and low-regret cutting-plane methods [4 , 12 , 3 , 23 ] . In online inverse linear optimization, the learner recommends an action from a feasible set and then observes the action that maximizes the unknown linear objective over that set. Under Euclidean unit-ball normalization, [20 , 13 ] obtain a horizon-independent O ( d ) O(\sqrt{d}) O ( d ) expected-regret bound for this problem. The distinction in feedback is important: the optimal action feedback is more informative than the one-bit contextual search feedback.
The problem of bilateral trade goes back to [18 ] , which, interestingly, originally focused on a one-dimensional Bayesian setting somewhat related to ours, albeit with a single round (T = 1 T = 1 T = 1 ). Cesa-Bianchi et al. [CBC+21, CCC+24] studied a sequential version of the problem where the algorithm competes with the best fixed price in hindsight, with valuations sampled from a fixed unknown distribution; here, the regret unavoidably depends on the number of rounds T T T , but the dependence can be made sublinear. The contextual (multi-dimensional) problem was introduced by [10 ] ; their noiseless algorithm, which requires two-bit feedback, has O ~ ( d 2 log T ) \widetilde{O}(d^2 \log T) O ( d 2 log T ) regret. In the weaker one-bit feedback setting, the best time-independent result achieves O ( d 6 d ) O(d 6^d) O ( d 6 d ) regret [8 ] .
In variants of bilateral trade, the broker can post two distinct prices: p p p for the buyer and q q q for the seller. This extra degree of freedom can facilitate maximizing gain from trade. To restrict that advantage, it is usually assumed that the algorithm respects “global budget balance” [2 ] , i.e., that it does not run persistent deficits, or “per-round budget balance” [7 ] , which imposes q ≤ p q \le p q ≤ p in every round. Allowing the broker to post distinct prices also enables other measures of performance for bilateral trade, such as broker profit maximization [10 , 11 ] . Our algorithms do not use this flexibility.
Notation
We use ∥ ⋅ ∥ 2 \lVert\cdot\rVert_2 ∥ ⋅ ∥ 2 for the Euclidean norm, B 2 d = { v ∈ R d : ∥ v ∥ 2 ≤ 1 } B_2^d = \{v \in\mathbb{R}^d : \lVert v \rVert_2 \le1\} B 2 d = { v ∈ R d : ∥ v ∥ 2 ≤ 1 } for the Euclidean ball, and A ⪰ B A \succeq B A ⪰ B for the positive-semidefinite Löwner order on symmetric matrices. The positive-semidefinite square root of a positive-semidefinite matrix is unique and denoted by Σ 1 / 2 \Sigma^{1/2} Σ 1/2 . We write Tr ( ⋅ ) \operatorname{Tr}(\cdot) Tr ( ⋅ ) for trace, Cov ( ⋅ ) \operatorname{Cov}(\cdot) Cov ( ⋅ ) for covariance, and sd ( ⋅ ) \operatorname{sd}(\cdot) sd ( ⋅ ) for standard deviation. We set sign ( 0 ) = 1 \operatorname{sign}(0) = 1 sign ( 0 ) = 1 , and write a + = max { a , 0 } a_+ = \max\{a, 0\} a + = max { a , 0 } for the positive part.
We usually use bold symbols to denote vectors in R d \mathbb{R}^d R d . Specifically, we use μ \mu μ for a distributional mean and m \mathbf{m} m for the algorithmic mean proxy, with scalar projections μ = x T μ \mu= \mathbf{x}^{\mathsf{T}}\mu μ = x T μ and m = x T m m = \mathbf{x}^{\mathsf{T}}\mathbf{m} m = x T m along a context x \mathbf{x} x . A covariance matrix is denoted by Σ \Sigma Σ , with directional standard deviation σ = x T Σ x \sigma= \sqrt{\mathbf{x}^{\mathsf{T}}\Sigma\mathbf{x}} σ = x T Σ x .
The observed history at time t t t , denoted by F t − 1 \mathcal{F}_{t-1} F t − 1 , contains the contexts, posted prices, feedback, and the learner’s randomization from previous rounds. We write E t = E [ ⋅ ∣ F t − 1 , x t ] \mathbb{E}_t = \mathbb{E}[\cdot\mid\mathcal{F}_{t-1}, \mathbf{x}_t] E t = E [ ⋅ ∣ F t − 1 , x t ] for expectation conditional on this history and the current context, before the learner’s fresh randomization. For both contextual search and bilateral trade, contexts may adapt to this history but are chosen before the learner’s fresh randomization. In the Bayesian setting, each context is conditionally independent of the hidden vector or pair given F t − 1 \mathcal{F}_{t-1} F t − 1 , so observing it does not change the posterior.
Additional notation is summarized in the table in Appendix § 7 .
Contextual Search
In contextual search, the learner is looking for an unknown target z ∈ R d z \in\mathbb{R}^d z ∈ R d . At round t t t , the learner receives a context x t \mathbf{x}_t x t with ∥ x t ∥ 2 ≤ 1 \lVert\mathbf{x}_t \rVert_2 \le1 ∥ x t ∥ 2 ≤ 1 , posts P t ∈ R P_t \in\mathbb{R} P t ∈ R , suffers loss
ℓ t = ∣ x t T z − P t ∣ , and receives feedback Y t = sign ( x t T z − P t ) , \ell_t = \left|\mathbf{x}_t^{\mathsf{T}}z - P_t\right|,\qquad\text{and receives feedback}\qquad Y_t = \operatorname{sign}(\mathbf{x}_t^{\mathsf{T}}z - P_t), ℓ t = x t T z − P t , and receives feedback Y t = sign ( x t T z − P t ) ,
without observing either the target value or the loss. We seek bounds on the total loss ∑ t = 1 T E [ ℓ t ] \sum_{t=1}^{T} \mathbb{E}[\ell_t] ∑ t = 1 T E [ ℓ t ] that are independent of T T T . In this section, we first present a Bayesian algorithm whose expected total loss is at most 24 Tr Σ 24\operatorname{Tr}\sqrt{\Sigma} 24 Tr Σ for any known prior on z z z with finite second moment and covariance matrix Σ \Sigma Σ (Theorem 2.1 ). We then give an algorithm that needs no prior and has expected total loss at most 12 d 12\sqrt{d} 12 d when the hidden vector z z z lies in the Euclidean unit ball (Theorem 2.4 ). Both guarantees hold for every horizon T T T . For completeness, we recall the classical Ω ( d ) \Omega(\sqrt{d}) Ω ( d ) lower bound for contextual search in Appendix § 11 .
Bayesian Contextual Search
In the Bayesian setting, the target z ∈ R d z \in\mathbb{R}^d z ∈ R d has a known prior with finite second moment. That distribution is updated with the information acquired by the learner in previous rounds. Just before round t t t , we denote by
μ t = E [ z ∣ F t − 1 ] , Σ t = Cov ( z ∣ F t − 1 ) \mu_t = \mathbb{E}[z \mid\mathcal{F}_{t-1}],\qquad\Sigma_t = \operatorname{Cov}(z \mid\mathcal{F}_{t-1}) μ t = E [ z ∣ F t − 1 ] , Σ t = Cov ( z ∣ F t − 1 )
the posterior mean and covariance of the target. For the current context x t \mathbf{x}_t x t , we denote the scalar target by Z = x t T z Z = \mathbf{x}_t^{\mathsf{T}}z Z = x t T z , its conditional mean by μ t = x t T μ t \mu_t = \mathbf{x}_t^{\mathsf{T}}\mu_t μ t = x t T μ t and its standard deviation by σ t = ( x t T Σ t x t ) 1 / 2 \sigma_t = (\mathbf{x}_t^{\mathsf{T}}\Sigma_t\mathbf{x}_t)^{1/2} σ t = ( x t T Σ t x t ) 1/2 . Algorithm 1 queries one of two prices centered at μ t \mu_t μ t , as illustrated in Figure 2 .
Figure 2. (a) Bayesian prior; (b) posterior for ε t = 1 \varepsilon_t = 1 ε t = 1 with Y t = − 1 Y_t = -1 Y t = − 1 ; (c) posterior for ε t = 1 \varepsilon_t = 1 ε t = 1 with Y t = 1 Y_t = 1 Y t = 1 .
Algorithm 1 Bayesian Contextual Search
Given a known prior on z \boldsymbol{z} z with finite second moment, repeat the following at each round t = 1 , 2 , … t = 1, 2, \ldots t = 1 , 2 , … :
Compute the posterior moments μ t , Σ t \boldsymbol{\mu}_t, \boldsymbol{\Sigma}_t μ t , Σ t of z \boldsymbol{z} z and their projections on the context vector x t \boldsymbol{x}_t x t ,
μ t = x t T μ t , σ t = ( x t T Σ t x t ) 1 / 2 . \mu_t = \boldsymbol{x}_t^{\mathsf{T}}\boldsymbol{\mu}_t,\qquad\sigma_t = \left(\boldsymbol{x}_t^{\mathsf{T}}\boldsymbol{\Sigma}_t\boldsymbol{x}_t\right)^{1/2}. μ t = x t T μ t , σ t = ( x t T Σ t x t ) 1/2 .
Draw a fresh independent uniform sign ε t ∈ { − 1 , 1 } \varepsilon_t \in\{-1,1\} ε t ∈ { − 1 , 1 } and post the price
P t = μ t + σ t 2 ε t . P_t = \mu_t + \frac{\sigma_t}{2}\varepsilon_t. P t = μ t + 2 σ t ε t .
Observe Y t = sign ( x t T z − P t ) Y_t = \operatorname{sign}(\boldsymbol{x}_t^{\mathsf{T}}\boldsymbol{z} - P_t) Y t = sign ( x t T z − P t ) and compute the posterior distribution on z \boldsymbol{z} z .
Theorem 2.1 (Bayesian Contextual Search). For any known prior on z ∈ R d \boldsymbol{z} \in\mathbb{R}^d z ∈ R d with finite second moment and covariance Σ 1 \boldsymbol{\Sigma}_1 Σ 1 , Algorithm 1 satisfies, for every horizon T ≥ 1 T \ge1 T ≥ 1 ,
∑ t = 1 T E [ ℓ t ] ≤ 24 Tr Σ 1 . (7) \sum_{t=1}^{T} \mathbb{E}[\ell_t] \le24 \operatorname{Tr}\sqrt{\boldsymbol{\Sigma}_1}. \tag*{(7)} t = 1 ∑ T E [ ℓ t ] ≤ 24 Tr Σ 1 . (7) The expectation is over the prior and the randomization of the learner and the contexts.
Proof of Theorem 2.1. We use the following one-dimensional contraction bound for the standard deviation, stated in Lemma 2.2. The lemma, whose proof is elementary, implies that a single bit of information suffices to shrink the posterior standard deviation of a scalar distribution by a constant factor. The proof of this lemma is given in Appendix § 9 .§ 2 .
Lemma 2.2 (One-bit deviation contraction). Let Z Z Z be a square-integrable real random variable, with μ = E [ Z ] \mu= \mathbb{E}[Z] μ = E [ Z ] and σ = sd ( Z ) \sigma= \operatorname{sd}(Z) σ = sd ( Z ) . Let ε \varepsilon ε be uniform on { − 1 , 1 } \{-1,1\} { − 1 , 1 } and independent of Z Z Z . Define
P = μ + σ 2 ε , Y = sign ( Z − P ) . P = \mu+ \frac{\sigma}{2}\varepsilon,\qquad Y = \operatorname{sign}(Z-P). P = μ + 2 σ ε , Y = sign ( Z − P ) . Writing the posterior standard deviation as σ ′ = sd ( Z ∣ P , Y ) \sigma' = \operatorname{sd}(Z \mid P,Y) σ ′ = sd ( Z ∣ P , Y ) , we have E [ σ ′ ] ≤ 23 24 σ \mathbb{E}[\sigma'] \le\frac{23}{24}\sigma E [ σ ′ ] ≤ 24 23 σ .
The intuition is the following: because the threshold is placed at ± 1 2 σ \pm\frac{1}{2}\sigma ± 2 1 σ away from the mean, the middle region [ μ − 1 2 σ , μ + 1 2 σ ] [\mu- \frac{1}{2}\sigma,\mu+ \frac{1}{2}\sigma] [ μ − 2 1 σ , μ + 2 1 σ ] can hold at most 1 4 \frac{1}{4} 4 1 of the variance σ 2 \sigma^2 σ 2 ; at least one of the two outer tails must hold a large fraction of the variance. Conditioning on whether Z Z Z falls in that tail creates a win-win situation:
If the tail has large probability, then every point in the tail is at least 1 2 σ \frac{1}{2}\sigma 2 1 σ away from the mean, so learning whether Z Z Z is in the tail causes a large shift in the posterior mean, which reduces the variance (by the law of total variance).
If the tail has small probability, then isolating the tail removes a large chunk of variance from the “main body” of the distribution (shrinking the main body’s standard deviation), while the tail itself occurs so rarely that its own conditional standard deviation—which grows only like 1 / p 1/\sqrt{p} 1/ p while its probability shrinks like p p p —contributes almost nothing (∝ p \propto\sqrt{p} ∝ p ) to the expectation.
We now move on to the core argument. First, we bound the loss in a round of Algorithm 1 by σ t \sigma_t σ t , the uncertainty along the context vector. If σ t = 0 \sigma_t=0 σ t = 0 , then P t = Z = μ t P_t=Z=\mu_t P t = Z = μ t almost surely, so the loss is zero. For σ t > 0 \sigma_t>0 σ t > 0 , we have
E t [ ℓ t ] = E t [ ∣ Z − P t ∣ ] = E t [ max { ∣ Z − μ t ∣ , σ t 2 } ] ≤ σ t 2 + E t [ ( Z − μ t ) 2 ] 2 σ t = σ t . \mathbb{E}_t[\ell_t]=\mathbb{E}_t[|Z-P_t|]=\mathbb{E}_t\left[\max\left\{|Z-\mu_t|,\frac{\sigma_t}{2}\right\}\right]\le\frac{\sigma_t}{2}+\frac{\mathbb{E}_t[(Z-\mu_t)^2]}{2\sigma_t}=\sigma_t. E t [ ℓ t ] = E t [ ∣ Z − P t ∣ ] = E t [ max { ∣ Z − μ t ∣ , 2 σ t } ] ≤ 2 σ t + 2 σ t E t [( Z − μ t ) 2 ] = σ t .
where we used max { ∣ u ∣ , σ t / 2 } ≤ σ t / 2 + u 2 / ( 2 σ t ) \max\{|u|,\sigma_t/2\}\le\sigma_t/2+u^2/(2\sigma_t) max { ∣ u ∣ , σ t /2 } ≤ σ t /2 + u 2 / ( 2 σ t ) .
Next, we pay for each round’s loss with a decrease in the posterior potential Ψ t = Tr Σ t \Psi_t=\operatorname{Tr}\sqrt{\Sigma_t} Ψ t = Tr Σ t , where Σ t = Cov ( z ∣ F t − 1 ) \Sigma_t=\operatorname{Cov}(\mathbf z\mid\mathcal{F}_{t-1}) Σ t = Cov ( z ∣ F t − 1 ) . Let σ t = ( x t T Σ t x t ) 1 / 2 \sigma_t=(\mathbf{x}_t^{\mathsf T}\Sigma_t\mathbf{x}_t)^{1/2} σ t = ( x t T Σ t x t ) 1/2 and σ t ′ = ( x t T Σ t + 1 x t ) 1 / 2 \sigma'_t=(\mathbf{x}_t^{\mathsf T}\Sigma_{t+1}\mathbf{x}_t)^{1/2} σ t ′ = ( x t T Σ t + 1 x t ) 1/2 be the directional standard deviations of the target projection before and after the observation; we apply Lemma 2.2 to the random variable x t T z \mathbf{x}_t^{\mathsf T}\mathbf z x t T z and Lemma 1.2 to the potential Ψ t \Psi_t Ψ t to obtain the potential inequality
E t [ ℓ t ] ≤ σ t ≤ Lemma 2.2 24 ( σ t − E t [ σ t ′ ] ) ≤ Lemma 1.2 24 ( Ψ t − E t [ Ψ t + 1 ] ) . \mathbb{E}_t[\ell_t]\le\sigma_t\overset{\text{Lemma 2.2}}{\le}24\left(\sigma_t-\mathbb{E}_t[\sigma'_t]\right)\overset{\text{Lemma 1.2}}{\le}24\left(\Psi_t-\mathbb{E}_t[\Psi_{t+1}]\right). E t [ ℓ t ] ≤ σ t ≤ Lemma 2.2 24 ( σ t − E t [ σ t ′ ] ) ≤ Lemma 1.2 24 ( Ψ t − E t [ Ψ t + 1 ] ) .
Telescoping this inequality yields the theorem:
∑ t = 1 T E [ ℓ t ] ≤ 24 ( Ψ 1 − E [ Ψ T + 1 ] ) ≤ 24 Ψ 1 . \sum_{t=1}^{T}\mathbb{E}[\ell_t]\le24\left(\Psi_1-\mathbb{E}[\Psi_{T+1}]\right)\le24\Psi_1. t = 1 ∑ T E [ ℓ t ] ≤ 24 ( Ψ 1 − E [ Ψ T + 1 ] ) ≤ 24 Ψ 1 .
Adversarial Contextual Search
We now consider a fixed unknown target z \mathbf z z in the unit Euclidean ball. Our worst-case algorithm, Algorithm 2, maintains two parameters: a vector m t ∈ R d \mathbf m_t\in\mathbb{R}^d m t ∈ R d , the mean proxy, and a symmetric positive-definite scale matrix R t ∈ R d × d \mathbf R_t\in\mathbb{R}^{d\times d} R t ∈ R d × d , the square-root covariance proxy. This algorithm mirrors the Bayesian algorithm, Algorithm 1, in that m t \mathbf m_t m t plays the role of μ t \boldsymbol{\mu}_t μ t and R t \mathbf R_t R t plays the role of Σ t 1 / 2 \boldsymbol{\Sigma}_t^{1/2} Σ t 1/2 (their one-dimensional projections along the context axis are denoted by m t m_t m t and r t r_t r t ). The key nuance is that, without Bayesian posterior updates, Algorithm 2 specifies explicit updates for both proxies m t , R t \mathbf m_t,\mathbf R_t m t , R t that depend only on the posted price and the feedback received, as specified in (10) . Figure 3 illustrates one round of the algorithm.
Figure 3. Proxy ellipsoids: (a) before feedback; (b) after ε t = 1 \varepsilon_t=1 ε t = 1 with Y t = − 1 Y_t=-1 Y t = − 1 ; (c) after ε t = 1 \varepsilon_t=1 ε t = 1 with Y t = 1 Y_t=1 Y t = 1 .
Algorithm 2 Adversarial Contextual Search
Initialize
m 1 = 0 , R 1 = 1 d I d . (8) m_1=0,\qquad R_1=\frac{1}{\sqrt{d}}I_d. \tag*{(8)} m 1 = 0 , R 1 = d 1 I d . (8)
At each round t = 1 , 2 , … t=1,2,\ldots t = 1 , 2 , … :
Receive x t x_t x t , compute m t = x t ⊤ m t m_t=x_t^\top m_t m t = x t ⊤ m t , u t = R t x t u_t=R_tx_t u t = R t x t , a t = x t ⊤ u t a_t=x_t^\top u_t a t = x t ⊤ u t , and r t = ∥ u t ∥ 2 r_t=\lVert u_t\rVert_2 r t = ∥ u t ∥ 2 .
Draw a fresh independent uniform sign ε t ∈ { − 1 , 1 } \varepsilon_t\in\{-1,1\} ε t ∈ { − 1 , 1 } and post
P t = m t + r t 2 ε t . (9) P_t=m_t+\frac{r_t}{2}\varepsilon_t. \tag*{(9)} P t = m t + 2 r t ε t . (9)
Observe Y t Y_t Y t and update
m t + 1 = m t + Y t r t a t ( 3 − ε t Y t ) u t , R t + 1 = R t + ε t Y t a t ( 3 − ε t Y t ) u t u t ⊤ . (10) m_{t+1}=m_t+\frac{Y_tr_t}{a_t(3-\varepsilon_tY_t)}u_t,\qquad R_{t+1}=R_t+\frac{\varepsilon_tY_t}{a_t(3-\varepsilon_tY_t)}u_tu_t^\top. \tag*{(10)} m t + 1 = m t + a t ( 3 − ε t Y t ) Y t r t u t , R t + 1 = R t + a t ( 3 − ε t Y t ) ε t Y t u t u t ⊤ . (10)
Before providing our regret guarantee, we first verify that the algorithm is well-defined, meaning that the updates in (10) preserve the positive definiteness of the scale matrix R t ≻ 0 R_t\succ0 R t ≻ 0 . This observation is obvious in the case where ε t Y t = 1 \varepsilon_tY_t=1 ε t Y t = 1 , because adding a positive semidefinite matrix preserves positive definiteness; so it suffices to verify that positive definiteness is preserved whenever ε t Y t = − 1 \varepsilon_tY_t=-1 ε t Y t = − 1 .
Theorem 2.4 (Adversarial Contextual Search). For every fixed z z z with ∥ z ∥ 2 ≤ 1 \lVert z\rVert_2\le1 ∥ z ∥ 2 ≤ 1 , every horizon T ≥ 1 T\ge1 T ≥ 1 , and every admissible adaptive context strategy with ∥ x t ∥ 2 ≤ 1 \lVert x_t\rVert_2\le1 ∥ x t ∥ 2 ≤ 1 , Algorithm 2 satisfies
∑ t = 1 T E [ ℓ t ] ≤ 12 d . (11) \sum_{t=1}^{T}\mathbb{E}[\ell_t]\le12\sqrt{d}. \tag*{(11)} t = 1 ∑ T E [ ℓ t ] ≤ 12 d . (11)
The algorithm uses O ( d 2 ) O(d^2) O ( d 2 ) arithmetic operations and O ( d 2 ) O(d^2) O ( d 2 ) real-valued storage per round.
Proof of Theorem 2.4 . For a fixed hidden target, we consider the non-negative potential defined by
Φ t = Φ ( m t , R t , z ) = Tr R t + ( z − m t ) T R t − 1 ( z − m t ) . (12) \Phi_t = \Phi(m_t, R_t, z) = \operatorname{Tr} R_t + (z-m_t)^\mathsf{T}R_t^{-1}(z-m_t). \tag*{(12)} Φ t = Φ ( m t , R t , z ) = Tr R t + ( z − m t ) T R t − 1 ( z − m t ) . (12)
At initialization, the potential satisfies Φ 1 = d + d ∥ z ∥ 2 2 ≤ 2 d \Phi_1 = \sqrt{d}+\sqrt{d}\|z\|_2^2 \le2\sqrt{d} Φ 1 = d + d ∥ z ∥ 2 2 ≤ 2 d . We use the following potential-decrease bound, which is shown in Appendix § 9 .§ 3 .
Lemma 2.5 (One-round potential decrease). On every round of Algorithm 2,
E t [ ℓ t ] ≤ 6 ( Φ t − E t [ Φ t + 1 ] ) . (13) \mathbb{E}_t[\ell_t] \le6(\Phi_t-\mathbb{E}_t[\Phi_{t+1}]). \tag*{(13)} E t [ ℓ t ] ≤ 6 ( Φ t − E t [ Φ t + 1 ]) . (13)
As in the Bayesian case, the proof reduces to one dimension: we define φ ( m , r , z ) = r + ( m − z ) 2 r \varphi(m,r,z)=r+\frac{(m-z)^2}{r} φ ( m , r , z ) = r + r ( m − z ) 2 , which is just a scalar version of the potential Φ ( ⋅ ) \Phi(\cdot) Φ ( ⋅ ) . Going from R t R_t R t to R t + 1 R_{t+1} R t + 1 is a rank 1 perturbation, so the Sherman–Morrison formula expresses the expected potential drop Φ t − E t [ Φ t + 1 ] \Phi_t-\mathbb{E}_t[\Phi_{t+1}] Φ t − E t [ Φ t + 1 ] as a multiple of φ ( m t , r t , z ) − E t [ φ ( m t + 1 , r t + 1 , z ) ] \varphi(m_t,r_t,z)-\mathbb{E}_t[\varphi(m_{t+1},r_{t+1},z)] φ ( m t , r t , z ) − E t [ φ ( m t + 1 , r t + 1 , z )] , where m t m_t m t and r t r_t r t are the projected mean and deviation proxies; the proof now follows from elementary calculations.
Summing the potential inequality (13) over rounds yields ∑ t = 1 T E [ ℓ t ] + 6 E [ Φ T + 1 ] ≤ 6 Φ 1 ≤ 12 d \sum_{t=1}^{T}\mathbb{E}[\ell_t]+6\mathbb{E}[\Phi_{T+1}]\le6\Phi_1\le12\sqrt{d} ∑ t = 1 T E [ ℓ t ] + 6 E [ Φ T + 1 ] ≤ 6 Φ 1 ≤ 12 d , which proves the theorem.
In the algorithm, computing R t x t R_tx_t R t x t and performing the rank-one update each take O ( d 2 ) O(d^2) O ( d 2 ) arithmetic operations, whereas storing R t R_t R t and m t m_t m t requires O ( d 2 ) O(d^2) O ( d 2 ) real numbers. Importantly, the algorithm never evaluates Φ t \Phi_t Φ t or computes R t − 1 R_t^{-1} R t − 1 , which only serve in the analysis.
Contextual Bilateral Trade
In bilateral trade, a broker intermediates between a seller and a buyer who are represented by two vectors s , b ∈ R d s,b\in\mathbb{R}^d s , b ∈ R d . At round t t t , the broker receives a context vector x t x_t x t with ∥ x t ∥ 2 ≤ 1 \|x_t\|_2\le1 ∥ x t ∥ 2 ≤ 1 , proposes a price p t p_t p t , and observes whether trade occurs:
Y t = 1 { x t T s ≤ p t ≤ x t T b } . Y_t = 1\{x_t^\mathsf{T}s\le p_t\le x_t^\mathsf{T}b\}. Y t = 1 { x t T s ≤ p t ≤ x t T b } .
In particular, a failed trade does not identify the agent who rejected the price. The lost “gain from trade” in round t t t is defined as ℓ t = ( x t T ( b − s ) ) + ( 1 − Y t ) \ell_t=(x_t^\mathsf{T}(b-s))_+(1-Y_t) ℓ t = ( x t T ( b − s ) ) + ( 1 − Y t ) .
In § 3.1 we present a Bayesian algorithm whose expected total loss is at most 2 11 ( Tr Σ S + Tr Σ B ) 2^{11}(\operatorname{Tr}\sqrt{\Sigma_S}+\operatorname{Tr}\sqrt{\Sigma_B}) 2 11 ( Tr Σ S + Tr Σ B ) , for any known prior on the targets with marginal covariance matrices Σ S \Sigma_S Σ S and Σ B \Sigma_B Σ B (Theorem 3.2 ). In § 3.2 , we then give an algorithm that needs no prior and has expected total loss at most 2 12 d + 1 2^{12}\sqrt{d}+1 2 12 d + 1 when both targets lie in the unit Euclidean ball, so that w = ( s , b ) ∈ K = B 2 d × B 2 d w=(s,b)\in K=B_2^d\times B_2^d w = ( s , b ) ∈ K = B 2 d × B 2 d (Theorem 3.4 ). All our guarantees hold for every horizon T T T . For completeness, we recall the classical Ω ( d ) \Omega(\sqrt{d}) Ω ( d ) lower bound for bilateral trade in Appendix § 11 .
Bayesian Contextual Bilateral Trade
In the Bayesian setting, write W = ( s , b ) W=(s,b) W = ( s , b ) for the random pair of valuations. Its components may be dependent, and we require only finite second moments. For a distribution π \pi π of W W W , define
Ψ T ( π ) = Ψ ( Cov ( s ) ) + Ψ ( Cov ( b ) ) = Tr Cov ( s ) + Tr Cov ( b ) . (14) \Psi_T(\pi)=\Psi(\operatorname{Cov}(s))+\Psi(\operatorname{Cov}(b))=\operatorname{Tr}\sqrt{\operatorname{Cov}(s)}+\operatorname{Tr}\sqrt{\operatorname{Cov}(b)}. \tag*{(14)} Ψ T ( π ) = Ψ ( Cov ( s )) + Ψ ( Cov ( b )) = Tr Cov ( s ) + Tr Cov ( b ) . (14)
This is the sum of the two search potentials, not the trace square root of the joint covariance. If π \pi π is supported on K K K , then Ψ t r ( π ) ≤ 2 d \Psi_{\mathrm{tr}}(\pi) \le2\sqrt{d} Ψ tr ( π ) ≤ 2 d , because each marginal covariance has trace at most one. For support in [ − 1 , 1 ] d × [ − 1 , 1 ] d [-1,1]^d \times[-1,1]^d [ − 1 , 1 ] d × [ − 1 , 1 ] d , the corresponding bound is 2 d 2d 2 d .
Given a context x x x , the one-dimensional problem along x x x now involves a pair ( S , B ) (S,B) ( S , B ) rather than a single target. For a common price p ∈ R p \in\mathbb{R} p ∈ R , let Y ( p ) = 1 { S ≤ p ≤ B } Y(p) = 1\{S \le p \le B\} Y ( p ) = 1 { S ≤ p ≤ B } denote the trade bit, so that the loss incurred by posting price p p p is
L ( p ) = E [ ( B − S ) + ( 1 − Y ( p ) ) ] . (15) L(p) = \mathbb{E}[(B-S)_{+}(1-Y(p))]. \tag*{(15)} L ( p ) = E [( B − S ) + ( 1 − Y ( p ))] . (15)
To quantify the information obtained from the trade bit, for each Z ∈ { S , B } Z \in\{S,B\} Z ∈ { S , B } , we define the standard deviation drop D Z ( p ) = σ Z − E [ sd ( Z ∣ Y ( p ) ) ] D_Z(p) = \sigma_Z - \mathbb{E}[\operatorname{sd}(Z \mid Y(p))] D Z ( p ) = σ Z − E [ sd ( Z ∣ Y ( p ))] , so that the overall drop is
D ( p ) = D S ( p ) + D B ( p ) . (16) D(p) = D_S(p) + D_B(p). \tag*{(16)} D ( p ) = D S ( p ) + D B ( p ) . (16)
Each D Z ( p ) D_Z(p) D Z ( p ) is nonnegative by the law of total variance and the concavity of the square root. We now introduce the key lemma that shows the existence of a specific price p p p relating these two terms. We provide a proof sketch below, while the full proof is deferred to Appendix § 10 .§ 1 .
Lemma 3.1 (Trade or information). For every pair ( S , B ) (S,B) ( S , B ) of square-integrable real random variables, there is a common price p p p such that
L ( p ) ≤ 2 11 D ( p ) . (17) L(p) \le2^{11}D(p). \tag*{(17)} L ( p ) ≤ 2 11 D ( p ) . (17) The price can be chosen as a function of the joint distribution.
Proof sketch. Let α ( p ) = P ( S ≤ p ≤ B ) \alpha(p) = \mathbb{P}(S \le p \le B) α ( p ) = P ( S ≤ p ≤ B ) be the trade profile. For fixed valuations, ( B − S ) + (B-S)_{+} ( B − S ) + is the length of the interval of prices permitting trade. Averaging this length and interchanging expectation and integration gives
G = E [ ( B − S ) + ] = ∫ R α ( p ) d p . G = \mathbb{E}[(B-S)_{+}] = \int_{\mathbb{R}} \alpha(p)\,\mathrm{d}p. G = E [( B − S ) + ] = ∫ R α ( p ) d p .
Write μ Z = E [ Z ] \mu_Z = \mathbb{E}[Z] μ Z = E [ Z ] , σ Z = sd ( Z ) \sigma_Z = \operatorname{sd}(Z) σ Z = sd ( Z ) for Z ∈ { S , B } Z \in\{S,B\} Z ∈ { S , B } , σ = σ S + σ B \sigma= \sigma_S + \sigma_B σ = σ S + σ B , and m = μ B − μ S m = \mu_B - \mu_S m = μ B − μ S . A deterministic valuation (i.e., σ Z = 0 \sigma_Z = 0 σ Z = 0 ) is handled by posting that value. Otherwise, the analysis has two cases.
Overlapping case (m < 3 σ m < 3\sigma m < 3 σ ). In this case, the seller’s and buyer’s means are close to each other. To deal with this case, we put D ‾ = sup p D ( p ) \overline{D} = \sup_p D(p) D = sup p D ( p ) and, since L ( p ) ≤ G L(p) \le G L ( p ) ≤ G , we bound the entire area under α \alpha α by constructing the envelope H H H in Figure 4 . The crucial ingredient that we use to construct H H H is the following information identity, which is proved in the appendix and holds for any Z ∈ { S , B } Z \in\{S,B\} Z ∈ { S , B } :
Figure 4. A schematic trade profile α \alpha α (solid blue) and its piecewise upper bound H H H (dashed orange) in the overlapping case. The area under α \alpha α is G G G . The tails and central intervals contribute at most 162 D 162D 162 D under H H H ; the remaining plateau has area ( m − σ / 3 ) + (m-\sigma/3)_+ ( m − σ /3 ) + . Claim D.4 establishes the bound.
E [ ( E [ Z ∣ Y ( p ) ] − μ Z ) 2 + ( sd ( Z ∣ Y ( p ) ) − σ Z ) 2 ] = 2 σ Z D Z ( p ) . \mathbb{E}\left[\left(\mathbb{E}[Z \mid Y(p)]-\mu_Z\right)^2+\left(\operatorname{sd}(Z \mid Y(p))-\sigma_Z\right)^2\right] = 2\sigma_ZD_Z(p). E [ ( E [ Z ∣ Y ( p )] − μ Z ) 2 + ( sd ( Z ∣ Y ( p )) − σ Z ) 2 ] = 2 σ Z D Z ( p ) .
(Information Identity)
The left-hand side averages the squared change in the mean and standard deviation after observing rejection or trade. Thus a feedback outcome that substantially changes either quantity must provide information, weighted by its probability. In the tails of α ( ⋅ ) \alpha(\cdot) α ( ⋅ ) , a successful trade forces a large shift of the conditional mean, yielding inverse-square bounds. For instance, if p < μ S p < \mu_S p < μ S , trading implies E [ S ∣ Y ( p ) = 1 ] ≤ p \mathbb{E}[S \mid Y(p)=1] \le p E [ S ∣ Y ( p ) = 1 ] ≤ p , thus providing a uniform upper bound on α ( p ) \alpha(p) α ( p ) in terms of D S ( p ) D_S(p) D S ( p ) (a similar derivation holds for the buyer’s tail):
α ( p ) ( μ S − p ) 2 ≤ 2 σ S D S ( p ) ⟹ α ( p ) ≤ 2 σ S D S ( p ) ( μ S − p ) 2 . \alpha(p)(\mu_S-p)^2 \le2\sigma_SD_S(p) \;\Longrightarrow\; \alpha(p) \le\frac{2\sigma_SD_S(p)}{(\mu_S-p)^2}. α ( p ) ( μ S − p ) 2 ≤ 2 σ S D S ( p ) ⟹ α ( p ) ≤ ( μ S − p ) 2 2 σ S D S ( p ) .
(Tail Bound)
For ∣ p − μ S ∣ ≤ σ S / 3 |p-\mu_S|\le\sigma_S/3 ∣ p − μ S ∣ ≤ σ S /3 , consider the values of sellers who trade at p p p : they either lie within σ S / 3 \sigma_S/3 σ S /3 of their mean or fall below μ S − σ S / 3 \mu_S-\sigma_S/3 μ S − σ S /3 (and would also permit trade at price μ S − σ S / 3 \mu_S-\sigma_S/3 μ S − σ S /3 ). Trade at μ S − σ S / 3 \mu_S-\sigma_S/3 μ S − σ S /3 forces a conditional mean shift of at least σ S / 3 \sigma_S/3 σ S /3 , so the information identity controls these outliers’ contribution to the second moment. Thus either conditioning on trade at p p p substantially changes the mean or spread, or the outliers needed to preserve the spread provide information at μ S − σ S / 3 \mu_S-\sigma_S/3 μ S − σ S /3 . Combining the bounds from these two prices gives
α ( p ) ≤ 225 D ‾ 2 σ S . \alpha(p) \le\frac{225\overline{D}}{2\sigma_S}. α ( p ) ≤ 2 σ S 225 D .
(Close-to-mean Bound)
The buyer’s bound is symmetric. For values of p p p close to the average of μ S \mu_S μ S and μ B \mu_B μ B , we employ the trivial upper bound α ( p ) ≤ 1 \alpha(p)\le1 α ( p ) ≤ 1 . Integrating H ( p ) H(p) H ( p ) over R \mathbb{R} R provides the desired upper bound on G G G (and thus on L ( p ) L(p) L ( p ) ) in terms of D ‾ \overline{D} D . Integrating the tail bounds yields 6 D ‾ 6\overline{D} 6 D , while the close-to-mean regions have width 2 σ Z / 3 2\sigma_Z/3 2 σ Z /3 and height 225 D ‾ / ( 2 σ Z ) 225\overline{D}/(2\sigma_Z) 225 D / ( 2 σ Z ) , for a total area of 162 D ‾ 162\overline{D} 162 D . Finally, the central plateau has height one and length ( m − σ / 3 ) + (m-\sigma/3)_+ ( m − σ /3 ) + , hence
G ≤ ∫ R H ( p ) d p ≤ 162 D ‾ + ( m − σ / 3 ) + . G \le\int_{\mathbb{R}} H(p)\,\mathrm{d}p \le162\overline{D}+(m-\sigma/3)_+. G ≤ ∫ R H ( p ) d p ≤ 162 D + ( m − σ /3 ) + .
Since m ≤ G m\le G m ≤ G , this implies min { G , σ / 3 } ≤ 162 D ‾ \min\{G,\sigma/3\}\le162\overline{D} min { G , σ /3 } ≤ 162 D . Also, Cauchy–Schwarz gives G ≤ m + + σ < 4 σ G\le m_++\sigma<4\sigma G ≤ m + + σ < 4 σ , so
G ≤ 12 min { G , σ / 3 } ≤ 1944 D ‾ . G\le12\min\{G,\sigma/3\}\le1944\overline{D}. G ≤ 12 min { G , σ /3 } ≤ 1944 D .
If D ‾ = 0 \overline{D}=0 D = 0 , then G = 0 G=0 G = 0 and any price works. Otherwise, since 1944 < 2 11 1944<2^{11} 1944 < 2 11 , a price sufficiently close to maximizing D D D satisfies L ( p ) ≤ G < 2 11 D ( p ) L(p)\le G<2^{11}D(p) L ( p ) ≤ G < 2 11 D ( p ) .
Well-separated case (m ≥ 3 σ m\ge3\sigma m ≥ 3 σ ). In this case, the seller’s and buyer’s means are sufficiently far apart that we can post their midpoint as the price. A failed trade forces either S − μ S > m / 2 S-\mu_S>m/2 S − μ S > m /2 or μ B − B > m / 2 \mu_B-B>m/2 μ B − B > m /2 ; thus, conditional on rejection, the combined root-mean-square deviation is at least m / 2 ≥ 3 σ / 2 m/2\ge3\sigma/2 m /2 ≥ 3 σ /2 , compared with at most σ \sigma σ before conditioning. This increase requires changes in the conditional means or standard deviations. Their probability-weighted squared changes are bounded by 2 σ D ( p ) 2\sigma D(p) 2 σ D ( p ) , while the missed gain is controlled by the same valuation deviations. Comparing these bounds gives L ( p ) ≤ 41 D ( p ) L(p)\le41D(p) L ( p ) ≤ 41 D ( p ) . □
Our Bayesian algorithm posts the price supplied by the lemma.
Algorithm 3 Bayesian Contextual Bilateral Trade
Input: a known joint prior π \pi π on ( s , b ) (s,b) ( s , b ) with finite second moments. Initialize the posterior π 1 = π \pi_1=\pi π 1 = π . For t = 1 , 2 , … t=1,2,\ldots t = 1 , 2 , … :
Receive x t x_t x t and let π t \pi_t π t be the current posterior of ( s , b ) (s,b) ( s , b ) .
Apply Lemma 3.1 under π t \pi_t π t to S = x t T s S=x_t^\mathsf{T}s S = x t T s and B = x t T b B=x_t^\mathsf{T}b B = x t T b and post the resulting price p t p_t p t .
Observe Y t Y_t Y t and condition the joint posterior on this bit and the posted offer.
Theorem 3.2 (Bayesian Bilateral Trade). For every known joint prior π \pi π with finite second moments, Algorithm 3 satisfies the following bound at every horizon:
∑ t = 1 T E [ ℓ t ] ≤ 2 11 Ψ t r ( π ) . (18) \sum_{t=1}^{T}\mathbb{E}[\ell_t]\le2^{11}\Psi_{\mathrm{tr}}(\pi). \tag*{(18)} t = 1 ∑ T E [ ℓ t ] ≤ 2 11 Ψ tr ( π ) . (18)
Proof. Condition on the history and current context, and let π t + \pi_t^+ π t + be the posterior after the offer and trade bit. With D ( p t ) D(p_t) D ( p t ) evaluated under π t \pi_t π t , the price choice and Lemma 1.2 give
E t [ ℓ t ] ≤ 2 11 D ( p t ) ≤ 2 11 ( Ψ t r ( π t ) − E t Ψ t r ( π t + ) ) . (19) \mathbb{E}_t[\ell_t] \le2^{11}D(p_t) \le2^{11}\left(\Psi_{\mathrm{tr}}(\pi_t)-\mathbb{E}_t\Psi_{\mathrm{tr}}(\pi_t^+)\right). \tag*{(19)} E t [ ℓ t ] ≤ 2 11 D ( p t ) ≤ 2 11 ( Ψ tr ( π t ) − E t Ψ tr ( π t + ) ) . (19)
The second inequality applies the directional comparison of Lemma 1.2 to each marginal. It holds for any observed signal, including a trade bit that depends on both agents. By the context assumption in § 1.4 , the next context supplies no additional information about the hidden pair. Taking expectations and telescoping therefore yields
∑ t = 1 T E [ ℓ t ] ≤ 2 11 ( Ψ t r ( π ) − E [ Ψ t r ( π T + ) ] ) ≤ 2 11 Ψ t r ( π ) . \sum_{t=1}^{T}\mathbb{E}[\ell_t]\le2^{11}\left(\Psi_{\mathrm{tr}}(\pi)-\mathbb{E}\left[\Psi_{\mathrm{tr}}(\pi_T^+)\right]\right)\le2^{11}\Psi_{\mathrm{tr}}(\pi). t = 1 ∑ T E [ ℓ t ] ≤ 2 11 ( Ψ tr ( π ) − E [ Ψ tr ( π T + ) ] ) ≤ 2 11 Ψ tr ( π ) .
The common price ensures per-round budget balance. The normalized bounds follow from (14).
Adversarial Contextual Bilateral Trade
In the adversarial setting, no prior is given, and the hidden pair is fixed: w = ( s , b ) ∈ K = B d 2 × B d 2 \boldsymbol{w}=(\boldsymbol{s},\boldsymbol{b})\in K=\mathbb{B}_d^2\times\mathbb{B}_d^2 w = ( s , b ) ∈ K = B d 2 × B d 2 . Our algorithm maintains a center m = ( m S , m B ) ∈ R 2 d \boldsymbol{m}=(m_S,m_B)\in\mathbb{R}^{2d} m = ( m S , m B ) ∈ R 2 d and a block-diagonal positive-definite matrix R = diag ( R S , R B ) ∈ R 2 d × 2 d R=\operatorname{diag}(R_S,R_B)\in\mathbb{R}^{2d\times2d} R = diag ( R S , R B ) ∈ R 2 d × 2 d , where both R S R_S R S and R B R_B R B belong to R d × d \mathbb{R}^{d\times d} R d × d . These three quantities induce the same potential as in search, but in dimension 2 d 2d 2 d :
Φ ( m , R , w ) = Tr R + ( w − m ) ⊤ R − 1 ( w − m ) = Φ ( m S , R S , s ) + Φ ( m B , R B , b ) . (20) \Phi(\boldsymbol{m},R,\boldsymbol{w})=\operatorname{Tr}R+(\boldsymbol{w}-\boldsymbol{m})^\top R^{-1}(\boldsymbol{w}-\boldsymbol{m})=\Phi(m_S,R_S,\boldsymbol{s})+\Phi(m_B,R_B,\boldsymbol{b}). \tag*{(20)} Φ ( m , R , w ) = Tr R + ( w − m ) ⊤ R − 1 ( w − m ) = Φ ( m S , R S , s ) + Φ ( m B , R B , b ) . (20)
Note that the learner never evaluates the potential at the unknown pair w \boldsymbol{w} w . In each time step, our algorithm designs a suitable plan , which specifies an offer p p p and two successor states ( m ( 0 ) , R ( 0 ) ) (\boldsymbol{m}^{(0)},R^{(0)}) ( m ( 0 ) , R ( 0 ) ) and ( m ( 1 ) , R ( 1 ) ) (\boldsymbol{m}^{(1)},R^{(1)}) ( m ( 1 ) , R ( 1 ) ) , one for each possible feedback bit. Let m + , R + \boldsymbol{m}^+,R^+ m + , R + denote the random successor state induced by the observed feedback. Ideally, we would like to find a plan that balances decreasing the expected potential at ( m + , R + , w ) (\boldsymbol{m}^+,R^+,\boldsymbol{w}) ( m + , R + , w ) and incurring little regret ℓ ( w ) \ell(\boldsymbol{w}) ℓ ( w ) . The following lemma shows that there exists a lottery over prices (i.e., a randomized plan) that ensures this property, up to some slack.
Lemma 3.3 (A valid lottery exists). For every m ∈ R 2 d m \in\mathbb{R}^{2d} m ∈ R 2 d , every block-diagonal R ≻ 0 R \succ0 R ≻ 0 , every context x x x with ∥ x ∥ 2 ≤ 1 \lVert x\rVert_2 \le1 ∥ x ∥ 2 ≤ 1 , and every γ ∈ ( 0 , 1 ] \gamma\in(0,1] γ ∈ ( 0 , 1 ] , there is a finite lottery of plans satisfying
E [ ℓ ( w ) + 2 10 Φ ( m + , R + , w ) ] ≤ 2 10 Φ ( m , R , w ) + γ for every w ∈ K . (21) \mathbb{E}\left[\ell(w)+2^{10}\Phi(m^{+},R^{+},w)\right]\le2^{10}\Phi(m,R,w)+\gamma\qquad\text{for every }w\in K. \tag*{(21)} E [ ℓ ( w ) + 2 10 Φ ( m + , R + , w ) ] ≤ 2 10 Φ ( m , R , w ) + γ for every w ∈ K . (21) Each plan in the lottery posts the same price, drawn from a finite grid, to both agents. The lottery can be chosen as a function of the state and context.
Note that the expectation in the lemma is only over the lottery, and the successor is selected using the bit generated by the sampled plan. For a given slack γ ∈ ( 0 , 1 ] \gamma\in(0,1] γ ∈ ( 0 , 1 ] , the lottery must satisfy the one-round bound in (21), which balances incurred regret against the decrease in the (unknown) potential and must hold for all possible hidden pairs. We provide here a proof sketch of the lottery lemma, and defer the detailed proof to Appendix § 10 .§ 2 .
Proof sketch. The goal is to show that, for every fixed current state and context, we can first construct a good plan for each hypothetical prior, and then use minimax to obtain one lottery that works for every hidden pair. A plan a a a consists of a common price and two successor states, one for rejection and one for trade, all fixed before observing the bit. A lottery Q Q Q is a probability distribution over plans: the learner samples a plan, posts its price, and keeps the successor selected by the observed bit. We seek to find such a lottery and to ensure that it has finite support.
Let us write Φ 0 ( w ) = Φ ( m , R , w ) \Phi_0(w)=\Phi(m,R,w) Φ 0 ( w ) = Φ ( m , R , w ) for the current quadratic potential from (6) , and Φ a + ( w ) \Phi_a^{+}(w) Φ a + ( w ) for the successor quadratic potential selected when the hidden pair is w w w . Moreover, let us define the excess cost
f a ( w ) = ℓ a ( w ) + 2 10 Φ a + ( w ) − 2 10 Φ 0 ( w ) , (Excess cost) f_a(w)=\ell_a(w)+2^{10}\Phi_a^{+}(w)-2^{10}\Phi_0(w), \qquad\text{(Excess cost)} f a ( w ) = ℓ a ( w ) + 2 10 Φ a + ( w ) − 2 10 Φ 0 ( w ) , (Excess cost)
where ℓ a \ell_a ℓ a is the lost gain under plan a a a . The required inequality is therefore E a ∼ Q [ f a ( w ) ] ≤ γ \mathbb{E}_{a\sim Q}[f_a(w)]\le\gamma E a ∼ Q [ f a ( w )] ≤ γ for every w ∈ K w\in K w ∈ K . Indeed, f a f_a f a is the loss plus the scaled successor potential minus the scaled current potential, so this is exactly (21).
A plan for each prior.* Temporarily suppose that the hidden pair W W W is sampled from a known prior π \pi π on K K K . Lemma 3.1, together with the directional comparison of Lemma 1.2, supplies a common price p p p satisfying
L ( p ) ≤ 2 11 ( Ψ t r ( π ) − P π ( Y ( p ) = 0 ) Ψ t r ( π 0 ) − P π ( Y ( p ) = 1 ) Ψ t r ( π 1 ) ) , (Bayesian bound) L(p)\le2^{11}\left(\Psi_{\mathrm{tr}}(\pi)-\mathbb{P}_{\pi}(Y(p)=0)\Psi_{\mathrm{tr}}(\pi_0)-\mathbb{P}_{\pi}(Y(p)=1)\Psi_{\mathrm{tr}}(\pi_1)\right), \qquad\text{(Bayesian bound)} L ( p ) ≤ 2 11 ( Ψ tr ( π ) − P π ( Y ( p ) = 0 ) Ψ tr ( π 0 ) − P π ( Y ( p ) = 1 ) Ψ tr ( π 1 ) ) , (Bayesian bound)
where π y = L π ( W ∣ Y ( p ) = y ) \pi_y=\mathcal{L}_{\pi}(W\mid Y(p)=y) π y = L π ( W ∣ Y ( p ) = y ) is the posterior after observing bit y y y . Thus the scaled prior potential covers both the expected loss and the scaled posterior potential remaining after the bit. We want to replace these potentials by the quadratic potentials of the current and successor states.
For each bit, choose the posterior mean as the successor center and the square roots of the posterior marginal covariances as the matrix blocks, adding λ I d \lambda I_d λ I d before taking the roots to ensure positive definiteness. These choices define a plan a λ a_\lambda a λ . We stress that both successors are fixed before posting the price, and the observed bit only selects which successor is kept. The variational identity (6) gives
E π [ Φ 0 ( W ) ] ≥ 2 Ψ t r ( π ) , \mathbb{E}_{\pi}\left[\Phi_0(W)\right]\ge2\Psi_{\mathrm{tr}}(\pi), E π [ Φ 0 ( W ) ] ≥ 2 Ψ tr ( π ) ,
lim λ → 0 + E π [ Φ a λ + ( W ) ] = 2 ( P π ( Y ( p ) = 0 ) Ψ t r ( π 0 ) + P π ( Y ( p ) = 1 ) Ψ t r ( π 1 ) ) , (Potential bounds) \lim_{\lambda\to0+}\mathbb{E}_{\pi}\left[\Phi_{a_\lambda}^{+}(W)\right]
=2\left(\mathbb{P}_{\pi}(Y(p)=0)\Psi_{\mathrm{tr}}(\pi_0)+\mathbb{P}_{\pi}(Y(p)=1)\Psi_{\mathrm{tr}}(\pi_1)\right), \qquad\text{(Potential bounds)} λ → 0 + lim E π [ Φ a λ + ( W ) ] = 2 ( P π ( Y ( p ) = 0 ) Ψ tr ( π 0 ) + P π ( Y ( p ) = 1 ) Ψ tr ( π 1 ) ) , (Potential bounds)
Combining these comparisons with the Bayesian bound cancels the posterior terms:
inf a E π [ f a ( W ) ] ≤ lim λ → 0 + E π [ f a λ ( W ) ] \inf_a\mathbb{E}_{\pi}[f_a(W)]
\le\lim_{\lambda\to0+}\mathbb{E}_{\pi}[f_{a_\lambda}(W)] a inf E π [ f a ( W )] ≤ λ → 0 + lim E π [ f a λ ( W )]
≤ 2 11 Ψ t r ( π ) − 2 10 E π [ Φ 0 ( W ) ] ≤ 0. (Average bound) \le2^{11}\Psi_{\mathrm{tr}}(\pi)-2^{10}\mathbb{E}_{\pi}\left[\Phi_0(W)\right]\le0. \qquad\text{(Average bound)} ≤ 2 11 Ψ tr ( π ) − 2 10 E π [ Φ 0 ( W ) ] ≤ 0. (Average bound)
We have therefore constructed plans with arbitrarily small average excess cost for every prior, although the plans may depend on that prior.
One lottery for every hidden pair. It remains to turn a suitable plan for each prior into a single lottery that works for every hidden pair. The obstacle to applying minimax directly is that the trade bit jumps when a valuation crosses the posted price. In the analysis, we slightly contract the hidden pair toward the origin and add a small common random shift to both valuations. The contraction keeps the perturbed pair in K K K , while averaging over the shift makes the expected cost continuous. Corresponding changes to the price and successor states preserve the averaged bound up to a uniformly vanishing error. We then apply Claim D.5 together with Sion’s minimax theorem (Theorem D.6 [22 ] ) to these continuous costs and then let the perturbation vanish, giving
inf Q ∈ Q sup w ∈ K E a ∼ Q [ f a ( w ) ] = sup ρ ∈ P ( K ) inf a E ρ [ f a ( W ) ] ≤ 0. \inf_{Q \in\mathcal{Q}} \sup_{w \in K} \mathbb{E}_{a \sim Q}[f_a(w)] = \sup_{\rho\in\mathcal{P}(K)} \inf_a \mathbb{E}_{\rho}[f_a(W)] \le0. Q ∈ Q inf w ∈ K sup E a ∼ Q [ f a ( w )] = ρ ∈ P ( K ) sup a inf E ρ [ f a ( W )] ≤ 0.
Above, we write P ( K ) \mathcal{P}(K) P ( K ) for the set of all probability measures on K K K , representing the possible prior distributions of the hidden pair. At this point, Q Q Q ranges over arbitrary lotteries, not necessarily with finite support. Since the minimax value is at most zero, we can find a lottery with excess cost below any positive tolerance. We choose γ / 3 \gamma/3 γ /3 , leaving the remaining 2 γ / 3 2\gamma/3 2 γ /3 for the price and successor-state approximations below. Consequently, there is a lottery satisfying
sup w ∈ K E a ∼ Q [ f a ( w ) ] < γ 3 . \sup_{w \in K} \mathbb{E}_{a \sim Q}[f_a(w)] < \frac{\gamma}{3}. w ∈ K sup E a ∼ Q [ f a ( w )] < 3 γ .
This bound holds for every fixed hidden pair, with expectation only over the sampled plan.
A finite lottery. The same claim lets us choose Q Q Q with a bounded price density and compact ranges of prices and successor states. Using this regularity and compactness, we round prices to a finite grid and approximate successor states by a finite net, making each error smaller than γ / 3 \gamma/3 γ /3 . Thus, the resulting lottery has finite support and satisfies the required bound with slack γ \gamma γ .
The detailed proof is deferred to Appendix § 10 .§ 2 .
Algorithm 4 Adversarial Contextual Bilateral Trade
Initialize m 1 = 0 ∈ R 2 d \mathbf{m}_1 = 0 \in\mathbb{R}^{2d} m 1 = 0 ∈ R 2 d and R 1 = I 2 d / d R_1 = I_{2d}/\sqrt{d} R 1 = I 2 d / d .
For t = 1 , 2 , … t = 1,2,\ldots t = 1 , 2 , … :
Receive x t \mathbf{x}_t x t and set γ t = 1 t ( t + 1 ) \gamma_t = \frac{1}{t(t+1)} γ t = t ( t + 1 ) 1 .
Choose a lottery of plans as in Lemma 3.3 with current state ( m t , R t ) (\mathbf{m}_t, R_t) ( m t , R t ) , context x t \mathbf{x}_t x t , and slack γ t \gamma_t γ t .
Draw a plan from the finite lottery and post its price p t p_t p t .
Observe Y t Y_t Y t and retain the plan’s successor state for that bit as ( m t + 1 , R t + 1 ) (\mathbf{m}_{t+1}, R_{t+1}) ( m t + 1 , R t + 1 ) .
The algorithm uses only its state, the current context, its own randomization, and the observed bit. It needs neither a prior nor a horizon. We do not claim an efficient implementation of the optimization in step 2.
Theorem 3.4 (Adversarial Bilateral Trade). For every fixed w ∈ K \mathbf{w} \in K w ∈ K , every admissible adaptive context strategy with ∥ x t ∥ 2 ≤ 1 \lVert\mathbf{x}_t\rVert_2 \le1 ∥ x t ∥ 2 ≤ 1 , and every horizon T T T , Algorithm 4 satisfies
∑ t = 1 T E [ ∣ ℓ t ∣ ] ≤ 2 12 d + 1. (22) \sum_{t=1}^{T} \mathbb{E}[\lvert\ell_t\rvert] \le2^{12}\sqrt{d}+1. \tag*{(22)} t = 1 ∑ T E [∣ ℓ t ∣] ≤ 2 12 d + 1. (22)
Proof. Fix w = ( s , b ) ∈ K w=(s,b)\in K w = ( s , b ) ∈ K and write Φ t = Φ ( m t , R t , w ) \Phi_t=\Phi(m_t,R_t,w) Φ t = Φ ( m t , R t , w ) . Lemma 3.3 guarantees the existence of the lottery required by Algorithm 4 at every round. Conditional on the observed history and current context, before the lottery is drawn, (21) gives
E t [ ℓ t ] + 2 10 E t [ Φ t + 1 ] ≤ 2 10 Φ t + γ t . \mathbb{E}_t[\ell_t]+2^{10}\mathbb{E}_t[\Phi_{t+1}]\le2^{10}\Phi_t+\gamma_t. E t [ ℓ t ] + 2 10 E t [ Φ t + 1 ] ≤ 2 10 Φ t + γ t .
Since Φ 1 \Phi_1 Φ 1 is finite and all losses and potentials are nonnegative, this inequality also establishes their integrability inductively. Taking full expectations and summing over t = 1 , … , T t=1,\ldots,T t = 1 , … , T telescopes the potential terms:
∑ t = 1 T E [ ℓ t ] + 2 10 E [ Φ T + 1 ] ≤ 2 10 Φ 1 + ∑ t = 1 T γ t . \sum_{t=1}^{T}\mathbb{E}[\ell_t]+2^{10}\mathbb{E}[\Phi_{T+1}]\le2^{10}\Phi_1+\sum_{t=1}^{T}\gamma_t. t = 1 ∑ T E [ ℓ t ] + 2 10 E [ Φ T + 1 ] ≤ 2 10 Φ 1 + t = 1 ∑ T γ t .
The chosen slacks have total sum at most one, because
∑ t = 1 T γ t = ∑ t = 1 T 1 t ( t + 1 ) = ∑ t = 1 T ( 1 t − 1 t + 1 ) = 1 − 1 T + 1 < 1. \sum_{t=1}^{T}\gamma_t=\sum_{t=1}^{T}\frac{1}{t(t+1)}=\sum_{t=1}^{T}\left(\frac{1}{t}-\frac{1}{t+1}\right)=1-\frac{1}{T+1}<1. t = 1 ∑ T γ t = t = 1 ∑ T t ( t + 1 ) 1 = t = 1 ∑ T ( t 1 − t + 1 1 ) = 1 − T + 1 1 < 1.
Finally, the initialization and ∥ s ∥ 2 , ∥ b ∥ 2 ≤ 1 \lVert s\rVert_2,\lVert b\rVert_2\le1 ∥ s ∥ 2 , ∥ b ∥ 2 ≤ 1 give
Φ 1 = Φ ( 0 , I 2 d / d , w ) = 2 d + d ( ∥ s ∥ 2 2 + ∥ b ∥ 2 2 ) ≤ 4 d . \Phi_1=\Phi(0,I_{2d}/\sqrt{d},w)=2\sqrt{d}+\sqrt{d}(\lVert s\rVert_2^2+\lVert b\rVert_2^2)\le4\sqrt{d}. Φ 1 = Φ ( 0 , I 2 d / d , w ) = 2 d + d (∥ s ∥ 2 2 + ∥ b ∥ 2 2 ) ≤ 4 d .
Substituting these two bounds proves (22) .
Acknowledgment
Federico Fusco, Stefano Leonardi, and Matteo Russo acknowledge OpenAI for providing complimentary access through the ChatGPT for Academic Researchers program. The work of Federico Fusco and Stefano Leonardi is partly supported by AI-PHOQUS PNR RIC 2021-2027, co-financed by EU Italian Ministry MIMIT and MUR. Anupam Gupta was supported in part by NSF awards CCF-2422926 and CCF-2608359.
Disclosure of AI Usage
The first proof of O ( d ) O(\sqrt{d}) O ( d ) regret for the adversarial version of contextual bilateral trade was suggested by GPT-6 Astra in conversations with the authors. Subsequently, we dedicated considerable effort to simplifying the proofs, to understanding and interpreting the potential Φ \Phi Φ used in the proof, to exploring the (somewhat simpler) setting of contextual search, to identifying concrete connections between the Bayesian and adversarial versions of both problems, and to investigating a Gaussian setting of contextual search, which led to interpreting the parameters of the algorithm as posterior mean and covariance proxies. The authors have substantially rewritten the proofs (albeit with some help from Gemini, Claude, and ChatGPT) and take full responsibility for the content of this work.
All the proofs have been formalized in Lean4 and can be found at this url.
Appendix
Notation
We summarize the main notations used in the paper in the table below. We generally use bold symbols for d d d -dimensional vectors, capital Roman letters for matrices and scalar random variables, and Greek letters for distributional quantities (such as moments) and potentials. Time dependence is usually indicated by a subscript; for example, Ψ t = Ψ ( Σ t ) \Psi_t = \Psi(\Sigma_t) Ψ t = Ψ ( Σ t ) denotes the potential at the t t t -th round.
Table 3.
Concavity of the Gap Function
This appendix proves the concavity and monotonicity of the gap function g x g_{\mathbf{x}} g x used in Lemma 1.2 . We do so by expressing g x g_{\mathbf{x}} g x as an infimum of affine functions with positive-semidefinite slopes.
Lemma B.1 (Gap representation and directional comparison). Fix x ∈ R d \mathbf{x} \in\mathbb{R}^{d} x ∈ R d with ∥ x ∥ 2 ≤ 1 \lVert\mathbf{x}\rVert_{2} \le1 ∥ x ∥ 2 ≤ 1 and define, for Σ ⪰ 0 \Sigma\succeq0 Σ ⪰ 0 ,
g x ( Σ ) = Tr Σ − x T Σ x . (23) g_{\mathbf{x}}(\Sigma) = \operatorname{Tr}\sqrt{\Sigma} - \sqrt{\mathbf{x}^{\mathsf{T}}\Sigma\mathbf{x}}. \tag*{(23)} g x ( Σ ) = Tr Σ − x T Σ x . (23) The function g x g_{\mathbf{x}} g x admits the affine representation
2 g x ( Σ ) = inf R ≻ 0 { Tr R − ∥ R x ∥ 2 + Tr [ ( R − 1 − x x T ∥ R x ∥ 2 2 ) Σ ] } . (24) 2g_{\mathbf{x}}(\Sigma) = \inf_{R \succ0} \left\{ \operatorname{Tr} R - \lVert R\mathbf{x}\rVert_{2} + \operatorname{Tr}\left[\left(R^{-1} - \frac{\mathbf{x}\mathbf{x}^{\mathsf{T}}}{\lVert R\mathbf{x}\rVert_{2}^{2}}\right)\Sigma\right] \right\}. \tag*{(24)} 2 g x ( Σ ) = R ≻ 0 inf { Tr R − ∥ R x ∥ 2 + Tr [ ( R − 1 − ∥ R x ∥ 2 2 x x T ) Σ ] } . (24) Here x x T / ∥ R x ∥ 2 2 \mathbf{x}\mathbf{x}^{\mathsf{T}}/\lVert R\mathbf{x}\rVert_{2}^{2} x x T / ∥ R x ∥ 2 2 is defined to be zero when x = 0 \mathbf{x}=0 x = 0 . If Σ ≻ 0 \Sigma\succ0 Σ ≻ 0 , the infimum is attained at R = Σ 1 / 2 R=\Sigma^{1/2} R = Σ 1/2 .
Each function inside the infimum in (24) is affine in Σ \Sigma Σ and has positive-semidefinite slope. Consequently, g x g_x g x is concave as a pointwise infimum of affine functions, and it is nondecreasing in the positive semidefinite order. Applied to E t [ Σ t + 1 ] ⪯ Σ t \mathbb{E}_t[\Sigma_{t+1}] \preceq\Sigma_t E t [ Σ t + 1 ] ⪯ Σ t in the Bayesian search model, the lemma thus implies
Ψ t − E t [ Ψ t + 1 ] ≥ σ t − E t [ σ t ′ ] . (25) \Psi_t-\mathbb{E}_t[\Psi_{t+1}] \ge\sigma_t-\mathbb{E}_t[\sigma'_t]. \tag*{(25)} Ψ t − E t [ Ψ t + 1 ] ≥ σ t − E t [ σ t ′ ] . (25)
Proof of Lemma B.1. Fix R ≻ 0 R \succ0 R ≻ 0 and put T = Σ 1 / 2 T=\Sigma^{1/2} T = Σ 1/2 , M = ( T − R ) 2 ⪰ 0 M=(T-R)^2 \succeq0 M = ( T − R ) 2 ⪰ 0 , r = ∥ R x ∥ 2 r=\lVert Rx\rVert_2 r = ∥ R x ∥ 2 , and σ = ∥ T x ∥ 2 \sigma=\lVert Tx\rVert_2 σ = ∥ T x ∥ 2 . Expanding the square and using cyclicity of the trace gives
Tr ( R − 1 M ) = Tr ( R − 1 Σ ) − 2 Tr T + Tr R . (26) \operatorname{Tr}(R^{-1}M)=\operatorname{Tr}(R^{-1}\Sigma)-2\operatorname{Tr}T+\operatorname{Tr}R. \tag*{(26)} Tr ( R − 1 M ) = Tr ( R − 1 Σ ) − 2 Tr T + Tr R . (26)
For x ≠ 0 x \ne0 x = 0 , Cauchy–Schwarz in the R R R -inner product, followed by x T R x ≤ ∥ x ∥ 2 ∥ R x ∥ 2 ≤ r x^{\mathsf T}Rx \le\lVert x\rVert_2\lVert Rx\rVert_2 \le r x T R x ≤ ∥ x ∥ 2 ∥ R x ∥ 2 ≤ r , yields
R − 1 ⪰ x x T x T R x ⪰ x x T r . R^{-1} \succeq\frac{xx^{\mathsf T}}{x^{\mathsf T}Rx} \succeq\frac{xx^{\mathsf T}}{r}. R − 1 ⪰ x T R x x x T ⪰ r x x T .
Thus H R = R − 1 − x x T / r ⪰ 0 H_R=R^{-1}-xx^{\mathsf T}/r \succeq0 H R = R − 1 − x x T / r ⪰ 0 , and the reverse triangle inequality gives
Tr ( R − 1 M ) ≥ x T M x r = ∥ ( T − R ) x ∥ 2 2 r ≥ ( σ − r ) 2 r . \operatorname{Tr}(R^{-1}M) \ge\frac{x^{\mathsf T}Mx}{r}=\frac{\lVert(T-R)x\rVert_2^2}{r}\ge\frac{(\sigma-r)^2}{r}. Tr ( R − 1 M ) ≥ r x T M x = r ∥( T − R ) x ∥ 2 2 ≥ r ( σ − r ) 2 .
Combining this inequality with (26) and rearranging proves
2 Tr T − 2 σ ≤ Tr R − r + Tr ( H R Σ ) . (27) 2\operatorname{Tr}T-2\sigma\le\operatorname{Tr}R-r+\operatorname{Tr}(H_R\Sigma). \tag*{(27)} 2 Tr T − 2 σ ≤ Tr R − r + Tr ( H R Σ ) . (27)
For x = 0 x=0 x = 0 , take H R = R − 1 H_R=R^{-1} H R = R − 1 ; the same bound follows directly from (26) . If Σ ≻ 0 \Sigma\succ0 Σ ≻ 0 , equality holds at R = T R=T R = T . For singular Σ \Sigma Σ , the same value is approached by R η = ( Σ + η I ) 1 / 2 R_\eta=(\Sigma+\eta I)^{1/2} R η = ( Σ + η I ) 1/2 as η → 0 + \eta\to0^+ η → 0 + .
Supporting Proofs for Contextual Search
We have deferred two proofs in § 2 : Lemma 2.2 in the Bayesian analysis and Lemma 2.5 in the worst-case analysis. Both rely on the same one-dimensional potential decrease, stated in Lemma C.1 below. We first establish this common inequality, then use it to complete the two proofs.
A One-Dimensional Potential Lemma
Lemma C.1 (One-dimensional potential decrease). For m , z ∈ R m,z\in\mathbb{R} m , z ∈ R and r > 0 r>0 r > 0 , define
φ ( m , r , z ) = r + ( m − z ) 2 r . \varphi(m,r,z)=r+\frac{(m-z)^2}{r}. φ ( m , r , z ) = r + r ( m − z ) 2 . Let ϵ \epsilon ϵ be uniform on { − 1 , 1 } \{-1,1\} { − 1 , 1 } , set
P = m + r 2 ϵ , Y = sign ( z − P ) , P=m+\frac{r}{2}\epsilon,\qquad Y=\operatorname{sign}(z-P), P = m + 2 r ϵ , Y = sign ( z − P ) , and define
m + = m + r Y 3 − ϵ Y , r + = 3 r 3 − ϵ Y . m^+=m+\frac{rY}{3-\epsilon Y},\qquad r^+=\frac{3r}{3-\epsilon Y}. m + = m + 3 − ϵ Y r Y , r + = 3 − ϵ Y 3 r . Then
φ ( m , r , z ) − E ϵ [ φ ( m + , r + , z ) ] ≥ 1 6 E ϵ [ ∣ z − P ∣ ] = 1 6 max { ∣ z − m ∣ , r 2 } . (28) \varphi(m,r,z)-\mathbb{E}_{\epsilon}\left[\varphi(m^+,r^+,z)\right]\ge\frac{1}{6}\mathbb{E}_{\epsilon}[|z-P|]=\frac{1}{6}\max\left\{|z-m|,\frac{r}{2}\right\}. \tag*{(28)} φ ( m , r , z ) − E ϵ [ φ ( m + , r + , z ) ] ≥ 6 1 E ϵ [ ∣ z − P ∣ ] = 6 1 max { ∣ z − m ∣ , 2 r } . (28) In particular,
E ϵ [ φ ( m + , r + , z ) ] ≤ φ ( m , r , z ) − r 12 . (29) \mathbb{E}_{\epsilon}\left[\varphi(m^+,r^+,z)\right]\le\varphi(m,r,z)-\frac{r}{12}. \tag*{(29)} E ϵ [ φ ( m + , r + , z ) ] ≤ φ ( m , r , z ) − 12 r . (29)
Proof. The identity for the expected loss follows by averaging over the two prices. We prove the potential bound by separating targets between the two prices from targets outside that interval, as illustrated in Figure 5 .
Figure 5. Prices and possible updated centers m + ∈ { m ± r / 4 , m ± r / 2 } m^+ \in\{m \pm r/4, m \pm r/2\} m + ∈ { m ± r /4 , m ± r /2 } in Lemma C.1 .
Interior: ∣ z − m ∣ < r / 2 |z-m| < r/2 ∣ z − m ∣ < r /2 . Both answers point inward, so ε Y = − 1 \varepsilon_Y=-1 ε Y = − 1 and r + = 3 r / 4 r^+=3r/4 r + = 3 r /4 . The new center is m + r / 4 m+r/4 m + r /4 or m − r / 4 m-r/4 m − r /4 , each with probability 1 / 2 1/2 1/2 . Thus
E ε [ ( m + − z ) 2 ] = ( m − z ) 2 + r 2 16 , \mathbb{E}_{\varepsilon}\left[(m^+-z)^2\right] = (m-z)^2+\frac{r^2}{16}, E ε [ ( m + − z ) 2 ] = ( m − z ) 2 + 16 r 2 ,
and
E ε [ φ ( m + , r + , z ) ] = 3 r 4 + 4 3 r ( ( m − z ) 2 + r 2 16 ) = φ ( m , r , z ) − r 4 + ( m − z ) 2 3 r + r 12 ≤ φ ( m , r , z ) − r 12 . \begin{aligned}
\mathbb{E}_{\varepsilon}\left[\varphi(m^+,r^+,z)\right]
&=\frac{3r}{4}+\frac{4}{3r}\left((m-z)^2+\frac{r^2}{16}\right)\\
&=\varphi(m,r,z)-\frac{r}{4}+\frac{(m-z)^2}{3r}+\frac{r}{12}
\leq\varphi(m,r,z)-\frac{r}{12}.
\end{aligned} E ε [ φ ( m + , r + , z ) ] = 4 3 r + 3 r 4 ( ( m − z ) 2 + 16 r 2 ) = φ ( m , r , z ) − 4 r + 3 r ( m − z ) 2 + 12 r ≤ φ ( m , r , z ) − 12 r .
Here E ε [ ∣ z − P ∣ ] = r / 2 \mathbb{E}_{\varepsilon}[|z-P|]=r/2 E ε [ ∣ z − P ∣ ] = r /2 , proving (28) in this case.
Exterior: ∣ z − m ∣ > r / 2 |z-m|>r/2 ∣ z − m ∣ > r /2 . By reflection, it suffices to consider z > m + r / 2 z>m+r/2 z > m + r /2 . Both prices yield the answer Y = 1 Y=1 Y = 1 , and the two equally likely successor states are
( m + , r + ) = ( m + r / 4 , 3 r / 4 ) and ( m + r / 2 , 3 r / 2 ) . (m^+,r^+)=(m+r/4,3r/4)\quad\text{and}\quad(m+r/2,3r/2). ( m + , r + ) = ( m + r /4 , 3 r /4 ) and ( m + r /2 , 3 r /2 ) .
Consequently,
E ε [ r + ] = 9 r 8 , \mathbb{E}_{\varepsilon}[r^+]=\frac{9r}{8}, E ε [ r + ] = 8 9 r ,
and
E ε [ ( z − m + ) 2 r + ] = 1 2 ( z − m − r / 4 ) 2 3 r / 4 + 1 2 ( z − m − r / 2 ) 2 3 r / 2 = ( z − m ) 2 r − 2 3 ( z − m ) + r 8 . \begin{aligned}
\mathbb{E}_{\varepsilon}\left[\frac{(z-m^+)^2}{r^+}\right]
&=\frac{1}{2}\frac{(z-m-r/4)^2}{3r/4}+\frac{1}{2}\frac{(z-m-r/2)^2}{3r/2}\\
&=\frac{(z-m)^2}{r}-\frac{2}{3}(z-m)+\frac{r}{8}.
\end{aligned} E ε [ r + ( z − m + ) 2 ] = 2 1 3 r /4 ( z − m − r /4 ) 2 + 2 1 3 r /2 ( z − m − r /2 ) 2 = r ( z − m ) 2 − 3 2 ( z − m ) + 8 r .
Adding the two terms and using z − m ≥ r / 2 z-m\geq r/2 z − m ≥ r /2 gives
E ε [ φ ( m + , r + , z ) ] = φ ( m , r , z ) + r 4 − 2 3 ( z − m ) ≤ φ ( m , r , z ) − 1 6 ( z − m ) . \mathbb{E}_{\varepsilon}\left[\varphi(m^+,r^+,z)\right]
=\varphi(m,r,z)+\frac{r}{4}-\frac{2}{3}(z-m)
\leq\varphi(m,r,z)-\frac{1}{6}(z-m). E ε [ φ ( m + , r + , z ) ] = φ ( m , r , z ) + 4 r − 3 2 ( z − m ) ≤ φ ( m , r , z ) − 6 1 ( z − m ) .
Since E ε [ ∣ z − P ∣ ] = z − m \mathbb{E}_{\varepsilon}[|z-P|]=z-m E ε [ ∣ z − P ∣ ] = z − m , this proves the claim for exterior targets.
Boundary: ∣ z − m ∣ = r / 2 |z-m|=r/2 ∣ z − m ∣ = r /2 . Our convention sign ( 0 ) = 1 \operatorname{sign}(0)=1 sign ( 0 ) = 1 gives one inward and one outward update when z = m + r / 2 z=m+r/2 z = m + r /2 , as in the exterior calculation. When z = m − r / 2 z=m-r/2 z = m − r /2 , both updates are inward, as in the interior calculation. Substituting into the corresponding expressions gives a decrease of exactly r / 12 r/12 r /12 in either case, while the expected loss is r / 2 r/2 r /2 . This proves (28) at both endpoints. Finally, the expected loss is always at least r / 2 r/2 r /2 , which implies (29) .
Proof of Lemma 2.2
Lemma 2.2 (One-bit deviation contraction). Let Z Z Z be a square-integrable real random variable, with μ = E [ Z ] \mu=\mathbb{E}[Z] μ = E [ Z ] and σ = sd ( Z ) \sigma=\operatorname{sd}(Z) σ = sd ( Z ) . Let ε \varepsilon ε be uniform on { − 1 , 1 } \{-1,1\} { − 1 , 1 } and independent of Z Z Z . Define
P = μ + σ 2 ε , Y = sign ( Z − P ) . P=\mu+\frac{\sigma}{2}\varepsilon,\qquad Y=\operatorname{sign}(Z-P). P = μ + 2 σ ε , Y = sign ( Z − P ) . Writing the posterior standard deviation as σ ′ = sd ( Z ∣ P , Y ) \sigma'=\operatorname{sd}(Z\mid P,Y) σ ′ = sd ( Z ∣ P , Y ) , we have E [ σ ′ ] ≤ 23 24 σ \mathbb{E}[\sigma']\leq\frac{23}{24}\sigma E [ σ ′ ] ≤ 24 23 σ .
Proof of Lemma 2.2. If σ = 0 \sigma=0 σ = 0 , then Z = μ Z=\mu Z = μ almost surely and σ ′ = 0 \sigma'=0 σ ′ = 0 , so the result is immediate. Assume σ > 0 \sigma>0 σ > 0 . For any mean proxy m ∈ R m\in\mathbb{R} m ∈ R and deviation proxy r > 0 r>0 r > 0 ,
2 sd ( Z ) ≤ 2 E [ ( Z − m ) 2 ] ≤ r + E [ ( Z − m ) 2 ] r = E [ φ ( m , r , Z ) ] . (30) 2\operatorname{sd}(Z)\leq2\sqrt{\mathbb{E}[(Z-m)^2]}\leq r+\frac{\mathbb{E}[(Z-m)^2]}{r}=\mathbb{E}[\varphi(m,r,Z)]. \tag*{(30)} 2 sd ( Z ) ≤ 2 E [( Z − m ) 2 ] ≤ r + r E [( Z − m ) 2 ] = E [ φ ( m , r , Z )] . (30)
Equality holds at m = μ m=\mu m = μ and r = σ r=\sigma r = σ . We apply this bound conditionally after observing the price and answer, with the proxies
m + = μ + σ Y 3 − ε Y , r + = 3 σ 3 − ε Y . m^+=\mu+\frac{\sigma Y}{3-\varepsilon Y},\qquad r^+=\frac{3\sigma}{3-\varepsilon Y}. m + = μ + 3 − ε Y σ Y , r + = 3 − ε Y 3 σ .
Because σ > 0 \sigma>0 σ > 0 , the sign ε \varepsilon ε is determined by P P P , so these proxies are ( P , Y ) (P,Y) ( P , Y ) -measurable. Applying (30) to the conditional law yields
2 σ ′ ≤ E [ φ ( m + , r + , Z ) ∣ P , Y ] , 2 E [ σ ′ ] ≤ E [ φ ( m + , r + , Z ) ] . 2\sigma'\leq\mathbb{E}[\varphi(m^+,r^+,Z)\mid P,Y],\qquad2\mathbb{E}[\sigma']\leq\mathbb{E}[\varphi(m^+,r^+,Z)]. 2 σ ′ ≤ E [ φ ( m + , r + , Z ) ∣ P , Y ] , 2 E [ σ ′ ] ≤ E [ φ ( m + , r + , Z )] .
For each fixed Z = z Z=z Z = z , Lemma C.1 with m = μ m=\mu m = μ and r = σ r=\sigma r = σ gives
E [ φ ( m + , r + , Z ) ∣ Z = z ] ≤ φ ( μ , σ , z ) − σ 12 . \mathbb{E}[\varphi(m^+,r^+,Z)\mid Z=z]\leq\varphi(\mu,\sigma,z)-\frac{\sigma}{12}. E [ φ ( m + , r + , Z ) ∣ Z = z ] ≤ φ ( μ , σ , z ) − 12 σ .
Averaging over Z Z Z and using E [ φ ( μ , σ , Z ) ] = 2 σ \mathbb{E}[\varphi(\mu,\sigma,Z)]=2\sigma E [ φ ( μ , σ , Z )] = 2 σ gives
2 E [ σ ′ ] ≤ 2 σ − σ 12 = 23 12 σ . 2\mathbb{E}[\sigma']\leq2\sigma-\frac{\sigma}{12}=\frac{23}{12}\sigma. 2 E [ σ ′ ] ≤ 2 σ − 12 σ = 12 23 σ .
Division by two proves the lemma.
Proof of Lemma 2.5
Lemma 2.5 (One-round potential decrease). On every round of Algorithm 2 ,
E t [ ℓ t ] ≤ 6 ( Φ t − E t [ Φ t + 1 ] ) . (31) \mathbb{E}_t[\ell_t]\leq6(\Phi_t-\mathbb{E}_t[\Phi_{t+1}]). \tag*{(31)} E t [ ℓ t ] ≤ 6 ( Φ t − E t [ Φ t + 1 ]) . (31)
Proof of Lemma 2.5. For x t = 0 x_t=0 x t = 0 , the loss and potential change are both zero. Otherwise, condition on the history and current context, suppress time subscripts, and put
m = x T m , z = x T z , u = R x , a = x T R x , r = ∥ R x ∥ 2 . m=x^{\mathsf{T}}m,\qquad z=x^{\mathsf{T}}z,\qquad u=Rx,\qquad a=x^{\mathsf{T}}Rx,\qquad r=\lVert Rx\rVert_2. m = x T m , z = x T z , u = R x , a = x T R x , r = ∥ R x ∥ 2 .
Since R ≻ 0 \mathcal{R} \succ0 R ≻ 0 and ∥ x ∥ 2 ≤ 1 \lVert x\rVert_2 \le1 ∥ x ∥ 2 ≤ 1 , we have
0 < a = x T u ≤ ∥ x ∥ 2 ∥ u ∥ 2 ≤ r . (32) 0 < a = x^{\mathsf{T}}u \le\lVert x\rVert_2\lVert u\rVert_2 \le r. \tag*{(32)} 0 < a = x T u ≤ ∥ x ∥ 2 ∥ u ∥ 2 ≤ r . (32)
For a realization of the random sign and the answer, let m + , R + m_{+},R_{+} m + , R + be the updated state. The update formulas imply
m + = x T m + = m + Y r 3 − ε Y , R + x = 3 3 − ε Y R x , r + = ∥ R + x ∥ 2 = 3 r 3 − ε Y . m^{+}=x^{\mathsf{T}}m_{+}=m+\frac{Yr}{3-\varepsilon Y}, \qquad R_{+}x=\frac{3}{3-\varepsilon Y}Rx, \qquad r^{+}=\lVert R_{+}x\rVert_2=\frac{3r}{3-\varepsilon Y}. m + = x T m + = m + 3 − ε Y Y r , R + x = 3 − ε Y 3 R x , r + = ∥ R + x ∥ 2 = 3 − ε Y 3 r .
Thus m + , r + m^{+},r^{+} m + , r + are exactly the successor quantities in Lemma C.1 .
We first prove the identity
Φ ( m + , R + , z ) − Φ ( m , R , z ) = r a ( φ ( m + , r + , z ) − φ ( m , r , z ) ) . (33) \Phi(m_{+},R_{+},z)-\Phi(m,R,z)=\frac{r}{a}\left(\varphi(m^{+},r^{+},z)-\varphi(m,r,z)\right). \tag*{(33)} Φ ( m + , R + , z ) − Φ ( m , R , z ) = a r ( φ ( m + , r + , z ) − φ ( m , r , z ) ) . (33)
The trace change is
Tr ( R + − R ) = ε Y r 2 a ( 3 − ε Y ) = r a ( r + − r ) . (34) \operatorname{Tr}(R_{+}-R)=\frac{\varepsilon Yr^{2}}{a(3-\varepsilon Y)}=\frac{r}{a}(r^{+}-r). \tag*{(34)} Tr ( R + − R ) = a ( 3 − ε Y ) ε Y r 2 = a r ( r + − r ) . (34)
For the quadratic term, write δ = m + − m = Y r / ( 3 − ε Y ) \delta=m^{+}-m=Yr/(3-\varepsilon Y) δ = m + − m = Y r / ( 3 − ε Y ) . The updates give
m + − m = δ a u , R + − 1 = R − 1 − ε Y 3 a x x T . m_{+}-m=\frac{\delta}{a}u,\qquad R_{+}^{-1}=R^{-1}-\frac{\varepsilon Y}{3a}xx^{\mathsf{T}}. m + − m = a δ u , R + − 1 = R − 1 − 3 a ε Y x x T .
The inverse identity follows directly by multiplication with R + R_{+} R + . Using R − 1 u = x R^{-1}u=x R − 1 u = x and u T R − 1 u = a u^{\mathsf{T}}R^{-1}u=a u T R − 1 u = a , we obtain
( z − m + ) T R + − 1 ( z − m + ) = ( z − m ) T R − 1 ( z − m ) − 2 δ ( z − m ) a + δ 2 a − ε Y 3 a ( z − m + ) 2 = ( z − m ) T R − 1 ( z − m ) + 3 − ε Y 3 a ( z − m + ) 2 − ( z − m ) 2 a = ( z − m ) T R − 1 ( z − m ) + r a ( ( z − m + ) 2 r + − ( z − m ) 2 r ) . \begin{aligned}
(z-m_{+})^{\mathsf{T}}R_{+}^{-1}(z-m_{+})
&=(z-m)^{\mathsf{T}}R^{-1}(z-m)-\frac{2\delta(z-m)}{a}+\frac{\delta^{2}}{a}-\frac{\varepsilon Y}{3a}(z-m^{+})^{2}\\
&=(z-m)^{\mathsf{T}}R^{-1}(z-m)+\frac{3-\varepsilon Y}{3a}(z-m^{+})^{2}-\frac{(z-m)^{2}}{a}\\
&=(z-m)^{\mathsf{T}}R^{-1}(z-m)+\frac{r}{a}\left(\frac{(z-m^{+})^{2}}{r^{+}}-\frac{(z-m)^{2}}{r}\right).
\end{aligned} ( z − m + ) T R + − 1 ( z − m + ) = ( z − m ) T R − 1 ( z − m ) − a 2 δ ( z − m ) + a δ 2 − 3 a ε Y ( z − m + ) 2 = ( z − m ) T R − 1 ( z − m ) + 3 a 3 − ε Y ( z − m + ) 2 − a ( z − m ) 2 = ( z − m ) T R − 1 ( z − m ) + a r ( r + ( z − m + ) 2 − r ( z − m ) 2 ) .
The second equality uses z − m + = ( z − m ) − δ z-m^{+}=(z-m)-\delta z − m + = ( z − m ) − δ ; the third uses r + = 3 r / ( 3 − ε Y ) r^{+}=3r/(3-\varepsilon Y) r + = 3 r / ( 3 − ε Y ) . Adding (34) proves (33) .
Finally, take the conditional expectation and apply Lemma C.1 :
Φ − E t [ Φ + ] = r a ( φ ( m , r , z ) − E t [ φ ( m + , r + , z ) ] ) ≥ r 6 a E t [ ∣ z − P ∣ ] ≥ 1 6 E t [ ℓ t ] , \begin{aligned}
\Phi-\mathbb{E}_{t}[\Phi_{+}]
&=\frac{r}{a}\left(\varphi(m,r,z)-\mathbb{E}_{t}\left[\varphi(m^{+},r^{+},z)\right]\right)\\
&\ge\frac{r}{6a}\mathbb{E}_{t}\left[\lvert z-P\rvert\right]\ge\frac{1}{6}\mathbb{E}_{t}[\ell_{t}],
\end{aligned} Φ − E t [ Φ + ] = a r ( φ ( m , r , z ) − E t [ φ ( m + , r + , z ) ] ) ≥ 6 a r E t [ ∣ z − P ∣ ] ≥ 6 1 E t [ ℓ t ] ,
where the last inequality is (32) . This is the desired drift bound.
Supporting Proofs for Bilateral Trade
We first prove the trade-or-information inequality of Lemma 3.1, which directly yields the Bayesian guarantee. We then use it, together with quadratic bounds derived from Lemma B.1 and a minimax argument, to prove the lottery-existence statement of Lemma 3.3.
Proof of Lemma 3.1
Recall that Y ( p ) = 1 { S ≤ p ≤ B } Y(p)=1\{S\leq p\leq B\} Y ( p ) = 1 { S ≤ p ≤ B } indicates whether trade occurs at price p p p . The expected lost gain and the expected reduction in the sum of the two standard deviations are, respectively,
L ( p ) = E [ ( B − S ) + ( 1 − Y ( p ) ) ] , L(p)=\mathbb{E}[(B-S)_{+}(1-Y(p))], L ( p ) = E [( B − S ) + ( 1 − Y ( p ))] ,
D ( p ) = ( sd ( S ) − E [ sd ( S ∣ Y ( p ) ) ] ) + ( sd ( B ) − E [ sd ( B ∣ Y ( p ) ) ] ) . D(p)=(\operatorname{sd}(S)-\mathbb{E}[\operatorname{sd}(S\mid Y(p))])+(\operatorname{sd}(B)-\mathbb{E}[\operatorname{sd}(B\mid Y(p))]). D ( p ) = ( sd ( S ) − E [ sd ( S ∣ Y ( p ))]) + ( sd ( B ) − E [ sd ( B ∣ Y ( p ))]) .
Before proving the lemma, we show that D ( p ) D(p) D ( p ) is nonnegative, provide a useful integral representation of the gain from trade, and introduce a useful result on the information produced by binary feedback.
Claim D.1. For every pair ( S , B ) (S,B) ( S , B ) of square-integrable real random variables, D ( p ) ≥ 0 D(p)\geq0 D ( p ) ≥ 0 for all p ∈ R p\in\mathbb{R} p ∈ R .
Proof. For each Z ∈ { S , B } Z\in\{S,B\} Z ∈ { S , B } , the law of total variance gives
Var ( Z ) = E [ Var ( Z ∣ Y ( p ) ) ] + Var ( E [ Z ∣ Y ( p ) ] ) ≥ E [ Var ( Z ∣ Y ( p ) ) ] . \operatorname{Var}(Z)=\mathbb{E}[\operatorname{Var}(Z\mid Y(p))]+\operatorname{Var}(\mathbb{E}[Z\mid Y(p)])\geq\mathbb{E}[\operatorname{Var}(Z\mid Y(p))]. Var ( Z ) = E [ Var ( Z ∣ Y ( p ))] + Var ( E [ Z ∣ Y ( p )]) ≥ E [ Var ( Z ∣ Y ( p ))] .
Consequently, by Jensen’s inequality and the concavity of the square root,
∑ y ∈ { 0 , 1 } P ( Y ( p ) = y ) sd ( Z ∣ Y ( p ) = y ) = E [ Var ( Z ∣ Y ( p ) ) ] ≤ E [ Var ( Z ∣ Y ( p ) ) ] ≤ sd ( Z ) . \begin{aligned}
\sum_{y\in\{0,1\}}\mathbb{P}(Y(p)=y)\operatorname{sd}(Z\mid Y(p)=y)=\mathbb{E}\left[\sqrt{\operatorname{Var}(Z\mid Y(p))}\right] \\
&\leq\sqrt{\mathbb{E}[\operatorname{Var}(Z\mid Y(p))]} \\
&\leq\operatorname{sd}(Z).
\end{aligned} y ∈ { 0 , 1 } ∑ P ( Y ( p ) = y ) sd ( Z ∣ Y ( p ) = y ) = E [ Var ( Z ∣ Y ( p )) ] ≤ E [ Var ( Z ∣ Y ( p ))] ≤ sd ( Z ) .
Thus, assuming finite variances, each summand in the definition of D ( p ) D(p) D ( p ) is nonnegative, and hence D ( p ) ≥ 0 D(p)\geq0 D ( p ) ≥ 0 . Here, outcomes y y y with P ( Y ( p ) = y ) = 0 \mathbb{P}(Y(p)=y)=0 P ( Y ( p ) = y ) = 0 are omitted from the sum.
Trade profile and gain from trade. Here we give an integral representation of the optimal expected gain from trade under ( S , B ) (S,B) ( S , B ) , in terms of the trade-profile function α ( p ) = P ( p ∈ [ S , B ] ) \alpha(p)=\mathbb{P}(p\in[S,B]) α ( p ) = P ( p ∈ [ S , B ]) . Denote the optimal expected gain from trade by G = E [ ( B − S ) + ] G=\mathbb{E}[(B-S)_{+}] G = E [( B − S ) + ] , where ( ⋅ ) + (\cdot)_{+} ( ⋅ ) + denotes the positive part. The claim does not require independence and also holds when both sides are infinite.
Claim D.2 (Gain-from-trade decomposition). The following integral decomposition holds:
G = ∫ R α ( p ) d p . G=\int_{\mathbb{R}}\alpha(p)\,dp. G = ∫ R α ( p ) d p .
Proof. For every realization ( s , b ) (s,b) ( s , b ) of ( S , B ) (S,B) ( S , B ) , we can write the corresponding gain from trade as follows:
( B − S ) + = ∫ R 1 { S ≤ p ≤ B } d p , (B-S)_{+}=\int_{\mathbb{R}}1\{S\leq p\leq B\}\,dp, ( B − S ) + = ∫ R 1 { S ≤ p ≤ B } d p ,
since the integral is the length of the interval of prices at which trade is possible. Because the integrand is nonnegative, Tonelli’s theorem gives
E [ ( B − S ) + ] = E [ ∫ R 1 { S ≤ p ≤ B } d p ] = ∫ R P ( S ≤ p ≤ B ) d p = ∫ R α ( p ) d p . \mathbb{E}[(B-S)_{+}]=\mathbb{E}\left[\int_{\mathbb{R}}1\{S\leq p\leq B\}\,dp\right]=\int_{\mathbb{R}}\mathbb{P}(S\leq p\leq B)\,dp=\int_{\mathbb{R}}\alpha(p)\,dp. E [( B − S ) + ] = E [ ∫ R 1 { S ≤ p ≤ B } d p ] = ∫ R P ( S ≤ p ≤ B ) d p = ∫ R α ( p ) d p .
Information as displacement. For any event E E E of positive probability, we introduce two notions of “distance” to measure the information provided by the occurrence of E E E about S S S and B B B .
δ Z ∣ E 2 = ( E [ Z ∣ E ] − μ Z ) 2 + ( sd ( Z ∣ E ) − σ Z ) 2 , ϱ Z ∣ E 2 = E [ ( Z − μ Z ) 2 ∣ E ] . \delta_{Z\mid E}^{2} = \bigl(\mathbb{E}[Z\mid E]-\mu_Z\bigr)^2+\bigl(\operatorname{sd}(Z\mid E)-\sigma_Z\bigr)^2,\qquad\varrho_{Z\mid E}^{2}=\mathbb{E}\bigl[(Z-\mu_Z)^2\mid E\bigr]. δ Z ∣ E 2 = ( E [ Z ∣ E ] − μ Z ) 2 + ( sd ( Z ∣ E ) − σ Z ) 2 , ϱ Z ∣ E 2 = E [ ( Z − μ Z ) 2 ∣ E ] .
The first quantity δ Z ∣ E 2 \delta_{Z\mid E}^{2} δ Z ∣ E 2 measures the distance from the posterior point ( E [ Z ∣ E ] , sd ( Z ∣ E ) ) \bigl(\mathbb{E}[Z\mid E],\operatorname{sd}(Z\mid E)\bigr) ( E [ Z ∣ E ] , sd ( Z ∣ E ) ) to ( μ Z , σ Z ) (\mu_Z,\sigma_Z) ( μ Z , σ Z ) , while the second one ϱ Z ∣ E 2 \varrho_{Z\mid E}^{2} ϱ Z ∣ E 2 is the conditional second moment around the unconditional mean μ Z \mu_Z μ Z .
Claim D.3 (Information is displacement). For a square-integrable Z Z Z and a binary signal Y Y Y ,
∑ y ∈ { 0 , 1 } P ( Y = y ) δ Z ∣ { Y = y } 2 = 2 σ Z ( σ Z − ∑ y ∈ { 0 , 1 } P ( Y = y ) sd ( Z ∣ Y = y ) ) . (35) \sum_{y\in\{0,1\}}\mathbb{P}(Y=y)\delta_{Z\mid\{Y=y\}}^{2}
=2\sigma_Z\left(\sigma_Z-\sum_{y\in\{0,1\}}\mathbb{P}(Y=y)\operatorname{sd}(Z\mid Y=y)\right). \tag*{(35)} y ∈ { 0 , 1 } ∑ P ( Y = y ) δ Z ∣ { Y = y } 2 = 2 σ Z σ Z − y ∈ { 0 , 1 } ∑ P ( Y = y ) sd ( Z ∣ Y = y ) . (35) For either positive-probability branch E E E , we also have
∣ E [ Z ∣ E ] − μ Z ∣ ≤ δ Z ∣ E , ∣ ϱ Z ∣ E − σ Z ∣ ≤ δ Z ∣ E . (36) \left|\mathbb{E}[Z\mid E]-\mu_Z\right|\leq\delta_{Z\mid E},\qquad
\left|\varrho_{Z\mid E}-\sigma_Z\right|\leq\delta_{Z\mid E}. \tag*{(36)} ∣ E [ Z ∣ E ] − μ Z ∣ ≤ δ Z ∣ E , ϱ Z ∣ E − σ Z ≤ δ Z ∣ E . (36) If ∣ E [ Z ∣ E ] − μ Z ∣ ≥ η > 0 \left|\mathbb{E}[Z\mid E]-\mu_Z\right|\geq\eta>0 ∣ E [ Z ∣ E ] − μ Z ∣ ≥ η > 0 , then ϱ Z ∣ E ≤ ( 1 + σ Z / η ) δ Z ∣ E \varrho_{Z\mid E}\leq(1+\sigma_Z/\eta)\delta_{Z\mid E} ϱ Z ∣ E ≤ ( 1 + σ Z / η ) δ Z ∣ E .
Proof. By the law of total variance,
∑ y ∈ { 0 , 1 } P ( Y = y ) ( ( E [ Z ∣ Y = y ] − μ Z ) 2 + sd ( Z ∣ Y = y ) 2 ) = σ Z 2 . \sum_{y\in\{0,1\}}\mathbb{P}(Y=y)\left(\bigl(\mathbb{E}[Z\mid Y=y]-\mu_Z\bigr)^2+\operatorname{sd}(Z\mid Y=y)^2\right)=\sigma_Z^2. y ∈ { 0 , 1 } ∑ P ( Y = y ) ( ( E [ Z ∣ Y = y ] − μ Z ) 2 + sd ( Z ∣ Y = y ) 2 ) = σ Z 2 .
Expanding the square in the definition of δ Z ∣ { Y = y } 2 \delta_{Z\mid\{Y=y\}}^{2} δ Z ∣ { Y = y } 2 and using this identity gives
∑ y ∈ { 0 , 1 } P ( Y = y ) δ Z ∣ { Y = y } 2 = ∑ y ∈ { 0 , 1 } P ( Y = y ) [ ( E [ Z ∣ Y = y ] − μ Z ) 2 + sd ( Z ∣ Y = y ) 2 − 2 σ Z sd ( Z ∣ Y = y ) + σ Z 2 ] = 2 σ Z 2 − 2 σ Z ∑ y ∈ { 0 , 1 } P ( Y = y ) sd ( Z ∣ Y = y ) = 2 σ Z ( σ Z − ∑ y ∈ { 0 , 1 } P ( Y = y ) sd ( Z ∣ Y = y ) ) , \begin{aligned}
\sum_{y\in\{0,1\}}\mathbb{P}(Y=y)\delta_{Z\mid\{Y=y\}}^{2}
&=\sum_{y\in\{0,1\}}\mathbb{P}(Y=y)\left[\bigl(\mathbb{E}[Z\mid Y=y]-\mu_Z\bigr)^2+\operatorname{sd}(Z\mid Y=y)^2-2\sigma_Z\operatorname{sd}(Z\mid Y=y)+\sigma_Z^2\right]\\
&=2\sigma_Z^2-2\sigma_Z\sum_{y\in\{0,1\}}\mathbb{P}(Y=y)\operatorname{sd}(Z\mid Y=y)\\
&=2\sigma_Z\left(\sigma_Z-\sum_{y\in\{0,1\}}\mathbb{P}(Y=y)\operatorname{sd}(Z\mid Y=y)\right),
\end{aligned} y ∈ { 0 , 1 } ∑ P ( Y = y ) δ Z ∣ { Y = y } 2 = y ∈ { 0 , 1 } ∑ P ( Y = y ) [ ( E [ Z ∣ Y = y ] − μ Z ) 2 + sd ( Z ∣ Y = y ) 2 − 2 σ Z sd ( Z ∣ Y = y ) + σ Z 2 ] = 2 σ Z 2 − 2 σ Z y ∈ { 0 , 1 } ∑ P ( Y = y ) sd ( Z ∣ Y = y ) = 2 σ Z σ Z − y ∈ { 0 , 1 } ∑ P ( Y = y ) sd ( Z ∣ Y = y ) ,
which proves (35) .
Fix an event E E E of positive probability. The first inequality in (36) follows directly from
δ Z ∣ E 2 = ( E [ Z ∣ E ] − μ Z ) 2 + ( sd ( Z ∣ E ) − σ Z ) 2 ≥ ( E [ Z ∣ E ] − μ Z ) 2 . \delta_{Z\mid E}^{2}=\bigl(\mathbb{E}[Z\mid E]-\mu_Z\bigr)^2+\bigl(\operatorname{sd}(Z\mid E)-\sigma_Z\bigr)^2\geq\bigl(\mathbb{E}[Z\mid E]-\mu_Z\bigr)^2. δ Z ∣ E 2 = ( E [ Z ∣ E ] − μ Z ) 2 + ( sd ( Z ∣ E ) − σ Z ) 2 ≥ ( E [ Z ∣ E ] − μ Z ) 2 .
To prove the second inequality, first note that
ϱ Z ∣ E 2 = E [ ( Z − μ Z ) 2 ∣ E ] = E [ ( Z − E [ Z ∣ E ] ) 2 ∣ E ] + ( E [ Z ∣ E ] − μ Z ) 2 = sd ( Z ∣ E ) 2 + ( E [ Z ∣ E ] − μ Z ) 2 . \begin{aligned}
\varrho_{Z\mid E}^{2}
&=\mathbb{E}\bigl[(Z-\mu_Z)^2\mid E\bigr]\\
&=\mathbb{E}\bigl[(Z-\mathbb{E}[Z\mid E])^2\mid E\bigr]+\bigl(\mathbb{E}[Z\mid E]-\mu_Z\bigr)^2\\
&=\operatorname{sd}(Z\mid E)^2+\bigl(\mathbb{E}[Z\mid E]-\mu_Z\bigr)^2.
\end{aligned} ϱ Z ∣ E 2 = E [ ( Z − μ Z ) 2 ∣ E ] = E [ ( Z − E [ Z ∣ E ] ) 2 ∣ E ] + ( E [ Z ∣ E ] − μ Z ) 2 = sd ( Z ∣ E ) 2 + ( E [ Z ∣ E ] − μ Z ) 2 .
Here the cross term vanishes because E [ Z − E [ Z ∣ E ] ∣ E ] = 0 \mathbb{E}[Z-\mathbb{E}[Z\mid E]\mid E]=0 E [ Z − E [ Z ∣ E ] ∣ E ] = 0 and, in particular, ϱ Z ∣ E ≥ sd ( Z ∣ E ) \varrho_{Z\mid E}\ge\operatorname{sd}(Z\mid E) ϱ Z ∣ E ≥ sd ( Z ∣ E ) . Therefore,
( ϱ Z ∣ E − σ Z ) 2 = ϱ Z ∣ E 2 + σ Z 2 − 2 σ Z ϱ Z ∣ E ≤ ϱ Z ∣ E 2 + σ Z 2 − 2 σ Z sd ( Z ∣ E ) = ( E [ Z ∣ E ] − μ Z ) 2 + ( sd ( Z ∣ E ) − σ Z ) 2 = δ Z ∣ E 2 . \begin{aligned}
(\varrho_{Z\mid E}-\sigma_Z)^2
&= \varrho_{Z\mid E}^2+\sigma_Z^2-2\sigma_Z\varrho_{Z\mid E}\\
&\le\varrho_{Z\mid E}^2+\sigma_Z^2-2\sigma_Z\operatorname{sd}(Z\mid E)\\
&= (\mathbb{E}[Z\mid E]-\mu_Z)^2+(\operatorname{sd}(Z\mid E)-\sigma_Z)^2\\
&= \delta_{Z\mid E}^2.
\end{aligned} ( ϱ Z ∣ E − σ Z ) 2 = ϱ Z ∣ E 2 + σ Z 2 − 2 σ Z ϱ Z ∣ E ≤ ϱ Z ∣ E 2 + σ Z 2 − 2 σ Z sd ( Z ∣ E ) = ( E [ Z ∣ E ] − μ Z ) 2 + ( sd ( Z ∣ E ) − σ Z ) 2 = δ Z ∣ E 2 .
Taking square roots proves ∣ ϱ Z ∣ E − σ Z ∣ ≤ δ Z ∣ E |\varrho_{Z\mid E}-\sigma_Z|\le\delta_{Z\mid E} ∣ ϱ Z ∣ E − σ Z ∣ ≤ δ Z ∣ E , and hence (36) .
Finally, if ∣ E [ Z ∣ E ] − μ Z ∣ ≥ η > 0 |\mathbb{E}[Z\mid E]-\mu_Z|\ge\eta>0 ∣ E [ Z ∣ E ] − μ Z ∣ ≥ η > 0 , the first inequality in (36) gives δ Z ∣ E ≥ η \delta_{Z\mid E}\ge\eta δ Z ∣ E ≥ η . Combining this with the second inequality yields
ϱ Z ∣ E ≤ σ Z + δ Z ∣ E ≤ σ Z η δ Z ∣ E + δ Z ∣ E = ( 1 + σ Z η ) δ Z ∣ E . \varrho_{Z\mid E}\le\sigma_Z+\delta_{Z\mid E}\le\frac{\sigma_Z}{\eta}\delta_{Z\mid E}+\delta_{Z\mid E}=\left(1+\frac{\sigma_Z}{\eta}\right)\delta_{Z\mid E}. ϱ Z ∣ E ≤ σ Z + δ Z ∣ E ≤ η σ Z δ Z ∣ E + δ Z ∣ E = ( 1 + η σ Z ) δ Z ∣ E .
We now proceed with the proof of Lemma 3.1.
Lemma 3.1 (Trade or information). For every pair ( S , B ) (S,B) ( S , B ) of square-integrable real random variables, there is a common price p p p such that
L ( p ) ≤ 2 11 D ( p ) . (37) L(p)\le2^{11}D(p). \tag*{(37)} L ( p ) ≤ 2 11 D ( p ) . (37) The price can be chosen as a function of the joint distribution.
Proof. We write μ Z = E [ Z ] \mu_Z=\mathbb{E}[Z] μ Z = E [ Z ] and σ Z = sd ( Z ) \sigma_Z=\operatorname{sd}(Z) σ Z = sd ( Z ) for Z ∈ { S , B } Z\in\{S,B\} Z ∈ { S , B } to denote the mean and standard deviation of valuation Z Z Z , respectively. As a first-order measure of the gain from trade achievable for a given pair ( S , B ) (S,B) ( S , B ) , we use m = μ B − μ S m=\mu_B-\mu_S m = μ B − μ S , while we use σ = σ S + σ B \sigma=\sigma_S+\sigma_B σ = σ S + σ B as a proxy for the spread of the two variables. We start by addressing some simple corner cases, and then move to the most challenging regime.
Deterministic values. If either σ S \sigma_S σ S or σ B \sigma_B σ B is zero, then one of the two variables is deterministic and posting that value yields the optimal gain from trade. If σ S = 0 \sigma_S=0 σ S = 0 , then posting μ S \mu_S μ S is optimal and yields L ( μ S ) = 0 ≤ D ( μ S ) L(\mu_S)=0\le D(\mu_S) L ( μ S ) = 0 ≤ D ( μ S ) (by Claim D.1 ); similarly, posting μ B \mu_B μ B when σ B = 0 \sigma_B=0 σ B = 0 yields the desired inequality.
Well-separated case. This case is characterized by a large distance m m m between the expected values of S S S and B B B , relative to their standard deviations, i.e., m ≥ 3 σ m\ge3\sigma m ≥ 3 σ , and a price satisfying the statement of the lemma is p ˉ = ( μ S + μ B ) / 2 \bar{p}=(\mu_S+\mu_B)/2 p ˉ = ( μ S + μ B ) /2 . Let F = { Y ( p ˉ ) = 0 } F=\{Y(\bar{p})=0\} F = { Y ( p ˉ ) = 0 } be the event that trade fails at price p ˉ \bar{p} p ˉ . If p ˉ \bar{p} p ˉ always results in a trade, then Claim D.1 yields the statement. We may therefore assume that P ( F ) > 0 \mathbb{P}(F)>0 P ( F ) > 0 . Conditioning on F F F , at least one of S − μ S S-\mu_S S − μ S and μ B − B \mu_B-B μ B − B exceeds m / 2 m/2 m /2 . Hence
N = ( S − μ S ) 2 + ( B − μ B ) 2 > m / 2 , ( B − S ) + ≤ m + 2 N ≤ ( 2 + 2 ) N . N=\sqrt{(S-\mu_S)^2+(B-\mu_B)^2}>m/2,\qquad(B-S)_+\le m+\sqrt{2}N\le(2+\sqrt{2})N. N = ( S − μ S ) 2 + ( B − μ B ) 2 > m /2 , ( B − S ) + ≤ m + 2 N ≤ ( 2 + 2 ) N .
Put ν = E [ N 2 ∣ F ] ≥ m / 2 ≥ 3 σ / 2 \nu=\sqrt{\mathbb{E}[N^2\mid F]}\ge m/2\ge3\sigma/2 ν = E [ N 2 ∣ F ] ≥ m /2 ≥ 3 σ /2 . Then
L ( p ˉ ) ≤ ( 2 + 2 ) P ( F ) ν . (38) L(\bar{p})\le(2+\sqrt{2})\mathbb{P}(F)\nu. \tag*{(38)} L ( p ˉ ) ≤ ( 2 + 2 ) P ( F ) ν . (38)
Claim D.3 applied to each agent under F F F yields
P ( F ) [ ( ϱ S ∣ F − σ S ) 2 + ( ϱ B ∣ F − σ B ) 2 ] ≤ 2 σ S D S ( p ˉ ) + 2 σ B D B ( p ˉ ) ≤ 2 σ D ( p ˉ ) . \mathbb{P}(F)\left[(\varrho_{S\mid F}-\sigma_S)^2+(\varrho_{B\mid F}-\sigma_B)^2\right]\le2\sigma_S D_S(\bar{p})+2\sigma_B D_B(\bar{p})\le2\sigma D(\bar{p}). P ( F ) [ ( ϱ S ∣ F − σ S ) 2 + ( ϱ B ∣ F − σ B ) 2 ] ≤ 2 σ S D S ( p ˉ ) + 2 σ B D B ( p ˉ ) ≤ 2 σ D ( p ˉ ) .
e n d s m i d = 1 {ends_mid=1} e n d s m i d = 1
The vector ( ϱ S ∣ F , ϱ B ∣ F ) (\varrho_{S\mid F},\varrho_{B\mid F}) ( ϱ S ∣ F , ϱ B ∣ F ) has norm ν \nu ν , while ( σ S , σ B ) (\sigma_S,\sigma_B) ( σ S , σ B ) has norm at most σ \sigma σ . The quantity in brackets is therefore at least ( ν − σ ) 2 ≥ ν 2 / 9 (\nu-\sigma)^2 \ge\nu^2/9 ( ν − σ ) 2 ≥ ν 2 /9 . It follows that
D ( p ) ≥ P ( F ) ν 2 18 σ ≥ P ( F ) ν 12 , L ( p ) ≤ 12 ( 2 + 2 ) D ( p ) ≤ 41 D ( p ) . D(p) \ge\frac{\mathbb{P}(F)\nu^2}{18\sigma} \ge\frac{\mathbb{P}(F)\nu}{12}, \qquad L(p) \le12(2+\sqrt{2})D(p) \le41D(p). D ( p ) ≥ 18 σ P ( F ) ν 2 ≥ 12 P ( F ) ν , L ( p ) ≤ 12 ( 2 + 2 ) D ( p ) ≤ 41 D ( p ) .
Overlapping case. We are left with the last case, i.e., m < 3 σ m < 3\sigma m < 3 σ , which is arguably the most intricate: the seller’s and buyer’s expected values are relatively close, and we want to find a “good” price. We tackle this case by providing a uniform upper bound on the trade profile α ( p ) \alpha(p) α ( p ) , which yields, by Claim D.2 , the desired result. We refer to Figure 4 for a visualization of this bound. Define the supremum of D D D on R \mathbb{R} R by D ‾ = sup p ∈ R D ( p ) \overline{D} = \sup_{p\in\mathbb{R}} D(p) D = sup p ∈ R D ( p ) . Note that 0 ≤ D ‾ ≤ σ 0 \le\overline{D} \le\sigma 0 ≤ D ≤ σ . We first bound the trade profile uniformly over all prices in terms of the auxiliary piecewise function H H H :
H ( p ) = { 2 σ S D ‾ ( μ S − p ) 2 , p < μ S − σ S / 3 , 225 D ‾ 2 σ S , μ S − σ S / 3 ≤ p ≤ μ S + σ S / 3 , 1 , μ S + σ S / 3 < p < μ B − σ B / 3 , 225 D ‾ 2 σ B , p > μ S + σ S / 3 , μ B − σ B / 3 ≤ p ≤ μ B + σ B / 3 , 2 σ B D ‾ ( p − μ B ) 2 , p > max { μ S + σ S / 3 , μ B + σ B / 3 } . H(p) =
\begin{cases}
\frac{2\sigma_S\overline{D}}{(\mu_S-p)^2}, & p < \mu_S-\sigma_S/3,\\
\frac{225\overline{D}}{2\sigma_S}, & \mu_S-\sigma_S/3 \le p \le\mu_S+\sigma_S/3,\\
1, & \mu_S+\sigma_S/3 < p < \mu_B-\sigma_B/3,\\
\frac{225\overline{D}}{2\sigma_B}, & p > \mu_S+\sigma_S/3,\ \mu_B-\sigma_B/3 \le p \le\mu_B+\sigma_B/3,\\
\frac{2\sigma_B\overline{D}}{(p-\mu_B)^2}, & p > \max\{\mu_S+\sigma_S/3,\mu_B+\sigma_B/3\}.
\end{cases} H ( p ) = ⎩ ⎨ ⎧ ( μ S − p ) 2 2 σ S D , 2 σ S 225 D , 1 , 2 σ B 225 D , ( p − μ B ) 2 2 σ B D , p < μ S − σ S /3 , μ S − σ S /3 ≤ p ≤ μ S + σ S /3 , μ S + σ S /3 < p < μ B − σ B /3 , p > μ S + σ S /3 , μ B − σ B /3 ≤ p ≤ μ B + σ B /3 , p > max { μ S + σ S /3 , μ B + σ B /3 } .
If the central intervals overlap, the seller’s bound is used through μ S + σ S / 3 \mu_S+\sigma_S/3 μ S + σ S /3 and the buyer’s bound thereafter.
Claim D.4 (Uniform bound on the trade profile). For every p ∈ R p \in\mathbb{R} p ∈ R , we have α ( p ) ≤ H ( p ) \alpha(p) \le H(p) α ( p ) ≤ H ( p ) .
Proof. For any positive-probability branch E E E of Y ( p ) Y(p) Y ( p ) , Claim D.3 gives
P ( E ) δ Z ∣ E 2 ≤ 2 σ Z D Z ( p ) ≤ 2 σ Z D ‾ , Z ∈ { S , B } . \mathbb{P}(E)\delta_{Z\mid E}^2 \le2\sigma_ZD_Z(p) \le2\sigma_Z\overline{D}, \qquad Z \in\{S,B\}. P ( E ) δ Z ∣ E 2 ≤ 2 σ Z D Z ( p ) ≤ 2 σ Z D , Z ∈ { S , B } .
We prove the seller’s tail and central bounds first. If α ( p ) = 0 \alpha(p)=0 α ( p ) = 0 , both are immediate, so assume that E = { S ≤ p ≤ B } E=\{S\le p\le B\} E = { S ≤ p ≤ B } has positive probability. For p < μ S p<\mu_S p < μ S , we have E [ S ∣ E ] ≤ p \mathbb{E}[S\mid E]\le p E [ S ∣ E ] ≤ p , and hence
α ( p ) ( μ S − p ) 2 ≤ α ( p ) δ S ∣ E 2 ≤ 2 σ S D ‾ . \alpha(p)(\mu_S-p)^2 \le\alpha(p)\delta_{S\mid E}^2 \le2\sigma_S\overline{D}. α ( p ) ( μ S − p ) 2 ≤ α ( p ) δ S ∣ E 2 ≤ 2 σ S D .
This proves the upper bound in the first piece of H H H .
For μ S − σ S / 3 ≤ p ≤ μ S + σ S / 3 \mu_S-\sigma_S/3\le p\le\mu_S+\sigma_S/3 μ S − σ S /3 ≤ p ≤ μ S + σ S /3 , set η = σ S / 3 \eta=\sigma_S/3 η = σ S /3 , α = α ( p ) \alpha=\alpha(p) α = α ( p ) , and ϱ = ϱ S ∣ E \varrho=\varrho_{S\mid E} ϱ = ϱ S ∣ E . Sellers trading at p p p with S ≥ μ S − η S\ge\mu_S-\eta S ≥ μ S − η are within η \eta η of their mean. Those with S < μ S − η S<\mu_S-\eta S < μ S − η also trade at the lower price μ S − η \mu_S-\eta μ S − η , since B ≥ p ≥ μ S − η B\ge p\ge\mu_S-\eta B ≥ p ≥ μ S − η . Thus, with E ′ = { S ≤ μ S − η ≤ B } E'=\{S\le\mu_S-\eta\le B\} E ′ = { S ≤ μ S − η ≤ B } ,
α ϱ 2 ≤ η 2 α + E [ ( S − μ S ) 2 1 E ′ ] . (39) \alpha\varrho^2 \le\eta^2\alpha+\mathbb{E}\left[(S-\mu_S)^2\mathbf{1}_{E'}\right]. \tag*{(39)} α ϱ 2 ≤ η 2 α + E [ ( S − μ S ) 2 1 E ′ ] . (39)
If P ( E ′ ) > 0 \mathbb{P}(E')>0 P ( E ′ ) > 0 , then E [ S ∣ E ′ ] ≤ μ S − η \mathbb{E}[S\mid E']\le\mu_S-\eta E [ S ∣ E ′ ] ≤ μ S − η . By Claim D.3 ,
P ( E ′ ) ϱ S ∣ E ′ 2 ≤ 16 P ( E ′ ) δ S ∣ E ′ 2 ≤ 32 σ S D ‾ . \mathbb{P}(E')\varrho_{S\mid E'}^2 \le16\mathbb{P}(E')\delta_{S\mid E'}^2 \le32\sigma_S\overline{D}. P ( E ′ ) ϱ S ∣ E ′ 2 ≤ 16 P ( E ′ ) δ S ∣ E ′ 2 ≤ 32 σ S D .
The same bound on the last expectation in (39) is immediate if P ( E ′ ) = 0 \mathbb{P}(E')=0 P ( E ′ ) = 0 . On E E E itself, Claim D.3 also gives α ( σ S − ϱ ) 2 ≤ 2 σ S D ‾ \alpha(\sigma_S-\varrho)^2\leq2\sigma_S\overline{D} α ( σ S − ϱ ) 2 ≤ 2 σ S D . Consequently,
σ S α ≤ η 2 α + 32 σ S D ‾ + 2 σ S D ‾ ≤ σ S 3 α + 5 2 σ S D ‾ . \sigma_S\sqrt{\alpha}\leq\sqrt{\eta^2\alpha+32\sigma_S\overline{D}}+\sqrt{2\sigma_S\overline{D}}\leq\frac{\sigma_S}{3}\sqrt{\alpha}+5\sqrt{2\sigma_S\overline{D}}. σ S α ≤ η 2 α + 32 σ S D + 2 σ S D ≤ 3 σ S α + 5 2 σ S D .
Rearranging and squaring yields α ( p ) ≤ 225 D ‾ / ( 2 σ ) \alpha(p)\leq225\overline{D}/(2\sigma) α ( p ) ≤ 225 D / ( 2 σ ) , proving the second piece.
Applying these two bounds to ( − B , − S , − p ) (-B,-S,-p) ( − B , − S , − p ) gives the buyer’s central bound for μ B − σ B / 3 ≤ p ≤ μ B + σ B / 3 \mu_B-\sigma_B/3\leq p\leq\mu_B+\sigma_B/3 μ B − σ B /3 ≤ p ≤ μ B + σ B /3 and tail bound for p > μ B + σ B / 3 p>\mu_B+\sigma_B/3 p > μ B + σ B /3 . These prove the fourth and fifth pieces. The third piece is simply α ( p ) ≤ 1 \alpha(p)\leq1 α ( p ) ≤ 1 . The five cases cover R \mathbb{R} R , regardless of the ordering of the two means. □
By Claim D.2 , we can now integrate the uniform bound in Claim D.4 over all of R \mathbb{R} R . The seller’s tail and central pieces have integrals
∫ − ∞ μ S − σ S / 3 2 σ S D ‾ ( μ S − p ) 2 d p = 6 D ‾ , ∫ μ S − σ S / 3 μ S + σ S / 3 225 D ‾ 2 σ S d p = 75 D ‾ . \int_{-\infty}^{\mu_S-\sigma_S/3}\frac{2\sigma_S\overline{D}}{(\mu_S-p)^2}\,dp=6\overline{D},\qquad\int_{\mu_S-\sigma_S/3}^{\mu_S+\sigma_S/3}\frac{225\overline{D}}{2\sigma_S}\,dp=75\overline{D}. ∫ − ∞ μ S − σ S /3 ( μ S − p ) 2 2 σ S D d p = 6 D , ∫ μ S − σ S /3 μ S + σ S /3 2 σ S 225 D d p = 75 D .
The buyer’s tail and central interval have the same respective integrals; restricting them to p > μ S + σ S / 3 p>\mu_S+\sigma_S/3 p > μ S + σ S /3 can only decrease their contribution. The plateau has length ( μ B − σ B / 3 − μ S − σ S / 3 ) + = ( m − σ / 3 ) + (\mu_B-\sigma_B/3-\mu_S-\sigma_S/3)_+=(m-\sigma/3)_+ ( μ B − σ B /3 − μ S − σ S /3 ) + = ( m − σ /3 ) + . Therefore,
G = ∫ R α ( p ) d p ≤ ∫ R H ( p ) d p ≤ 162 D ‾ + ( m − σ / 3 ) + . (40) G=\int_{\mathbb{R}}\alpha(p)\,dp\leq\int_{\mathbb{R}}H(p)\,dp\leq162\overline{D}+(m-\sigma/3)_+. \tag*{(40)} G = ∫ R α ( p ) d p ≤ ∫ R H ( p ) d p ≤ 162 D + ( m − σ /3 ) + . (40)
Since m = E [ B − S ] ≤ G m=\mathbb{E}[B-S]\leq G m = E [ B − S ] ≤ G , subtracting ( G − σ / 3 ) + (G-\sigma/3)_+ ( G − σ /3 ) + gives
min { G , σ / 3 } ≤ 162 D ‾ . (41) \min\{G,\sigma/3\}\leq162\overline{D}. \tag*{(41)} min { G , σ /3 } ≤ 162 D . (41)
Finally, m < 3 σ m<3\sigma m < 3 σ , Cauchy–Schwarz, and the triangle inequality imply
G ≤ m + + E [ ∣ ( B − μ B ) − ( S − μ S ) ∣ ] ≤ m + + σ < 4 σ . G\leq m_++\mathbb{E}\left[|(B-\mu_B)-(S-\mu_S)|\right]\leq m_++\sigma<4\sigma. G ≤ m + + E [ ∣ ( B − μ B ) − ( S − μ S ) ∣ ] ≤ m + + σ < 4 σ .
Thus G ≤ 12 min { G , σ / 3 } ≤ 1944 D ‾ G\leq12\min\{G,\sigma/3\}\leq1944\overline{D} G ≤ 12 min { G , σ /3 } ≤ 1944 D . If D ‾ = 0 \overline{D}=0 D = 0 , every price has zero lost gain. Otherwise, because 1944 < 2 11 1944<2^{11} 1944 < 2 11 , choose any price with 2 11 D ( p ) > 1944 D ‾ 2^{11}D(p)>1944\overline{D} 2 11 D ( p ) > 1944 D . Then L ( p ) ≤ G ≤ 2 11 D ( p ) L(p)\leq G\leq2^{11}D(p) L ( p ) ≤ G ≤ 2 11 D ( p ) . □
Proof of Lemma 3.3
Recall the quadratic variational expression for Φ \Phi Φ , given in (6) :
Φ ( m , R , z ) = Tr R + ( z − m ) T R − 1 ( z − m ) . \Phi(m,R,z)=\operatorname{Tr}R+(z-m)^{\mathsf{T}}R^{-1}(z-m). Φ ( m , R , z ) = Tr R + ( z − m ) T R − 1 ( z − m ) .
For a random vector U ∈ R n U\in\mathbb{R}^n U ∈ R n with mean μ \mu μ and covariance Σ \Sigma Σ , expanding around the mean and applying Lemma B.1 with x = 0 x=0 x = 0 gives, for every m ∈ R n m\in\mathbb{R}^n m ∈ R n and R ≻ 0 R\succ0 R ≻ 0 ,
E [ Φ ( m , R , U ) ] ≥ 2 Ψ ( Σ ) , \mathbb{E}\left[\Phi(m,R,U)\right]\geq2\Psi(\Sigma), E [ Φ ( m , R , U ) ] ≥ 2Ψ ( Σ ) ,
with equality when m = E [ U ] m=\mathbb{E}[U] m = E [ U ] and R = Cov ( U ) ≻ 0 R=\sqrt{\operatorname{Cov}(U)}\succ0 R = Cov ( U ) ≻ 0 .
Lemma 3.3 (A valid lottery exists). For every m ∈ R 2 d m\in\mathbb{R}^{2d} m ∈ R 2 d , every block-diagonal R ≻ 0 R\succ0 R ≻ 0 , every context x x x with ∥ x ∥ 2 ≤ 1 \lVert x\rVert_2\leq1 ∥ x ∥ 2 ≤ 1 , and every γ ∈ ( 0 , 1 ] \gamma\in(0,1] γ ∈ ( 0 , 1 ] , there is a finite lottery of plans satisfying
E [ ℓ ( w ) + 2 10 Φ ( m + , R + , w ) ] ≤ 2 10 Φ ( m , R , w ) + γ for every w ∈ K . (42) \mathbb{E}\left[\ell(w)+2^{10}\Phi(m^+,R^+,w)\right]\leq2^{10}\Phi(m,R,w)+\gamma\qquad\text{for every }w\in K. \tag*{(42)} E [ ℓ ( w ) + 2 10 Φ ( m + , R + , w ) ] ≤ 2 10 Φ ( m , R , w ) + γ for every w ∈ K . (42) Each plan in the lottery posts the same price, drawn from a finite grid, to both agents. The lottery can be chosen as a function of the state and context.
Proof. Fix the current state ( m , R ) (\mathbf{m},R) ( m , R ) , context x x x , and slack γ ∈ ( 0 , 1 ] \gamma\in(0,1] γ ∈ ( 0 , 1 ] , and write Φ 0 ( w ) = Φ ( m , R , w ) \Phi_0(w)=\Phi(\mathbf{m},R,w) Φ 0 ( w ) = Φ ( m , R , w ) . If x = 0 x=0 x = 0 , there is nothing to prove as the gain from trade is zero at any price, so assume x ≠ 0 x\ne0 x = 0 . Let A \mathcal{A} A be the set of plans consisting of a common price p a p_a p a and two successor states ( m a ( y ) , R a ( y ) ) (\mathbf{m}_a^{(y)},R_a^{(y)}) ( m a ( y ) , R a ( y ) ) for y ∈ { 0 , 1 } y\in\{0,1\} y ∈ { 0 , 1 } , with each R a ( y ) R_a^{(y)} R a ( y ) positive definite and block diagonal.
We recall some useful notation. For w = ( s , b ) ∈ K w=(s,b)\in K w = ( s , b ) ∈ K , the valuations S S S and B B B are given by S = x T s S=x^{\mathsf T}s S = x T s and B = x T b B=x^{\mathsf T}b B = x T b . For the price p a p_a p a associated with the generic plan a ∈ A a\in\mathcal{A} a ∈ A , we denote by Y a ( w ) Y_a(w) Y a ( w ) the indicator of whether S S S and B B B permit trade at p a p_a p a , and by ℓ a ( w ) \ell_a(w) ℓ a ( w ) the corresponding loss in terms of the gain from trade:
Y a ( w ) = 1 { S ≤ p a ≤ B } , ℓ a ( w ) = ( B − S ) + ( 1 − Y a ( w ) ) . Y_a(w)=1\{S\le p_a\le B\},\qquad\ell_a(w)=(B-S)_+(1-Y_a(w)). Y a ( w ) = 1 { S ≤ p a ≤ B } , ℓ a ( w ) = ( B − S ) + ( 1 − Y a ( w )) .
We denote by Φ a + ( w ) \Phi_a^+(w) Φ a + ( w ) the value of the potential under the realized feedback Y a ( w ) Y_a(w) Y a ( w ) for the generic plan a ∈ A a\in\mathcal{A} a ∈ A with price p a p_a p a and successor states ( m a ( y ) , R a ( y ) ) (\mathbf{m}_a^{(y)},R_a^{(y)}) ( m a ( y ) , R a ( y ) ) for y ∈ { 0 , 1 } y\in\{0,1\} y ∈ { 0 , 1 } :
Φ a + ( w ) = Φ ( m a ( Y a ( w ) ) , R a ( Y a ( w ) ) , w ) . \Phi_a^+(w)=\Phi\left(\mathbf{m}_a^{(Y_a(w))},R_a^{(Y_a(w))},w\right). Φ a + ( w ) = Φ ( m a ( Y a ( w )) , R a ( Y a ( w )) , w ) .
Finally, we introduce the function f a f_a f a , which is central to our proof:
f a ( w ) = ℓ a ( w ) + 2 10 Φ a + ( w ) − 2 10 Φ 0 ( w ) . f_a(w)=\ell_a(w)+2^{10}\Phi_a^+(w)-2^{10}\Phi_0(w). f a ( w ) = ℓ a ( w ) + 2 10 Φ a + ( w ) − 2 10 Φ 0 ( w ) .
The function f a f_a f a is defined in such a way that inequality (21) in the statement is equivalent to the existence of a finite lottery Q Q Q satisfying E a ∼ Q [ f a ( w ) ] ≤ γ \mathbb{E}_{a\sim Q}[f_a(w)]\le\gamma E a ∼ Q [ f a ( w )] ≤ γ for every w ∈ K w\in K w ∈ K . We first show that, for every hypothetical prior, the infimum of the expected payoff over plans is nonpositive, and then use minimax and discretization to obtain a single such lottery for all hidden pairs.
A plan for each prior. Fix any valuation distribution π ∈ P ( K ) \pi\in\mathcal{P}(K) π ∈ P ( K ) over K K K , where P ( K ) \mathcal{P}(K) P ( K ) is the set of all possible prior distributions of the hidden pair on K K K . We assume that S S S and B B B are induced by sampling W W W according to π \pi π and using the fixed context x x x . For any such distribution, Lemma 3.1 supplies a common price p p p with L ( p ) ≤ 2 11 D ( p ) L(p)\le2^{11}D(p) L ( p ) ≤ 2 11 D ( p ) . For simplicity, let Y Y Y denote the bit 1 { S ≤ p ≤ B } 1\{S\le p\le B\} 1 { S ≤ p ≤ B } . Write π y = L π ( W ∣ Y = y ) \pi_y=\mathcal{L}_{\pi}(W\mid Y=y) π y = L π ( W ∣ Y = y ) whenever P π ( Y = y ) > 0 \mathbb{P}_{\pi}(Y=y)>0 P π ( Y = y ) > 0 . Here, the latter is the conditional law of W W W given Y = y Y=y Y = y . Lemma 1.2, applied to both marginals, bounds D ( p ) D(p) D ( p ) by the decrease in Ψ t r \Psi_{\mathrm{tr}} Ψ tr , so
E π [ ℓ p ( W ) ] = L ( p ) ≤ 2 11 ( Ψ t r ( π ) − ∑ y ∈ { 0 , 1 } P π ( Y = y ) Ψ t r ( π y ) ) . \mathbb{E}_{\pi}[\ell_p(W)]=L(p)\le2^{11}\left(\Psi_{\mathrm{tr}}(\pi)-\sum_{y\in\{0,1\}}\mathbb{P}_{\pi}(Y=y)\Psi_{\mathrm{tr}}(\pi_y)\right). E π [ ℓ p ( W )] = L ( p ) ≤ 2 11 Ψ tr ( π ) − y ∈ { 0 , 1 } ∑ P π ( Y = y ) Ψ tr ( π y ) .
Here and below, sums over y y y omit zero-probability branches. For j ∈ { S , B } j\in\{S,B\} j ∈ { S , B } , let μ y , j \mu_{y,j} μ y , j and Σ y , j \Sigma_{y,j} Σ y , j be the mean and covariance of W j W_j W j under π y \pi_y π y . For λ > 0 \lambda>0 λ > 0 , define a plan a λ a_\lambda a λ with common price p p p and successor states
m a λ ( y ) = ( μ y , S , μ y , B ) , R a λ ( y ) = diag ( ( Σ y , S + λ I d ) 1 / 2 , ( Σ y , B + λ I d ) 1 / 2 ) . \mathbf{m}_{a_\lambda}^{(y)}=(\mu_{y,S},\mu_{y,B}),\qquad R_{a_\lambda}^{(y)}=\operatorname{diag}\left((\Sigma_{y,S}+\lambda I_d)^{1/2},(\Sigma_{y,B}+\lambda I_d)^{1/2}\right). m a λ ( y ) = ( μ y , S , μ y , B ) , R a λ ( y ) = diag ( ( Σ y , S + λ I d ) 1/2 , ( Σ y , B + λ I d ) 1/2 ) .
Choose arbitrary admissible successor states on zero-probability branches. We add the perturbation λ I d \lambda I_d λ I d to ensure that both Σ y , S + λ I d \Sigma_{y,S}+\lambda I_d Σ y , S + λ I d and Σ y , B + λ I d \Sigma_{y,B}+\lambda I_d Σ y , B + λ I d are positive definite, so the inverses of their square roots are well defined. Applying the quadratic variational identity (6) separately to the two marginals gives
E π [ Φ 0 ( W ) ] ≥ 2 Ψ t r ( π ) , lim λ → 0 + E π [ Φ a λ + ( W ) ] = 2 ∑ y ∈ { 0 , 1 } P π ( Y = y ) Ψ t r ( π y ) . \mathbb{E}_{\pi}[\Phi_0(W)]\ge2\Psi_{\mathrm{tr}}(\pi),\qquad\lim_{\lambda\to0^+}\mathbb{E}_{\pi}[\Phi_{a_\lambda}^+(W)]=2\sum_{y\in\{0,1\}}\mathbb{P}_{\pi}(Y=y)\Psi_{\mathrm{tr}}(\pi_y). E π [ Φ 0 ( W )] ≥ 2 Ψ tr ( π ) , λ → 0 + lim E π [ Φ a λ + ( W )] = 2 y ∈ { 0 , 1 } ∑ P π ( Y = y ) Ψ tr ( π y ) .
To compute the limit, diagonalize each marginal covariance: an eigenvalue τ ≥ 0 \tau\ge0 τ ≥ 0 contributes τ + λ + τ / τ + λ \sqrt{\tau+\lambda}+\tau/\sqrt{\tau+\lambda} τ + λ + τ / τ + λ to the corresponding conditional expected successor potential, which tends to 2 τ 2\sqrt{\tau} 2 τ as λ → 0 + \lambda\to0^{+} λ → 0 + , including when τ = 0 \tau=0 τ = 0 . Combining the preceding bounds yields
inf a ∈ A E π [ f a ( W ) ] ≤ lim λ → 0 + E π [ f a λ ( W ) ] ≤ 2 11 Ψ t r ( π ) − 2 10 E π [ Φ 0 ( W ) ] ≤ 0. \inf_{a\in\mathcal{A}} \mathbb{E}_{\pi}[f_a(W)] \le\lim_{\lambda\to0^{+}} \mathbb{E}_{\pi}[f_{a_\lambda}(W)] \le2^{11}\Psi_{\mathrm{tr}}(\pi)-2^{10}\mathbb{E}_{\pi}[\Phi_0(W)]\le0. a ∈ A inf E π [ f a ( W )] ≤ λ → 0 + lim E π [ f a λ ( W )] ≤ 2 11 Ψ tr ( π ) − 2 10 E π [ Φ 0 ( W )] ≤ 0.
Since π \pi π was arbitrary, the “Bayesian value” V B V_{\mathrm{B}} V B satisfies
V B = sup π ∈ P ( K ) inf a ∈ A E π [ f a ( W ) ] ≤ 0. V_{\mathrm{B}}=\sup_{\pi\in\mathcal{P}(K)}\inf_{a\in\mathcal{A}}\mathbb{E}_{\pi}[f_a(W)]\le0. V B = π ∈ P ( K ) sup a ∈ A inf E π [ f a ( W )] ≤ 0.
The following claim exchanges the order of choice and provides the regularity needed to discretize the resulting lottery. Its proof involves a nontrivial application of Sion’s theorem and is deferred to the end of the section. We introduce the inf sup value:
V W = inf Q sup w ∈ K E a ∼ Q [ f a ( w ) ] . V_{\mathrm{W}}=\inf_{Q}\sup_{w\in K}\mathbb{E}_{a\sim Q}[f_a(w)]. V W = Q inf w ∈ K sup E a ∼ Q [ f a ( w )] .
Claim D.5. Allowing arbitrary probability lotteries Q Q Q on A \mathcal{A} A , we have
sup π ∈ P ( K ) inf a ∈ A E π [ f a ( W ) ] = inf Q sup w ∈ K E a ∼ Q [ f a ( w ) ] . \sup_{\pi\in\mathcal{P}(K)}\inf_{a\in\mathcal{A}}\mathbb{E}_{\pi}[f_a(W)]=\inf_{Q}\sup_{w\in K}\mathbb{E}_{a\sim Q}[f_a(w)]. π ∈ P ( K ) sup a ∈ A inf E π [ f a ( W )] = Q inf w ∈ K sup E a ∼ Q [ f a ( w )] . Moreover, for every η > 0 \eta>0 η > 0 , there is a lottery Q Q Q with sup w ∈ K E a ∼ Q [ f a ( w ) ] < V W + η \sup_{w\in K}\mathbb{E}_{a\sim Q}[f_a(w)]<V_{\mathrm{W}}+\eta sup w ∈ K E a ∼ Q [ f a ( w )] < V W + η whose price distribution has bounded density and compact support, and whose successor states range over a compact set of positive-definite block-diagonal states.
A finite lottery on a finite grid. Apply Claim D.5 with η = γ / 3 \eta=\gamma/3 η = γ /3 . Since V W ≤ 0 V_{\mathrm{W}}\le0 V W ≤ 0 , it gives a lottery whose payoff is uniformly less than γ / 3 \gamma/3 γ /3 , with the regularity stated in the claim. Round its common price to the nearest multiple of 1 / n 1/n 1/ n , retaining both successor states. Compact price support ensures that only finitely many grid points occur. The feedback can change only if the original price lies within 1 / n 1/n 1/ n of S S S or B B B . The bounded density makes this event have probability O ( 1 / n ) O(1/n) O ( 1/ n ) uniformly over w ∈ K w\in K w ∈ K . The branch payoffs are uniformly bounded, so the rounding changes the expected payoff uniformly by o ( 1 ) o(1) o ( 1 ) .
Next replace the two successor states by representatives of a sufficiently fine finite net in their compact range. Uniform continuity of Φ \Phi Φ on the product of that range and K K K allows the additional payoff error to be made uniformly as small as desired; choosing representatives from the range preserves positive definiteness and block diagonality. Take each of these two errors smaller than γ / 3 \gamma/3 γ /3 . The resulting lottery has finite support, satisfies (21), and uses common prices on a finite rational grid.
Sion’s theorem. Before proving Claim D.5, we recall Sion’s minimax theorem in its general semicontinuous form and record the affine version used in its proof. Recall that K K K is defined as B 2 d × B 2 d ⊂ R 2 d \mathbb{B}^{d}_{2}\times\mathbb{B}^{d}_{2}\subset\mathbb{R}^{2d} B 2 d × B 2 d ⊂ R 2 d and is endowed with the Euclidean metric, so that it is a nonempty compact metric space. Quasiconcavity means that every superlevel set is convex, and quasiconvexity means that every sublevel set is convex.
Theorem D.6 (Sion’s minimax theorem [22 ] ). Let M M M and N N N be nonempty convex subsets of real topological vector spaces, and suppose that at least one of M M M and N N N is compact. Let F : M × N → R F:M\times N\to\mathbb{R} F : M × N → R satisfy the following conditions:
For every n ∈ N n \in N n ∈ N , the function F ( ⋅ , n ) F(\cdot,n) F ( ⋅ , n ) is upper semicontinuous and quasiconcave on M M M .
For every m ∈ M m \in M m ∈ M , the function F ( m , ⋅ ) F(m,\cdot) F ( m , ⋅ ) is lower semicontinuous and quasiconvex on N N N .
Then
sup m ∈ M inf n ∈ N F ( m , n ) = inf n ∈ N sup m ∈ M F ( m , n ) . \sup_{m\in M}\inf_{n\in N} F(m,n)=\inf_{n\in N}\sup_{m\in M} F(m,n). m ∈ M sup n ∈ N inf F ( m , n ) = n ∈ N inf m ∈ M sup F ( m , n ) .
Corollary D.7 (Separately continuous affine payoffs). Let C ( K ) C(K) C ( K ) be the space of continuous real-valued functions on K K K . Let G ⊂ C ( K ) G \subset C(K) G ⊂ C ( K ) be nonempty and convex, equipped with the uniform norm. Equip the space P ( K ) P(K) P ( K ) of Borel probability measures on K K K with the weak topology. Suppose that F : G × P ( K ) → R F:G \times P(K) \to\mathbb{R} F : G × P ( K ) → R is separately continuous in these topologies and affine in each variable. Then
inf g ∈ G sup π ∈ P ( K ) F ( g , π ) = sup π ∈ P ( K ) inf g ∈ G F ( g , π ) . \inf_{g\in G}\sup_{\pi\in P(K)} F(g,\pi)=\sup_{\pi\in P(K)}\inf_{g\in G} F(g,\pi). g ∈ G inf π ∈ P ( K ) sup F ( g , π ) = π ∈ P ( K ) sup g ∈ G inf F ( g , π ) .
We now turn to the proof of Claim D.5.
Proof of Claim D.5. We start by proving the “easy” direction of the equality, via weak duality. For any prior π \pi π and lottery Q Q Q , draw W ∼ π W \sim\pi W ∼ π and a ∼ Q a \sim Q a ∼ Q independently. Then
inf a ∈ A E π [ f a ( W ) ] ≤ E a ∼ Q [ E W ∼ π [ f a ( W ) ] ] = E W ∼ π [ E a ∼ Q [ f a ( W ) ] ] ≤ sup w ∈ K E a ∼ Q [ f a ( w ) ] . \inf_{a\in A}\mathbb{E}_{\pi}[f_a(W)] \leq\mathbb{E}_{a\sim Q}\left[\mathbb{E}_{W\sim\pi}[f_a(W)]\right] = \mathbb{E}_{W\sim\pi}\left[\mathbb{E}_{a\sim Q}[f_a(W)]\right] \leq\sup_{w\in K}\mathbb{E}_{a\sim Q}[f_a(w)]. a ∈ A inf E π [ f a ( W )] ≤ E a ∼ Q [ E W ∼ π [ f a ( W )] ] = E W ∼ π [ E a ∼ Q [ f a ( W )] ] ≤ w ∈ K sup E a ∼ Q [ f a ( w )] .
The first and last inequalities use that an average is at least the infimum and at most the supremum. The exchange of expectations follows from Tonelli’s theorem after adding the constant 2 10 max K Φ 0 2^{10}\max_K \Phi_0 2 10 max K Φ 0 , which makes the integrand nonnegative. Taking the supremum over π \pi π and then the infimum over Q Q Q gives V B ≤ V W V_B \leq V_W V B ≤ V W . Both values are finite: f a ≥ − 2 10 max K Φ 0 f_a \geq-2^{10}\max_K \Phi_0 f a ≥ − 2 10 max K Φ 0 , and retaining the current state gives a bounded payoff.
We now move to the other direction. Unfortunately, we cannot directly invoke Sion’s theorem, as the function f a ( w ) f_a(w) f a ( w ) has the discontinuities induced by Y a ( w ) Y_a(w) Y a ( w ) . To smooth it out, we introduce a random perturbation of the posted price. More precisely, we first average the discontinuous payoffs over a small random perturbation, apply minimax to the resulting continuous functions, and then let the perturbation vanish.
Fix any 0 < ε < 1 2 0 < \varepsilon< \frac{1}{2} 0 < ε < 2 1 and let U U U be sampled uniformly at random in [ − ε ∥ x ∥ 2 , ε ∥ x ∥ 2 ] [-\varepsilon\lVert x\rVert_2,\varepsilon\lVert x\rVert_2] [ − ε ∥ x ∥ 2 , ε ∥ x ∥ 2 ] (recall that x x x is the nonzero context we are given). For any realization u u u of U U U , we define the perturbed vector T u w T_u w T u w as follows:
T u w = ( 1 − ε ) ⋅ w + u ⋅ v , where v = ( x ∥ x ∥ 2 2 , x ∥ x ∥ 2 2 ) . T_u w=(1-\varepsilon)\cdot w+u\cdot v,\qquad\text{where }v=\left(\frac{x}{\lVert x\rVert_2^2},\frac{x}{\lVert x\rVert_2^2}\right). T u w = ( 1 − ε ) ⋅ w + u ⋅ v , where v = ( ∥ x ∥ 2 2 x , ∥ x ∥ 2 2 x ) .
By construction, the “perturbed” values are just the original S S S and B B B , scaled by 1 − ε 1-\varepsilon 1 − ε and shifted by u u u :
x T [ ( 1 − ε ) ⋅ s + u ⋅ x ∥ x ∥ 2 2 ] = ( 1 − ε ) S + u , x T [ ( 1 − ε ) ⋅ b + u ⋅ x ∥ x ∥ 2 2 ] = ( 1 − ε ) B + u . x^\mathsf{T}\left[(1-\varepsilon)\cdot s+u\cdot\frac{x}{\lVert x\rVert_2^2}\right]=(1-\varepsilon)S+u,\qquad x^\mathsf{T}\left[(1-\varepsilon)\cdot b+u\cdot\frac{x}{\lVert x\rVert_2^2}\right]=(1-\varepsilon)B+u. x T [ ( 1 − ε ) ⋅ s + u ⋅ ∥ x ∥ 2 2 x ] = ( 1 − ε ) S + u , x T [ ( 1 − ε ) ⋅ b + u ⋅ ∥ x ∥ 2 2 x ] = ( 1 − ε ) B + u .
Moreover, T u T_u T u maps K K K into itself, i.e., T u K ⊆ K T_uK \subseteq K T u K ⊆ K . To see this, we consider the first d d d components of T u ( w ) T_u(w) T u ( w ) ; the other case is analogous:
∥ ( 1 − ε ) ⋅ s + u ⋅ x ∥ x ∥ 2 2 ∥ 2 ≤ ( 1 − ε ) ∥ s ∥ 2 + ∣ u ∣ ∥ x ∥ 2 ≤ ( 1 − ε ) + ε = 1. \left\lVert(1-\varepsilon)\cdot s+u\cdot\frac{x}{\lVert x\rVert_2^2}\right\rVert_2 \leq(1-\varepsilon)\lVert s\rVert_2+\frac{|u|}{\lVert x\rVert_2}\leq(1-\varepsilon)+\varepsilon=1. ( 1 − ε ) ⋅ s + u ⋅ ∥ x ∥ 2 2 x 2 ≤ ( 1 − ε ) ∥ s ∥ 2 + ∥ x ∥ 2 ∣ u ∣ ≤ ( 1 − ε ) + ε = 1.
For any base plan a a a , draw U U U and implement the common price and successor states
p a , U = p a − U 1 − ε , m a , U ( y ) = m a ( y ) − U v 1 − ε , R a , U ( y ) = R a ( y ) 1 − ε . p_{a,U} = \frac{p_a-U}{1-\varepsilon},\qquad m_{a,U}^{(y)} = \frac{m_a^{(y)}-Uv}{1-\varepsilon},\qquad R_{a,U}^{(y)} = \frac{R_a^{(y)}}{1-\varepsilon}. p a , U = 1 − ε p a − U , m a , U ( y ) = 1 − ε m a ( y ) − U v , R a , U ( y ) = 1 − ε R a ( y ) .
Denote this actual plan by a U ε a_U^\varepsilon a U ε . By construction, the original valuations S S S and B B B permit trade at the perturbed price p a , u p_{a,u} p a , u if and only if the perturbed valuations permit trade at the original price, for any plan a a a and realization u u u of U U U :
1 { S ≤ p a − u 1 − ε ≤ B } = 1 { ( 1 − ε ) S + u ≤ p a ≤ ( 1 − ε ) B + u } . \mathbf{1}\left\{S \leq\frac{p_a-u}{1-\varepsilon} \leq B\right\} = \mathbf{1}\left\{(1-\varepsilon)S+u \leq p_a \leq(1-\varepsilon)B+u\right\}. 1 { S ≤ 1 − ε p a − u ≤ B } = 1 { ( 1 − ε ) S + u ≤ p a ≤ ( 1 − ε ) B + u } .
The transformation T u T_u T u is used only in the analysis; the learner implements the displayed price and successor states using its sampled u u u . For either branch y y y , substitution into the quadratic potential gives
Φ ( m a ( y ) − u v 1 − ε , R a ( y ) 1 − ε , w ) = 1 1 − ε Φ ( m a ( y ) , R a ( y ) , T u w ) . \Phi\left(\frac{m_a^{(y)}-uv}{1-\varepsilon},\frac{R_a^{(y)}}{1-\varepsilon},w\right)=\frac{1}{1-\varepsilon}\Phi\left(m_a^{(y)},R_a^{(y)},T_uw\right). Φ ( 1 − ε m a ( y ) − uv , 1 − ε R a ( y ) , w ) = 1 − ε 1 Φ ( m a ( y ) , R a ( y ) , T u w ) .
Also, ( ( 1 − ε ) B + u − ( 1 − ε ) S − u ) + = ( 1 − ε ) ( B − S ) + \bigl((1-\varepsilon)B+u-(1-\varepsilon)S-u\bigr)_+=(1-\varepsilon)(B-S)_+ ( ( 1 − ε ) B + u − ( 1 − ε ) S − u ) + = ( 1 − ε ) ( B − S ) + , so the lost gain has the same scaling. Combining these identities and subtracting the unchanged current potential gives
g a ε ( w ) = E U [ f a U ε ( w ) ] = 1 1 − ε E U [ f a ( T U w ) ] + 2 10 E U [ Φ 0 ( T U w ) 1 − ε − Φ 0 ( w ) ] . g_a^\varepsilon(w)=\mathbb{E}_U\left[f_{a_U^\varepsilon}(w)\right]=\frac{1}{1-\varepsilon}\mathbb{E}_U\left[f_a(T_Uw)\right]+2^{10}\mathbb{E}_U\left[\frac{\Phi_0(T_Uw)}{1-\varepsilon}-\Phi_0(w)\right]. g a ε ( w ) = E U [ f a U ε ( w ) ] = 1 − ε 1 E U [ f a ( T U w ) ] + 2 10 E U [ 1 − ε Φ 0 ( T U w ) − Φ 0 ( w ) ] .
The crucial fact is that now, for each fixed a a a , the averaged payoff g a ε g_a^\varepsilon g a ε is continuous in w w w . To see this, consider any sequence w n → w w_n\to w w n → w . Except at the two noise values u = p a − ( 1 − ε ) S u=p_a-(1-\varepsilon)S u = p a − ( 1 − ε ) S and u = p a − ( 1 − ε ) B u=p_a-(1-\varepsilon)B u = p a − ( 1 − ε ) B , the feedback at w n w_n w n eventually agrees with that at w w w , and the corresponding branch payoff converges. These exceptional values have probability zero under U U U . Both branch payoffs are bounded on the compact set of hidden pairs ( w ∈ K ) (w\in K) ( w ∈ K ) and noise values ( ∣ u ∣ ≤ ε ∥ x ∥ 2 ) (|u|\leq\varepsilon\lVert x\rVert_2) ( ∣ u ∣ ≤ ε ∥ x ∥ 2 ) , so dominated convergence applies, including when S = B S=B S = B .
Moreover, the absolute value of the difference between Φ 0 \Phi_0 Φ 0 and its scaled version converges uniformly to 0 0 0 :
δ ε = 2 10 sup w ∈ K ∣ u ∣ ≤ ε ∥ x ∥ 2 ∣ Φ 0 ( T u w ) 1 − ε − Φ 0 ( w ) ∣ ⟶ 0. \delta_\varepsilon=2^{10}\sup_{\substack{w\in K\\ |u|\leq\varepsilon\lVert x\rVert_2}}\left|\frac{\Phi_0(T_uw)}{1-\varepsilon}-\Phi_0(w)\right|\longrightarrow0. δ ε = 2 10 w ∈ K ∣ u ∣ ≤ ε ∥ x ∥ 2 sup 1 − ε Φ 0 ( T u w ) − Φ 0 ( w ) ⟶ 0.
Indeed, ∥ T u w − w ∥ 2 ≤ 2 2 ε \lVert T_uw-w\rVert_2\leq2\sqrt{2}\varepsilon ∥ T u w − w ∥ 2 ≤ 2 2 ε , and the current potential Φ 0 \Phi_0 Φ 0 is uniformly continuous on K K K . In particular, the correction is controlled independently of the base plan a a a .
For a prior π \pi π , let π ε \pi_\varepsilon π ε be the law of T U W T_UW T U W when W ∼ π W\sim\pi W ∼ π and U U U is independent. Since T u K ⊆ K T_uK\subseteq K T u K ⊆ K , this is another prior in P ( K ) P(K) P ( K ) . Averaging the payoff identity and using the definition of V B V_B V B yields
inf a E π [ g a ε ( W ) ] ≤ 1 1 − ε inf a E W ′ ∼ π ε [ f a ( W ′ ) ] + δ ε ≤ V B 1 − ε + δ ε . \inf_a\mathbb{E}_{\pi}\left[g_a^\varepsilon(W)\right]\leq\frac{1}{1-\varepsilon}\inf_a\mathbb{E}_{W'\sim\pi_\varepsilon}\left[f_a(W')\right]+\delta_\varepsilon\leq\frac{V_B}{1-\varepsilon}+\delta_\varepsilon. a inf E π [ g a ε ( W ) ] ≤ 1 − ε 1 a inf E W ′ ∼ π ε [ f a ( W ′ ) ] + δ ε ≤ 1 − ε V B + δ ε .
We are now ready to apply the version of Sion’s theorem presented in Corollary D.7 . To this end, we consider the space C ( K ) C(K) C ( K ) of continuous functions from K K K to R \mathbb{R} R , equipped with the uniform norm; in particular, we focus on G ε ⊂ C ( K ) \mathcal{G}_\varepsilon\subset C(K) G ε ⊂ C ( K ) , which is defined as the convex hull of the functions g a ε g_a^\varepsilon g a ε . By definition, every g ∈ G ε g\in\mathcal{G}_\varepsilon g ∈ G ε has the form
g = ∑ i = 1 N α i g a i ε , α i ≥ 0 , ∑ i = 1 N α i = 1 , g=\sum_{i=1}^{N}\alpha_i g_{a_i}^\varepsilon,\qquad\alpha_i\geq0,\qquad\sum_{i=1}^{N}\alpha_i=1, g = i = 1 ∑ N α i g a i ε , α i ≥ 0 , i = 1 ∑ N α i = 1 ,
for finitely many base plans a 1 , … , a N a_1,\ldots,a_N a 1 , … , a N . To implement g g g , first sample an index i i i with probabilities ( α i ) i = 1 N (\alpha_i)_{i=1}^N ( α i ) i = 1 N , then independently sample U U U as above and execute the plan ( a i ) U ~ (a_i)_{\tilde U} ( a i ) U ~ . The resulting lottery Q g Q_g Q g on A \mathcal A A satisfies, for every hidden pair,
E a ∼ Q g [ f a ( w ) ] = ∑ i = 1 N α i E U [ f ( a i ) U ~ ( w ) ] = g ( w ) . \mathbb E_{a\sim Q_g}[f_a(w)] = \sum_{i=1}^N \alpha_i \mathbb E_U\left[f_{(a_i)_{\tilde U}}(w)\right] = g(w). E a ∼ Q g [ f a ( w )] = i = 1 ∑ N α i E U [ f ( a i ) U ~ ( w ) ] = g ( w ) .
Here the mixture uses finitely many base plans, but Q g Q_g Q g itself need not have finite support because U U U has a continuous distribution. Such lotteries are allowed in the definition of V W V_W V W ; finite support will be obtained in the subsequent discretization step. Thus minimizing over g ∈ G ε g\in\mathcal G_\varepsilon g ∈ G ε restricts the admissible lotteries and can only increase the infimum defining V W V_W V W .
Define the payoff pairing
F ( g , π ) = ∫ K g ( w ) d π ( w ) . F(g,\pi)=\int_K g(w)\,\mathrm d\pi(w). F ( g , π ) = ∫ K g ( w ) d π ( w ) .
Recall that G ε \mathcal G_\varepsilon G ε is equipped with the uniform norm ∥ g ∥ ∞ = max w ∈ K ∣ g ( w ) ∣ \lVert g\rVert_\infty=\max_{w\in K}|g(w)| ∥ g ∥ ∞ = max w ∈ K ∣ g ( w ) ∣ , while P ( K ) \mathcal P(K) P ( K ) is equipped with the topology of weak convergence of probability measures. Since K K K is compact, P ( K ) \mathcal P(K) P ( K ) is compact in this topology; it is also convex. The set G ε \mathcal G_\varepsilon G ε is convex by construction, and F F F is affine in each argument separately.
Explicitly, for t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] , g , h ∈ G ε g,h\in\mathcal G_\varepsilon g , h ∈ G ε , and π , π 1 , π 2 ∈ P ( K ) \pi,\pi_1,\pi_2\in\mathcal P(K) π , π 1 , π 2 ∈ P ( K ) , linearity of integration gives
F ( t g + ( 1 − t ) h , π ) = t F ( g , π ) + ( 1 − t ) F ( h , π ) , F(tg+(1-t)h,\pi)=tF(g,\pi)+(1-t)F(h,\pi), F ( t g + ( 1 − t ) h , π ) = tF ( g , π ) + ( 1 − t ) F ( h , π ) ,
F ( g , t π 1 + ( 1 − t ) π 2 ) = t F ( g , π 1 ) + ( 1 − t ) F ( g , π 2 ) . F(g,t\pi_1+(1-t)\pi_2)=tF(g,\pi_1)+(1-t)F(g,\pi_2). F ( g , t π 1 + ( 1 − t ) π 2 ) = tF ( g , π 1 ) + ( 1 − t ) F ( g , π 2 ) .
These are exactly the affine identities required in Corollary D.7 . We next check separate continuity, meaning continuity in either variable with the other held fixed.
For a fixed prior π \pi π and any g , h ∈ G ε g,h\in\mathcal G_\varepsilon g , h ∈ G ε ,
∣ F ( g , π ) − F ( h , π ) ∣ ≤ ∫ K ∣ g − h ∣ d π ≤ ∥ g − h ∥ ∞ . |F(g,\pi)-F(h,\pi)|\le\int_K |g-h|\,\mathrm d\pi\le\lVert g-h\rVert_\infty. ∣ F ( g , π ) − F ( h , π ) ∣ ≤ ∫ K ∣ g − h ∣ d π ≤ ∥ g − h ∥ ∞ .
For a fixed g ∈ G ε g\in\mathcal G_\varepsilon g ∈ G ε , weak convergence π n → π \pi_n\to\pi π n → π gives
F ( g , π n ) = ∫ K g d π n ⟶ ∫ K g d π = F ( g , π ) , F(g,\pi_n)=\int_K g\,\mathrm d\pi_n\longrightarrow\int_K g\,\mathrm d\pi=F(g,\pi), F ( g , π n ) = ∫ K g d π n ⟶ ∫ K g d π = F ( g , π ) ,
because g g g is continuous and bounded on K K K . This is precisely where continuity of the smoothed payoffs is used.
We can therefore apply Corollary D.7 with G = G ε \mathcal G=\mathcal G_\varepsilon G = G ε and the pairing F ( g , π ) = ∫ K g d π F(g,\pi)=\int_K g\,\mathrm d\pi F ( g , π ) = ∫ K g d π . The hidden-pair set K K K is a nonempty compact metric space, G ε ⊂ C ( K ) \mathcal G_\varepsilon\subset C(K) G ε ⊂ C ( K ) is nonempty and convex with the uniform norm, and P ( K ) \mathcal P(K) P ( K ) carries the weak topology. The two preceding calculations verify separate affinity and continuity. We obtain
inf g ∈ G ε sup π ∈ P ( K ) F ( g , π ) = sup π ∈ P ( K ) inf g ∈ G ε F ( g , π ) . \inf_{g\in\mathcal G_\varepsilon}\sup_{\pi\in\mathcal P(K)}F(g,\pi)
=
\sup_{\pi\in\mathcal P(K)}\inf_{g\in\mathcal G_\varepsilon}F(g,\pi). g ∈ G ε inf π ∈ P ( K ) sup F ( g , π ) = π ∈ P ( K ) sup g ∈ G ε inf F ( g , π ) .
For each fixed g g g , an average under any prior is at most max K g \max_K g max K g . Conversely, g g g attains this maximum at some w g ∈ K w_g\in K w g ∈ K , and the point mass δ w g \delta_{w_g} δ w g attains the same value in the prior formulation. Hence
sup π ∈ P ( K ) F ( g , π ) = F ( g , δ w g ) = max w ∈ K g ( w ) . \sup_{\pi\in\mathcal P(K)}F(g,\pi)=F(g,\delta_{w_g})=\max_{w\in K}g(w). π ∈ P ( K ) sup F ( g , π ) = F ( g , δ w g ) = w ∈ K max g ( w ) .
For each fixed prior π \pi π , linearity gives, for every finite mixture,
F ( ∑ i = 1 N α i g a i ε , π ) = ∑ i = 1 N α i E π [ g a i ε ( W ) ] ≥ inf a ∈ A E π [ g a ε ( W ) ] . F\left(\sum_{i=1}^{N}\alpha_i g^{\varepsilon}_{a_i},\pi\right)=\sum_{i=1}^{N}\alpha_i\mathbb{E}_{\pi}\left[g^{\varepsilon}_{a_i}(W)\right]\geq\inf_{a\in\mathcal{A}}\mathbb{E}_{\pi}\left[g^{\varepsilon}_{a}(W)\right]. F ( i = 1 ∑ N α i g a i ε , π ) = i = 1 ∑ N α i E π [ g a i ε ( W ) ] ≥ a ∈ A inf E π [ g a ε ( W ) ] .
Since each individual g a ε g^{\varepsilon}_{a} g a ε also belongs to the convex hull, the reverse inequality holds after taking the infimum over g g g . Thus
inf g ∈ G ε F ( g , π ) = inf a ∈ A E π [ g a ε ( W ) ] . \inf_{g\in\mathcal{G}_{\varepsilon}}F(g,\pi)=\inf_{a\in\mathcal{A}}\mathbb{E}_{\pi}\left[g^{\varepsilon}_{a}(W)\right]. g ∈ G ε inf F ( g , π ) = a ∈ A inf E π [ g a ε ( W ) ] .
Combining the implementation of g g g , the point-mass identity, Sion’s exchange, and the convex-hull identity, in that order, gives
V W ≤ inf g ∈ G ε max w ∈ K g ( w ) = inf g ∈ G ε sup π ∈ P ( K ) F ( g , π ) = sup π ∈ P ( K ) inf g ∈ G ε F ( g , π ) = sup π ∈ P ( K ) inf a ∈ A E π [ g a ε ( W ) ] ≤ V B 1 − ε + δ ε . \begin{aligned}
V_{\mathrm{W}} &\leq\inf_{g\in\mathcal{G}_{\varepsilon}}\max_{w\in K}g(w)\\
&=\inf_{g\in\mathcal{G}_{\varepsilon}}\sup_{\pi\in\mathcal{P}(K)}F(g,\pi)\\
&=\sup_{\pi\in\mathcal{P}(K)}\inf_{g\in\mathcal{G}_{\varepsilon}}F(g,\pi)\\
&=\sup_{\pi\in\mathcal{P}(K)}\inf_{a\in\mathcal{A}}\mathbb{E}_{\pi}\left[g^{\varepsilon}_{a}(W)\right]\leq\frac{V_{\mathrm{B}}}{1-\varepsilon}+\delta_{\varepsilon}.
\end{aligned} V W ≤ g ∈ G ε inf w ∈ K max g ( w ) = g ∈ G ε inf π ∈ P ( K ) sup F ( g , π ) = π ∈ P ( K ) sup g ∈ G ε inf F ( g , π ) = π ∈ P ( K ) sup a ∈ A inf E π [ g a ε ( W ) ] ≤ 1 − ε V B + δ ε .
The last inequality is the bound proved above for every prior π \pi π , whose right-hand side does not depend on π \pi π . This estimate holds for every 0 < ε < 1 / 2 0<\varepsilon<1/2 0 < ε < 1/2 . Since V B V_{\mathrm{B}} V B is finite, letting ε → 0 + \varepsilon\to0^{+} ε → 0 + gives V W ≤ V B V_{\mathrm{W}}\leq V_{\mathrm{B}} V W ≤ V B . Together with weak duality, this proves equality: V W = V B V_{\mathrm{W}}=V_{\mathrm{B}} V W = V B . The limit is taken only in this numerical bound, so no convergence of the implementing lotteries is needed.
For the additional assertion, choose ε \varepsilon ε small enough and then an element of G ε \mathcal{G}_{\varepsilon} G ε whose maximum is less than V B + η V_{\mathrm{B}}+\eta V B + η ; no attainment of the infimum is required. This element is implemented by a finite mixture of the smoothed plans a U ε a^{\varepsilon}_{U} a U ε . Each common price is uniform on a bounded interval of positive length, and each successor state is a continuous function of U U U on a compact interval. The finite mixture therefore has bounded price density, compact price support, and a compact range of positive-definite block-diagonal successor states.
More explicitly, every price interval has length 2 ε ∥ x ∥ 2 / ( 1 − ε ) 2\varepsilon\lVert x\rVert_{2}/(1-\varepsilon) 2 ε ∥ x ∥ 2 / ( 1 − ε ) , so the mixture’s density is bounded by ( 1 − ε ) / ( 2 ε ∥ x ∥ 2 ) (1-\varepsilon)/(2\varepsilon\lVert x\rVert_{2}) ( 1 − ε ) / ( 2 ε ∥ x ∥ 2 ) . The choice of ε > 0 \varepsilon>0 ε > 0 and the finite mixture is fixed before the subsequent grid approximation.
Proof of Corollary D.7. Since K K K is compact, P ( K ) \mathcal{P}(K) P ( K ) is a compact convex subset of the space of finite signed Borel measures equipped with the weak topology. Apply Theorem D.6 with M = P ( K ) M=\mathcal{P}(K) M = P ( K ) , N = G N=\mathcal{G} N = G , and the transposed payoff F ~ ( π , g ) = F ( g , π ) \widetilde{F}(\pi,g)=F(g,\pi) F ( π , g ) = F ( g , π ) . For fixed g g g , continuity in π \pi π implies upper semicontinuity, and affinity implies concavity and hence quasiconcavity. For fixed π \pi π , continuity in g g g implies lower semicontinuity, and affinity implies convexity and hence quasiconvexity. Thus all the hypotheses hold, with compactness supplied by the prior space P ( K ) \mathcal{P}(K) P ( K ) , and the theorem gives the stated equality.
Lower Bounds
In this section, we present standard lower bounds for both contextual search and contextual bilateral trade. First, we recall the standard coordinate-wise lower-bound argument for contextual search [16 ] .
Proposition E.1 (Lower bound for contextual search). For every d ≥ 1 d \ge1 d ≥ 1 , every T ≥ d T \ge d T ≥ d , and every possibly randomized algorithm, there exists a fixed target z ∈ R d \boldsymbol{z} \in\mathbb{R}^{d} z ∈ R d with ∥ z ∥ 2 = 1 \lVert\boldsymbol{z}\rVert_{2} = 1 ∥ z ∥ 2 = 1 and a deterministic sequence of context vectors of norm at most one such that
∑ t = 1 T E [ ℓ t ] ≥ d . \sum_{t=1}^{T} \mathbb{E}[\ell_t] \ge\sqrt{d}. t = 1 ∑ T E [ ℓ t ] ≥ d .
Proof. We consider an adversary that chooses the coordinates of z \boldsymbol{z} z independently and uniformly from { − 1 / d , 1 / d } \{-1/\sqrt{d},1/\sqrt{d}\} { − 1/ d , 1/ d } , so that ∥ z ∥ = 1 \lVert\boldsymbol{z}\rVert= 1 ∥ z ∥ = 1 . For the first d d d rounds, the adversary lets x t \boldsymbol{x}_t x t be the t t t -th basis vector, and sets x t = 0 \boldsymbol{x}_t = 0 x t = 0 afterward. At round t ≤ d t \le d t ≤ d , z t = x t ⊤ z z_t = \boldsymbol{x}_t^\top\boldsymbol{z} z t = x t ⊤ z is independent of any previous observation made by the algorithm, and thus of the posted price P t P_t P t . Therefore,
E [ ℓ t ∣ P t ] = 1 2 ∣ P t − 1 d ∣ + 1 2 ∣ P t + 1 d ∣ ≥ 1 d . \mathbb{E}[\ell_t \mid P_t] = \frac{1}{2}\left|P_t-\frac{1}{\sqrt{d}}\right|+\frac{1}{2}\left|P_t+\frac{1}{\sqrt{d}}\right| \ge\frac{1}{\sqrt{d}}. E [ ℓ t ∣ P t ] = 2 1 P t − d 1 + 2 1 P t + d 1 ≥ d 1 .
Summing the loss over t ∈ { 1 , … , d } t \in\{1,\ldots,d\} t ∈ { 1 , … , d } provides the desired lower bound.
We now turn to the matching lower bound for contextual bilateral trade. The coordinate construction in [8 Proposition 4.3] , rescaled to the Euclidean unit ball, gives the following bound. Here, we allow the learner to post two distinct prices, as long as budget balance is enforced, i.e., the price p t p_t p t offered to the seller is at most the price q t q_t q t offered to the buyer.
Proposition E.2 (Lower bound for contextual bilateral trade). For every d ≥ 1 d \ge1 d ≥ 1 , every T ≥ d T \ge d T ≥ d , and every possibly randomized learner satisfying p t ≤ q t p_t \le q_t p t ≤ q t , there are a fixed pair ( s , b ) ∈ K (\boldsymbol{s},\boldsymbol{b}) \in K ( s , b ) ∈ K and deterministic contexts of norm at most one for which
∑ t = 1 T E [ ℓ t ] ≥ d 6 . \sum_{t=1}^{T} \mathbb{E}[\ell_t] \ge\frac{\sqrt{d}}{6}. t = 1 ∑ T E [ ℓ t ] ≥ 6 d .
The same lower bound holds in the Bayesian setting for the prior whose coordinates are independent and for which each pair ( d s j , d b j ) (\sqrt{d}s_j,\sqrt{d}b_j) ( d s j , d b j ) is uniform on { ( 0 , 1 / 3 ) , ( 2 / 3 , 1 ) } \{(0,1/3),(2/3,1)\} {( 0 , 1/3 ) , ( 2/3 , 1 )} .
Proof. This prior is supported on K K K , since ∥ s ∥ 2 2 ≤ 4 / 9 \lVert\boldsymbol{s}\rVert_2^2 \le4/9 ∥ s ∥ 2 2 ≤ 4/9 and ∥ b ∥ 2 2 ≤ 1 \lVert\boldsymbol{b}\rVert_2^2 \le1 ∥ b ∥ 2 2 ≤ 1 . Use the t t t -th coordinate context on rounds 1 ≤ t ≤ d 1 \le t \le d 1 ≤ t ≤ d , and zero contexts afterwards. Each round has gain 1 / ( 3 d ) 1/(3\sqrt{d}) 1/ ( 3 d ) , but its trading interval is equally likely to be [ 0 , 1 / ( 3 d ) ] [0,1/(3\sqrt{d})] [ 0 , 1/ ( 3 d )] or [ 2 / ( 3 d ) , 1 / d ] [2/(3\sqrt{d}),1/\sqrt{d}] [ 2/ ( 3 d ) , 1/ d ] . Conditional on the learner’s random seed and previous coordinates, the current interval remains independent and uniform. The nonempty interval [ p t , q t ] [p_t,q_t] [ p t , q t ] can lie inside at most one of these two disjoint intervals, so trade occurs with probability at most 1 / 2 1/2 1/2 . Each of the first d d d rounds therefore loses at least 1 / ( 6 d ) 1/(6\sqrt{d}) 1/ ( 6 d ) in expectation. Summing gives at least d / 6 \sqrt{d}/6 d /6 , and later losses are nonnegative. Averaging over this finite prior selects a fixed pair with at least the same expected loss, even when the learner is given the prior.
Both marginal covariances of this prior are I d / ( 9 d ) I_d/(9d) I d / ( 9 d ) , so Ψ t r ( π ) = 2 d / 3 \Psi_{\mathrm{tr}}(\pi) = 2\sqrt{d}/3 Ψ tr ( π ) = 2 d /3 . Thus the Bayesian lower bound is Ψ t r ( π ) / 4 \Psi_{\mathrm{tr}}(\pi)/4 Ψ tr ( π ) /4 , and the dependence on the trace-square-root potential cannot be improved by more than a constant factor uniformly over priors. The dimension dependence in Theorems 3.2 and 3.4 is consequently optimal.