Summary
This paper studies a setting where a single seller runs repeated multi-unit auctions. In each multi-unit auction, there are $K$ identical units of good for sale. Each buyer individually has a valuation for the good with decreasing marginal returns and submits a bid vector. The seller will allocate the units according to the ranking order of the bids, and use uniform pricing. Specifically, the seller will set the price to be the $K$-th highest bid (or $(K+1)$-st highest bid in another variant). Such an auction format takes place in many important real-world settings, such as license auctions for CO2 emissions, ad auctions on online platforms.
The authors first show how to efficiently compute an optimum bid vector in the offline setting, which also serves as a benchmark bidding strategy for performance evaluation in the online setting. In the online setting, they can design algorithms with polynomial running time and low regret under either full information feedback or bandit feedback. They also give a lower bound on the expected regret of this problem. Additionally, they analyze the equilibria in the two variants of the auction to study whether they are susceptible to bidder collusion.
Strengths
1. This work contributes the line of literature on multi-unit auctions by considering dynamic bidding strategies rather than focusing the seller's side. The model is well built on previous work of mechanism design in combinatorial auctions, learning algorithm design in repeated auctions, and has significant implications for real-world issues such as license allocation.
2. The main insight that the bidder can compute an optimum bidding strategy in the offline setting by finding a maximum wight path in a DAG is quite novel. Particularly, the weight of an edge appears to depend on the whole bid vector but turns out to rely only on two neighbor bids, which I find quite interesting. Moreover, it also requires non-trivial techniques to design unbiased estimators for the bandit feedback model.
3. Other characterizations about this problem are provided, including regret lower bounds and equilibrium analysis.
4. All results and proofs are well written.
Weaknesses
The organization of this paper looks weird to me. Section 1.2 covers more than two pages. In particular, "equilibrium analysis" is one of the contributions but all the results about it are piled up in Introduction without an independent section. The paper is titled with ``online learning'', so I assume the algorithms for the online setting should be the highlight of this work, but now Subsubsection 1.2.3 accounts for more than half of Subsection 1.2.
Actually, this part of equilibrium analysis seems to have almost no connection to the $T$-round setting. Theorem 3 and 4 only give regret upper bounds, and do not analyze the convergence of the algorithm. No-regret learning algorithms can converge to a coarse correlated equilibrium, but there is no guarantee of convergence to any pure Nash equilibrium. Therefore, this part in fact studies the pure equilibria in a static setting from the perspective of the seller, aiming to figure out which kind of uniform pricing is a better pricing rule. Maybe the authors should consider changing the title to enlarge the scope of this paper.
Questions
1. I don't see why the authors concludes with a summary that the $K$-th price auction format may be preferable to the $(K+1)$-st price auction. Theorem 6 is a negative result about the core stable profile in the $(K+1)$-st price auction while the $K$-th price auction does not even have a pure Nash equilibrium. Why are they comparable?
2. Minor comments.
- In line 65, $z$ is used to denote an allocation, but then in the following paragraph, $x$ is used to denote the allocation. And $z$ is later used to denote a vertex in DAG.
- I personally feel that "repeated auctions" is the only accurate expression, while "repeated mechanisms" (line 33), "repeated setting" (line 76), "repeated auction" (line 272) are not appropriate expressions.
- Line 195, the angle -> from the angle.
- Line 201, such problem -> such a problem.
- In the definition of $S_i$ (equation 1), no value for $t$ (the superscript) is given.
- The key evaluating metric, regret, is not defined in the model part.
- There are some meaningless repetitions. For example, lines 220-223 almost repeat lines 89-93, the footnote on page 6 repeats the meaning of $x_i$ in line 68.
- Example 1 can help readers to better understand the model, so I think it is better not to defer it to the appendix.
- When $K=1$, the problem then becomes bidding in repeated first-price ($K$-th price) or second-price ($(K+1)$-st price) auctions. Pointing out the special cases may help readers better understand why the $k$-th price auction does not have a pure Nash equilibrium, and why the $k+1$-st price auction is more susceptible to bidder collusion.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.