Fair Online Bilateral Trade

• Adding a summary table

Great idea! We are happy to do it.

• Fair dynamic pricing

The few existing works on fair dynamic pricing study notions of fairness that are orthogonal to what ours would be when translated to dynamic pricing. For example, see Xu et al., Doubly Fair Dynamic Pricing, and Maestre et al., Reinforcement Learning for Fair Dynamic Pricing. Note that in bilateral trade, since the platform is the learner, there is a symmetry between the buyer's and seller's utility, and thus, it is sensible that our fair gain from trade function strives to make their utilities as similar as possible. In contrast, in dynamic pricing, the seller is the learner, and hence there is an inherent asymmetry in how the learner will choose their objective. The seller might still have an incentive to reduce their margin to improve that of the buyer because this way, they could provide enough incentives for buyers to join and continue using the platform. For this reason, we think that a suitable alternative reward function in dynamic pricing should remain somewhat asymmetric and give more weight to the seller's margin. An example can be the minimum between the seller's profit and a factor of $w$ times the buyer's profit. A similar idea was also discussed in the answer to reviewer 89Fg, in the context of bilateral trade.

• One-bit feedback

We conjecture that the techniques in [8] can be tweaked to show that learning is impossible with 1-bit feedback, for reasons analogous to that in [8]: lack of observability. With only 1 bit of feedback, we conjecture it is possible to build two different instances that are undistinguishable from one another such that the optimal price in one instance is highly suboptimal in the other.

• Weighted fair gain from trade objective

A possible weighted generalization of the fair gain from trade could be

$WFGFT(p,s,b) = \min( w \cdot (p-s)^+$, $(b - p)^+ )$

for a fixed constant $w \ge 1$ and where we recall that $p$ is the posted price, $s$ is the seller valuation and $b$ is the buyer valuation. This would address the reviewer's question in the sense that here the buyer's utility (profit) is valued $w$ times that of the seller. For fixed $s <b$, the optimal price is $(w s + b) / (w+1)$, and this price gets "pulled" toward the seller side as $w$ increases, thus increasing the buyer's profit (since the buyer's profit is valued more).

Our regret upper bounds can be extended to this weighted fair gain from trade. This is straightforward in the deterministic setting, since we just need to locate the optimal price $(w s + b) / (w+1)$. We either see it immediately (in the full-feedback model) or, otherwise, we use a binary search.

In the stochastic case, the following extension of the convolution lemma can be shown to hold (recall that it is under independence of buyer and seller):

$\mathbb E [ WFGFT(p,S,B) ] = \int_0^1 \mathbb{P} [ S \le p - \frac{u}{w} ] \mathbb{P} [ u+p \le B ] du$

Hence the proofs (Theorems 2 and 6) can be extended with minor adjustments, yielding the same rates.

Analogous considerations hold for lower bounds, which can be easily adapted to obtain the same rates we obtained for $FGFT$.

• Applications of fair online bilateral trade

A natural application is online ride-sharing services like Uber and Lyft where fairness problems have been previously studied, although in different settings with metrics different from ours (see, e.g., Sühr et al. "Two-sided fairness for repeated matchings in two-sided markets: A case study of a ride-hailing platform", 2019).

• Weakness 1

We are not sure we understand what the reviewer meant here. We are happy to provide clarifications if the reviewer needs some.

• Valuations not in $[0,1]$

Extending beyond $[0,1]$ works as in the bandit literature: If $[0,1]$ is replaced by $[0,m]$ (for some $m$), the same results apply up to a multiplicative $m$; If the interval is unbounded, no meaningful results can be obtained, unless additional assumptions on the distributions are made (e.g., $\sigma$-sub-Gaussianity, with known $\sigma$).

• Why minimax?

Yao's minimax theorem immediately implies the result, but the reviewer is correct in stating that the result would have also followed by observing that a lower bound on the expected regret of the stochastic case implies a lower bound in the adversarial case because in-expectation lower bounds can be turned into worst-case lower bounds. We will mention this in the revised version.

• Kleinberg and Leighton (FOCS'03)

We agree that dynamic pricing is a sufficiently related setting to be mentioned in the related work section. The revised version will contain a paragraph about it.

• Experiments comparing against bandits

The comparison with bandit algorithms would not be fair given that bandit algorithms cannot run in the two-bit feedback setting (the two bits of feedback are not sufficient to reconstruct the realized reward of posted prices, see Lines 39-41). Moreover, from a practical point of view, the bandit version of our problem is not well-motivated, as it is hard to imagine that a learner would be able to observe the reward of a price without access to the valuations (which would lead back to the full-info case). If the reviewer agrees with us, we would prefer not to implement this change.

• One-shot version

To the best of our knowledge, we are the first to introduce this fair variant of the bilateral trade problem, which arose as a natural continuation of the recent stream of works on online learning in bilateral trade. We agree with the reviewer that studying the one-shot version would also be an interesting extension of our work.

• Does regularity help?

It does not, in fact, our current lower bound constructions could be modified by "smoothing" the Dirac masses into uniform distributions over squares, obtaining the same results. To give some intuition as to why this is the case, in bilateral trade problems, smoothness helps by making the objective (i.e., the expected reward) Lipschitz, which in turn reduces the continuum-arm problem to a finite-arm problem via discretization. In the fair bilateral trade problem, however, the objective is already $1$-Lipschitz with no further assumptions. What hinders learnability in our problem is a lack of observability, which is recovered by assuming independence of buyers and sellers. Although we don't have an explicit lower bound construction at hand for the monotone hazard rate, we believe that this assumption would also be insufficient to obtain learnability.

• Additional challenges here compared to Cesa-Bianchi et al., EC '21

A first high-level observation is that the pairs "assumption"/"regret rate" differ between our setting (Fair Bilateral Trade) and that of Cesa-Bianchi et al. [10] ("regular" Bilateral Trade), suggesting that different ideas will be needed to obtain optimal results for each pair. For example, while smoothness (bounded densities) was crucial in obtaining sublinear rates in [10], we had to understand that, in our work, it plays no role, and consequently discover new algorithmic and proof ideas. At a very high level, we share with [10] the same issue of having poor feedback, which is not even sufficient to reconstruct the reward at the price we post. In our case, however, the different form of the objective requires new procedures to recover usable information on the reward function, which is made possible by our new Convolution Lemma. Another difference is that, in [10], to maximize the realized gain from trade, it is sufficient to post a price $p\in[S,B]$, while, in our case, we have to address the more delicate task of locating the midpoint $p = (S+B)/2$. This is the reason why (even optimal) algorithms for bilateral trade can suffer linear regret in our setting (as we show in Section 2). Another technical subtlety that we had to tackle is that a direct application of the convolution lemma in the 2-bit feedback setting would yield a suboptimal upper bound of $T^{3/4}$. Instead, by carefully defining a data-gathering procedure such that each observation contributes to estimating the convolution of the cdfs at all points, we are able to obtain the optimal $T^{2/3}$ rate. We will better highlight these various challenges in the paper.

• Justification for focusing specifically on maximizing Fair GFT

We fully agree that developing a broader framework is an interesting goal to pursue. We suspect that obtaining estimators for a reasonably large class of objective functions in bilateral trade could be a challenging problem if one aims at capturing at least both the GFT and FGFT objectives. The main reason for this difficulty is that different objectives would likely require significantly different techniques due to the problem-specific quantities that the learner has to estimate. For example, the fair and regular gain from trade problems rely on different algorithms, estimation lemmas, proofs, and assumptions, as discussed above.

Our specific focus on the Fair Gain From Trade objective is motivated by the so-called egalitarian rule in social choice theory (sometimes also called the max-min rule or the Rawlsian rule), where one favors the alternative that maximizes the minimum utility of the involved parties to promote fairness. We will add a paragraph about this bullet point in the revised version.