We study the role of contextual information in the online learning problem of
brokerage between traders. At each round, two traders arrive with secret
valuations about an asset they wish to trade. The broker suggests a trading
price based on contextual data about the asset. Then, the traders decide to buy
or sell depending on whether their valuations are higher or lower than the
brokerage price.
We assume the market value of traded assets is an unknown linear function of
a $d$-dimensional vector representing the contextual information available to
the broker. Additionally, we model traders' valuations as independent bounded
zero-mean perturbations of the asset's market value, allowing for potentially
different unknown distributions across traders and time steps. Consistently
with the existing online learning literature, we evaluate the performance of a
learning algorithm with the regret with respect to the gain from trade. If the
noise distributions admit densities bounded by some constant $L$, then, for any
time horizon $T$:
- If the agents' valuations are revealed after each interaction, we provide
an algorithm achieving $O ( L d \ln T )$ regret, and show a corresponding
matching lower bound of $\Omega( Ld \ln T )$.
- If only their willingness to sell or buy at the proposed price is revealed
after each interaction, we provide an algorithm achieving $O(\sqrt{LdT \ln T
})$ regret, and show that this rate is optimal (up to logarithmic factors), via
a lower bound of $\Omega(\sqrt{LdT})$.
To complete the picture, we show that if the bounded density assumption is
lifted, then the problem becomes unlearnable, even with full feedback.

我们研究了在经纪人之间的在线学习问题中上下文信息的作用。我们假设交易资产的市场价值是代表经纪人可用的上下文信息的 $d$ 维向量的未知线性函数。我们通过与交易利润相关的遗憾来评估学习算法的性能，并提供了相应的遗憾界限。

经纪的情境在线学习理论

A Contextual Online Learning Theory of Brokerage

We explore brokerage between traders in an online learning framework. At any
round $t$, two traders meet to exchange an asset, provided the exchange is
mutually beneficial. The broker proposes a trading price, and each trader tries
to sell their asset or buy the asset from the other party, depending on whether
the price is higher or lower than their private valuations. A trade happens if
one trader is willing to sell and the other is willing to buy at the proposed
price. Previous work provided guidance to a broker aiming at enhancing traders'
total earnings by maximizing the gain from trade, defined as the sum of the
traders' net utilities after each interaction. In contrast, we investigate how
the broker should behave to maximize the trading volume, i.e., the total number
of trades. We model the traders' valuations as an i.i.d. process with an
unknown distribution. If the traders' valuations are revealed after each
interaction (full-feedback), and the traders' valuations cumulative
distribution function (cdf) is continuous, we provide an algorithm achieving
logarithmic regret and show its optimality up to constant factors. If only
their willingness to sell or buy at the proposed price is revealed after each
interaction ($2$-bit feedback), we provide an algorithm achieving
poly-logarithmic regret when the traders' valuations cdf is Lipschitz and show
that this rate is near-optimal. We complement our results by analyzing the
implications of dropping the regularity assumptions on the unknown traders'
valuations cdf. If we drop the continuous cdf assumption, the regret rate
degrades to $\Theta(\sqrt{T})$ in the full-feedback case, where $T$ is the time
horizon. If we drop the Lipschitz cdf assumption, learning becomes impossible
in the $2$-bit feedback case.

通过在在线学习框架中的交易者之间进行经纪，我们研究了经纪的关键问题。我们探索了经纪机构如何最大限度地提高交易量，并分析了对于交易者来说最优的交易策略和遗憾率。

在线学习中的交易量最大化

Trading Volume Maximization with Online Learning

We investigate brokerage between traders from an online learning perspective.
At any round $t$, two traders arrive with their private valuations, and the
broker proposes a trading price. Unlike other bilateral trade problems already
studied in the online learning literature, we focus on the case where there are
no designated buyer and seller roles: each trader will attempt to either buy or
sell depending on the current price of the good.
We assume the agents' valuations are drawn i.i.d. from a fixed but unknown
distribution. If the distribution admits a density bounded by some constant
$M$, then, for any time horizon $T$:
$\bullet$ If the agents' valuations are revealed after each interaction, we
provide an algorithm achieving regret $M \log T$ and show this rate is optimal,
up to constant factors.
$\bullet$ If only their willingness to sell or buy at the proposed price is
revealed after each interaction, we provide an algorithm achieving regret
$\sqrt{M T}$ and show this rate is optimal, up to constant factors.
Finally, if we drop the bounded density assumption, we show that the optimal
rate degrades to $\sqrt{T}$ in the first case, and the problem becomes
unlearnable in the second.

在线学习视角下研究交易者间的经纪服务，在不同情况下，通过算法实现不同的后悔率和界定密度。