Fair Online Bilateral Trade

Authors: françois  bachoc
nicolò  cesa-bianchi
tommaso  cesari
roberto  colomboni
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 17:01:57

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.

Main paper: 
 introduction: 
 In the online bilateral trade problem, at each round t = 1, 2, . . . a seller and a buyer with private valuations for a certain good connect to a trading platform. The seller's valuation S t is the smallest price at which they are willing to sell the good. Similarly, the buyer's valuation B t is the highest price they would pay to get the good. The platform posts a price P t to both buyer and seller. A trade happens if and only if both agents agree to trade, i.e., S t ≤ P t ≤ B t . At the end of the round, S t and B t remain unknown and the platform only observes I{S t ≤ P t } (i.e., whether the seller accepted the deal) and I{P t ≤ B t } (i.e., whether the buyer accepted the deal).Previous works [12, 2, 9, 13, 7, 5] focused on minimizing regret with respect to the gain from trade function GFT∶ (p, s, b) ↦ (bs)I{s ≤ p ≤ b}. The quantity GFT of the seller's utility P t -S t and the buyer's utility B t -P t 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 P t not being close to the mid-price (S t + B t )/2. As argued in [20] , prices generating unequal gains may lead to a reduced participation in the market, which translates to less trading on the platform.To address this problem, instead of using the sum of the utilities (i.e., the gain from trade) as 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 P t as close as possible to the mid-price, equalizing the profit of sellers and buyers. We call this new reward function fair gain from trade and denote it by FGFT. Our specific focus on 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., I{S t ≤ P t } and I{P t ≤ B t }) are not enough to compute bandit feedback (the reward earned by posting the price P t )-neither for FGFT nor for GFT. 1Our 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 1), achieving a regret of Õ(T 2/3 ) after T rounds (Theorem 2). This algorithm is built around the key Convolution Lemma (Lemma 1), which shows how one can estimate the expected FGFT through the feedback the learner has access to. Algorithm 1 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 a 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, e.g., [15] ), that force the learner to perform a certain amount of costly exploration. An analogous phenomenon shows up even in the deterministic case, where S t = s and B t = b for all t and for some unknown constants s, b. In this simpler setting, we prove that posting some clearly suboptimal but informative prices is unavoidable, showing that no strategy can obtain a regret better than Ω(ln T ) (Theorem 4). We complement this result by showing that this rate is 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 t , B t ) are drawn i.i.d. from an arbitrary joint distribution, then the FGFT regret must grow linearly with time (Theorem 1).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 (S t , B t ) is revealed at the end of each round-the so-called full feedback model. Here, we show that a regret of O( √ T ) can be achieved for any joint distribution of sellers' and buyers' valuations (Theorem 6), and we show that this rate is optimal up to constant factors, even if we assume that the traders' valuations are independent of each other (Theorem 7).Our results are summarized in Table 1 .Technical challenges. When regret is minimized with respect to the gain from trade, the independence of sellers' and buyers' valuations is not enough to guarantee sublinear regret, and an additional smoothness assumption2 is required to compensate for the lack of Lipschitzness of GFT. In [9, 10] the optimal regret for GFT under the smoothness assumption turns out to be the same as the optimal rate Θ(T 2/3 ) achievable for FGFT without smoothness. This happens because the fairness condition confers Lipschitzness to the gain from trade, allowing us to compare against a broader range of distributions. In 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., a 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.e., our new Convolution Lemma (Lemma 1)-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 ∈ [S, B]. 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 3/4 . To obtain the optimal T 2/3 rate, we carefully define a data-gathering procedure in which each observation contributes to estimating the convolution of the cdfs at all points.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 Θ(ln T ) rate when the reward function is FGFT, as we discuss at the beginning of Section 4.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, 17, 3] .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 [6] considers online prediction with expert advice and studies the problem of combining individually non-discriminatory experts while preserving non-discrimination. An early investigation of fairness in linear bandits is 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 a specific group of actions. In [4] , 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 [28, 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 fairness requirement is also considered in [32] where the optimal policy is pulling an arm with a probability proportional to its merit (a problem-specific function of the arm's expected reward). Finally, the work [24] considers a K-armed bandit setting in which pulling an arm yields different rewards for different agents. The algorithm's goal is to control regret against the optimal Nash Social Welfare (NSW). The NSW of a 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 [1] , 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 each 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 a 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 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 as an online version of the Kalai-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 in online fair division, instead, corresponds to the Nash solution to the bargaining problem.Finally, we mention that the line of research where online learning is applied to trading problems, was initiated in one-sided settings, like dynamic pricing, whose seminal paper was [26] . For an interesting comparison of (a 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, 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 p ∈ [0, 1] and any s, b ∈ [0, 1], we define the fair gain from trade achieved with p when the seller's valuation is s and the buyer's valuation is b byFGFT(p, s, b) ∶= min {(p -s) + , (b -p) + } , where x + ∶= max{x, 0} for any x ∈ R.We assume a stochastic model where the sequence (S t , B t ) t∈N of sellers' and buyers' valuations is an i.i.d. process with a fixed but unknown distribution. The regret after T rounds of an algorithm posting prices P 1 , P 2 , . . . is defined byR T ∶= max 0≤p≤1 E [ T ∑ t=1 FGFT(p, S t , B t )] -E [ T ∑ t=1 FGFT(P t , S t , B t )] .In the deterministic setting (which can be viewed as a special case of the above stochastic setting) there exist s, b ∈ [0, 1] such that, for every t ∈ N, it holds that S t = s and B t = b. In both cases, note that the maximum exists because the expected FGFT is a 1-Lipschitz function of the price.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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
maximization of gain from trade does not imply fairness: 
 In this section, we show that, in general, a no-regret algorithm for GFT fails to achieve no-regret guarantees for FGFT.Consider the stochastic setting, where the sequence (S t , B t ) t∈N is an i.i.d. process. Pick 0 < h < 1/2 and, for all t ∈ N, let S t be such that S t = 0 with probability 1/2 and S t = 1h with probability 1/2. Let also B t = 1 for all t ∈ N. Then, the only prices maximizing GFT are those in the interval[1 -h, 1]. Now, any price p ∈ [1 -h, 1] achieves an expected FGFT of E[FGFT(p, S t , B t )] = 1 2 ⋅ (1 -p) + 1 2 ⋅ min{(1 -p), (p -(1 -h))}and the maximum of this quantity is h/2, which is attained, for example, by posting p = 1h. On the other hand, it is easy to see that the maximum of the expected FGFT on the whole interval[0, 1] is 1/4 > h/2, achieved by posting p = 1/2 / ∈ [1 -h, 1]. So, if we use any no-regret algorithm for the standard bilateral trade problem to post prices P 1 , P 2 , . . . , we suffer linear FGFT regret on this instance. Even more strikingly, on these instances, for any t ∈ N,E[FGFT(1 -h, S t , B t )] E[FGFT(1/2, S t , B t )] = 2h → 0 + for h → 0 + ,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 earned by a no-regret algorithm for the fair bilateral trade problem. 33 The stochastic caseWe 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: we can devise two different distributions whose maximum expected fair gain from trade is achieved in disjoint regions-so that posting a price that is in the good region for one distribution leads to an instantaneous regret bounded away from zero for the other distribution-but the learner cannot distinguish which is the underlying distribution generating the valuations, given that these distributions are designed so that the (push-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 a joint distribution under which, for an i.i. ) ). Suppose that the sequence of valuations (S t , B t ) t∈N is drawn i.i.d. from µ or ν. If the underlying distribution is µ, the optimal point is 5/16 and, for all p ∈ [1/2, 1] and t ∈ N, the differenceE[FGFT(5/16, S t , B t )] -E[FGFT(p, S t , B t )] is at least 1 3 ( 5 16 -3 16 ) = 1 24 .Analogously, if the underlying distribution is ν, the optimal point is 11/16 and, for all p ∈ [0,1/2] and t ∈ N, E[FGFT(11/16, S t , B t )] -E[FGFT(p, S t , B t )] ≥ 124 . This means that the only way for the learner not to suffer Ω(T ) regret is to distinguish whether the underlying distribution is µ or ν. But a direct verification shows that the distribution of the feedback is the same for every p ∈ [0, 1], regardless of whether the underlying distribution is µ or ν. Hence, the learner has no means to distinguish between µ and ν and must suffer Ω(T ) regret. Indeed, let N T be the random number of times the platform posts a price P t in [0, 1 2 ]. Then N T has the same distribution under µ and ν.If E µ [N T ] = E ν [N T ] ≥ T 2 , then the expected regret under ν is at least T 2 ⋅ 1 24 = T 48 . Conversely, If E µ [N T ] = E ν [N T ] ≤ T2 , then the expected regret under µ is at least T 48 . Remark 1. Note that Theorem 1 together with Yao's Minimax Theorem immediately imply that the adversarial fair bilateral trade problem-where the goal is to obtain sublinear worst-case expected regret against the best fixed-price when the sequence of seller/buyer valuations (S t , B t ) t∈N 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 ∈ N, the two valuations S t and B t are independent of each other.To this end, we first present the Convolution Lemma (Lemma 1), which provides a way to avoid the aforementioned lack of observability when the traders' valuations are independent of each other. This lemma plays for FGFT a role analogous to the one played by the Decomposition Lemma [9, Lemma 1] for GFT. Lemma 1 (The Convolution Lemma). For all s, b, p ∈ [0, 1],EQUATIONIn particular, if S and B are [0, 1]-valued independent random variables, for each p ∈ [0, 1],EQUATIONProof.If FGFT(p, s, b) = (b -p) + , note that (b -p) + = ∫ 1 0 I{u ≤ (b -p) + } du = ∫ 1 0 I{u ≤ (p -s) + }I{u ≤ (b -p) + } du = ∫ 1 0 I{u ≤ p -s}I{u ≤ b -p} du = ∫ 1 0 I{s ≤ p -u}I{p + u ≤ b} du .The same conclusion holds with an analogous argument if FGFT(p, s, b) = (ps) + . 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 a careful pointwise estimation of both cumulative distributions, but just of (2), which involves certain products of their translates. The crucial observation-from which Lemma 1 takes its name-is that (2) is the (incomplete) convolution of 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 at different time steps. This observation suggests that we can approximate the continuous (incomplete) convolution by a discrete (incomplete) convolution involving the noisy observations we collect at different time steps, e.g., by posting prices on a uniform grid. These ideas are exploited in the design of Algorithm 1 and in the proof of its regret guarantees.Algorithm 1: Convolution Pricing (Stochastic Setting)Input: K ∈ N; Initialization: for each t ∈ Z, set V t ∶= W t ∶= 0; for time t = 1, 2, . . . , K do Post price P t ∶= t K and set V t ∶= I{S t ≤ P t }, W t ∶= I{P t ≤ B t }; Let I ∈ argmax i∈[K] 1 K ∑ K-1 k=0 V i-k W i+k ; for t = K + 1, K + 2, . .Post price P t ∶= I/K; Theorem 2. In the stochastic case, under the additional assumption that for each t ∈ N the seller's valuation S t is independent of the buyer's valuation B t , by setting K ∶= ⌊T 2/3 ⌋, the regret suffered by Algorithm 1 is Õ(T 2/3 ).Proof. For each k ∈ [K], define q k ∶= k K . Note that for each t ∈ N the function p ↦ E[FGFT(p, S t , B t )] is 1-Lipschitz being the expectation of (random) 1-Lipschitz functions. Hence, if for each p ∈ [0, 1] we denote by k ⋆ (p) the index of the closest point to p in the grid {q 1 , . . . , q K }, we have, for each t ∈ N, that,EQUATIONLet F be the common cumulative function of the random variables in the process (S t ) t∈N and let G be the common co-cumulative function of the random variables in the process (B t ) t∈N , i.e., for each t ∈ N and each p ∈ R, define F (p) ∶= P[S ≤ p] and G(p) ∶= P[p ≤ B]. Note that F (u) = 0 for each u ≤ 0, that G(u) = 0 for each u ≥ 1, and that for each p ∈ [0, 1], the function u ↦ F (p -u)G(p + u)is non-increasing, being the product of two non-increasing functions. Hence, for each t ∈ N and eachk ∈ [K],by Lemma 1, we can sandwich the quantityEQUATIONNow, by the independence assumption,1 K K-1 ∑ i=0 F (q k-i ) G (q k+i ) = 1 K K-1 ∑ i=0 E[V k-i ]E[W k+i ] = E [ 1 K K-1 ∑ i=0 V k-i W k+i ]and, by noting that for each k ∈[K] we have that 1 K ∑ K-1 i=0 V k-i W k+iis the empirical mean of K {0, 1}-valued independent random variables, by Hoeffding's inequality and a union bound, we have that, for any ε > 0,P [ max k∈[K] | 1 K K-1 ∑ i=0 V k-i W k+i - 1 K K-1 ∑ i=0 F (q k-i ) G (q k+i )| ≥ ε] ≤ 2K exp(-2ε 2 K) .In particular, if we set ε T ∶= √ ln(2T )2⌊T 2/3 ⌋ , recalling that K = ⌊T 2/3 ⌋, and defining the (good) eventEQUATIONNow, let p ⋆ ∈ argmax p∈[0,1] E[FGFT(p, S t , B t )] (whose definition is independent of t, given that the process (S t , B t ) t∈N is i.i.d.) and, recalling the definition of I from Algorithm 1, note, for each t > K, thatE[FGFT(P t , S t , B t )] = E[FGFT(q I , S t , B t )] = E[E[FGFT(q I , S t , B t ) | I]] = E[[E[FGFT(q k , S t , B t )]] k=I ] ≥ E [[ 1 K K-1 ∑ i=0 F (q k-i ) G (q k+i ) - 1 K ] k=I ] = E [ 1 K K-1 ∑ i=0 F (q I-i ) G (q I+i )] - 1 K ≥ E [I E T ⋅ 1 K K-1 ∑ i=0 V I-i W I+i ] -ε T - 1 K ≥ E [I E T ⋅ 1 K K-1 ∑ i=0 V k ⋆ (p ⋆ )-i W k ⋆ (p ⋆ )+i ] -ε T - 1 K ≥ E [ 1 K K-1 ∑ i=0 V k ⋆ (p ⋆ )-i W k ⋆ (p ⋆ )+i ] -P[E c T ] -ε T - 1 K = 1 K K-1 ∑ i=0 F (q k ⋆ (p ⋆ )-i ) G (q k ⋆ (p ⋆ )+i ) -P[E c T ] -ε T - 1 K ≥ E[FGFT(p ⋆ , S t , B t )] -P[E c T ] -ε T - 2 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 E T , the third inequality from the definition of I, and the last inequality from the sandwich inequalities in (4) and inequality (3). Putting everything together, we can upper bound the regret as followsR T ≤ K + T ∑ t=K+1 E[FGFT(p ⋆ , S t , B t ) -FGFT(P t , S t , B t )] ≤ K + T ∑ t=K+1 (P[E c T ] + ε T + 2 K ) . Recalling that K = ⌊T 2/3 ⌋, ε T = √ ln(2T )2⌊T 2/3 ⌋ , and (5), we obtain the conclusion.We now prove that the strategy employed by Algorithm 1 is worst-case optimal, up to logarithmic factors. At a high level, the reason why the T 2/3 rate is optimal is that the fair bilateral trade problem contains instances that closely resemble the revealing action problem in partial monitoring [15] , where, in order to distinguish which one of two actions is optimal, we have to play for a 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 A due to space constraints.Theorem 3. There exists a constant c > 0 such that the following holds. For every algorithm for the fair bilateral trade problem and for every time horizon T ∈ N, there exists an i.i.d. sequence (S t , B t ) t∈[T ] of pairs of sellers' and buyers' valuations such that, for each t ∈ [T ], S t is independent of B t , and the algorithm suffers regret of at least cT 2/3 on that sequence.Proof sketch.For each ε ∈ [-1, 1], consider the distribution µ ε ∶= 1+ε 2 δ 0 + 1-ε 2 δ 1/4 where δ a is the Dirac measure centered at a point a ∈ R. For each ε ∈ [-1, 1], let (S ε t ) t∈N be an i.i.d. sequence whose distribution is µ ε . For each t ∈ N, let B t = 1. Then, for each ε ∈ [-1, 1], the sequence (S ε t , B t ) t∈N is i.i.d. and for each t ∈ N the valuation S ε t is (obviously) independent of the (deterministic) valuation B t . 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 ε t , B t ) t∈N is 1/2 while if ε < 0 the optimal price is 5/8. If ε > 0 and we post prices greater or equal than 9/16 we suffer instantaneous regret of at least order of |ε|, while if ε < 0 and we post prices less or equal than 9/16 we suffer instantaneous regret of at least order of |ε|. Hence, to avoid suffering Ω(|ε|T ) regret we need to distinguish the sign of ε.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 0 and 1/4. In this case, the feedback we see is equivalent to seeing a Bernoulli of parameter 1+ε 2 , and hence, due to information-theoretic arguments, we need Ω(1/ε 2 ) to distinguish the sign of ε. Now, every price in the region [0, 1/4] suffers instantaneous regret of order Ω(1). Hence, any algorithm has to suffer Ω ( 1ε 2 + |ε|T ) regret, which is Ω(T 2/3 ) when |ε| = Θ(T -1/3 ).Remark 2. The T 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.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: See Section 6.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a 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 on 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not 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 to address problems of privacy and fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer Justification: There are no experiments in the paper.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 it into the paper). 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 circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
the deterministic case: 
 In this section, we study the deterministic case where there exist fixed but unknown constants s, b ∈ [0, 1] such that, for all time t ∈ N, S t = s and B t = b. In this case, we note that if b < s no trade can occur while, if b = s, even though a trade can occur for the posted price P t = 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.We begin by the following remark: in the standard bilateral trade setting where the reward function is the gain from trade p ↦ (bs)I{s ≤ p ≤ b}, we can devise an algorithm that achieves constant regret. In fact, the learner can post prices following a 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 as soon as a successful (dyadic) price p is proposed, i.e., a price p ∈ [s, b]. 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 n ⋅ 2 -n ≤ 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 learnability (and hence, in this sense, was harder) than the fair bilateral trade problem. Theorem 4. In the deterministic case, for any horizon T ≥ 17, any algorithm suffers a worst-case regret larger than or equal to 1 32 log 2 (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 a deterministic algorithm posts at most k prices in [0, 1 4 ], then there is an interval E k ⊂ [0, 1 4 ] of length Θ(2 -k ) such that, for each s, s ′ ∈ E k , 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 α. There exists k ⋆ ∈ {0, 1, . . . , T } such that, for all s ∈ E k ⋆ , the algorithm posts exactly k ⋆ prices in [0, 1 4 ]. A direct verification shows that, for any s ∈ E k ⋆ , the instantaneous regret paid for the time steps where P t ∈ [0, 1 4 ] is Ω(1). Therefore, the regret paid by the algorithm for playing k ⋆ times in [0, 1 4 ] is Ω(k ⋆ ). Moreover, let T be the set of time steps t ∈ [T ] where the algorithm posts prices P t ∈ ( 14 , 1]. Leveraging the fact that the algorithm posts the same prices for every s ∈ E k ⋆ , it can be proved that there exists an s ∈ E k ⋆ such that the average distance 1 |T | ∑ t∈T |P t -b+s 2 | of the points P t played at rounds t ∈ T from the maximizer b+s 2 of the FGFT is at least Ω(2 -k ⋆ ). Putting everything together, the worst-case regret of the algorithm is lower bounded byΩ(k ⋆ + (T -k ⋆ )2 -k ⋆ ), which is Ω(ln T ) regardless of the specific value of k ⋆ .A "double" binary search algorithm suffices to obtain a matching O(ln T ) regret rate. The idea of the algorithm is very simple. First, spend Θ(ln T ) rounds performing a 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 pseudocode of this algorithm in Appendix C (Algorithm 3). For a full proof of the following theorem, see Appendix C. Theorem 5. In the deterministic case, the (deterministic) regret suffered by Algorithm 3 is O(ln T ).Proof sketch. The idea is first to invest a budget of order ln T to locate the seller's valuation with error O(1/T ). Second, we proceed similarly to locate the buyer's valuation with error O(1/T ). Finally, this yields a O(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 ln T while the regret of the last phase is of order T ⋅ 1 T , and thus bounded. 
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 P t , the learner has access to both S t and B t . We show that the cost is two-fold: slower rates (both in the deterministic -Θ(ln T ) vs Θ(1)and stochastic case -Θ(T 2/3 ) vs Θ( √ T )) and the need for additional assumptions (independence of buyer and seller valuations in the stochastic case).For the full-feedback setting, we show that following the best empirical price leads to an algorithm (Algorithm 2) whose regret guarantees are optimal. We remark that Algorithm 2 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. 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 1, note that1 t ∑ t i=1 FGFT(p, S t , B t ) = ∫ 1 0 1 t ∑ t i=1 I{S i ≤ p -u}I{p + u ≤ B i } du =∶ Ĝt (p). Now, by the two-dimensional DKW inequality, it can be proved that the empirical estimates Ĝt (p) are uniformly ε-close (in p) to E[FGFT(p, S t+1 , B t+1 )] with probability 1 -O(e -Ω(ε 2 t) ). These probability estimates, together with the fact that the algorithm selects P t+1 by maximizing p ↦ Ĝt (p), translates to a O (1/ √ t + 1)-control over the expectation max 0≤p≤1 E[FGFT(p, S t+1 , B t+1 ) -FGFT(P t+1 , S t+1 , B t+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 7. There exists a constant c > 0 such that the following holds. For every algorithm for the fair bilateral trade problem with full feedback and for every time horizon T ∈ N, there exists an i.i.d. sequence (S t , B t ) t∈[T ] of pairs of sellers' and buyers' valuations such that, for each t ∈ [T ], S t is independent of B t , and the algorithm suffers regret at least c √ T on that sequence.Since the proof of this result follows along the same lines as the proof of Theorem 3 (whose full details can be found in Appendix A), we present only a proof sketch.Proof sketch. The hard instances are the same as those in the proof of Theorem 3 for the Ω(T 2/3 ) 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 Ω(|ε|T ) regret we need to distinguish the sign of ε. Now, given that full-feedback is available, the information we retrieve after each interaction is equivalent to observing a Bernoulli r.v. of parameter 1+ε 2 , regardless of the price we posted. Again, informationtheoretic arguments imply that we need Ω( 1 ε 2 ) rounds before being able to distinguish the sign of ε. During these rounds, the best we can do is to play (essentially) at random in the candidate set of optimal prices {1/2, 5/8}, suffering an expected instantaneous regret of Ω(|ε|). Overall, we suffer Ω (min {|ε| ⋅ Remark 3. In the same spirit of Remark 1, 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 Ω( √ T ). 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 [10, 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. 
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 is only tight up to logarithmic factors, so an improved analysis of the upper or lower bound is needed. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: We do not see any negative societal impacts of our theoretical work. In fact, its goal is to make a positive impact on trading mechanisms by improving the fairness of exchanges.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 societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: Being theoretical work, we are not releasing any data or models.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses for existing assets Question: 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?Answer: [NA] Justification: We do not use any assets.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: Fix any ε ∈ [0, 1/4] and letµ ±ε ∶= 1 ± ε 2 δ 0 + 1 ∓ ε 2 δ 1/4where δ a is the Dirac measure centered at a point a ∈ R. Noting that, for all p ∈ [0, 1],p ≤ 1 -p ⇐⇒ p ≤ 1 2 p - 1 4 ≤ 1 -p ⇐⇒ p ≤ 5 8and letting S ± be a random variable with distribution µ ± and B = 1, we have . At a high level: I sub is an informative, but Θ(1)-suboptimal region; in contrast, regions I + and I -are both uninformative, but, when the underlying distribution of the sellers' valuations is µ +ε (resp, µ -ε ) I + (resp, I -) contains the maximizer p ⋆ + = 1 2 (resp, p ⋆ -= 5 8 ) while all points is I -(resp., I + ) are Θ(ε)-suboptimal. More precisely:EQUATION• Since B = 1, the feedback I{p ≤ B} is immaterial.• The feedback I{S ± t ≤ p} observed by posting a price p ∈ I sub at a time t ∈ N is a Bernoulli random variable with parameter 1±ε 2 . Moreover, for all p ∈ I submax f + -f + (p) = f + ( 1 2 ) -f + (p) = 3 + ε 8 - 1 + ε 2 p ≥ 1 4 max f --f -(p) = f -( 5 8 ) -f -(p) = 3 8 - 1 -ε 2 p ≥ 1 4At a high level, posting a price p ∈ I sub reveals information about the underlying distribution of the sellers' valuations but at the cost of an instantaneous regret of at least 1/4.• The feedback I{S ± t ≤ p} observed by posting a price p ∈ I + at a time t ∈ N when the underlying sellers' distribution is µ ±ε is a constant random variable always equal to 1.Moreover, argmax f + = 1 2 ∈ I + , but, for all p ∈ I + , max f --f -(p) = { 3 8 -( 1-ε 8 + (p -1 4 )) ≥ ε 8 ≥ ε 16 if p ∈ [1/4, 1/2) 3 8 -(( 1-ε 8 + 1 4 ) -ε ( 1 2 -p)) ≥ ε 16 if p ∈ [1/2, 9/16)At a high level, posting a price p ∈ I + reveals no information about the underlying distribution of the sellers' valuations, the region I + contains the optimal price when the underlying distribution of the sellers' valuations is µ +ε , but posting in I + has an instantaneous regret of at least ε/16 when the underlying distribution of the sellers' valuations is µ -ε .• The feedback I{S ± t ≤ p} observed by posting a price p ∈ I -at a time t ∈ N when the underlying sellers' distribution is µ ±ε is a constant random variable always equal to 1. Moreover, argmax f -= 5 8 ∈ I -, but, for all p ∈ I -,max f + -f + (p) = { 1+ε 8 + 1 4 -(( 1+ε 8 + 1 4 ) + ε ( 1 2 -p)) ≥ ε 16 if p ∈ [9/16, 5/8) 1+ε 8 + 1 4 -(( 1+ε 8 + 1 4 -ε 8 ) + ( 5 8 -p)) ≥ ε 8 ≥ ε 16 if p ∈ [5/8, 1]At a high level, posting a price p ∈ I -reveals no information about the underlying distribution of the sellers' valuations, the region I -contains the optimal price when the underlying distribution of the sellers' valuations is µ -ε , but posting in I -has an instantaneous regret of at least ε/16 when the underlying distribution of the sellers' valuations is µ +ε .We will now show that these two "+" and "-" instances are no easier than two corresponding instances of a related partial monitoring game (for the reader unfamiliar with partial monitoring, see, e.g, [27, Chapter 27] ). Consider the following partial monitoring game, where, again ε ∈ [0, 1/4], the learner's action set is {1, 2, 3}, the environment's outcome set is {1, 2}, the reward (ρ) and feedback (φ) matrices are, respectively,ρ ∶= ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ 0 0 1/16 0 0 1/16 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ and φ ∶= ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ 1 0 0 0 0 0 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦and where the environment is constrained to draw outcomes i.i.d. from one of two distributions: the first of which has a probability 1 2 + ε 2 of drawing outcome 1, while the second has a smaller probability of 1 2 -ε 2 of drawing outcome 1. More precisely, letEQUATIONfor all t ∈ N. In the "+" (resp, a "-") scenario, at any time t, the environment plays outcome A + t (resp., A - t ). Therefore, in the "+" scenario, the learner's optimal action is action 2, and, for all t ∈ N, the instantaneous expected regrets paid by the learner for playing actionEQUATION). Similarly, in the "-" scenario, the learner's optimal action is action 3, and, for all t ∈ N, the instantaneous expected regrets paid by the learner for playing actionEQUATION). Finally, playing actions 2 or 3 reveals no feedback, while the feedback φ(1, A ± t ) that the learner observes after playing action 1 at time t ∈ N in scenario "±" is a Bernoulli random variable with parameter 1 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 P t that the algorithm would post at any time t ∈ N into the actionJ t = ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ 1 if P t ∈ I sub 2 if P t ∈ I + 3 if P t ∈ I -then feeding back to the algorithm the pair (φ(I t , A ± t ), 1). By construction, this is the same feedback (more precisely, it is a Bernoulli random variable drawn i.i.d. from the same distribution) that the algorithm would observe by playing P t in the original fair bilateral trade problem, and the expected regret of the partial monitoring game is less than or equal to that of the original fair bilateral trade problem. Therefore, by lower bounding the regret of the partial monitoring game, we a 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 T 2/3 /112 (see, e.g., [16, Theorem 5.1] , up to turning losses into rewards and rescaling them by multiplying by 1/16).Given that we are in a deterministic setting, without loss of generality we (can) restrict our analysis to deterministic algorithms. Let b = 1. We begin by proving the following property by induction on k = 0, 1, 2, . . .. t∈T P t - b 2 ) - s 2 | .Since the prices P 1 , . . . , P T chosen by the algorithm are the same for any s∈ E k ⋆ , then 1 |T | ∑ t∈T P t -b 2does not depend on s and thus we can move s in the segment of length 1 4 2 -k * , and find a value of sfor which |( 1 |T | ∑ t∈T P t -b 2 ) -s 2 | ≥ 1 16 2 -k * .Hence, for this s the cumulative regret of the steps in T is lower bounded by|T | ⋅ 1 16 2 -k * .In the end, the total cumulative regret is lower bounded byk * 8 + 1 16 (T -k * )2 -k * .If k * ≥ T 2 , we can lower bound the total cumulative regret by T 16 . Else, we can lower bound the total cumulative regret byk * 8 + 1 32 T 2 -k * . If 2 k * ≤ T log 2 (T )then the total cumulative regret is lower bounded by log 2 (T ) 32. Else, we have2 k * ≥ T log 2 (T ) ≥ √ T ,where in the last inequality we used T ≥ 17, and hencek * ≥ log 2 ( √ T ) = log 2 (T ) 2. In the end, the lower bound ismin { T 16 , log 2 (T ) 32 } = log 2 (T ) 32 .C Pseudocode of Double Binary Search Pricing and proof of Theorem 5The 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 E ∶= [c, d] with c < d, we define left(E) ∶= c, mid(E) ∶= c+d 2 and right(E) ∶= d.Algorithm 3: Double Binary Search Pricing -Deterministic setting Input: horizon T ∈ N;Initialization: Set E S ∶= E B ∶= [0, 1]. If 2⌈log 2 (T )⌉ + 1 ≤ T set N ∶= ⌈log 2 (T )⌉, else set N ∶= 0; for time t = 1, 2, . . . , N do Post price P t ∶= mid(E S ); if s ≤ P t then Set E S ∶= [left(E S ), mid(E S )]; else Set E S ∶= [mid(E S ), right(E S )]; for time t = N + 1, N + 2, . . . , 2N do Post price P t ∶= mid(E B ); if P t ≤ b then Set E B ∶= [mid(E B ), right(E B )]; else Set E B ∶= [left(E B ), mid(E B )]; for time t = 2N + 1, . .Post price P t ∶= mid(E S )+mid(E B );We now present the full proof of Theorem 5.Proof. If T < 2⌈log 2 (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 2⌈log 2 (T )⌉ + 1 ≤ T .The cumulative regret from time steps1 to 2N is bounded by 2N = 2⌈log 2 (T )⌉ because FGFT ∈ [0, 1].It is easy to see that the property that s ∈ E S is maintained from time steps 1 to N . At time N (after which E S is left unchanged), the length of E S is smaller than or equal to 2 -N ≤ 1 T . Similar properties hold for b and E B . Hence, at time steps 2N + 1, . . . , T , we have thatEQUATIONTherefore, the individual regret at each one of these time steps is bounded byEQUATIONEQUATION) If b -s ≤ 2 T this quantity is smaller than or equal to 1 T . If b -s > 2 T , then from (6), we have mid(E S ) + mid(E B ) 2 -s ≥ b -s 2 -| mid(E S ) + mid(E B ) 2 - s + b 2 | ≥ b -s 2 - 1 T . Similarly b - mid(E S ) + mid(E B ) 2 ≥ b -s 2 -| mid(E S ) + mid(E B ) 2 - s + b 2 | ≥ b -s 2 - 1 T .Hence, the quantity in 7 is smaller than or equal to 1 T , and consequently, the cumulative regret from steps 2N + 1 to T is smaller than or equal to T -2N T ≤ 1. Putting everything together, the cumulative regret from steps 1 to T is smaller than or equal to 1 + 2⌈log 2 (T )⌉.For notational convenience, let (S, B) be another pair of seller/buyer valuations, independent of the whole sequence (S t , B t ) t∈N , and sharing the same distribution of any element in this i.i.d. sequence. The proof shares ideas with the proof of [9, Theorem 1] . For each p ∈ [0, 1], notice that, as a consequence of Equation ( 1) in Lemma 1, we haveE[FGFT(p, S, B)] = ∫ 1 0 P[{S ≤ p -u} ∩ {p + u ≤ B}] du =∶ G(p) ,and, for each t ∈ N, also1 t t ∑ i=1 FGFT(p, S t , B t ) = ∫ 1 0 1 t t ∑ i=1 I{S i ≤ p -u}I{p + u ≤ B i } du =∶ Ĝt (p)We have, for any p ∈ [0, 1] and any t ∈ N,|G(p) -Ĝt (p)| = | ∫ 1 0 P[{S ≤ p -u} ∩ {-B ≤ -p -u}] du -∫ 1 0 1 t t ∑ i=1 I{S i ≤ p -u}I{-B i ≤ -p -u} du| ≤ sup x,y∈R |P[{S ≤ x} ∩ {-B ≤ y}] - 1 t t ∑ i=1 I{S i ≤ x, -B i ≤ y}| .Hence, we can apply the two-dimensional DKW inequality, see [9, Theorem 15, Appendix J], from which it follows that there are positive constants m 0 ≤ 1200, c 1 ≤ 13448 and c 2 ≥ 1/576 such that for all ε > 0, if t ≥ m 0 /ε 2 ,P[|G(p) -Ĝt (p)| ≥ ε] ≤ P [ sup x,y∈R |P[{S ≤ x} ∩ {-B ≤ y}] - 1 t t ∑ i=1 I{S i ≤ x, -B i ≤ y}| ≥ ε] ≤ c 1 e -c2tε 2 .Hence, for each t ∈ N, by Fubini's theorem, we have thatE ⎡ ⎢ ⎢ ⎢ ⎣ sup p∈[0,1] |G(p) -Ĝt (p)| ⎤ ⎥ ⎥ ⎥ ⎦ = ∫ ∞ 0 P ⎡ ⎢ ⎢ ⎢ ⎣ sup p∈[0,1] |G(p) -Ĝt (p)| ≥ ε ⎤ ⎥ ⎥ ⎥ ⎦ dε ≤ √ m 0 t + ∫ ∞ √ m 0 t c 1 exp(-c 2 tε 2 ) dε ≤ √ m 0 t + c 1 2 ∫ ∞ -∞ exp(-c 2 tε 2 ) dε = √ m 0 t + c 1 2 √ 2π √ 2c 2 t = ( √ m 0 + c 1 √ π 2 √ c 2 ) 1 √ t .Then, for any t ∈ N, we have, using the law of total expectation conditioned on (S i , B i ) i=1,...,t ,E[FGFT(p ⋆ , S t+1 , B t+1 )] -E[FGFT(P t+1 , S t+1 , B t+1 )] = G(p ⋆ ) -E[G(P t+1 )] = G(p ⋆ ) -E[ Ĝt (p ⋆ )] + E[ Ĝt (p ⋆ ) -Ĝt (P t+1 )] + E[ Ĝt (P t+1 ) -G(P t+1 )] ≤ G(p ⋆ ) -E[ Ĝt (p ⋆ )] + E[ Ĝt (P t+1 ) -G(P t+1 )] ≤ 2E ⎡ ⎢ ⎢ ⎢ ⎣ sup p∈[0,1] | Ĝ(p) -G(p)| ⎤ ⎥ ⎥ ⎥ ⎦ ≤ 2 ( √ m 0 + c 1 √ π 2 √ c 2 ) 1 √ t .Hence, for any T ≥ 2,R T ≤ 1 + 2 ( √ m 0 + c 1 √ π 2 √ c 2 ) T ∑ t=2 1 √ t -1 ≤ 1 + 4 ( √ m 0 + c 1 √ π 2 √ c 2 ) √ T -1 .NeurIPS Paper ChecklistIn fact, if a trade occurs, we only know that St ≤ Pt ≤ Bt, but this information alone allows us to compute neither min{St -Pt, Bt -Pt} nor Bt -St.A distribution is smooth whenever it admits a bounded density; see, e.g.,[21,11].The reader familiar with the notion of α-regret will note that this is equivalent to saying that any no-regret algorithm for the standard bilateral trade problem fails to be a no-α-regret algorithm for the fair bilateral trade problem, regardless of how large α is chosen. 


Decision: 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.

Reviews: review: paper_summary: paper_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. 

In 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.
strength_weakness: strength_weakness: 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).

The 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.
questions: questions: See weaknesses
limitations: limitations: Limitations are discussed.
paper_summary: paper_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.
The paper is comprehensive in studying both upper/lower bounds in various settings.
strength_weakness: strength_weakness: Technicality
- It is good to know that the ETC style of algorithm 1 works well, but I must admit that it is not particularly interesting.
- 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.


Minor comments
- 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. 
- 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.
- 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.
- L#80 does not seem necessary, or a footnote might suffice.
- 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.
- 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.
questions: 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.
- 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: limitations: Mentioned above.
paper_summary: paper_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.

The 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.
strength_weakness: strength_weakness: 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. 

While 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.
questions: 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?

What types of applications come to mind for the fair online bilateral trade problem?
limitations: limitations: The authors have adequately addressed the limitations.
paper_summary: paper_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)$. 

In 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.

The 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.
strength_weakness: strength_weakness: There are no major weaknesses.

As 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.
questions: questions: The problem of bilateral trade is closely related to that of dynamic pricing. Do you know any work studying fairness in that setting?

Although 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: limitations: The authors addressed adequately the limitations of their work.

Comments: title: Rebuttal acknowledgment
comment: Thank you to the authors for the detailed response. I have no additional questions.
Thanks the authors for the detailed response. I have no further question.
Although the techniques are not particularly interesting, I think the paper is worth being accepted as it introduces a novel problem that might interest the community in several directions.
I would like to thank the authors for their response, and have no further questions or comments at this time.
The authors have adequately answered my questions. 

Having read again the grading guidelines for Neurips, I believe that this paper will belong to the 50% of the top accepted papers, and is a "clear accept". I therefore raise my score to 8.