- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
this paper studies maximizing Gain from Trade (GFT) in (repeated) bilateral trade. In prior work, either fully adversarial or stochastic environment alone has been well understood.
The main contirbution of this paper is to propose a new and unified online learning algorithm that can handle both envs. This requires a new type of primal-dual-style alg. design.
Critical strengths
- in the well-established online bilateral trade setting, this paper gives an improved algorithm in the sense that it achieves the best of both worlds between sto. and adv. envs.
- the algorithm design is under primal-dual framework, which is of independent interest due to its broad use. In this particular problem, the proposed algorithm can bypass the standard Slater condition to a weaker one.
Critical weaknesses
- unfortunately, due to page limit, in the main body, the authors were not able to give discussion/future direction/limitation
Questions for authors
- could authors explain how the equations in lines 1319 - 1323 derived?
- can this new primal-dual design be potentially applied to other constrained online learning problem, such as the basic online OCO?
- why does the formulation in Eq. (2) make sense? I.e., why do not we care about how much the revenue is, as long as it's non-negative?
We thank the reviewer for the positive evaluation and for these questions.
The submitted Lemma 3 did not justify the signed comparator-revenue term in this display. We have corrected Lemma 3 and added its proof in the appendix. The corrected lemma gives ∑t∈T1E(p,q)∼π[GFTt(p,q)+Revt(p,q)]≤M∑t∈T1Revt(pt,qt)+2+MO(KT). Moving ∑t∈T1E(p,q)∼π[Revt(p,q)] to the right and subtracting the learner’s nonnegative GFT on T1 gives the displayed regret bound. At the chosen K, the additive error is absorbed into O(T3/4). Adding the Primal-Dual bound cancels the learner’s Rev-Max revenue and leaves −∑t=1TwtE(p,q)∼π[Revt(p,q)], where wt=1 on T1 and wt=λt on T2.
The design could extend to online convex optimization with a cumulative resource constraint if the learner can replenish the resource and bound the objective loss incurred while doing so. In bilateral trade, the corrected Lemma 3 supplies that bound by relating the comparator’s GFT plus its signed revenue to the revenue earned on replenishment rounds. Convexity alone does not imply such a bound. An extension would therefore require an analogous comparison for the actions and feedback available in the new problem.
Thank you for raising this point. We study a standard formulation in bilateral trade, in which the goal is to maximize gains from trade subject to budget balance. Revenue plays an important role because it can finance trades that generate surplus but require a subsidy. Giving additional weight to profit could favor policies that earn more revenue at the expense of gains from trade. Eq. (2) therefore requires nonnegative expected revenue over the horizon and compares feasible policies by their expected gains from trade.