Comparing Uniform Price and Discriminatory Multi-Unit Auctions through Regret Minimization

Thank you for the review.

Comparison with prior work

We begin by clarifying how our work differs from previous ones (Potfer et al., Branzei et al. and Galgana et al.).

Comparing auction formats

All these previous works focused primarily on developing learning algorithms for one auction format at a time and studied the case of adversarial opposing bids. This work studies and compares learning in both the auction formats and focuses on stochastic opposing bids. Galgana et al. provide some numerical experiments comparing both formats in how quickly the bids converge and regarding the equilibrium achieved, in the appendix without theoretical analysis.

Technical differences

We will make sure to better highlight the technical differences with prior work. Since we focus on stochastic bids, our algorithms are fundamentally different in the techniques they leverage. While other work relied on discretizing the bidding space $B$ (defined in line 109) and applying a randomized algorithm, our algorithm works directly on $B$ and does not need randomization. As you mentioned, we mainly rely on statistical CDF estimation techniques. Besides the fact that this approach is technically different, it allows for a simpler and more tractable analysis, which is the basis allowing us to compare both auction formats under a common framework.

Natarajan dimensions intuition

Regarding the Natarajan/multiclass classification, we believe a good intuition for its usefulness in our special case is the following: in multiclass classification, given a context, you want to evaluate the probabilities of the sample belonging to each available class; because the classes are mutually exclusive, the probabilities must sum to one. Furthermore, when observing the true class of one sample, the indicator function corresponding to the true class takes the value 1 and the others take the value 0. In our problem, a very similar structure appears when, given a bid profile $\mathbf{b}$, we make estimates of the probabilities of obtaining $1,2, ...$ or $K$ items. This is similar to the multiclass setting in the sense that both probabilities and indicator functions of the events must also sum up to 1 here. This is the property that we mention as "strong negative correlation" on line 174.

Line-by-line comments

• Line 15: You are right, adding a more recent reference will strengthen the argument. We will add the following reference : Khezr, Peyman, and Anne Cumpston. "A review of multiunit auctions with homogeneous goods." Journal of Economic Surveys 36.4 (2022): 1225-1247

• Line 61-71: This can indeed be unclear; we will ensure to mention $K$ is the number of items available at auction before using the notation.

• Line 99: We will note right away that items are indivisible and identical to ensure the setting is clear.

• Line 104: The $(\beta_k)_{k\in [K]}$ are indeed non-increasing (they belong to $B$, which is defined on line 109 as the non-increasing sequences of $[0,1]^K$). It is indeed also common to assume the marginal valuations $v_1,...,v_K$ are non-increasing. This question was also raised by another reviewer, we will make this more explicit in the final version.

• Line 119: We used the term "standard" instead of "efficient" or "welfare maximizing" as these two types of auctions have been studied and shown to be inefficient by De Keijzer, Bart, et al. and they are called "standard auction" in this work (cf [1] end of this response). We nevertheless acknowledge that the term "standard" might not be the most transparent and will prefer a descriptive approach explaining the rationale behind the allocation, highlighting the fact that it would be optimal if bidders were to bid truthfully (bidding $b_i=v_i$).

• Line 124-126: Your understanding is mostly correct. In the discriminatory auction, the price of the $k^{th}$ item allocated to the bidder is set as $b_k$. Be aware that the bid $b_k$ is not necessarily the bidder's marginal valuation $v_k$. Since these auction formats are non-truthful, it is not optimal to bid $b_i=v_i$.
  You are correct in your understanding that the $b_k$ for $k > x(\mathbf{b},\beta)$ do not change the bidder utility.

Remark 1

We understand the need for a more detailed argument. As it is not the main focus of the paper, and to adhere to space constraints, we did not provide too much detail. The main arguments to show the complexity of the maximization are the following :

• $\hat{u}^t (\mathbf{b})$ is written as a function of $\mathbf{b}$ and $\hat{F}_k^t$ (equations (13) and (14)) and it is separable into functions of neighbouring pairs of components of $\mathbf{b}$.
• Each of these functions is piecewise linear with pieces joining at the past observed $\beta_k^t$.

Given these two points, one can prove the complexity bounds by using Theorem 1 in Branzei et al., which shows that the maximization problem is equivalent to a shortest path problem in a Directed Acyclic Graph.

Section 5

This section indeed focuses on Bandit feedback. The main point of this section is the following: in general, we cannot say one auction or the other is easier to learn; yet if we restrict the possible distributions (or the valuation of the bidder), then some results showing that both auctions are not always equivalent can be obtained. This section focuses on showcasing some of these cases and providing the corresponding analysis.

Instance Dependent bounds

The strength of instance-dependent bounds is that they represent how the regret can be lower for certain instances. In short, they allow us to characterize what parameters make the learning problem easier or harder and how much our algorithms can leverage them. In our case, that can be having only unit-demand (or two-unit demand) or having an opposing bids distribution that is well-behaved. It is the focus of section 5 to understand what these parameters are for our auction settings and how they might differ depending on the auction format. We will make sure to more clearly explain why it is beyond worst case and highlight the interest of these bounds in the paper.

[1] De Keijzer, Bart, et al. "Inefficiency of standard multi-unit auctions." European Symposium on Algorithms. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013.

[2] Potfer, M., Baudry, D., Richard, H., Perchet, V., & Wan, C. (2024). Improved learning rates in multi-unit uniform price auctions. Advances in Neural Information Processing Systems, 37, 130237-130264.

[3] Brânzei, S., Derakhshan, M., Golrezaei, N., & Han, Y. (2023). Learning and collusion in multi-unit auctions. Advances in Neural Information Processing Systems, 36, 22191-22225.

[4] Galgana, R., & Golrezaei, N. (2025). Learning in repeated multiunit pay-as-bid auctions. Manufacturing & Service Operations Management, 27(1), 200-229.

Thank you for your response.

Thank you for the review.

Question

We characterize how the regret scales differently according to the number of positive valuations of the items (unit demand, two-unit demand, and more ). This is shown in Table 1 under the "worst case" column. While we did investigate further how specific parameters of the instance change the instance-dependent bound, our analysis only yielded conditions on the expected utility function. We were not able to derive explicit conditions on parameters of the instance (distribution, valuations, etc.).

Non-truthfullness

The two auction formats we consider are non-truthful. It is not clear to us how we could discuss further the non-truthful aspect of these auction formats, as the paper looks into how to learn online the best bids, which wouldn't be needed if the auction were truthful. We nevertheless included Lemma 7 in the Appendices, which describes how the uniform price auction is truthful for the first value/bid. We will consider making this aspect clearer in the main paper.

Single unit auction

Regarding the K=1 special case (for which our comparison reduces to a first-price versus second-price auction), it is indeed not addressed on its own. Nevertheless, it is a special case of the unit demand setting for which some results are mentioned (lines 285-288). Indeed, if K=1, then the bidder only has $v_1>0$

Opposing bids

You are right, $\beta^t_1, ..., \beta^t_K$ are indeed in non-increasing order. This is expressed in the paper by the fact that they belong to $B$, defined on lines 107-109 as the subset of $[0,1]^K$ composed of the non-increasing sequences. We note that this is somewhat implicit and will try to highlight it more explicitly.

Thank you for the review.

We take note that the exposition of the literature and of the contribution could be clearer and will improve the issues you raised. We first provide clarification regarding the issue raised in the summary and then answer the remaining questions.

Typo in the literature review

There is indeed a typo here. In the uniform price auction, under full-information feedback, Branzei et al, provided an upper bound which grows as $\tilde{\mathcal{O}} \left ( K^{3/2} \sqrt{T} \right )$, leaving a gap with the lower bound of $\Omega \left ( K \sqrt{T} \right )$. In this work, we provide an algorithm that guarantees a regret upper bounded by $\tilde{\mathcal{O}} \left ( K \sqrt{T} \right )$. In light of the previously mentioned lower bound, this algorithm's regret upper bound is optimal, fully characterizing the regret rates of this problem as $\Theta \left ( K \sqrt{T} \right )$. We apologize for this particularly confusing typo.

Contribution bandit feedback

• Under bandit feedback, for the uniform price auction, the main contribution of our work is the lower bound of order $\Omega \left (T^{2/3} \right )$ provided by Theorem 3. In the literature, the best lower bound available for the uniform price auction was the one in the full-information setting of $\Omega \left (K \sqrt{T} \right )$ by Branzei et al. This lower bound matches the rates in $T$ of the upper bounds provided by Potfer et al., therefore fully characterizing how regret scales in $T$ in this setting. We will ensure to better highlight that this lower bound is tight in $T$, not in $K$.
• As you mentioned, the worst-case bound we obtained for Algorithm 3 is worse by a factor $K^{1/3}$ in comparison to Potfer et al.. The main novelty of this algorithm is that it is able to adapt, guaranteeing $\tilde{\mathcal{O}} \left ( K \sqrt{T} \right )$ in the bandit setting when facing "easy" instances. The worst-case guarantees of $\tilde{\mathcal{O}} \left ( K^{5/3} T^{2/3} \right )$ ensure that, while able to leverage favorable instances, this algorithm still guarantees reasonable regret in other instances.

Techniques and challenges

We understand the need to provide more information on how our work differs from previous ones (Potfer et al., Branzei et al., Galgana et al.) in the techniques we used for algorithm design and analysis. We will include a "techniques and challenges" subsection. We will emphasize the fact that since we focus on stochastic opposing bids, our algorithms are fundamentally different from the ones used in previous work. Namely, while the previous approaches relied on discretizing the bid space $B$ (defined on line 109) and using randomized bandit algorithms, we neither need to discretize nor use randomized algorithms. Our algorithms mainly leverage statistical CDF estimation techniques. A key advantage of this approach is that it allows for a more straightforward analysis.

Table 1

We did not specify the dependence in $K$ in Table 1 to improve readability. We were able to obtain upper and lower bounds on the regret that match in their dependence on the time horizon $T$. Yet, the dependence on the number of items, $K$, is not tight. To represent these results accurately, we would need to present upper and lower bounds separately, using $\tilde{\mathcal{O}}$ and $\Omega$ instead of $\Theta$. We emphasized the differences in scaling with respect to $T$, as we believe this is the most interesting aspect of the contribution. To ensure that the notation is clear and represents the bounds fairly, we propose to mention that $\tilde{\Theta}$ hides factors that depend on $K$. Would these improvements be satisfying?

[1] Potfer, M., Baudry, D., Richard, H., Perchet, V., & Wan, C. (2024). Improved learning rates in multi-unit uniform price auctions. Advances in Neural Information Processing Systems, 37, 130237-130264.

[2] Brânzei, S., Derakhshan, M., Golrezaei, N., & Han, Y. (2023). Learning and collusion in multi-unit auctions. Advances in Neural Information Processing Systems, 36, 22191-22225.

[3] Galgana, R., & Golrezaei, N. (2025). Learning in repeated multiunit pay-as-bid auctions. Manufacturing & Service Operations Management, 27(1), 200-229.

Thank you for your feedback. We are happy to provide further clarification. Our contribution for the discriminatory auction are the following.

An Algorithm for the stochastic opposing bids

We propose the first algorithm for the stochastic opposing bid setting under the full-information feedback, which relies on CDF concentration bands. The main upsides of this algorithm compared to the one available in Galgana and Golrezaei 2025 are that it is deterministic, doesn't use a discretized version of the action space $B$, and its analysis is short and straightforward.

A More general lower bound for bandit feedback

We also provide an improved version of the existing lower bounds of $\Omega ( T^{2/3} )$ for the bandit feedback. We improve on the already existing bound in the following sense : the previously known lower bound scaled similarly with $T^{2/3}$ but was only valid for bids which can only take a discete set of values. We provide a version which allows for the bids to take any values in $B$. In essence, previous bounds only applied to discrete a action space while the bound we provide is valid for a continuous one (which is the setting in this paper).

Lower bounds validity for certain family of instances

We finally show, in section 5, that under bandit feedback, the lower bound still stands in several special cases in which the uniform price auction can be learned with a regret guarantee $\tilde{\mathcal{O}} \left ( \sqrt{T} \right )$.

Galgana, R., & Golrezaei, N. (2025). Learning in repeated multiunit pay-as-bid auctions. Manufacturing & Service Operations Management, 27(1), 200-229.

Thank you for the review.

In the absence of questions, we will address the two weaknesses mentioned in the review.

1. We believe our results are non-trivial and several aspects are surprising. For instance, the degeneracy of achievable regret rates in the uniform price auction, depending on whether the learner has unit, two-unit, or more than two-unit values (cf Table 1) is, in our opinion, rather surprising. We also consider it surprising that, under bandit feedback, when opposing bids are order statistics, uniform price and discriminatory auction exhibit regret rates which scale differently with $T$ (respectively $\Theta \left ( \sqrt{T} \right)$ and $\Theta \left ( T^{2/3} \right)$). Nevertheless, we understand your comment since some results intuitively make sense, such as the fact that regret in both auction formats scales identically under full-information (as $\theta \left ( K \sqrt{T} \right )$).

2. It is true that for practical applications, such an assumption might be considered strong. On the other hand, considering that opposing bids are fully adversarial is also not realistic. We believe a realistic middle ground is to consider a contextual version of the problem: opposing bids would be i.i.d. conditionally on a context, which the bidder would observe before participating in each auction. In this work, to keep the modeling aspect straightforward, we do not consider that contextual aspect.

We also want to point out the fact that the lower bounds derived in the paper are also valid for adversarial opposing bids. In that sense, only the upper bounds results in the paper are "limited" in their scope to stochastic opposing bids.

Furthermore, technically, this assumption has two main upsides. First, it makes the analysis of the algorithms more tractable as we can use a deterministic algorithm. Second, it enables us to derive instance-dependent bounds; these types of bounds, which characterize regret beyond worst-case, are not classically obtained for adversarial settings in the bandit literature [1].

[1] Lattimore, T., Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.