Improved learning rates in multi-unit uniform price auctions

Summary

This paper considers online learning in repeated multi-unit uniform price auctions, motivated by the strategic participation of electricity producers in the electricity day-ahead market. By introducing a new modeling of the action space to EXP3, the authors propose an algorithm that achieves $\tilde{O}(K^{3/2}\sqrt{T})$, $\tilde{O}(K^{5/2}\sqrt{T})$, and $\tilde{O}(K^{4/3}T^{2/3})$ regret bounds for full information, all-winner, and bandit feedback, respectively. They also provide lower bounds for each case.

Strengths

1. They provide regret bounds for various feedback settings: full feedback, partial feedback, and bandit feedback. 2. The proposed algorithm improves the regret bound by using a new model of the action space.

Weaknesses

1. I think that the setting is not clearly written and seems to differ from previous work [1] without justification. In more detail, for the allocation described in (1), for player $i$, any items with a value larger than a price are allocated. However, in [1], the auctioneer allocates the $j$-th unit to the player who submitted the $j$-th highest bid. Additionally, the role of the valuation $v_l$ is not clearly described. 2. The motivation for the allocation policy in this setting may not be well described. [1]Brânzei, Simina, et al. "Learning and collusion in multi-unit auctions." Advances in Neural Information Processing Systems 36 (2024).

Questions

1. Could you provide a motivating example to justify the allocation policy in setting (1)? According to (1), it seems that multiple players may receive the same item, which may not be convincing to me. 2. According to the paper, the valuation $v_l$ is known to the bidder. What is the motivating example?

Rating

5

Confidence

2

Soundness

2

Presentation

2

Contribution

2

Limitations

The authors have addressed some of the open problems in the conclusion.

Summary

This work studies the problem of multi-unit uniform price auctions. By introducing a new modeling of the action space, the paper improves the regret of the online learning problem to $\tilde{O}(K^{4/3}T^{2/3})$ under bandit feedback, and $\Omega(T^{2/3})$ is a regret lower bound under this feedback model. Under the all-winner (partial feedback), the algorithm achieves a regret of $\tilde{O}(K^{5/2} \sqrt{T})$.

Strengths

The main strength of this work is to provide a new modelling of the action space to largely improve the regret of the considered problem. This new finding, together with the improvement, if correct, already makes a solid contribution in my view.

Weaknesses

The manuscript has the following weaknesses in my view: 1. Although the all-winner feedback model could be first raised in the multi-unit auctions, other similar partial feedback models have already been introduced in different settings, e.g., Chen et al., 2024. 2. The paper's method is an improvement over the method of Branzei et al., 2024, as claimed. Yet, the authors do not provide details on their DAG equivalence method, which makes it a bit hard to appreciate all the details of the newly proposed method. 3. The authors could provide more intuitions on some technical details; see Questions. 4. There seems to be an extra "}" in Equation (4); And should Equation (6) be $b_k \geq (j + 1) \epsilon \geq j \epsilon \geq b_{k + 1}$? [Ref] Chen et al., Dynamic Budget Throttling in Repeated Second-Price Auctions, AAAI 2024.

Questions

1. Could the authors provide more intuitions and details on the method of Branzei et al., 2024? 2. Could the authors provide some intuitions on Algorithm 2, the weight-pushing sampling? In my sense, this algorithm makes a sequential sampling of all $h$'s in $\mathbf{h}$. Please correct me if I am wrong. 3. In bandit and all-winner feedback models, why do you need to subtract $K$ in the numerator of the estimator? Could you please provide some intuition on this by comparing it with your treatment in the full feedback model where you do not do this step?

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors have addressed the limitations of their work.

Summary

The paper studies no-regret bidding algorithms in multi-unit uniform-price auctions with adversarial competing bids. In this problem, the bidder has diminishing marginal values for units of the item, and submits one bid for each unit. The top K bids win, and the payment is uniformly the lowest winning bid for each unit of the item. The authors present an algorithm that (1) under bandit feedback, achieves regret $\tilde{O}(T^{2/3})$, and (2) in a slightly more informative model where all winning bids are revealed, achieves regret $\tilde{O}(T^{1/2})$. Both bounds are almost optimal.

Strengths

The paper makes concrete improvement and presents almost optimal bounds for a meaningful problem that has received considerable attention. The techniques appear nontrivial.

Weaknesses

The paper is somewhat hard to navigate. For example, I was lost a few times when new concepts / definitions / constructions are introduced while it's not clear at the moment what purposes they serve. Some explanatory text would help. I'd also appreciate more motivation for the problem setup (e.g., diminishing marginal values). The paper could also use some polishing (there are many more small issues in addition to the ones listed below in detailed comments).

Questions

(also including detailed comments) Line 9: "this feedback interpolate ..." Line 27: "this represent ..." Line 28: "... others bidding strategies" Line 41, "... with uniform pricing is strictly harder than with uniform pricing": the latter "uniform" should be "discriminatory"? Also I wouldn't say they "suggest the former *is* strictly harder". Something like "the former *might be* strictly harder" sounds more accurate. "Auction rules" paragraph: it might help to quickly motivate diminishing marginal values here. I imagine someone unfamiliar with auctions / microeconomics may not immediately see why this makes sense. Line 59: competing bids being adversarial (and not stochastic) seems like an important modeling choice, and I'd mention this upfront (e.g., in the abstract or earlier in the introduction). Line 137: the gaps here seems to be $K^{3/2}$ instead of $K$? Line 183, eq (4): brackets don't match.

Rating

6

Confidence

3

Soundness

4

Presentation

2

Contribution

3

Limitations

No concerns.

Summary

The paper analyzes repeated multi-unit uniform price auctions through the lens of online learning. At each time step, a bidder submits a sequence of bids $(b_1,\dots,b_K)$ to win up to $K$ identical items for which the bidder holds known valuations that depends only on the number of won items and are the same from one round to the other. Other bidders participate to these multi-unit uniform price auctions and the first $K$ higher bids are the one that get the items, paying the $K$-th highest price or the $K+1$-th highest price, depending on the model. This setting was already studied by Branzei et al. (2024), but they obtained suboptimal learning rates for this problem. In this paper, the authors close the gap in the regret rate and they further analyze and characterize the learning rates arising from a different type of feedback that was not previously considered.

Strengths

The paper provides interesting insights on how to tackle repeated multi-unit uniform price auctions and this understanding translates into improved (and matching in the time horizon) learning rate with respect to the SOTA. The paper also provides a model for a new type of feedback that could be of interest in concrete applications and also characterize (in the time horizon) the learning rate of this problem. Overall, the paper provides a valid contribution to the development of online learning in auctions.

Weaknesses

Though this is quite common in this literature, the paper does not explore what can be done in strategic settings where also the other bidders learn, and what kind of dynamic might arise in this case. It would be interesting to model other bidders not as an oblivious environment, but rather as other learning agents. Typo. Line 41. "suggesting that bidding multi-unit auctions with uniform pricing is strictly harder than with uniform pricing." I assume that the second should be discriminatory pricing.

Questions

1) I see that there's still a mismatching rate when it comes to the other parameter $K$. Do you think that this is an artifact of the proof or we need better algorithms / better lower bounds to close this gap? 2) What if also the other bidders learn? I think that in this case we probably need a different definition of the regret. Do you have in mind any way to tackle this problem? 3) What kind of dynamic could arise if also the other bidders utilize the algorithm you proposed? Does the dynamic converge somewhere?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors correctly state the assumptions under which the theorem they proved hold.