Randomized Truthful Auctions with Learning Agents

Authors: gagan  aggarwal
anupam  gupta
andres  perlroth
grigoris  velegkas
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 12:51:38

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})$.

Main paper: 
 introduction: 
 In auction design, truthfulness is a highly sought-after property. It allows bidders to simply reveal their true valuations, simplifying the bidding process. In the standard single item setting with fully rational profit-maximizing bidders, Myerson's seminal paper Myerson (1981) shows that an auctioneer can achieve optimal revenue by using a truthful and deterministic auction mechanism -a Second Price Auction (SPA) with a reserve price.In many applications nowadays, buyers no 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 to 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 in the presence of such learning bidders. In particular, when (profit-maximizing) bidders use no-regret learning algorithms, the second-price 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 bid is less than their value with positive probability, which diminishes the second price auction's revenue. Moreover, Kolumbus and Nisan (2022b) 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-maximizing auctioneer must now carefully balance the randomization within a truthful mechanism to incentivize learning without incurring excessive revenue loss due to mis-allocation.We build our theory based on the model presented by Kolumbus and Nisan (2022a) . We consider single-item repeated interactions over T periods. There are two profit-maximizing bidders participating in 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 a week. Thus, there is typically a 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 is 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 convergence of learners who are using Multiplicative Weights Update (MWU) in repeated deterministic auctions. In particular, we 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 runner-up type will not converge to bidding truthfully, even as T → ∞; 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 (2022a) 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 3 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 A 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 is not revenue-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 Myerson (1981) which shows that SPA with reserve is optimal for rational bidders.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, e.g., if bidder values are independently drawn in each round, as in Feng et al. (2021) . But if not, and if 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 showcase 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.A Non-Asymptotic Analysis. Our next set of results in Section 5 address 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 to 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 auctiondeterministic or randomized -can achieve an auctioneer-regret better than O(T 3/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 a time independent of the bid history, then the auctioneer's regret drops to O( √ T ), as we show in Section 5 Moreover, we show in Proposition 5.4 that this bound of O( √ T ) is optimal even if the auctioneer can design the auction schedule. As a 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.To show that an auctioneer facing learning bidders using MWU must suffer an Ω(T 3/4 ) revenue loss compared to the setting when it is facing rational agents, we break down the revenue loss into two non-overlapping 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 a 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 Ω(T 3/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( √ T ) 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 O( √ T ) seems surprising, because in traditional no-regret learning settings the optimal regret is achieved when the exploration and exploitation phase are intermixed.The most closely related works to our setting are Feng et al. (2021) ; Deng et al. (2022) ; Kolumbus and Nisan (2022a) ; Banchio and Skrzypacz (2022) ; Rawat (2023) . All these works study the longterm 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. Feng et al. (2021) 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 auctions that classical theory predicts, i.e., the bids in second-price auctions are truthful and the bids in 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-price 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 to push its bid distribution up to its valuation. On the other hand, when the valuations are redrawn as in Feng et al. (2021) , 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. (2022) 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-Colell (2000) showed that when players deploy no-regret algorithms to participate in games they converge to coarse-correlated equilibria. Recently, there has been a growing interest in the study of no-regret learning in repeated auctions. The empirical study of Nekipelov et al. (2015) showed that the bidding behavior of advertisers on 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 a seller faces a 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) ; Rawat (2023) 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 second-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., 2021 Asker et al., , 2022b;; den Boer et al., 2022; Epivent and Lambin, 2022; Asker et al., 2022a) . Notably, Bertrand et al. (2023) formally proved that Q-learners do collude when deployed in repeated prisoner's dilemma games.In a related line of work, Zhang et al. (2023) 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 a particular equilibrium that the designer wants them to. An interpretation of our results is that randomization is a way to achieve some kind of equilibrium steering in repeated auctions.Diverging slightly from the setting we consider, some recent papers have illustrated different advantages 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 value-maximizing autobidding agents compared to 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. 
model: 
 Our model follows the setup used in Kolumbus and Nisan (2022a) . There are T rounds, and the auctioneer sells a single item in each round t = 1, . . . , T . There are two bidders, with bidder i ∈ {1, 2} having a persistent private valuation v i drawn i.i.d. over the discrete set B ∆ := {0, 1 /∆, 2 /∆, . . . , 1} from a regular distribution F . (A discrete distribution is regular if the discrete virtual valuation function φ(v):= v -1 ∆ v >v Pr[v ] Pr[v]is non-decreasing.) Given an allocation probability x and price p, the bidder with valuation v receives a payoff of v • x -p. In what follows, we refer to the bidder with valuation v L = min{v 1 , v 2 } (resp. v H = max{v 1 , v 2 }) as the low type (resp. high type).We are interested in truthful auctions, (also called strategy-proof auctions, or dominant-strategy incentive-compatible mechanisms) that are individually rational, so that at every round t the auctioneer uses a mechanism ((x t 1 , x t 2 ), (p t 1 , p t 2 )) satisfying v i • x t i (v i , b ) -p t i (v i , b ) ≥ v i • x t i (b, b ) -p t i (b, b ), ∀v i , b, b ∈ B ∆ , i = 1, 2 , v i • x t i (v i , b ) -p t i (v i , b ) ≥ 0, ∀v i , b ∈ B ∆ , i = 1, 2 .In this work, we study various properties of randomized truthful auctions. Definition 2.1 (Randomized Truthful Auction). A truthful auction ((x 1 , x 2 ), (p 1 , p 2 )) is randomized if there is some bid profile (b 1 , b 2 ) ∈ B ∆ such that either x 1 (b 1 , b 2 ) ∈ (0, 1) or x 2 (b 1 , b 2 ) ∈ (0, 1).Bidders employ learning algorithms that bid over the T rounds. We assume that the learning algorithms are mean-based no-regret learning algorithms (Braverman et al., 2018) . For the following discussion, defineU t i (b | b t -i ) := t τ =1 v i • x τ i (b, b τ -i ) -p τ i (b, b τ -i) to be the cumulative reward of agent i when they bid b over the t rounds, whereas the other agent's bids are bt -i = {b τ -i } τ ∈[t]. The mean-based property states that if a bid b ∈ B ∆ has performed significantly better than bid b ∈ B ∆ , then the probability of bidding b in the next round is negligible. This is formalized below. Definition 2.2 (Mean-Based Property (Braverman et al., 2018) ). An algorithm for agent i is δ-meanbased if for any bid sequence bt -i such that U t-1 i (b | b t -i ) -U t-1 i (b | b t -i ) > δ • T , for some b, b ∈ B ∆ ,the probability of playing bid b in the next round is at most δ. We say that an algorithm is mean-based if it is δ-mean-based for some δ = o(1).The no-regret learning property states that the cumulative utility that the bidding algorithm generates is 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.1. Mean-based no-regret learning algorithms are becoming a standard class of learning algorithms to use in auction environments (see, e.g., Braverman et al. (2018) ; Feng et al. (2021) ; Deng et al. (2022) ; Kolumbus and Nisan (2022a) , and references therein) and include many known no-regret learning algorithms, including the multiplicative-weights update algorithm (MWU). For completeness, we present the version of MWU that we use in our work in Algorithm 1. The above definitions consider a fixed value of T. Thus, given a sequence of such values T and the limiting behavior as T → ∞, we say that a family of algorithms, parameterized by the time horizon T , satisfies the mean-based definition if there exists {δ T } T ∈N such that δ T → T →∞ 0, and each algorithm in this family is δ T -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 ∈ [T ], the algorithm learns for each bid b ∈ B ∆ the (expected) utility it would have generated had it played bid b. In Appendix G, we discuss potential extensions.Throughout this paper we make a natural assumption on the algorithms which restrict bidders to never bid over their value. Specifically, for any round t, and any history of bids before period t, agent i bids b i > v i with zero probability. Without this assumption, Braverman et al. (2018) ; Cai et 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 → ∞. 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., 2022b,a; Cai and Zheng, 2022) . This is formalized in Definition C.2.Due to space limitations, all the proofs of our results can be found in the appendix. 
deterministic truthful auctions: 
 In this section we study the effect of the learning rate on the convergence of no-regret learning algorithms in 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 R wins the item by bidding v R but does not win by bidding v R -1 /∆. The formal definition is given in Definition D.1. 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 strictly faster than that of the winning bidder, then the runner-up bidder converges to a bidding distribution whose mean is strictly smaller than its true value. This result holds under an even milder requirement than nondegeneracy. Namely, as 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 deterministic. 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 byv W ∈ {v L , v H } and η W T (resp., v R ∈ {v L , v H }, and η R T )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 η T of MWU is a decreasing function of T and is chosen in a way to minimize the quantityC∆ /η T + C ∆ • η T • T , where C ∆ , C ∆ are discretization-dependent constants. Usually, it is instantiated with η T = 1/ √ T .However, for the purposes of our analysis we will say that ηT is non-degenerate if lim T →∞ η T • T = ∞, lim T →∞ η T • log T = 0 .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 v W , we show that its bids converge to a distribution supported between p, the price it would pay if both bidders bid truthfully, and its value v W , 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 η R T /η W T = ω(1), i.e., the runner-up bidder learns more aggressively than the winning bidder, then it converges to bidding truthfully. However, if η R T /η W T < C ∆ , where C ∆ is some discretization-dependent constant, then the runner-up converges to a bidding distribution that puts positive mass on every (discretized) point between 0 and v R , and, in particular, its expected value is strictly less than v R . We remark that even though our proof idea is inspired by Kolumbus and Nisan (2022a) , our analysis considers all the possible learning rates that MWU could be instantiated with and requires a 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 η R T /η W T < C ∆ . The idea of the proof is to split the horizon into consecutive periods of size O(1/η R T ), 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 Ω(1/η W T ) many times, so the total utility of the winning bidder for bidding between p and v W will be at least Ω(1/η W T ) greater than bidding anything between 0 and p -1/∆. Because its learning rate is η W T , this means that it will move a constant fraction of its mass from the region {0, 1/∆, . . . , p -1/∆} to the region {p, . . . , v W }. Summing this geometric series, we see that the winning bidder will submit bids in the region {0, 1/∆, . . . , p -1/∆} at most O(1/η W T ) many times. Let us now focus on the runner-up bidder. Following the previous argument, its total utility for bidding v R will be at most O(1/η W T ) greater than bidding some other bid b ∈ B ∆ . Since η R W /η W T < C, this means the probability of bidding b after T rounds is only smaller than the probability of bidding v R by a discretization-dependent multiplicative constant. The formal statement of this result and its proof follow are postponed to Appendix D.Our next result illustrates that the convergence behavior of the runner-up type exhibits a sharp phase-transition phenomenon: if η R T is even slightly faster than η W T , i.e., η R T /η W T = ω(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/η W T ). 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 v R -1/∆ at least Ω(1/η W T ) many times. Thus, this means that the total utility of bidding v R for the runner-up bidder will be at least Ω(1/η W T ) greater than bidding any other bid. Since η R T /η W T = ω(1), after the first epoch the MWU algorithm will place all but a o(1)-fraction of the probability mass to bidding truthfully. The formal statement and its proof appear in Appendix D.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 (1981) 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 no 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 B ∆ , which we denote by U [B ∆ ]. 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 T → ∞. Theorem 3.1 (SPA with Reserve Is Not Revenue Optimal). Let two agents draw their valuations from the uniform distribution over U [B ∆ ] and participate in T repeated auctions using mean-based learners. Let b T 1 , b T 2 be the bid distributions after T rounds. Let Rev(b 1 , b 2 ; r) denote the revenue of the second-price auction with reserve price r when the bids are b1 , b 2 ∈ B 2 ∆ . Then, for all r < 1 -1/∆, E v1,v2∼U [B∆] lim T →∞ E b1∼b T 1 ,b2∼b T 2 [Rev(b 1 , b 2 ; r) | v 1 , v 2 ] < E v1,v2∼U [B∆] [Rev(v 1 , v 2 ; r)] -c ,where c > 0 is some constant that does not depend on T.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) 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 a 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 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? 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, confidence intervals, or statistical significance tests, at least for the experiments that support the 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, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• 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 a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error 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. 
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 mean-based 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 i ∈[n], valuation v i ∈ B ∆ , and bid profile b -i ∈ B n-1 ∆ it holds that v i • x i (v i , b -i ) -p i (v i , b -i ) > v i • x i (b, b -i ) -p i (b, b -i ), ∀b = v i .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 t -1 is much smaller than the utility of some other bid b , 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 → ∞, the bidders converge to truthful bidding in a last-iterate sense.The next important observation is that when we are taking a 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 = (x(•), p(•)) be an IC auction and A = (x (•), p (•)) be a strictly IC auction. For some q ∈ (0, 1) we define the q-mixture of the auctions A, A to the be auctionA q = (q • x(•) + (1 -q) • x (•), q • p(•) + (1 -q) • p (•)) .Notice that for the allocation rule q•x(•)+(1-q)•x (•) Myerson's lemma states that the corresponding payment rule that makes the auction truthful is 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.Claim 1 (Mixture of IC and Strictly IC Auction). Let A, A be an IC, strictly IC auction, respectively. Then, for any q ∈ (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 a strictly IC auction A so that as T → ∞, any mean-based learning algorithms converges to truthful bidding, and the auction A is close to the auction A in the sense that|x i (b) -x i (b)| = o(1), |p i (b) -p i (b)| = o(1), ∀i ∈ [n], ∀b ∈ B n ∆ .The formal statement of the result follows.Theorem 4.4. Let A be an IC auction for n agents with valuations v 1 , . . . , v n . Let each agent i ∈ [n] use a mean-based no-regret learning algorithm to bid in the auction. Then, there exists an auction A such that for each agent i ∈[n] we have that lim T →∞ b T i = v i and |x i (b) -x i (b)| = o(1), |p i (b) -p i (b)| = o(1), ∀b ∈ B n ∆ , where x i (•), x i (•) (resp. p i (•), p i (•)) 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 to in Section 1. Recall that this game is defined as follows: the agents submit their valuations to 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 a 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 L > v H to its bidding algorithm. Then, the bidder with type v H will take the role of the low bidder in the interaction and will converge to bidding strictly below v H . Now if its expected bid is also below v L , 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 E 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 → ∞. 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 → ∞. 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 3, 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 E is, essentially, a corollary of Theorem 4. ∆ . Corollary 4.5. Consider an environment with n agents that draw their values i.i.d. from some regular distribution F and participate in repeated single-item auctions using mean-based no-regret learning algorithms. Then, there is a randomized auction A so thatE v1,...,vn∼F n lim T →∞ E b1∼b T 1 ,...,bn∼b T n [Rev(A; b 1 , . . . , b n )] v 1 , . . . , v n ≥ E v1,...,vn∼F n [Rev(Myerson; v 1 , . . . , v n )] -o(1).Given the results from Theorem 3.1 and Corollary 4.5 we would like to remark the following. Remark 1 (Randomized Auctions vs. SPA with Reserve). Our results illustrate that randomized auctions have strictly better revenue guarantees compared to SPA with reserve price, when the bidders are using mean-based no-regret learning algorithms. This is a property of randomized auctions that is not witnessed in the setting where the bidders are fully rational, as proven by Myerson (1981) . 
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 finite-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-based no-regret learning algorithms to participate in single-item auctions for T rounds. Since 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 is to choose an auction in a way that minimizesReg T (A; v L , v H ) = T t=1 Rev(v L , v H ; SP) -E T t=1 Rev(b t L , b t H ; 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 is the followingγ A = min i∈{1,2},bi,b-i,vi∈B 3 ∆ :bi =vi {(v i • x i (v i , b -i ) -p i (v i , b -i )) -(v i • x i (b i , b -i ) -p i (b i , b -i ))} ,i.e., the minimum increase in the utility by bidding truthfully instead of bidding non-truthfully in A.Our first goal is to 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 ∆. Our first result shows that given any strictly IC auction A there exists an auction A T that achieves auctioneerregret O T • ∆•δ T γ A. This is formalized below and the proof is postponed to Appendix F.Proposition 5.1. There exists auction A T which is a mixture of some strictly IC auction A and SPA such that, for all v L , v H ∈ [0, 1] 2 and for all δ T -mean-based learning algorithms it holds thatReg T (A T ; v L , v H ) = O ∆•δ T γ A • T , ∀v L , v H ∈ B 2 ∆ .We emphasize that for common mean-based no-regret learning algorithms such as MWU it is the case that δ T = O ( 1 / √ T ) , which implies that the auctioneer regret from Proposition 5.1 grows as O T 3/4 . Our next result complements this result by showing that even if the high-valuation bidder always bids truthfully and the low-valuation bidder uses MWU with learning rate Θ( 1 / √ T ), no auction can achieve a better auctioneer regret than O(T 3/4 ). Proposition 5.2 (Lower Bound for Constant Auction Policies). Consider a repeated auction environment where the high-valuation bidder bids truthfully and the low-valuation bidder uses MWU with rate Θ( 1 / √ T ). Then, every truthful auction A T has an auctioneer regret Reg T (AT ; v L , v H ) ≥ C ∆ • T 3/4, where C ∆ > 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/ √ T gives the optimal no-regret guarantees. Other choices, such as η T = Ω(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 to an auction schedule {A 1 , . . . , A T } 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 RegT (A 1 , . . . , A T ; v L , v H ) = T t=1 Rev(v L , v H ; SP) -E[ T t=1 Rev(b t L , b t H ; A t )] .Our next result shows that there exists an auction schedule where the auctioneer changes the underlying auction only once throughout the interaction so that its regret is bounded by O(δ T • T ). For typical choices of η T this translates to an auctioneer regret bounded by O( √ T ). The main insight is that the auctioneer can split the interaction into two intervals: the first interval has size T 0 , for some appropriately chosen T 0 ∈ [T ], where the auctioneer uses some strictly IC auction A that encourages the learners to converge to bidding truthfully. Then, assuming that T 0 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 (A 1 , . . . , A T ) in which A 1 = A 2 = . . . = A T0 = A, where A is any strictly IC auction, andA T0+1 = A T0+2 = . . . = A T = SP, that achieves Reg(A 1 , . . . , A T ; v L , v H ) ≤ O δ T • T • 1 γ A + ∆ , ∀v L , v H ∈ B 2 ∆ .The formal proof of this result is postponed to Appendix F. The previous result shows that forη T = O ( 1 / √ T )the auctioneer regret of the auction schedule we designed is O( √ T ). Thus, we see an O(T 1/4 ) 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 is (almost) optimal with respect to the time horizon T. The proof idea is that when the agents are using MWU with learning rate η T , the signals in the first O(1/η T ) steps are insufficient for them to move their bidding distribution to truthful bids. I.e., with at least some constant probability in every round within the first O(1/η T ) rounds, they will not be bidding their true valuation. Importantly, our lower bound holds even in the (unrealistic) setting where the auctioneer can choose A 1 , . . . , A T , conditioned on v L , v H . This is formalized below; the proof is postponed to Appendix F. Proposition 5.4. When two agents are using MWU with learning rate 1 / √ T to participate in repeated single-item auctions for all the auction schedules (A 1 , . . . , A T ) it holds thatReg(A 1 , . . . , A T ; v L , v H ) = Ω( √ T ) .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 ∆.First, we define an auction Ā that satisfies γ Ā = Θ( 1 /∆ 2 ). Definition 5.5 (Staircase Auction). We define the allocation rule of auction Ā in the following way: with probability 1/2 select a bidder i ∈ {1, 2} independently of their bids and then allocate to i with probability b i . We define the payment rule in the way that makes the auction truthful.A simple application of Myerson's lemma shows that γ Ā = Θ( 1 /∆ 2 ). This is because between any two consecutive bids, i.e., bids whose distance is 1/∆, the increase in the allocation is 1 /2∆ 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-based learner with η T = O( log ∆ /T ) and the auctioneer use the schedule(A 1 , . . . , A T ) with A 1 = . . . = A T0 = Ā, A T0+1 = A T0+2 = . . . = A T = SPA, for T 0 = O √ T /∆ 2 . Then, Reg(A 1 , . . . , A T ; v L , v H ) ≤ O ∆ 2 √ T , ∀v L , v H ∈ B 2 ∆ . 
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 in single-parameter environments, and of the power of randomization. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification:Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or 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 or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses for existing assets Question: 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?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: 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 η T = log ∆ T . Initialize ∆ weights, letting w t i be the value of the ith weight at round t. Initially, set all w 0 i = 1, let v be the valuation of the agent. 2: for t = 1 to T do 3:Choose bid b i with probability p t i = w t-1 i / j w t-1 j .4:for j = 1 to K do 5: Let u t j = v • x t (b j , b ) -p t (b j , b ) 6:Set w t j = w t-1 j• e η T u t j .7:end for 8: end forWe 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 by Feng et al. (2021) ). Intuitively, consider two agents and SPA: for every valuation of player 1, there is some positive probability that player 2's draw is 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 to 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 to "restore" the single-shot behavior in natural auctions, such as second-price auctions, in the presence of meanbased 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 (2022a) 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) .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 ∆ → ∞: specifically, Proposition 1 from that paper gives the following claims. Claim 2. A mechanism is truthful if and only for every v -i x i (v i , v -i ) is non-decreasing on v i and p i satisfy thatp i (v i , v -i ) -v i x i (v i , v -i ) - vi 0 x i (z, v -i )dz ≤ O(1/∆).Claim 3. Suppose bidders are rational agents (i.e., they maximize profits). Let OP T be the revenue of the revenue-maximizing mechanism (among truthful or non-truthful) that the auctioneer can implement, and Rev(r -SP A) be the revenue of a Second Price Auction with reserve r. Then for r = min{v : φ(v) ≥ 0}, we have that OP T = Rev(r -SP A). Definition C.1 (No-Regret Learning Property). Let {b τ i } τ ∈[T ] be the bid sequence submitted by agent i's algorithm, andU T i (b T ) = T τ =1 v i • x τ i (b τ i , b τ -i ) -p τ i (b τ i , b τ -i) the total reward agent i receives. We say that this algorithm satisfies the no-regret property if for any sequence b T -i it holds thatE max b∈B∆ U T i (b | b T -i ) -U T i (b T ) = o(T ) ,where the expectation is taken with respect to the randomness of the algorithm. Definition C.2 (Last Iterate Convergence (LIC)). Let bT i the bid distribution of bidder i in the last round T . We say that bT i converges to some distribution q over B ∆ if lim T →∞ d TV ( bT i , q) = o(1), where d TV := 1 2 b∈B∆ | bT i (b) -q(b)| is the Total-Variation (TV) distance between bT i and q.D Omitted Details from Section 3 Definition D.1 (Non-Degenerate auctions). A single-item auction (x, p) for two agents is nondegenerate with respect to the valuation profileEQUATIONmax {v 1 • x 1 (v 1 , v 2 ) -p 1 (v 1 , v 2 ), v 2 • x 2 (v 1 , v 2 ) -p 2 (v 1 , v 2 )} > 0 .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-negative payments (see, e.g., Roughgarden (2010, Thm 9.36)) for n bidders.A single-item auction is truthful, and satisfies NPT, i.e., no payment transfers from the auctioneer to the bidders, if and only if:• x i (•, v -i ) is monotone for every i ∈ [n], v -i ∈ B n-1 ∆ . • For all i ∈ [n], v i ∈ B ∆ , v -i ∈ B n-1 ∆ we have that p i (v i , v -i ) = 0, if x i (v i , v -i ) = 0 min{b ∈ B ∆ : x i (b, v -i ) = 1}, if x i (v i , v -i ) = 1 .Theorem D.3 (No Deterministic Auction Leads to Truthful Bidding). Fix a valuation profile (v 1 , v 2 ) and a deterministic truthful auction. Suppose bidders bid using MWU and with non-degenerate learning rates. Let W (respectively R), be the bidder i ∈ {1, 2} such thatx i (v i , v -i ) = 1 (re- spectively, x i (v i , v -i ) = 0) and let p = p W (v W , v R ). Assume that lim T →∞ η R T /η W T < ∞ and v W • x W (v W , v R ) -p > 0.Then, with probability at least 0.99, the winner's bids converge to a distribution supported between p, v W and the runner-up bidder converges to a bidding distribution satisfying 0< Pr[0] ≤ Pr[1/∆] ≤ . . . ≤ Pr[v R ].Proof of Theorem D.3. The idea of the proof is to split the horizon T into continuous non-overlapping epochs of length c/η W T , where c is some sufficiently large constant that depends on the discretization parameter ∆. Notice that since lim T →∞ η W T • T = ∞ these epochs are well-defined, when T is sufficiently large. Assume without loss of generality that the weights of all the bids that are at most v W (resp. v R ) for the winning bidder (resp. runner-up) are initialized to 1. (The proof holds as long as 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 t.Let c W = v W -p be the utility the bidder gets when it wins the auction. By assumption, c W > 0. Let W W be the set of bids between p and v W , i.e., W W = {p, p + 1 /∆, . . . , v W }. Whenever the runner-up bids v R all the bids in W W increase their weights by a multiplicative factor of e c W •η W T , whereas the weights of the other bids remain unchanged. Moreover, since the allocation rule is non-decreasing and the price does not depend on the bid, whenever the weight of some bid b ∈ B ∆ is increased, the weights of all the bids that are greater than b are also increased by the same amount. Notice that, since bidding v R is a weakly-dominant strategy for the runner-up type, the mass that it puts on v R will never decrease relatively to the mass of the rest of the bids. Thus, the probability of bidding v R for the runner-up type is at least 1/∆ in every round. Hence, if we consider an interval of size T 0 = 8∆2 /(η W T • c W ) and we denote by Z i , i ∈ [T 0 ], the indicator variable of whether the runner-up bid v R in round i ∈ [T 0 ] we have that for any α > 0Pr [Z 1 + . . . + Z T0 ≥ α] ≥ Pr Z1 + . . . + ZT0 ≥ α ,where Zi , ∈ [T 0 ] are i.i.d. Bernoulli random variables with mean 1/∆. Then, the multiplicative version of Chernoff bound on { Zi } i∈[T0] shows that, with probability at least 1 -e -∆/(η W T •c W ) the runner-up type will bid at least 4∆/(η W T • c W )) many times v R in this window. By a union bound, we know that with probability at least 1 -(T • η W T /c) • e -∆/(η W T •c W )this holds across all the T • η W T /c different epochs. We call this event E 1 and condition on it for the rest of the proof. Our assumption that η T is non-degenerate shows that this probability is at least 1 -o(1).W (b) be the total weight that the winning type assigns to b at the beginning of epoch τ and m τ W (b) be its probability. Notice that at τ = 1 this distribution is uniform. Consider the ratio of the weights of any b ≤ p -1/∆ and p. We have thatEQUATIONwhere w τ W (b), w τ W (p) are the weights that the winner puts on b, p at the beginning of epoch τ (similarly for the τ + 1 terms). For the probability of each bid in MWU,m τ +1 W (b) = w τ +1 W (b) b ∈B ∆ w τ +1 W (b )(and symmetrically for the other terms). Thus, by dividing the numerator and the denominator of the RHS of Equation ( 1) by b ∈B∆ w τ W (b ) and the numerator and denominator of the LHS of Equation ( 1) by b ∈B∆ w τ +1 W (b ) we get:m τ +1 W (b) m τ +1 W (p) ≤ m τ W (b) m τ W (p) • e -4∆ .Multiplying by m τ +1 W (p) gives usm τ +1 W (b) ≤ m τ +1 W (p) m τ W (p) • m τ W (b) • e -4∆ .Notice that m 1 W (p) = 1/∆, m τ W (p) is non-decreasing in τ since bidding p is a weakly-dominant strategy for the winning type 2 , and, by definition, m τ +1 H (p) ≤ 1, som τ +1 W ( p) m τ W ( p) ≤ ∆. Hence, m τ +1 W (b) ≤ ∆e -4∆ • m τ +1 W (b) < 0.1 • m τ W (b), ∀b < p, where the second inequality follows from xe -4x < 1, ∀x > 0. Thus, after each epoch the probability that the winning type does not bid in W W decreases by a factor of 0.9. Hence, we can see that after O(η W T • T ) epochs that total mass in this region is at mostO(0.1 η W T •T -1 ) = o(1). This proves the claim about the distribution of the winning type.Let Z i , i ∈ [T ], be the random variable that indicates whether v W bid in {0, 1/∆, . . . , p -1/∆} in round i ∈ [T ]. Let also T denote the total number of epochs. Let Z τ = Z τ + . . . + Z τ +T0-1 , so that E[Z 1 + . . . Z T ] = T τ =1 E[ Z τ ].The preceding steps of the proof had shown that after every round, the probability that the winner bids in this region is non-increasing (since the bids in interval I are weakly dominated by the bids in { p, . .. , v W }), hence E[ Z τ ] ≤ T 0 • E[Z (τ -1)•T0+1 ]. Thus, it suffices to bound T τ =1 E[Z (τ -1)•T0+1 ]. By definition, E[Z (τ -1)•T0+1 ] = b< p m (τ -1)•T0+1 W (b). Now, the previous step of the proof had shown that the mass of each bid in interval I drops by a factor of 0.9 between the beginning of consecutive epochs, i.e., m τ•T0+1 W (b) ≤ 0.1 • m (τ -1)•T0+1 W (b) for all b ∈ {0, 1/∆, . . . p -1}. This implies E[Z τ •T0+1 ] ≤ 0.1 • E[Z (τ -1)•T0+1 ]. Using E[Z 1 ] ≤ 1, we get T τ =1 E[Z (τ -1)•T0+1 ] ≤ T τ =1 (0.1) τ -1 . Multiplying this by the value of T 0 gives E [Z 1 + . . . + Z T ] ≤ T τ =1 (8∆ 2 /(η W T • c W )) • (0.1) τ -1 ≤ ∞ τ =1 (8∆ 2 /(η W T • c W )) • (0.1) τ -1 ≤ 16∆ 2 /(η W T • c W ) .Hence, using Markov's inequality we see thatPr Z 1 + . . . + Z T ≥ 101 • 16∆ 2 /(η W T • c W ) ≤ E [Z 1 + . . . Z T ] 101 • 16∆ 2 /(η W T • c W ) ≤ 1 101 .Let us call this event E 2 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 m R (•). Recall that whenever the winning type bids in W W , the runner-up type performs no updates. Moreover, whenever it does perform an update its utility when it bids v R is at most 1 greater than bidding b = 0. Notice that whenever the weight of some bid b 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 v R by some quantity that is independent of T. We havethat m R (0) m R (v R ) ≥ e -η R T 101•(16∆ 2 /(η W T •c W )) =⇒ m R (0) ≥ e -η R T 101•(16∆ 2 /(η W T •c W )) ∆ ,where the second inequality follows from the fact that the distribution is initialized to be uniform and v R is a weakly-dominant strategy across all rounds, so its probability is not decreased. Notice that limT →∞ η R T /η W T < C ,for some discretization-dependent C, it follows that m R (0) > C , where C > 0 is some discretization-dependent constant. Since Pr[E 1 ] ≥ 1 -o(1), Pr[E 2 ] ≥ 100/101, we have that Pr[E 1 ∩ E 2 ] ≥ 99/100, when T is large enough.Theorem D.4 (Effect of Learning Rate on Convergence). Fix a valuation profile (v 1 , v 2 ) and a non-degenerate deterministic truthful auction with respect to (v 1 , v 2 ). Suppose bidders bid using MWU and with non-degenerate learning rates. Let W (respectively R), be the bidder i ∈ {1, 2} such thatx i (v i , v -i ) = 1 (respectively, x i (v i , v -i ) = 0). Let p be the minimum winning bid of W when R bids v R . Assume that η R T /η W T = ω(1). Then, with probability at least 1 -o(1), bidder R converges to bidding v R and bidder W converges to a bidding distribution supported in {p, p + 1 /∆, . . . , v W }.Proof of Theorem D.4. Consider the first T 0 = c ∆ /η W T rounds of the game, for some c ∆ discretization-dependent constant. Assume without loss of generality that the weights of all the bids that are at most v W (resp. v R ) for the winning bidder (resp. runner-up) are initialized to 1. (Again, the argument works so long as all the weights are initialized with some constants.) Since the auction is non-degenerate with respect to v W , v R , there exists some bid of the winning type b W ≤ v W so that the runner-up bidder wins the auction when bidding truthfully and gets positive utility, i.e.,v R • x R (v R , b W ) -p R (v R , b W ) > 0 . Moreover, for all bids b R < v R it holds v R • x R (v R , b W ) -p R (v R , b W ) -(v R • x R (b R , b W ) -p R (b R , b W )) > 0 .Since the auction is truthful, the difference above is minimized atb R = v R -1 /∆. Let u R := v R • x R (v R , b W ) -p R (v R , b W ) -(v R • x R (v R -1 /∆, b W ) -p R (v R -1 /∆, b W )) ,and, by definition, u R > 0. Let us consider the winning type and look at the worst-case ratio of the probability that is placed on bids b t W = b W , b t W = v W at the end of every round t ∈ {1, . . . , T 0 }. We have thatPr[b t W = b W ] Pr[b t W = v W ] ≥ e -η W T •v W •t ≥ e -η W T •v W •T0 = e -c ∆ •v W ,where the first inequality follows from the fact that bidding v W always yields at most v W utility more than bidding any other bid and the second one because t ≤ T 0 . Moreover, since Pr[b 1 W = v W ] = 1/∆ and the probability that is placed on b t W = v W is non-decreasing across the executions (since it is a weakly-dominant strategy), we have thatPr[b t W = b W ] ≥ e -c ∆ •v W /∆, ∀t ∈ {1, . . . , T 0 } .Let Z T0 denote the random variable that counts the number of times the winning type bids b W within the first T 0 rounds. Let Zτ , τ ∈ [T 0 ] be independent Bernoulli random variables with meane -c ∆ •v W /∆. Notice that, ∀α > 0, it holds that Pr[Z T0 ≥ α] ≥ Pr[ T0 τ =1 Zτ ≥ α]. Moreover, E T0 τ =1 Zτ ≥ T 0 • e -c ∆ •v W /∆ = c ∆ /η W T • e -c ∆ •v W /∆ .To simplify the notation, let us denote c∆ = c ∆ • e -c ∆ •v H /∆. Thus, a multiplicative Chernoff bound shows that, with probability at least 1 -e -c∆/(8η W T ) = 1 -o(1), we have that Z T0 ≥ c∆ /(2η W T ). 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 T 0 rounds. Notice that whenever the winning bidder bids b W then bidding v R yields utility at least u R greater than bidding any other bid to the runner-up type, and in the rounds where this does not happen, bidding v R is still a weakly dominant strategy so it generates as much utility as any other bid. Thus, we have thatPr[b T0 R = v R -1/∆] Pr[b T0 R = v R ] ≤ e -u R •η R T •Z T 0 ≤ e -η R T •c∆/(2η W T ∆) = o(1)Thus, since bidding v R is a weakly dominant strategy for the runner-up this ratio is non-increasing in t we can immediately see thatPr[b T0 R = v R -1/∆] Pr[b T0 R = v R ] = o(1) , which gives that Pr[b T R = v R -1/∆] = o(1). The same argument can be applied to all bids in {0, 1/∆, . . . , v R -1/∆}.For the winning type, a symmetric argument shows that since after O(η W T ) many rounds the runner-up type bids v R with high probability, all the bids in the region {v W , . . . , v W } will yield utility that is larger than bidding v R -1/∆ by at least 1/∆ (again with high probability), so after another ω(η W T ) rounds its mass will be concentrated on bidding in this region.Proof of Theorem 3.1. Let E = {r < v 1 } ∩ {r < v 2 } ∩ {v 1 = v 2 }. We can decompose E v1,v2∼U [B∆] [Rev(v 1 , v 2 ; r)] as: E v1,v2∼U [B∆] [Rev(v 1 , v 2 ; r)] = E v1,v2∼U [B∆] [Rev(v 1 , v 2 ; r)| E] • Pr v1,v2∼U [B∆] [E] + E v1,v2∼U [B∆] [Rev(v 1 , v 2 ; r)| E ] • Pr v1,v2∼U [B∆] [E ] .Notice that under E , the revenue of the auction in the learning setting satisfiesE v1,v2∼U [B∆] lim T →∞ E b1∼b T 1 ,b2∼b T 2 [Rev(b 1 , b 2 ; r) | v 1 , v 2 ] E ≤ E v1,v2∼U [B∆] [Rev(v 1 , v 2 ; r)| E ] .This is because both bidders will be bidding at most their valuation, so the revenue of the auction cannot increase. Let us now focus on the first term. Under the event E, the revenue of the auction under rational agents is min{v 1 , v 2 } > r. However, in the learning setting, the runner-up bidder will be bidding strictly below their valuation in expectation, by Theorem D.3. Hence, we have thatE v1,v2∼U [B∆] lim T →∞ E b1∼b T 1 ,b2∼b T 2 [Rev(b 1 , b 2 ; r) | v 1 , v 2 ] E < E v1,v2∼U [B∆] min{v 1 , v 2 } E -c = E v1,v2∼U [B∆] [Rev(v 1 , v 2 ; r)| E] -c .Since Pr[E] > 0, the result follows by combining the two inequalities.Proof of Lemma 4.2. Letγ A = min i∈[n],v∈B∆,b-i∈B n-1 ∆ ,b∈B∆:b =v {u i (v, b -i ) -u i (b, b -i )} ,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 a strictly IC auction we have that γ A > 0. Consider any round t ∈ [T ] of the interaction.For any player i ∈ [n], we have thatu t (v i , b t -i ) -u t (b , b t -i ) ≥ γ A , ∀b = v i ,no matter what the bids b t -i are. Let δ 1 , . . . , δ n be the mean-based parameters of the algorithms that the agents are using. Moreover, letT 0 = max i∈[n] δ i • T /γ A . Notice that since δ i = o(1), ∀i ∈ [n],by picking T sufficiently large we have that T 0 < T. We immediately get that, for every playeri ∈ [n] T0 t=1 u t (v i , b t -i ) -u t (b , b t -i ) ≥ γ A • T 0 ≥ δ i • T, ∀b = v i ,no matter what the bid profile b t -i of the other bidders in every round is. Thus, for every bidder i ∈ [n], by taking a union bound over all bids b = v i , we see that in round T 0 + 1 the probability of not bidding truthfully is at most ∆ • δ i = o(1). Hence, we have shown the result.Proof of Theorem 4.4. Let δ , . . . , δ n 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 δ 1 is the slowest one, i.e., limT →∞ δi /δ1 ≤ C, ∀i ∈ [n],where C is some discretization-dependent constant. Let A be a strictly IC auction and defineγ A = min i∈[n],v∈B∆,b-i∈B n-1 ∆ ,b∈B∆:b =v { u i (v, b -i ) -u i (b, b -i )} .Similarly as in the previous proof, notice that γ A does not depend on T. Consider the q T -mixture of the auctions A, A and let us denote this auction by A . Let x, x, x be the allocation rules of A, A, A , respectively, and let us define the payment rules in a symmetric way. Notice that sincex (•) = q T x(•) + (1 -q T )x(•), p (•) = q T p(•) + (1 -q T )p(•), it follows immediately that γ A ≥ q T • γ A .Moreover, notice that|x (•) -x(•)| ≤ q T • | x(•) -x(•)| ≤ q T |p (•) -p(•)| ≤ q T • | p(•) -p(•)| ≤ q T .Let us focus on agent 1 since it is the one that has the slowest convergence. After T 0 rounds of the game we have thatT0 t=1 u t (v 1 , b t -1 ) -u t (b , b t -1 ) ≥ γ A • T 0 ≥ q T • γ A • T 0 , ∀b = v 1 ,no matter what the bid profile of 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 us the desired convergence we see that we need T 0 ≥ δ1•T /q T •γ A . Since T 0 ≤ T, this places a constraint on the choice of q T , namely that q T ≥ δ1 /γ A . Thus, since this is the only constraint that we have on the choice of q T we see that choosing q T = 2δ1 /γ A = o(1) suffices to get the result.Proof of Corollary 4.5. Let A be the output of Theorem 4.4 when the input auction is Myerson's revenue-optimal auction for F. For any fixed valuation profile v ∈ B n ∆ , for sufficiently large T, each bidder i ∈ [n] will be bidding v i except with probability o(1). Moreover, the payments in these two auctions differ by some o(1). Thus,E b1∼b T 1 ,...,bn∼b T n lim T →∞ Rev(A; b 1 , . . . , b n ) ≥ Rev(Myerson; v 1 , . . . , v n ) -o(1) .The result follows by taking the expectation over the random draw of v 1 , . . . , v n .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 T be the number of interactions. Assume that n agents use mean-based no-regret learning algorithms to bid in these repeated auctions. Then, there is an auction A such that• |x i (b) -x i (b)| = o(1), |p i (b) -p i (b)| = o(1), ∀i ∈ [n], ∀b ∈ B n ∆ .• In the meta-game that is induced by A every agent can gain at most o(1) utility by misreporting its value to the bidding algorithm.Proof of Corollary E.1. Let v 1 , . . . , v n be the values of the agents and let v1 , . . . , vn be the reports to the bidding algorithms. Let A be auction obtained by feeding the auction A into the transformation described in Theorem 4.4. The guarantees of this result show that• |x i (b) -x i (b)| = o(1), |p i (b) -p i (b)| = o(1), ∀i ∈ [n]∀b ∈ B ∆ , • Pr[b T i = vi ] = o(1), ∀i ∈ [n],where b T i is the bid of the i-th agent in round T. Thus, with high probability after a large enough number of rounds, for every agent i ∈ [n] the algorithm is bidding the reported value vi no matter what the other reports v-i are. Since the auction A is truthful, the utility of each agent is maximized when b T i = v i . Hence, the optimal strategy, up to o(1), is to reportv i = vi , ∀i ∈ [n].To be more formal, the expected utility of the i-th agent in round T isE u i (b T i , b T -i ) = u i (v i , v-i ) + o(1) , thus, since A is truthful, this quantity is maximized for vi = v i , up to the o(1) term.Proof of Proposition 5.1.Let A T = p T • A + (1 -p T ) • SPA,where A is some auction with γ A > 0 and some p T that will be defined shortly. Notice thatγ A T ≥ p T • γ A + (1 -p T ) • γ SPA ≥ p T • γ A .Since the bidders are mean-based no-regret learners, we know that whenT0 τ =1 v i • x i (v i , b τ ) -p i (v i , b τ ) ≥ T0 τ =1 v i • x i (b , b τ ) -p i (b , b τ ) + δ T • T, ∀i ∈ {0, 1}, ∀b ∈ B ∆ ,they will be bidding truthfully with probability at least 1 -∆ • η T . We know that in every roundv i • x i (v i , b τ ) -p i (v i , b τ ) ≥ v i • x i (b , b τ ) -p i (b , b τ ) + γ A T ≥ v i • x i (b , b τ ) -p i (b , b τ ) + p T • γ A , ∀i ∈ {0, 1}, b τ , b ∈ B 2 ∆ , b = v i Thus, we define T 0 = min{t ∈ N : p T • γ A • t ≥ δ T • T } = δ T •T /p T •γ A . The regret is Reg T (A T ; v L , v H ) = Reg T0 (A T ; v L , v H ) + T t=1 Rev(v L , v H ; SP) -E T t=T0+1 Rev(b t L , b t H ; A) ≤ v L • T 0 + v L • (T -T 0 ) • (2∆ • δ T ) • (1 -p T ) + (T -T 0 ) • p T • v L ≤ v L • (T 0 + 2∆ • δ T • T • (1 -p T ) + T • p T ) ≤ v L • δ T • T p T • γ A + 2∆ • δ T • T + p T • T ≤ v L • 2∆ • δ T • T p T • γ A + p T • T ,where the first inequality follows from the fact that after the first T 0 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) • 2∆ • η T , and the probability that auction is not SPA, which is p T . The rest of the inequalities are just algebraic manipulations. Thus, by setting p T = 2∆•δ T /γ A we get thatReg T (A T ; v L , v H ) ≤ v L • 3 • 2∆ • δ T γ A • T ,which concludes the proof.Proof of Proposition 5.2. Consider the v L , v H pairs of the form v H = v L + 1 /∆, such that both are bounded away from 0 and 1. Then, Myerson's payment formula shows that pH (v H , v L ) ≤ (v H -1 /∆) • x H (v H , v L ) = v L • x H (v H , v L ). We first argue that x H (v H , v L ) < 1. Indeed, suppose that x H (v H , v L ) = 1.Then the low type gets no signal about their bid and hence bids uniformly at random between [0, v L ]. In particular, with some C ∆ probability that is independent of T, the low type bids the value b L = v L /2. Now the only way for the auction A T to generate(v L -o(1)) revenue from such rounds is if x H (v H , v L /2)-x H (v L , v L /2) = 1-o(1). But if this is the case, then consider the valuation pair (v L /2, v L /2+ 1 /∆): the auctioneer allocates at most x H (v L /2+ 1 /∆, v L /2) ≤ o(1) per round, and gets almost no revenue from the high type. Moreover, the low type will generate at most v L /2 revenue, so the the regret of the auctioneer is at linear in T ; this gives the desired contradiction.Sincex H (v H , v L ) < 1, let q := 1 -x H (v H , v L ). Then, x L (v L , v H ) ≤ q and so u L (v L , v H ) - u L (v L -1 /∆, v H ) ≤ q • 1 /∆ ≤ q.In order to cancel the effect of the learning rate of η T , we need to wait for T 0 := Ω(1) /(q•η T ) rounds. For some C ∆ fraction of these T 0 rounds the agent of low type will bid v L /2, and an argument similar the previous paragraph shows that the revenue of the auction will be at least 1/∆ -o(1) less than v L . Thus, the regret in these T 0 rounds will be Ω(T 0 ), where we are hiding constants depending on ∆. Let us assume that after T 0 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 -T 0 ) • q). Summing up the two terms we get a regret of Ω ( 1 /(qηT ) + q • T -1 /η T ) . Since η T = Θ(1/ √ T ), this is Ω( √ T /q + qT - √ T ), which for any choice of q is Ω T 3/4 .Proof of Theorem 5.3. We will upper bound the auctioneer regret in the two epochs {1, . . . , T 0 }, and {T 0 + 1, . . . , T }, separately, where T 0 ∈ [T ] is a parameter of the design which we will define shortly. For the first epoch, we will use the simple upper bound of v L • T 0 .Let us consider the bid distribution of the two bidders after T 0 rounds. Since they are mean-based no-regret learners we know that ifT0 τ =1 v i • x i (v i , b τ ) -p i (v i , b τ ) ≥ T0 τ =1 v i • x i (b , b τ ) -p i (b , b τ ) + δ T • T, ∀i ∈ {1, 2}, ∀b ∈ B ∆ ,then, by a union bound over the possible bids, they will both be bidding truthfully with probability at least 1 -2∆ • η T .We know that in every round τ ∈ [T 0 ] we have thatv i • x i (v i , b τ ) -p i (v i , b τ ) ≥ v i • x i (b , b τ ) -p i (b , b τ ) + γ A , ∀i ∈ {0, 1}, b τ , b ∈ B 2 ∆ , b = v i .Therefore, we set T 0 = min{t ∈ N : t • γ A • t ≥ δ T • T } = δ T •T /γ A ., v H ) ≤ v L • T 0 + v L • (T -T 0 ) • 2∆ • η T ≤ v L • δ T • T γ A + v L • T • 2∆ • η T = O δ T • T • 1 γ A + ∆ ,where the first inequality follows from the fact that with probability at most 2∆ • η T one of the two bidders will not be truthful in the last (T -T 0 ) rounds, and the other inequalities are just algebraic manipulations.Proof of Proposition 5.4. It is not hard to see that in the setting we are working on the auctioneer cannot have negative auctioneer regret in any interval of the interaction. For instance, when v H = v L -1/∆, the SPA performs optimally. Since every A t , t ∈ [T ], is a truthful auction, Myerson's lemma shows thatu t i (v i , b -i )-u t i (b , b -i ) = vi z=b x t i (z, b -i )dz-(v i -b )•x t i (b , b -i ), ∀i ∈ {1, 2}, ∀v i , b , b -i ∈ B 3 ∆ , so for b = v i -1/∆ we get that u t i (v i , b -i ) -u t i (v i -1/∆, b -i ) ≤ 1 ∆ , ∀v i , b , b -i ∈ B 3 ∆ .Thus, in every iteration the utility gain of bidding v i is at most 1/∆ greater than bidding v i -1/∆. Summing up over the first T 0 iterations, we get thatT0 t=1 u t i (v i , b -i ) -u t i (v i -1/∆, b -i ) ≤ T 0 ∆ , ∀v i , b , b -i ∈ B 3 ∆ .Let us now shift our attention to the weights that MWU puts on v i -1/∆, v i , after T 0 iterations. We havePr[b T0 i = v i ] Pr[b T0 = v i -1/∆] = e η T T 0 t=1 (u t i (vi,b t -i )-u t i (vi-1/∆,b t -i ))≤ e η T • T 0 ∆ , so for T 0 = ∆ /η T we have thatPr[b T0 = v i -1/∆] ≥ Pr[b T0 i = v i ] e .This immediately implies thatPr[b t = v i -1/∆] ≥ Pr[b t i = v i ] e , ∀t ∈ [T 0 ] .Thus, the probability of bidding truthfully of both algorithms is bounded by 9/10. Thus, when v H = v L + 1/∆ when both bidders are not bidding truthfully the revenue loss compared to SPA is at least 1/∆. Putting it together, we can see that within the first T 0 rounds the total revenue loss compared to SPA is at leastC • 1 /∆ • T 0 = C • η T = C • √ T , for some absolute constant C > 0.Next, we show that the auction we defined in Definition 5.5 is optimal, in terms of its parameter γ A .Lemma F.1. In the setting with two bidders it holds that the optimal choice of the parameter γ A is Θ ( 1 /∆ 2 ) . Moreover, the auction defined in Definition 5.5 achieves that bound.Proof of Lemma F.1. Consider some auction A and fix the bid of the second bidder to be b ∈ B ∆ .Then, x 1 (•, b ) is a non-decreasing function, with 0 ≤ x 1 (b, b ) ≤ 1, ∀b ∈ B ∆ . Notice that for any consecutive bids, Myerson's lemma shows thatu 1 (b, b ) -u 1 (b -1/∆, b ) ≤ 1 /∆ • (x 1 (b, b ) -x 1 (b -1/∆, b )) .Since there are 1/∆ different b ∈ B ∆ and the function x 1 (•, b ) is monotone and bounded between [0, 1] we have b>0x 1 (b, b ) -x 1 (b -1/∆, b ) = x 1 (1, b ) -x 1 (0, b ) ≤ 1 ,and since there are 1/∆ terms in the summation, all of which are non-negative at least one of them must be at most1/∆. Let b * 1 ∈ B ∆ be such that x(b * 1 , b ) -x(b * -1/∆, b ) ≤ 1 ∆ . Then, picking v 1 = b * 1 witnesses that γ A ≤ 1 ∆ 2 .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-based no-regret algorithms such as EXP3 (Braverman et al., 2018) with η T = O(T 1/4 ). Notice that our positive results are stated for mean-based learners, so the guarantees hold in this setting as 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 5 there is a 1/n degradation to the auctioneer regret bound. When we are dealing with n bidders we can create a strictly IC auction A by building upon our "staircase auction" approach for two bidders in the following way: we select some bidder i ∈ [n] uniformly at random (independently of their bids) and then we allocate to bidder i with probability b i . Thus, for each bidder i ∈ [n] their allocation probability x i (b) is a linear function withx i (0) = 0, x i (1) = 1/n. Hence, Myerson's lemma shows that u i (v i )-u i (v i -1/∆) = Θ(1/(n∆ 2 )), thus, γ A = Θ(1/(n∆ 2 )).Recall that in the two-bidder case we have shown that this auction gives γ A = Θ(1/∆ 2 ), so the degradation in γ A 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 formv L = v, v H = v + 1/∆.Let us now consider a distributional setting where v 1 , v 2 are drawn from distributions D 1 , D 2 , and then the two bidders participate in repeated second-price auctions using MWU parametrized by these valuations. Similarly as in the prior-free setting, the goal of the auctioneer 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• E v1∼D1,v2∼D2 [min{v 1 , v 2 }], so this is the benchmark the auctioneer competes with (in this setting, we can modify the benchmark to be SPA with personalized reserves with the same arguments). If these distributions D 1 , D 2 , place some constant probability (i.e., independent of T ) on every element of {0, 1/∆, 2/∆, . . . , 1} then with some constant probability we will see a draw of the form v L = v, v H = v + 1/∆, so these pairs will be contributing a constant fraction of the expected revenue of the second-price auction, i.e., the term E v1∼D1,v2∼D2 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 a separate "Limitations" section in 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 on 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.This is where we are using the assumption that the runner-up type does not overbid. Otherwise, the argument can still go through with a different constant since we can show that the winning type will overbid only some O(η W T ) many times and we need to account for this term. 


Decision: 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!

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: I have a number of questions and concerns regarding the generality of the results and the presentation of the paper.

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.

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?
questions: 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: limitations: The limitations are discussed as the modeling assumptions are stated clearly.
paper_summary: paper_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.

The 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. 

Overall, 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.
strength_weakness: strength_weakness: See main review
questions: questions: See main review
limitations: limitations: See main review
paper_summary: paper_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.

Generalizing [Kolumbus and Nisan 2022a]'s results on second-price auctions with two equal-learning rate MWU bidders, the authors show that:

(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).

(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).

Then, 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.
strength_weakness: strength_weakness: (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.

(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).

I lean towards rejection for now due to the above concerns, but may change opinions based on the authors' response.
questions: questions: (Q1) What's the difference/improvement of this work compared to [Cai et al 2023]? (See W1)?

(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?

(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.

(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: limitations: **Suggestions:**

(1) Typo: Line 119, "in the prior-free"

(2) Typo: Line 237, "to a bidding truthfully"

(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)). 

(4) Line 372: "number of actions $\Delta$" -> "number of discretized bids $\Delta$"

(5) Typo: Line 388: "theoptimal"

(6) Line 559 in Theorem D.1: What is "NPT"?

(7) Typo: Line 608: "round $t$" -> " round $i$"

(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?
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: NA
limitations: limitations: NA

Comments: title: Response to the rebuttal
Happy with authors' response and raise rating to 6
comment: Thanks for your response.
I thank the authors for their detailed response. I am satisfied with the answers provided and keep my score as is.
My concerns are resolved by the authors' response and I raised rating to 6. 

Given authors' response to W1, I agree with the authors that this paper has a sufficient additional contribution to the literature. 

And thank you for clarifying my question Q2.  I completely agree that, in the revision, you should "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."  A formal proof is really needed since the devil is always in the details. 

Another minor suggestion regarding readability:  Since your Section 3 now only presents all results informally and redirect the reader to Appendix D, you might consider adding formal theorem statements there or pointing to the specific theorems (like Theorem D.2, D.3).
Thank you for the response! I will retain my current evaluation.