An Online Learning Theory of Trading-Volume Maximization
Authors: Tommaso Cesari
Roberto Colomboni
Venue: ICLR 2025 Poster (2025)
Keywords: regret minimization
bilateral trade
online learning
fairness
theory
Primary area: learning theory
TL;DR: We study the online learning problem of brokerage between traders where the objective is to maximize the total number of trades

Abstract: 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.
This classical notion of reward can be highly unfair to traders with small profit margins, and far from the real-life utility of the broker.
For these reasons, 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 constants.
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 its near-optimality.
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.

Published as a conference paper at ICLR 2025
AN ONLINE LEARNING THEORY OF TRADING- VOLUME MAXIMIZATION
Tommaso Cesari EECS
Roberto Colomboni
DEIB Dept. of Computer Science
University of Ottawa Ottawa, Canada
Politecnico di Milano / University of Milan
Milano, Italy
tcesari Setaariuuotee twwt
robertoccolomeen @po imi.it
ABSTRACT
We explore brokerage between traders in an online learning framework. At any round f, 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 the sum of the traders' net utilities after each interaction. This classical notion of reward can be highly unfair to traders with small profit margins, and far from the real-life utility of the broker. For these reasons, 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 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 (edf) is continuous, we provide an algorithm achieving logarithmic regret and show its optimality up constants. If only their willingness sell or buy at the proposed price is revealed after each interaction (2-bit feedback), we provide achieving poly-logarithmic regret when the traders' valuations edf is Lipschitz and show its near-optimality. We complement dropping the regularity assumptions on the unknown traders' valuations cdf. If we drop the continuous edf assumption, the regret rate degrades to @( in the full-feedback case, where T is the time horizon. If we drop the Lipschitz edf assumption, learning becomes impossible in the 2-bit feedback case.
algorithm
results by analyzing the implications
INTRODUCTION
In modern financial markets, Over-the-Countee (OTC) trading platforms have emerged as dynamic and decentralized hubs, offering diverse alternatives to traditional exchanges. In recent years, these markets have experienced remarkable growth, solidifying their central role in the global financial ecosystem: OTC asset trading in the US surpassed 50 trillion USD in value in 2020 (Weill 2020).
with an upward trend documented since 2016 (www.bis.org 2022).
Brokers play crucial role in OTC markets. Beyond acting as intermediaries between traders, they utilize their understanding of the market to identify the optimal prices for assets. Additionally, traders in these markets often respond to price changes: higher prices usually lead to selling, while lower prices typically result in buying (Sherstyuk et al.) 2020). This adaptability appears across various asset classes, including stocks, derivatives, art, collectibles, precious metals and minerals, energy commodities (like gas and oil), and digital currencies (cryptocurrencies) (Bolić et al. 2024).
Our study draws inspiration from recent research analyzing the bilateral trade problem from online learning perspective (Cesa-Bianche Bianchi et al. 2021 Azar et al. 2022 Cesa- BiaaaBi et al., 2023 2024a build insights from Bolie et al. (2024). which addresses the brokerage problem in OTC markets where traders may decide to buy or sell their assets depending on prevailing market conditions.
Bolié et al.] 2024 Bernascooi et al. 22024] Bachoc et al. 2024a b). In particular,

---

Published as a conference paper at ICLR 2025
1.1 MOTIVATIONS FOR CHOOSING TRADING VOLUME AS REWARD
Previous works have entirely focused on scenarios where brokers aim at maximizing the so-called cumulative gain from Irade-the sum of the net utilities of the traders over the entire sequence of interactions with the broker. This classical approach has the two following pitfalls.
Traders' Perspective. Gain-from-trade maximization can cause unfairness in settings where the majority of traders make living off of small margins (e.g.. in micro trading or trading), and only handful of high-payoff trades have the potential occur. In these cases, gain- from-trade maximization can lead to sacrificing the majority of the population in favor of small minority of traders that are lucky enough to be paired with people that are willing to be greatly underpaid for the good sale. In contrast, trading-volume maximization gives the same dignity to all traders, granting everybody the same opportunity to trade, independently of their buying power. For striking concrete example of this pitfall, see Section 3
Broker's Perspective. From the broker's 's perspective, too, might not be as beneficial to potentially miss out traders' exchanges by maximizing the gain from trade, given that, typically, brokers only earn when trades occur. For example, in settings where traders have to pay a small fee for each trade, is clear that the broker's ultimate goal is maximize trading volume. Another example where maximizing trading volume is superior to maximizing the gain from trade is the one discussed in the Trader's Perspective paragraph (and Section 3}. In this case, gain-from-trade maximizing broker would risk alienating the vast majority of the population which, realistically, would end up leaving broker that does not give them trading opportunities, consequently hurting the broker's bottom line.
For these reasons, in this work, we aim at providing strategies that boost the trading volume by maximizing the number of trades in the broker-traders interaction sequence.
1.2 SETTING
In what follows, for any two real numbers a, b, we denote their minimum by as b and their maximum by a v b. We now describe the brokerage online learning protocol. For any time t = 1,2....
Two traders arrive with their private valuations Vzc-1 and V22
The broker proposes trading price P.
If the price P. is between the lowest valuation V2.-1 V22 and the highest valuation V2.-1 Vir -er-mannng the trader with the lower valuation is willing to sell at P, and the trader with the higher valuation is willing to buy P- transaction occurs with the valuutival trader purchasing the asset from the lower-valuation trader at the price Pa
The broker receives some feedback
As commonly assumed in the existing bilateral trade literature, we assume valuations and prices belong 10. While previous literature aims at maximizing the cumulative gain from trade- defined as the sum of traders' net utilitie!! in the whole interaction sequence-our objective is to maximize the number of trades. Formally, for any U1, U2 & [0, 1]. our utility posting price p when the valuations of the traders are V1 and 0/2 is
g(p, 01, v2) == (u) A 02 $ sps V 02]
The goal of the broker is to minimize the regret, defined, for any time horizon T' N, as
T (GG
-G..)))
R = sup E
PE[U.1]
A=1
where Gz(g) == g(g, V2--1, Vi2)) for all q [0. 1] and e N. and the expectation is taken over the randomness present in (V.)te and the (possible) randomness used by the broker's algorithm to generate the prices (P:)teN.
Forrmllly for any P. U1, e [0, 1]. the gain from trade of price p when the valuations of the traders 11 and vp is GFT(p, 21, x2) = (vi Va- vi A T 02 S S 0s v2).
2

---

Published as a conference paper at ICLR 2025
M -LLiscchitz
Continuous
General
Full
(2(1n T) Thm
(InT) Thm
e ((VT)
Thm
2-Bit
In ((I((M)) Thm 3
((T)) Thm
((T)
Table I: Overview of all the regret regimes: In T (cyan), (mMM)) (green), VT (yellow), and T (red), depending on the feedback (full 2-bit) and the assumption on the edf (M -LLissschitz, continuous, or no assumptions).
As in Bolić et al. 2024), we assume that traders' valuations V. V1, V2,... are generated i.i.d. from an unknown distribution
practical assumption for large and stable markets
Finally, we consider the following two different types of feedback commonly studied in the online learning bilateral trade literature:
Full-feedback. At each round t, after having posted the price Pt. the broker has access the traders' valuations Vz-1 and V22
2-bit feedback. At each round t, after having posted the price Pt, the broker has access to the indicator functions T(V2-1 1 P.) and [(V2. s P.).
The full-feedback model draws its motivation from direct revelation mechanisms, where the traders disclose their valuations V2-1 and V22 before each round, but the mechanism has access to this information only after having posted the current bid Pt (Cesa-Bianch) et al. 2021 2024a).
The 2-bit feedback model corresponds to posted price mechanisms, where the broker has access only to the traders' willingness to buy or sell at the proposed posted price, and the valuations V2--1 and V22 are never revealed.
1.3 OVERVIEW OF OUR CONTRIBUTIONS
In the full-feedback case, if the distribution of the traders' valuations has continuous edf, design an algorithm (Algorithm D suffering O(I T)) regret in the time horizon T (Theorem [ and
provide matching lower bound (Theorem 2 We complement these results by showing that dropping the continuous cdf assumption leads to worse regret rate of S (T) (Theorem and design an algorithm (Algorithm 3 achieving O O(VT) regret (Theorem
In the 2-bit feedback case, if the edf of the traders' valuations is M Lipschhih we design an algorithm (Algorithm 2) achieving regret ((n(MT) In T) (Theorem 3) where T is the time horizon, and
provide near-matching lower bound 22(1n (MT) (Theorem 4 We complement these results by showing that the problem becomes unlearnable if we drop the Lipschitzness assumption (Theorem 7
For full summary of our results, Table 1
1.4
TECHNIQUES AND CHALLENGES
Online learning with a continuous action domain and full-feedback is usually tackled by discretizing the action domain and then playing an optimal expert algorithm on the discretization, or by directly running exponential weights algorithms in the continuum (Maillard & Munos 2010: Krichene et al.) 2015 Cesa-Bianchi et al.) 2024b). These approaches require that the (expected) reward function is Lipschitz and lead to a regret rate of order Ö(VT). In contrast, our expected reward function not Lipschitz in general. To overcome this challenge, we leverage the specific structure of the problem by proving Lemma [ which enables us to design an algorithm that achieves an exponentially better regret rate of (In T even when the underlying is only continuous. Moreover, we establish a matching Q(In 7') lower bound that, surprisingly, applies even when the reward function is Lipschitz, demonstrating that additional Lipschitz regularity beyond continuity does not contribute to faster rates in this setting. This lower bound construction is particularly challenging because the shape of the function - (p)) can only be controlled indirectly through the traders' valuation distribution: to avoid exceedingly complex calculations,
hence the associated reward function
For further discussion this assumption, see Appendix

---

In the 2-bit feedback model, we remark that the available feedback is enough to reconstruct bandir feedback. Consequently, when the underlying edf-and hence the expected reward function- M- M-Lipschitz, viable approach is to discretize the action space [0, 1] with K uniformly spaced points and run an optimal bandit algorithm on the discretization. This approach immediately yields a regret rate of order O(MT/K + VKT). This bound leads to a regret of order O 0(M4/37//3) by tuning K = ((M2/81113)) when M is known to the learner, or of order O(MT2/3) by tuning = O(T2()) when the learner does not possess this knowledge. In contrast, we exploit the extra information provided by the 2-bit feedback and the intuition provided by Lemma[]je to devise a binary search algorithm achieving the exponentially better rate of O (In( MT) In T),, with the additional feature of being oblivious to .M. Our corresponding lower bound shows that this rate is optimal (up Published as a conference paper at ICLR 2025
extra care is required in selecting appropriate instances. Even then, needed subtle and somewhat intricate Bayesian argument to obtain the lower bound.
In T factor), demonstrating through an information-theortti argument that some sort of binary search is essentially necessary step for optimal learning.
1.5 RELATED WORK
Bilateral trade was originally studied a one-shot setting where a broker has to devise mechanism to make buyer and seller trade, and classical properties like incentive compatibility, individual rationality, budget balance, and efficiency were investigated. Since the pioneering work of Myerson and Satterthwaite and their celebrated impossibility result (Myerson & Satterthwaite 1983). the
study of bilateral trade has grown sigmificantly, particularly from a game- theoerthe and approximation perspective (McAfee [2088]
& Mizrahi 2016 Brustle 2017; 2017; Baldeshh et al. | [abaioff et al. 2020; Ditting et al.) | [021] Deng et al.
et al. [2016]
et al.
2022
Kang et al. 2022 Fei 2022 Archbold et al. 2023 Xu et al. 2024). For a comprehensive
overview, refer to BiascB et al. (2024a).
In recent years, the focus has expanded to include online learning settings for bilateral trade. Given their close relevance to our paper, we concentrate our discussion on these works.
In Cesa-Bianchi et al. (2021) Azar et al. (2022); Cesa-Biaacci et al. (2024a] 2023); Bernasconí et al. (2024); Cesa- Bianchi et al. (2024b), the authors examined bilateral trade problems where the reward
function is the gain from trade and each trader has a fixed role as either a seller or a buyer.
In BessaBiaanchi et al. 2202I) the authors investigated a scenario where seller and buyer valuations form two distinct i.i.d. sequences. In the full-feedback case, they achieved regret bound of Ö(VT) which was later refined to O(VT) in Cesa- Besa-Bianchh et al. (2024a). They also demonstrated a worst- case regret of R(VTT) even when sellers' and buyers' valuations independent of each other and their edfs are Lipschitz. For the 2-bit feedback scenario under i.i.d. valuations, (Caiiioonn,,CCaa--a Bianchi et al. (202T) proved that any algorithm must suffer linear regret, even under either the M-Lippshitzz joint edf assumption or the traders' valuation independence assumption. However, when both conditions are simultaneously satisfied, they proposed an algorithm achieving a regret rate of Ö( /3223))22 later refined to O (M33332233 in Cesa-Bianchi et al. (2024a). Cesa-Bianchi et al. 2021) also established a worst-case regret lower bound of 2/34 in this case, which, however, does not display any dependence on M.
[Cesa-Bianchi
Cesa-Bianchi et al. 1202 2024a) also showed that the adversarial bilateral trade problem is un- learnalle even with fell-feedback. To achieve learnability beyond the i.i.d. case, (Cesa-Bianchi et al.) (2023) 2024b) explored weakly budget-balanced mechanisms, allowing the broker to post differ- ent selling and buying prices as long as the buyer pays more than what the seller receives. They demonstrated that learning can be achieved using weakly budget-balancee mechanisms in the 2-bit feedback setting at regret rate of (M/T8/4 when the joint seller/buyer edf may vary over time but is M- M-Lipschitz. Furthermore, for the same setting, they provided a (2(3/11) matching lower bound in the time horizon, even when the process is required to be i.i.d., but their lower bound does not feature any dependence on M. Azar et al. (2022) investigated whether learning is possible in the adversarial case by considering a-regret, achieving G(VT) bounds for 2-regret in full-feedbach and Ö(73/4) upper bound in 2-bit feedback. Following another direction, Bernasconi et al. 2024)
4

---

Published as a conference paper at ICLR 2025
explored globally mudget-balancee mechanisms in the adversarial case, showing ((VT) regret rate in full-feedback and a O(T3/4) rate in the 2-bit feedback case.
The closest to our work is Bolić et al. 22224) ) where the authors studied the same i.i.d. version of our trading problem with flexible seller and buyer roles, but with the target reward function being the gain from Irade. Under the M- M-Lipschitz edf assumption, they obtained tight ( In regret in the full-feedback case. Surprisingly, in the same full-feedback case, but using different reward function, we achieve a @(In 7) regret rate even when the edf is only continuous: in our case, the additional Lipschitz regularity does not offer any speedup once the continuity assumption is fulfilled.. Furthermore, under the M M-Lipschitz edf assumption, [olić et al. (2024) proved sharp rate of O (VMM)) in the 2-bit feedback case. Interestingly, using our different reward function, we achieve an exponentially faster upper bound of (In( (In(M) In In,, which is tight up to a In factor. If the Lipschitz edf assumption is removed, the learning rate for both our problem and the one in [Bolć et al. 2024)) degrades to ((vT) in the full-feedback case, and the problem becomes unlearnable in the 2-bit feedback case.
THE MEDIAN LEMMA
In this section, present the Median Lemma (Lemma [ simple but crucial result for what follows, and the key upon which our main algorithms are based. At a high level, Lemma] states that broker who aims at maximizing the number of trades should post prices that median of the (unknown) traders' valuation distribution and the instantancous regret which the broker incurs by playing any price is (proportional to) the square of the distance between the median and the price, if distances are measured with respect to the pseudo-metris induced by the traders' valuation edf.
close possible the
Lemma (The median lemma). the edf F of continuous, then, for any t é N and any p [0. 1].
and 1 ]-B[GG(o)] - (--
E (GG()))=2(())
In particular, the function p Gp)) is maximized at any point m é [0, 1] such that F F(m)
Before presenting the proof of Lemma just remark that points m e [0,1] satisfying F(m) 1/2 do exist by the intermediate value theorem, because F(0) 0, F(1) = 1, and F is continuous.
Proof. For each é N and each p [0, 1], we have that
[[G) IP ( V22-1 s p< V28 u (V2 S sps V2r-1}]
P V22-111 $ p|p[p< V21 P[V2 s p|F[ps (
where the second equality follows from additivity and independence, while in the last equality leveraged the continuity of F to obtain P[p S V | PIp < == F()). To conclude, it is enough to note that, for each p [0, 1] holds that 1/4 F()) F())) F()))
L
3 TRADING VOLUME Vs GAIN FROM TRADE
In this section, we leverage Lemma to show with a formal example that, unlike trading-volume maximizing brokers, sain-from-trade maximization brokers can be heavily biased towards small segments of the population and, as result, end up hurting their own bottom lines.
Assume that the distribution of the traders' valuations V, Vi, V2,... have common density f defined, x 1) +[[1 E s s 1), for some E (0. 1
for all e [0, 1]. by fx) = 1)
At a high level, this population of traders is clustered into two segments: low-valuation cluster that believes that the good sale has value slightly smaller than 1 and high-valuation cluster H that believes the value is slightly smaller than 1. If & 0, the overwhelming majority of the population belongs to the low-valuation cluster T. In this case, will prove that gain-from-tree from-trade maximizing
5

---

Published as a conference paper at ICLR 2025
broker would sacrifice the majority of the population favor trades that include trader coming from the (extremely small) high-valuation cluster H.
Indeed, by Bolić et al. (2024), gain-frome from-trade maximizing broker would post the expectation E[V] 3. contrast, by Lemma| a trade-volume maximizing broker would post the median m = 1-2s of V, which is value roughly in the middle of the low-valuation cluster L.
By posting the expectation, the probability of having trade is, for all e N, P P2222-1 A V2 s V2--1 v V2.) = 2(1 E)E. which is close to zero when E x 0.
In contrast, by posting the median, the probability of having a trade is, for all e N, (P A V2r m S V2-1 V2[] 2. which is always bounded away from zero, irrespectively of
This shows two ways in which (unlike a trade-volume maximizing broker) gain-from teo---froorrreee max- imizing broker is biased towards favoring the high valuation cluster H. First, they are willing to accept that only negligible fraction of the population will trade. Second, being [[[] = they only (with probability 1) allow trades where one of the two traders comes from the high-vafuation cluster H, resulting in only the high-valuation trader making large profit, while the low valuation trader is left with a profit of order e & O, even in the low-probability event where they are given the opportunity to trade. It is easy to imagine that, in real life, such bias would cause the low-valuation traders in to leave the broker, in turn greatly reducing the broker's ' own profit.
For further discussion on the trading- trading-volume metric, Appendix A
4 FULL-FEEDDBCK
We now investigate how the broker should behave to maximize the number trades in the full- feedback case where after each interaction the traders' valuations are disclosed. We begin by studying the full-feedback case under the continuous edf assumption. In this case, taking inspiration from Lemma D a natural strategy is play the empirical median, which leads Algorithm
Algorithm 1: Follow the Empirical Median (FEM)
Post Pj = 1/2 and receive feedback Vi, V2;
for time = 2, do
(t-1)) ((9) 2(--D) where v-(1) ((-1)
(2((-11)
Post the empirical median P; order statistics of the observed sample Vi,..., V2(1-1). and receive feedback V2 V2si
2(t- 2(e-1)
are the
The next theorem leverages Lemma to show that Algorithm suffers regret O(I T) when the traders' valuation edf is continuous.
Theorem 1. If y has a continuous odf F, the regret of FEM satisfies, for all time horizons T e N,
7 21 (1+ 1 (1+In(T-1))
Rr
2 2
Proof. Without loss of generality, we can (and do!) assume that 7 2 2. Then, we have
1 max E Rr S
T - E Σ G.()))
T
T Σ (1 11 F(P)) )1
(p)
+2
pe [c
Now, let m [0, 1 be such that F(m) 1/2, and let V be random variable whose distribution is v, independent of V1, ....... Then, for any e N such that t 2 2 we have
E 1 n(P)))
[P(mms V P.))
[P(P PPPIP)
P.))²] +IT)

---

Published as a conference paper at ICLR 2025
Now, for the term (I), leveraging the fact that V and Pa are independent of each other, together with the Minkowski's s integral inequality (see, e.g., (Stein 1970 Appendix A.1)), we have:
V(T E [ V V PP) P.)) B
B [ V [v]
E [e[Vmmss = S mm
S(m..) VPi= S P:] dx(x)) = (+)
For each e [0, 1] and for any N, let (x) = (s s V.J. and notice that B1 (3). B2 is
an i.i.d. sequence of Bernuulli random variables of parameter 1 F(x). Let v
(2((-1))
((t-1) ((-11)
be the order statistics of the observed sample , V2((11)) For any x [m, 1]. observing that
F(x) 2 0 and P|æ s Pi] s P x Hoeffding's 's inequality obtain
(t)
1(t-1) s IP Σx-1 2((1-)) (=(2)22-1 we can leverage
1(-1))
2(1-1) B₂(x)
t-1 2(t- (1 - F(x))
P[* s P
= Σ (,
Σ
2(t
2(L-1) (x
= P Σ 2)
(( - (())0(([00))))))
2
from which, by the change of variable formula (Revuz & Yor 2013 follows also that
Proposition 4.10, Chapter 1),
exp -4(1- 1) (v[00.]))] 1) du(x)= ['] expl -2(1 1-((-11) ) du (+) J [m,1] V
1/2
1
Lo0 00 exp (-r²) dr V 1
/2(t-1) 1)
2 Vi-T
and hence (1) S
x 8(1-1)
Analogously, we can prove that (11) S 8(1-1)
x Hence,
Rr S - --1
1 1 1
Σ S ds 1-1 22222 E2
1 x -
T-1
1
ds
(1+I((T-)) O
2 E2
t-1
222
2
2
We now establish the optimality of FEM by demonstrating matching 2(I 7) regret lower bound. We remark that this result holds even when competing against underlying distributions that have 2-Lipschitz edf, thus proving the optimality of FEM even under the Lipschitz edf assumption.
Theorem 2. There exist two numerical constants eı and eg such that, for any time horizon T 2 C2. the worst-case regret of any full-feedbuck algorithm satisfies
sup Rr cnln, DcD2
where Ry is the regret at time T of the algorithm when the i.i.d. sequence of traders' valuations follows the distribution v, and D2 is the set of all distributions that admit a 2-Lipschitz cdf.
Due to space constraints, we defer the (long and technical) proof of this result to Appendix and only present a short, high-level sketch here.
Proof sketch. In the proof, we build family of 2-Lipschitz edfs F. parameterized by 8 [0, 1]. so that if two instances are parameterized by and e' respectively, then their medians are O(E ((s--e)) e'l)- away from each other (Figure []]. The high-level idea
leverage Bayesian argument to show that if the underlying instance FE such that E is drawn uniformly random in [0, 1]. then, at round the broker cannot reliably determine prices that are much closer than 1/ /E to the corresponding median m. when distances are measured with respect to the metric induced by the edf Fr. This, together with key Lemma leads to the conclusion.
7

---

Published as a conference paper at ICLR 2025
@ - =9Rt
2(1 -
2(1 )
1
2g
28
0 1/8
7/8
0 7/s
O(|= =')) 7/8
Figure I: Qualitative plots of the densities fe, for (left) and corresponding expected rewards (right) used in the proof of Theorem 2 for two values 6, Note that the difference reward by posting a price that optimal for one instance when the actual instance is e @(l - =²1)..
5 B-BIT FEEDBACK
We start the study of the 2-bit feedback case under the assumption that the traders' valuation distribution admits a Lipschitz cdf F. The algorithm following observation: by posting any price p. the broker has access to two noisy realizations of F()). Recalling that Lemma suggests tracking the median of F (i.e., a point at which F(m) 1/2), and since F is non-decreasing function, we can proceed using a natural binary search strategy to move toward the median. This can be done in epochs: in each one, we repeatedly test (dyadic) price until the first time we can confidently decide that the median is to the left or right of the current price.
propose (Algorithm ( is based the
Algorithm 2: Median Binary Search (MBS)
Input: Confidence parameter 8 é (0, 1), time horizon n N; Initialization: Q1 == 2, 1,
while time do
= Let s = 0, Yr,. == 0, 1
while time t do
Post P, = Q, and receive feedback 2( $ P,), 1(22 Pt);
Update
Yr,- -, T[ ((22-1 Pt) [(22 $ Pt), 1;
if ! Y
lm(2/))
<
then let Q++1 = Q++1 + gml 8, = = 8, + 1, and break;
2a
else if ! V
(2/8))
then let Q7+1 Qr+1 2 87 ==
1, and break:
7,8
25
We now show that a suitably tuned Algorithm has regret guarantees of (TT (T() In particular, stress that the tuning of Algorithm 2 does not need prior knowledge of M. Due to space constraints, we defer the full proof of the next result to Appendix
Theorem 3. If has M M-Lipschitz cdf F for some M 1, then, for all time horizons T e N, the regret of MBS tuned with parameters = 2/T and n T satisfies
RT < + 6 log (MT) In(T).
Proof sketch. The proof is based on the following observations. First, during an epoch where price p is tested, given that one has distinguish if the parameter F(p) of sequence of Bernoulli random variables is bigger or smaller than 1/2, concentration argument shows that the duration of this epoch most (In(1
where é is the confidence parameter. Second, by Lemma the broker regrets 2 FF())) by playing a price p. and hence the total regret of an epoch where the broker tests p is at most (In(1/8)) We then use the fact that the F' is M-Lipschitzz to prove that, after at most Olog, (MT)) epochs, the cumulative regret that the algorithm suffers from that point onward is constant, and conclude by showing that the tuning of 8 leads to the stated guarantees. Li
We now show that Algorithm 2 optimal, up to a multiplicative T term. Due to space constraints, defer the full proof of this result to Appendix H
8

---

Published as a conference paper at ICLR 2025
Theorem 4. There exist two numerical constants er and 02 such that for any M 16 and any time horizon T 2 02 (M), the worst-case regret of any 2-bit feedback algorithm satisfies
sup R4 2 In(M))
vcDM
where Ri is the regret at time T of the algorithm when the i...d. sequence of traders' valuations follows the distribution v, and M is the set of all distributions v that admits an M Lipschitz cdf.
Proof sketch. The proof builds a family of distributions, each supported in different region of length M))MM), whose cdfs are M M-Lipschitz. To avoid suffering linear regret the traders' valuations are generated according to one of these distributions, the broker has to detect the corresponding support. To accomplish this task, we show that the broker is essentially forced to solve a binary search problem that needs logz( (M) rounds in each of which the instantaneous regret constant. Noticing that any regret lower bound for full-feedback algorithms also applies to 2-bit feedback algorithms, the In T lower bound Theorem together with the binary search In M lower bound yield lower bound of O maxx(n T, In M)) 22 (2(n(MM))
NON-LIPSCHITZ OR DISCONTINUOUS PDFS
We now investigate how the problem changes if lift the assumption that has Lipschitz or continuous cdf. First, note that when the edf of v is not continuous, Lemma [ and, consequently, the guarantees of Theorem [ no longer hold. Indeed, in general, no full-feedback algorithm can achieve regret guarantees better than VT. As shown in the proof of the next theorem, the reason that our problem contains instances that resemble online learning with expert advice (with 2 experts), which has known lower bound of Ω ((VT).
Theorem 5. There exist two numerical constants eı and 02 such that, for any time horizon T 220 C2. the worst-case regret of any full feedback algorithm satisfies
sup Rr 2cVT.
VED
where Ry is the regret at time T of the algorithm when the i.i.d. sequence of traders' valuations follows the distribution v, and D is the set of all distributions v.
1 8 where, for any R. we denoted by 8, the Dirac's delta probability measure centered at a. Let sV=:)))([-1/ be an independent family such that for each [-1/4, 1/4] the sequence Ve,1, Ve,2.... is i..d.
Proof sketch. For each e E 1-/4, define ug == - 5n 10133 + 1
with common distribution Vg. For each e & [-1/4, 1/4], each & N, and each p E [0, 1]. define Ge,(p) g(P, Ve,21-1, Ve,2). Straightforward computations show that, for each e [-1/4, 1/4] and each N, the function p (E..,.(P) is maximized at 1/3 or 2/3, with any other point having an expected reward that is less than 31/256-away from the minimum expected reward achieved 1/3 or 2/3. Furthermore, for any 8 1/4, and any L N, the maximum is at 1/3 or 2/3 depending on and E (2/3)
2 from T GZ. (1/3)) = Hence, in order not to suffer (1 T) regret, an algorithm has to detect the sign of e. However, standard informitiin-thherrtiicc argument shows that sample of order 2(1/e²) is required order to detect the sign of e. During this period, the best any algorithm can do to play blindly in the set ( {1/3, 2/3). incurring in a cumulative regret
whether or O, given that TE G5 (1/3)
11
11 + +
16
16
which it follows also that T. Gr. (2/3)]
of order ? ( |El) Ω [=]). Overall, any learner has to suffer ? min 1 |E(T)) worst-case
regret, which, by tuning |s| (1/VT)), leads to worst-case regret lower bound of Ω ((VT).
O
We now focus on the upper bound. A closer look at the proof of Lemma | shows that we drop the edf continuity assumption in the Median Lemma, the formula generalizes to
El B(Gx(P)) 2F( F()) F(D)F = V(p),
Vp [0, 1], VteN,
with no assumptions on v, and where F is the edf of v and we defined (p) = rf {p} This suggests the strategy of building an empirical proxy i of To with the feedback available time t, and posting

---

Published as a conference paper at ICLR 2025
prices that maximize v, By replacing the theoretical quantities by their empirical counterparts, for any & N and any p E [0, 1]. we define an empirical proxy for (p) as follows:
1 21
24 Σ
24 Σ 28
1
1 26
1 (p)
2 Σ
IVV s)
Up V.)
T(V
s p)
E
21
21
28
This definition leads to Algorithm
Algorithm 3: Follow the Empirical V (FEV)
Post P1 = and receive feedback V1, V2:
for time = 2.3,... do
Post P. argmmaxp(o..] (p) and receive feedback V2--1, V22i
We now state regret guarantees for Algorithm The proof of the following result (which hinges on showing that V. is uniformly close to Ti with high probability) is deferred to Appendix F
Theorem 6. For all time horizons T N, the regret of FEW satisfies
Ry S1 VI-I.
We conclude by showing that, without the Lipschitz edf assumption, the 2-bit feedback problem is unlearnable. This can be deduced as a simple corollary of the proof of Theorem 4 Specifically, we can obtain a linear worst-case lower bound for any 2-bit feedhack algorithm, even if we assume that the underlying distribution has continuous edf.
Theorem 7. There exist two numerical constants e1 and such that, for any time horizon T 02. the worst-case regret of any 2-bit feedback algorithm satisfies
sup R2 2 ciT,
veD
where Ry is the regret at time T of the algorithm when the i.i.d. sequence of traders' valuations follows the distribution and De is the set of all distributions v that admits continuous edf.
Proof. As a consequence of the last part of the proof of Theorem (see Appendix E. we have that, for any time horizon T 2 4, if we set M 2n, then the conditions M 16 and T 2 log (M) in that proof holds, and hence, any 2-bit feedback algorithm has worst-case regret that is at least 4hn2 M T.gT.
7 CONCLUSIONS AND OPEN PROBLEMS
Motivated by maximizing trading volume in OTC markets, we proposed a novel objective that departs from the classical gain-from-trade reward studied in the bilateral trade literature. For this new problem, we investigated optimal brokerage strategies from an online learning perspective. Under the assumption that traders are free to sell or buy depending on the trading price and that traders' valuations form an i.i.d. sequence, we provided complete picture with matching (up to, at most, logarithmic factors) upper and lower bounds in all the proposed settings, fleshing the role of regularity assumptions in achieving these fast regret rates.
In addition closing the logarithmic In I gap the regret rate of the 2-bit feedback setting, a few other future research directions are to find non-stationary variants of this problem where learning is still achievable, investigate trading volume maximization when traders have definite seller and buyer roles, and explore the contextual version of the problem when the broker has access to relevant side information before posting each price. One could also consider the 1-bit feedback setting, where the learner receives no individual feedback from traders but only observes if trades occurred or not. This a desirable property of the mechanism as it ensures complete privacy regarding the preferences of the traders. Lastly, natural question arising from our unlearnability result in the bit feedback setting is if learning is possible when the objective is weakened to a-regret. We leave the investigation of these intriguing problems to future research.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
TC gratefully acknowledges the support of the University of Ottawa through grant GR002837 (Start-Up Funds) and that of the Natural Sciences and Engineering Research Council of Canada (NSERC) through grants RGPIN-2023- -02-0003-03688 (Discovery Grants Program) and DGECR2023-00208 (Discovery Grants Program, DGECR Discovery Launch Supplement). RC is partially supported by MUR PRIN grant 2022EKNE5K (Learning in Markets and Society), the FAIR (Future Artificial Intelligence Research) project, funded by the NextGenerationFUU program within the PNRR-PP PE- AI scheme, the EU Horizon CLA-202-HUMAN--0 research and innovation action under grant agreement 101 120237, project ELIAS (European Lighthouse of Al for Sustainability).
REFERENCES
Thomas Archbold, Bart de Keijzer, and Carmine Ventre. Non-obvious manipulability for single- parameter agents and bilateral trade. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pp. 2107-2115, USA, 2023. International Foundation for Autonomous Agents and Multiagent Systems.
Yossi Azar, Amos Fiat, and Federico Fusco. An alpha-regret analysis of adversarial bilateral trade. Advances in Neural Information Processing Systems, 35:1685-1697, 2022.
Moshe Babaioff, Kira Goldner, and Yannai A. Gonczarowski. welfare maximization in two-sided markets. In Proceedings the Thirty- First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '20, pp. 2452-2471, USA, 2020. Society for Industrial and Applied Mathematics.
baloo-klemperee-sttlle results for
François Bachoe, Nicolò Cesa-Bianchi, Tommaso Cesari, and Roberto Colomboni. Fair online bilateral trade. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024a.
François Bachoc, Tommaso Cesari, and Roberto Colomboni. contextual online learning theory of brokerage. arXiv preprint 20Xiv:2407.01566. 20244..
François Bachoc, Tommaso Cesari, and Roberto Colomboni. tight regret analysis of non- non-parametric repeated contextual brokerage. In Proceedings of The 28th International Conference Artificial Intelligence and Statistics, Proceedings of Machine Learning Research. PMLR, 03-05 May 2025.
Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Federico Fusco. No-regret learning in bilateral trade via global budget balance. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024.
Liad Blumrosen and Yehonatan Mizrahi. Approximating gains-from-trade in bilateral trading. In Web and Internet Economics, WINE" 16, volume 10123 of Lecture Notes in Computer Science, pp- 400-413, 413, Germany, 2016. Springer.
Natasa Bolić, Tommaso Cesari, and Roberto Colomboni. An online learning theory of brokerage. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, AAMAS '24, pp. 216-224. Richland, SC. 2024. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 9798400704864.
Johannes Brustle, Yang Cai, Fa Wu, and Mingfei Zhao. Approximating gains from trade in two-sided markets via simple mechanisms. In Proceedings of the 2017 ACM Conference on Economics and Computation, EC 17, pp. 589-590, New York, NY, USA. 2017. Association for Computing Machinery. ISBN 9781450345279.
Nicolò Cesa- Bisnch,, Tommaso R Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. A regret analysis of bilateral trade. Proceedings of the 22nd ACM Conference on Economics and Computation, pp. 289-309, USA, 2021. Association for Computing Machinery.
Nicolò Cesa- Bianchi, Tommaso R Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Repeated bilateral trade against a smoothed adversary. In The Thirty Sixth Annual Conference on Learning Theory, pp. 1095-1133 130, USA, 2023. PMLR, PMLR.
11

---

Published as a conference paper at ICLR 2025
Nicolò Cesa-Bianche Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Bilateral trade: A regret minimization perspective. Mathematics of Operations Research, 49(1): 171-203, 2024a.
Nicolò Cesa-Bianche Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Regret analysis of bilateral trade with a smoothed adversary. Journal of Machine Learning Research, 25(234)11-36, 2024b.
Tommaso R Cesari and Roberto Colomboni. A nearest neighbor characterization of Lebesgue points in metric measure spaces. Mathematical Statistics and Learning, 3(1):71-112. 2021.
Riccardo Colini-Baai Baldeschi, Bart de Keijzer, Stefano Leonardi, and Stefano Turchetta. Approximately efficient double auctions with strong budget balance. In ACM-SIAM Symposium on Discrete Algorithms, SODA 16, pp. 1424-1443, USA, 2016. SIAM.
Riccardo Colini-Baldeschi, Paul W. Goldberg, Bart de Keijzer, Stefano Leonardi, and Stefano Turchetta. Fixed price approximability of the optimal gain from trade. In Web and Internet Economics, WINE' 17, volume 10660 of Lecture Notes in Computer Science, pp. 146-160, Germany, 2017. Springer.
Riccardo Colini-Baldeschi, Paul W Goldberg, Bart de Keijzer, Stefano Leonardi, Tim Roughgar- den, and Stefano Turchetta. Approximately efficient two-sided combinatorial auctions. ACM Transactions Economics and Computation (TEAC), 8(1):1-29, 2020.
Yuan Deng, Jieming Mao. Balasubramanian Sivan, and Kangning Wang. Approximately efficient bilateral trade. In STOC, pp. 718-721, Italy, 2022. ACM.
Paul Dütting, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenhäuser. Efficient two-sided markets with limited information. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pp. 1452-1465, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450380539.
Yumou Fei. Improved approximation to first-best caasssfro-ttrrde In International Conference Web and Internet Economics, pp. 204-218. Springer, 2022.
Zi Yang Kang, Francisco Pernice, and Jan Vondrák. Fixed-price approximations in bilateral trade. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithmss (SODA), pp. 2964-2985, Alexandria, VA, USA, 2022. SIAM, Society for Industrial and Applied Mathematics.
Walid Krichene, Maximilian Balandat, Claire Tomlin, and Alexandre Bayen. The Hedge algorithm on continuum. In International Conference on Machine Learning, pp. 824 832. PMLR, 2015.
Odalric-Ambrym Maillard and Rémi Munos. Online learning in adversarial lipschitz environments. In ECML/KKDD (2), volume 6322 of Lecture Notes in Computer Science, pp. 305-320. Springer, 2010.
Pascal Massart. The tight constant in the diveetak--iieeerwwolooitzzz inequality. The annals of Probability, pp. 1269-1283, 1990.
Preston McAfee. The gains from trade under fixed price mechanisms. Applied economics research bulletin, 1(1):1-10, 2008.
Roger B Myerson and Mark A Satterthwaite. Efficient mechanisms for bilateral trading. Journal of economic theory, 29(2):265-28) 1983.
Daniel Revuz and Mare Yor. Continuous martingales and Brownian motion, volume 293. Springer Science & Business Media, 2013.
Katerina Sherstyuk, Krit Phankitnirundorm. and Michael J Roberts. Randomized double auctions: gains from trade, trader roles, and price discovery. Experimental Economies, 24(4):1-40, 2020.
Elias M Stein. Singular integrals and differentiability properties of functions. Princeton university press, 1970.
12

---

Published as a conference paper at ICLR 2025
Pierre-Oliviee Weill. The search theory of over-the-counter markets. Annual Review of Economics, 12:747-773, 2020.
www.bis.org. OTC derivatives statistics at Jnd-June 2022. Bank for International Settements, 2022.
URL hwtp:httt//www.... wwtpwwww...... http:///is.orggpoo//otto.aooo/// hycccc__y2211_11 pdf
Yixuan Even Xu, Hanrui Zhang, and Vincent Conitzer. Non-excludable bilateral trade between groups. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 9952-9959, 2024.
A FURTHER DISCUSSION ON THE TRADING- VOLUME METRIC
To further elaborate on our choice of maximizing the trading volume, we first compute the individual expected utilities of the traders in our motivating example in Section 3 in the two cases in which the learner posts the price 1/2 maximizing the gain from the trade and the price m 1 - 2-27 1-8 maximizing the trading volume. A direct verification shows the following:
1-2s
1. The selling expected utility of traders at 1/2 is O(=2)
2. The buying expected utility of traders at 1/2 is s 26 + + Oss).
3. Thus, the gain from trade at 1/2 is 2e O(s).
On the other hand:
1. The selling expected utility of traders at is g fe²² O(e)
2. The buying expected utility of traders at m is ee= O(e).
3. Thus, the gain from trade m is fe _ 022=0(s).
Since the distribution of the traders' valuations is continuous and supported on the union [ - 10 [1 [1- 1] of a low and a nigh-valuationn cluster (with the overwhelming majority of the population concentrated in the low-valuation cluster), then, posting the price 1/2 that maximizes the gain from trade has the following consequences:
Traders from the high-valuation cluster (who enter the market with probability O(=)) will trade with probability 0(1) and earn utility @(1).
Traders from the low-valuation cluster (who enter the market with probability 0(1)) trade with probability (e)) and earn utility ((s).
This is arguably an unfair division of utilities because traders the low-valuation cluster (which constitutes the near-totality of the population) are effectively made unable to trade with each other and, as a consequence, end up earning negligible O(=²) expected utilities. this case, the near-totality of the gain from trade comes from the (cc) expected utility accrued by the high-valuation traders.
In contrast, posting the price m that maximizes the trading volume has the following consequences.
Traders from the high-valuation cluster (who enter the market with probability O(=)) will trade with probability O(1) and earn utility @(1).
Traders from the low-valuation cluster (who enter the market with probability 0(1)) trade with probability (1)) and earn utility (ee).
In this case, low-valuation traders can trade with each other (as well as with nigh-valuation traders), and consequently, their expected utilities rise to (s)). Both low and high-valuation traders accrue (E) expected utilities, maintaining in particular the same order @(s) of expected gain from trade.
However, there is no free lunch. The fairness obtained by moving away from directly maximizing the gain from trade comes at the cost that, in general, the gain from trade won't 't be exactly maximized. Take the previous instance as example. The trading-volume objective effectively manages to drive a balance of the utilities of traders coming from high and low- wwwuatttooo clusters of the population but the price of slightly lowering the gain from trade (note that although the order is the same, the
13

---

Published as a conference paper at ICLR 2025
gain from trade at m is lower than the optimal one by multiplicative constant). If & is constant (however small) independent of the time horizon, this will result a linear regret with respect to the gain from trade.
This should not come as a surprise, though, as it is what one should expect from fair objectives: generally speaking, they are not as efficient as unfair ones. This is point worth raising in broader sense. Is it worth losing a fraction the global value to obtain a fairer distribution of a slightly lower total wealth? Perhaps. This is profound philosophical question that reaches far beyond the scope of our work and whose answer probably varies depending on the circumstances. Still, we believe it is valuable to investigate both options and, at the very least, shine light on the possible pros and cons of the two, as well as to flesh out the different techniques that are needed to tackle each variant of the problem.
B FURTHER DISCUSSION ON THE I.I.D. ASSUMPTION
Same-distributton 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 sell. Instead, they simply hold valuation for the item 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, descrihed in (Sherstyuk al. 2020 "Consider, for example, mar- kets 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 simply one population of traders.
This naturally leads the assumption that the traders' valuations come from distribution modeling fluctuation of the market value of the item on sale.
To elaborate further, the reader might wonder: "What 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 of the two traders are drawn 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.c., 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 -istriibtii 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 change, and different techniques are needed depending on the assumptions relating contextual information to market prices. Recent attempts at investigating contextual models for the brokerage problem can be found in (Bachoc et al. 2024b 2025).
Incentive- Incentive-compatibiie compatibility and the i.i.d. assumption. Consistent with the broader body of bilateral trade literature studied from an online learning perspective, our mechanism is truthful for traders who make "take-it-on -ore-ittor--evve--i decisions and subsequently leave the broker permanently. In such scenarios, traders have no incentive to misreport their valuations, as doing would yield no benefit and could instead result in forfeiting the opportunity to secure a non-negative utility. This assumption aligns naturally with the i.i.d. framework, which can be interpreted as representing traders drawn
14

---

Published as a conference paper at ICLR 2025
from large and stable market. In such markets, re-entry effects are negligible, and the distribution of traders' valuations remains essentially unchanged over time.
C PROOF OF THEOREM 2
For each e [0, 1J. consider the following density function (see Figure | left)
fe: [0. 1] - [0,2],
-- 2sI x 5) I1 x
8) 2(1 -)]I
7
x {
7
8
Notice that, for each E [o, 1] with explicit expression given by
the cumulative function associated to the density fo is 2-Lipschitz
28 - 8 + - <x <<<<<
7 x2 8 (2-11 -=
Fe: [0, 1] [0, 1J, -- 2exl x S
Consider for each e [o, 1]. an i.i.d. sequence (Be of Bernoulli random variables of parameter an ii.d. sequence (Dt)ten of Bernoulli random variables of parameter 1. an i.idd sequence (Ut)res of uniform random variables on [0, 1J. and a uniform random variable E on [0, 1J, such that (BNN0))) (Di))), (U,) E) is independent family. For each [0, [] and / e N, define
U1 + (I-B,,) 8 Ve, == Dr (Be+ 8
+ (1- (1) (=+ U. -U)
(I)
Tedious but straightforward computations show that, for each E E [0 the sequence (Ve,t)aa is i..dd with common density given by fes and this sequence is independent of E. For any 8 [0. 1]. p [0. 1], and E N. let (p) g(p. Vg.2t-1.Ve..
(for qualitative representation of its expectation, see Figure [ right). We now show how to lower bound the worst-case regret of any arbitrary deterministic algorithm for the full-feedback setting (as)teN, i.e., sequence of functions
ay. [[0, x 1]) t-1 + [0, where each element maps past feedback into a price (with the convention that on is a number in [0, 1)). We remark that we do not lose any generality in considering only deterministic algorithms given that we are in a stochastic i.i.d. setting, and the minimax regret over deterministic algorithms coincides with that over randomized algorithmss For each & e N, define
I. and equal to 1/2 ) 2 (F.oa,) (1 a.). otherwise. Notice that for each 8 [o, 1] it holds that (Fooū)) (11 P. o ā,)
ae ([o, 1] x [0, 1]) - [ 3 equal to a whenever a takes values in []] 3]
and hence, due to Lemma for each E N, it holds that E (G,,, (ā.(,............... V=2((-1))] 2 (e) Notice also that for each E [0, we have that m. == 5-26 is the
E [[Ge:(aa(VV,,1 unique element in [0. 1] such that Fe(m)) 1/2. For any time horizon T 2 144, we have that the worst-case regret of the algorithm (az)teN can be lower bounded as follows
T
HG sup Σ E(Gea(mm)) (aaommm))GG.((a(Vaa.... [000.1]
sup veD
2 sup ee(o.1]
T Σ
B (m.) -
(o2(()))) _
T sup
Σ E
2 Fa(aa(Ve...... )Vao
13
=e(0.1] 5-13
2
E
2
Fe(@ (VE, (.........:..)))))
T 2
Σ
B
5 5- 22
Te &e.VE. VERCC-w))
1-
1=
5 2E
5- 5-2E
BE......, B Di,..., D2(-11), Un Shy...,U(((-1)) D
2 2
Σ
B
E
6-13
8
8
2 Σ
B
( 15 - 2E
E
5 5-28 2E
BE, BB
1)
1 Σ
E (E - E[E| BE BEI...,BEx(-))) BE2(+1)))]
8
8
8 +=13
1
2(t-)
BE, +1
1 T
((t-1)
Be, + 1
27
Σ
T2
F
R
5
de
2t
1-13
2
22((11) Ba.
22(1-1) Bad
2(1111) Ba.
27
Σ
[
de
2(1 1)
2(1- 1)
21
21
 E
22(1-11 Be.
1
1(--1)
1
27
Σ
B
ds
1-13
2(t -
2f(t-1)
x-1
2t
15

---

Published as a conference paper at ICLR 2025
12 Be
- Be,
1(
1((-))
Σ
0
8
2( 1)
c
2(t - 1)
21(1 - 1)
Σ
Br,
21
ds
1-1
E Bes
) Bes
E
de
2(1- 1)
2(1- 1)
1-13
1
Var(Br.1)
1
Var( (Ba))
1
L-
1
de
Σ
da
1=
2(t 1)
i
2(t 1)
13
2(t 1)
i
2(t 1)
1
T-1
1
2
ds
8 1-13
12(t-
81
2(
12
16v6
1-
8
12
16v6
12
8
T
1
1
In
In(T).
12
16v6
12
16
12
16v6
where follows from Lemma 1 "o" follows from the fact that E and Ve...... V. 1(--1)) are inde-
pendent of each other; followws from the fact that ãi takes values in S 7 and the explicit formula of Fg in that interval for any E [0, 1]: " follows from the fact that ā (VE.1..... ()) is Fi= = (BB.,.,......................... (g,,( DI.... D2(1-1), UI....... ................................ U2((-1) Uag-z))-masurrable measurable and that, for any Y the minimizer in (FF, of the functional X E [(Y x) is X = E[Y Fi];
follows from the fact that E' and (DI...., D2((-1). UI...., ... U2-11) are independent of each other; "*" follows from the fact E| BE.,,..., B Bg))((-1) has beta distribution; and "x" follows from the fact that B2, Be. is an i.i.d. Bernoulli process of parameter e, together with Jensen's inequality.
D PROOF OF THEOREM
Without loss of generality, we can (and do!) assume that T 2 2. and so log2(MT) 2 1. First, let Tr be the final value of if the algorithm ends at time T without a break, or define it as 7 1 if it ends with a break. For each r [Tr]. we define the epoch as the collection of rounds from 4-1 to f.,. Notice that, for each
[TT], we have that 8, is the number of bits collected during the epoch r. Let Qi= == 1/2, and define by induction Qi+1 as Q + 2 if F(2:) < 1/2, as Q; यमम if F(Q,) > 1/2, or as Q if F(Q2)= = 1/2. If there is T E N such that F(Q;) 1/2, let m == Q Otherwise, let m e [o, 1] be such that F(m) 1/2 (its existence has already been pointed out after Lemma Crucially, notice that for each 7 e N, we have that [m 12--222 Q21 s 2-
Let (V2,k) 2e(o,))(()) be an independent family of random variables with common distribution given by v, and for each x e [0, 1] and L ε N, define Nx(x) == 2. Et=l PPPx = z). Notice that without loss of generality, we assume that for each L. E N it holds that Vi-1 == VP..N.(P.)+1 and Vz == VP.)N.(P))+2- Define the "good" event
E= T
MVoo 2Q) < ( J
1n(2/8) 2j
3 even
and notice that by De Morgan's 's laws, a union bound, and Hoeffding's inequality, we can upper bound the probability of the "bad" event Ed by P[E*] s 8T2. Notice that for each i, [T] with F(Q;) }
2lu(2/6) 2, then, whenever we are in the good event E, we have that and even satisfying j j ( (!-P())))
1 1
(n(0))
2 (2/8)
1
Σ
IVV s sii+
<F(Q)) +
j $ 2
j k=1
2j
whenever F(Q2) < 1/2, while
1
Σ
1
nVV $ Q In In(2/0)
2 12(1))
1
3
2j
F(Q2)
j
2 2
whenever F(Q;)> > 1/2. Instead, if i,j [T] with F(Q;) = and j is even, have that In(2/6)
1
1
I I[Vo < Q1
2 F(Q;) 2
j k=1
2j
16

---

Published as a conference paper at ICLR 2025
and analogously
i
In(2/0) S <F(Q)) 1 2
Σ
IVv & s Qi)
V
k=1
2j
In particular, if we are in the good event &, these inequalities imply on the one hand that Q1 Qi,-... Q Qry and, if E [Tr] is such that F(Q;) 1/2, then T TT- On the other hand, if T [TT] is such that F(Q2)= # 1/2 and we are in the good event &, they imply that the number of bits (I-P(Q:))*
8, collected during the epoch t cannot be greater than 21m(2/6) because the condition that ends
21n(2/6) bits in that epoch. the epoch r with a break is met by the time that we have collected (1 ()=F())))²
Define T/ = [logg define T as the smallest T E such that F(Q;) 1/2 if exists, and to otherwise, and define - == min(> Th. Tr). In what follows, when we are in the event TT max Tr), we use the convention that any summation of the form - is zero by definition. For each t E [T], define H4 oVi..... V2-2) the o-algebra generated by the history observed before time t. We can control the regret in the following way
Rr Σ ([(((()-
E (m) [4.]
1-1
F(P:)) }]
2.
Σ
E
P.P.
22 Σ E (2 F(P.))
T
[g
P[E9]
2
9--1
( f(O:))
2
1
(1 --((Q:))
2
T
E
Σ 8r
LE
EE
Σ
8T
1E
221(2
2
Tr.
T 2
$
Σ
( -FF((Q)))
I6
+
Σ 87 M |m Q7p +
( F(Q:))²
T
$ (T 1) 2- ln(2/) +T 2 .2 2- +
s 2 (ogg((MT) In()).
2
where in used Lemma and in we used that fact that F(m) 1/2 and F is M Lipschitz.
we used the Freezing Lemma (see, (Csari & Colomboni 2021 Lemma 8)), in we
E PROOF OF THEOREM
We already know that algorithms that have access to full-feedback have suffer worst-case regret of at least e₁ In T' if T 2 C2. where e₁ and C2 are the constants in the statement of Theorem 2 In particular, the same statement holds a fortiori for any 2-bit feedback algorithm, given that any 2-bit feedback algorithm can be trivially converted into an algorithm operating with full-feedback. It follows that it is enough to prove that there exist two universal constants こ and 22 such that the worst- case regret of any 2-bit feedback algorithm is at least ट₁ In M whenever T 2 T2 (og,(M). In fact, in this case, we can set ē = min(c,, 2 and E₂ == max C2, (2) to obtain that the worst-case regret of any b-tit feedback algorithm is at least 26, max(In In M) ε In(MT') whenever T' 8g log, M.
We now prove the existence of TT and T2. Let E N be the greatest integer such that 2n M and consider the elements V DD whose density is 2n II 5- .k) for some l é [2"]. and notice that the corresponding cdfs are M -Lipschitz.
Consider the following surrogate game. The adversary secretly chooses kz e =[2"). The player action space is [2"]. The surrogate game ends the first time N when the player plays 1, k² Before that, if the player plays I # k², the player suffers a loss 1/2 and receives I[ S } as feedback. Now, note that we can convert any algorithm for the 2- feedback problem into algorithm ã for the surrogate game in the following way. For each E [2" - 1]. define Jj = [[k 11)2-,, ..k2 k2)
and Jzm [(2" 1)2 " 1]. Whenever the algorithm a plays P. E Jk. the algorithm ā plays
17

---

Published as a conference paper at ICLR 2025
and passes (I(1, s k* J. k*)) a, where k" is the underlying instance of the surrogate game. Now, notice that can map every instance k' E [2"] for the surrogate game into the instance Pk- Ms of the original problem and that the regret of the algorithm a on the instance Vkk is greater than equal to than the regret of the algorithm ā the instance k" It follows that worst-case regret lower bound for the surrogate game is also a worst-case regret lower bound for the original problem.
Fix an algorithm a for the surrogate game. Given that the surrogate game is deterministic, without any loss of generality we can assume that a is deterministic. We say that S [2"] is discrete segment if S is of the form {k E [2"] S k S b} for some a, b E [2"] with S b. We can prove the following property by induction on
there is a discrete segment Jj with at least 21 elements such that, for each k, k' E S₁, the algorithm has not won the game by the time t and receives the same feedback (and hence selects the same actions) if the underlying instance is or k' For t 0 the property is true by setting So == [2"]. Assume that the property is true for some t e (0, ,0..,,,,. - 23. Assume that a, b E [2"] with a b are such that S. (A: e [2n] a s s b}, where S, is segment that enjoys the property. Now, if the algorithm plays Ie-1 S, we can set S == Si, and we see that the required properties hold trivially. Instead, if I E St we set and we set St+1 {k: E [2"]
,,...,
k & I, 10-11 1} if Ie+1 aah Notice that given that Se has at least 2 - 1 points, we have that S contains at 2
S411 (k: E [2"] I + s ks & b) if T--1 < a+b
2
points and, for each & S1+1, the game does not end by the time + 1. Hence the induction step is proved. It follows that Sn-1 is non-empty and, if we pick k' Sn-1- the game goes on at least up to time n 1 whenever the time horizon T is at least n 1. Hence, T2 log2(M)) (M) (which implies in particular that T 2 1), the worst-case regret of the algorithm is (M) 1 (M)
least 2" 1-2 2n-(4+)
at least R-1 m+1 12
1 (ln(2) In M, where in the last inequality we used 1 and 02 == 1, concluding the proof.
2
M 16. Hence, we can pick ट == zinz
F PROOF OF THEOREM 6
For any / e N, tedious but straightforward computations show that
P sup (p)) (.(p) = S [ee[0.1]
sup pER
1
Σ
2t
I[V. sp) - F(p)
2 s 2eexp
8 4
1 (-1=²t
21
where the last inequality follows from the DKW inequality (Massart
1990). Let p"
argmaxp<fo.1 (p) (which does exist due to the upper-semicontimuity of V) Then, for any t E N. we have that
E [[T(p') (P [(V(p') ..(p')] [ - [ - (P(z1)
50
$ 2E
sup
(p))) (,((D|
= L 100
IP
sup
((p) - v.(p))
[p|[0.1]
[=[00.]]
100
- de
4
$ 2
2 exp
1
Vt
Hence
R S 11+B
Σ (v((')) - -(()))
T
11+4/T
Σ
1
$1+8/=
Vt
1=2
1
18


Reviews:
[{"review_id": "RtjTDqkH0g", "reviewer": "Reviewer_BE5B", "summary": "The paper studies a online learning problem for the brokerage who aims to maximize the total trading volume by posting a single price to two sequentially arriving traders. In particular, at each round $t$, there are two traders arriving with their private valuations $V_{2t-1}$ and $V_{2t}$. The broker then posts a price $P_t$ for this round, and if this price $P_t$ is between $V_{2t-1} \\vee V_{2t}$ and $V_{2t-1} \\wedge V_{2t}$, then the trade happens. \nInstead of optimizing the total gain from trade discussed in previous works, the goal of the brokerage of this work is to maximizing the total trading volume — i.e., the total expected trading probability. \n\nThe paper assumes that the two valuations of both traders are all independently and identically realized from an unknown distribution. The paper considers two feedback structure. One is full feedback where the brokerage can observe both traders’ valuations $V_{2t-1}, V_{2t}$, another is the 2-bit feedback where the brokerage can only observe indicators $\\mathbb{I}\\{V_{2t-1}\\le P_t\\}$ and $\\mathbb{I}\\{V_{2t}\\le P_t\\}$.\n\nThe paper first shows that in the full-feedback case, if the distribution of the traders’ valuations has a continuous cdf, then an $O(\\ln T)$-regret algorithm exists and this is tight. They also show that if we dropthe continuous cdf assumption, then the regret degrades to $\\Omega(\\sqrt{T})$, and they also provide an algorithm for this regret bound. \n\nIn the 2-bit feedback case, if the cdf of the traders’ valuations is M -Lipschitz, they show that  $O(\\ln(MT)\\lnT)$-regret algorithm exists and also provide a near-matching lower bound $O(\\ln(MT))$. The problem becomes becomes unlearnable if one drop the Lipschitzness assumption.", "questions": "Please see above comments.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper studies an online brokerage problem with adopting a new metric compared to current online bilateral trade problems. The new metric measures the expected probability of a successful trade which is motivated by a fairness concern: ``trading-volume maximization gives the same dignity to all traders, granting everybody the same opportunity to trade, independently of their buying power’’. I think taking a step to study the fairness issue in bilateral trade has solid motivation. The paper also provides complete results for this problem (though making some simplifying assumptions).", "weaknesses": "Although I agree with that studying the fairness issue in bilateral trade is an interesting problem, I found the paper lack of justifications on why the “trading-volume maximization” is indeed achieving certain fairness, as this only grants the same trading probability for each party. How does metric compared to the metric that is related trader’s welfare? I think more discussions here may be helpful to better motivate the current metric. \n\nMeanwhile, I think the current results are bit restricted given that they assume both traders’ valuations are all realized from a same distribution. This assumption seems to be a bit unpractical in real-world. Would current results/algorithms generalize to this setting?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JzO5ertwVp", "reviewer": "Reviewer_RtL8", "summary": "The paper studies trade volume maximization in brokerages through an online learning perspective. It considers bilateral trades where in each round two traders participate. The brokerage sets a price $p_t$, and the traders independently sample a private valuation from a fixed distribution. The trade happens if the brokerage price is between the two traders' sampled valuations, that is one trader values it below the price and is willing to sell it at this price, and one trader values it more than the price and is willing to buy at the price.\n\nPrevious works consider regret minimization aiming to maximize total profits, but this paper introduces a new objective where the goal of the brokerage is to maximize the number of trades. \n\nThe authors motivate the objective by showing an example where profit maximization can lead to low trade volumes.  \n\nThey consider full feedback setting and partial feedback setting. \n\nFor the full feedback setting, they show that having continuous CDF is enough to get $O(\\ln T)$ regret upper bound. In contrast, for the profit maximization setting, prior work has shown that Lipschitzness of the CDF is required to achieve even $\\tilde{O}(T)$ upper bounds. They also show a matching lower bound. For the non-continuous case, they show a $O(\\sqrt{T})$ lower bound and give an algorithm that achieves a matching upper bound. \n\nFor the partial feedback, the brokerage only learns if the valuations were lower or higher than the price. Under $M$ Lipschitzness of the CDF, the authors give an algorithm with $O(\\ln(MT) \\ln T)$ upper bound and show an $ \\Omega( \\ln(MT))$ lower bound. They also show that Lipschitzness is required to obtain sublinear regret in the partial feedback case.", "questions": "1. Can you please talk about the potential drawbacks of trade volume maximization?\n\n2. Can you please discuss how the 2 distribution i.i.d. cases studied in the literature relate to the i.i.d. case with one distribution regarding problem difficulty?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The profit maximization objective in online trades is well-studied in recent literature, the new objective introduced in this paper considers trade volume maximization and is reasonably motivated. \n\n2. The insight that the i.i.d. assumption in trade volume maximization simplifies the setting into a median estimation problem is novel resulting in tighter upper/lower bounds than the profit maximization objective.\n\n3. The paper provides tight upper and lower bounds in the full feedback setting, and strong results in the partial feedback setting with thorough analysis. \n\n4. The paper does a good job of explaining the related work in this domain.", "weaknesses": "1. Even though the authors motivate the trading volume objective, I would also benefit from some discussion on the potential drawbacks of aiming for trading volume maximization. Even in the motivating example in Section 3, when the price is optimized for trading volume maximization, even though it leads to more trades, the total profits the traders achieve are almost halved (from approx $\\frac{\\epsilon(1-\\epsilon)}{2}$ to approx $\\frac{\\epsilon(1-\\epsilon)}{4} + O(\\epsilon^2)$) which is linear regret for total profit. \n\n2. Most insights and algorithms are based on the fact that trade volume is maximized at the median in the i.i.d. setting where buyers and sellers have the same valuation distribution. Thus, the techniques may not translate to the generally studied i.i.d setting where the buyer and seller have different and possibly correlated distributions. The authors mention it as a possible future work, but maybe they can motivate the i.i.d setting more.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ApD3pqF619", "reviewer": "Reviewer_TXbV", "summary": "The authors study the online learning to maximize trading volume. Two traders come with private valuation in pairs, and the brokerage posts a price. If the price lies in between the valuation of the pair of traders a trade takes place. They study full information and 2-bit feedback structure. In full information, the valuation of two traders are revealed, while in 2-bit feedback whether the trader's valuation is higher than the posted price are revealed. They study the regret guarantees in three settings - the cdf of the reward is  (a) Lipschitz, (b) Continuous, and (c) General. In full information they provide tight regret bounds for all three settings. In 2-bit feedback Lipschitz functions admit tight logarithmic regret bounds, while linear regret lower bounds are established for the other two settings.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- The characterization of regret in the different setting seems quite complete. \n- The study of the online trading-volume maximization is an interesting addition to online learning in bilateral trade.", "weaknesses": "- The results though complete seems a bit lacking in terms of technical challenges. Simple median based algorithms suffice. \n    - Complementing the general setting with $\\alpha$-regret (for some reasonable $\\alpha$) would improve the paper. \n    -  Coverage of the 1-bit feedback (whether trade went through or not) would improve the paper.\n- Incentive compatibility of the proposed technique is not discussed.\n- There are some work in bandit learning in online Auctions/double auctions. Is there any connection to that work?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "owN9cgcmro", "reviewer": "Reviewer_6KDK", "summary": "This paper focuses on the bilateral trade problem in an online learning setting. Specifically, the authors consider a setting where, at each time step, a buyer and a seller arrive, and the algorithm, acting as the broker, needs to decide on a price for the trade. The trade is successful if the buyer's value is higher than the price, and the seller's value is lower than the price. Unlike prior works on bilateral trade that focused on optimizing **gain from trade**, the authors study the problem under a new measure of performance: **total number of trades**. The buyer's and the seller's values are drawn from an unknown distribution i.i.d. at each time step. The authors study two models of the algorithm's observation: after each time step, it observes either both players' values or their willingness to sell or buy at each time step. Under both models, and under different assumptions on the distribution of the values, the authors provide algorithms with guarantees on their regret and lower bounds on the regret of any algorithm. In most cases, the regret guarantees and lower bounds match each other asymptotically.", "questions": "1. Both the buyer and the seller share the same value distribution. Can you further discuss the motivation behind this assumption? What would happen if they have different value distributions?\n2. Does any prior work on bilateral trade consider the total number of trades as the performance measure?\n3. How do you think the results in this paper will impact the community? Is it more about the techniques or the problem setting?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The models considered in this paper are natural, and the theoretical assumptions are mostly reasonable.\n2. The theoretical results are mostly tight and elegantly shown in Table 1.\n3. The paper is quite well-written and easy to follow.", "weaknesses": "I have no major concerns about this paper and am happy to recommend it for acceptance. However, I have a few minor comments that the authors may consider addressing. Please also refer to the question section for some questions that I have. Feel free to ignore them since I am already positive about the paper.\n\n1. **Impact.** The paper presents a number of theoretical results, and it is commendable that they are almost tight. However, these results are mostly derived from standard techniques. This makes it unclear how this work will inspire future research from a technical perspective.  \n2. **Related work.** The discussion on related work about the original (non-online-learning) bilateral trade problem is a bit limited from my perspective. Currently, it is mostly stacked citations in one paragraph without sufficient explanation (even Myerson & Satterthwaite, 1983). It would be helpful to have a bit more discussion on the original bilateral trade problem and how it is related to the setting in this paper. Moreover, a few references are missing, such as:\n   - The Gains from Trade Under Fixed Price Mechanisms (Applied Economics Research Bulletin 2008)\n   - Improved Approximation to First-Best Gains-from-Trade (WINE 2022)\n   - Non-excludable Bilateral Trade between Groups (AAAI 2024)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)