An $\alpha$-regret analysis of Adversarial Bilateral Trade
Authors: Yossi Azar
Amos Fiat
Federico Fusco
Venue: NeurIPS 2022 Accept (2022)
Keywords: online learning
bilateral trade
pricing
partial feedback

Abstract: We study sequential bilateral trade where sellers and buyers valuations are completely arbitrary ({\sl i.e.}, determined by an adversary). Sellers and buyers are strategic agents with private valuations for the good and the goal is to design a mechanism that maximizes efficiency (or gain from trade) while being incentive compatible, individually rational and budget balanced. In this paper we consider gain from trade which is harder to approximate than social welfare.
We consider a variety of feedback scenarios and distinguish the cases where the mechanism posts one price and when it can post different prices for buyer and seller. We show several surprising results about the separation between the different scenarios. In particular we show that (a) it is impossible to achieve sublinear $\alpha$-regret for any $\alpha<2$, (b) but with full feedback sublinear $2$-regret is achievable (c) with a single price and partial feedback one cannot get sublinear $\alpha$ regret for any constant $\alpha$  (d) nevertheless, posting two prices even with one-bit feedback achieves sublinear $2$-regret, and (e) there is a provable separation in the $2$-regret bounds between full and partial feedback. 

An a-regret analysis of Adversarial Bilateral Trade
Yossi Azar
Amos Fiat Department Computer Science Tel Aviv University, Israel fiatêtau. ac.
Department of Computer Science Tel Aviv University, Israel azar@tauex. ac..ac.il
Federico Fusco
Department of Computer, Control and Management Engineering Sapienza Università di Roma, Italy fuscof@diag uniroma1.
Abstract
We study sequential bilateral trade where sellers and buyers valuations are com- pletely arbitrary (i.e., determined by an adversary). Sellers and buyers are strategic agents with private valuations for the good and the goal is to design mechanism that maximizes efficiency (or gain from trade) while being incentive compatible, individually rational and budget balanced. In this paper we consider gain from trade which is harder to approximate than social welfare.
We consider variety of feedback scenarios and distinguish the cases where the mechanism posts one price and when it can post different prices for buyer and seller. We show several surprising results about the separation between the differ- ent scenarios. In particular, we show that (a) it is impossible to achieve sublinear a-regret for any
2, (b) but with full feedback sublinear 2-regret is achievable (c) with single price and partial feedback one cannot get sublinear regret for any constant a (d) nevertheless, posting two prices even with one-bit feedback achieves sublinear 2-regret, and (e) there is provable separation in the 2-regret bounds between full and partial feedback.
Introduction
The bilateral trade problem arises when two rational agents, seller and buyer, wish to trade a good; they both hold private valuation for it, and their goal is to maximize their utility. The solution to the problem consists in designing a mechanism that intermediates between the two parties to make the trade happen. Ideally, the mechanism should maximize social welfare even though the agents act strategically (incentive compatibility) and should guarantee non-negative utility to the agents (individual rationality). Furthermore,
interested in mechanisms for bilateral trade that do not subsidize the agents (budget balance). Obvious mechanisms that satisfy incentive compatibility, individual rationality, and budget balanced, are posted price mechanisms. Two common metrics used to measure the efficiency of a mechanism: social welfare subsequent to trade and gain from trade (i.e., the increase social welfare). Consider mechanism that posts prices p (price for the seller) and (price for the buyer) to agents with valuations and 6, formally we have:
Social Welfare: SW (p. q, s) = s s) I(s < p <ps
Gain from trade: GFT 9, b) = s) I[s p 9
We use [[Q) for indicator variable that takes the value the predicated Q is true and zero otherwise.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

It is clear from these expressions that if we are interested in exact optimality then maximizing gain from trade is equivalent to maximizing social welfare. However, Myerson and Satterthwaite [1983] showed that there is no mechanism for bilateral trade that is simultaneously social welfare maxi- mizing (alternately, gain from trade maximizing), incentive compatible, individually rational, and budget balanced It follows that the best one can hope for is an incentive compatible, individually rational, and budget balanced mechanism that approximates the optimal social welfare. This creates an asymmetry between the two metrics: multiplicative approximation to the maximal gain from trade implies an approximation at least as good (2 c) to the maximal social welfare but not vice versa. Ergo, it is harder to approximate the gain from trade than to approximate social welfare. For example, consider an instance where the seller has valuation 0.99 and the buyer is willing to pay up to 1: irrespective of if a trade occurs not, 99% of the optimal social welfare is guaranteed. Le.., mechanism that posts a price of zero and generates no trade gets good approximation to the social welfare. Contrariwise, the gain from trade is non-zero only if the mechanism manages post prices in the narrow [0.99, 1] interval.
The vast body of work subsequent to Myerson and Satterthwaite [1983] primarily considers the Bayesian version of the problem, where agents' valuations are drawn from some distribution and the efficiency is evaluated in expectation with respect to the valuations' randomness. There are many incentive compatible mechanisms that give a constant approximation to the social welfare (in the Bayesian setting), e.g., see Blumrosen and Dobzinski [2014]. On the other hand, finding constant approximation to the gain from trade has been a long standing problem and only a very recent paper of Deng al. [2022] has given Bayesian incentive compatible mechanism for this problem. In this paper, we deal with the harder scenario where an adversary determines seller and buyer valuations (i.e., valuations are not drawn from some distribution). Ergo, positive results in the Bayesian setting are inapplicable in our setting.
et al. [2021a]. we consider the sequential adversarial bilateral trade problem, where at each time step 1, a new seller-buyer pair arrives. The seller has some private valuation 8t E [0, 1] representing the smallest price she is willing to accept; conversely, the buyer holds as private information by E [0. 1], i.e. the largest price she is willing to pay to get the good. Concurrently, the mechanism posts price Pr the seller and q: to the buyer. If they both accept (s; S Pt and qu S 6)), then the trade happens at those prices, otherwise the agents leave forever. By the requirement that the mechanism is budget balanced, the prices posted by the mechanism are such that pt S q-- At the end of each time step, the mechanism receives some feedback that depends on the outcome of the trade. Ideally, we would like have a strategy for the sequential bilateral trade problem whose average gain from trade converges to that of the best fixed posted price mechanism in hindsight. However, as Cesa-Bianchi al. [2021a] showed, this is hopeless task.
Following
Our goal this work is then to achieve mechanisms whose average performance converges to a constant factor of the best fixed posted price mechanism in hindsight. We would like to find the smallest a 2 1 such that the a-regret [Kakade et al., 2009] is sublinear in the time horizon T:
GFT(p.q.s;,b)) a.E.E. Σ GFT gt, Sc,
max P.I
If the goal is only to maximize gain from trade, there is never any sense in offering two different prices (to the seller and buyer). However, critically, offering two prices is provably helpful in the context of a learning algorithm.
To conclude the description of our learning framework, we specify the type of feedback received by the mechanism. We focus on the two extremes of the feedback spectrum. On the one hand, we study the full feedback model, where, after prices posted, the mechanism learns both seller and buyer valuations bt). On the other hand, we investigate a more realistic partial feedback model, the one-bis feedbuck, where the learner only discovers if trade took place or not. We also consider an intermediate (partial feedback) model, called the two-bit feedback model. In this model, the learner posts (one or two) prices, and learns if the buyer willing to trade and if the seller is willing trade, at these prices, Clearly, a trade actually occurs only if both are willing to trade. Note that these two models enforce the desirable property that buyers and sellers only communicate to the mechanism minimal amount of information useful for the trade, without disclosing their actual valuations.
2This impossibility result holds even when the (private) agents valuations are assumed to be drawn from some (public) random distributions and the incentive compatibility is only enforced in expectation.

---

Full Feedback
Two-bit feedback
One-bit feedback
Single price
O(VT)- Theorem 2
((7)- Theorem 4
Two prices
((VT)- Thhorrm 3
(2(T2/3) Theorem 6
O(T9/4)
Theorem 5
Table 1: Summary of 2-regret results in various settings.
1.1
Overview of our Results
We present our results for the adversarial sequential bilateral trade problem (see also Table 1).
We show that no learning algorithm can achieve sublinear a-regret for any a < (Theo- rem 1). This holds in the full feedback model (and thus for both partial feedback models).
We give learning algorithm with full feedback that achieves Ö( (() 2-regret² (Theorem 2) and show that no algorithm can improve upon this (Theorem 3).
We show that if limited to a single price, no learning algorithm achieves sublinear a-regret for any constant in either partial feedback model: one or two-bit feedback (Theorem 4). Given the negative results above, we show that allowing the learning algorithm to post two prices gives sublinear 2-regret even for one-bit feedback (Theorem 5). This means that our learning algorithm achieves, average, least half of the gain from trade of the best fixed price hindsight, using only one bit of feedback at each step!
We show a separation between partial versus full feedback by giving a ((T2/3) lower bound in the former model on the 2-regret for any learning algorithm (Theorem 6).
The gaps in Table I may appear misleading because upper bounds in weaker models apply in stronger models and lower bounds in stronger models apply weaker models. The only remaining open gap in our results is between the 2(T2/33 lower bound and the ((T3/4) upper bound that hold for two prices and partial feedback (either one or two-bit feedback). It is also worth noting that in our worst case model, two prices are required but one-bit suffices for sublinear 2-regret. This is different qualitative behavior than the one observed in the stochastic case (Cesa-Bianchi et al., 2021a], where it is enough to use one single price but the two-bit feedback is required to achieve sublinear (1- (1-)regret. One may wonder why two prices are helpful at all in our adversarial setting, given their suboptimality in maximizing the gain from trade. turns out that by randomizing over two prices it is possible to estimate the (non-stochastic) valuations of the agents.
1.2 Technical challenges
From experts to prices. As already observed in Cesa-Bianchi et al. [2021a]. the full feedback model nicely fits into the prediction with experts framework (Cesa-Bianchi and Lugosi, 2006]: there is clear mapping between expert and prices and the mechanism easily reconstruct the gain that each price/expert experiences using the feedback received. The main challenge here is given by the continuous nature of the possible prices, as the usual experts framework assumes a finite number of experts. There are workarounds that exploit some regularity of the gain function such as the Lipschitz property or convexity/concavity [see, e.g., 2016, Slivkins, 2019]. Unfortunately, gain from trade is not such a function. Moreover, in our adversarial setting, we cannot adopt the smoothing trick used in Cesa-Bianchi et al. [2021a], where they assume some regularity on the agents' distribution to argue that E [GFT(-)] becomes Lipschitz. Our main technical tool to address this issue is discretization claim that allows us to compare the performance of the best fixed price in [0, 1] with that of the best on a finite grid.
and Lugosi, 2006, Hazan,
A magic estimator. Consider any of the two partial feedback models; there at each time step & the learner only receives minimal information about what happened at time t: namely, one or two-bit versus the full knowledge of (-). Note that this type of feedback is strietly more difficult than the classic bandit feedback [Cesa-Bianchi and Lugosi, 2006], where the learner always observes at least the gain its action incurred. Our main technical tool to circumvent this issue is given by the design of a procedure that, posting two randomized prices, is able to estimate the GFT in a given price. This unbiased estimator then used in carefully designed block decomposition of the time horizon to achieve sublinear 2-regret in presence of this very poor feedback.
'The Ô hides poly- logarithii terms
3

---

Lower bounds. For our lower bounds we adopt two different strategies. In Theorems 1 and 4 we construct randomized instances where no algorithm can learn anything: the only prices the learner could use to discriminate between different instances are cautiously hidden, while all the other prices do not reveal any useful information, given the type of feedhack considered. The randomized in- stances used in Theorems 3 and 6 involve instead more structured approach; given the challenge posed by the contemporary handling of the multiplicative and additive part of the 2-regret. To this end, we carefully hide the optimal ex-post prices and make it hard for the learner to achieve small (I-)regret with respect to some "second best" prices. A crucial task we often face is to "hide" some small finite sets of critical prices from the learning algorithm. We employ two techniques to do so: random shifts (as in the proof of Theorem 4) and repeatedly dividing overlaps (Theorems I and 3).
1.3 Related work
The work most closely related to ours is Cesa-Bianchi et al. [2021a]. There, the authors study the same sequential bilateral trade problem as we do, with the objective of minimizing the (I-)regret with respect to the best fixed price. They focus on the (easier) stochastic model, where the adversary chooses a distribution over valuations and not a deterministic sequence like we do. A full charac- terization of the minimax regret regimes is offered, for the same type of feedback we consider (the one-bit feedback is only addressed in the extended version (Cesa-Bianchi et al., 2021b]*) and with various regularity assumptions on the underlying random distributions. Cesa-Bianchi al. [2021a] la] also provide the first result for the adversarial setting we consider, showing that no learning algo- rithm can achieve sublinear 1-regret. Regret minimization in the context of economics has been studied in many papers [e.g.. Morgenstern and Roughgarden, 2015, Cesa-Bianchi et al., 2015, Ho al., 2016, Daskalakis and Syrgkanis, 2016, Lykouris al., 2016]. In particular, Kleinberg and Leighton [2003] studied the one-sided pricing problem, proving a Ó(T2/3) upper bound on the re- gret in the adversarial setting and opening a fruitful line of research [Blum et al., 2004, Blum and Hartline, 2005, Bubeck et al., 2019]. The notion of a-regret has been formally introduced by Kakade et al. [2009] but was already present in Kalai and Vempala [2005]. It has then found applications in linear [Garber, 2021] and submodular optimization [Roughgarden and Wang, 2018], learning with sleeping actions [Emamjomeh--addeh et al., 2021]. combinatorial auctions (Roughgarden and Wang, 2019] and market design [Niazadeh et al., 2021]. We mention that our work fits in the line of research that studies online learning with feedback models different from full information and the bandit ones; our one and two-bit feedback models share similarities with the feedback graphs model (see e.g., Alon et al. [2017], van der Hoeven et al. [2021]. Esposito et al. [2022]) and the partial monitoring framework (see e.g., Bartók et al. (2014), Lattimore and Szepesvári [2019]).
While Myerson and Satterthwaite [1983] were the first to thoroughly investigate the bilateral trade problem in the Bayesian setting with their famous impossibility result, it was the seminal paper of Vickrey [ [Vickrey, 1961] that introduced the problem, proving that any mechanism that is welfare maximizing, individually rational, and incentive compatible may not be budget balanced. In the Bayesian setting, it was only very recently that Deng et al. [2022] gave the first (Bayesian) incen- tive compatible, individually rational, and budget balanced mechanism achieving a constant factor approximation of the optimal gain from trade. Prior to this paper, a posted price Oloo log 3) approx- imation bound was achieved by Baldiii-alddescii et al., 2017]. with being the probability that a trade happens (i.e., the value of the buyer is higher than the value of the seller). The literature also includes many individually rational, incentive compatible, and budget balanced mechanisms achiev- ing a constant factor approximation of the optimal social welfare. Blumrosen and Dobzinski [2014] proposed a simple posted price mechanism, the median mechanism, yielding a 2-approximation of the optimal social welfare; the same authors then implemented a randomized fixed price mechanism improving the approximation to e/(e-1) 1) [Blumrosen and Dobzinski, 2021]. Recently, Dütting et al. single sample from the seller distribution as price is enough to achieve a 2 approximation to the optimal social welfare. The class of fixed price mechanism is of particular interest it has been shown that all (dominant strategy) incentive compatible and individually rational mechanisms that enforce a stricter notion of budget balance, i.e., the so-called
[2021] showed that even posting
*Cesa- Bianchi et al. [2021b] use definition of gain from trade that slightly different than ours when the prices posted to seller and buyer differ. In practice, however, the two definitions are equivalent. In particular, all our lower bounds apply automatically to their definition, while the analyses of our learning algorithms carry over exactly the same also with their definition.

---

Learning Protocol of Sequential Bilateral Trade
for time t 1, ....... do
new seller/buyer pair arrives with (hidden) valuations (s,, b,) [0, 1]2
the learner posts prices Pt. 9t E [0,1]
the learner receives a (hidden) reward GFT.(Pt.g) qt) = GFT qt st, be) E [0.1]
feedback 2, is revealed
strong budget balance (where the mechanism is not allowed to subsidize extract revenue from the agents) are indeed fixed price [Hagerty and Rogerson, 1987, Maini-Baldeschi et al., 2016].
Preliminaries
The formal protocol for the sequential bilateral trade follows Cesa-Bianchi et al. [2021a]. At each time step f, new pair of seller and buyer arrives, each with private valuations 8, and by in [0, 1]; the learner posts two prices: Pt E [0, 1] to the seller and E [0. 1] to the buyer. A trade happens if and only if both agents agree trade, i.e, when 8t S Pt. and qt I by. Since we want our mechanism to enforce budget balance, the resulting increase social welfare, i.e., b 8t. The learner then observes some feedback 2, The gain from trade at time l depends on the valuations and by and on the price posted. To simplify the notation we introduce the following:
require that Pt S for all t. When a trade occurs, the learner is awarded
GFT, q) == GFT 9, 8t, b.) 1s S S 9 bx) (b. - -8)
When the two prices are equal, we omit one of the arguments simplify the notation.
Given any constant a 2 1, the a-regret of a learning algorithm A against sequence of valuations on time horizon T is defined follows
T
(A, =
mnxX Σ GF., - 7 (PG
p.
E=1
In the right side of the equation, the dependence on S is contained in the GFT,()). Note that the expectation the previous formula is with respect to the internal randomization of the learning algorithm: pt and qi are the (possibly random) prices posted by A.
The a-regret of learning algorithm A, without specifying the dependence of the sequence, is defined as its a-regret against the "worst" sequence of valuations: (AA) == sups (A, Stated differently, the performance of an algorithm measured against an oblivious adversary that generates the sequence of valuations ahead of time: the learner has to perform well on all possible sequences. this paper we study the minimax a-regret, R. that measures the performance of the best (learning) algorithm versus the optimal fixed price in hindsight, on the worst possible instance: RG: = inf (A4). The set of learning algorithms we consider depends on which of the various settings we are dealing with. In this paper we consider variety of such settings (i.e., how many prices are posted, what feedback is available, see below Sections 2.1 and 2.2).
2.1 Single Price vs. Two Prices Seller price and Buyer price
We consider two families of learning algorithms, differing in the nature of the probe they perform, corresponding to notions of what means be budget balanced:
Single price mechanisms. we want to enforce a stricter notion of budget balance, namely strong budget balance, the mechanism is neither allowed to subsidize nor extract revenue from the system. This is modeled by imposing = qt. for all t. If p = qe we use the notation GFT,(p)) to represent the gain from trade at time
Two price mechanisms. If we require that the mechanism enforces (weak) budget balance, it can post two different prices, Pt to the seller and d to the buyer, as long as Pt < qt- lee., we only require that the mechanism never subsidize trade, we do not require that the mechanism not make profit. In this setting
the notation GFT,(Pt, qt) represent the gain from trade at time t. Observation Note that the only reason to post two prices is to obtain information. For any pair of prices (p, q) with 9 posting any single price [p, guarantees no less gain from trade.
5

---

In particular, any budget balanced algorithm that knows the future and seeks to maximize gain from trade while repeatedly posting the same prices will never choose different prices.
Feedback models
We consider three types of feedback, presented here in increasing order of difficulty for the learner. (Note that full feedback "implies" two-bit feedback which turn implies one-bit feedback):
Full feedback. In the full feedback model, the learner receives both seller and buyer valuations, immediately after posting prices: formally, 2G (st, be). E.g., both seller and buyer send sealed bids that are opened immediately after the [one or two] price[s] are revealed. By Observation 1, in the full feedback model there no reason to post two prices, as all the relevant information revealed anyway.
Two-bit feedback. In two-bit feedback the algorithm observes separately if the two agents agree the given price, i.e., the feedback at time t is 2, = (Ifs, S Pt Pr].I(4. S b.)).
One-bit feedback The one-bit feedback is arguably the minimal feedback the learner could get: the only information revealed whether the trade occurred or not, i.e., 2t I( S Pt S q: S be).
Regret due to discretization
Our first theoretical result concerns the study of how discretization impacts the regret. In particular, we compare the performance of the best fixed price taken from the continuous set [0, 1] to that of the best fixed price chosen from some discrete grid Q [0, 1]. Optimizing over continuous set may seemingly be a problem because our object, gain from trade, is discontinuous (thus non- Lipschitz), non-convex and non-concave; such regularity conditions. What we show in the following Claim (whose proof is deferred to the Appendix together with all the other missing proofs) is that it is possible to compare the performance of the best continuous fixed price with twice that of the best fixed price on the grid.
cannot the "standard approach" that makes of
Claim 1 (Discretization error). Let Q {go = 0 < q1 S ..... I 4n = 1} be any finite grid of prices in [0, 1] and let 5(Q) be the largest difference between contiguous prices, i.e maxi=1,... 19: qi-1 1 then for any sequence (81,b1), b1), (sT, br) and any price we have
Σ GFT,()) 2
GFT,(g) (Q) T
QEQ
Let be any learning algorithm that posts prices (pt, (:), then the following inequality holds:
T
(A) I 2sup
max QEQ
GFT
(x(GFT ((()))
Before moving to the next section, we spend some words to compare our discretization result with the one in Cesa-Bianchi et al. [2021a] (Second decomposition Lemma). There the authors exploit stochastic nature of the valuations to argue that EE (G) Lipschitz, under some regularity assumptions on the random distributions. We study the adversarial model, thus we cannot use this "smoothing" procedure; this is why we lose an extra multiplicative factor of
3 Full Feedback
In this section, we study the full feedback model, where the learner receives as feedback both seller and buyer valuations after posting a single price (see Observation 1). The learner can thus evaluate GFT,(P) for all p [0, 1]. independently of the price posted. Even with this very rich feedback, we show that the impossibility result from Cesa-Bianchi et al. [2021a], i.e., no learning algorithm achieves sublinear regret (I-regret) in the sequential bilateral trade problem, can be extended to hold for a-regret for all a E 21.
Theorem 1 (Lower bound on (2 regrett,) In the full-feed model, for all e E (0, and horizons T, the minimax (2 E) -rerett satisfies R2r 2-- 2 LT..

---

To prove Theorem we use Yao's Minimax Theorem: randomized family of valuations sequences constructed, with the property that any deterministic learner would suffer, on average, linear regret against it. The detailed proof is deferred to the Appendix, but we sketch here the main ideas. Specifically, any valuations sequence from the randomized family consists of (sell, buy) prices that have the form (0, b,) or (s;; 1). for some carefully designed {s and (. These sequences are generated iteratively in a way such that all realized [sell, buy] segments overlap and the next segment is chosen at random among two disjoint options (0, 6;) or (st, 1). Since all realized [sell, buy] segments overlap, there is at least one price in the intersection of all intervals: this is the optimal fixed price in hindsight. Conversely, at each time step no learner post price that guarantees trade with probability greater than 1/2, thus yielding the lower bound.
Moving to positive results, there is clear connection between our problem in the full feedback and the prediction with experts framework (Cesa-Bianchi and Lugosi, 2006]. In particular, if we simplify the task of the learner to be competitive against the best price in finite grid, we can use classical results on prediction with experts as a black box. Combining this with our discretization result (Claim 1), we show an (vT)) upper bound on the 2-regret. The details are postponed to the Appendix.
Theorem 2 (Upper bound on 2-regret given full feedback). In the full-feedbate setting, there exists a learning ulgorithm whose 2-regret, for T large enough, respects Rig. (A) S 5 -og
We conclude the full feedback analysis with lower bound that shows that the previous result is tight up logarithmic factor: the minimax 2-regret of the full feedback problem is @(vT).
Theorem 3 (Lower bound on 2-regret given full feedback). In the feel-bee model, for all hori- zons T large enough, the minimax 2-regret satisfies R 1, VT.
The proof uses once again Yao's Theorem and consists in constructing a randomized family of sequences such that any deterministic learning algorithm suffers, in expectation, a (((T)) 2-regret. The detailed construction is deferred the Appendix and it involves the careful combination of two scaled copies of the hard sequences used in the proof of Theorem 1.
4 Partial Feedback
In this section, we study the partial feedback models where the learner receives very limited informa- tion on the realizations of the gain from trade. Specifically, one or two bits that describe the relative positions of the prices proposed to the agents and their valuations.
4.1 Lower bound a-regret posting single price given two-bit feedback
Consider a learner that is constrained to post one single price at every iteration; the same to both seller and buyer. For this class of algorithms we show very strong impossibility result, namely that for any constant a, there exists no algorithm achieving sublinear a-regret. We prove this in the two-bit feedback model and thus trivially holds also if given one-bit feedback. The core of the lower bound construction (details are postponed to the Appendix) resides in the possibility for the adversary to hide large interval between many shorter ones; a learner posting only one price will not be able to locate it using partial feedback (which consists in just counting the number of intervals on the left and on the right).
Theorem (Lower bound on a-regret posting single price, two-bit feedback), In the two-bit feed- back model where the learner is allowed to post one single price, for all horizons T E IN and any constant a > 1, the minimax a-regret satisfies Ra 2 123.. T.
4.2 Upper bound on the 2-regret, posting two prices and given one-bit feedback
The main result in this section is presented in Theorem 5: it is possible to achieve sublinear 2-regret with one-bit feedback (and by posting two prices). We find this to be the most surprising result in this paper. The crucial ingredient of our approach is an unbiased estimator, GFT, of the gain from trade that uses two prices and one single of feedhack. This seems quite remarkable. The gain from trade is discontinuous function composed by two different objects: the difference (6 (6-3) s) and
7

---

Estimation procedure of GFT using two prices and one-bit feedback
Input: price p
Toss a biased coin with head probability p if head then Draw U u.a.r. in [0. pl and set U, u p
else Draw V u.a.r. in [p. 1] and set p +- p. á + Post price to the seller and g to the buyer and observe the one-bit feedback Ifs < b} >. Unbiased estimator of GFT
Return: GFT(p) < {s S á I q - b}
the indicator variable 1(p E [s, b]}. Both these two objects are easy to estimate independently, but for the gain from trade need an estimator of their product. To estimate GFT(p) for any fixed price p. we construct an estimation procedure that considers both features at the same time: it tosses biased coin with head probability p; if head, it posts price p the buyer and price drawn u.a.r. in [0. p] to the seller; if tails, it posts price p to the seller and a price drawn u.a.r. in [p, 1] to the buyer. The formal procedure is described in the pseudocode, while the following lemma proves that this procedure yields an unbiased estimator of the gain from trade.
Lemma 1. Fix any agents' valuations 8, b E [0. 1]. For any price p E [0, 11, it holds that GFT(p) is an unbiased estimator of GFT(p): E GFT GFT(p), where the expectation is with respect to the randomness of the estimation procedure.
Proof. Note that is fixed and known to the learner, s and b are fixed but unknown and the learner has to estimate the fixed but unknown quantity GFT I(s S P S S b}- (be (62s) st) using only the two-bit feedback. To analyze the expected value of GFT(p) we define two random variables:
(p) = HegUSp5b), Xo(p) = [(SSSVV5),, where ~ Uni and V ~ Uni 1). p & [s, b). the two random variables attain value O with probability 1 (and are thus both unbiased estimators of GFT(p) in that case). Consider now p E [s, bj and compute their expectation:
E(x,(p)) = PP (S S S b) (s S U)-
p-8
p
= b-p
E [(6(p)) = P (s S p V < b) = P (V < b)
1-p
The estimator GF) works as follows: with probability p it posts prices (U, p). otherwise (p. V), then receives the one-bit feedback from the agents and returns it. Conditioning the result of the toss of the biased coin it is then easy to compute the expected value of GFT(p):
E GFT()) = p [x)())) + (1 - [X,()) = I(s s q b} (b- 8) GFT(p) L
This estimation procedure becomes a powerful tool to estimate the gain from trade that the learner would have extracted at time posting price p using randomization and one single bit of feedback. Note here that the possibility of posting two different prices is crucial: as we have argued in the pre- vious section, one single price is not able to do that, even for two-bit feedback. Given the estimator
GFT (actually, it consists of a family of estimators: one for each price p) we present our learning algorithm DECCCKK-DOOOOOTIOOOOO Similarly what is done in Chapter 4 of Nisan al. [2007], the learner divides the time horizon in S time blocks B, of equal length² and uses as subroutine some expert algorithm on a meta-instance that considers each time block as a time step and each price in a suitable grid Q as an action. In each block the learner posts the same price p- in all but
QQ] time steps, where it uses GFT estimate the total gain from trade obtained in B, by all prices in Q. The details of BLOCK-DECOME DECOMPOSITION are presented in the pseudocode, and its guarantees are detailed in the following Theorem, whose proof deferred to the Appendix.
Theorem 5 (Upper bound on 2-regret posting two prices, one-bit feedback). In the one-bit feedback model where the learner is allowed post two prices, the 2-regret of
(BD) is such that RZ (BD) 3/4 Vlog(T), (, for appropriate choices of the expert algoritim E, grid Q and number of blocks S.
For ease of exposition we assume that S divides T. This is without loss of generality in our case, as one can always add some dummy time steps for an additive regret of at most T/S.
8

---

DECCK-DECOMPOITION (BD)
1: Input: time horizon T, number of blocks S, grid Q and expert algorithm &
2: A - T/S.
Q
................................ 3: B, (T- L A}, for all 2.......
4: Initialize & with time horizon S and actions, one for each p: E Q
5: for each round 1, ........ do
6: Receive from & the price pr
7: Select uniformly at random injection h, Q B,
> We need A >> [Q]
8: for each round E B, do
9: if (p:) f for some price p; then
10:
Use the estimator GFT at time and call its output GFT,(p) else: Post price p- and ignore feedback 12: Feed to & the estimated gains (GFT,(P:)) (
11:
4.3
Lower bound on 2-regret, posting two prices and two-bit feedback
In this section, we complement the positive results for the single price and two-bit feedback setting with lower bound on the 2-regret achievable in the (easier) two-price and two-bit feedback setting. This lower bound strongly depends on powerful characterization result from the partial monitoring literature [Bartók et al., 2014] and consists in constructing a class of instances with the following structure that mimics "hard" partial monitoring game. The [0, 1] interval is divided into 4 disjoint regions, the first one composed to be the second best after p". The only way for the learner to actually discriminate between the two candidates and assess which is the actual second best is to post prices in the last, suboptimal region of the [0, 1] interval. The construction is such that there is a multiplicative factor 2 between the gain from trade of p" and that of the second best. For the learner it impossible to locate the single point p" (given the structure of the feedback), and its regret with respect to the second best prices is at least ((T2/3). The reader familiar with the learning literature would recognize the similarity of this structure to the classical revealing action problem [Cesa-Bianchi al., 2006].
single optimal price p", then two intervals that are candidates
The randomized family of instances that are hard to learn for any deterministic learner is easy to describe: the beginning. the adversary randomly and uniformly select one of the two following distributions over valuations (s, b) and then draws T i.idd samples from it:
(0, 2
with probability
+
(0, 2
with probability
(1: 1
with probability
(2:3)
with probability
( 3 with probability
(2)
2
with probability
(5, with probability
(H,1) with probability
+
We can compute the expected performance E [GFT(p)] of any price p against them (the first, re- spectively second, column corresponds to the first, respectively second, distribution)
+
if E [0, 4
if E (0, if E 1 3:2)
G
+
if 13:
5
if
1
if
if E (1
if E (2:
if E 13
if (3.1)
It is clear that the best price is 1,, which yields expected gain from trade that is approximately multiplicative factor larger than the one induced by the second best price, i.. p E [ }) or p E (1. 3 depending on the instance question. The two candidates to the second best price are an additive ((e) factor away while posting prices in [0, 1) 1 (2. 1] gives a constant loss. The crucial property is that the only way the learner can discriminate between the two instances is to post prices in the low gain region [0, 1)) (2 1). For example, posting a price of 3 the learner observes trade with probability exactly 2 in both the distributions, while posting 0 yields trade
with probability & + E in the first case while exactly in the second (thus allowing some learning

---

to happen). Moreover, the learner cannot take advantage of the possibility of posting more than one price: the only useful thing to learn is where the extra E probability is, and there no way of doing without suffering a constant instantaneous regret; not even with two-bits of feedback. We formalize these considerations the following lemma, whose proof is deferred to the Appendix.
Lemma 2. Consider the class of learning algorithms that can post two prices (both different from 1 1/2) and receive two-bit feedback. For any A in this class, there exists a sequence from the family we described such that the following bound on the regret holds. for some constant e. >> O:
T
max GFT(p) - EE Σ GFT.(P).
4)) 2 2T
To conclude our lower bound, we need to show how to hide to the learner the price 1/2 that is clearly optimal. It is sufficient to add a small, random, perturbation of the instance.
Theorem 6 (Lower bound regret for two prices and two-bit feedback). In the two-bit feedback model where the learner is allowed to post two prices, all horizons E N, the minimax 2-regret satisfies Ry 2 2T2 for some constant ē.
Proof. Let 5= > O be an arbitrarily small constant. We perturb each instance of the family we have constructed earlier in the following way: the adversary draws uniformly at random a shift x E [o, 5). then adds it to all valuations and finally it divides them all by + 5. The valuations are still in [0. 1] and the optimal price p" has now become 2(148) + I+8 the exact location of p" since it is impossible to locate a specific point in [0, 6] using two-bit feedback. Finally, the addition of new, independent, random noise does not make the learning of the second best price easier, i.e., the bound of Lemma 2 holds. Thus, for any learning algorithm A, we have:
x The learner has now no way of pinpointing
T
E [A) ZE
max pEJ0,11
GFT, - 2 max pdp
(P)
1=1
2. E
max
Σ GFT,(P)
Σ
GFT, GFT,(P)..)
pfP"
280(T) + 2/3 2 T. T2/3
5 Discussion, Extensions, and Open Problems
In this paper, we investigate the sequential bilateral trade problem with adversarial valuations. We study various feedback scenarios and consider the possibility of the mechanism to post one price vs. when it can post different prices for buyer and seller. We identify the exact threshold of a that allows sublinear a-regret. We show that with partial feedback it is impossible to achieve sublinear a-regret for any constant a with a single price while 2-regret is achievable with 2 prices. Finally, we show separation in the minimax 2-regret between full and partial feedback. Although in this paper only consider the gain from trade, our positive results trivially hold with respect to social welfare. Furthermore, by modifying our lower bound from Theorem it is possible to show that sublinear a-regret is not achievable for a < 2 with respect to social welfare. An obvious open problem, with respect to both gain from trade and to social welfare, consists in determining the exact regret term as a function of T. Clearly, there is a gap in our Table of results, and the exact term is yet unclear also for social welfare. We focus the sequential problem where at each step one buyer and one seller appear. It would be interesting to study the model where multiple buyers and multiple sellers arrive at each time step and sellers have values for their goods, buyers have values for the different goods.
Acknowledgments and Disclosure of Funding
Yossi Azar was supported in part by the Israel Science Foundation (grant No. 2304/20). Federico Fusco was supported by the ERC Advanced Grant 788893 AMDROMA Algorithmic and Mecha- nism Design Research in Online Markets and MIUR PRIN grant Algorithms, Games, and Digital Markets (ALGADIMAR)
10

---

References
Noga Alon, Nicolò Cesa-Bianchi, Claudio Gentile, Shie Mannor, Yishay Mansour, and Ohad Shamir. Nonstochastic multi-armed bandits with graph-structured feedback. SIAM J. Comput., 46(6); 1785-1826, 2017.
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta- algorithm and applications. Theory Comput., 8(1):121-14, 2012. 2012..
Gábor Bartók, Dean P. Foster, Dávid Pál, Alexander Rakhlin, and Csaba Szepesvári. Partial moni- toring classification, regret bounds, and algorithms. Math. Oper. Res., 39(4):667 2014.
Avrim Blum and Jason D. Hartline. Near-optimal online auctions. In SODA, pages 1156-1163. SIAM, 2005.
Avrim Blum, Vijay Kumar, Atri Rudra, and Felix Wu. Online learning in online auctions. Theoreti- cal Computer Science, 324(2-3):337116, 2004.
Liad Blumrosen and Shahar Dobzinski. Reallocation mechanisms. In EC, page 617. ACM, 2014.
Liad Blumrosen and Shahar Dobzinski. (almost) efficient mechanisms for bilateral trading. Games Econ. Behav., 130:369-383, 2021.
Sébastien Bubeck, Nikhil R. Devanur, Zhiyi Huang, and Rad Niazadeh. Multi-scale online learning: Theory and applications to online auctions and pricing. J. Mach. Learn. Res., 20:62:1-62:37,
2019.
Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge University Press, UK, 2006.
Nicolò Cesa-Bianchi, Gábor Lugosi, and Gilles Stoltz. Regret minimization under partial monitor- ing. Math. Oper. Res., 31(3):562-580, 2006.
Nicolò Cesa- Besa-Bianchi, Claudio Gentile, and Yishay Mansour. Regret minimization for reserve prices in second-price auctions. IEEE Trans. Inf. Theory, 61(1):549-564, 2015.
Nicolò Cesa-Bianchi, Tommaso R. Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. regret analysis of bilateral trade. In EC, pages 289- 399-309. ACM, 2021a.
Nicolò Cesa-Bianchi, Tommaso R. Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Bilateral trade: A regret minimization perspective. CoRR, 1b9721 2021b.
Riccardo Colini-Baldeschi, Bart de Keijzer, Stefano Leonardi, and Stefano Turchetta. Approxi- mately efficient double auctions with strong budget balance. In SODA, pages 1424-1443. SIAM, 2016.
Riccardo Colini-Baldeschi, Paul W. Goldberg, Bart de Keijzer, Stefano Leonardi, and Stefano Turchetta. Fixed price approximability of the optimal gain from trade. In WINE, volume 10660 of Lecture Notes in Computer Science, pages 146-160. Springer, 2017.
Constantinos Daskalakis and Vasilis Syrgkanis. Learning in auctions: Regret is hard, envy easy. In FOCS, pages 219-228. IEEE Computer Society, 2016.
Yuan Deng, Jieming Mao. Balasubramanian Sivan, and Kangning Wang. Approximately efficient bilateral trade. In STOC, pages 718-721. ACM, 2022.
Paul Dütting, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenhäuser. Efficient two-sided markets with limited information. In STOC, pages 1452-1444 1465, ACM, 2021.
Ehsan Fmaajjoee-ZZadeh, Chen- Yu Wei, Haipeng Luo, and David Kempe. Adversarial online learning with changing action sets: Efficient algorithms with approximate regret bounds. In ALT, volume 132 of Proceedings of Machine Learning Research, pages 599-618. PMLR, 2021.
Emmanuel Esposito. Federico Fusco, Dirk van der Hoeven, and Nicolò Cesa-Bianchi. Learning on the edge: Online learning with stochastic feedback graphs. To appear NeurIPS, Preprint on the arXiv abs/2210.04229, 2022.
11

---

Dan Garber. Efficient online linear optimization with approximation algorithms. Math. Oper. Res., 46(1):204-225) 2021.
Kathleen Hagerty and William P Rogerson. Robust trading mechanisms. Journal of Economic Theory, 42(1):94-107, 1987.
Elad Hazan. Introduction to online convex optimization. Found. Trends Optim,, 2(3-4):15-325,, 2016.
Chien-Ju Ho, Aleksandrs Slivkins, and Jennifer Wortman Vaughan. Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated principal-agent problems. J. Artif. Intell. Res., 55:317-359, 2016.
Sham M. Kakade, Adam Tauman Kalai, and Katrina Ligett. Playing games with approximation algorithms. SIAM Comput.. 39(3):1088-1106 2009.
Adam Tauman Kalai and Santosh S. Vempala. Efficient algorithms for online decision problems. Comput. Syst. Sci., 71(3):291-377, 2005.
Robert D. Kleinberg and Frank Thomson Leighton. The value of knowing demand curve: Bounds on regret for online posted-price auctions. FOCS, pages 594-605 IEEE Computer Society, 2003.
Tor Lattimore and Csaba Szepesvári. Cleaning up the neighborhood: A full classification for ad- versarial partial monitoring. In ALT, volume 98 of Proceedings of Machine Learning Research, pages 529-556. PMLR, 2019.
Thodoris Lykouris, Vasilis Syrgkanis, and Éva Tardos. Learning and efficiency in games with dy- namic population. In SODA, pages 120-129. SIAM, 2016.
Jamie Morgenstern and Tim Roughgarden. On the pscudo-dimension of nearly optimal auctions. In NIPS, pages 136-144, 2015.
Roger B Myerson and Mark A Satterthwaite. Efficient mechanisms for bilateral trading. Journal of economic theory, 2922)266--21, 1983.
Rad Niazadeh, Negin Golrezaei, Joshua R. Wang, Fransisca Susan, and Ashwinkumar Badanidiyuru. Online learning via offline greedy algorithms: Applications in market design and optimization. In EC, pages 737-738. ACM, 2021.
Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay V. Vazirani, editors. Algorithmic Game Theory. Cambridge University Press, 2007.
José Luis Palacios. On the simple symmetric random walk and its maximal function. The American Statistician, 62(2):33--44) 2008
Tim Roughgarden and Joshua R. Wang. An optimal learning algorithm for online unconstrained submodular maximization. In COLT, volume 75 of Proceedings of Machine Learning Research, pages 1307-1325. PMLR, 2018.
Tim Roughgarden and Joshua Wang. Minimizing regret with multiple reserves. ACM Trans. Economics and Comput., 1031:17:1117:18, 2019.
Aleksandrs Slivkins. Introduction multi-armed bandits. Found. Trends Mach. Learn., 12(1-2): 1-286, 2019.
Dirk van der Hoeven, Federico Fusco, and Nicolò Cesa-Bianchi. Beyond bandit feedback in online multiclass classification. In NeurIPS, pages 13280-13291, 2021.
William Vickrey. Counterspcculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1):8-37, 1961.
Andrew Chi-Chil Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity (ex- tended abstract). FOCS, pages 222-227. IEEE Computer Society, 1977.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] All the claims are supported by formal statements and proofs either in the main body appendix
(b) Did you describe the limitations of your work? [Yes] For each result we state the conditions under which it holds.
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work primarily theoretical and we do not foresee any potential negative societal impacts of our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] All the results are supported by formal proofs, either in the main body or in the appendix
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/eurating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "x27Fdi1tA1p", "reviewer": "Reviewer_5g6N", "summary": "This paper studies the sequential adversarial bilateral trade problem under various feedback models: 1) full feedback 2) one-price 1 bit feedback 3) two-price 2 bit feedback 4) two-price 1 bit feedback. This paper provides a regret lower bound of 2-approximation for the full feedback model. Additionally, they give a learning algorithm that achieves $\\tilde{O}(\\sqrt{T}) 2$ regret in this setting. Then, for the partial feedback model with 1 or 2-bit feedback, the authors shows that no learning algorithm can achieve sublinear regret for constant $\\alpha$. Moreover, the paper provides a separation result between partial feedback and full feedback. For all the above results, the benchmark solution is the best fixed price in hindsight. ", "questions": "1. Is there any \\emph{existing} regret lower bound on adversarial bilateral trade similar to the settings of this paper? \n\n2. Does the gain from trade results of this paper implies improvement for the social welfare benchmark?\n\n3. Is the two-price setting realizable?\n\n4. What did the paper mean by sublinear $\\alpha$-regret when $\\alpha > 1$. Conventionally, sublinear regret means the total regret is sublinear in total time horizon $T$, hence algorithm with sublinear regret can be viewed as near-optimal. \n", "limitations": "If the paper could explain how the \"gain from trade\" benchmark outperforms the standard social welfare benchmark, that would be great.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. Section 1.2 introduces in detail the technical challenges of this paper, as well as related literature. \n\n2. This paper provides intensive theoretical analysis on the proposed algorithm in various settings.\n\n3. This paper provides a regret lower bound on full feedback model. \n\nWeakness:\n1. Some of the notations used in this paper are not standard, e.g., sublinear $\\alpha$-regret. \n\n2. The result comparison table (Table 1) is informal. The paper should specify which is the lower bound for the specific setting, and which is the performance of the proposed algorithm, by adding more descriptions to the table. \n\n3. The review find it hard to follows some proof intuitions, even with figures (Figure 1 and Figure 2)\n\n4. This paper doesn't have runtime analysis or experiments. \n\nMinor Comments:\n1. [line 86] the full feedback model achieves $\\tilde{O}(\\sqrt{T}) 2$-regret. What does it mean?\n\n2. [line 288] broken link \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "jKARc-3-TW", "reviewer": "Reviewer_wuuk", "summary": "This paper studies the problem optimizing gains from trade when a buyer with value b and seller with cost s arrive online. The process sets a single price p = q or two prices p and q, a trade happens if s <= p <= q <= b. The gain from trade is (b-s). Gain from trade is harder objective to optimize as the value is zero if no trade happens. \n\nThe authors consider online pricing with the goal of minimizing regret compared to the optimal gains from trade in hindsight. In this model 1-regret is not possible, so authors consider 2-regret where the optimal hindsight gains from trade - 2 x achieved gains from trade is sub-linear in the number of steps T. \n\nThey consider three different models on what information is available: Full feedback where the planner learns (s, b), 2 bit feedback where the planner learns if (s < p) and (q < b) and 1 bit feedback where the planner learns if the trade happened or not. The authors provide variety of lower bounds on the regret-approximation and regret as a function of T and provide close/matching upper bounds. \n\nIn particular the authors show.\n* a lower bound of 2 for the regret approximation in full feedback model\n* A matching upper and lower bound of O(\\sqrt(T)) for the regret in the full feedback model. \n* A lower bound of O(T) for regret with two bit feedback and single price. \n* A lower bound of O(T^{2/3})  with two prices and two bit feedback. \n* Upper bound of O(T^{3/4}) with two prices and 1 bit feedback. ", "questions": "* Please clarify the details for the result in Section 4.2.", "limitations": "Authors note some of the gaps in their results. There are no societal impact implications to note. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The results in this paper are comprehensive and the questions studied seem interesting.  \n\nThe results are non-trivial. The upper bound in the full information model comes from multiplicative weights. For the two lower bound the authors provide specific constructions that have high gains from trade in hindsight but the gains from trade of any pricing algorithm are much lower. The lower bound constructions for the two bid feedback models are much more involved. The upper bound for two bit feedback model is also involved. \n\nA big weakness is in the presentation of the paper. A lot of the details in the main body are difficult to follow without consulting the appendix. The appendix itself has also becomes difficult to follow due to having to refer back to the main paper. Perhaps the authors could find a better way to split the content. As an example, the lower bound constructions in Figure 1 and Figure 2 made no sense without the verbal description. \n\nAnother concern is about the correctness of some of the results. The more involved results in the paper are also hard to follow. In particular, Section 4.2 does not make complete sense even after putting it together with the appendix. \nThe estimator \\hat{GFT} is defined without a subscript but is later used with a variety of subscripts. The subscript h^{-1}(p) seems like a typo and should be h(p). The subscript \\tau refers to a batch of requests. It's not clear what is going on here. \nI am also not sure how \\hat(GFT)(p_i) is evaluated when the model only allows posting one pair of prices. Please clarify in the block decomposition algorithm, what price is posted in step 10. It will be important for authors to clarify this and assure that their result is indeed correct. \n\nI also found some typos in the lower bound result for the two bit feedback model and haven't checked the correctness of the rest of the result as it is fairly complex. Please consider including a statement of Theorem 4 from Bartok et al. for completeness.\n\nOther typos:\nPage 17, line 629: define N_{\\Delta}\nPage 17, line 632: Claim only holds for integer \\alpha. But the extension to other values in between follows.\nPage 18, line 649: Clarify what q is. \nPage 19, line 692: \nWhy is E[GFT(p)] for p in [0, 1/3] not 1/8? And the next line not 1/8 + 1/24?\n\nUpdate after rebuttal: \nThe authors response about the GFT estimator’s definition makes sense to me and I no longer think that the approach us fundamentally wrong. I will look at the proof some more. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VXW7l3vatZ", "reviewer": "Reviewer_VWf6", "summary": "This paper studies a sequential bilateral trade problem, where one seller and one buyer arrive at every round. The seller and the buyer both have a private valuation of the item that are adversarial. The learning algorithm posts one or two prices for the seller/buyer and aims to minimize the alpha-regret of the trade over T rounds (alpha-regret is due to the hardness result shown by prior work). \n\nThe paper considered different types of feedbacks including the full feedback (seller and buyer's values are revealed); the one-bit feedback (only the trade happened or not is revealed), and the two-bit feedback (whether the seller or the buyer accepts the price). The paper also studied these feedbacks with different strategy of the learner --posting one price or two prices.\n\nThe main results include a hardness result which shows that no algorithm can achieve sublinear alpha-regret when alpha<2. Then, with alpha=2, the authors provide sublinear regret algorithms with two-price strategy, one-price strategy under different types of feedbacks. When the feedback is incomplete (one-bit or two-bit), two-price algorithms are needed in order to achieve a sublinear regret rate.", "questions": "(please see the above weakness section too)\n- about the gaps in the current results: under the two-bit feedback system can the two-price algorithm achieve T^{2/3} regret upper bound, for example by an explore-then-commit type strategy with the discretization? \n- Is it necessary for the Block-Decomposition algorithm to know T, can one apply the doubling trick and make it independent of T?\n- the paper proposed the estimation procedure to estimate the price unbiasedly -- would it be useful to apply an upper/lower confidence bound for the prices over the rounds (or reasons that was not needed/used) ?  ", "limitations": "Yes (work is mainly theoretical)", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n- the paper is well-written and I appreciate that the authors provided a detailed review on the prior works, and how the setup and techniques in this work are different from those.\n- I found the technical part of the paper to be interesting, including the estimation procedure using two prices and the lower bound example 's construction. \n\nWeaknesses:\n- the upper bound results were a bit less exciting-- after doing the discretization, one can then use the prediction with experts framework on a grid of prices. \n- the results in table 1 contains a few gaps, in particular the study under the one-bit feedback seems to be quite incomplete and many questions remain open. e.g. what is the best possible regret a one-price strategy can achieve with one-bit feedback? what about the two-price strategy?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QlGd6HLFa_B", "reviewer": "Reviewer_cUb6", "summary": "This paper studies online bilateral trade in the adversarial setting. Previously, there had been some work on online bilateral trade but in the stochastic setting. The authors prove a number of results. First, note that one cannot hope to have an online algorithm that is able to compete with the optimal GFT (this is a result due to Cesa-Bianchi et al.).They further strengthen this to show that one cannot obtain any approximation ratio better than 1/2 even with full feedback, even in the adversarial setting.\n\nOn the upper bound side, the authors show that sqrt(T log T) 2-regret is possible when full feedback is available.\n\nThey also consider different feedback models. In the one-bit feedback model, one is allowed to post a single price and observes only the event of whether or not a trade occurs. In the two-bit feedback model, one sees two events: the event that the buyer is willing to trade and the event that the seller is willing to trade. They also consider two ways of “pricing”. The first is to use a single price and the second is to use two prices.\n\nOn the upper bound side, they show that in the one-bit feedback model, can obtain 2-regret of T^{3/4} by using two prices. If one uses only a single price then one has 2-regret at least T. They also show T^{2/3} 2-regret with two prices in the two-bit feedback model.", "questions": "- Mention in abstract that only a single seller and single buyer is considered.\n- Line 288, missing reference\n- Out of curiosity, I wonder if the authors consider multiple buyers and/or multiple sellers at all?\n- Line 50, it mentions that Deng et al give a BIC mechanism for approximating the first-best GFT. This is slightly inaccurate in that they analyzed a known mechanism. For example, the mechanism was also discussed in \"Approximating Gains from Trade in Two-sided Markets\nvia Simple Mechanisms\" by Brustle, Cai, Wu, and Zhao.", "limitations": "Limitations discussions looks good. They filled out the checklist.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths.**\n- I think the problem is very nice and I think the authors prove a number of very nice results. The techniques are very nice (Lemma 1 is a very neat trick). I think this paper is a pretty solid contribution.\n\n**Weaknesses.**\n- None", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DgvhMjDgdJG", "reviewer": "Reviewer_4zj6", "summary": "The paper studies sequential bilateral trade where sellers and buyers valuations are adversarially chosen. The paper considers two types of posted price mechanisms: (1) mechanisms that post a single price and (2) mechanisms that post different prices for buyer and seller. In addition, three types of feedback are considered: full observation of the seller’s and the buyer’s valuations, observing whether the trade happens, and observing whether the seller and the buyer are willing to trade respectively. The paper proves both lower bounds and upper bounds of the regret when the performance is measured by gain from trade. It first gives a strong impossibility result that no mechanism can achieve sublinear a-regret for any a<2, so 2-regret is the best we can hope for. Second, with full feedback sublinear 2-regret is proved to be achievable. Third, for partial feedback, they show a contrast between single-price mechanisms and two-price mechanisms: with a single price, one cannot get sublinear a-regret for any constant a; but posting two prices even with one-bit feedback achieves sublinear 2-regret. Finally, they prove that there is a separation in the 2-regret bounds between full and partial feedback.", "questions": "I have no questions. ", "limitations": "Yes.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper studies an important problem and proves strong results. The fact that setting two prices can drastically improve the performance in the sequential setting is fascinating to me. I find no reason to reject the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept