A Parametric Contextual Online Learning Theory of Brokerage

We thank the reviewer for their insightful comments.

Essential References After reviewing the submission in light of the reviewer remarks, we agree that the mentioned statements could be weakened a bit. We are happy to make the requested changes in the revised version.

Q1 Great question! One could indeed think of the traders in our model as "impatient". They arrive sequentially and permanently exit if unable to (or after completing a) trade immediately. Under such a sequence of "one-shot" interactions, misreporting valuations offers no future strategic advantage, making truthfulness naturally incentive-compatible. Similar "single-shot participation" modeling assumptions are not uncommon in the bilateral trade literature (Myerson and Satterthwaite, 1983; Blumrosen and Mizrahi, 2016; Colini-Baldeschi et al., 2020; Cesa-Bianchi et al., 2021), as they simplify analyses without sacrificing practical relevance (think of large markets where the broker interacts with new traders every day, like future markets, where the median trader participates in at most 4 trades before leaving the market forever; Ferko et al., Retail Traders in Futures Markets, 2024). Still, the reviewer might wonder: "Why not even attempt to systematically analyze recurring traders?" The answer is that the problem wouldn't simply become harder, but unlearnable. The proof of Theorem 5.2 implies, as a corollary, that learning is impossible if valuations are chosen strategically. In fact, it gives the even stronger result that learning is impossible even against oblivious adversaries (i.e., when valuations are deterministic sequences of numbers in $[0,1]$ that are fixed ahead of time and don't vary as a function of the learner's actions). That said, our model still captures some degree of strategic behavior, as we discuss in our answer to Reviewer AKyE regarding Assumption 1.2.

Q2 Good question. Please note that the algorithm SBIP in Gaucher et al. requires additional assumptions to guarantee their stated regret upper bound. In particular, the noise distribution for the seller is assumed i.i.d. across times (while we can deal with time-changing noise distributions), and the same is true for the buyer. Furthermore, note that an algorithm for the classic bilateral trade problem needs to be adapted to the brokerage setting since, in the brokerage problem, sellers' and buyers' roles are not fixed. A way to do this is by interpreting the agent with the lower valuation as a seller and the agent with the higher valuation as a buyer. Hence setting $S_t = V_t \land W_t$ and $B_t = V_t \lor W_t$. However, by doing this, the independence between sellers' and buyers' valuations, as well as the assumption that these valuations are zero-mean perturbations of a linear function of the contexts, both present in the statement of the regret guarantees in Gaucher et al., are lost.

This suggests that their algorithm might not yield sublinear guarantees in our setting. We validate this intuition by running the experiments the reviewer requested and comparing our regret with theirs. As we suspected, their algorithm applied to our setting suffers linear regret, while our Algorithm 1 grows at the theoretical rate of $O(\sqrt{T})$ we proved; see picture in anonymized link: https://i.ibb.co/MkXr19t4/plot.jpg.

The experiments were run for time horizons $T = 1000, 2000, \cdots, 10^4$ for $20$ simulations for each time horizon. At these time steps, the algorithms are tuned by using the parameters prescribed by the respective theories for each specific time horizon, and the corresponding regret is plotted. The dimension $d$ is set to $10$, the noise is uniform in $[-1/4,1/4]$, the unknown vector $\phi$ is picked at random in the $d$-dimensional simplex, while contexts are an i.i.d. process drawn at random in $[1/4,3/4]^d$.

We remain available for clarifications in case we missed something or if something needs further explanation. If our response convinces the reviewer, we'd kindly ask them if they would consider adjusting their score accordingly.

We thank the reviewer for carefully reading the paper and for their kind words! Thanks also for spotting the typos ($\xi_{t} \rightsquigarrow \xi_{t,\theta}$ and $\zeta_{t} \rightsquigarrow \zeta_{t,\theta}$) on Line 407. We will correct them in the revised version.

It is our understanding that no further clarification or comment is required from us at the moment, but of course, we remain available to provide them upon request.

We thank the reviewer for their review of our work and the comments on our submission.

We are pleased to read that the reviewer evaluates positively the soundness of our setting, the correctness of our results, and our discussion of the relevant related literature.

It is our understanding that no further clarification or comment is required from us at the moment, but of course, we remain available to provide them upon request.

We thank the reviewer for their insightful comments.

Additional references We thank the reviewer for bringing the two additional references to our attention. We will add them to the revised version. Regarding one-sided problems (like auctions or dynamic pricing), no techniques we are aware of can be directly applied to or give clear insights into two-sided problems (like our brokerage problem) other than high-level online learning ideas (like constructing hard lower-bound instances by hiding slightly better actions in an appropriately constructed set of "hard-to-distinguish" actions). If the reviewer has any specific references in mind, we are happy to add them to the revised related works section. If they want us to add a concise part on related one-sided problems (like auctions or dynamic pricing), we can do that too.

With Assumption 1.2, we aimed to capture the variability of individual preferences rather than systematic strategic behavior around a target quantity. The assumption is consistent with economic models where the "market price" is the notion that aggregates strategic behaviors, asymmetric information, and biases, so that deviations from the market price reduce to unbiased residual noise once strategic behaviors are reflected in the market price itself. In other words, the market price does not represent an asset's inherent value but the market participants' average opinion. Importantly, our theoretical results do not require identical distributions across time. The market's opinion can vary arbitrarily (even adversarially) over time, and the noise distributions too (representing periods where opinions are more or less aligned). The only concept that remains stationary is that the market participants' average opinion determines assets' "market values".

We agree that altering this assumption by allowing systematic biases or strategic deviations around a notion of "inherent value" would be an interesting alternative path. We will mention this future research direction in the conclusions section and thank the reviewer for raising this point!

Assumption 1.1 (Market values and contexts) is indeed an assumption on market values and contexts. A natural and common special case in which this assumption holds is when $|| \phi ||_1 = 1$, i.e., when $\phi$ is an unknown vector of weights belonging to the probability simplex, representing how important each component of the context vector $c_t$ is to determine the market value at round $t$ (with the boundary cases being $\phi_i = \mathbb{I}$ {$i=j$}, for some $j$, i.e., all the information necessary to reconstruct the market value is contained in a component $j$, or $\phi_i = 1/d$ for all $i$, i.e., all components are equally as informative). In this case, $\langle \phi, c_t \rangle \in [0,1]$ for all $t$. By Holder's inequality, this can be further generalized by assuming that $||\phi||_p \le 1$ and $||c_t||_q \le 1$ (where $q$ is the Holder conjugate of $p$), which is just another way of expressing boundedness of the vectors. Instead of fixing one of these specific assumptions, we opted for the most general case where only the property $\langle \phi, c_t \rangle \in [0,1]$ is assumed. Note that this assumption is merely for the sake of consistency (it is intuitive to model valuations and market prices all belonging to the same set $[0,1]$), but the same algorithm works, and the same analysis yields the same rate (up to a factor of $d$) if market prices are in $[0,d]$. Thus, our core theoretical insights remain intact up to minor technical adjustments if this assumption is lifted.

Assumption 1.2: $V_t, W_t \in [0,1]$
For $V_t = m_t + \xi_t$ and $W_t = m_t +\zeta_t$ to be bounded in $[0,1]$ for all $t$, the noise random variables $\xi_t$ and $\zeta_t$ need to be bounded in $[- m_t , 1 - m_t]$. A sufficient condition for this to happen is to assume that $m_t \in [a,b]$, with $0<a<b<1$. This is simply stating that the value of the assets traded is never 0 (in real life, if the asset is, e.g., some stock of a company, then $m_t = 0$ only if the company goes bankrupt, in which case, of course, people would not trade the stock) or 1 (which is equally as natural since the fact that prices are normalized in $[0,1]$ means that $1$ represents an upper bound on the largest amount of money that traders would spend to exchange an asset). Note that this boundedness condition does not conflict with the zero-mean assumption but simply ensures that valuations are always interpretable as prices within the normalized range $[0,1]$.

If, in light of this discussion, the reviewer agrees that the assumptions we made (Assumptions 1.1 and 1.2) do not significantly restrict the general applicability of our theory, we'd kindly ask them if they would consider adjusting their score accordingly. We remain available for clarifications in case we missed something or if something needs further explanation.