Fair Online Bilateral Trade
Authors: François Bachoc
Nicolò Cesa-Bianchi
Tommaso Cesari
Roberto Colomboni
Venue: NeurIPS 2024 poster (2024)
Keywords: Regret minimization
online learning
two-sided markets
fairness
Primary area: bandits
TL;DR: We prove tight regret bounds for a fair version of the online bilateral trade problem

Abstract: In online bilateral trade, a platform posts prices to incoming pairs of buyers and sellers that have private valuations for a certain good. If the price is lower than the buyers' valuation and higher than the sellers' valuation, then a trade takes place. Previous work focused on the platform perspective, with the goal of setting prices maximizing the *gain from trade* (the sum of sellers' and buyers' utilities). Gain from trade is, however, potentially unfair to traders, as they may receive highly uneven shares of the total utility. In this work we enforce fairness by rewarding the platform with the _fair gain from trade_, defined as the minimum between sellers' and buyers' utilities.
After showing that any no-regret learning algorithm designed to maximize the sum of the utilities may fail badly with fair gain from trade, we present our main contribution: a complete characterization of the regret regimes for fair gain from trade when, after each interaction, the platform only learns whether each trader accepted the current price. Specifically, we prove the following regret bounds: $\Theta(\ln T)$ in the deterministic setting, $\Omega(T)$ in the stochastic setting, and $\tilde{\Theta}(T^{2/3})$ in the stochastic setting when sellers' and buyers' valuations are independent of each other. We conclude by providing tight regret bounds when, after each interaction, the platform is allowed to observe the true traders' valuations.

Fair Online Bilateral Trade
François Bachoc IMT
Nicolò Cesa-Bianchi
Department of Computer Science Università degli Studi di Milano
Université Paul Sabatier
Toulouse, France, 31062
DEIB
Institut universitaire de France (IUF)
Politecnico di Milano
bachoc @math. wetihhuuivv-toluseee
francois. bachoc
Milano, Italy, 20133
cesa-bianchiddi unimi.
Tommaso Cesari EECS University of Ottawa
Roberto Colomboni
DEIB
Politecnico di Milano
Ottawa, Canada, KIN 6N5 tcesari@uottawa.ca
Department of Computer Science
Università degli Studi di Milano
Milano, Italy, 20133
coblmboo.colommnn @poiimi.pmmmm.mmmmmm it
Abstract
In online bilateral trade, platform posts prices to incoming pairs of buyers and sellers that have private valuations for a certain good. If the price is lower than the buyers' valuation and higher than the sellers' valuation, then a trade takes place. Previous work focused on the platform perspective, with the goal of setting prices maximizing the gain from trade (the of sellers' and buyers' utilities). Gain from trade is, however, potentially unfair to traders, as they may receive highly uneven shares of the total utility. In this work we enforce fairness by rewarding the platform with the fair gain from trade, defined as the minimum between sellers' and buyers' utilities. After showing that any no-regret learning algorithm designed to maximize the sum of the utilities may fail badly with fair gain from trade, we present main contribution: complete characterization of the regret regimes for fair gain from trade when, after each interaction, the platform only learns whether each trader accepted the current price. Specifically, we prove the following regret bounds: O(I in the deterministic setting, !2(Z') in the stochastic setting, and ((T2/3) in the stochastic setting when sellers' and buyers' valuations are independent of each other. We conclude by providing tight regret bounds when, after each interaction, the platform is allowed to observe the true traders' valuations.
1 Introduction
In the online bilateral trade problem, at each round = 1, 2, ... a seller and buyer with private valuations for certain good connect trading platform. The seller's 's valuation S, is the smallest price at which they are willing to sell the good. Similarly, the buyer's valuation B, is the highest price they would pay to get the good. The platform posts price P. both buyer and seller. A trade happens if and only if both agents agree to trade, i.c., S, Pt s By. At the end of the round, S, and B, remain unknown and the platform only observes 11,,, < Pt} (i.c., whether the seller accepted the deal) and IfP s B3} (i.e., whether the buyer accepted the deal).
7 5 focused minimizing regret with respect to the gain from trade Previous works 12 2 9 13
function GFT: (p. s, b) > 8) {) S ps b). The quantity GFT(P,, St, B,) corresponds to the sum
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Determistic InT
Stochastic (i.i.d. independent valuations)
Stochastic (i.i.d)
Two-bit feedback
T
T
Full feedback
VT
Table I: Summary of our results.
of the seller's utility Pt - St and the buyer's utility B, Pt at time t when a trade happens, and zero otherwise. This reward function, however, is oblivious to asymmetries in the utilities of the buyer and the seller caused by Pt not being close to the mid-price (S; + B2)/2. As argued in [20], prices generating unequal gains may lead a reduced participation in the market, which translates less trading on the platform.
To address this problem, instead of using the sum of the utilities (i.e., the gain from trade) reward function, we use the minimum of the utilities. This reward function ignores any surplus a trader may achieve at the expense of the other, thus encouraging the platform to set prices Pt close as possible to the mid-price, cqualizing the profit of sellers and buyers. We call this new reward function fair gain from trade and denote it by FGFT. Our specific focus the fair gain from trade objective can be seen as an implementation of the so-called egalitarian rule in social choice theory (sometimes also called the max-min rule or the Rawlsian rule), where one favors the alternative that maximizes the minimum utility of the involved parties to promote fairness. This approach might be especially relevant for online ride-sharing services like Uber and Lyft, where fairness problems have been previously studied, although in different settings with metrics different from ours (see, e.g., (31). Our goal is to design algorithms minimizing the regret over T rounds. This is the difference between the (expected) total FGFT achieved by the best fixed price p' and the (expected) total FGFT achieved by the algorithm. Note that the two bits received as feedback at the end of each round (i.e., ([S, < P') and I(P; Be) are not enough to compute bandit feedback (the reward carned by posting the price Peinheither for FGFT nor for GFT
Our contributions. If sellers' and buyers' valuations are independent and drawn i.i.d. from two fixed but unknown distributions, we obtain an efficient algorithm (Algorithm) D. achieving a regret of O(T2/3) after T rounds (Theorem 2). This algorithm is built around the key Convolution Lemma (Lemma] I which shows how one can estimate the expected FGFT through the feedback the learner has access to. Algorithm [ does so by building uniform estimates for the expected FGFT via a discrete convolution procedure that combines the feedback collected from sellers and buyers across different time steps. We then derive a lower bound matching this rate up to logarithmic factor (Theorem 3). The lower bound construction leverages the relationship between the feedback and the FGFT to build hard instances of our problem. These hard instances are similar to the ones in the revealing action problem of partial monitoring (see, c.g., [5]. that force the learner to perform a certain amount of costly exploration. An analogous phenomenon shows up even in the deterministic case, where S, = s and B, = b for all and for some unknown constants 8, b. In this simpler setting, we prove that posting some clearly suboptimal but informative prices is unavoidable, showing that strategy can obtain a regret better than ?'n (Theorem 4). We complement this result by showing that this rate matched by a double binary search algorithm (Theorem 5
We also show that the independence of sellers' and buyers' valuations is necessary to minimize regret with respect to fair gain from trade: if the pairs (S,, B:) are drawn i.i.d. from arbitrary joint distribution, then the FGFT regret must grow linearly with time (Theorem [T).
Finally, we complete the picture by quantifying the cost of partial information. We do so by analyzing the regret rates at which the platform can learn if the pair (St, B,) is revealed at the end of each round-the so-called full feedback model. Here, we show that a regret of (VTT) can achieved for any joins distribution of sellers' and buyers' valuations (Theorem (). and we show that this rate is optimal up to constant factors, even if we assume that the traders' valuations are independent of cach other (Theorem
Our results are summarized in Table
In fact, if a trade occurs, we only know that S, s Pt s B., but this information alone allows us to compute neither min(S, - Pt, B. Pt) nor B:- S..
2

---

Technical challenges. When regret is minimized with respect to the from trade, the indepen- dence of sellers' and buvers' valuations is not enough to guarantee sublinear regret, and an additional smoothness assumption is required to compensate for the lack of Lipschitzness of GFT. In 2 I0] the optimal regret for GFT under the smoothness assumption turns out to be the same as the optimal rate @(T2/3) achievable for FGFT without smoothness. This happens because the faimess condition confers Lipschitzness to the gain from trade, allowing us to compare against broader range of distributions. fact, the smoothness assumption plays no role in the fair version of the problem. To further compare the two settings, note that the issue appearing in [9] i.e., feedback so poor that is not even sufficient to reconstruct the reward at the posted price, arises here as well. In our case, however, the specific form of the objective requires new ideas-i.c our new Convolution Lemma (Lemma)) - to recover usable information about the reward function. Another difference is that, in (9. the realized gain from trade is maximized by posting any price p E [S, B3. In our setting, instead, we have to address the more delicate task of locating the midpoint p = (S B)/2. This is the reason why, as we show in Section 2 even optimal algorithms for bilateral trade can suffer linear regret in our setting. From the technical viewpoint, note that a direct application of the convolution lemma in the 2-bit feedback setting would yield a suboptimal upper bound of T To obtain the optimal T2/3 rate, we carefully define a data-gathering procedure in which each observation contributes to estimating the convolution of the edfs at all points.
P
Another interesting discrepancy between the two settings arises in the deterministic case, where a learner can devise a strategy whose regret is constant when the reward function is GFT. This is in contrast to the O(n rate when the reward function is FGFT, as we discuss at the beginning of Section 4
Related work. Attempts to circumvent the linear lower bound for the regret of gain from trade in adversarial environments include (2), where they focus on 2-regret, and [5), where they consider a global budget balance condition that allows the learner to subsidize trades with money accumulated
in previous rounds. Recently, online brokerage, a related though incomparable setting where traders can sell or buy depending on the contingent market conditions, has been studied in 7 [7
Fairness is an intensively studied topic in online learning, with the goal of understanding the extent to which the fairness constraints impact on the regret. The work ( considers online prediction with expert advice and studies the problem of combining individually non- non-discriminttoyy experts while preserving non-discrimination. An early investigation of fairness in linear bandits conducted in [23]. where the fairness constraints demand that similar action be assigned approximately equal probabilities of being pulled, and the similarity metric must be learned via fairness violation feedback. Fairness in linear bandits is also investigated in [22. where the reward observed by the learner is biased towards specific group of actions. In the authors study an online binary classification problem with one-sided feedback where the fairness constraint requires the false positive rate to be equal across two groups of incoming users. The paper [19] applies Blackwell's approachability theory to investigate online learning under group fairness constraints. A different notion of fairness in bandits is considered by (2 30), where each arm has to be pulled at least a pre-specified fraction of times (see also [8] for related results). This type of faireess requirement is also considered in [2 where the optimal policy is pulling an arm with a probability proportional to its merit (a wooblem-specing function of the arm's 's expected reward). Finally, the work [44 considers K-armed bandit setting in which pulling an arm yields different rewards for different agents. The algorithm's 's goal is to control regret against the optimal Nash Social Welfare (NSW). The NSW of probability assignment ' over the arms is the product of the agents' reward in expectation according to π.
Online learning with fairness constraints is also investigated in online fair division M]. where each good in a sequence must be allocated to a set of agents who receive some utility that depends on the good. The goal is to satisfy a given fairness criterion, which is typically not aligned with the maximization of the agents' utilities. Traditionally, this problem has been studied under the assumption that at the beginning of cach round agents report their true utilities (29]. Very recently,
the problem was studied in a bandit setting, where only the stochastic utility of the agent receiving the good is revealed 33 In that setting, there is finite set of types and the expected utility of agent i for type j is fixed but unknown. The regret is then defined in terms of the geometric mean of the total expected utilities of the agents. Our regret, instead, is defined additively over the minimum
AA distribution is smooth whenever it admits bounded density; see, e.g., 21 |
3

---

of the agents' utilities in each round, where the utilities of sellers and buyers depend on each other through the price posted by the platform. Our notion of regret can also be viewed an online version of the Salai-Smorodinsky solution to the bargaining problem, in the sense that we also strive to equalize the utilities of the two players [25] The regret typically studied online fair division, instead, corresponds to the Nash solution to the bargaining problem.
Finally, we mention that the line of research where online learning applied trading problems, was initiated in one-sided settings, like dynamic pricing, whose seminal paper was [26]. For an interesting comparison of generalization of) the dynamic pricing setting and the bilateral trade setting, see also [14].
Formal problem definition. We study the following problem. At each time t N,
1. A seller and buyer arrive with private valuations S, [0, and B, [0,
2. The platform proposes a trading price Pt [0,1]
3. If S, s S B,, then the buyer gets the object and pays P. to the seller
4. I[S; s P.) and I(P: } are revealed
The boundedness assumption for valuations and prices is standard in regret minimization settings. We enforce fairness by rewarding the platform with the minimum of the utilities of sellers and buyers. More precisely, for any E [0, ] and any 8, s, [0, I]. we define the fair gain from trade achieved with p when the seller's valuation s and the buyer's valuation is by
FGFT s, b) min {p-- (b- p)-}.
where x, max (ar 0} for any a
We assume a stochastic model where the sequence (St, B.) of sellers' and buyers' valuations is an i.ddd process with fixed but unknown distribution. The regret after T rounds an algorithm posting prices P2... is defined by
T Σ FGFT(P,
T Σ
FGFT Se, S.. B.)
R == max E 0epe1
-E
In the deterministic setting (which can be viewed special case of the above stochastic setting) there exist s, e [0, 1] such that, for every t e N, holds that S, = s and B, = b. both cases, note that the maximum exists because the expected FGFT is 1-Lipschitz function of the price.
2 Maximization of gain from trade does not imply fairness
In this section, we show that, in general, a no-regret algorithm for GFT fails achieve no-regret guarantees for FGFT.
Consider the stochastic setting, where the sequence (S,, Be) is an i.i.d. process. Pick 0 h < 1/2 and, for all t E N, let S, be such that S, = with probability 1/2 and S; = 1- with probability 1/2. Let also B, 1 for all N. Then, the only prices maximizing GFT are those in the interval [1 h. 1]. Now, any price e [1 h, 1] achieves an expected FGFT of
1 E [[FGFT(P, St, B.)] = (1- min
and the maximum of this quantity is h/2, which is attained, for example, by posting p 1- h.. On the other hand, it is easy to see that the maximum of the expected FGFT on the whole interval [o. 1] is 1/4 > h/2, achieved by posting p= 1/2 & [1- 11,1] So, if we any no-regret algorithm for the standard bilateral trade problem to post prices Pı, Pa...., we suffer línear FGFT regret on this instance. Even more strikingly, on these instances, for any t N.
E [[[FrT[1 S,, B.)]
2h + 0*
for h + 0*
E FGFT(1/2, (1/2, S. B.)]

---

which implies that there are instances where any no-regret algorithm for the standard bilateral trade problem fails even if we content ourselves with competing against a fraction of the reward eamndd by no-regret algorithm for the fair bilateral trade problem
3 The stochastic case
We begin by providing a linear lower bound on the worst-case regret for the stochastic case. The idea of the proof is to leverage a lack of observability phenomenon: can devise two different distributions whose maximum expected fair gain from trade is achieved in disjoint regions- -s that posting price that is in the good region for one distribution leads to instantaneous regret bounded away from zero for the other distribution-but the learner cannot distinguish which the underlying distribution generating the valuations, given that these distributions are designed so that the (push-forwl forward) distribution of the received feedback is exactly the same for both of them.
Theorem 1. In the stochastic case, for every algorithm for the fair bilateral trade problem, there exists joint distribution under which, for an i.i.d. sequence (St, B₁ LeN of sellers and buyers,
have, for all T e N,
T
RT 2
48
Proof. For any point x [0, let 5₂ be the Dirae measure centered at x. Consider the two ( (g2 ) + ((21)) and v = (Q)..) + ((2.) + (())))) Suppose
distributions / == 3 (5(o.)) that the sequence of valuations (S.. Be) is drawn i.i.d. from 1 or v. If the underlying dis- tribution is μ., the optimal point is 5/16 and, for all p [1/2.1] and
N, the difference [[FGFT(5/16, Se, B.)] E[FGrT(P, S,, B.)] is at least ( T6 24' Analogously, if the underlying distribution is the optimal point is 11/16 and, for all p [0, 1/2] and / N, [[rGFT(11/16, Sr, B.)] [[FGFT(P. Se, B.)] 1 not to suffer Q(T) regret is to distinguish whether the underlying distribution is u. But direct verification shows that the distribution of the feedback is the same for every p E [0, 1]. regardless of whether the underlying distribution is μ v. Hence, the learner has means to distinguish between jt and y and must suffer S?(T) regret. Indeed, let Nr be the random number of times the platform posts a price P, in [0 Then Nr has the same distribution under 14 and v. If E, [Nr] E., [T]] 2 T 2. then the expected regret under v is at least T 7 24 48
3
24. This means that the only way for the learner
T
Conversely, If
[N[ = [,[N]] 2. then the expected regret under μ is at least T
18'
Remark 1. Note that Theorem D together with Yao's 's Minimax Theorem immediately imply that the adversarial fair bilateral trade problem-wher where the goal is to obtain sublinear worst-case expected regret against the best fixed-price when the sequence of seller/buyer valuations (St, Bt) 1ees is chosen by an oblivious adversary- is unlearnable.
We now show that we can achieve learnability in the stochastic case by assuming that, for each t E N, the two valuations S, and B, are independent of each other.
To this end, we first present the Convolution Lemma (Lemma I which provides way to avoid the aforementioned lack of observability when the traders' valuations are independent of each other. This lemma plays for FGFT role analogous to the one played by the Decomposition Lemma 9 Lemma 1] for GFT.
Lemma (The Convolution Lemma). For all s, s, [0.1].
FGFT(p,s,)) S. T((sspp
du.
(1)
In particular, if S and B are [0, 1]-valued independent rundom variables, for each 6 [0, 1],
B[ S, S, [[]
p- p- B] du
'The reader familiar with the notion of a-regret will note that this is equivalent to saying that any no-regret algorithm for the standard bilateral trade problem fails to be no-a-regret algorithm for the fair bilateral trade problem, regardless of how large a is chosen.
5

---

Proof. If (p, -(b)))0---- (b- p)+, note that
(b-p)+ S I(u (b p)-} J,
(b-p)++ du
J. I(usp- s]I(s du= S/ uI] du.
The same conclusion holds with an analogous argument if FGFT s, 6) (p-s)+. The stochastic case follows immediately from Fubini's theorem and the independence of S and B.
We now explain how the previous lemma can be used to recover the observability of the expected FGFT under the independence assumption. Note that, given the feedback we have access to, we can estimate the cumulative distributions of both sellers' and buyers' valuations pointwise with arbitrary precision, and hence, a fortiori, we can estimate
(2). However, even if this observation alone would be enough to ensure learnability, this is not the most efficient way of learning the expected fair gain from trade function. In fact, we do not really need careful pointwise estimation both cumulative distributions, but just of (2), which involves certain products of their translates. The crucial observation from which Lemma [ takes its name-in -is that (2) is the (incomplete) convolution the cumulative distribution of the sellers' valuations and the co-cumulative distribution of the buyers' valuations, and that we have noisy access to these functions at the points we need to estimate them, though different time steps. This observation suggests that (incomplete) convolution by a discrete (incomplete) convolution involving the noisy observations we collect at different time steps, e.g., by posting prices uniform grid. These ideas exploited in the design of Algorithm | and in the proof of its regret guarantees.
approximate the continuous
Algorithm 1: Convolution Pricing (Stochastic Setting)
Input: K N;
Initialization: for each I e Z, set V, W, O; for time & 1, 1,2,..., K do
Post price Pt == K and set V = I[S; s P.), W. T(P: B.): K-
Let / argmax K Ek=0 V Wi.:;
for t = K 1,K 2,..., do
Post price P. = I/K:
Theorem 2. In the stochastic case, under the additional assumption that for each t N the seller's 's valuation S. is independent of the buyer's 's valuation B,, by setting K = 2 the regret suffered by Algorithm is 2(r2(3).
Proof. For each k E [K]. define 9k == E| FGFT(P, St, B,)] is 1-Lipschitz being the expectation of (random) 1-Lipschitz functions. Hence, if for each [0. 1] we denote by k (p) the index of the closest point in the grid (91...., 9K }
& Note that for each t E N the function >
K.
we have, for each N, that,
E[FGFT(P, S,, B.) BE FGFT(TH (p) Sr B.)] K
(3)
Let F be the common cumulative function of the random variables in the process (St (ee and let G
be the common co-cumulative function of the random variables the process (B, rare, i.e, for each
I E N and each p R, define F(p) == P[S y] and G(p) = P(p S B]. Note that F(u) 0 for each M. S 0, that Guu) for each 2 1, and that for each p E [0, 1]. the function u F(p u Gp u)
non-increasing, being the product of two non- aom-ncceasiin functions. Hence, for each N and each

---

ke [K] by Lemma]) 1 we can sandwich the quantity
EK-1
F G (gk+s) as follows:
k
K-1
* F ( u)G + u) du
FGFF qk. Sz, B:)]
F(gx u))
+2) du
Σ
1=0
k
K-1
k
i
K-1
Σ
G
du
Σ
F (gx-:)) G (qeni)
*
K
K
1=0
1
K-1
Σ
F (11-(1+1)) G ((
1
K-1
Σ
ill
k
i+
i 11
du
K
K
K
K
K
1-0
1-0
1
K-1
- (lak-u)Ge uudu= 1
F(gx
u) G(g
u) du
K
*
K
1=0
1
B[FGFT(QU, St, St, B.)
(4)
K
Now, by the independence assumption,
K-1 Σ K 2-0
K-1 Σ ((k-)) G (Ac+s) = K 1-0
1
K-1 Vk-;
B[V [E =
Σ 2-1
Wk+s
K
and, by noting that for each &s E [K] we have that マ Σi= Vk-eWk+e is the empirical mean of K {0, 1 --valued independent random variables, by Hoeffding's 's inequality and union bound, we have that, for any E > O,
max kE[K]
Σ =0
Va-iWari
Wkii
Σ
((k- G ((x-e)) 2 < 2K exp(-2e²K) K).
K
K
1=0
In particular, if we set eT
In(2T) A[T28]
recalling that = [T2/33, J. and defining the (good) event
Er = {max 1 EK- VK-iW 1 EKo' F G <TT) we have
P( S T2/3
(S)
Now, letp' p' argmax,<(o.) [[FGFT(P, Sc, B,) (whose definition is independent of t, given that the process (S,, Be)ee is i..d.) and, recalling the definition of I from Algorithm I note, for each t K, that
E
(C. B.)] = B FG B.)] E { (I B.) I]]
1
E
[[FFFF((): (x. St, B.)]
2
F (gk=i) G (UK+i)
k=1
K
K
k=1
K-1
1
1 K-1
1
E
F (g1=+)))))+))
E
Ler
Σ
VI-WW1+
ET
K
K
K
K
K-1
K-1
2 EE
Ter
Σ
-ST
2
E
V (-
- -P[[T]] ET K
K
K
K
K-1 Σ
F ((e C (N)))))) -P[E]] eT
2 B[FGFT(p' Se. B.) [[[G]] ST K
2 K
K
where the third equality follows from the Freezing Lemma (see, e.g., 18 Lemma 8)), the first
inequality from the sandwich inequalities in (4), the second inequality from the definition of εx, the third inequality from the definition of I, and the last inequality from the sandwich inequalities in (4) upper bound the regret as follows
and inequality (3). Putting everything together,
T
T Σ [-K+1
2 x) [
Ry S K
E FGFT(( ,S,, B.) (-K+1
Σ
Bi)]
Recalling that K | J,
ET=
In(27) 2[T2/8]
and (5) obtain the conclusion.
7

---

We now prove that the strategy employed by Algorithm[] T is worst- optimal, up to logarithmic factors. At high level, the reason why the 7 rate is optimal is that the fair bilateral trade problem contains instances that closely resemble the revealing action problem in partial monitoring [T3]. where, in order to distinguish which one of two actions is optimal, we have to play for significant amount of time a third highly suboptimal action to gather this information. We formalize this intuition in the following theorem, whose full proof is deferred to Appendix (uu to space constraints.
Theorem 3. There exists constant e 0 such that the following holds. For every algorithm for the fair bilateral trade problem and for every time horizon
N, there exists an i.i.d. sequence (St, Be Beary of pairs of sellers' and buyers' valuations such that, for each L E [T]. Sy is independent of Bu, and the algorithm suffers regret of at least 2/3 on that sequence.
Proof sketch. For each e E [-1,1] 1]. consider the distribution fr = 1 26000 + I-c 5/51/1 where dn is the Dirac measure centered at a point a R. For each & E [-1,1], let (S₁ Jeets an i.i.d. sequence whose distribution is jlc. For each e N. let B, 1. Then, for each [1.. the sequence (S₁, Be) is ii.d. and for each N the valuation S is (obviously) independent of the (deterministic) valuation B, Now, one can show that if 0 the optimal price to post in order to maximize the expected fair gain from trade over the sequence (S₁, B₁ ser is 1/2 while if e < 0 the optimal price is 5/8. If e 0 and we post prices greater or equal than 9/16 we suffer instantaneous regret of at least order of [el, while if æ < 0 and we post prices less or equal than 9/16 we suffer instantaneous regret of at least order of |s]. Hence, to avoid suffering (((s/(T) regret we need to distinguish the sign of e. Given that what we see are the two bits in the feedback, the only way to discriminate the sign of is to post prices in the region between and 1/4. In this case, the feedback we see is equivalent to arguments, we need 9(1/e") to distinguish the sign of e. Now, every price in the region [0. 1/4] suffers instantaneous regret of order (1)). Hence, any algorithm has to suffer ? + |=(T) regret, which is 2(T2/33 when |e| (T-))/3)
2
2
Lts, and hence, due to inffrrmation-theoree seeing Bernoulli of parameter 2
Remark 2. The 2/3 rate we achieve in Theorem 3 was also the regret rate for the standard bilateral trade problem in (9. where in order to achieve learnability, on top of the stochastic and independent valuations assumptions, it was also required that the valuations admitted a bounded density. In that case, the regret rate degraded multiplicatively with the upper bound on that density. Instead, we manage to obtain this rate without the extra bounded density assumption and our bound does not explode if the bounded density constant diverges. The reason is that, differently from the discontinuous gain from trade function, the fair gain from trade is 1-Lipschitz.
4 The deterministic case
In this section, we study the deterministic case where there exist fixed but unknown constants s, be [0, 1] such that, for all time t E N, S. s and B, = b. In this case, we note that if 6 < trade can occur while, if b = s, even though a trade can occur for the posted price Pa- = b = s, no gain from trade or fair gain from trade can be obtained from it. Consequently, we focus on the only interesting case s <<b b.
We begin by the following remark: in the standard bilateral trade setting where the reward function the gain from trade p + (b- - x)I((s 2 p S b). we can devise an algorithm that achieves constant regret. In fact, the learner can post prices following binary search (starting by posting the price 1/2), move to the next dyadic point to the left (resp., right) if both valuations were lower (resp.. higher) than the proposed price, while keep playing the same price soon as successful (dyadic) price p is proposed, i.e., a price p E [s, bj. This way, if the learner fails n times before the first success, an upper bound on the cumulative regret suffered in the "failure" phase is 2 s 1, and from the subsequent rounds the instantaneous regret is always zero
In contrast, the deterministic fair bilateral trade problem is still sufficiently layered that a costly exploration phase is unavoidable to achieve learnability given the intertwined relationship between the reward function and the feedback. This is also in contrast to what happens in the stochastic setting, where the standard bilateral trade problem required the extra bounded density assumption to achieve Icarnabllity (and hence, in this sense, harder) than the fair bilateral trade problem.
8

---

Theorem 4. In the deterministic case, for any horizon T 2 17, any algorithm suffers worst-case regret larger than or equal to 32 log2(T)
For the full proof of this result, see Appendix
B
Proof sketch. Since the setting is deterministic, we can restrict the proof to deterministic algorithms without loss of generality. Then, the key property we leverage is that for any k N, if deterministic algorithm posts at most k prices in [0, ] then there is interval E, [o, ] of length @(2**) such that, for each s,s' E Eg, the algorithm receives the same feedback from the environments defined by seller/buyer pairs (s, 1) and (s', 1), therefore selecting the same prices.
Now, fix a deterministic algorithm a. There exists k' E {0,, ,'' such that, for all 8 E Ex the algorithm posts exactly k* prices in [o, $.. A direct verification shows that, for any Eg,, the instantaneous regret paid for the time steps where P: [o, [] is Q(1). Therefore, the regret paid by the algorithm for playing k' times in [0, _ is (2()". Moreover, let T be the set of time steps te [T]] where the algorithm posts prices P: (1.1). Leveraging the fact that the algorithm posts the same prices for every E Eg,, , it can be proved that there exists an s E Eg such that the average from the maximizer htts of the 2
distance IT Exe |P
bts of the points Pt played at rounds 2
FGFT is at least ((2=*)). Putting everything together, the worst-case regret the algorithm is lower bounded by 22(k= + (T k= )2 kk) ), which is (2n regardless of the specific value of k*
A "double" binary search algorithm suffices to obtain matching O(I)7) regret rate. The idea of the algorithm is very simple. First, spend OIn 7') rounds performing binary search for the valuation of the seller. Then, do the same for the valuation of the buyer. Finally, commit to the average of these two estimates for the remaining time steps. For completeness, we report the pscudocode of this
algorithm in Appendix (Algorith J. For full proof of the following theorem, Appendix C
Theorem 5. In the deterministic case, the (deterministic) regret suffered by Algorithm is O(In 7).
Proof sketch. The idea is first to invest a budget of order In T to locate the seller's valuation with error O(1TT). Second, we proceed similarly to locate the buyer's valuation with error O(ITT). Finally, this yields a (1/TT) ((1/T)-precise estimate of the optimal price (s + b)/2, and we commit to this estimate for the remaining time steps. The regret incurred by the two first phases is of order In T while the regret of the last phase is of order T 1. and thus bounded.
7.
5 The full-feedback model
We conclude this paper by quantifying the cost of partial information by analyzing the full feedback model, where, after posting the price Pt, the learner has access to both S; and B. We show that the cost two-fold: slower rates (both in the deterministic OIn 7) vs 6(1) and stochastic case - vs ((VT)) and the need for additional assumptions (independence buyer and seller valuations in the stochastic case).
For the feldbecdbbck setting, we show that following the best empirical price leads to an algorithm (Algorithm 2 whose regret guarantees are optimal. We remark that Algorithm needs full feedback to run, given that it needs to compute the FGFT function for counterfactual prices. For the full proof of the next theorem, see Appendix D
Algorithm 2: Follow the Best Empirical Price
Initialization: Select P1 == 1/2: for time t= 1, 2, do Post price Pt, and receive feedback (St, B:): Select P argmax 1 E FGFT(P, S,, B₂)
Theorem 6. In the stochastic full-feedback case, the regret suffered by Algorithm O(VT). In the deterministic setting, the (deterministic) regret of Algorithm 2 is upper bounded by 1/2.

---

Proof sketch. The deterministic case is immediate: by posting 1/2, the regret in the first round is at most 1/2, and the algorithm pays no regret in the subsequent rounds. For the stochastic case, due to Lemma note that & E (GFT St, B.) - Lo & E 1[S; s p u u s Bi) du =: Gp). Now, by the two-dimensional DKW inequality, it can be proved that the empirical estimates (.(p) are uniformly E-close (in p) to [FGFT((p S1+1, Bi+1)] with probability - O(e (e=(<=))) These probability estimates, together with the fact that the algorithm selects P by maximizing p (p),, translates to O (1/vt+ conttol over the expectation maX0sps1 E [FGFT(p, S4+1 BB-1) FGFT (Pt+1, S4+1 By-1)] The conclusion follows by summing over time steps.
We now show that the guarantees provided by Algorithm 2 are worst-case optimal, even if sellers' and buyers' valuations are required to be independent of each other.
Theorem There exists a constant O such that the following holds. For every algorithm for the fair bilateral trade problem with full feedback and for every time horizon T e N, there exists an i.d. sequence (S,, serterry of pairs of sellers' and buyers' valuations such that, for each [T], Se is
independent of Bu, and the algorishm suffers regret at least cvT on that sequence.
Since the proof of this result follows along the same lines as the proof of Theorem (whose full details can be found in Appendix A we present only a proof sketch.
Proof sketch. The hard instances are the same those in the proof of Theorem for the 2/(3/33) lower bound in the stochastic i.i.d. case with independent sellers' and buyers' valuations. We refer to the proof sketch of Theorem 3] for the relevant notation and observations. We recall that in those instances to avoid suffering (I=TTT regret need to distinguish the sign of e. Now, given that full-feedback is available, the information we retrieve after each interaction is equivalent to observing a Bernoulli r.v. of parameter Its regardless of the price we posted. Again, information-
theoretic arguments imply that we need S2( ()) rounds before being able to distinguish the sign of During these rounds, the best we can do to play (essentially) at random in the candidate set of optimal prices 11/2,/88), suffering an expected instantaneous regret of 12(ss). Overall, we suffer
Ω min [lel- 3.1())) cumulative regret, which leads to the claimed 2 (T) regret rate once we
tune |e|
Remark 3. In the same spirit of Remark Theorem 7 together with Yao's Minimax Theorem immediately imply that any full-feedback algorithm to solve the adversarial fair bilateral trade problem has to suffer regret of at least 52( TT). A nearly matching (up to logarithmic factors) upper bound for this problem can be deduced using the algorithm Hedge for [0, 1]-Armed Experts (see (1O) Appendix A)). We leave to future research the understanding of whether the adversarial case is logarithmically harder than the stochastic case or whether a different algorithm can achieve better regret rates.
6 Limitations and conclusions
Our analysis is based on different assumptions on the generation of the sellers' and buyers', valuations (stochastic, stochastic and independent, deterministic, adversarial). Our results characterize (up to constant or log factors) the regret rates in each case. Hence, there are no specific a priori assumptions that we need to make to prove our results.
Our results can be extended in different directions. For example, by linking the unknown valuations of sellers and buyers to contextual information visible to the platform. In practice, platforms simultaneously deal with multiple sellers and buyers, in which case the platform may have to post a set of prices and consequently operate in a multidimensional decision space. Finally, our result for the stochastic setting with independence between sellers and buyers only tight up to logarithmic factors, an improved analysis of the upper lower bound is needed.
10

---

Acknowledgments and Disclosure of Funding
The work of FB was supported by the Project GAP FANR-2I-CE40-00 of the French National Research Agency (ANR) and by the Chair UQPhysAI of the Toulouse ANITI AI Cluster. NCB and RC are partially supported by the MUR PRIN grant 2022EKNE5K (Learning in Markets and Society), the FAIR (Future Artificial Intelligence Research) project, funded by the NextGenerationEU program within the ENRR-PE-A scheme, the EU Horizon
research and innovation action under grant agreement 101 120237, project ELIAS (European Lighthouse of Al for Sustainability). 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 DGECR2023-00209 (Discovery Grants Program, DGECR Discovery Launch Supplement).
1--2222HHUAN
(Discovery Grants Program) and
References
[1] M. Aleksandrov and T. Walsh. Online fair division: A survey, In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 13557-13562, 2020.
[2] Y. Azar, A. Fiat, and F. Fusco. An a-regret analysis of adversarial bilateral trade. Advances in Neural Information Processing Systems, 35:1685-1697, 2022.
[3] F. Bachoc, T. Cesari, and R. Colomboni. A contextual online learning theory of brokerage. arXiv preprint arXiv:2407.00 0..40001166,,, 2024.
[4] Y. Bechavod, K. Ligett, A. Roth, B. Waggoner, and Z. Wu. Equal opportunity in online classification with partial feedback. Advances in Neural Information Processing Systems, 32, 2019.
[5] M. Bernasconi, M. Castiglioni, A. Celli, and Fusco. No-regret learning in bilateral trade via global budget balance. In STOC. ACM, 2024.
[6] A. Blum, S. Gunasekar, T. Lykouris, and N. Srebro. On preserving non-discrimination when combining expert advice. Advances in Neural Information Processing Systems, 31, 2018.
[7] N. Bolić, T. Cesari, and R. Colomboni. An online learning theory of brokerage. In Proceedings of the 23rd International Conference Autonomous Agents and Multiagent Systems, AAMAS 224, page 216-224, Richland, SC, 2024. International Foundation for Autonomous Agents and Multiagent Systems.
[8] L. E. Celis, S. Kapoor, F. Salehi, and N. Vishnoi. Controlling polarization in personalization: An algorithmic framework. In Proceedings of the conference on fairness, accountability, and transparency, pages 160-169, 2019.
[9] N. Cesa-Bianchi, T. Cesari, R. Colomboni, F. Fusco, and S. Leonardi. Bilateral trade: A regret minimization perspective. Mathematics of Operations Research, 49(1):171-203, 2024.
[10] N. Cesa-Bianchi, T. Cesari, R. Colomboni, F. Fusco, and S. Leonardi. Regret analysis of bilateral trade with a smoothed adversary. Journal of Machine Learning Research, 25(234):1-36, 2024.
[11] N. Cesa-Bianchi, T. Cesari, Colomboni, F. Fusco, and S. Leonardi. The role of transparency in repeated fiss--pric auctions with unknown valuations. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 225-236. 2024.
[12] N. Desa-Bianchi, T. R. Cesari, R. Colomboni, F. Fusco, and S. Leonardi. A regret analysis of bilateral trade. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 289-309, USA, 2021. Association for Computing Machinery.
[13] N. Cesa-Bianchi, T. R. Cesari, R. Colomboni, F. Fusco, and S. Leonardi. Repeated bilateral trade against a smoothed adversary. In The Thirty Sixth Annual Conference on Learning Theory, pages 1095-1130, USA, 2023. PMLR, PMLR.
[14) N. Cesa- Desa-Bianchi, R. Colomboni, and M. Kasy. Adaptive maximization of social welfare. arXiv preprint arXiv:2310.0959/ 2023,
11

---

[15] N. Cesa- Fesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge University Press, UK, 2006.
[16] N. Bian-Bi G. Lugosi, and G. Stoltz. Regret minimization under partial monitoring. Mathematics of Operations Research, 31(3):562-580, 2006.
[17] T. Cesari and R. Colomboni. Trading volume maximization with online learning. arXiv preprint arXiv:2405. 130.2,0...1., 13102, 2024.
[18] T. R. Cesari and R. Colomboni. nearest neighbor characterization of Lebesgue points in metric measure spaces. Mathematical Statisties and Learning, 3(1):71-112, 2021.
[19] E. Chzhen, C. Giraud, and G. Stoltz. A unified approach to fair online learning via Blackwell approachability. Advances in Neural Information Processing Systems, 34:1 18418880-1822, 2021.
[20] A. Ciccone, O. Rogeberg, and R. Braaten. Fairness preferences in a bilateral trade experiment. Games, 11(1):8, 2020.
[21] N. Durvasula, N. Haghtalab, and M. Zampetakis. Smoothed analysis of online non-parametric auctions. In EC, pages 540-560, ACM, 2023.
[22] S. Gaucher, A. Carpentier, and C. Giraud. The price of unfairmess in linear bandits with biased feedback. Advances in Neural Information Processing Systems, 18:31363-8, 2022.
[23] Gillen, C. Jung, M. Kearns, and A. Roth. Online learning with an unknown fairness metric. Advances in neural information processing systems, 31, 2018.
[24] S. Hossain, E. Micha, and N. Shah. Fair algorithms for multi- multi-armer bandits. Advances Neurul Information Processing Systems, 34:24005-24017, 2021.
[25] E. Kalai and M. Smorodinsky. Other solutions to Nash's bargaining problem. Econometrica: Journal of the Econometric Society, pages 513-518, 1975.
[26] R. Kleinberg and T. Leighton. The value of knowing a demand curve: Bounds regret for online posted-price auctions. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings,, pages 594-605. IEEE, 2003.
[27] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[28] F. Li, J. Liu, and B. Ji. Combinatorial sleeping bandits with fairness constraints. IEEE Transactions on Network Science and Engineering, 1799119991 2019.
[29] L. Liao, Y. Gao, and C. Kroer. Nonstationary dual averaging and online fair allocation. Advances in Neural Information Processing Systems, 35:37159-37172. 2022.
[30] V. Patil, G. Ghalme, V. Nair, and Y. Narahari. Achieving fairness in the stochastic multi-armed bandit problem. Journal of Machine Learning Research, 22(174):1-31, 2021.
[31] T. Sühr, A. J. Biega, M. Zehlike, K. P. Gummadi, and A. Chakraborty. Two-sided fairness for repeated matchings two-sided markets: A case study of a ride-hailing platform. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 3082-3092, 2019.
International Conference Machine Learning, pages 10686-10696. PMLR, 2021. [32] L. Wang, Y. Bai, W. Sun, and T. Joachims. Fairness of exposure in stochastic bandits. In
[33] H. Yamada, J. Komiyama, K. Abe, and A. Iwasaki. Learning fair division from bandit feedback. International Conference on Artificial Intelligence and Statistics, pages 3106-3114 14. PMLR, 2024.
12

---

A Proof of Theorem 3 Fix any e 1/4] and let
1
1
Pas
60
2 81/4
where 0g is the Dirac measure centered at point R. Noting that, for all p [0. 1].
psl-p- -s--p= = ps
- -- ps
p p- 4
and letting 5* be a random variable with distribution μı= and B we have f* (p) T8 min 5t)+, (B (B)-).)]
El min ( 5t) 1- 1-p]
pp]
1 1
min {1D- (p- 4
1
= min (p, 1 1pp
1
2
2
ltc
pe (0,01//4
2 P
Lse
2 p+ (p 1) ltf
(<(1/,,
7
(1 p) 1sc
1sc
i 2
(1 p)
1se + (1 (1-p) p)
[=[5/8,1]
2
L=
pc (0,11/4)
P
1sc
8 p 1)
[=/14,1/22
+ 1 -p)
De [
lst
-p)
pe [5/8,1]
Note that:
argmax f" 1
and
f ("
1+c 1 3+
2
5
f 1 1-6 6 3
argmax f
and
8
8
1+ Consider the three regions psub = - (9/16, 1]. At high level: suub is an informative, but ((())ssuopptim) region: in contrast, regions I" and I are both uninformative, but, when the underlying distribution of the sellers' valuations is pts (resp, p(=)) 1" (resp, I") contains the maximizer p, 2 (resp, p- )) while all points / (resp., 1*) are ((e)-suboptimal. More precisely:
Since B 1, the feedback 1fps B} is immaterial.
The feedback I1 p) observed by posting price p suub at time e N is Bernoulli Moreover, for all p ysub
random variable with parameter 2
1tc
3+
1+
max / - (p) = 2 1r (p)
=
p2
8
2
4
max f- ())
3
1-5
f (p)
8
2
4
high level, posting price p E Guab reveals information about the underlying distribution of the sellers' valuations but at the cost of an instantancous regret of at least 1/4.
The feedback I(S; < p} observed by posting a price E I' at a time e N when the underlying sellers' distribution is fee constant random variable always equal to 1. Moreover, argmax / = TT, but, for all p I*,
()- 2 - 16 if [1/2,9/16)
i 11/4,1/2)
max f (x)
high level, posting a price reveals no information about the underlying distribution of the sellers' valuations, the region /* contains the optimal price when the underlying distribution of the sellers' valuations is M+z. but posting I has an instantaneous regret of at least e/16 when the underlying distribution of the sellers' valuations is p-g-
13

---

The feedback 1{S & p\ observed by posting a price I at a time t e N when the underlying sellers' distribution is paz constant random variable always equal to 1. Moreover, argmax f -= 5 T. but, for all per. r
1tz + ( 8 8
( +
p e [9/16, 5/8) p [5/8.1] 1]
max f -f = 1+z + ( 1-c + - + (p) 16
At a high level, posting a price p I reveals no information about the underlying distribution of the sellers' valuations, the region / contains the optimal price when the underlying distribution of the sellers' valuations is μ! but posting in I has an instantancous regret of at least s/16 when the underlying distribution of the sellers' valuations is p.s.
We will now show that these two "+" and "-" instances are no easier than two corresponding instances of related partial monitoring game (for the reader unfamiliar with partial monitoring, see, e-g. 27 Chapter 271). Consider the following partial monitoring game, where, again e [0. 1/4], the learner's action set is (1,2.3), the environment's outcome set {1, 2), the reward (p) and feedback (i)) matrices are, respectively,
0
1
0
p
1/16
0
and
yp
0
0
1/16
0
0
and where the environment is constrained to draw outcomes i.idd from of two distributions: the first of which has probability 1/2 of drawing outcome 1, while the second has a smaller probability of" 2 of drawing outcome 1. More precisely, let (A1, A 42: .2....) be independent sequence of (1, 2)valued random variables such that (Af) is i.i.d. sequence satisfying P[A; 1]= }
for all e N, and (A,))ett JeN is an i.i.d. sequence satisfying P[A; = 1] 2 - for all N. In the "+" (resp, a "-") scenario, at any time t. the environment plays outcome A (resp., A,). Therefore, the scenario, the learner's s optimal action is action 2, and, for all f N, the instantancous expected regrets paid by the learner for playing action 1 (resp., (resp., (E(((2,A)))
E[p(2, - A;)] 32 + 32 S TR Similarly, in the scenario, the learner's optimal action action 3. and, for all / N. the instantaneous expected regrets paid by the learner for playing action (resp., 2) is [[p A7)] E[p(1, [[)] 32 + &
E[, A?) = 32 32
32
32
32 (resp.,
E[p(3, - feedback, while the feedback (p11 A,) that the learner observes after playing action time e N
(7)](21)]]=) 17)]
( S ( 32 32 ). Finally, playing actions or 3 reveals no
in scenario "+" is Bernoulli random variable with parameter 2 + 2
Note now that every algorithm for the fair bilateral trade problem can be turned into an algorithm for this partial monitoring game by simply mapping the price Ps that the algorithm would post at any time N into the action
1 if P. Taub if Pi e I*
J
2
3
if P. I
then feeding back to the algorithm the pair (s((1, Af), 1). By construction, this is the same feedback (more precisely, it is Bernoulli random variable drawn i.i.d. from the same distribution) that the algorithm would observe by playing P; in the original fair bilateral trade problem, and the expected regret of the partial monitoring game is less than equal to that of the original fair bilateral trade problem. Therefore, by lower bounding the regret of the partial monitoring game, we fortiori lower bound the regret of the fair bilateral trade problem. To conclude the proof, we simply remark that for any algorithm for this partial monitoring game there exists a choice of [0, 1/4] such that the regret of the algorithm is at least rewards and rescaling them by multiplying by 1/16).
(see, e.g., [16] Theorem 5.1], up to turning losses into
B Proof of Theorem 4
Given that we are in a deterministic setting, without loss of generality we (can) restrict our analysis to deterministic algorithms. Let b We begin by proving the following property by induction on k = 0, 1,,,....
14

---

Property. There is a segment Es of length 7 satisfying E, = [o. such that, for each s, Eg. the algorithm receives the same feedback from the environments defined by (s, b) and (s', "b,, b))-and thus selects the same query prices- as long as it has allocated at most & prices in the segment [0, =
and
For k O the property is true by setting En == [0, } since long the algorithm posts no prices in [0. 11 it receives for each price P. : 1] the feedback I[s < Pt) [[ s P:) 1 and I(P, s b) P(p s 1) =
Assume that the property is true for some & {0, 1. We set [c, d] == Es for the segment the until it posts price
property. For any Eg. the algorithm has behavior that does not depend Pt E [O. 1] for the (A+ + 1)-th time, since before that it has received feedback that does not depend on s. If the algorithm never posts a price P. [O. ]]] for the (k + 1)-th time, then the property remains true (e.g., by setting Eg-1 == add d)). If the algorithm posts this price P. for the (I: 1) 1-tth time, we std Note that this price Pt is the set Ex-1 == _ d] Pt < end and we set Ex+1 = [c, - if P3 2 2 same for any e Ek+1, since depends only on the feedback from times 1 to t- 1. At this time t, for any s E Es+1, the feedback is the same. Indeed, regardless of which $ E E we might choose, this feedback is (I(s S P.). s 6)) = (0.1) if P, atd while it is (Ifs s P.). S 6)) = (1,1) 2. The feedback then remains the same for all the next times until time t' t when the
?
2
if P. 2 std algorithm posts price P. [0, 1 for the (k 2)-th time. Hence the property is true step k + 1. Note that our construction shows that we can even consider nested segments F.g 2 F1 2 Eg 2
There is a value k* of k {O...., T)) such that the property is true, and for any S Éxe, the algorithm posts exactly k- times price in [o. 11 from times to T. This is because if we write to = 0 and for k 1, l for the time at which the algorithm posts for the k-th time price in [0, 3] (for any e Ex), then we have to $ f S ... Hence, we let k" be the largest l such that 1 $ T.
For any E Eg the instantaneous regret for the time steps where P. [0. ] is lower bounded
b- (P: 5)+
3
1
2
8
8
Then let T be the set of time steps {l,..., T) when P. E 22, Note that (Pi) does not depend on which s E Eg- we might have chosen. The FGFT function reaches its maximum value b=s brs at 2- [ ]. and decreases with slope one in the segments
2
b+s
and b+s 2 .1]. Hence, the FGFT
[
function at any pe (3. 1] is equal to b-g Ip btel
2
Hence the cumulative regret for the steps in T is lower bounded by
b+ 2
b+ b+.)
-
6 P.
- 2 2
Σ RT
P.
Σ 1=
P
Σ ET
Since the prices Pı,..., Pr chosen by the algorithm are the same for any s e Ek., then IT Eier P. does not depend on 8 and thus we can move s in the segment length 2 k* and find a value of s
for which ( EeeT Pt - }) 1 2 Hence, for this s the cumulative regret of the steps in T is lower bounded by
1 2"
IT|
16
In the end, the total cumulative regret is lower bounded by
k²
1
(T-
16
h 2 T we can lower bound the total cumulative regret by T cumulative regret by
Else, we can lower bound the total
2,
16
k*
T2
8
32
2k
T then the total cumulative regret is lower bounded by loga(T) (T)
Else, we have
32
T
24"
2 VT,
loga (T)
15

---

where in the last inequality we used T 17, and hence h- 2 log2(vT) lower bound
log,(2)
In the end, the
T
loga (T)
loga
min
16
32
32
C Pseudocode of Double Binary Search Pricing and proof of Theorem 5
The pseudocode of Double Binary Search Pricing is given in Algorithm 3 In the algorithm and in the proof, we use the following notation: for a segment of the form c, d] with < d, we define left (cft(E) c, mid(E) e-d and right(E) d.
Algorithm 3: Double Binary Search Pricing Deterministic setting
Input: horizon T N; Initialization: Set Eg Eg [0, 1]. If 1 7 set N [[lgg else set N
for time t= 1.2..... N do
Post price Pj == middmm(ss))
if S P. then
Set F.s = [left Fis), mid( Fis)];
else
Set Es = [mid( Es), right (Es)];
for time N 1, 2, 2....... 2N do
Post price Pt == mid EB);
if < b then
Set FB = [mid( En) right (En)];
clse
Set Fg [lest FBB), mid FBB)];
for time = 2N 1....,T T do
Post price P. mid(Es)) -mid))mmii
We now present the full proof of Theorem
Proof. If T < (T)) + 1, the result is true because FGFT takes values in [0, 1] and so the instantaneous regret at any time is bounded by 1. Consider then the case (T)
T.
The cumulative regret from time steps to 2NN is bounded by 2N 2 2oog (7) because FGFT [0. 1]. It is easy to see that the property that Ei is maintained from time steps to N. At time N (after which Es is left unchanged), the length of Es smaller than or equal 2-N 1. Similar properties hold for b and Eg. Hence, at time steps 2N 1....,
T
T, we have that
1mid(EE)) mid(Ex) +
1 (1s mid( Es) + |b- mid (Edd())))) 1 T
(6)
2
Therefore, the individual regret each one of these time steps bounded by
b b-x min midd Es) + mid(Fg)
(6 mid( (Es) mid EB))
2
2
2
If h 8 T. mid(Es) mid( EB).
1 2 this quantity is smaller than or equal to 7. If & 7: then from
6
we have
b
mid Es) + mid(EB)
s
s 1 2
8
2
2
2
2
T
Similarly
b mid (E)) + mid EB)
b -
mid( Es) + mid(EE)))
s+b
b b-s 1
2
2
2 T
Hence, the quantity in 7 is smaller than or equal to 5. and consequently, the cumulative regret from steps 2N 1 to T is smaller than equal to T-2N 1. Putting everything together, the cumulative regret from steps 1 to T' is smaller than equal to 1 2[log (T)
16

---

D Proof of Theorem 6
For notational convenience, let B)) be another pair of seller/buyer valuations, independent of the whole sequence (St, IeN and sharing the same distribution of any element in this i.dd. sequence.
The proof shares ideas with the proof of [ Theorem 1]. For each p e [0. 1]. notice that, as
consequence of Equation ① in Lemma]
!
we have
S,FG S P[(S sp- ut + s du G(p),
and, for each & N, also
SG, = J - Bu du G.(p)
1=1
We have, for any p e [0, and any t N.
[G(p) -(())) = S.
J Σ Sp- -p u} du
=l
[[(Ss)](-Bss]] E1ss: x, - BBs B
$ sup 2.yeR
Hence, we can apply the two-dimensional DKW inequality, see 99 Theorem 15, Appendix JJ. from which it follows that there are positive constants mo s 1200, c₁ s 13448 and c2 1/576 such that for all E O, if t 2 mo/E?.
F((G(p) G.( 26 s
[[(Ss=)n(-BBu]) Z.yeR
US B su 28 cate"
sup
Hence, for each t N, by Fubini's theorem, we have that
sup [G(p) ((()) = [=][0.]]
I sup [x[[o.]]
26 de V
mo
+
G exp(-cate") de
ma
f. exp(-cats de
mo
2T
|
CIV π
1
2
222t
2/
Vt
Then, for any N, have, using the law of total expectation conditioned on (Si, B:)
El B..,)) 3|
[3(p) - G(x) 52 / + CIVT
s +GG)))-((C(+))))+C((3))))) 2
sup pE[[0,1]
2/02 Vt
Hence, for any 7
CIVT π
s1+ 4 \m + CIVT π
Rr 11
VT
2/
t=2 vt
2//22
17

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Theorems correspond to all claims (with clear statements and proofs).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Section 0
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
18

---

Justification:
All claims are clearly stated (including assumptions) and all proofs are present.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: There are no experiments in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
19

---

Answer: [NA]
Justification:
The paper does not include any dataset or code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
icy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppi.ccppulli//uuuiu wwwticccguie//eeeeeeeeeis CoodeSubeiiieeee ssi wsionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
There are no experiments in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: There are no experiments in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
20

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: There are no experiments in the paper.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
Our thcoretical work aims to establish fair trading mechanisms.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., -., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
We do not see any negative societal impacts of our theoretical work. In fact, its goal make positive impact on trading mechanisms by improving the fairness of exchanges.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
21

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Being theoretical work, we are not releasing any data or models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We do not any assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
22

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not introduce any assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
23


Reviews:
[{"review_id": "rlzTXRgHyf", "reviewer": "Reviewer_mLA5", "summary": "The paper focuses on the online bilateral trade problem, in which at each round a buyer and a seller with private valuations for an item arrive, and the platform has to post prices for the item being traded. In this paper the objective of the platform is that of maximizing the cumulative “fair gain from trade”, that is the minimum between the seller’s and buyer’s utilities. \n\nIn the two-bit feedback setting, the paper proves a tight $O(\\log T)$ regret bound in the deterministic setting, and a $O(T^{2/3)$ regret in the stochastic setting when seller’s and buyer’s valuations are independent of each other. In the full-feedback setting, the paper provides tight regret bounds.", "questions": "See weaknesses", "limitations": "Limitations are discussed.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The paper is well-structured and explores a research direction which could potentially be very interesting.", "weaknesses": "Section 2 is clear but does not sufficiently explain the additional challenges that need to be addressed compared to the standard online bilateral trade framework by Cesa-Bianchi et al. (EC 21).\n\nThe main area for improvement in this paper is the generalization of the results beyond the specific objective of Fair GFT. What is the general structure required to achieve results similar to those presented? Could similar results be directly obtained for other objectives? The justification for focusing specifically on maximizing Fair GFT is not particularly convincing at the moment. Developing a broader framework to address these problems would significantly strengthen the results and make them more widely applicable and interesting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Additional challenges here compared to Cesa-Bianchi et al., EC '21\n\nA first high-level observation is that the pairs \"assumption\"/\"regret rate\" differ between our setting (Fair Bilateral Trade) and that of Cesa-Bianchi et al. [10] (\"regular\" Bilateral Trade), suggesting that different ideas will be needed to obtain optimal results for each pair. \nFor example, while smoothness (bounded densities) was crucial in obtaining sublinear rates in [10], we had to understand that, in our work, it plays no role, and consequently discover new algorithmic and proof ideas.\nAt a very high level, we share with [10] the same issue of having poor feedback, which is not even sufficient to reconstruct the reward at the price we post. \nIn our case, however, the different form of the objective requires new procedures to recover usable information on the reward function, which is made possible by our new Convolution Lemma.\nAnother difference is that, in [10], to maximize the realized gain from trade, it is sufficient to post a price $p\\in[S,B]$, while, in our case, we have to address the more delicate task of locating the midpoint $p = (S+B)/2$. \nThis is the reason why (even optimal) algorithms for bilateral trade can suffer linear regret in our setting (as we show in Section 2).\nAnother technical subtlety that we had to tackle is that a direct application of the convolution lemma in the 2-bit feedback setting would yield a suboptimal upper bound of $T^{3/4}$. \nInstead, by carefully defining a data-gathering procedure such that each observation contributes to estimating the convolution of the cdfs at *all* points, we are able to obtain the optimal $T^{2/3}$ rate.\nWe will better highlight these various challenges in the paper. \n\n- Justification for focusing specifically on maximizing Fair GFT\n\nWe fully agree that developing a broader framework is an interesting goal to pursue. We suspect that obtaining estimators for a reasonably large class of objective functions in bilateral trade could be a challenging problem if one aims at capturing at least both the GFT and FGFT objectives.\nThe main reason for this difficulty is that different objectives would likely require significantly different techniques due to the problem-specific quantities that the learner has to estimate.\nFor example, the fair and regular gain from trade problems rely on different algorithms, estimation lemmas, proofs, and assumptions, as discussed above.\n\nOur specific focus on the Fair Gain From Trade objective is motivated by the so-called egalitarian rule in social choice theory (sometimes also called the max-min rule or the Rawlsian rule), where one favors the alternative that maximizes the minimum utility of the involved parties to promote fairness. We will add a paragraph about this bullet point in the revised version.", "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": "zRpRNi0NyW", "reviewer": "Reviewer_6Ak7", "summary": "The paper considers a fair version of online bilateral trade problem to minimize fair GFT regret w.r.t. optimal fixed price in hindsight.\nThe paper is comprehensive in studying both upper/lower bounds in various settings.", "questions": "- Has the one-shot version of this problem ever been studied? I.e., whether FGFT can be constant apx to the ex-post FGFT or any structural connection between FGFT, first-best GFT, etc.\n- It seems the regret lower bound largely depends on a highly concentrated distribution. Do you think a sort of smoothness assumption like regularity or monotone hazard rates can be a remedy for better regret bounds", "limitations": "Mentioned above.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The problem setup is pretty interesting, with a good motivation to the practical scenario.\n- The paper is pretty comprehensive, and the paper well-written and easy to follow.\n- It is interesting that ETC style of algorithm is order-optimal.", "weaknesses": "Technicality\n- It is good to know that the ETC style of algorithm 1 works well, but I must admit that it is not particularly interesting.\n- The algorithm for deterministic case is also tight, but the algorithm itself is a straightforward application of binary search, and the regret lower bound is not difficult to come up with, so I would exclude this section for my evaluation.\n\n\nMinor comments\n- Is it necessary to have bounded support of [0,1] for the valuations? If not (or it's wlog), it would be worth mentioning it. \n- Why would one need to invoke minimax theorem to argue Remark 1? It seems to trivially follow as the adversary there is simply stronger, correct me if I'm wrong.\n- It might be good to decompose the introduction to explicitly distinguish the true intro / the paper's results / relate work. As of now it's difficult to follow the intro as they are highly mixed up.\n- L#80 does not seem necessary, or a footnote might suffice.\n- The problem of online bilateral trade itself seems highly relevant to Kleinberg and Leighton FOCS'03 (Bounds on Regret for On-line Posted-Price Auctions) and its follow-up works, but it is never mentioned.\n- Since the algorithm is rather simple but is proven to be order-optimal, I think it would be good to add experiments to see whether it works well compared to other candidates from standard bandit literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Weakness 1\n\nWe are not sure we understand what the reviewer meant here. \nWe are happy to provide clarifications if the reviewer needs some.\n\n- Valuations not in $[0,1]$\n\nExtending beyond $[0,1]$ works as in the bandit literature: If $[0,1]$ is replaced by $[0,m]$ (for some $m$), the same results apply up to a multiplicative $m$; If the interval is unbounded, no meaningful results can be obtained, unless additional assumptions on the distributions are made (e.g., $\\sigma$-sub-Gaussianity, with known $\\sigma$).\n\n- Why minimax?\n\nYao's minimax theorem immediately implies the result, but the reviewer is correct in stating that the result would have also followed by observing that a lower bound on the expected regret of the stochastic case implies a lower bound in the adversarial case because in-expectation lower bounds can be turned into worst-case lower bounds.\nWe will mention this in the revised version.\n\n- Kleinberg and Leighton (FOCS'03)\n\nWe agree that dynamic pricing is a sufficiently related setting to be mentioned in the related work section. \nThe revised version will contain a paragraph about it.\n\n- Experiments comparing against bandits\n\nThe comparison with bandit algorithms would not be fair given that bandit algorithms cannot run in the two-bit feedback setting (the two bits of feedback are not sufficient to reconstruct the realized reward of posted prices, see Lines 39-41).\nMoreover, from a practical point of view, the bandit version of our problem is not well-motivated, as it is hard to imagine that a learner would be able to observe the reward of a price without access to the valuations (which would lead back to the full-info case).\nIf the reviewer agrees with us, we would prefer not to implement this change.\n\n- One-shot version\n\nTo the best of our knowledge, we are the first to introduce this fair variant of the bilateral trade problem, which arose as a natural continuation of the recent stream of works on online learning in bilateral trade.\nWe agree with the reviewer that studying the one-shot version would also be an interesting extension of our work.\n\n- Does regularity help?\n\nIt does not, in fact, our current lower bound constructions could be modified by \"smoothing\" the Dirac masses into uniform distributions over squares, obtaining the same results. \nTo give some intuition as to why this is the case, in bilateral trade problems, smoothness helps by making the objective (i.e., the expected reward) Lipschitz, which in turn reduces the continuum-arm problem to a finite-arm problem via discretization.\nIn the *fair* bilateral trade problem, however, the objective is already $1$-Lipschitz with no further assumptions.\nWhat hinders learnability in our problem is a lack of observability, which is recovered by assuming independence of buyers and sellers.\nAlthough we don't have an explicit lower bound construction at hand for the monotone hazard rate, we believe that this assumption would also be insufficient to obtain learnability.", "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": "vqhLV9sviu", "reviewer": "Reviewer_89Fg", "summary": "This paper studies the fair online bilateral trade problem, where a platform posts prices for one item at a time. At each time point, a (buyer, seller) pair arrives, each with private valuations. A trade occurs if the posted price is between the buyer and seller valuations. In this paper, the goal is to maximize the minimum utility of the buyer and the seller; this differs from prior work, where the objective was to maximize the total utility. The paper considers multiple valuation regimes, including deterministic, stochastic, stochastic and independent, and full feedback, and bounds the regret in each regime.\n\nThe main results of the paper are as follows. First, the paper provides a linear lower bound in the stochastic case where buyer and seller valuations are not necessarily independent. The paper complements this result with an upper bound of $\\tilde{O}(T^{⅔})$ in the stochastic case where buyer and seller valuations are independent. This result relies on the Convolution Lemma, which is the key technical insight from the paper. The paper further shows that in the deterministic setting (where buyer and seller valuations are fixed over all rounds), there is a tight regret bound of $\\Theta(\\ln(T))$. Finally, when valuations are known, the paper provides an algorithm which achieves $O(\\sqrt{T})$ regret and shows that this bound is tight.", "questions": "How well and/or easily would the main results generalize to a weighted fair gain from trade objective? For example, would similar arguments work if the buyer’s utility was weighted twice as much as the seller’s utility?\n\nWhat types of applications come to mind for the fair online bilateral trade problem?", "limitations": "The authors have adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The problem statement is interesting and the difference from prior work is clearly stated. The model is clean and easy to understand, and I appreciated the formal problem definition in lines 114 - 117. The paper provides comprehensive results (often both lower and upper bounds) for multiple reasonable assumptions, and gives intuition for where the difficulty comes from in each regime. The work seems relevant for NeurIPS.\n\nI found the paper to be very easy to follow. The assumptions are clearly stated in each section, and the presentation is generally well done. In particular, I liked how the theorem statements are rigorous and clear and that proof sketches are given when there is a lack of space for full proofs. The proofs are nicely written and correct as far as I checked. In particular, Lemma 1 (the Convolution Lemma) was clean and clever, and is made good use of throughout the rest of the paper (i.e. in the proofs of Theorems 2 and 6). I felt that the lower bound examples in section 2 and in the proof of Theorem 1 were also excellent at building intuition for the remainder of the paper, and interesting examples in and of themselves.", "weaknesses": "The structure of section 1 made it a bit harder to follow than the rest of the paper. Personally, I would have found it helpful for section 1 to be split into multiple parts (such as intro/related work/our contributions) in order to be able to more easily pinpoint the main contributions. \n\nWhile the paper presents a very nice theoretical model, it does not discuss many applications. I would have found it helpful if the paper had further discussed applications of fair online bilateral trade – for example, by discussing when such an objective function would make sense.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Weighted fair gain from trade objective\n\nA possible weighted generalization of the fair gain from trade could be\n\n$WFGFT(p,s,b) = \\min( w \\cdot  (p-s)^+$, $(b - p)^+ )$\n\nfor a fixed constant $w \\ge 1$ and where we recall that $p$ is the posted price, $s$ is the seller valuation and $b$ is the buyer valuation. \nThis would address the reviewer's question in the sense that here the buyer's utility (profit) is valued $w$ times that of the seller. \nFor fixed $s <b$, the optimal price is  $(w s + b) / (w+1)$, and this price gets \"pulled\" toward the seller side as $w$ increases, thus increasing the buyer's profit (since the buyer's profit is valued more).  \n\nOur regret upper bounds can be extended to this weighted fair gain from trade. This is straightforward in the deterministic setting, since we just need to locate the optimal price $(w s + b) / (w+1)$. We either see it immediately (in the full-feedback model) or, otherwise, we use a binary search.   \n\nIn the stochastic case, the following extension of the convolution lemma can be shown to hold (recall that it is under independence of buyer and seller):\n\n$\\mathbb E [  WFGFT(p,S,B) ] = \\int_0^1 \\mathbb{P} [ S \\le p - \\frac{u}{w} ] \\mathbb{P} [ u+p \\le B ] du $\n\nHence the proofs (Theorems 2 and 6) can be extended with minor adjustments, yielding the same rates. \n\nAnalogous considerations hold for lower bounds, which can be easily adapted to obtain the same rates we obtained for $FGFT$.\n\n- Applications of fair online bilateral trade\n\nA natural application is online ride-sharing services like Uber and Lyft where fairness problems have been previously studied, although in different settings with metrics different from ours (see, e.g., Sühr et al. \"Two-sided fairness for repeated matchings in two-sided markets: A case study of a ride-hailing platform\", 2019).", "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": "Xq9gjfkVDu", "reviewer": "Reviewer_rYk6", "summary": "This paper addressed the problem of fair bilateral trade: at each round $t\\leq T$ a buyer and a seller, with respective valuations $B_t$ and $S_t$, want to trade a good. The agent acts as a facilitator for the trade, by posting a common price $p_t$. The trade happens if $p_t \\leq B_t$ and  $p_t \\geq S_t$. Importantly, the agent only observes the two-bit feedback $(\\1{p_t \\leq B_t\\}, p_t \\geq S_t)$. \n\nIn classical bilateral trade, the objective is to maximize the cumulative expected Gain From Trade (GFT), where the GFT at round $t$ is $B_t - S_t$ if the trade succeeds, 0 otherwise. Here, the authors propose to consider an other performance measure called the Fair Gain From Trade, defined as $\\min(B_t-p_t,p_t - S_t)$ if the trade happens, 0 otherwise. This performance measures encourages trades that share fairly the utility between buyer and seller.\n\nThe authors first consider the two-bit feedback model with i.i.d. valuations of for the buyer and the seller. They show that, as is the case when maximizing the GFT, the FGFT can be linear in $T$ if the seller's and the buyer's valuations are not independent. Interestingly, when these valuations are independent, regrets of order $\\tilde{O}(T^{2/3})$ (in terms of FGFT) can be achieved under milder assumption than when considering GFT: namely, Lipschitz continuity of the c.d.f. of the valuations is no longer required. They provide a matching lower bound, proving that this rate is tight up to logarithmic factors. They also consider deterministic valuations, showing that in this case, the regret scales as $\\log(T)$ (they provide an upper and lower bound on the regret). Again, this departs from the regrets observed when maximizing GFT. Finally, they consider the full information model, when the agent observes both $B_t$ and $S_t$. They show that in this case, the regret scales as $\\sqrt(T)$ in the stochastic case, which is optimal, and is constant in the deterministic case.", "questions": "The problem of bilateral trade is closely related to that of dynamic pricing. Do you know any work studying fairness in that setting?\n\nAlthough I understand that this is probably beyond the scope of this already dense paper, do you think your results could be extended to the one-bit feedback setting?", "limitations": "The authors addressed adequately the limitations of their work.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper studies an interesting an well-motivated problem. The results provided highlight a very different behavior than in classical bilateral trade problems, which I find very interesting. The treatment of the subject is thorough: the authors explore various models, including two-bit and full feedback, as well as i.i.d. and deterministic valuations, and both independent and dependent valuations. For each case, they provide matching upper and lower bounds on the regret. They also comment on the adversarial case.\n\nThe paper is also very clear and well-written. Each theorem is accompanied by easily understandable proof sketches, supplemented by rigorous proofs in the Appendix.", "weaknesses": "There are no major weaknesses.\n\nAs a minor suggestion, given the paper's density, it might be helpful for readers if the rates in the different settings were summarized in a table, alongside the corresponding rates for maximizing the gain from trade.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Adding a summary table\n\nGreat idea! We are happy to do it. \n\n- Fair dynamic pricing\n\nThe few existing works on fair dynamic pricing study notions of fairness that are orthogonal to what ours would be when translated to dynamic pricing. \nFor example, see Xu et al., Doubly Fair Dynamic Pricing, and Maestre et al., Reinforcement Learning for Fair Dynamic Pricing.\nNote that in bilateral trade, since the platform is the learner, there is a symmetry between the buyer's and seller's utility, and thus, it is sensible that our fair gain from trade function strives to make their utilities as similar as possible.\nIn contrast, in dynamic pricing, the seller is the learner, and hence there is an inherent asymmetry in how the learner will choose their objective. The seller might still have an incentive to reduce their margin to improve that of the buyer because this way, they could provide enough incentives for buyers to join and continue using the platform.\nFor this reason, we think that a suitable alternative reward function in dynamic pricing should remain somewhat asymmetric and give more weight to the seller's margin. \nAn example can be the minimum between the seller's profit and a factor of $w$ times the buyer's profit.\nA similar idea was also discussed in the answer to reviewer 89Fg, in the context of bilateral trade.\n\n- One-bit feedback\n\nWe conjecture that the techniques in [8] can be tweaked to show that learning is impossible with 1-bit feedback, for reasons analogous to that in [8]: lack of observability. With only 1 bit of feedback, we conjecture it is possible to build two different instances that are undistinguishable from one another such that the optimal price in one instance is highly suboptimal in the other.", "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:
We thank the four reviewers for the time spent reading our work and for sharing their comments.
We will update the submission in light of the feedback. 
In particular, we will further highlight our technical contributions and the economic relevance of our results, we will provide additional discussions and clarifications in light of the comments and questions, and we will discuss potential extensions of our results. Additionally, we agree that subdividing the first section into "Introduction", "Related Work", and "Our Contributions" will improve readability.  The revised version will be structured as suggested. 

Given the additional content page allowed, and the available time left, we are confident that we will successfully improve the submission with the requested changes.

We hope that our four separate responses have appropriately answered all questions and comments. We remain available should any further clarifications be needed.

Meta-review: The paper studies an interesting and natural extension of the online bilateral trading model, where the goal is to maximize the minimum gain across the buyer and the seller, instead of the sum of their gains. The consensus is that the extension is well-motivated and has clear practical relevance. In addition the paper provides solid and comprehensive results on the achievable regret in various settings. Furthermore, the paper is well-written and well-structured. By tying well with the themes of fairness and online algorithms, the paper would be interesting to broader community.
Decision: Accept (poster)