An Online Learning Theory of Trading-Volume Maximization

Related work

We thank the reviewer for pointing out the additional related work. We will add them to the revised version. We are also open to expand the beginning of the related work section as suggested. We agree that it is currently a tad too compressed.

Q1. Same distribution

The key difference from the classical bilateral trade problem is that here, there are no designated "buyers" and "sellers" populations, but a single "traders" population exists. We elaborate on this in the general answer, as other reviewers asked similar questions. Please, check it out and if you have any further questions, do not hesitate to ask!

Q2. Prior work considering the total number of trades as the performance measure

To the best of our knowledge, we are the first to analyze this performance measure. Anecdotally, from the moment bilateral trade problems started to get traction in the online learning community, this performance measure has been brought up many times in conferences/workshops/seminars in which bilateral trade works have been discussed. This is what originally motivated us to attempt investigating it.

Q3. Impact

In terms of impact, the aspect we feel most strongly about is that trading-volume maximization drives more fairness in trading because it does not sacrifice traders who live off small margins. Another positive aspect where trading volume differs from gain from trade is that it is an observable metric, which can be quantified without the traders revealing their valuations and, as such, can be more transparently tracked. As an additional positive side-effect, maximizing trading volume leads to consistent regret minimization speed-ups (i.e., increased efficiency in maximizing the objective) that can't be otherwise obtained if the metric is the gain from trade. (E.g., in the $2$-bit feedback setting, it is possible to minimize the regret at a logarithmic rate, exponentially faster than the corresponding $\sqrt{T}$ when the objective is the gain from trade.)

Another aspect of our work that we hope will inspire future research is the care of having lower bounds that match in all relevant parameters. Most notably, optimality with respect to the Lipschitz constant of the cdfs is seldom studied, as there are no standard techniques that allow to derive it and require ad hoc analyses depending on the variants of the problem at hand.

Technical challenges

We appreciate the reviewer’s observation regarding the simplicity of the high-level algorithmic ideas, but we see this as a strength rather than a weakness of our work. Presenting simple and intuitive ideas was possible only after extensive refinements and it is not necessarily indicative of a lack of technical challenges. The process of identifying the right approach was not straightforward, but we understand that presenting the final algorithms and analysis in a clear and accessible manner inevitably conceals the underlying development process, which was far from trivial.

Moreover, even for intuitive algorithmic ideas, proving that their guarantees are optimal was challenging. We hope the reviewer acknowledges that the proofs of both the upper and lower bound guarantees, which establish the optimality of these algorithms, required a nuanced and technically demanding analysis.

Extensions

The reviewer also expressed curiosity about potential directions to extend our work.

$\alpha$-regret

To begin with, the reviewer inquired about what can be said if the notion of regret is weakened to $\alpha$-regret.
We note that $\alpha$-regret is a meaningful benchmark only in scenarios where the problem is unlearnable under the standard regret framework. In our setting, this occurs in the $2$-bit feedback scenario when the Lipschitz constant of the cumulative distribution function can vary with the time horizon (or when the cdf is not Lipschitz), as we proved that the problem is unlearnable in this case (Theorem 7).
To illustrate why meaningful $\alpha$-regret guarantees are unattainable for any $\alpha$ in this case, we provide the following intuitive argument. Consider a highly concentrated valuation density for the traders, such as the normalized indicator function $f_{r,\varepsilon}$ of an interval centered at $r$ with length $\varepsilon$. For any algorithm, we can find a suitable $r$ such that the algorithm requires at least $\Omega(\log(1/\varepsilon))$ queries to locate the region where the density mass is concentrated. During this period, no trades occur, resulting in zero gain for the algorithm in these rounds.
In contrast, a trader with knowledge of the underlying density $f_{r,\varepsilon}$ could post $r$ immediately, achieving a trading probability of $1/4$. Consequently, for any time horizon $T$ and any algorithm, there exist some $r$ and sufficiently small $\varepsilon$ such that no multiplicative constant $\alpha$ can bridge the gap between the learner’s earnings (zero) and those of an oracle with knowledge of the distribution ($T/4$).

$1$-bit feedback

The reviewer also inquired about the case where, after each interaction, the learner has access only to a single bit of feedback indicating whether a trade occurred at the proposed price.

We did not consider this type of feedback in our work because it is arguably less relevant than the $2$-bit feedback (corresponding to posted-price mechanisms) and full feedback (corresponding to direct revelation mechanisms), which are by far two most studied settings in the economics literature. Additionally, it is difficult to envision real-life scenarios where the broker has access only to a binary indicator of whether a trade occurred, rather than the two individual responses from the traders with whom the interaction takes place. Nevertheless, we acknowledge that this is an interesting mathematical question.
First, we note that this $1$-bit feedback is inherently less informative than the $2$-bit feedback, which we already proved to be unlearnable when we drop the $M$-Lipschitz cdf assumption. Therefore, we discuss this problem under the assumption that the cdf of the valuations is $M$-Lipschitz. Second, we note that this feedback is still sufficient to reconstruct bandit feedback. Hence, a natural approach in this case could involve discretization: we could build a uniform grid with $K$ price points and use an optimal bandit algorithm, treating these prices as arms. This strategy incurs a regret of at most $\sqrt{KT}$ from the bandit algorithm, along with additional regret from the discretization error. Leveraging our Lemma 1, the fact that $F(m) = 1/2$, and the assumption that $F$ is $M$-Lipschitz, we can bound the regret due to discretization by $\frac{M^2}{K^2}T$. Balancing these terms by choosing $K = M^{4/5}T^{1/5}$ leads to sublinear regret guarantees of order $O(M^{2/5}T^{3/5})$.

We believe that determining whether this algorithm is optimal (for example, by establishing a suitable matching lower bound) is an intriguing question. Notably, as demonstrated in other studies on bilateral trade with a continuum of arms, exotic rates like this could, in principle, emerge, deviating from the standard $\sqrt{T}$, $T^{2/3}$, and $T$ trichotomy observed in finite partial monitoring. We leave this exploration as an interesting open direction for future research.

Dear reviewer,

Please, see the two general answers that address your comments. If you have any further questions, do not hesitate to ask!

Dear Authors,

Thanks for your feedback and responses for my questions. It might be good to add those discussions related to the fairness metric in your revision as they are helpful to motivate the current fairness metric. (Feel free to ignore this) For example, you can add a new section to discuss the implication of why trading-volume maximization can indeed achieve certain fairness. To me, I think this alone is an interesting question to explore in more detail.

Also I feel it may be helpful to add those examples of the OTC market that can motivate the same valuation distribution.

I have increased my score as I am satisfied with authors' response.

Dear reviewer,

Thank you for your kind words. Please, see the two general answers that address your comments. If you have any further questions, do not hesitate to ask!

General Comment #2: Same-distribution assumption

Unlike bilateral trade settings where traders join the market as either buyers or sellers (in which case, it is natural to assume that the populations of buyers and sellers have distinct valuation distributions), in our setting, each trader has no predetermined intent to buy or sell. Instead, they simply hold a valuation for the item on sale and are willing to either buy or sell depending on the price proposed by the broker.

Settings with flexible seller/buyer roles have already appeared in the literature and are prevalent in OTC markets. Think of the stock market, or markets of gems and minerals, but also (perhaps less obviously) agricultural markets, as described in [1]: "Consider, for example, markets for agricultural goods [...]. Participants in agricultural markets [...] may switch between seller and buyer roles depending on individual outcomes, consumption needs, and trading opportunities. [...] A considerable literature in development economics studies agricultural households navigating such decisions (e.g., Singh et al. (1986), Key et al. (2000), Taylor and Adelman (2003), and Barrett (2008))."

In all these markets, there are no two distinct populations of buyers and sellers. There is simply one population of traders.

This naturally leads to the assumption that the traders' valuations come from a distribution modeling fluctuation of the market value of the item on sale.

To elaborate further, the reader might wonder: "What if there are multiple segments of the population, each with its own skewed idea of the market price of the item". If at every round, two (possibly different) population segments are drawn i.i.d. and then the valuations and the two traders are drawn i.i.d. from the (possibly different) valuations distribution of each segment, would our techniques still apply? The answer is yes. To see it, simply note that the setting we investigate is context-free, i.e., we do not assume that any information about the traders that come each round is available to the learner before they propose the current trading price at each round. Without knowing a priori the segment each trader belongs to, writing the expected utility explicitly shows that the problem becomes equivalent to our formulation, where the single distribution is the mixture of all the distributions coming from different segments.

Therefore, the same-distribution assumption in a context-free setting where traders are allowed to buy or sell depending on current market conditions is essentially done without loss of generality.

In a contextual setting, instead, things changes, and different techniques are needed depending on the assumptions relating contextual information to market prices. A (very) recent attempt at investigating a contextual linear model for the brokerage problem can be found in [2].

[1] Sherstyuk et al., Randomized double auctions: gains from trade, trader roles, and price discovery.

[2] Bachoc et al., A contextual online learning theory of brokerage.