Improved learning rates in multi-unit uniform price auctions

Thank you for your review.

W1/Q1 It is inexact to say that our setting is not the same as in [1]. While the way our allocation policy is described indeed differs from the description in [1] it results in the same allocations as allocating the $j^{th}$ items to the $j^{th}$ highest bid. Indeed, since all items are identical, it is sufficient to keep count of how many bids from player $i$ are above the price (and hence amongst the $K$ highest). Therefore strictly allocating the $j^{th}$ items to the $j^{th}$ highest bid and allocating one item for each bid in the $K$ highest gives the same allocation (as permuting identical items does not change the allocation). While it is possible for two players $i,k$ to have the same allocation $x_i(\mathbf{b})=x_k(\mathbf{b})$ this only means they get allocated the same number of items. We take note that this might not be straighforward and will ensure to make it clearer.

W2. Multi-unit auctions with uniform pricing and the associated allocation rule [1] used in this paper is a natural model for the short-term electricity market. We give some references l99.

Q2. From both a motivation and technical point of view, it is reasonable to assume some knowledge of the valuations :

• The value is a quantity that represents how useful each item will be to the bidder. In that sense, any bidder trying to acquire items should have some knowledge of the valuation of this item $*for them*$.
• We are studying the adversarial opposing bid setting, yet, as pointed out in [2] without any assumption on the valuation (ie adversarial valuation that can vary across auctions) no non-trivial regret guarantees can be obtained. Since their setting ( first price single item auction with valuation observed before each round ) is strictly easier this impossibility result also applies to multi-unit uniform auctions.

We chose to focus on known valuation as it allows for a more concise and understandable analysis. Another possible model would be to assume that valuations are unknown but constant across auctions and that a noisy version of the valuation is observed whenever an item is won. Adapting our algorithm to this setting would require to use estimates of valuations instead of the real values. We leave this adaptation to future work as we believe the main ideas of our work are easier to get in the setting we consider.

[1] Brânzei, Simina, et al. "Learning and collusion in multi-unit auctions." Advances in Neural Information Processing Systems 36 (2024).

[2] Balseiro, S., Golrezaei, N., Mahdian, M., Mirrokni, V., & Schneider, J. (2019). Contextual bandits with cross-learning. Advances in Neural Information Processing Systems, 32.

Thank you for your response. I have some further questions based on your response.

According to your response, the items are identical. Then, what is the reason for having different valuations for each item? Also, based on your motivation example of the electricity market, I'm wondering whether the items are identical or may be different based on the usage.

Thank you for these questions.

First, we need to clarify that both our allocation function and valuation are parameters that relate to the number of items attributed to a player (because items are identical, their indexes are irrelevant). Furthermore, the valuations are marginal: for bidder $i$ and for $j \in [K]$, $v_{i,j}$ quantify how much more bidder $i$ values getting $j$ items than $j-1$ items.

With this in mind, the reason we have different valuations is to allow for diminishing marginal utility, a common microeconomics assumption introduced in [1], chapter 2. The main intuition is that the more someone has of an item, the less he values getting more of it (drinking water for instance is only very valuable for the first liters of the day). In the example of electricity markets, while the first MWh and the tenth MWh attributed to a bidder are identical, the bidder will dedicate the first to make critical infrastructure work, while the tenth would be used to activate processes that are more easily shut down and restarted.

In our setting, an item cannot be allocated to multiple bidders at the same time. The description of our setting only specifies the number of items to be allocated to each player, hence ensuring that the total amount of allocated items is equal to $K$ is sufficient to ensure no items need to be allocated twice. Because items are identical it is unnecessary to give them an index and determine which item goes to which bidder.

[1] Greenlaw, Steven A., et al. Principles of Microeconomics 2e. United States, OpenStax, 2017.

Thank you for your review.

W1. The all-winner feedback model is indeed a particular case of partial feedback that is widely studied. However, it has never been studied in multi-unit auctions which is the focus of our study. We will clarify this in the related work section.

W2/Q1. The key idea in [1] is the decomposition of the utility in a sum of terms where each term only depends on two consecutive bids. They therefore associate to every set of bids a path and the utility is seen as the sum over the utility of each edge. In contrast, we are able to decompose the utility as a sum of terms that can be estimated individually (without any need for a dependency in previous terms) and therefore obtain improved guarantees.

W4. Indeed equation (4) has an extra “}“ and equation (6) should be $b_k \geq (j+1) \epsilon > j \epsilon \geq b_{k+1}$.

Q2. Your understanding is correct. Algorithm 2 indeed performs a sequential sampling of the $h$’s in $\mathbf{h}$, this allows for both a more efficient sampling and the use of specific weights for each $h$, see [3] for a more complete overview. One could also directly sample $\mathbf{h}$, ensuring the weights of each $\mathbf{h}$ are the sum of all the weights of their components $h$’s. Intuitively this would have a higher complexity cost as it would sample in the product space instead of successively in each space. (for $N,M$ integers computing weights and sampling once in $[N]^M$ is exponentially less efficient than computing weights and sampling $M$ times an element of $[N]$).

Q3. Subtracting $K$ in the numerator is a technical detail which ensures that the value the estimator $\hat{u}^t(\mathbf{h})$ takes can be upper bounded which is necessary for the analysis of EXP3. In the full-information feedback, we directly use the utility (and not an estimator) $u^t(\mathbf{h})$, which is already upper bounded by $K$. The difference between Hedge and Exp3 is discussed in [2] notes 11.5 remark 3.

[1] Brânzei, Simina, et al. "Learning and collusion in multi-unit auctions." Advances in Neural Information Processing Systems 36 (2024).

[2] Lattimore, Tor, and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.

[3] TAKIMOTO, Eiji et WARMUTH, Manfred K. Path kernels and multiplicative updates. In : International Conference on Computational Learning Theory. Berlin, Heidelberg : Springer Berlin Heidelberg, 2002. p. 74-89.

Thank you for your review. Thank you for noticing the typos and for suggesting some improvements in the presentation of our approach. We will clarify this part and make the necessary correction in the revision.

Line 41: Indeed you are right, we will reformulate according to your suggestion.

“Auction rule paragraph”: The non-increasing assumption on the values $v_1,v_2,...,v_K$ results from the law of diminishing returns, a standard assumption in microeconomics see [2] chapter 2. It is also a standard assumption in multi-units uniform auction and is studied in [1] in the non repeated setting. We will add these comments just after line 61.

Line 59: We agree and will add that competing bids are adversarial in the abstract

Line 137: The gap with the lower bound is indeed a multiplicative factor of $K^{3/2}$. In that sentence we meant to highlight that under all winner feedback our algorithms upper bound is only worse of a factor $K$ compared to the full-information upper bounds ( $\mathcal{O}(K^{5/2} \sqrt{T})$ versus $\mathcal{O}(K^{3/2} \sqrt{T})$ ). We take note that it can be ambiguous and will reformulate it.

Line 183: Thank you for noticing, it should be h_{k+\frac{1}{2},j} (\mathbf{b}) = \mathbb{1} \left \\{ \exists \boldsymbol{\beta} \in B_{ \setminus \epsilon}, \\{x(\mathbf{b},\boldsymbol{\beta})=k \\} \cap \\{ (j+1)\epsilon > p(\mathbf{b},\boldsymbol{\beta}) > j\epsilon \\} \right \\}

[1] Ausubel, Lawrence M., Peter Cramton, Marek Pycia, Marzena Rostek, and Marek Weretka. “Demand Reduction and Inefficiency in Multi-Unit Auctions.” The Review of Economic Studies 81, no. 4 (289) (2014): 1366–1400.

[2] Greenlaw, Steven A., et al. Principles of Microeconomics 2e. United States, OpenStax, 2017.

Thank you for your review.

Q1. Indeed our upper and lower bound do not match for the parameter K. We believe the lower bound in the bandit setting is not tight with respect to its dependency in $K$, we expect the tight bound to depend on the scale of the utility $K$. Regarding upper bounds, we do not see any obvious way to improve them. We therefore leave the question of closing the gap to future work and in particular the task to show whether the all-winner feedback is strictly harder than the full information feedback.

Q2. If the other bidders learn, we need to move from an oblivious adversary to an adaptive one. The notion of regret we should use remains the same : comparing the average utility to the best strategy in hindsight, but we need to allow the opposing bids at time $t$, $\boldsymbol{\beta}^t$ to depend on the history up to time $t-1$. Our algorithm is a variation of EXP3 for which the regret bounds can be generalized to an adaptive (or $*reactive*$ ) adversary, as discussed in [3] notes 11.5, point 4, this can be done without any change in the analysis. We are confident that the regret bounds therefore also hold in this setting.

Q3.The dynamics of play that arise when players use no-regret algorithms in a game is an active field of research. The multi-unit uniform auction is a game with continuous action space. However, even in finite games the dynamics are not fully characterized. In finite games, if all players play EXP3, the average play converges to a Coarse Correlated Equilibrium or Hannan set (see chapter 7.4 of [1]). The convergence of iterates towards a Nash equilibrium is only shown for finite potential games [2] which does not fit multi-unit uniform auctions. The current theory is therefore not sufficient to characterize the dynamics of play in our framework.

[1] Cesa-Bianchi, Nicolo, and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.

[2] Heliou, Amélie, Johanne Cohen, and Panayotis Mertikopoulos. "Learning with bandit feedback in potential games." Advances in Neural Information Processing Systems 30 (2017).

[3] Lattimore, Tor, and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.