pith. sign in

arxiv: 1906.09331 · v1 · pith:CEAUZAF6new · submitted 2019-06-21 · 💻 cs.GT · cs.LG· stat.ML

Reserve Pricing in Repeated Second-Price Auctions with Strategic Bidders

Alexey Drutsa This is my paper

Pith reviewed 2026-05-25 18:05 UTC · model grok-4.3

classification 💻 cs.GT cs.LGstat.ML
keywords repeated second-price auctionsstrategic biddersreserve pricingregret boundslearning algorithmsmulti-buyer auctionsrevenue optimizationsingle to multi-buyer transformation
0
0 comments X

The pith

A novel transformation allows single-buyer reserve algorithms to handle multiple strategic bidders with O(log log T) strategic regret.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that a transformation can upgrade algorithms designed for a single buyer to the multi-buyer setting in repeated second-price auctions. This yields an algorithm with strategic regret bounded by O(log log T) even for worst-case fixed valuations of the bidders. A reader would care because strategic bidders in repeated interactions can manipulate their bids to affect future reserves, leading to potential revenue loss for the seller, and this method limits that loss to grow very slowly with time. The approach provides theoretical guarantees that learning the valuations remains possible despite the uncertainty introduced by competing bidders.

Core claim

The central claim is that there is a novel transformation that upgrades an algorithm for the single-buyer setup to the multi-buyer case, and the resulting pricing algorithm achieves a strategic regret upper bound of O(log log T) for worst-case valuations, while maintaining the ability to learn each strategic buyer's valuation despite their uncertainty about the future due to rivals.

What carries the argument

The novel transformation that upgrades a single-buyer algorithm to the multi-buyer case while preserving learning guarantees.

If this is right

  • The seller can optimize revenue in repeated auctions involving multiple strategic bidders using this upgraded algorithm.
  • The strategic regret remains bounded by O(log log T) regardless of the number of bidders or their fixed valuations.
  • The learning of valuations succeeds even when each buyer faces uncertainty from the presence of rivals.
  • Existing single-buyer algorithms can be extended to more realistic multi-buyer auction environments.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This method could potentially be adapted to other auction formats where strategic behavior occurs over repeated interactions.
  • In practice, it suggests that platforms can implement low-regret pricing strategies without needing to assume myopic bidders.
  • Testing the transformation on real auction data with multiple participants could validate its robustness beyond theoretical worst-case bounds.

Load-bearing premise

The transformation from single-buyer to multi-buyer algorithms preserves the ability to learn valuations despite each strategic buyer having uncertainty about the future due to the presence of rivals.

What would settle it

Running the algorithm in a simulated repeated auction with multiple strategic bidders holding fixed but unknown valuations and observing whether the cumulative strategic regret stays within O(log log T) or if valuation learning fails due to rival-induced uncertainty.

read the original abstract

We study revenue optimization learning algorithms for repeated second-price auctions with reserve where a seller interacts with multiple strategic bidders each of which holds a fixed private valuation for a good and seeks to maximize his expected future cumulative discounted surplus. We propose a novel algorithm that has strategic regret upper bound of $O(\log\log T)$ for worst-case valuations. This pricing is based on our novel transformation that upgrades an algorithm designed for the setup with a single buyer to the multi-buyer case. We provide theoretical guarantees on the ability of a transformed algorithm to learn the valuation of a strategic buyer, which has uncertainty about the future due to the presence of rivals.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper studies revenue optimization via reserve pricing in repeated second-price auctions involving multiple strategic bidders, each with a fixed private valuation who maximize expected discounted future surplus. It proposes a novel algorithm achieving O(log log T) strategic regret for worst-case valuations, obtained by a transformation that upgrades any single-buyer algorithm to the multi-buyer setting, together with theoretical guarantees that the transformed algorithm can still learn each buyer's valuation despite the additional uncertainty created by rivals.

Significance. If the single-to-multi-buyer transformation is shown to carry the O(log log T) bound without extra regret terms arising from inter-bidder strategic interactions, the result would be a substantial improvement over standard online-learning bounds in strategic mechanism design. The paper's explicit focus on preserving valuation-learning guarantees under rival-induced uncertainty is a strength that, if rigorously established, would advance the literature on low-regret pricing against strategic agents.

major comments (2)
  1. [Abstract] Abstract (paragraph on theoretical guarantees): the central claim that the novel transformation 'upgrades an algorithm designed for the setup with a single buyer to the multi-buyer case' while preserving O(log log T) strategic regret requires an explicit argument that the additional uncertainty each bidder faces about rivals' future actions does not introduce new regret terms or alter the information structure used in the single-buyer analysis; without this, the bound does not automatically carry over.
  2. [Abstract] The manuscript must identify the precise single-buyer algorithm being transformed and state the conditions under which the transformation preserves the regret bound; if the single-buyer algorithm itself relies on a particular information structure absent in the multi-buyer case, the O(log log T) guarantee is at risk.
minor comments (1)
  1. [Abstract] The abstract uses 'strategic regret' without a formal definition; a one-sentence definition or pointer to the section where it is defined would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address the major comments point by point below.

read point-by-point responses

  1. Referee: [Abstract] Abstract (paragraph on theoretical guarantees): the central claim that the novel transformation 'upgrades an algorithm designed for the setup with a single buyer to the multi-buyer case' while preserving O(log log T) strategic regret requires an explicit argument that the additional uncertainty each bidder faces about rivals' future actions does not introduce new regret terms or alter the information structure used in the single-buyer analysis; without this, the bound does not automatically carry over.

    Authors: We agree that the abstract would benefit from greater explicitness on this point. The manuscript's main body establishes that the transformation preserves the O(log log T) bound by showing that rival-induced uncertainty is controlled through the discounting and does not alter the single-buyer information structure used for valuation learning. We will revise the abstract to include a concise statement referencing this preservation argument. revision: yes

  2. Referee: [Abstract] The manuscript must identify the precise single-buyer algorithm being transformed and state the conditions under which the transformation preserves the regret bound; if the single-buyer algorithm itself relies on a particular information structure absent in the multi-buyer case, the O(log log T) guarantee is at risk.

    Authors: The transformation applies to any single-buyer algorithm achieving O(log log T) regret that relies only on observed bids for valuation estimation. The paper proves that the multi-buyer information structure satisfies the same conditions. We will revise the abstract to name the class of single-buyer algorithms and the preservation conditions. revision: yes

Circularity Check

0 steps flagged

No circularity: theoretical regret bound stands independently

full rationale

The provided abstract and description present the O(log log T) strategic regret bound and single-to-multi-buyer transformation as novel theoretical results with stated guarantees on valuation learning. No equations, parameter-fitting steps, self-definitional reductions, or load-bearing self-citations that collapse the central claim to its inputs are exhibited. The derivation chain is self-contained against external benchmarks as a mathematical guarantee rather than a fitted or renamed quantity.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only; no explicit free parameters, axioms, or invented entities are described. The transformation itself may implicitly rely on standard assumptions about bidder rationality and discounting that are not detailed here.

pith-pipeline@v0.9.0 · 5629 in / 1011 out tokens · 21820 ms · 2026-05-25T18:05:12.835889+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

78 extracted references · 78 canonical work pages · 5 internal anchors

  1. [1]

    Agarwal, S

    D. Agarwal, S. Ghosh, K. Wei, and S. You. Budget pacing for targeted online advertisements at linkedin. In KDD’2014, pages 1613–1619, 2014

    work page 2014

  2. [2]

    Aggarwal, G

    G. Aggarwal, G. Goel, and A. Mehta. Efficiency of (revenue-) optimal mechanisms. InEC’2009, pages 235–242, 2009

    work page 2009

  3. [3]

    Aggarwal, S

    G. Aggarwal, S. Muthukrishnan, D. Pál, and M. Pál. General auction mechanism for search advertising. In WWW’2009, pages 241–250, 2009

    work page 2009

  4. [4]

    Robust Repeated Auctions under Heterogeneous Buyer Behavior

    S. Agrawal, C. Daskalakis, V . Mirrokni, and B. Sivan. Robust repeated auctions under heterogeneous buyer behavior. arXiv preprint arXiv:1803.00494, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  5. [5]

    K. Amin, M. Kearns, and U. Syed. Bandits, query learning, and the haystack dimension. In COLT, pages 87–106, 2011

    work page 2011

  6. [6]

    K. Amin, A. Rostamizadeh, and U. Syed. Learning prices for repeated auctions with strategic buyers. In NIPS’2013, pages 1169–1177, 2013

    work page 2013

  7. [7]

    K. Amin, A. Rostamizadeh, and U. Syed. Repeated contextual auctions with strategic buyers. InNIPS’2014, pages 622–630, 2014

    work page 2014

  8. [8]

    Ashlagi, C

    I. Ashlagi, C. Daskalakis, and N. Haghpanah. Sequential mechanisms with ex-post participation guarantees. In EC’2016, 2016

    work page 2016

  9. [9]

    Ashlagi, B

    I. Ashlagi, B. G. Edelman, and H. S. Lee. Competing ad auctions. Harvard Business School NOM Unit Working Paper, (10-055), 2013

    work page 2013

  10. [10]

    Babaioff, S

    M. Babaioff, S. Dughmi, R. Kleinberg, and A. Slivkins. Dynamic pricing with limited supply. ACM Transactions on Economics and Computation, 3(1):4, 2015

    work page 2015

  11. [11]

    Balseiro, O

    S. Balseiro, O. Besbes, and G. Y . Weintraub. Dynamic mechanism design with budget constrained buyers under limited commitment. In EC’2016, 2016

    work page 2016

  12. [12]

    S. R. Balseiro, O. Besbes, and G. Y . Weintraub. Repeated auctions with budgets in ad exchanges: Approximations and design. Management Science, 61(4):864–884, 2015

    work page 2015

  13. [13]

    M. S. Baltaoglu, L. Tong, and Q. Zhao. Online learning of optimal bidding strategy in repeated multi- commodity auctions. In Advances in Neural Information Processing Systems, pages 4507–4517, 2017

    work page 2017

  14. [14]

    Bikhchandani

    S. Bikhchandani. Reputation in repeated second-price auctions.Journal of Economic Theory, 46(1):97–119, 1988

    work page 1988

  15. [15]

    Caillaud and C

    B. Caillaud and C. Mezzetti. Equilibrium reserve prices in sequential ascending auctions. Journal of Economic Theory, 117(1):78–95, 2004

    work page 2004

  16. [16]

    O. Carare. Reserve prices in repeated auctions. Review of Industrial Organization, 40(3):225–247, 2012

    work page 2012

  17. [17]

    L. E. Celis, G. Lewis, M. M. Mobius, and H. Nazerzadeh. Buy-it-now or take-a-chance: a simple sequential screening mechanism. In WWW’2011, pages 147–156, 2011

    work page 2011

  18. [18]

    Dynamic Pricing with Finitely Many Unknown Valuations

    N. Cesa-Bianchi, T. Cesari, and V . Perchet. Dynamic pricing with finitely many unknown valuations.arXiv preprint arXiv:1807.03288, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  19. [19]

    Cesa-Bianchi, C

    N. Cesa-Bianchi, C. Gentile, and Y . Mansour. Regret minimization for reserve prices in second-price auctions. In SODA’2013, pages 1190–1204, 2013

    work page 2013

  20. [20]

    Charles, N

    D. Charles, N. R. Devanur, and B. Sivan. Multi-score position auctions. In WSDM’2016, pages 417–425, 2016

    work page 2016

  21. [21]

    Chawla, N

    S. Chawla, N. R. Devanur, A. R. Karlin, and B. Sivan. Simple pricing schemes for consumers with evolving values. In SODA’2016, pages 1476–1490, 2016

    work page 2016

  22. [22]

    Chen and V

    Y . Chen and V . F. Farias. Robust dynamic pricing with strategic customers. InEC’2015, pages 777–777, 2015

    work page 2015

  23. [23]

    Chhabra and S

    M. Chhabra and S. Das. Learning the demand curve in posted-price digital goods auctions. In ICAAMS’2011, pages 63–70, 2011

    work page 2011

  24. [24]

    M. C. Cohen, I. Lobel, and R. Paes Leme. Feature-based dynamic pricing. In EC’2016, 2016

    work page 2016

  25. [25]

    A. V . den Boer. Dynamic pricing and learning: historical origins, current research, and new directions. Surveys in operations research and management science, 20(1):1–18, 2015. 10

    work page 2015

  26. [26]

    N. R. Devanur, Y . Peres, and B. Sivan. Perfect bayesian equilibria in repeated sales. InSODA’2015, pages 983–1002, 2015

    work page 2015

  27. [27]

    A. Drutsa. Horizon-independent optimal pricing in repeated auctions with truthful and strategic buyers. In WWW’2017, pages 33–42, 2017

    work page 2017

  28. [28]

    A. Drutsa. On consistency of optimal pricing algorithms in repeated posted-price auctions with strategic buyer. CoRR, abs/1707.05101, 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  29. [29]

    A. Drutsa. Weakly consistent optimal pricing algorithms in repeated posted-price auctions with strategic buyer. In ICML’2018, pages 1318–1327, 2018

    work page 2018

  30. [30]

    Dütting, M

    P. Dütting, M. Henzinger, and I. Weber. An expressive mechanism for auctions on the web. InWWW’2011, pages 127–136, 2011

    work page 2011

  31. [31]

    Feldman, T

    M. Feldman, T. Koren, R. Livni, Y . Mansour, and A. Zohar. Online pricing with strategic and patient buyers. In NIPS’2016, pages 3864–3872, 2016

    work page 2016

  32. [32]

    H. Fu, P. Jordan, M. Mahdian, U. Nadav, I. Talgam-Cohen, and S. Vassilvitskii. Ad auctions with data. In Algorithmic Game Theory, pages 168–179. Springer, 2012

    work page 2012

  33. [33]

    Fudenberg and J

    D. Fudenberg and J. M. Villas-Boas. Behavior-based price discrimination and customer recognition. Handbook on economics and information systems, 1:377–436, 2006

    work page 2006

  34. [34]

    Golrezaei, M

    N. Golrezaei, M. Lin, V . Mirrokni, and H. Nazerzadeh. Boosted second-price auctions for heterogeneous bidders. 2017

    work page 2017

  35. [35]

    Gomes and V

    R. Gomes and V . Mirrokni. Optimal revenue-sharing double auctions with applications to ad exchanges. In WWW’2014, pages 19–28, 2014

    work page 2014

  36. [36]

    O. D. Hart and J. Tirole. Contract renegotiation and coasian dynamics. The Review of Economic Studies, 55(4):509–540, 1988

    work page 1988

  37. [37]

    J. D. Hartline and T. Roughgarden. Simple versus optimal mechanisms. In Proceedings of the 10th ACM conference on Electronic commerce, pages 225–234. ACM, 2009

    work page 2009

  38. [38]

    D. He, W. Chen, L. Wang, and T.-Y . Liu. A game-theoretic machine learning approach for revenue maximization in sponsored search. In IJCAI’2013, pages 206–212, 2013

    work page 2013

  39. [39]

    Heidari, M

    H. Heidari, M. Mahdian, U. Syed, S. Vassilvitskii, and S. Yazdanbod. Pricing a low-regret seller. In ICML’2016, pages 2559–2567, 2016

    work page 2016

  40. [40]

    Huang, J

    Z. Huang, J. Liu, and X. Wang. Learning optimal reserve price against non-myopic bidders. In Advances in Neural Information Processing Systems, pages 2042–2052, 2018

    work page 2042

  41. [41]

    P. Hummel. Reserve prices in repeated auctions. International Journal of Game Theory, 47(1):273–299, 2018

    work page 2018

  42. [42]

    Hummel and P

    P. Hummel and P. McAfee. Machine learning in an auction environment. In WWW’2014, pages 7–18, 2014

    work page 2014

  43. [43]

    Immorlica, B

    N. Immorlica, B. Lucier, E. Pountourakis, and S. Taggart. Repeated sales with multiple strategic buyers. In EC’2017, pages 167–168, 2017

    work page 2017

  44. [44]

    K. Iyer, R. Johari, and M. Sundararajan. Mean field equilibria of dynamic auctions with learning. ACM SIGecom Exchanges, 10(3):10–14, 2011

    work page 2011

  45. [45]

    Kanoria and H

    Y . Kanoria and H. Nazerzadeh. Dynamic reserve prices for repeated auctions: Learning from bids. 2014

    work page 2014

  46. [46]

    Kleinberg and T

    R. Kleinberg and T. Leighton. The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In Foundations of Computer Science, pages 594–605, 2003

    work page 2003

  47. [47]

    V . Krishna. Auction theory. Academic press, 2009

    work page 2009

  48. [48]

    Lahaie, A

    S. Lahaie, A. M. Medina, B. Sivan, and S. Vassilvitskii. Testing incentive compatibility in display ad auctions. In WWW’2018, 2018

    work page 2018

  49. [49]

    R. P. Leme and J. Schneider. Contextual search via intrinsic volumes. arXiv preprint arXiv:1804.03195, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  50. [50]

    R. P. Leme, V . Syrgkanis, and É. Tardos. Sequential auctions and externalities. In SODA’2012, pages 869–886. SIAM, 2012

    work page 2012

  51. [51]

    T. Lin, J. Li, and W. Chen. Stochastic online greedy learning with semi-bandit feedbacks. In NIPS’2015, pages 352–360, 2015

    work page 2015

  52. [52]

    J. A. List and J. F. Shogren. Price information and bidding behavior in repeated second-price auctions. American Journal of Agricultural Economics, 81(4):942–949, 1999

    work page 1999

  53. [53]

    J. Mao, R. Leme, and J. Schneider. Contextual pricing for lipschitz buyers. In Advances in Neural Information Processing Systems, pages 5648–5656, 2018. 11

    work page 2018

  54. [54]

    A. M. Medina and S. Vassilvitskii. Revenue optimization with approximate bid predictions. In NIPS’2017, pages 1856–1864, 2017

    work page 2017

  55. [55]

    Mirrokni, R

    V . Mirrokni, R. Paes Leme, P. Tang, and S. Zuo. Non-clairvoyant dynamic mechanism design. 2017

    work page 2017

  56. [56]

    Mirrokni, R

    V . Mirrokni, R. Paes Leme, P. Tang, and S. Zuo. Optimal dynamic auctions are virtual welfare maximizers. Available at SSRN, 2018

    work page 2018

  57. [57]

    Mohri and A

    M. Mohri and A. M. Medina. Learning theory and algorithms for revenue optimization in second price auctions with reserve. In ICML’2014, pages 262–270, 2014

    work page 2014

  58. [58]

    Mohri and A

    M. Mohri and A. M. Medina. Non-parametric revenue optimization for generalized second price auctions. In UAI’2015, 2015

    work page 2015

  59. [59]

    Mohri and A

    M. Mohri and A. Munoz. Optimal regret minimization in posted-price auctions with strategic buyers. In NIPS’2014, pages 1871–1879, 2014

    work page 2014

  60. [60]

    J. H. Morgenstern and T. Roughgarden. On the pseudo-dimension of nearly optimal auctions. InNIPS’2015, pages 136–144, 2015

    work page 2015

  61. [61]

    R. B. Myerson. Optimal auction design. Mathematics of operations research, 6(1):58–73, 1981

    work page 1981

  62. [62]

    Nisan, T

    N. Nisan, T. Roughgarden, E. Tardos, and V . V . Vazirani.Algorithmic game theory, volume 1. v.1 CUPC, 2007

    work page 2007

  63. [63]

    Ostrovsky and M

    M. Ostrovsky and M. Schwarz. Reserve prices in internet advertising auctions: A field experiment. In EC’2011, pages 59–60, 2011

    work page 2011

  64. [64]

    Paes Leme, M

    R. Paes Leme, M. Pál, and S. Vassilvitskii. A field guide to personalized reserve prices. InWWW’2016, 2016

    work page 2016

  65. [65]

    Peters and S

    M. Peters and S. Severinov. Internet auctions with many traders. Journal of Economic Theory, 130(1):220– 245, 2006

    work page 2006

  66. [66]

    Roughgarden and J

    T. Roughgarden and J. R. Wang. Minimizing regret with multiple reserves. In EC’2016, pages 601–616, 2016

    work page 2016

  67. [67]

    M. R. Rudolph, J. G. Ellis, and D. M. Blei. Objective variables for probabilistic revenue maximization in second-price auctions with reserve. In WWW’2016, 2016

    work page 2016

  68. [68]

    K. M. Schmidt. Commitment through incomplete information in a simple repeated bargaining game. Journal of Economic Theory, 60(1):114–139, 1993

    work page 1993

  69. [69]

    Y . Sun, Y . Zhou, and X. Deng. Optimal reserve prices in weighted gsp auctions.Electronic Commerce Research and Applications, 13(3):178–187, 2014

    work page 2014

  70. [70]

    D. R. Thompson and K. Leyton-Brown. Revenue optimization in the generalized second-price auction. In EC’2013, pages 837–852, 2013

    work page 2013

  71. [71]

    Optimal Pricing in Repeated Posted-Price Auctions

    A. Vanunts and A. Drutsa. Optimal pricing in repeated posted-price auctions. arXiv preprint arXiv:1805.02574, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  72. [72]

    H. R. Varian. Position auctions. international Journal of industrial Organization, 25(6):1163–1178, 2007

    work page 2007

  73. [73]

    H. R. Varian. Online ad auctions. The American Economic Review, 99(2):430–434, 2009

    work page 2009

  74. [74]

    H. R. Varian and C. Harris. The vcg auction in theory and practice. The A.E.R., 104(5):442–445, 2014

    work page 2014

  75. [75]

    J. Weed, V . Perchet, and P. Rigollet. Online learning in repeated auctions. JMLR, 49:1–31, 2016

    work page 2016

  76. [76]

    S. Yuan, J. Wang, B. Chen, P. Mason, and S. Seljan. An empirical study of reserve price optimisation in real-time bidding. In KDD’2014, pages 1897–1906, 2014

    work page 2014

  77. [77]

    Y . Zhu, G. Wang, J. Yang, D. Wang, J. Yan, J. Hu, and Z. Chen. Optimizing search engine revenue in sponsored search. In SIGIR’2009, pages 588–595, 2009

    work page 2009

  78. [78]

    Zoghi, Z

    M. Zoghi, Z. S. Karnin, S. Whiteson, and M. De Rijke. Copeland dueling bandits. In NIPS’2015, pages 307–315. A Missed proofs A.1 Missed proofs from Section 3 A.1.1 Proof of Lemma 1 Proof. Let Im = {tm i }Im i=1 be the set of rounds in which the bidder m is not eliminated by a barrage re- serve pricing. Therefore, we have decomposition of the sequence of a...

    work page 2015