Fair Online Bilateral Trade

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.

Strengths

This paper studies an interesting an well-motivated problem. The results provided highlight a very different behavior than in classical bilateral trade problems, which I find very interesting. The treatment of the subject is thorough: the authors explore various models, including two-bit and full feedback, as well as i.i.d. and deterministic valuations, and both independent and dependent valuations. For each case, they provide matching upper and lower bounds on the regret. They also comment on the adversarial case. The paper is also very clear and well-written. Each theorem is accompanied by easily understandable proof sketches, supplemented by rigorous proofs in the Appendix.

Weaknesses

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

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?

Rating

8

Confidence

4

Soundness

4

Presentation

4

Contribution

4

Limitations

The authors addressed adequately the limitations of their work.

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.

Strengths

The problem statement is interesting and the difference from prior work is clearly stated. The model is clean and easy to understand, and I appreciated the formal problem definition in lines 114 - 117. The paper provides comprehensive results (often both lower and upper bounds) for multiple reasonable assumptions, and gives intuition for where the difficulty comes from in each regime. The work seems relevant for NeurIPS. I found the paper to be very easy to follow. The assumptions are clearly stated in each section, and the presentation is generally well done. In particular, I liked how the theorem statements are rigorous and clear and that proof sketches are given when there is a lack of space for full proofs. The proofs are nicely written and correct as far as I checked. In particular, Lemma 1 (the Convolution Lemma) was clean and clever, and is made good use of throughout the rest of the paper (i.e. in the proofs of Theorems 2 and 6). I felt that the lower bound examples in section 2 and in the proof of Theorem 1 were also excellent at building intuition for the remainder of the paper, and interesting examples in and of themselves.

Weaknesses

The structure of section 1 made it a bit harder to follow than the rest of the paper. Personally, I would have found it helpful for section 1 to be split into multiple parts (such as intro/related work/our contributions) in order to be able to more easily pinpoint the main contributions. 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

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?

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

4

Limitations

The authors have adequately addressed the limitations.

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.

Strengths

- The problem setup is pretty interesting, with a good motivation to the practical scenario. - The paper is pretty comprehensive, and the paper well-written and easy to follow. - It is interesting that ETC style of algorithm is order-optimal.

Weaknesses

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

- 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

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Mentioned above.

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.

Strengths

The paper is well-structured and explores a research direction which could potentially be very interesting.

Weaknesses

Section 2 is clear but does not sufficiently explain the additional challenges that need to be addressed compared to the standard online bilateral trade framework by Cesa-Bianchi et al. (EC 21). 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

See weaknesses

Rating

6

Confidence

3

Soundness

4

Presentation

3

Contribution

2

Limitations

Limitations are discussed.

Rebuttal acknowledgment

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.