- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper studies repeated trading between a single seller and multiple buyers under i.i.d. valuations. In a second-price auction with asymmetric feedback, buyers' bids exceeding the reserve price are observable, whereas the seller only provides an accept/reject response. The proposed algorithms leverage GFT decomposition, adaptive price grids, and bandit learning to optimize cumulative GFT under budget constraints. The paper reports a regret of for a WBB algorithm compared to the SBB benchmark, and for a GBB algorithm relative to a fixed-price benchmark with nonnegative expected revenue. The GBB result assumes either independence between seller and buyer valuations or a bounded joint density.
Critical strengths
-
The asymmetric feedback highlights the significant disparity in information available to buyers and the seller. This setting naturally facilitates the exploration of how richer buyer feedback influences learning under budget constraints.
-
The adaptive grid leverages observed buyer valuations to tackle discontinuities in GFT. This approach links the enhanced feedback to a specific challenge in learning over continuous pricing.
-
Dividing GFT into two components aligns effectively with the available feedback: one component is estimated via randomized exploration, while the other is derived from observed bids and seller responses. This segmentation provides a clear framework for algorithm design.
-
For a fixed seller price, using one reserve price also yields feedback for higher reserve prices. The constrained bandit formulation makes this structure explicit and offers an interesting direction for sharing information across price pairs.
Critical weaknesses
The authors should address the following concerns:
-
It seems that the cost condition before Algorithm 3 and the proof use opposite directions. The proof assumes that an infeasible succeeding arm implies an infeasible preceding arm. Consider one line with and . This satisfies the stated condition, but Algorithm 3 removes the optimal feasible arm , then the infeasible arm , and keeps playing . The resulting regret contradicts Theorem 2.
-
Lemmas 2–3 leave the choice of optimal price pair unspecified. The proof of Lemma 3 also assumes that zero trading probability remains zero after rounding up. With deterministic and , is an optimal feasible pair with no trade. Rounding it to gives GFT and revenue . These violate both bounds for fixed and sufficiently large .
-
In Lemma 7, the proof drops and then claims revenue of at least from the condition \max(q,w)-2^{-(j-1)}\le s\le\max(q,w)-2^{-j}. This condition only guarantees that the seller accepts the offer. If , no buyer meets the reserve price and revenue is zero. The claimed revenue comparison may not follow.
-
The budget proof in Appendix G uses the wrong sign for . The definition of gives . The proof also treats as a lower bound on , which is false when the cumulative cost is negative and . These steps do not establish the claimed budget guarantee.
-
The formula for the second-highest bid excludes all bids equal to the highest bid. Let , true valuations be , and ties favor buyer 1. By reporting , buyer 1 still wins but pays instead of . The buyer gains by misreporting, so the stated payment rule may be not DSIC.
-
SBB implies only when trade occurs. If no buyer meets the reserve price, any seller quote gives zero revenue, and different quotes can still give different feedback if seller responses are observed. Thus, zero revenue alone does not establish the claimed pricing restriction. Also, for , Algorithm 2 uses , , and in its three phases. All satisfy SBB, contrary to the claim that WBB is necessary for learning.
-
Algorithm 3 initializes all UCBs to zero, but Equation (1) is undefined when .
-
This paper is missing an experimental chapter.
Questions for authors
Please see the weakness.
2 comments
I appreciate the authors’ detailed response and their efforts to address the concerns raised in my review. The proposed corrections address my main mathematical concerns. My remaining reservations concern the strength and scope of the revised contribution. First, withdrawing the claim that relaxing SBB to WBB is necessary narrows the budget-balance aspect of the original optimality claim. Second, the auxiliary constrained-bandit result provides guarantees without a Slater condition, but these guarantees are established for multi-line feedback graphs satisfying the specified feasibility-monotonicity condition. I view this as a useful but specialized methodological contribution. Moreover, empirical comparisons under comparable feedback and budget constraints would further help assess practical performance relative to relevant baselines. The absence of such evidence limits my assessment of the methods’ practical benefits. Taking into account the revised contribution, and the available evidence on practical performance, I prefer to maintain my original overall score.
We thank the reviewer for carefully reading the paper and identifying these errors and omissions. We apologize for the lack of precision. Below, we provide the corrections and explain how they address the concerns while preserving the stated guarantees. We hope these clarifications address the reviewer’s concerns and we welcome any further questions.
The condition before Algorithm 3 contains a reversed implication; the proof uses the intended condition: c(ai,k)>0⟹c(ai,j)>0,j<k. For fixed seller price p, revenue is nondecreasing in q for q<p, and nonnegative for q≥p. This supplies the required implication for the shifted costs.
We omitted a convention: when the optimal GFT is zero, choose (p∗,q∗)=(0,1), which belongs to the grid and requires no rounding. Otherwise, the optimal pair has positive trading probability. Under independence, feasibility then implies $p^*\le \mathbb E[\max(q^*,w)\mid v\ge q^*] \le \mathbb E[v\mid v\ge q^*],$ which supplies the inequalities needed for the seller-rounding arguments. We will state this convention explicitly and replace the incorrect zero-probability argument. We will make this convention explicit and remove the incorrect zero-probability assertion.
The indicator I(v≥q) should remain throughout the dyadic decomposition. Together with the stated interval condition, it guarantees trade and revenue 2−j. Restoring the indicator establishes the intended comparison with unchanged constants.
You are correct about both algebraic errors. For N final-phase rounds, the corrected calculation is ∑tRev(pt,qt)=−(1+ζˉ)∑tc(pt,qt)−Nζˉ≥−(1+ζˉ)∑t[c(pt,qt)]+−Nζˉ. Theorem 2 directly bounds the positive-cost sum. Including exploration losses and concentration error therefore gives $\text{total revenue}\ge \beta-\widetilde O\left(T_0+\sqrt{KT}+T\bar\zeta\right).$ Choosing the constant in β=O(T2/3) sufficiently large yields the claimed budget guarantee.
Similarly to our response to reviewer tAVM, the second price auction is the standard bt=maxi∈[n]bt,i, and bt=maxi∈[n]\It∗bt,i, letting It∗=argmaxi∈[n]bt,i with fixed tie-breaking. This is the model that is used in the whole paper and the equation at line 150 is the typo. This model guarantees the DSIC property, and in the example above the buyer would pay 0.8 by falsely reporting value 0.8.
We will qualify the pricing identity as applying on trading outcomes. On no-trade outcomes, zero revenue does not determine the seller quote or its feedback. We also agree that Algorithm 2 is SBB when n=1 and guarantees WBB for general n. Our result establishes that WBB suffices for the stated regret guarantee. We will remove the claim that WBB is necessary for learning.
For unobserved arms, we initialize the confidence bounds using the known reward and cost ranges: rt(a)=−1, rt(a)=1, and ct(a)=−1. Equation (1) applies only when nt(a)>0. We will update Algorithm 3 accordingly.
We thank the Reviewer for raising this point. We chose to keep the paper theoretical because its contribution is to establish worst-case regret guarantees under budget balance over the whole class of valuation distributions covered by each theorem. Experiments would address a substantially different question about how the algorithms perform on particular market instances. That question is worthwhile in its own right, but it falls outside the scope of this work and worst case regret minimization.
This approach follows closely related work in online bilateral trade ([1],[2]) that characterizes learnability through regret bounds and impossibility results.
[1] Cesa-Bianchi, Nicolò, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. "Bilateral trade: A regret minimization perspective." Mathematics of Operations Research 49, no. 1 (2024): 171-203
[2] Bernasconi, Martino, Matteo Castiglioni, Andrea Celli, and Federico Fusco. "No-regret learning in bilateral trade via global budget balance." In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pp. 247-258. 2024