Randomized Truthful Auctions with Learning Agents
Authors: Gagan Aggarwal
Anupam Gupta
Andres Perlroth
Grigoris Velegkas
Venue: NeurIPS 2024 poster (2024)
Keywords: Auctions
No-Regret Learning
Revenue Maximization
Primary area: algorithmic_game_theory
TL;DR: We show that in repeated deterministic truthful auctions with two bidders using MWU, they do not converge to truthful bidding for many choices of learning rates. However, adding a small amount of randomization to the auction leads to convergence.

Abstract: We study a setting where agents use no-regret learning algorithms to participate in repeated auctions. Recently, Kolumbus and Nisan [2022a] showed, rather surprisingly, that when bidders participate in second-price auctions using no-regret bidding algorithms, no matter how large the number of interactions $T$ is, the runner-up bidder may not converge to bidding truthfully. Our first result shows that this holds forall deterministictruthful auctions. We also show that the ratio of the learning rates of different bidders can qualitatively affect the convergence of the bidders. Next, we consider the problem of revenue maximization in this environment. In the setting with fully rational bidders, the seminal result of Myerson [1981] showed that revenue can be maximized by using a second-price auction with reserves. We show that, in stark contrast, in our setting with learning bidders, randomized auctions can have strictly better revenue guarantees than second-price auctions with reserves, when $T$ is large enough. To do this, we provide a black-box transformation from any truthful auction $A$ to an auction $A'$ such that: i) all mean-based no-regret learners that participate in $A'$ converge to bidding truthfully, ii) the distance between the allocation rule and the payment rule between $A, A'$ is negligible. Finally, we study revenue maximization in the non-asymptotic regime. We define a notion of auctioneer regret that compares the revenue generated to the revenue of a second price auction with truthful bids. When the auctioneer has to use the same auction throughout the interaction, we show an (almost) tight regret bound of $\tilde{\Theta}(T^{3/4})$. Then, we consider the case where the auctioneer can use different auctions throughout the interaction, but in a way that is oblivious to the bids. For this setting, we show an (almost) tight bound of $\tilde{\Theta}(\sqrt{T})$.

Randomized Truthful Auctions with Learning Agents
Gagan Aggarwal
Anupam Gupta
Google Research gagana@google..oom
New York University, Google Research anupam. gannyu.ddi
Andres Perlroth
Grigoris Velegkas
Google Research
Yale University gri.oriis.vllegassellleecce
Abstract
We study setting where agents use no-regret learning algorithms to participate in repeated auctions. Kolumbus and Nisan (2022a) showed, rather surprisingly, that when bidders participate in second-price -picep auctions using no-regret bidding algorithms, no matter how large the number of interactions is, the runner-up bidder may not converge to bidding truthfully. Our first result shows that this holds for general deterministic truthful auctions. We also show that the ratio of the learning rates of the bidders Next, we consider the problem of revenue maximization in this environment. In the setting with fully rational bidders, Myerson (1981) showed that revenue can be maximized by using a second-pric auction with reserves. We show that, in stark contrast, in our setting with learning bidders, randomized auctions have strictly better revenue guarantees than second-prics auctions with reserves, when T is large enough. Finally, we study revenue maximization in the non-asymptotic regime. We define notion of auctioneer regret comparing the revenue generated to the revenue second price auction with truthful bids. When the auctioneer has use the same auction throughout the interaction, we show an (almost) tight regret bound of (TT3/4) If the auctioneer can change auctions during the interaction, but in a way that is oblivious to the bids, we show an (almost) tight bound of é ((VT).
qualitatively affect the convergence of the bidders.
Introduction
In auction design, truthfulness is highly sought-after property. It allows bidders to simply reveal their true valuations, simplifying the bidding process. standard single item setting with fully rational profit-maximizing bidders, Myerson's seminal paper Myerson (198T) shows that an auctioneer can achieve optimal revenue by using a truthfuul and deterministic auction mechanism a Second Price Auction (SPA) with reserve price.
In many applications nowadays, buyers longer bid directly in the auction but, instead, use learning algorithms to bid on their behalf. For example, in online advertising, platforms offer automated bidding tools that manage ad campaigns on behalf of advertisers. Such bidders learn bid over many rounds and are not fully rational. In a surprising result, Kolumbus and Nisan (2022a) show that some appealing properties of second- price auctions break down the presence of such learning bidders. In particular, when pprofitmmximizingg bidders use no-regret learning algorithms, the second-prics auction does not achieve as much revenue as with fully rational bidders. Indeed, bidders do not learn to bid their value, and consequently, the runner-up bidder's 's bid is less than their value with positive probability, which diminishes the second price auction's 's revenue. Moreover, Kolumbus and Nisan
Part of the work done while the author research intern Google Research in Mountain View.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

(202bb) show that for a setting where rational agents are using learning algorithms to bid, then it is no longer optimal to truthfully submit their value as the input to the learning algorithm. This raises a crucial question: are there truthful auctions that promote convergence to the true valuations within a learning environment, and can they also guarantee strong revenue performance?
In this paper we provide an affirmative answer to this question. In doing so, we also showcase the value of randomized mechanisms often overlooked in settings with profit-maximizing bidders for environments where bidders are learning agents. While randomization introduces inherent inefficiencies due to allocations to low-valuation bidders, this very behavior facilitates learning among low-valuation bidders. A revenue avvenue-mxxmizing maximizing auctioneer must now carefully balance the randomization within a truthful mechanism incentivize learning without incurring excessive revenue loss due to mis-allocation.
We build our theory based the model presented by Kolumbus and Nisan (2022)). We consider single-item repeated interactions over T periods. There are two profit-maximizing bidders participat- ing the auctions, with valuations that are drawn independently from the same distribution, and fully persistent over time. This assumption is motivated by online ad auctions, where multiple auctions are taking place every second, and the valuations of the advertisers remain stable for certain time scales, e.g., a day or week. Thus, there is typically very large sequence of auctions where the valuations of the participating agents are persistent. Bidders use mean-based no-regret learning algorithms (Braverman et al. 2018)) and receive full feedback on which they base their updates. (Many of our results extend immediately to multiple bidders. We discuss other extensions, such as the partial feedback settings, in Appendix G The auctioneer focuses on truthful auctions, and their objective to maximize the total revenue they achieve over the T rounds of interaction. Our results are the
following:
1.1 Our Results and Techniques
Limitations of Deterministic Auctions. Our first set of results (in Section 3 characterize the con- vergence of learners who are using Multiplicative Weights Update (MWU) in repeated deterministic auctions. In particular, show the following sharp phase transition:
If the learning rate of the winning type is at least as fast as the learning rate of the runner-up type, then the rumner-up type will not converge to bidding truthfully, even as T -> oo; in fact, it will be bidding strictly below its true value, in expectation.
On the other hand, we show that in many auctions, such as SPA, if the learning rate of the runner-up type is strictly faster than that of the winning type, then the runner-up type will indeed converge to truthful bidding.
These generalize the results of Kolumbus and Nisan (022a) who showed that in SPA, when bidders are using MWU with the same learning rate, then the low type will not converge to bidding truthfully. The main challenges to proving this set of results arise from our study of general deterministic auctions, which have less structure than second-price auctions. Indeed, small differences in the learning rates can affect the landscape qualitatively, as is manifested from our results. Moreover, while the auctions are deterministic, the learning algorithms are randomized and highly correlated. Hence our approach is to break down the interaction into several epochs and establish some qualitative properties which hold, with high probability, at the end of each epoch. This requires a careful accounting of the cumulative utility of each bid of both bidders within every epoch; in particular, if our estimation is off by even some (1) term, then it will not be sufficient to establish our result.
Strictly-IC Auctions and the Power of Randomized Mechanisms. The results in Section show that since the low valuation bidder tends to underbid, an auctioneer using SPA with reserve makes strictly less revenue than that predicted by the model with rational agents. Motivated by this, we consider a special class of randomized auctions called strictly-IC auctions. These are randomized truthful auctions where for each bidder, it is strictly better to bid their true valuation compared to any other bid. We show that any strictly-IC auction is asymptotically truthful: that is, the limit point of the bidder's bid converges to their true value. Furthermore, we provide a black-box transformation from any truthful auction A (deterministic or not) to a randomized auction A' that has the following two properties: (i) the bidders converge towards truthful bidding, and (ii) the difference between the allocation and payment rules of the original auction and its strictly-IC counterpart A' are negligible for any bid profile. Hence, such an auction A' behaves similarly to A, but, crucially, it conveys

---

information to the low bidder to help it converge to truthful bidding. As a corollary of this result, we get that SPA with reserve not revenue-maximizg maximizing in this setting, and that randomization can get strictly more revenue than SPA with reserve. This is in stark contrast with the seminal result of 198T) which shows that SPA with reserve is optimal for rational bidders.
|Myerson|
At a more conceptual level, our results for randomized mechanisms can be viewed as showing that having enough randomness is key to the low bidder converging to truthful bidding: this randomness can come from the process itself, c.g., if bidder values are independently drawn in each round, as in Feng et al. 2021)) But if not, and the ranking of the bidders does not change much due to the lack of inherent randomness, our results show that injecting external randomness into the auction induces the desired learning behavior and hence improves the revenue. Having persistent valuations is just one case of the ranking of the bidders remaining stable over time: studying this case allows us to showease our main ideas, but a central message of our work is that the presence or absence of stability in the rankings of the bidders is the main factor that dictates convergence to truthful bidding.
Kon-Asymptotte Analysis. Our next set of results in Bection[Jaddress the non-asymptotic regime. Here we consider the prior-free setting, meaning that the valuations of the bidders could be drawn from potentially different distributions that are unknown the auctioneer. In order to evaluate its revenue performance when bidders are learning agents, we introduce the notion of auctioneer regret for an auction, which measures the difference between the revenue achieved over T' rounds of implementing a given auction with learning bidders and the revenue achieved by implementing the optimal auction with rational bidders (i.e., SPA with a reserve price). Proposition [5.2 shows that if the auctioneer is constrained to use the same auction rule for all T rounds, then no truthful auction- deterministic or randomized - can achieve an auctioneer-regret better than O(T3/4) in the setting of adversarial valuations. However, if the auctioneer can change the auction rule just once within the T rounds, with the change happening at time independent of the bid history, then the auctioneer's s show in Proposition 5.4 that this bound of Ó D(VT) is optimal even if the auctioneer can design the auction schedule. As byproduct of our result, we show that the first-stage randomized auction used by the mechanism leads to the fastest convergence to truthful bidding from no-regret learning agents.
regret drops Ö(VT), as we show in Section 5 Moreover,
To show that an auctioneer facing learning bidders using MWU must suffer Q(T revenue loss compared to the setting when is facing rational agents, we break down the revenue loss into two oon-overlapiing epochs: one where the learning bidders have not converged to truthful bidding, and the other where the bidders are truthful. Now an auctioneer using the same auction throughout the interaction faces trade-off: they can speed up the learning process to reduce the revenue loss from the first epoch, but this loses revenue in the second epoch due to the fact that the auction now differs significantly from SPA. Our result optimizes this trade-off to show that an 2((73/4) revenue loss is unavoidable. This naturally suggests decomposing the interaction into two epochs: in the first one, the auctioneer uses a truthful auction to facilitate the convergence to truthful bidding, and in the second one it uses SPA. We then design an auction that guarantees the fastest convergence to truthful bidding for mean-based learners in the prior-free setting, and we show that an improved revenue loss of at most O(VT) can be achieved with this approach. (Importantly, to maintain truthfulness, the decisions of the auctioneers are fixed before the beginning of the interaction and are not affected by the bids.) This regret of Ö(VT) seems surprising, because in traditional no-regret learning settings the optimal regret is achieved when the exploration and exploitation phase are intermixed.
1.2 Related Work
The most closely related works to our setting are Feng et al. (202I): |): and Nisan (2022a); [Banchio and Skrzypacz (2022); Rawat (2023). All these works study the long- term behavior of bidding algorithms that participate in repeated auctions, focusing on first-price and second-price auctions, but they give qualitatively different results. This is because they make different assumptions across two important axes: the type of learning algorithms that the bidders use and whether their valuation is persistent across the interaction or it is freshly drawn in each round. |Fng et al. (202T) studied the convergence of no-regret learning algorithms that bid repeatedly in second-price and first-price auctions, where all agents have i.i.d. valuation that are redrawn in every round from a discrete distribution that has non-negligible mass on each point. They show that in this setting the bidders exhibit the same-long term behavior in both second- price and first-price
Deng al. (2022); Kolumbus
3

---

auctions that classical theory predicts, i.e., the bids in second-price auctions are truthful and the bids in first-pre first-price auctions form Bayes-Nash equilibria. Kolumbus and Nisan (2022a) studied the same setting with the crucial difference that agents' valuations are persistent across the execution and they are not resampled from some distribution at every iteration. Interestingly, they showed that in the case of two bidders with in second-pric auctions, the agent that has the highest valuation will end up bidding between the low valuation and its valuation, whereas the agent with the low type will end up bidding strictly below its valuation. Intuitively, in their setting the high type bidder quickly learns to bid above the valuation of the low type bidder and always win the auction, and thus the low type does not get enough signal push its bid distribution up to its valuation. On the other hand, when the valuations are redrawn as in Feng et al. (02T). the competition that the agents face varies. In the long run, this gives enough information to the algorithms to realize that bidding truthfully is the optimal strategy. In the case of first-price auctions where the agents have persistent valuations, both Kolumbus and Nisan (2022a) ; Deng et al. (022) provide convergence guarantees of no-regret learning algorithms. The type of "meta-games" we touch upon in our work, where we want to understand the incentives of the agents who are submitting their valuations to bidding algorithms that participate in the auctions on the behalf of these agents, were originally studied by Kolumbus and Nisan (2022a) and, subsequently, for more general classes of games by Kolumbus and Nisan (2022b).
The pioneering work of Hart and Mas-Colay (000) showed that when players deploy no-regret correlaadd equilibria. Recently, there has been a growing interest in the study of no-regret learning in repeated auctions. The empirical study of
algorithms to participate in games they converge
Nekipelov al. (2015) showed that the bidding behavior of advertisers Bing is consistent with the use of no-regret learning algorithms that bid on their behalf. Subsequently, [Braverman et al. (2018) showed, among other things, that when seller faces no-regret buyer in repeated auctions and can use non-truthful, it can extract the whole welfare as its revenue. A very recent work (Cai et al.] 2023) extended some of the previous results to the setting with multiple agents. For a detailed comparison
between our work and Cai et al. 2023), we refer to Appendix B
Banchio and Skrzypacz (2022): Rawal (023)) diverge from the previous works and consider agents that use Q-learning algorithms instead of no-regret learning algorithms. Their experimental findings show that in first-price auctions, such algorithmic bidders exhibit collusive phenomena, whereas they converge to truthful bidding in sccond-price auctions. One of the main reasons for these phenomena is the asynchronous update used by the Q-learning algorithm. The collusive behavior of such algorithms
has also been exhibited in other settings (Calvano et al. 2020) Asker et al. [002]] 2022b den Boer et al. 2022 Epivent and Lambin 2022. Asker et al. (022a). Notably, [Bertrand et al. (2023) formally
proved that Q-learners do collude when deployed in repeated prisoner's 's dilemma games.
In related line of work. Zhang et al. (203)) study the problem of steering no-regret learning agents to a particular equilibrium. They show that the auctioneer can use payments to incentivize the algorithms to converge to particular equilibrium that the designer wants them to. An interpretation of our results is that randomization is a way to achieve some kind of cquilibrium steering in repeated auctions.
Diverging slightly from the setting we consider, some recent papers have illustrated different ad- vantages of using randomized auctions over deterministic ones. Mehta (2022); Liaw et al. (2023) showed that there are randomized auctions which induce equilibria with better welfare guarantees for galue-maximizing autobidding agents compared deterministic ones. In the setting of revenue maximization in the presence of heterogeneous rational buyers. Guruganesh et al. (2022) showed that randomization helps when designing prior-free auctions with strong revenue guarantees, when the valuations of the buyers are drawn independently from, potentially, non-identical distributions.
2 Model
Our model follows the setup used in Kolumbus and Nisan (2022a). There are T rounds, and the auc- tioncer sells a single item in each round = I,..., T. There are two bidders, with bidder i E 21 having persistent private valuation v; drawn i.i.d. over the discrete set Ba from a regular distribution F. (A discrete distribution is regular the discrete virtual valuation
1/2,
function (vv) := V 1 En'se Prfe'] non-decreasing.) Given an allocation probability x and price Pr(e)
p. the bidder with valuation e receives a payoff of x - pp. In what follows, we refer to the bidder with valuation 7y = min(v1, v2) (resp. UH max(U1,22 v2 as the low type (resp. high type).
4

---

We are interested in truthful auctions, (also called strategy-prood auctions, or dominant sicentive-compatte mechanisms) that are individually rational, so that at every round the auctioneer uses mechanism ((z), (rh.r5) satisfying
V;- (1; b') -pp (v,, b) 2 oi x; - b), V;- (1; b') - p 8) 2 0,
Vvi,b,b' E BB. i i= 1,2, Ve, E Ba, i i= 1,2.
In this work, we study various properties of randomized truthful auctions.
Definition 2.1 (Randomized Truthful Auction). A truthiful auction ((z1, (pi. P2]) is randomized if there is some bid profile (b,, b2) E B3 such that either xn (b), b2) E (0, 1) or 22(b1, b2) E (0. 1).
Bidders employ learning algorithms that bid over the T rounds. We assume that the learning algorithms are mean-based no-regret learning algorithmss (Braverman et al. 2018). For the following discussion, define (/{(b b².) : =En= 8.- x7 (b, b_,) p. (b, 6_.) to be the cumulative reward of agent i when they bid b over the t rounds, whereas the other agent's ' bids are b': = (o The mean-based property states that if a bid b E Ba has performed significantly better than bid D' E Ba, then the probability of bidding D' in the next round is negligible. This is formalized below.
Definition 2.2 (Mean-Based Based Property (Braverman et al. 2018), ). An algorithm for agent i is 8-mean- based if for any bid sequence b": such that U,- (b b'
Uf- b'm.) > 5 T, for some b, b' E Ba, the probability of playing bid U' in the next round is at most 6. We say that an algorithm is mean-based if it is t-mean-basele for some 8 = o(1)
The no-regret learning property states that the cumulative utility that the bidding algorithm generates close to the cumulative utility that the optimal fixed bid would have generated, regardless of the history of bids the other bidders played. This is formalized in Definition C.I Mean-based no-regret learning algorithms are becoming a standard class of learning algorithms use in auction environments (see, e.g.. |raverman et al.) (2018); Feng et al. (202T): DDng et al. (2022): (0022)][Kol])) Kolumbus and Nisan (2022a), and references therein) and include many known no-regret learning algorithms, including the multiplicative-wert weriihtttiiewwihhts update algorithm (MWU). For completeness, we present the version of MWU that we use in our work in Algorithm I The above definitions consider a fixed value of T. Thus, given sequence of such values T and the limiting behavior as T - cc, say that a family of algorithms, parameterized by the time horizon T, satisfies the mean-based definition if there exists {8r Fren such that 8T ++ O, and each algorithm in this family is dy-mean- based. We define the no-regret property of such a family of algorithms in a similar way. In general, the asymptotic behavior of the algorithms we study in this work is with respect to T and the big O notation suppresses quantities that do not depend on T.
For the sake of exposition, we focus on the full feedback setting: after every round t E [T]. the algorithm learns for each bid E BA the (expected) utility it would have generated had it played bid b. In Appendix G we discuss potential extensions.
Throughout this paper we make natural assumption on the algorithms which restrict bidders to never bid over their value. Specifically, for any round f, and any history of bids before period t. agent i bids b, > & with zero probability. Without this assumption. [Braverman et al. (2018); Cai al. (2023) show that the auctioneer can extract the entire welfare in the setting where the valuations of the agents are drawn i.i.d. in each round. We focus on the last-iterate convergence of the distribution of the bids of the algorithms as T + co. This is a desirable property of algorithms in multi-agent games, and recent work has focused on establishing it for learning algorithms (Cai et al., 20226 a Cai and Zheng 2022). This is formalized in Definition C
Due to space limitations, all the proofs of our results can be found in the appendix.
3 Deterministic Truthful Auctions
In this section we study the effect of the learning rate on the convergence of no-regret learning algo- rithms non-degenerate deterministic truthful auctions. Informally, the non-degeneracy requirement states that i) the winning bidder W under truthful bidding gets strictly positive utility, ii) there is some sufficiently small bid of the winning bidder such that the runner-up bidder wins the item by bidding UR but does not win by bidding UR- 1/5. The formal definition is given in Definition D.I
5

---

We focus our attention to bidders that use MWU to participate in the auctions and we study the bidding distribution they converge to as a function of the ratio of the learning rate of their algorithms. Throughout this section we refer to the bidder who wins the auction under truthful bidding as the winning bidder and to the bidder that loses the auction under truthtelling as the runner-up bidder. Our main result in this section shows the following behavior in non-degenerate deterministic truthful auctions:
The winning bidder converges to bidding between its minimum winning bid and its true value, no matter what the choice of the learning rates of the algorithms are.
If the learning rate of the runner-up bidder is strictly faster than the learning rate of the winning bidder, then the runner-up bidder converges to bidding truthfully.
If the learning rate of the runner-up bidder is not strietly faster than that of the winning bidder, then the runner-up bidder converges to bidding distribution whose mean is strictly smaller than its true value. This result holds under an even milder requirement than non- degeneracy. Namely, long as the utility of the winning bidder under truthful bidding is strictly positive.
We remark that, when the learning rates of the algorithms are instantiated before the random draw of the two valuations of the agents that are i.i.d. from some distribution F. then with probability at least 1/2 the runner-up bidder will not converge to bidding truthfully, if the underlying auction is deterministie. As we will show later, this behavior worsens the revenue guarantees of the auction.
Let us first set up some notation to facilitate our discussion. We denote by ow E {UL, hh} and ny (resp., UR E {Ur, UH}. and n the value and learning rate of the winning bidder (i.e., the one who wins if both bidders bid truthfully) and the runner-up bidder, respectively. We would like to remind the readers that, typically, the learning rate 1/r of MWU is a decreasing function of T and is chosen in way to minimize the quantity Ca/or + CA '/T -,, where C2. CA are -eeeedde constants. Usually, it is instantiated with 1/T = 1/VT. However, for the purposes of our analysis we will say that yr is non-degenerate if lim //T T = oo, limm AT- log T = O. The intuition is that if the learning rate is slower than 1/"T, the bidder will be adjusting its bid distribution very slowly, so it will not learn to bid correctly. On the other hand, if the rate is faster than 1/ log T then the bidder will be adjusting its distribution too aggressively.
Our results show that in deterministic auctions the convergence behavior of the bidders depends heavily on the ratio between the learning rates. In particular, for the bidder with valuation tw. we show that its bids converge to distribution supported between P. the price it would pay if both bidders bid truthfully, and its value uW, no matter what the choice of the learning rate of its algorithm is. On the other hand, the convergence behavior of the runner-up bidder is more nuanced: if 0 = w(1), i... the runner-up bidder learns more aggressively than the winning bidder, then it converges to constant,
bidding truthfully. However, if //// W < C'a, where C' is some discretization-depenie then the runner-up converges to a bidding distribution that puts positive mass on every (discretized) point between 0 and UR, and, in particular, its expected value is strictly less than UR. We remark that even though our proof idea is inspired by Kolumbus and Nisan (002a).. our analysis considers all the possible learning rates that MWU could be instantiated with and requires more technically involved argument. In particular, we notice that while the result of Kolumbus and Nisan (2022a) is, implicitly, proved for identical learning rates, we show that the choice of the learning rate affects the qualitative behavior of the algorithms in a crucial way.
We prove this result in two parts. We start with the case where of/n0 < Cs. The idea of the proof is to split the horizon into consecutive periods of size (11/n)), which we call epochs. Now following the idea of Kolumbus and Nisan (2022a), we show that within each epoch the runner-up bidder bids truthfully 211/T/ ) many times, so the total utility of the winning bidder for bidding between P and ew will be least (2(1 /ny greater than bidding anything between 0 and ý - 1/AA. Because its learning rate is 17/ this means that will move a constant fraction of its mass from the region {0. 1 1/A..... p- - } to the region (p..... Ew }. Summing this geometric series, we see that the winning bidder will submit bids in the region (0. 1/2, "
1/4} at most (1 ) many times. Let us now focus on the runner-up bidder. Following the previous argument, its total utility for bidding
on will be at most ((1 (1/n// W) greater than bidding some other bid 8' E BA. Since /f / < C. this means the probability of bidding b' after T rounds is only smaller than the probability of bidding

---

UR by discretization-deee dependent multiplicative constant. The formal statement of this result and its proof follow are postponed Appendix D
Our next result illustrates that the convergence behavior of the runner-up type exhibits a sharp transitran phenomenon: if ryf is even slightly faster than n/ i.e., w//n w(1), then the runner-up will learn to bid truthfully. Let us first give a high-level idea of the proof. Similarly as before, we split the horizon into intervals of size O(1/n ). We consider the first interval of this interaction. Because of the choice of the learning rate, we can show that the winning bidder will bid en - 1/A at least 12(1/g) many times. Thus, this means that the total utility of bidding un for the runner-up bidder will be at least QQ /1/ greater than bidding any other bid. Since n/f /// w(1), after the first epoch the MWU algorithm will place all but a o( )-fraction of the probability mass to bidding truthfully. The formal statement and its proof appear in Appendix [
Next, we discuss the implications that our results have to the revenue guarantees of the auctioneer, In the setting with rational bidders, the seminal work of Myerson (9811) showed that using second-price auctions with an anonymous reserve price, which depends on the value distribution F, generates the optimal revenue for the auctioneer. Our next result shows that this is longer true when the bidders are learning agents, even when the valuations of the agents are drawn i.i.d. from the uniform distribution on Ba, which we denote by U [BB.). Intuitively, this happens because, no matter what the reserve price is, with some non-zero probability the valuations of both agents will be higher than the reserve price. Then, since the runner-up bids will be strictly lower than the true valuation, the generated revenue will be strictly lower than in the setting with rational agents, even when ' - co.
Theorem 3.1 (SPA with Reserve Is Not Revenue Optimal), Let two agents draw their valuations from the uniform distribution over [[] and participate in T repeated auctions using mean- mean-based learners. Let by big be the bid distributions after T rounds. Let Rev(b, b2;r) denote the revenue of the second-price auction with reserve price r when the bids are bi, b2 E B Then, for all
r <<1 1 - 1/A,,
E UI D1
lim T
E ba
Rev(bi,
b2;r)
U1, 02l
<
E 01.02~U(Ba)
Rev(e1 12;r)] C,
where e > O is some constant that does not depend on T.
4 The Value of Randomized Truthful Auctions: The Asymptotic Case
In this section we show that there is a class of randomized auctions such that when maan- no-regret learners participate in them repeatedly, they converge to truthful bidding. This holds for any choice of the learning rates of these algorithms, which is in contrast to the results of Section 3 We start by defining a class of auctions called strictly IC.
Definition 4.1 (Strictly IC Auctions). An auction is called strictly IC if for every bidder E [m]. valuation U3 Ba, and bid profile b BR-1 it holds that U/ 22(2;, b-s) p,(ut, > 0 xz b-:) - pb,, b_.), vb + vi.
The next result, which is very useful for our derivation, states that when mean- based no-regret learning algorithms bid in some strictly IC auction they converge to bidding truthfully. Recall the definition of a mean-based learner (cf. Definition 2.2) which states that if the cumulative utility of some bid b up until round i 1 is much smaller than the utility of some other bid D', then the probability of playing b in the next round t is negligible. The proof is postponed to Appendix E
Lemma 4.2 (Convergence in Strictly IC Auctions). Consider n bidders that participate in a repeated strictly IC auction A using mean-based no-regret learning algorithms. Then, as T - co, the bidders converge to truthful bidding in a last-iterate sense.
The next important observation is that when we taking non-trivial combination of an IC auction with a strictly IC auction, the resulting auction is strictly IC. The notion of mixture we consider is formalized in Definition 4.3
Definition 4.3 (Mixture of Auctions). Let A = (z<-), p(-) be an IC auction and A' = (-)))'))) ()) be a strictly IC auction. For some q E (0, 1) we define the q-mixture of the auctions A, A' to the be auction A, (g x(.) + (1 - xz)),, g- p(-) + (1 q) p()-)).
7

---

Notice that for the allocation rule payment rule that makes the auction truthful indeed q: p(-) + (1 q) p'(-). The following claim. whose proof follows from the definition of this class of auctions, formalizes the fact that the class of strictly IC auctions is closed under mixtures with IC auctions.
Myerson's 's lemma states that the corresponding
Claim 1 (Mixture of IC and Strictly IC Auction). Let A' be an IC, strictly IC auction, respectively. Then, for any 9 E (0, 1) the auction q' A + (1 - q) - A'' is strictly IC.
We remark that we can construct strictly IC auctions using randomization; such an example is presented in Section 5 Equipped with the above results, we can show that there is a black-box transformation from any IC auction A to strictly IC auction A' so that T + 00, any mean-based learning algorithms converges to truthful bidding, and the auction A' is close to the auction A in the sense that (b) xz(6)] o(1), (p: p4(()] = o1)), vi E [n], Vb E B7. The formal statement of the result follows.
Theorem 4.4. Let A be an IC auction for n agents with valuations U1.-... Un. Let each agent i E (r] use a mean-based no-regret learning algorithm to bid in the auction. Then, there exists an auction A' such that for each agent [n] we have that limt by U2 and [I,(6) - zg(6)| =
(b:) - pb( = o(1), vb E BR where x, x,(,)(1() (resp. pt(-), pf(()) is the allocation (resp. payment) rule of A, A'.
Equilibria of Meta-Game in Repeated Strictly IC Auctions We now describe the implications that our results have for the meta-game that we alluded in Section [ Recall that this game is defined as follows: the agents submit their valuations to mean- mean-based no-regret learning algorithms and then, given these fixed valuations, they bid on the behalf of the agents in a repeated truthful auction A. The main question we are interested in understanding is given the specification of the auctions and the valuations of the agents, what is the optimal value they should submit to the algorithms in order to maximize their utility, after a large number of steps?
Despite the fact that A is IC and IR, Kolumbus and Nisan (2022a) showed that, rather surprisingly, when two agents use MWU to participate in repeated second price auctions there are instances where the agent with the low valuation has an incentive to report higher value to its algorithm than its true one. This is because the valuation reported by one agent affects the bidding distribution that the other agent will converge to. To illustrate this point, assume that the low type reports v'z >> HH to its bidding algorithm. Then, the bidder with type ey will take the role of the low bidder in the interaction and will converge to bidding strictly below UH. Now if its expected bid is also below Uz. this will generate strictly positive utility for its opponent. Using our previous construction from Theorem 4..4 and transforming the auction A to a strictly IC auction A', we can show that in the new meta- game every agent can gain at most o(1) more utility in the long run by misreporting to the algorithm than reporting its true valuation. The reason why we observe a qualitatively different behavior in our construction is that every algorithm converges to bidding its reported value, no matter what the reported values of the other agents are. Due to space constraints, we refer the interested reader to Appendix F
Revenue Maximization in the Learning Setting In this section, we illustrate another application of Theorem 4.4 to revenue maximization in the learning setting. We are interested in auctions with strong revenue guarantees when the bids are coming from the limiting distribution of the algorithms, as T - oc. This has the additional complication that not only do agents draw their valuations from the distribution F, but also their bids come from the limiting distribution that the algorithms converge to, as T + co. As we have seen already, this distribution depends on the valuation reported to the algorithm, the particular mean-based algorithm that it is using, and, potentially, the reported valuations and the algorithms of the opposing bidders.
As we explained in Section second price auctions with reserves have strictly worse revenue guarantees in the setting with learning bidders compared to the setting with rational bidders. Using our transformation described in Theorem 4.4 we can restore their revenue guarantees. The following result whose formal proof is deferred to Appendix D is, essentially, a corollary of Theorem 4.4 Let us denote by Rev Rev(A;b, b,,,.,..... ......... b,) the revenue of some auction and by Rev(Myerson: by..... b,) the revenue of Myerson's ' optimal auction for F, where the bid profile is by....,b, b, E B
Corollary 4.5. Consider an environment with n agents that draw their values i..d. from some regular distribution F and participate in repeated single-iter item auctions using mean-based no-regret learning
8

---

algorithms. Then, there is randomized auction A so that
E
lim T-000 by by by bob
E
RRe(AA; b::............ .n]] v1, u
E
Rev (Myerson, V1..... vn)] o(1).
no Fm
Given the results from Theorem 3.1 and Corollary 4.3 would like to remark the following. Remark (Randomized Auctions vs. SPA with Reserve). Our results illustrate that randomized auctions have strictly better revenue guarantees compared SPA with reserve price, when the bidders are using pean-based no-regret learning algorithms. This is property of randomized auctions that witnessed in the setting where the bidders are fully rational, as proven by Myerson (9877.
5 Revenue Maximization in the Finite Time Horizon Setting
So far, we have focused on the asymptotic regime and we have studied the convergence of the learning bidders under various auctions. In this section, we study the finit-horizon setting, where our goal is to come up with auctions that have strong revenue guarantees for the auctioneer. We focus on the prior-free setting, meaning that the auctioneer does not have any distributional knowledge about the valuation of the agents. Similarly to the rest of the paper, we assume that the two buyers are using mean-bat based no-regret learning algorithms we are working on the prior-free setting, it is natural to compete with the cumulative revenue of the second- price auction. The goal of the auctioneer to choose an auction in a way that minimizes
participate in single-item auctions for T rounds. Since
vH) Σ Rev(UZ, UH: SP) - E Σ Rev(b, byr A)
where the expectation is taken with respect to the randomness of the learning algorithms and, potentially, the auction. We will refer to this benchmark as the auctioneer regret. One quantity that will be useful for the derivation of our results the following
YA ie b1,2).,b,.b
min E.g
{(e (1,, b-:) - (, b_,)) - (v, 24 2b, - (((b.bb.)))
ie., the minimum increase in the utility by bidding truthfully instead of bidding non-truthfully in A. Our first goal understand the dependence of the auctioneer regret on the time horizon T', Then, we will move on to establishing bounds with respect to the number of discretized bids A. Our first result shows that given any strictly IC auction A there exists an auction Ar that achieves auctioneer
regret O (T V A.dr This is formalized below and the proof is postponed Appendix F
TA
Proposition 5.1. There exists auction Ar which is mixture of some strictly IC auction A and SPA such that, for all vL, UH E [0, 1)2 and for all ōr-mean-butt based learning algorithms it holds that
(egr(Ar: UL, 2H) O (V A.ór
7A T)
VUL.UH UH B3,
We emphasize that for common bean-based no-regret learning algorithms such as MWU it is the case that 87 Ô (1/VT), which implies that the auctioneer regret from Proposition 5.1 grows as Ö (TT34) Our next result complements this result by showing that even if the high-valuation bidder always bids truthfully and the www-valutiinn bidder uses MWU with learning rate O(/VT), no auction can achieve better auctioneer regret than (TT3/4).
Proposition 5.2 (Lower Bound for Constant Auction Policies). Consider a repeated auction environ- ment where the high-valuation bidder bids truthfully and the low-valuation bidder uses MWU with rate @(/VT). Then, every truthful auction Ay has an auctioneer regret Regr (Ar; UL, vH) 2 Cs T3/ where CA > 0 is some constant that depends on the discretization parameter.
The proof is postponed to Appendix F We note that choosing the learning rate of MWU to be 1 1/VT gives the optimal no-regret guarantees. Other choices, such 1/r 2(1), have trivial regret bounds.
Having established the previous results for repeated auctions where the auctions remain constant across all the iterations, it is natural to ask whether we can get improved results when the auctioneer

---

is allowed to change the underlying auction, but in a way that is oblivious to the bids that bidders have submitted so far. In other words, the auctioneer has to commit an auction schedule {AI..... Ar} before the beginning of the interaction. We extend the definition of the auctioneer regret in a natural way to allow for different auctions in every timestep and we denote RAg Ay; U2, UH)
Ei=1 Rev(vE,Wrr (P: SP) EIEi= t= Rev(bi, D/z; A+)] Our next result shows that there exists an auction schedule where the auctioneer changes the underlying auction only once throughout the interaction that its regret is bounded by Ö6 T). For typical choices of 1y this translates to an auctioneer regret bounded by Ö(VT). The main insight is that the auctioneer can split the interaction into two intervals: the first interval has size To, for some appropriately chosen To E [T], where the auctioneer uses some strictly IC auction A that encourages the learners to converge to bidding truthfully. Then, assuming that To is large enough to guarantee this convergence, the auctioneer switches to using second-price auction. This is perhaps counterintuitive because in other no-regret learning settings, such as multi-armed bandits, the optimal regret bound is achieved when exploration and exploitation are happening simultaneously, whereas in our setting these two phases are separated.
Theorem 5.3. There exists an auction schedule (A1,..., Ar) in which A = A2 ... AI, A, where A is any strictly IC auction, and ATo+1 = ATo+2 = Reg( (Ai,..., UT; vH) S 50 (0T (1 + +)) Vuz, un E B3.
Ar = SP, that achieves
The formal proof of this result is postponed to Appendix F. The previous result shows that for "r O (1/VT) the auctioneer regret of the auction schedule we designed is O(VT). Thus, we see an (44 improvement compared to the previous setting where the auctioneer was restricted to be using the same auction across all iterations.
Next, we prove that even if the auctioneer uses a different auction in every step, our bound from Theorem 5.3 (almost) optimal with respect to the time horizon T. The proof idea is that when the agents are using MWU with learning rate 7T, the signals in the first ((1/tr) steps are insufficient for them to move their bidding distribution to truthful bids. Le., with at least some constant probability in every round within the first (1/mr) rounds, they will not be bidding their true valuation. Importantly, our lower bound holds even in the (unrealistic) setting where the auctioneer conditioned on UL UH This is formalized below; the proof is postponed to Appendix F
choose A1 A1...., Ar,
Proposition 5.4. When in repeated single-item auctions for all the auction schedules ATT it holds that Reg(AI...... Ar; UL, vH) = Q(VT).
agents are using MWU with learning rate 1/VT to participate
Having established the optimal dependence with respect to the time horizon T, we now shift our attention to understanding the dependence of the auctioneer regret on the discretization parameter A. First, we define auction A that satisfies 7A= = O(122))
Definition 5.5 (Staircase Auction). We define the allocation rule of auction À in the following way: with probability 1/2 select a bidder i E {1, 2] independently of their bids and then allocate to with probubility b; We define the payment rule in the way that makes the auction truthful.
simple application of Myerson's 's lemma shows that A = O(%a²). This is because between any two consecutive bids, i.c., bids whose distance is 1/4, the increase in the allocation is 1/2a and the function is linear. A corollary of Theorem (5.3 shows the following bound in the auctioneer regret.
Corollary 5.6. Let the bidders use a mean- mean-based learner with π7 = Ō( Õ(y a/T) and the auctioneer use the schedule (Ai...., AT) with A = =... AT, = A, ATo+1 = ATo+2 =... = -Ar = SPA, for To ō (vT/2²). Then, Reg(A1,.. ArjuL, S Ō (2VT)) VUL, UH E B3.
6 Conclusion
Our work studies the behavior of learning bidders in repeated single-item auctions, with persistent valuations. We show the limitations of deterministic mechanisms, and how nuances such as learning rates can qualitatively affect participant behavior. Moreover, we show that randomized auctions can encourage faster convergence of bidders to truthful behavior. We hope our work paves the way to better understanding of learning agents' behavior single-parameter environments, and of the power of randomization.
10

---

Acknowledgements
Anupam Gupta is supported in part by NSF grants CCF-1955785 and CCF-2006953. Grigoris Velegkas is supported in part by the Al Institute for Learning-Enable Optimization at Scale (TILOS).
References
John Asker, Chaim Fershtman, and Ariel Pakes. 2021. Artificial intelligence and pricing: The impact of algorithm design. Technical Report. National Bureau of Economic Research.
John Asker, Chaim Fershtman, and Ariel Pakes. 2022a. The Impact Al Design on Pricing. Technical Report. Working Paper.
John Asker, Chaim Fershtman, Ariel Pakes, al. 2022b. Artificial intelligence, algorithm design and pricing. In AEA Papers and Proceedings, Vol. 112. American Economic Association, 452-56.
Martino Banchio and Andrzej Skrzypacz. 2022. Artificial intelligence and auction design. In Proceedings of the 23rd ACM Conference on Economics and Computation. 30-31.
Quentin Bertrand, Juan Duque, Emilio Calvano, and Gauthier Gidel. 2023. Q-learners Can Provably Collude in the Iterated Prisoner's Dilemma. arXiv:2312.08453 [cs.GT]
Mark Braverman, Jieming Mao, Jon Schneider, and Matt Weinberg. 2018. Selling to no-regret buyer. In Proceedings of the 2018 ACM Conference Economics and Computation. 523-538.
Linda Cai, S Matthew Weinberg, Evan Wildenhain, and Shirley Zhang. 2023. Selling to Multiple
No-Regret Buyers. arXiv preprint arXiv:2307.04/75 (2023).
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. 2022a. Accelerated algorithms for mono- tone inclusions and constrained nonconvex-noncoocaav min-max optimization. arXiv preprint 052:222006002248 (2022).
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. 2022b. Finite-time last-iterate convergence for learning in multi-player games. Advances Neural Information Processing Systems 35 (2022), 33904-3399 33919.
Yang Cai and Weiqiang Zheng. 2022. Accelerated single-call methods for constrained min-max optimization. arXiv preprint arXiv:2210.03096 (2022).
Emilio Calvano, Giacomo Calzolari, Vincenzo Denicolò, Joseph E Harrington Jr, and Sergio Pas- torello. 2020. Protecting consumers from collusive prices due to AL. Science 370, 6520 (2020), 1040-1042.
Arnoud den Boer, Janusz M Meylahn, and Maarten Pieter Schinkel. 2022. Artificial collusion: Examining supracompetitive pricing by Q-leaming algorithms. Amsterdam Law School Research Paper 2022-25 (2022).
Xiaotie Deng, Xinyan Hu, Tao Lin, and Weiqiang Zheng. 2022. Nash convergence of mean-based learning algorithms in first price auctions. In Proceedings of the ACM Web Conference 2022. 141-150.
Andréa Epivent and Xavier Lambin. 2022. On Algorithmic Collusion and Reward-Punishment Schemes. Available at SSRN 4227229 (2022).
Zhe Feng, Guru Guruganesh, Christopher Liaw, Aranyak Mchta, and Abhishek Sethi. 2021. Conver- gence analysis of no-regret bidding algorithms in repeated auctions. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 5399-5406.
Guru Guruganesh, Aranyak Mehta, Di Wang, and Kangning Wang. 2022. Prior-Independent Auctions for Heterogeneous Bidders. arXiv preprint arXiv:2207.09422 (2022).
Sergiu Hart and Andreu Mas-Colell. 2000. A simple adaptive procedure leading to correlated cquilibrium. Econometrica 68, 5 (2000), 1127-1150.

---

Yoav Kolumbus and Noam Nisan. 2022a. Auctions between regret- meneetiinniizznng agents. In Proceedings of the ACM Web Conference 2022. 100-111.
Yoav Kolumbus and Noam Nisan. 2022b. How and why to manipulate your own agent: On the incentives of users of learning agents, Advances in Neural Information Processing Systems 35 (2022), 28080-28088
Christopher Liaw, Aranyak Mehta, and Andres Perlroth. 2023. Efficiency of Non-Truthful Auctions in Auto-bidding: The Power of Randomization. In Proceedings of the ACM Web Conference 2023. 3561-3571.
Aranyak Mehta. 2022. Auction design in an auto-bidding setting: Randomization improves efficiency beyond veg. Proceedings of the ACM Web Conference 2022. 173-181.
Roger Myerson. 1981. Optimal auction design. Mathematics of operations research 6, (1981), 58-73.
Denis Nekipelov, Vasilis Syrgkanis, and Eva Tardos. 2015. Econometrics for learning agents. In Proceedings of the sixteenth acm conference on economics and computation. 1-18.
Pranjal Rawat. 2023. Designing Auctions when Algorithms Learn to Bid: The critical role Payment Rules. arXiv preprint arXiv:2306.00433 09437 (2023).
Tim Roughgarden. 2010. Algorithmic game theory. Commun. ACM 53, (2010), 78-86.
Vasiliki Skreta. 2006. Mechanism design for arbitrary type spaces. Economics Letters 91, (2006).
293-299. https:://oi..rr
1016 e.con..econ let 2005.12.005
Brian Hu Zhang, Gabriele Farina, Ioannis Anagnostides, Federico Cacciamani, Stephen Marcus McAleer, Andreas Alexander Haupt, Andrea Celli, Nicola Gatti, Vincent Conitzer, and Tuo- mas Sandholm. 2023. Steering No-Regret Learners Optimal Equilibria. arXiv preprint arXiv:2306.05221 (2023).
12

---

A Multtppiiaative Weights Update (MWU)
In this section we describe the version of MWU we consider in this work. Similar to Braverman et al. 2018), we are using the following version of the algorithm.
ALGORITHM 1: Multiplicative Weights Update Algorithm.
1: Choose 1/r = V log Initialize weights, letting of be the value of the ith weight at round
Initially, set ur = 1, let e be the valuation of the agent.
2: for f. = 1 to 7 do
3: Choose bid b, with probability pt =w; - E3 w3
12,
4: for
K do
5: Let u/ = v u- (bj, b) - -p'--pppe pb)b,
6: Set w = / enruj
7: end for
8: end for
B Further Related Work
We view our results and the setting in which we work as orthogonal to the setting Cai et al. (2023). Firstly, they do not restrict themselves truthful auctions, and for their welfare extraction results, the agents are allowed to overbid. Secondly, in their setting, redrawing valuations i.i.d. in every round helps the learning process (this also observed by |Feng et al. (202T)). Intuitively, consider two agents and SPA: for every valuation of player 1, there is some positive probability that player 2's draw below it, hence player 1 will learn that bidding truthfully is strictly better (in expectation over the other random draw), which leads to the desired bidding behavior. In such a system, randomness is already present due the draws of the valuations, which helps the convergence to the right bidding behavior.
Our work also differs from Cai et al. (2023) in having different conceptual goals: we aim "restore" the single-shot behavior in natural auctions, such as second-price auctions, the presence of mean- based learning agents by making minimal modifications to the underlying auction rule. On the other hand, Cai et al. 2023) aim to exploit the mean- based learning behavior to extract more revenue, and their auctions diverge from the truthful ones consider in our work. Thus, in setting, it is clear that reporting the valuation truthfully to the bidding algorithm an (almost) optimal strategy for the agents (i.e., the so-called "meta-game" considered by Kolumbus and Nisan (2022a) is truthful), whereas is not clear to us whether reporting the valuations truthfully to the no-regret algorithms is an optimal strategy in the setting Cai al. (023)
C Omitted Details from Section 2
Skreta 2006) shows that our discrete-type space mechanism design problem approximates the mechanism design problem with continuous type space as A oo: specifically. Proposition from that paper gives the following claims.
Claim 2. mechanism is truthful if and only for every u_s x. (vi, w-z) non-decreasing on e; and pa satisfy that
pelu,, v-)) - (1,2a(00, u-.) -f." "1,(2
O(1/A).
Claim 3. Suppose bidders rational agents (i.e., they maximize profits). Let OPT be the revenue of the erveue-maximiaa mechanism (among truthful or non-truthful) that the auctioneer can implement, and Rev(r SPA) be the revenue of a Second Price Auction with reserve r. Then for r r= min(u ((u) Z 0}. we have that OPT Rev(r SPAA..
Definition C.1 (No-Regret Learning Property). Let {bī Teet) be the bid sequence submitted by agent i's algorithm, and U. (b?)- ΣT= vs x (6) b_,) p (b7 b_,) the total reward agent i
13

---

receives. We say that this algorithm satisfies the no-regret property if any sequence b", it holds that
E max Uf (b (b =o(),
BEBa
where the expectation taken with respect the randomness of the algorithm.
Definition C.2 (Last Iterate Convergence (LIC)), Let by the bid distribution of bidder i in the last round T. We say that by converges to some distribution q over Ba io drv(0; = = where drv == 2 [EEEB 16! (b) - ((b)l) is the Total- Variation (TV) distance between b." and q.
D Omitted Details from Section 3
Definition D.1 "Non-Degenerate auctions). A single-iten auction (x.P) for two agents is non- degenerate with respect to the valuation profile (v1, 02) if there are bid profiles bj S U1, b2 S U2 so that
11 b2) P1(11, b2) > u1 21 (11 1/2, b2) - p1 b2) 2
U2 x2(bb,,, v2) P2(b1, 02) > U2 x2((1, 1/2) P2(b1, 1/2) 0,
and
max (U1 2n (v1, 02) pı (vi, v2), 12 (2 v2) P2(11, 22)) >
In order to show our result, we utilize a characterization (cf. Theorem D.2 regarding the structure of truthful deterministic single-item auctions that charge non-ne non-negative payments (see, e.g., Roughgarder (2010) Thm 9.36)) for bidders.
Theorem D.2 (Characterization of Truthful Deterministic Single-Item Auctions Roughgarden (2010).
A single-iten item auction is truthful, and satisfies NPT, i.e., payment transfers from the auctioneer to the bidders, if and only if:
z,(; U-1) is monotone for every E [n], v-4 B
For all i E [m], E BA, BB-1 we have that
10. (( (min(be E BA (b,(
fF,, u-1)= = 2z u-s) =
Theorem D.3 (No Deterministic Auction Leads to Truthful Bidding). Fix valuation profile (V1, U2) and a deterministic truthful auction. Suppose bidders bid using MWU and with non-degenerate learning rates. Let W (respectively R), be the bidder
[1,2] such that x,,(i,, U= :) = (re- pw (UW, UR). Assune that lim "//oW < and
spectively, z,(V1, v-1) 0) and let
Uw - -Iw -Iw(UW: Un) P > 0. Then, with probability at least 0.99, the winner's bids converge to distribution supported between P. uw and the runner-up bidder converges to a bidding distribution satisfying < PP < Pr(1/A] s... <..
Proof of Theorem D.3 The idea of the proof is to split the horizon T into continuous non-overlapping epochs of length e/ c/n² where e is some sufficiently large constant that depends on the discretization parameter A. Notice that since lim nit = oc these epochs are well-defined, when T is sufficiently large. Assume without loss of generality that the weights of all the bids that at most ow (resp. un) for the winning bidder (resp. runner-up) are initialized to 1. (The proof holds as long there is some constant mass on each bid at the initialization stage, albeit with different constants.) We denote the epochs by - and the rounds of the interaction by l.
Let cw = "w be the utility the bidder gets when it wins the auction. By assumption, ew > 0. Let Ww be the set of bids between P and ow, i.c. Ww = {p. 1/a.... )w.). Whenever the runner-up bids all the bids in Ww increase their weights by multiplicative factor of ww whereas the weights of the other bids remain unchanged. Moreover, since the allocation rule non-decreasing and the price does not depend on the bid, whenever the weight of some bid b E Ba is increased, the weights of all the bids that are greater than are also increased by the same amount. Notice that, since bidding UR is weakly-doming strategy for the runner-up type, the mass that it
14

---

puts on un will never decrease relatively to the mass of the rest of the bids. Thus, the probability of bidding on for the runner-up type is at least 1/A in every round. Hence, if we consider an interval of size To 84 / W cw) and we denote by Z i E [To]: the indicator variable of whether the runner-up bid un round E [To) we have that for any a > 0
Pr [1 +...+ + Zro 2 al 2 Pr 2 ..... Zr, 2 a
where 2, E [To] are i..dd Bernoulli random variables with mean 1/4. Then, the multiplicative version of Chernoff bound on {2, shows that, with probability at least e e-A/e- -ow) the runner-up type will bid at least 4A/(1/ (w)) many times en in this window. By a union bound, we know that with probability at least - (T' (7' /c) e- A/(0f sew) this holds across all the T Tny W /c different epochs. We call this event &, and condition on it for the rest of the proof. Our assumption that 1/r is non-degenerate shows that this probability is at least - o(1)
1V/
Let why (6) be the total weight that the winning type assigns to b the beginning of epoch 7 and miy (b) be its probability. Notice that at T = 1 this distribution is uniform. Consider the ratio of the weights of any b p 1/4 and p. We have that
ww (b)
(b)
Wi (b) " (p)
Why (b) wi (p)
e- -low-Amm /ow-n m
e 14
(1)
w W (p)
where why (b), Ty (f) are the weights that the winner puts on b.u at the beginning of epoch
(similarly for the + terms). For the probability of each bid in MWU, m ++1 (b) Evee ww (b')
why (b)
(and symmetrically for the other terms). Thus, by dividing the numerator and the denominator of
the RHS of Equation [ by EVEBA (b" and the numerator and denominator of the LHS of Equation
! by EvEBA wir (6') we get:
++1(6) m (b)
mW (b) m. (p)
<
1A
nw (p)
Multiplying by m (p) gives us
m (b)
W
my (b) -4
m (p)
Notice that (p) = 1/A, iy (p) is non-decreasing in t since bidding f is a weakly-dominant strategy for the winning type and, by definition, mH
r+1 (p) S 1, so mjy (F) mn (P)
S A. Hence,
mw (b) Ae 4A
++1 (b) < 0.1 miy (b), pb
my
where the second inequality follows from re xe-4- 42 < 1, Vz > 0. Thus, after each epoch the probability
that the winning type does not bid in Ww decreases by a factor of 0.9. Hence, we can see that after
On W. 7) epochs that total mass in this region is at most (0. W. -T-1) = o(1). This proves the claim about the distribution of the winning type.
Let Z,, i E [T], be the random variable that indicates whether uw bid in (0, 1/4 ... 1 1/2} in round i E [T]) Let also T" denote the total number of epochs. Let 2, = 7, + ....+++ +
- so that E|Z1 +.. Zr] = ΣT" E _[ The preceding steps of the proof had shown that after every round, the probability that the winner bids in this region is non- non-inereasing (since the bids in interval I are
weakly dominated by the bids in (p...., uw }), hence B[2,] < To E(Z(r-1)/6+t) Thus, it suffices to bound DT" r-1 E( E(Z(r-1)-T++1)-
By definition, ((Z(T-1)-T+ = Eocr mw shown that the mass of each bid in interval I drops by a factor of 0.9 between the beginning of
(1-1)-To+1 (b). Now, the previous step of the proof had
"his is where we are using the assumption that the runner-up type does not overbid. Otherwise, the argument can still go through with different constant since we can show that the winning type will overbid only some O W many times and we need account for this term.
15

---

(--1)-To+1 (b) for all E 10,1/A.... ........ ... 1}. This consecutive epochs, i.e., mi mw/ (b) S 0.1 m
implies T6 S 0.1 B[2 (1 Using E[Zi] s 1, we get E (I s
Σ (0.1)=-1. Multiplying this by the value of To gives
T'
E 11 + ................................ + 4T| -
(8A
/1/ 1 ow)) (0.1)--1
T=1
0c
(8A²
/1/ -ww) (0.1)--1
16A2 / .w).
Hence, using Markov's inequality we see that Pr [1 ... + ZT 101 (162²/ cw))] 5
E [Z + +...Zy ...
1 101
101 . (16A² //1 cw)
Let us call this event Eg and condition on it.
Let us now consider the bid distribution of the runner-up type after the end of the last epoch. We denote this distribution by (.) Recall that whenever the winning type bids in Ww, the runner-up type performs no updates. Moreover, whenever it does perform an update its utility when it bids most greater than bidding b O. Notice that whenever the weight of some bid is increased, the weights of all the bids greater than b are also increased by the same amount, so the monotonicity of the bid distribution follows immediately. It suffices now to bound the ratio of the probability of bidding zero and the probability of bidding uR by some quantity that is independent of T. We have that
T/. 1r/101-(1u) (1600-(1622//)) /60 sww)
MR (0)
2 e 1nf1000 (164>/(nf =ww) = ( 2
mn((n)
A
where the second inequality follows from the fact that the distribution is initialized to be uniform and on is weakly-dominatt strategy across all rounds, so its probability is not decreased. Notice that
lim w//oW < C T-200
for some discretizzaiion-deeedde C, follows that (0) > C², where C' > is some discretivaaiionddeeeneeet constant. Since Pr[&] 2 1 o(1), Pr( 2 100/101, we have that Pr(E1 & Z 99/100, when T is large enough.
Theorem D.4 (Effect of Learning Rate on Convergence). Fix a valuation profile (vi, v2) and non-degenerate deterministic truthful auction with respect to (u1,02). Suppose bidders bid using MWU and with non-degenerate leurning rates. Let W (respectively R), be the bidder E {1,2) such that z 2.(V,, v-1) 1 (respectively, 24(2), v_i) 0). Let P be the minimum winning bid of W when R bids un Assume that nf /nix" w1). Then, with probability at least 1 - o(1), bidder R converges to bidding Un and bidder W converges bidding distribution supported {p.6 1/a,..., uw).
Proof of Theorem D.4 Consider the first To /2/n/W' rounds of the game, for some d's disscetizaaiinnddpendde
constant. Assume without loss of generality that the weights of all the bids that are at most uw (resp. UR) for the winning bidder (resp. runner-up) are initialized 1. (Again, the argument works so long as all the weights are initialized with some constants.) Since the auction non-degenerate with respect to uw, there exists some bid of the winning type bw I ow so that the runner-up bidder wins the auction when bidding truthfully and gets positive utility, i.e.
un In(UR; bw) - pn(un, bw) > 0.
Moreover, for all bids bR < UR holds
UR IR(UR, bw) (R(UR, bw) - (DR ZR(bR, bw) ) PR(bR, bw)) > 0. Since the auction is truthful, the difference above is minimized b Un 1/a. Let u'R := UR IR(UR bw) PR(UR, bw) (UR ZR(UR 1/2, bw) PR(UR ( 1/4, bw))
16

---

and, by definition, u'R > O. Let us consider the winning type and look at the worst-case ratio of the probability that placed on bids by bw. biw uw the end of every round t {l..... To)- We have that
Pr(bi bw Pr(bf ow!
Mi -ew-t
2 mi -ww
=e ww
where the first inequality follows from the fact that bidding ow always yields most tw utility more than bidding any other bid and the second one because To. Moreover, since Pr(by = ow] = 1/A and the probability that is placed on biy uw is non-decreasing across the executions (since is a weakly-dominant strategy), we have that
Pr[py = bwl 2 e A ow / (1.....
Let 7 denote the random variable that counts the number of times the winning type bids bw within the first To rounds. Let Z,,7 [To] be independent Bernoulli random variables with mean e- /A. Notice that, Ya 0, it holds that Pr[ZTo a) 2 Pr 2, 2 a.. Moreover,
To
E
Zr
2 To <s.ow /A = Ca/1FT e VW IA.
To simplify the notation, let us denote مة ds - 2H /A. Thus, multiplicative Chernoff bound shows that, with probability at least 1 1 R /Bn) ) = - =1)( we have that To 2 /2/(2 )
Let us call this event E and condition on it.
Let us now focus on the bid distribution of the runner-up bidder after the first To rounds. Notice that whenever the winning bidder bids bw then bidding UR yields utility at least u'n greater than bidding any other bid to the runner-up type, and in the rounds where this does not happen, bidding UR is still weakly dominant strategy so it generates as much utility as any other bid. Thus, we have that
To Priba
UR 1/A]
"e " 20
Prip To = URl
S E 13 2/20 A)
o(1)
Thus, since bidding uR a weakly dominant strategy for the runner-up this ratio non-increasing in t we can immediately see that
Prib To =n - 1/A o(1),
Pr(p/ = vn)
which gives that
Pr OR - 1/A] o
The same argument can be applied to all bids in 1/ UR 1/A].
For the winning type, symmetric argument shows that since after 0 many rounds the runner-up type bids Ua with high probability, all the bids in the region (#w..... tw } will yield utility that is larger than bidding vą 1/A by at least 1 A (again with high probability). so after another w ( W rounds its mass will be concentrated on bidding in this region.
Proof of Theorem 3.7 Let E fr v1 n fr < 02) n for * U2). We can decompose
E Uu Rev(11, 02; r)] as:
Rev(vi, (25)))
E
Rev (ev( 12;r)) E]
Pr [8]
"
E U
Rev(E1, (23)))8)))
Pr
[E']
17

---

Notice that under E", the revenue of the auction in the learning setting satisfies
lim BBBBA T-000
(Rev(bi,b2;1) 01, U2] bpurb .b2
E 01.00rU[[Ba]
(Re 12;r) 87
This is because both bidders will be bidding at most their valuation, so the revenue of the auction cannot increase. Let under rational agents is min(rr U2 > r. However, in the learning setting, the runner-up bidder will be bidding strictly below their valuation in expectation, by Theorem D.3
focus the first term. Under the event &, the revenue of the auction
Hence, we have that
E v1 01,02~~U [Ba]
lim
E
Rev b2sr) 01, U2)
<
E vn 1000020000 [Ba]
min 111 22) 3 - d
T-00 by bT by
E 11,02~U[Pal
Rev(UI, U2: r) d'
Since Pr(E]
0, the result follows by combining the two inequalities.
E
Omitted Details from Section
Proof of Lemma
4.2 Let
7
min
(ui(v,bs)) u,(b, b-:))
BE "e
i.e. the minimum improvement in the utility that is guaranteed to every player when they switch to bidding truthfully from any non-truthful bid, no matter what their valuation and the bids of the opponents are. Notice that for any fixed auction A this quantity does not depend on T. Moreover, since A is strictly IC auction we have that TA > For any player E [n)] we have that
O. Consider any round E [7] of the interaction.
u' (or, n (b/ bL) 2 YA, VD' tv, vs
no matter what the bids b_ are. Let de. 8n be the mean-based parameters of the algorithms that the agents are using. Moreover, let To maxigl]] 8; T//AA Notice that since 6; = o[1), Vi E [n], by picking T sufficiently large we have that To < T. We immediately get that, for every player i [n]
Σ
2 7A To 2 8; T, AR 40.
matter what the bid profile bi_, of the other bidders in every round is. Thus, for every bidder i E [n), by taking a union bound over all bids F U,, we see that in round To + the probability of not bidding truthfully is at most A 6; o(1). Hence, we have shown the result.
Let 6, be the mean-based parameters of the algorithms that the agents are using. Recall that these parameters do depend on T. Assume without loss of generality that d1 is the slowest one, i.e., lim 61/8, I C, Vi E [n], where C' is some discretizatioon-deeedeen constant. Let À be strictly IC auction and define
Proof of Theorem 4.4
min a BEIn).EBB.A...BBB ".EBA:bo [ū,(v, (() - Tz(bbb.)))
Similarly as in the previous proof, notice that ア does not depend on T. Consider the mi-mixtere of the auctions A, A and let us denote this auction by A'. Let x, J, x' be the allocation rules of A, A, A', respectively, and let us define the payment rules in a symmetric way. Notice that since z'(+) = (-) (1 or (r)xx()),p'() 9Tr(-) (1 - qT )(-). it follows immediately that
7A' 2 qr VA
Moreover, notice that
(x(()) - x(-) S or [5(-) x(+) S gr
pp(()) (()) < (0-) p(:) S gr.
18

---

Let us focus on agent 1 since it is the one that has the slowest convergence. After To rounds of the game we have that
To Σ (( (b TA' To2 QT 7 To AR' U1
no matter what the bid profile the rest of the bidders in every round is. Thus, in order for the mean-based guarantee of the algorithm of the first bidder to give the desired convergence that we need To 2 61-T/97-75- Since To < T, this places a constraint on the choice of qr, namely that 9T 61/72- Thus, since this is the only constraint that we have on the choice of qr we that choosing 9r 261/73 = o(1) suffices to get the result.
see
Let A'' be the output of Theorem 4.4 when the input auction Myerson's oevemue-optimal auction for F. For any fixed valuation profile v E B for sufficiently large T, each bidder [n] will be bidding e except with probability o(1). Moreover, the payments in these two auctions differ by some o(1). Thus,
Proof of Corollary 4.3
lim 7
bm)) 2 Rev Rey(Myerson; 01, eI,..., un) o(1)
01 b1 p...
The result follows by taking the expectation over the random draw of u1,...; Un-
We present the formal result about the equilibria of the meta-game below.
Corollary E.1 (Equilibria of Meta-Game). Let A be an IC, IR auction. Let be the number of interactions. Assume that n agents mean-based no-regret learning algorithms to bid in these repeated auctions. Then, there is an auction A' such that
(x:(b) z((b) o (pbb) ==()) o(1), [n], Vb B".
In the meta- meta-game that is induced by A' every agent can gain at most o(1) utility by misre- porting its value to the bidding algorithm.
Proof of Corollary E.1 the bidding algorithms. Let A' be auction obtained by feeding the auction A into the transformation described in Theorem
Let 2i.....,,, Un be the values of the agents and let é1, ...... o be the reports to
4.4
The guarantees of this result show that
x (b) - x((6) o(1,, (b) p4(1) o (m BA.
Pr[b. + o,] = o(1), Vi [n).
where 67 is the bid of the i-th agent in round T. Thus, with high probability after large enough number of rounds, for every agent E [ni the algorithm is bidding the reported value i; no matter what the other reports ê-q are. Since the auction A' is truthful, the utility of each agent maximized when bf = v. Hence, the optimal strategy, up to o(1), is to report = úz vi E [n.]. To be more formal, the expected utility of the i-th agent in round T is
E [6 bE,]] = (f,, θ_.) o(1),
thus, since A' is truthful, this quantity is maximized for é Us up to the o(1) term.
Omitted Details from Section
Proof of Proposition Let Ar Pr A+ (1+ Pr) SPA, where A is some auction with 74 and some pr that will be defined shortly. Notice that
AAr 2 PT 7A + (1 PT) 7SPA 2 PT : 7A Since the bidders are mean-based no-regret learners, we know that when
To
To Σ
uy xe (vi, br) pe(us, by) N
ve (b p:(U,, + 8 T,W (0,1), e Ba.
19

---

they will be bidding truthfully with probability at least 1 1 A my. We know that in every round
2/ -. b,) - pi(u;, 2 us I.((',,,) p:(bb' b,) + YAr
2 . ,,, ) p:((',,,) b-) + pr 74. Vi (0,1), 8' B2, D' +
Thus, we define To = min(t E N; : PT YA t 2 bT - T = . 8ppr/ The regret is
Regr(Ari UZ, Ur, vH) Regty (ATi UL, UH) + Σ Rev(U,,
E
Σ
Rev(bi, bsgi A)
LI=To+1
S U1 To +1, (T To) (2A 57) (1 - pT) + (T To) pr Ur
x uz (To + 2A br T. pT) T pr)
8T + 8τ T + PT T
S uz
pr YAA
22A öT
T + pT .T)
'TA
where the first inequality follows from the fact that after the first To rounds the auctioneer regret is bounded the sum of the probabilities that the auction is SPA and the bidders do not bid truthfully, which is at most (1 - p) 2A ./T, and the probability that auction is not SPA, which is pr. The rest of the incqualities are just algebraic manipulations. Thus, by setting pr /2A-61/7A we get that
2A δr T
Reg, (AT; UL vH) S oz 3
YA
which concludes the proof.
Proof of Proposition 5.2 Consider the UL, un pairs of the form UH = or + 1/2, such that both
are bounded away from 0 and 1. Then, Myerson's 's payment formula shows that py (UH,,, (UH, S
(UH 1/2)- IH (UH, vz) = UL HH (UH, UL). We first argue that æ (UH, Uz. < 1. Indeed, suppose that (UH, v = Then the low type gets no signal about their bid and hence bids uniformly at random between [0, wz]- In particular, with some C' probability that is independent of the low type bids the value by = 22/ Now the only way for the auction Ar to generate (vy - o()) revenue from such rounds is if Zy (UH, 22/2) - zz (UL, 22) = 1 1 o(1). But if this is the case, then consider the valuation pair (2r./2, / 1/a): the auctioneer allocates at most 5 (vr,/2 ////, /2,/2) S o(1) per round, and gets almost no revenue from the high type. Moreover, the low type will generate at most nr./2 revenue, so the the regret of the auctioneer at linear in T; this gives the desired contradiction.
Since HH (UH, UL) < 1, g 1 (HH, UL). Then, Hy (UL, uH) S q and so (UL, UH) uz (Uz, - 1/4, < q 1/4 S q. In order to cancel the effect of the learning rate of T/,, we need to wait for To ((1)(o-))) rounds. For some C² fraction of these Tú rounds the agent of low type will bid 22/ and an argument similar the previous paragraph shows that the revenue of the auction will be least 1/A- ( o(1) less than Vz. Thus, the regret in these To rounds will be (TT,), where we are hiding constants depending on A. Let us assume that after To rounds the low type starts bidding truthfully. Then, the total regret in this period due to allocation of the item to the low type is Ω ((T - To) 7). Summing up the two terms we get a regret of Q (1/(rr)) + q -- 1/vr). Since MT 0(I/VT), this is R(VT/Q(T// + qI' VT), which for any choice of g is 8 (T9/4).
Proof of Theorem 3.3 We will upper bound the auctioneer regret in the two epochs (1...., To), and (To + 1, shortly. For the first epoch, we will use the simple upper bound of 7y To.
separately, where Tu E [T] is parameter of the design which we will define
Let us consider the bid distribution of the two bidders after To rounds. Since they are mean-based no-regret learners we know that if
To
To
uy xe (, br) - p((us, by) 2
Σ
(,b,bbb) pi + 8T T,ViE (1,2), W E Ba.
20

---

then, by union bound over the possible bids, they will both be bidding truthfully with probability at least 1 2A Trr.
We know that in every round 7 E [To] we have that
04 (y b,) - pi(1's b4) 2 Us ,,(,', b,) 7 ViE Vi (0,1),,, E BB uu.
Therefore, we set To minst N. 7A 1 8τ r} 67..//A. Thus, we can upper bound the cumulative auctioneer regret by
Reg(A, A, A,SPA SPA; S 31
To V (T)))).22 "r
bT T
S U1
+
T
22 1/
YA
= = = OT-
(-+ TA ++41 ++)
where the first inequality follows from the fact that with probability at most 2A yr one of the two bidders will not be truthful in the last (T - TT) rounds, and the other inequalities are just algebraic manipulations.
Proof of Proposition 3.4 It is not hard to that in the setting are working the auctioneer cannot have negative auctioneer regret in any interval of the interaction. For instance, when en = Vr. 1/A, the SPA performs optimally. Since every Ar, E (T], is truthful auction, Myerson's lemma shows that
U
(e; b,))-
bd 16' bb. Vi (1,2), Vu, E B3,
so for 1/ = =1 - 1/A we get that
u(( -
A Vei, V,,, E BA.
Thus, in every iteration the utility gain of bidding o most 1/4 greater than bidding is 1/A. Summing up over the first To iterations, we get that
To
To (ul(vr,b.)) - - 1/4,b..)
Vu, Vu, b,, E B²
A
Let us now shift our attention to the weights that MWU puts os 1/4, vx, after To iterations. We have
Pr To v. Pr b To = U2 1/A
Th (1toe. 110..,--111100 1/A,(L.)
S T T
so for To = A/er we have that
Pr LT Us]
Pr = 1/4|
This immediately implies that
Pr = 1/1/ > Pr u.] Vt E [Tol.
Thus, the probability of bidding truthfully of both algorithms is bounded by 9/10. Thus, when = 7y + 1/A when both bidders are not bidding truthfully the revenue loss compared to SPA least 1/2. Putting it together, we can see that within the first To rounds the total revenue loss
compared to SPA is at least C. 1/a To = 1T C. vT, for some absolute constant > 0. O
Next, we show that the auction defined in Definition 5.5 IS optimal, in terms of its parameter YA.
21

---

Lemma F.1. In the setting with two bidders it holds that the optimal choice of the parameter is (1/2)) Moreover, the auction defined in Definition 5.3 achieves that bound.
Proof of Lemmal F.I Consider some auction A and fix the bid of the second bidder to be H' E Ba- Then, xi ((,8)) is a non-decreasing function, with S z (6, b) - 1, Vb Ba. Notice that for any consecutive bids, Myerson's 's lemma shows that
"1 (6,66') - in (6 - 1/4, & 1/4 (II(b, x (b - 21(b-1/A,b)) 1/4,b'))
Since there are 1/A different b Ba and the function x (. is monotone and bounded between [0, we have
Σ (b. 21 1 1/2,8') =1 21(0)'') 0
1
and since there are 1/4 terms in the summation, all of which are non-negative at least one of them must be at most 1/2. Let bj B3 be such that x(bi,6') x(b' 1/4, 6') I 1 Then, picking 21 bj witnesses that YA I A
G Extensions
In this section we discuss potential extensions of our model and adaptations of our results.
Extension to partial feedback setting. Our results can be adapted to the partial feedback setting, with different quantitative bounds. In particular, there are mean-ban based no-regret algorithms such as EXP3 (Braverman et al. 2018) with yr = ÖTT/44). Notice that our positive results are stated for mean-based learners, so the guarantees hold in this setting well.
Extension to multiple bidders. We underline that our results in Section 4 are already stated and proven for multiple bidders. For our upper bounds in Section [ there is I/n degradation to the auctioneer regret bound. When we are dealing with n bidders we can create a strictly IC auction by building upon our "staircase auction" approach for two bidders in the following way: we select some bidder i E [n] uniformly at random (independently of their bids) and then we allocate to bidder with probability b, Thus, for each bidder E [n]] their allocation probability (b) is a linear function with I, (0) = 0, x, (1) = 1/n. Hence, Myerson's 's lemma shows that uy (1;
= ((1((nA)), thus, 74 ( / (n Recall that in the two-bidder case have shown that this auction gives 74 ( ) so the degradation in 7A by 1/n leads to a degradation of the same factor in the auctioneer regret compared to the two-bidder setting.
Extension of regret bounds to the distributional setting. In Section 5 we consider a setting where the auctioneer does not have any distributional knowledge about the valuation of the bidders. Notice that our lower bounds are witnessed by valuation pairs of the low type, high type, of the form VL 1, HH + 1/A. Let us now consider distributional setting where U1, U2 are drawn from distributions D,, D2. and then the two bidders participate in repeated second-price auctions using MWU parametrized by these valuations. Similarly in the prior-free setting, the goal of the auction- cer is to have small expected regret, where the expectation is over the random draw of the valuations and the random behavior of MWU. Notice that the cumulative revenue of SPA when the bidders are truthful is T ED,,D ~D, D. DD,,,, [min 21, 22 so this is the benchmark the auctioneer competes with (in this setting, we can modify the benchmark be SPA with personalized reserves with the same arguments). If these distributions D,, D2, place some constant probability (i.e., independent of T) on every element of {0, 1/ 2/4, /....... 1) then with some constant probability we will see draw of the form Vy. = UH = e 1/2, so these pairs will be contributing a constant fraction of the expected revenue of the second-price auction, i.e., the term Eu Dr... [min miin(1) (V1, 22)). Thus, if the auctioneer wants to have expected regret most O ((Rr). they need to have regret most O ((T)) for all such valuation pairs, where in the notation O()) we are suppressing all the parameters that do not depend on T.
22

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The main body and appendix of the submission provide proofs for all the claims.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We formally define the mathematical model our results hold for.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
23

---

Justification:
We present full proofs in the main body and the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
24

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips...
public gui Codeeuumie ss ooiioooolliieoo icy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips. cc/ wwwplillluiicooooooooooo / //ooiddeee/eeeeeeeee Cooeeeooeeeeeeee CoodeSummeeeee Submiss ww.biissionPoolt cissPooiccyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
25

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The work is primarily theoretical and does not have any immediate societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
26

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paper thcode com datasetttttt has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
27

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "ryrGle4Bdo", "reviewer": "Reviewer_rdXf", "summary": "This work builds upon Kolumbus and Nisan (2022a), which studies a setting where agents use no-regret learning algorithms to bid in a repeated auction setting. The authors first focus on a deterministic setting with two bidders that use the Multiplicative Weights Update (MWU) algorithm. In this case, they show that the runner-up bidder may not converge to bidding truthfully, depending on the learning rate it uses compared to the other agent. Next, they show that adding randomness to the auction can lead to the truthful bidding of the runner-up agent and, hence, maximize the revenue of the auctioneer. Finally, the authors study the non-asymptotic case.", "questions": "Please seem my comments above. Also, can the authors comment on the persistent value assumption? What if the values are drawn independently in each round but from different fixed distributions (in other words, we have persistent values with some noise)?", "limitations": "The limitations are discussed as the modeling assumptions are stated clearly.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I believe the question of studying repeated auctions where agents use algorithms is timely and interesting. I also appreciate how the authors attempt to extend the results of Kolumbus and Nisan (2022a) to any deterministic auction and also highlighting the importance of incorporating randomness.", "weaknesses": "I have a number of questions and concerns regarding the generality of the results and the presentation of the paper.\n\nFirst, as far as I understand, the results in Section 3 are limited to two bidders that use the MWU algorithm. If I am not mistaken, the results of Kolumbus and Nisan (2022a) are not limited to two bidders and also study other algorithms such as \"follow the perturbed leader.\" I wonder how the authors justify or perceive the limitations of their work in this regard.\n\nNext, the model described in Section 2 (and the results of Section 3) are for two bidders, but it seems that from Section 4 onward, the authors switch to an $n$ bidder case. Is this correct?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the Reviewer for their detailed feedback. Please find our answers to your questions below.\n\n> First, as far as I understand, the results in Section 3 are limited to two bidders that use the MWU algorithm. If I am not mistaken, the results of Kolumbus and Nisan (2022a) are not limited to two bidders and also study other algorithms such as \"follow the perturbed leader.\" I wonder how the authors justify or perceive the limitations of their work in this regard.\n\nRegarding the number of bidders in Section 3, we focus on the case of two bidders to keep the presentation cleaner; the results can go through when we have a larger number of bidders, where we let W be the winning bidder if they were all to bid truthfully and R the runner-up bidder if they were all to bid truthfully (i.e., the one who would win in the absence of W). Then, the convergence results about the ratio of the learning rates would apply to these two bidders.\nNotice that the theoretical results of Kolumbus and Nisan hold for the case of two bidders only.\n\nRegarding the choice of the algorithm, notice that the theoretical non-convergence result of Kolumbus and Nisan (Theorem 1 in their paper) applies to bidders who are using MWU. There are some simulations about FTRL, but, to the best of our knowledge, there is no theoretical understanding of the convergence behavior. \nNotice that our transformation in Section 4 considers $n$ bidders who are using mean-based no-regret learning algorithms (a natural class of algorithms that significant prior work has focused on), so these results do apply to Follow-the-Regularized-Leader/Follow-the-Perturbed-Leader type of algorithms.\n\n> Next, the model described in Section 2 (and the results of Section 3) are for two bidders, but it seems that from Section 4 onward, the authors switch to an $n$ bidder case. Is this correct?\n\nThis is correct; the results in Section 3, Section 5 consider two bidders, and the transformation in Section 4 applies to $n$ bidders. We are happy to state the model with n bidders, if the reviewer feels that it will make the presentation more transparent. \n\n>  Also, can the authors comment on the persistent value assumption? What if the values are drawn independently in each round but from different fixed distributions (in other words, we have persistent values with some noise)?\n\nThe persistent assumption is motivated by online ad-auctions, and is also the main setting that is considered by Kolumbus and Nisan. In the context of online ad auctions, while multiple auctions are run every second, the valuations of the advertisers do not change much for certain time scales, e.g., a day or a week. Thus, there are typically large intervals of size $T$ where the valuations of the participating agents are persistent.  We do agree, however, that the valuations will likely change over longer time horizons. We believe that as long as the persistence is significant, our results and the value of randomized mechanisms over deterministic mechanisms will hold. Having a theoretical analysis showing such behavior for a setting with not fully persistent valuations will be interesting but goes beyond the scope of this work.  \nIn the model you mentioned, where the valuations are re-drawn in every round but the distributions are different, we believe that the convergence (or non-convergence) would be dictated by the mass that the distributions put on overlapping regions of the supports of the distributions.\n\nAt a more conceptual level, we believe that a message of our work is the following: the key to convergence of the low-type bidder is the presence of enough randomness. If the ranking of the bidders is very stable due to the lack of inherent randomness (i.e., due to infrequent redraws of the valuations), our results show that injecting external randomness into the auction induces the desired learning behavior and hence improves the revenue. Moreover, it restores the property that advertisers can truthfully report their valuations to the learning agents that bid on their behalf on the queries. Having persistent valuations is just one case of the ranking of the bidders remaining stable over time: studying this case allows us to showcase our main ideas, but a central message here is the presence/absence of stability in the rankings of the bidders is key. We have tried to make this point in Lines 88-93 of our manuscript; we will emphasize it more in the next revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "73lLuZpXP9", "reviewer": "Reviewer_di38", "summary": "The paper considers the building auction mechanism for settings where the bids supplied by agents are chosen by automated no-regret algorithms operating on their behalf. It has been shown from prior work that when bidding with asymmetric valuations, no-regret algorithms converge to bids substantially far from their valuations even when the auctioneer utilizes a truthful mechanism such has a second-price auction. This leads to scenarios where the bidder with the lower valuations routinely bids lower than their true values resulting a loss of revenue for the auctioneer.\n\nThe paper undertakes a deeper study of this phenomenon and suggests methods to remedy this situation. They start by showing that the learning rates of the respective agents plays a substantial role in determining the types of  behavior observed at convergence. They show that when the learning rate of the agent with lower valuations is larger, they converge to truthful bids while this is no longer the case if they use a smaller rate. The most interesting contribution of the paper is the observation that the type of convergent behavior depends on the rewards observed by the learning agents. For instance, when second-price auctions are used, the agent with lower valuation rarely receives rewards as they never win the bid and hence, do not receive any feedback to update their bids. The paper shows that when the auctions are instead \\emph{randomized}, that is the auctioneer randomly chooses between say a second-price auction and another truthful mechanism, this allows for convergence to truthful bids irrespective of the specific implementation of the bidding algorithms. When the mixing mechanism is \\emph{strictly} incentive compatible, that is, a player obtains \\emph{strictly more} utility from truthful bidding, they show that any mean-based no-regret algorithm converges to truthful bidding. Furthermore, the proofs in the paper are natural and easy to follow. \n\nOverall, the paper considers a natural problem and presents an elegant solution. In the process, it also conceptually identifies the counterintuitive behavior of no-regret algorithms in this setting and demonstrates an approach toward remedying this. Furthermore, the technical material in the paper is well-presented and understandable. The main drawback of the results is their restriction to the setting of mean-based algorithms. It would be nice if the authors could comment on whether such a restriction may be removed.", "questions": "See main review", "limitations": "See main review", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "See main review", "weaknesses": "See main review", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the Reviewer for their detailed feedback. Please find our answers to your questions below.\n\n> The main drawback of the results is their restriction to the setting of mean-based algorithms. It would be nice if the authors could comment on whether such a restriction may be removed.\n\nOur choice of mean-based learners is motivated partly by prior work on learning in auctions, which, to a large extent, deals with mean-based learners, and partly by the fact that this is a broad class of learners which can be quantitatively reasoned about in one stroke. While we believe that our qualitative results should extend to other algorithms, it seems this would have to be a case-by-case analysis; it is not clear what broad general condition to place on a learning algorithm so that our results hold quantitatively.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fZwMqj0gSh", "reviewer": "Reviewer_Lf7G", "summary": "This work studies a setting where bidders use no-regret learning algorithms (e.g., MWU) to participate in repeated auctions. Bidders' values are assumed to be persistent.\n\nGeneralizing [Kolumbus and Nisan 2022a]'s results on second-price auctions with two equal-learning rate MWU bidders, the authors show that:\n\n(1) in *all deterministic truthful auctions*, if the learning rate of the runner-up bidder is asymptotically equal to or slower than the winning bidder, then the bidders will *not* converge to truthful bidding (which hurts the auctioneer's revenue).\n\n(2) for *some* deterministic truthful auctions (not *all*, see my (Q2)), if the learning rate of the runner-up bidder is asymptotically faster than the winning bidder, then the runner-up bidder converges to truthful bidding (while the winning bidder does not).\n\nThen, the authors design auctions to maximize the auctioneer's revenue, aiming to achieve no-regret against the second-price auction revenue. The basic idea is to take the mixture of the revenue-maximizing IC auction and a randomized strictly IC auction to ensure that bidders can converge to truthful bidding. For the finite horizon setting, the authors obtain a tight regret bound of $\\Theta(\\sqrt{T^{3/4}})$ by using a constant auction throughout $T$ rounds, and a tight regret bound of $\\Theta(\\sqrt T)$ by using an adaptive auction schedule.", "questions": "(Q1) What's the difference/improvement of this work compared to [Cai et al 2023]? (See W1)?\n\n(Q2) This is an important question regarding the correctness of a result. In Section 3, the authors claim that for *all* deterministic truthful actions, \"if the learning rate of the runner-up bidder is strictly faster than the learning rate of the winning bidder, then the runner-up bidder converges to bidding truthfully (Line 213)\". However, the formal result in Theorem D.3 and the proof are presented only for *second price auctions*. In fact, if the auction is a trivial auction that always allocates the item to bidder 1 (which is deterministic and weakly truthful), then all bids are the same for bidder 2 and hence bidder 2 cannot learn to converge to truthful bidding, so the authors' claim does not hold. I think the claim only holds for deterministic auctions where the low-value bidder can win by truthful bidding when the high-value-bidder submits a small enough bid, like the second-price auction.  A formal definition of such auctions is needed and a complete proof should be provided. Can the authors respond to this issue?\n\n(Q3) (minor clarification question) Section 4 assumes that a strictly IC auction $A'$ always exists. Does it always exist? Is the \"staircase auction\" in Definition 5.5 a strictly IC auction? If yes, then maybe mention it in Section 4.\n\n(Q4) What's the intuition that as the discretization is finer ($\\Delta$ is larger), the regret of the auctioneer becomes larger, in the order of $O(\\Delta^2 \\sqrt T)$ ? (Corollary 5.6) This feels a bit counterintuitive.", "limitations": "**Suggestions:**\n\n(1) Typo: Line 119, \"in the prior-free\"\n\n(2) Typo: Line 237, \"to a bidding truthfully\"\n\n(3) In Section 4, I'd suggest to elaborate on the black-box transformation from IC auctions to strictly IC auctions, and shorten the paragraph about \"Equilibrium of Meta-Game in Repeated Strictly IC Auctions\". For example, you can move Theorem E.1 (which is referred to in the following paragraphs) from appendix to here.  You can also clarify the existence of strictly IC auctions here (see my question (Q3)). \n\n(4) Line 372: \"number of actions $\\Delta$\" -> \"number of discretized bids $\\Delta$\"\n\n(5) Typo: Line 388: \"theoptimal\"\n\n(6) Line 559 in Theorem D.1: What is \"NPT\"?\n\n(7) Typo: Line 608: \"round $t$\" -> \" round $i$\"\n\n(8) When defining the auctioneer's regret, you compete with the revenue of the second-price auction. I think you can actually compete with the high value $v_H$, which is a stronger benchmark than the second-price revenue. And to achieve no-regret against $v_H$, the following non-oblivious adaptive auction schedule might work: use a strictly IC auction for $T_0$ rounds until the bidders converge to truthful bidding, observe the bidders' values from their truthful bids, and then in the remaining rounds switch to the auction that always allocates the item to the higher-value bidder at a price of $v_H - \\frac{1}{\\Delta}$. Is that correct?", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(S1) [Significance & Originality] The characterization of bidders' learning outcomes under different learning rates is very interesting. It is a significant generalization of previous work [Kolumbus and Nisan 2022a] that only considers equal learning rates. Result (1) above holds for all deterministic truthful auction, which is also a significant generalization of [Kolumbus and Nisan 2022a] on second-price auction only.\n\n(S2) [Quality] The auctioneer's regret bounds in the finite horizon analysis are tight (in $T$), which is good.\n\n(S3) [Clarity] The writing is clear in general. I like the discussion of high-level ideas and intuitions.", "weaknesses": "(W1) Bidders having persistent values is a strong assumption. Under this assumption, the results in Sections 4 and 5 (designing auctions to achieve no regret for the auctioneer) are relatively straightforward. Moreover, the recent paper [Cai et al 2023, Selling to Multiple No-Regret Buyers] has already studied the problem of auction design against multiple no-regret learning buyers with iid valuations across time, which seems to be a more natural and challenging setting than the persistent value setting here. Given [Cai et al 2023], this paper's additional contribution is limited.\n\n(W2) The conclusion that \"if the learning rate of the runner-up bidder is strictly faster than the learning rate of the winning bidder, then the runner-up bidder converges to bidding truthfully\" seems to only hold for some deterministic truthful auctions, not \"all deterministic truthful auctions\" as claimed by the authors. See my question (Q2).\n\nI lean towards rejection for now due to the above concerns, but may change opinions based on the authors' response.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the Reviewer for their detailed feedback. Please find our answers to your questions below.\n\n>  Bidders having persistent ...\n\nWe view our results and the setting in which we work as orthogonal to the setting of [Cai et al 2023]. Firstly, they do not restrict themselves to truthful auctions, and for their welfare extraction results, the agents are allowed to overbid. Secondly, in their setting, redrawing valuations i.i.d. in every round helps the learning process (this was also observed in [Feng et al. 2021]). Intuitively, consider two agents and SPA: for every valuation $v$ of player 1, there is some positive probability that player 2’s draw is below $v$, hence player 1 will learn that bidding truthfully is strictly better (in expectation over the other random draw), which leads to the desired bidding behavior. In such a system, randomness is already present due to the draws of the valuations, which helps the convergence to the right bidding behavior.\n\nOur setting of persistent valuations and restricting to truthful auctions, rather than complex mechanisms, is motivated by online ad-auctions. In such settings, multiple auctions are run every second, whereas the valuations of the advertisers may not change much for time scales of a day or a week. Thus, there are typically large intervals of size $T$ where the valuations of the participating agents are persistent. We agree, that the valuations will likely change over longer time horizons, but as long as the persistence is significant, we think our results and the value of randomized mechanisms over deterministic mechanisms will hold. It is an intriguing question to understand the behavior in an intermediate setting, where the valuations vary slowly over time. For this setting, ideas from our work (and from Kolumbus and Nisan (2022), who also consider bidders with persistent valuations) along with those from [Cai et al. 2023] where valuations are drawn in every round, are likely to be useful. Intuitively, the frequency at which the valuations are drawn would affect the amount of randomization we need to add to the auction to help the bidders converge to the right bidding behavior.\n\nOur work also differs from [Cai et al. 2023] in having different conceptual goals: we aim to “restore” the single-shot behavior in natural auctions, such as second-price auctions, in the presence of mean-based learning agents by making minimal modifications to the underlying auction rule. On the other hand, [Cai et al. 2023] aim to exploit the mean-based learning behavior to extract more revenue, and their auctions diverge from the truthful ones we consider in our work. Thus, in our setting, it is clear that reporting the valuation truthfully to the bidding algorithm is an (almost) optimal strategy for the agents (i.e., the so-called “meta-game” considered by Kolumbus and Nisan is truthful), whereas it is not clear to us whether reporting the valuations truthfully to the no-regret algorithms is an optimal strategy in the setting of [Cai et al. 2023].\n\nFinally, a conceptual message of our work is that the key to convergence of the low-type bidder is the presence of enough randomness. If the ranking of the bidders is very stable due to the lack of inherent randomness (i.e., due to infrequent redraws of the valuations), we show that injecting external randomness into the auction induces the desired learning behavior, improves the revenue and restores the property that advertisers can truthfully report their valuations to the learning algorithms. Having persistent valuations is one case of the ranking of the bidders remaining stable over time: studying it allows us to showcase our main ideas, but a central message here is the presence/absence of stability in the rankings of the bidders is key. We have tried to make this point in Lines 88-93 of our manuscript; we will emphasize it more in the next revision.\n\n>  The conclusion that ... \n\nThank you for pointing this out, we apologize for the confusion. Our Remark 2 in the Appendix (lines 674-678 of the submitted file) describes exactly the condition you are referring to. Under this condition, the proof provided in the appendix goes through for all such auctions. Notice also that if the runner-up bidder loses no matter what the opponent bids, then regardless of their learning rate they will converge to bidding uniformly at random. Thus, we can indeed characterize the convergence behavior for all deterministic auctions, and all learning rates. We will change the discussion in the main body, mention that this result holds for non-trivial auction  (for trivial ones we have convergence to uniform bidding), and change Remark 2 into a definition that states this property. Moreover, we will modify the proof to formally capture this setting.\n\n> (minor clarification question)...\n\nIndeed, the “staircase auction” does satisfy this condition. We will spell it out in the next version of our work.\n\n> What's the intuition ....\n\nIntuitively, if there are more bids, the strictly IC auction needs to “hedge” against more pairs of valuations of the agents and the strictly IC parameter decreases (i.e., the benefit of bidding truthfully decreases). Thus, we need to run this auction for a larger period of time to induce the desired behavior. In the setting of online ad auctions the number of bids is significantly smaller than the number of auctions, so our focus was to obtain optimal bounds with respect to $T$. \n\n> Suggestions...\n\nWe will fix the typos and clarify the black-box transformation in the next revision.\n\nRegarding suggestion (8), this is indeed correct, assuming that we use some *adaptive* auction schedule. However, we want to refrain from using such strategies and stick to non-oblivious ones, due to incentive issues – if the bidders know that we are trying to infer their valuations they should not be reporting truthfully to the learning algorithms. We wish to avoid that and stick to more practical approaches.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "33HRYJ9Of8", "reviewer": "Reviewer_9Ayy", "summary": "The paper considers repeated auctions with agents using no-regret learning algorithms. It first extends previous result on second price auction to all deterministic auctions that  the runner-up bidder may not converge to bidding truthfully, and provides the condition how the learning rates of the bidders affect the convergence of the bidders. Then it is shown that with bidders being learning agent, randomized auctions can have strictly better revenue guarantees than second price auctions with reserves. Finally, a notion of auctioneer regret is defined, measuring the revenue guarentee in learning agent settings comparing to second price auction with truthful bids, and corresponding regret bounds are provided for auctioneers using the same auction and various auctions.", "questions": "NA", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The results on biding convergence and the revenue of auctions with respects to bidders using learning algorithms are important.\n2. The idea of using auctioneer regret to analyze the revenue guarentee in learning agent settings is interesting and inspiring.\n3. The paper provides concrete theoretical proofs.", "weaknesses": "1. MWU is the only learning algorithm that considered for bidders. Although it is resresentative, it would be better see more general results for other learning algorithm, or more general characterization on learning algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the Reviewer for their detailed feedback. Please find our answers to your questions below.\n\n> MWU is the only learning algorithm that considered for bidders. Although it is representative, it would be better see more general results for other learning algorithm, or more general characterization on learning algorithms.\n\nNotice that our results in Sections 4, 5 hold for all mean-based algorithms, which generalize MWU. We will emphasize that more in the next version of our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Reviewers found the problem timely and interesting and the solution elegant. On the negative side, reviewers are generally concerned with (perhaps strong) assumptions and thus the generality of the results. This prevents the paper from being recommended beyond poster acceptance. We hope the authors find the reviews helpful. Thanks for submitting to NeurIPS!
Decision: Accept (poster)