acceptodds
Under review as a conference paper at ICLR 2027

Online Two-Sided Markets: Many Buyers Enhance Learning

Abstract

We study repeated trading problems involving a *single seller* and *multiple buyers*. We generalize classical bilateral trade mechanisms by introducing a second-price auction among the buyers before proposing a price to the seller. This setup increases competition and reveals more information about buyers' valuations, resulting in an *informational advantage* over bilateral trade. However, the seller still makes a binary accept/reject decision, resulting in *asymmetric feedback*. We show that this richer feedback model enables us to overcome known lower bounds in the single-buyer case. Specifically, we achieve a regret bound against the best *strong budget-balanced* mechanism, without assumptions on value distributions. Furthermore, when either *(i)* the valuations of the buyers and the seller are independent or *(ii)* they are sampled from bounded density distributions, we achieve a regret bound against *global budget-balanced* mechanisms. Along the way, we also derive new techniques for constrained bandits with feedback graphs.

Primary area:
learning theory
Keywords:
Online Learning, Bilateral Trade, Two-sided markets

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_tCb9OpenReview ↗
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 O~(T2/3)\widetilde{O}(T^{2/3}) 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
  1. 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.

  2. 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.

  3. 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.

  4. 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:

  1. 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 r=(0,1,−1)r=(0,1,-1) and c=(−1,0.1,0)c=(-1,0.1,0). This satisfies the stated condition, but Algorithm 3 removes the optimal feasible arm a1a_1, then the infeasible arm a2a_2, and keeps playing a3a_3. The resulting T−O(log⁡T)T-O(\log T) regret contradicts Theorem 2.

  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 s=0.5,v=0.1,w=0s=0.5,v=0.1,w=0 and K=100K=100, (0.495,0)(0.495,0) is an optimal feasible pair with no trade. Rounding it to (0.5,0)(0.5,0) gives GFT −0.4-0.4 and revenue −0.5-0.5. These violate both bounds for fixed δ\delta and sufficiently large T0T_0.

  3. In Lemma 7, the proof drops 1{v≥q}\mathbf1\{v\ge q\} and then claims revenue of at least 2−j2^{-j} 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 v<qv<q, no buyer meets the reserve price and revenue is zero. The claimed revenue comparison may not follow.

  4. The budget proof in Appendix G uses the wrong sign for ζˉ\bar\zeta. The definition of cc gives Rev⁡=−(1+ζˉ)c−ζˉ\operatorname{Rev}=-(1+\bar\zeta)c-\bar\zeta. The proof also treats −2∑tc(at)-2\sum_t c(a_t) as a lower bound on −(1+ζˉ)∑tc(at)-(1+\bar\zeta)\sum_t c(a_t), which is false when the cumulative cost is negative and ζˉ<1\bar\zeta<1. These steps do not establish the claimed budget guarantee.

  5. The formula for the second-highest bid excludes all bids equal to the highest bid. Let q=s=0q=s=0, true valuations be (0.9,0.8,0.1)(0.9,0.8,0.1), and ties favor buyer 1. By reporting 0.80.8, buyer 1 still wins but pays 0.10.1 instead of 0.80.8. The buyer gains by misreporting, so the stated payment rule may be not DSIC.

  6. SBB implies pt=max⁡(qt,wt)p_t=\max(q_t,w_t) 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 n=1,w=0n=1,w=0, Algorithm 2 uses (0,0)(0,0), (U,U)(U,U), and (q,q)(q,q) in its three phases. All satisfy SBB, contrary to the claim that WBB is necessary for learning.

  7. Algorithm 3 initializes all UCBs to zero, but Equation (1) is undefined when nt(a)=0n_t(a)=0.

  8. This paper is missing an experimental chapter.

Questions for authors

Please see the weakness.

2 comments

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.

1

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.c(a_{i,k})>0\implies c(a_{i,j})>0,\quad j<k. For fixed seller price pp, revenue is nondecreasing in qq for q<pq<p, and nonnegative for q≥pq\ge p. This supplies the required implication for the shifted costs.

2

We omitted a convention: when the optimal GFT is zero, choose (p∗,q∗)=(0,1)(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.

3

The indicator I(v≥q)\mathbb I(v\ge q) should remain throughout the dyadic decomposition. Together with the stated interval condition, it guarantees trade and revenue 2−j2^{-j}. Restoring the indicator establishes the intended comparison with unchanged constants.

4

You are correct about both algebraic errors. For NN final-phase rounds, the corrected calculation is ∑tRev(pt,qt)=−(1+ζˉ)∑tc(pt,qt)−Nζˉ≥−(1+ζˉ)∑t[c(pt,qt)]+−Nζˉ.\sum_t Rev(p_t,q_t)=-(1+\bar\zeta)\sum_t c(p_t,q_t)-N\bar\zeta\ge -(1+\bar\zeta)\sum_t[c(p_t,q_t)]_+ -N\bar\zeta. 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)\beta=\widetilde O(T^{2/3}) sufficiently large yields the claimed budget guarantee.

5

Similarly to our response to reviewer tAVM, the second price auction is the standard b‾t=max⁡i∈[n]bt,i\overline{b}_t=\max_{i\in [n]}b_{t,i}, and b‾t=max⁡i∈[n]\It∗bt,i\underline{b}_t= \max_{i\in [n]\backslash{I^*_t} }b_{t,i}, letting It∗=arg⁡max⁡i∈[n]bt,iI^*_t=\arg\max_{i\in [n]}b_{t,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.80.8 by falsely reporting value 0.80.8.

6

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=1n=1 and guarantees WBB for general nn. Our result establishes that WBB suffices for the stated regret guarantee. We will remove the claim that WBB is necessary for learning.

7

For unobserved arms, we initialize the confidence bounds using the known reward and cost ranges: r‾t(a)=−1\underline r_t(a)=-1, r‾t(a)=1\overline r_t(a)=1, and c‾t(a)=−1\underline c_t(a)=-1. Equation (1) applies only when nt(a)>0n_t(a)>0. We will update Algorithm 3 accordingly.

8

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

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.

Reviewer_MytGOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies online learning in two-sided markets with a single seller and multiple buyers. The authors consider a second-price auction among buyers, together with a seller's binary acceptance decision, resulting in an asymmetric feedback structure. By exploiting this richer feedback, the paper develops learning algorithms based on adaptive price discretization and bandit techniques. It establishes nearly tight regret bounds against the optimal strong budget-balanced (SBB) mechanism without additional distributional assumptions, and against the optimal global budget-balanced (GBB) fixed-price mechanism under independence or bounded-density assumptions.

Critical strengths

The paper establishes nearly tight regret bounds under different budget-balance requirements. In particular, achieving sublinear regret against the optimal SBB mechanism without additional distributional assumptions is an interesting result. The extension to the stronger GBB benchmark is also theoretically meaningful.

Critical weaknesses

The motivation for considering a single seller with multiple buyers under a second-price auction could be further strengthened. Although the paper discusses the benefits of buyer competition and the incentive properties of second-price auctions, it remains unclear why this particular market structure and auction mechanism are natural choices for the intended applications. In particular, the framework appears to be partly motivated by the richer valuation feedback provided by second-price auctions, which facilitates learning. More concrete application examples and a clearer justification of the modeling choices would strengthen the significance of the problem setting.

Questions for authors

1.Could the authors provide concrete real-world examples or supporting evidence from the literature to better motivate the single-seller, multiple-buyer setting and the choice of a second-price auction?

2.The analysis appears to rely on buyers truthfully reporting their valuations. While truthful bidding is weakly dominant in a standard second-price auction, how would the learning guarantees be affected by strategic misreporting or collusion among buyers? Investigating such strategic behaviors could also be an interesting direction for future research.

1 comment

We thank the reviewer for these helpful suggestions.

A concrete motivating example is an advertising opportunity supplied by one publisher and contested by multiple advertisers. Second-price auctions have historically been used in this setting, including Google’s advertising exchange before its transition to first-price auctions in 2019 (Google, 2019 [1]). Learning reserve prices in repeated second-price auctions also has an established literature (Cesa-Bianchi, Gentile, and Mansour, 2015 [2]). Our model abstracts this structure while incorporating the seller’s private valuation. The second-price rule provides a simple incentive-compatible way to allocate the item among competing buyers; its feedback is an additional learning benefit. We will strengthen this motivation in the introduction.

Our guarantees assume truthful, noncolluding participants. With fresh participants in each round, agents cannot benefit from influencing future prices, and truthful bidding is weakly dominant for the current auction. This supports truthful participation but does not guarantee robustness to arbitrary misreporting or collusion. Such behavior can invalidate the valuation feedback used by our analysis. We will clarify this limitation. Extending the guarantees to returning strategic participants and colluding buyers is an interesting direction for future work.

[1] https://blog.google/products/admanager/update-first-price-auctions-google-ad-manager/

[2] N. Cesa-Bianchi, C. Gentile and Y. Mansour, "Regret Minimization for Reserve Prices in Second-Price Auctions," in IEEE Transactions on Information Theory, vol. 61, no. 1, pp. 549-564, Jan. 2015, doi: 10.1109/TIT.2014.2365772.

Reviewer_tAVMOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies online two-sided markets involving a single seller and multiple buyers. The goal is to learn a pricing mechanism under an unknown valuation distribution, using only buyers’ bids above the reserve price and the seller’s accept/reject feedback, to maximize cumulative gains from trade subject to budget-balance constraints. Its core contribution is to exploit the informational advantage provided by a second-price auction through a decomposition of gains from trade, adaptive price discretization, and feedback sharing. Specifically, the authors design an algorithm that satisfies per-round weak budget balance and achieves O~(T2/3)\widetilde{O}(T^{2/3}) regret against the optimal strongly budget-balanced mechanism with a fixed reserve price, without additional structural assumptions on the valuation distribution. Furthermore, when the buyers’ valuation vector is independent of the seller’s valuation, or the joint distribution has a bounded density, the proposed algorithm achieves O~(T2/3)\widetilde{O}(T^{2/3}) regret against the optimal fixed-price pair with nonnegative expected revenue while satisfying global budget balance with high probability.

Critical strengths

The algorithm design makes effective use of asymmetric feedback. In particular, the adaptive price grid exploits buyer-side observations to handle discontinuities in gains from trade, enabling the SBB regret guarantee without assuming bounded densities for the valuation distributions.

Critical weaknesses

The paper contains issues with the formulation of mathematical definitions and unspecified boundary cases. See the Questions section for details.

Questions for authors
  1. In a second-price auction, the winner is the buyer with the highest bid, and the payment is determined by the second-highest bid. With two buyers who both bid 0.90.9, the highest and second-highest bids are both 0.90.9. However, this paper defines the second-highest valuation as bˉt=max⁡i∈[n]bt,i\bar b_t = \max_{i \in [n]} b_{t,i} and b‾t=max⁡i:bt,i≠bˉtbt,i\underline b_t = \max_{i: b_{t,i} \neq \bar b_t} b_{t,i}. This is not the standard second-highest order statistic. This discrepancy may invalidate the DSIC claim in the paper. Consider three buyers AA, BB, and CC, whose true valuations are vA=1v_A=1, vB=0.8v_B=0.8, and vC=0.9v_C=0.9, respectively, and let the reserve price be qt=0q_t=0. When all buyers bid truthfully, AA wins and CC receives zero utility. However, if CC raises their bid from 0.90.9 to 11 and is selected as the winner under the tie-breaking rule, the paper’s definition gives bˉt=1\bar b_t=1 and b‾t=0.8\underline b_t=0.8. Buyer CC therefore pays only 0.80.8 and obtains utility 0.9−0.8=0.1>00.9-0.8=0.1>0. This shows that a buyer can obtain higher utility by deviating from truthful bidding, violating DSIC. In contrast, under the standard second-price auction definition, the second-highest bid is 11, so CC pays 11 and does not benefit from this deviation. The authors should therefore clarify whether they intend to use the standard second-highest order statistic, revise the definition accordingly, and re-examine the DSIC property and subsequent theoretical analysis.

  2. When there is only one buyer in the market (n=1n=1), or when all buyers submit the same bid, such as bt=(0.9,0.9)\mathbf b_t=(0.9,0.9), the set of buyers satisfying bt,i≠bˉtb_{t,i}\neq\bar b_t is empty. Thus, b‾t\underline b_t is undefined as written. The authors should clarify how these cases are handled.

2 comments

We thank the reviewer for identifying this notation error and apologize for the ambiguity.

We intend the standard second-price auction. Let it\*i_t^\* be a highest bidder selected using fixed tie-breaking, and define b‾t=max⁡i∈[n]bt,i\overline b_t=\max_{i\in[n]}b_{t,i} and $\underline b_t= \max_{i\in[n]\setminus{i_t^*}}b_{t,i}$ for n≥2n\ge 2 and b‾t=0\underline b_t=0 for n=1n=1. Thus, tied highest bids are retained: for bids (0.9,0.9)(0.9,0.9), both order statistics equal 0.90.9. In the reviewer’s deviation example, buyer CC would pay 11 if selected and would not benefit.

We will correct the displayed definition at line 151 and explicitly state these conventions. The intended mechanism and subsequent analysis use this standard rule, under which truthful bidding is weakly dominant. We hope this clarification resolves the reviewer’s concerns.

Thank you for the clarification. Although the revised definition and the additional conventions have addressed the specific issues I raised, the inaccuracies of the original manuscript's basic mathematical definitions still raise some concerns about the paper’s overall rigor. After careful consideration of the contributions and current quality of the paper, I have decided to maintain the original rating.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.