{"id":"514e9e1e-e8fc-4f33-8060-851e5eb7f75f","arxiv_id":"2411.09517","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Randomized truthful auctions can restore truthful bidding by learning agents and strictly outperform second-price auctions with reserves, with auctioneer regret roughly T^(3/4) for fixed auctions and roughly sqrt(T) for scheduled ones.","lead":"This paper studies repeated auctions in which bidders use no-regret learning algorithms, and shows that deterministic truthful auctions generally fail to make the runner-up bidder learn to bid truthfully, while randomized truthful auctions can fix that and improve revenue. It also gives near-tight revenue regret bounds: about T^3/4 for a fixed auction rule, and about the square root of T if the auctioneer can switch rules once.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 5.2's Ω(T^{3/4}) lower-bound proof is incomplete: its 'linear regret' contradiction does not follow, because revenue at most v_L/2 does not imply regret when the benchmark is v_L/2; the low bidder's no-signal learning dynamics are essential but unanalyzed.","rationale":"The paper's central conceptual message—that deterministic truthful auctions fail to induce truthful convergence whereas randomized strictly-IC auctions restore it, and hence can asymptotically match Myerson revenue while SPA with reserve cannot—is supported by detailed proofs (Theorems D.3, 4.4, Corollary 4.5, Theorem 3.1) that, despite minor typos, appear largely sound. The persistent-valuation and no-overbidding assumptions are explicitly stated and limit scope, but do not create internal inconsistency; they are not the most load-bearing risk. The weakest point is the non-asymptotic lower bound, where the appendix proof contains a logical gap. The reader's rationale noted that Proposition 5.2 is only sketched; this stress-test sharpens that point: the specific 'contradiction' used to force linear regret is invalid as stated. A completed proof may well exist, which is why the appropriate verdict is CONDITIONAL rather than REJECT: accept once the lower-bound argument is made rigorous. The Ω(√T) lower bound (Proposition 5.4) also has sketchy steps but is less central; the T^{3/4} bound is the headline non-asymptotic result and should be verified before the paper's finite-time claims are accepted.","tokens_in":26471,"tokens_out":20862,"duration_ms":175044,"concrete_test":"Complete the second half of the Proposition 5.2 proof: for the valuation pair (v_L/2, v_L/2+1/∆), write out the low bidder's MWU update when its utility is identically zero for all bids, and prove algebraically that the auction's expected per-round revenue falls short of v_L/2 by a positive constant on a constant fraction of rounds. Equivalently, exhibit a truthful allocation rule satisfying x_H(v_H, v_L/2)=1 and x_H(v_L, v_L/2)=0, and compute its auctioneer regret; if a rule achieves o(T^{3/4}) regret, the proposition is false.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The most load-bearing concern is the proof of Proposition 5.2 (Appendix F), which underpins the claimed almost-tight Θ̃(T^{3/4}) bound for constant auction policies. The proof considers pairs v_H = v_L + 1/∆ and argues that if x_H(v_H, v_L) = 1, the low type gets no signal and bids uniformly, so it bids v_L/2 with constant probability. It then says the only way to get revenue v_L−o(1) in those rounds is x_H(v_H, v_L/2)−x_H(v_L, v_L/2)=1−o(1). For the valuation pair (v_L/2, v_L/2+1/∆), it notes the high type's allocation is o(1), 'the low type will generate at most v_L/2 revenue, so the regret is linear in T.' This inference is invalid: the SPA benchmark for that pair is exactly v_L/2, so revenue equal to v_L/2 gives zero regret, not linear regret. To obtain linear regret one must show the low type actually produces revenue strictly below v_L/2 on a constant fraction of rounds. That requires analyzing the low bidder's MWU dynamics in the second pair, where its utility may again be identically zero; such an analysis is absent. The deficiency is not a cosmetic typo: as written, the contradiction does not follow. Since Proposition 5.2 is explicitly advertised as the almost-tight lower bound for fixed auctions, this is a genuine gap in the paper's non-asymptotic results.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies repeated single-item truthful auctions in which two bidders have persistent private values drawn once from a discrete regular distribution and bid via mean-based no-regret learning algorithms under a no-overbidding assumption. The main results are: (i) a characterization of last-iterate bidding in deterministic truthful auctions, showing that the runner-up bidder fails to converge to truthful bidding unless its learning rate is strictly faster than the winner's (Theorem D.3 and Theorem D.4); (ii) a black-box transformation from any IC auction to a strictly-IC randomized auction whose allocation and payment rules are o(1)-close to the original and under which all mean-based learners converge to truthful bidding (Theorem 4.4), yielding revenue at least the Myerson revenue minus o(1) (Corollary 4.5) and hence a strict asymptotic revenue improvement over SPA with reserves; and (iii) a non-asymptotic prior-free analysis introducing an 'auctioneer regret' benchmark against truthful SPA, with an almost tight ~Theta(T^{3/4}) bound for a fixed auction (Propositions 5.1 and 5.2) and an almost tight ~Theta(sqrt(T)) bound when the auction can be switched once oblivious to the bids (Theorem 5.3 and Proposition 5.4).","tokens_in":26790,"tokens_out":18907,"duration_ms":184931,"significance":"If the results are correct, the paper makes a substantive contribution to the literature on learning agents in auctions. The phase transition in the ratio of learning rates generalizes Kolumbus and Nisan; the strictly-IC randomization principle is an elegant and potentially useful design tool; and the auctioneer-regret framework gives a clean way to quantify the finite-horizon revenue cost of learning. The asymptotic proofs are detailed, with explicit epoch arguments, Chernoff bounds, and union-bound accounting, and the positive convergence results are stated for the broad class of mean-based learners. The paper is also honest about its modeling assumptions, explicitly contrasting persistent valuations with the i.i.d.-valuations setting of Feng et al. and flagging the role of the no-overbidding assumption.","major_comments":[{"comment":"The contradiction step in the proof of Proposition 5.2 is invalid as written. For the valuation pair (v_L/2, v_L/2 + 1/Delta), the second-price benchmark is exactly v_L/2. The sentence 'the low type will generate at most v_L/2 revenue, so the regret of the auctioneer is linear in T' does not follow: revenue equal to v_L/2 yields zero regret against this benchmark. To obtain linear regret one must show that the low type bids strictly below v_L/2 (for example, v_L/2 - 1/Delta) with constant probability on a constant fraction of the rounds in the second valuation pair, which requires analyzing the low bidder's MWU dynamics under the allocation and payment rules of A_T. That analysis is absent. Because Proposition 5.2 supplies the lower bound for the advertised ~Theta(T^{3/4}) characterization of constant auction policies, this gap is load-bearing for the paper's non-asymptotic claims.","section":"Appendix F, Proposition 5.2"}],"minor_comments":[{"comment":"The phrase 'no truthful auction can achieve an auctioneer-regret better than ~O(T^{3/4})' is misleading; Proposition 5.2 proves a lower bound of Omega(T^{3/4}), so the text should say 'better than ~Omega(T^{3/4})' or 'of order o(T^{3/4})'.","section":"Section 5, paragraph before Proposition 5.2"},{"comment":"The theorem statement says 'there exists an auction A''', but the proof constructs a family of auctions indexed by T through the choice q_T = 2*delta_1/gamma_{~A}. The statement should make this horizon dependence explicit, since the allocation and payment rules change with T.","section":"Theorem 4.4 and its proof"},{"comment":"The title 'No Deterministic Auction Leads to Truthful Bidding' is stronger than the theorem's content: the theorem itself permits the runner-up to converge to truthful bidding when eta_R/eta_W = omega(1). A more qualified title or a clarifying remark would avoid the impression of a universal impossibility.","section":"Theorem D.3"},{"comment":"The revenue-loss step should be stated more carefully. The displayed ratio bound gives a constant lower bound on Pr[b_t = v_i - 1/Delta] only after using the uniform initialization and the weak dominance of v_i, and the relevant event for revenue loss is the low bidder's bidding below v_L, not 'both bidders are not bidding truthfully' as an event. Please spell out this argument.","section":"Appendix F, Proposition 5.4"}],"recommendation":"major_revision","confidential_remarks":"The paper is a good fit for a theory journal and I saw no attribution or scope concerns. The asymptotic sections are the strongest part of the paper. The main issue is the lower-bound proof for the constant-auction case, which needs a genuinely new analysis rather than a cosmetic correction; if the authors can supply that analysis, the paper would be suitable for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this paper earns its keep on the asymptotic side, and it has a genuine hole in the finite-horizon lower bound. The generalization of Kolumbus–Nisan from second-price to all deterministic truthful auctions is a solid extension, and the phase transition driven by the ratio of learning rates is a nice qualitative finding. The strictly-IC auction concept and the black-box transformation that makes any IC auction o(1)-close to a strictly-IC one while preserving revenue are the clearest contributions. Those results are proved carefully, and the revenue corollary—randomized auctions beat SPA-with-reserve in this learning setting—is a genuine surprise worth knowing about.\n\nThe soft spot is Proposition 5.2, the Ω(T^{3/4}) lower bound for constant auction policies. The proof in Appendix F is a sketch, not a proof, and the stress-test hits a real logical gap. The argument says that for the valuation pair (v_L/2, v_L/2+1/∆), the low type generates at most v_L/2 revenue, so regret is linear. But the SPA benchmark for that pair is exactly v_L/2. Revenue equal to v_L/2 is zero regret, not linear regret. To get linear regret you need the low type to produce revenue strictly below v_L/2 on a constant fraction of rounds, and that requires analyzing the low bidder's no-signal learning dynamics, which the proof does not do. This is not a typo-level issue; the contradiction as written does not follow. There are also several small typos in the proof equations, but those are minor by comparison.\n\nTo be fair, the paper itself flags that Section 5 is a prior-free non-asymptotic analysis, and the lower bound is the linchpin of the claimed Θ(T^{3/4}) tightness. The upper bounds, including the clever two-epoch schedule that switches once from a strictly-IC auction to SPA, appear sound. The model assumptions—persistent valuations, no overbidding, mean-based learners—are explicit and the paper is honest about scope, including the contrast with i.i.d. redrawn valuations.\n\nWho is this for? Anyone working on learning aggggents in auctions, especially the intersection of mechanism design and no-regret dynamics. The asymptotic results are ready to cite. The lower bound needs repair before I would trust the finite-horizon statements. I would send this to a serious referee: the core ideas are important and mostly well-executed, and a competent referee can either fix the lower-bound gap or guide the authors to a corrected statement.","headline":"The strictly-IC construction and asymptotic revenue restoration are real contributions worth citing, but the advertised Ω(T^{3/4}) lower bound for constant auctions is not proven as written.","tokens_in":27327,"tokens_out":1529,"would_cite":true,"duration_ms":17927,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B26","91A26"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper shows that randomizing a truthful auction makes no-regret learning bidders converge to truthful bidding, restoring near-optimal revenue where deterministic auctions fail.","keywords":["repeated auctions","no-regret learning","mean-based learners","truthful auctions","randomized mechanisms","revenue maximization","auctioneer regret","last-iterate convergence"],"falsifier":"Simulate two multiplicative-weights bidders with equal learning rates and fixed values in a repeated second-price auction; if the lower-valued bidder's last-round bid distribution converges to its value, the claimed non-convergence for deterministic truthful auctions is refuted. Equivalently, a strictly-IC randomized auction whose last-iterate bids do not approach values would refute the convergence lemma.","tokens_in":26256,"feed_emoji":"🎲","tokens_out":11454,"duration_ms":98453,"temperature":0.7,"pith_summary":"Automated bidding agents that run no-regret learning algorithms in repeated auctions do not automatically learn to bid their true values. This paper establishes that when a bidder's valuation is fixed over the whole interaction, no deterministic truthful auction can in general make the losing bidder converge to truthful bidding; the loser's expected bid stays strictly below its value unless its learning rate is strictly faster than the winner's. The constructive answer is randomization: a strictly incentive-compatible randomized auction gives truthful bidding a strictly positive utility margin, so every mean-based learner's last-iterate bid distribution converges to the true value. Because any truthful auction can be mixed with a small strictly-IC auction at $o(1)$ distortion of allocation and payments, randomized auctions can match the classical optimal-auction revenue benchmark up to $o(1)$, while second-price auctions with reserves lose a constant gap. In finite horizons the same machinery yields auctioneer-regret bounds of $\\widetilde{\\Theta}(T^{3/4})$ for a fixed auction rule and $\\widetilde{\\Theta}(\\sqrt{T})$ when the auctioneer switches once to the second-price auction.","feed_headline":"Randomizing auctions makes learning bidders bid truthfully","feed_subtitle":"With stable valuations, deterministic auctions lose revenue; randomizing restores truthful bidding and near-optimal revenue.","key_machinery":"The load-bearing object is the strictly incentive-compatible (strictly-IC) auction: a randomized truthful auction in which, for every bidder, every valuation, and every profile of others' bids, bidding the true value beats every other bid by a strictly positive utility margin, written $\\gamma_A$. The mean-based property of the learners—if one bid has outperformed another by more than $\\delta T$, the worse bid is played with probability at most $\\delta$—converts this per-round margin into last-iterate convergence to truthful bidding. The central construction is a mixture $q \\cdot A + (1-q) \\cdot A'$ of any truthful auction $A$ with a strictly-IC auction $A'$, where $q = o(1)$; the mixture stays truthful, is $o(1)$-close to $A$ in allocation and payments, and forces convergence. For finite horizons the paper uses a particular strictly-IC auction, the staircase auction, whose margin is $\\gamma_A = \\Theta(1/\\Delta^2)$, to control convergence speed and bound the auctioneer regret.","core_discovery":"The central claim is that the failure of no-regret bidders to bid truthfully in repeated second-price auctions is a general property of deterministic truthful auctions, not a quirk of that format. In any nondegenerate deterministic auction, when the runner-up's learning rate is no faster than the winner's, the runner-up's bids converge to a distribution whose mean is strictly below its true value; when the runner-up learns strictly faster, it converges to truthful bidding. This phase transition implies a negative revenue result: with learning bidders, the second-price auction with a reserve generates strictly less revenue than the rational-bidder benchmark. The paper's positive result is a black-box transformation: any truthful auction can be perturbed by adding a $o(1)$-weighted strictly-IC randomized auction, and in the perturbed auction every mean-based no-regret learner converges to truthful bidding in the last-iterate sense, so the auction's revenue approaches the revenue-optimal benchmark up to $o(1)$.","pith_inferences":["The same mix-in-a-strictly-IC-auction recipe should apply to any dominant-strategy mechanism with discrete types, not just single-item auctions, forcing last-iterate truthful play at negligible distortion for mean-based learners.","The near-optimality of an explore-then-exploit schedule suggests that in environments with persistent bidder rankings, separating a truth-learning phase from a revenue phase can beat the interleaved exploration usually recommended in bandit settings.","The paper's conceptual diagnosis—that stability of bidder rankings drives non-convergence—predicts that settings with slowly drifting valuations should also benefit from randomized perturbation; a testable extension would add small valuation drift and check whether the runner-up still underbids.","The convergence guarantee is specific to mean-based no-regret learners; running the proposed schedules with non-mean-based learners such as Q-learning is a natural stress test and is not covered by the theorems."],"forward_implications":["In any deterministic truthful auction where the winner and the runner-up learn at comparable rates, the runner-up's limiting bid distribution has expectation strictly below its value, so revenue is permanently below the truthful-bid benchmark.","Randomized strictly-IC auctions make mean-based no-regret bidders converge to truthful bidding in the last-iterate sense for every choice of learning rates, eliminating the learning-rate phase transition.","The $o(1)$-mixture transformation converts any truthful auction, including the revenue-optimal one, into an auction with the same allocation and payments up to $o(1)$ and with revenue approaching the optimal-auction revenue as $T \\to \\infty$.","An auctioneer limited to one auction rule for all $T$ rounds cannot beat $\\widetilde{\\Theta}(T^{3/4})$ auctioneer regret, but switching once from a strictly-IC auction to the second-price auction achieves $\\widetilde{\\Theta}(\\sqrt{T})$ regret.","In the game where agents choose what value to report to their own bidding algorithm, reporting the true value is optimal up to $o(1)$ after the transformation, because every algorithm converges to bidding its reported value."],"supporting_citations":[{"why":"Shows that in repeated second-price auctions with equal learning rates the runner-up bidder does not converge to truthful bidding; this is the baseline phenomenon the paper generalizes to all deterministic truthful auctions.","marker":"Kolumbus and Nisan (2022a)"},{"why":"Defines the mean-based no-regret learning class used throughout and shows that without a no-overbidding restriction an auctioneer can extract full welfare, motivating the paper's assumption.","marker":"Braverman et al. (2018)"},{"why":"Establishes the second-price auction with reserve as the revenue-optimal truthful auction for rational bidders, the benchmark the paper compares learning-bidder revenue against.","marker":"Myerson (1981)"},{"why":"Supplies the characterization of truthful deterministic single-item auctions with monotone allocation and threshold payments used in the proof of the deterministic non-convergence result.","marker":"Roughgarden (2010)"},{"why":"Shows that when valuations are freshly drawn each round, second-price bidders converge to truthful bidding; this contrast isolates persistent valuations as the driver of the negative results.","marker":"Feng et al. (2021)"},{"why":"Shows that welfare can be extracted when bidders overbid, which is why the paper restricts attention to bidders that never bid above their value.","marker":"Cai et al. (2023)"}],"fun_headline_variants":["Randomization makes learning bidders truthful","For learning bidders, randomized beats deterministic auctions","Deterministic auctions fail, randomization restores truthful bids","Randomized auctions fix learning bidders' truthful bidding","Learning agents need random auctions to bid truthfully"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument depends on both bidders' valuations remaining fixed for all $T$ rounds and on bidders never bidding above their value; dropping either assumption makes the negative results and the revenue comparison break down.","fun_headline_variants_meta":{"raw":{"variants":["Randomization makes learning bidders truthful","For learning bidders, randomized beats deterministic auctions","Deterministic auctions fail, randomization restores truthful bids","Randomized auctions fix learning bidders' truthful bidding","Learning agents need random auctions to bid truthfully"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000408,"raw_usage":{"total_tokens":2175,"prompt_tokens":1060,"completion_tokens":1115,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":676,"completion_tokens_details":{"reasoning_tokens":1040}},"tokens_in":676,"tokens_out":1115,"duration_ms":8444,"temperature":1.0,"reasoning_tokens":1040,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T20:34:37.189045+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate two multiplicative-weights bidders with equal learning rates and fixed values in a repeated second-price auction; if the lower-valued bidder's last-round bid distribution converges to its value, the claimed non-convergence for deterministic truthful auctions is refuted. Equivalently, a strictly-IC randomized auction whose last-iterate bids do not approach values would refute the convergence lemma.","supporting_citations":[],"review_version":1}