pith. sign in

arxiv: 2606.01142 · v1 · pith:DSR7DDU4new · submitted 2026-05-31 · 💻 cs.GT · cs.DS

Repeated Descent: A Framework for Online Budget-Feasible Auctions

Andreas Charalampopoulos , Dimitris Fotakis , Thanos Tolias This is my paper

Pith reviewed 2026-06-28 16:37 UTC · model grok-4.3

classification 💻 cs.GT cs.DS
keywords budget feasible auctionsonline posted-price mechanismssubmodular valuationssecretary arrivalscompetitive analysisprocurement auctionsadaptive pricingnon-monotone submodular
0
0 comments X

The pith

Repeated Descent gives a 1/046-competitive posted-price mechanism for online budget-feasible submodular auctions under random arrivals.

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

The paper presents Repeated Descent as a deterministic framework that uses adaptive linear posted pricing to handle budget constraints in procurement auctions. Agents arrive in random order and the mechanism posts prices without learning individual costs beyond accept or reject decisions. If the central claim holds, this yields a competitive ratio of 1/046 for submodular valuations, a large improvement over earlier bounds, and extends to constant competitiveness for non-monotone submodular functions via random subsampling. A reader would care because the result makes online budget-constrained hiring or procurement noticeably more efficient in settings where full information is unavailable. The paper also proves an Omega(log n over (log log n) squared) lower bound for XOS valuations.

Core claim

Using RED as the main building block, the paper obtains a 1/046-competitive posted-price mechanism for online budget feasible auctions with secretary agent arrivals and submodular valuations, improving on the previously best known ratio by several orders of magnitude. Combining RED with random subsampling produces the first constant-competitive posted-price budget feasible mechanism for non-monotone submodular valuations. On the negative side, every online budget feasible mechanism with XOS valuations has competitive ratio Omega(log n over (log log n) squared).

What carries the argument

Repeated Descent (RED), a deterministic framework based on adaptive linear posted pricing that enforces budget feasibility by adaptively adjusting pricing levels and balancing each level with the number of agents considered.

If this is right

  • The 1/046 ratio applies directly to secretary-arrival procurement with submodular public valuations.
  • Random subsampling yields the first constant-competitive posted-price mechanism for non-monotone submodular cases.
  • No online posted-price mechanism for XOS valuations can beat Omega(log n over (log log n) squared) competitiveness.
  • The balancing technique inside RED can be reused as a modular component for other online budget problems.

Where Pith is reading between the lines

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

  • The framework may extend to mildly adversarial arrival orders if the balancing step is adjusted with limited lookahead.
  • Similar descent methods could be tested on multi-dimensional budgets or matroid constraints beyond the single budget case.
  • In practice the ratio improvement suggests higher value extraction in crowdsourcing platforms that already use posted prices.
  • One could measure the typical-case ratio on random submodular instances to see how far the worst-case bound is from observed performance.

Load-bearing premise

Agents arrive in uniformly random order and the mechanism receives no feedback on service costs beyond acceptance or rejection of the posted price.

What would settle it

A concrete submodular valuation instance together with a cost vector and arrival order where the mechanism's total value is less than 1/046 of the optimal offline solution under the same budget would falsify the claimed ratio.

read the original abstract

We study budget feasible procurement auctions, in which $n$ agents, each with a privately held service cost, offer their services to an employer. The employer seeks to maximize a public submodular valuation function over the set of hired agents, while facing a hard budget constraint. We consider an online posted-price setting, in which agents arrive in a uniformly random order (a.k.a. \emph{secretary arrivals}) and the employer must make irrevocable take-it-or-leave-it offers upon their arrival. The employer does not get any feedback about the agent service costs other than whether they accept the offer or not. We introduce Repeated Descent (a.k.a. \RED), a deterministic framework based on adaptive linear posted pricing. \RED enforces budget feasibility by adaptively adjusting its pricing and balancing each pricing level with the number of agents considered in it. Using \RED as the main building block, we obtain a $1046$-competitive posted-price mechanism for online budget feasible auctions with secretary agent arrivals and submodular valuations, thus improving on the previously best known ratio of (Charalampopoulos et al., EC 2025) by several orders of magnitude. Combining \RED with random subsampling, we obtain the first constant-competitive posted-price budget feasible mechanism for non-monotone submodular valuations. On the negative side, we show that every online budget feasible mechanism with XOS valuations has a competitive ratio of $\Omega\!\left(\tfrac{\log n}{(\log\log n)^2}\right)$.

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

0 major / 3 minor

Summary. The paper introduces Repeated Descent (RED), a deterministic adaptive linear posted-price framework for online budget-feasible procurement auctions under secretary arrivals with no cost feedback beyond accept/reject. Using RED as the core building block, the authors derive a 1046-competitive mechanism for submodular valuations (improving prior work by orders of magnitude), combine it with random subsampling to obtain the first constant-competitive posted-price mechanism for non-monotone submodular valuations, and prove an Ω(log n / (log log n)^2) lower bound for any online budget-feasible mechanism with XOS valuations.

Significance. If the stated competitive ratios and lower bound hold, the work marks a substantial advance in online mechanism design for budget-feasible settings. The improvement from prior ratios to 1046 for submodular valuations, together with the extension to non-monotone cases, would make posted-price mechanisms far more viable in this model. The explicit handling of the no-feedback constraint and the XOS lower bound are also valuable.

minor comments (3)
  1. [Abstract, §1] Abstract and §1: the notation '1046-competitive' should be clarified as achieving at least OPT/1046 (standard in the literature) and the exact prior ratio from Charalampopoulos et al. (EC 2025) should be stated numerically for direct comparison.
  2. [§3] The analysis of RED in the submodular case relies on balancing pricing levels against the number of agents considered; a short intuitive example or small-n illustration would help readers follow the adaptive adjustment before the full proof.
  3. [§4] The random-subsampling extension for non-monotone submodular valuations is stated to yield a constant ratio; the dependence of the constant on the subsampling probability should be made explicit.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our paper and the recommendation for minor revision. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper introduces the new RED framework as the main building block for deriving the 1/046-competitive ratio via adaptive linear posted pricing under secretary arrivals. The citation to Charalampopoulos et al. (EC 2025) is used solely to benchmark the improvement and is not part of the derivation chain for the new result. No self-definitional elements, fitted inputs presented as predictions, or load-bearing self-citations appear in the stated construction or lower bound. The derivation is self-contained against the model assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Review based on abstract only; no free parameters, invented entities, or non-standard axioms are visible.

axioms (2)
  • domain assumption Valuations are submodular (or XOS for the lower bound)
    Explicitly stated as the setting for the positive and negative results.
  • domain assumption Agents arrive in uniformly random order
    Secretary-arrivals model is the core arrival assumption.

pith-pipeline@v0.9.1-grok · 5810 in / 1268 out tokens · 26065 ms · 2026-06-28T16:37:20.525213+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

126 extracted references · 15 canonical work pages

  1. [1]

    Abril and Robert Plant

    Patricia S. Abril and Robert Plant. The patent holder's dilemma: Buy, sell, or troll?. Communications of the ACM. 2007. doi:10.1145/1188913.1188915

    work page doi:10.1145/1188913.1188915 2007

  2. [2]

    Deciding equivalances among conjunctive aggregate queries

    Sarah Cohen and Werner Nutt and Yehoshua Sagic. Deciding equivalances among conjunctive aggregate queries. 2007. doi:10.1145/1219092.1219093

    work page doi:10.1145/1219092.1219093 2007

  3. [3]

    Special issue: Digital Libraries. 1996

    1996

  4. [4]

    Understanding Policy-Based Networking

    David Kosiur. Understanding Policy-Based Networking. 2001

    2001

  5. [7]

    The title of book two. 2008. doi:10.1007/3-540-09237-4

    work page doi:10.1007/3-540-09237-4 2008

  6. [8]

    Asad Z. Spector. Achieving application requirements. Distributed Systems. 1990. doi:10.1145/90417.90738

    work page doi:10.1145/90417.90738 1990

  7. [9]

    Douglass and David Harel and Mark B

    Bruce P. Douglass and David Harel and Mark B. Trakhtenbrot. Statecarts in use: structured analysis and object-orientation. Lectures on Embedded Systems. 1998. doi:10.1007/3-540-65193-4_29

    work page doi:10.1007/3-540-65193-4_29 1998

  8. [10]

    Donald E. Knuth. The Art of Computer Programming, Vol. 1: Fundamental Algorithms (3rd. ed.). 1997

    1997

  9. [11]

    Donald E. Knuth. The Art of Computer Programming. 1998

    1998

  10. [12]

    Structured Variational Inference Procedures and their Realizations (as incol)

    Dan Geiger and Christopher Meek. Structured Variational Inference Procedures and their Realizations (as incol). Proceedings of Tenth International Workshop on Artificial Intelligence and Statistics, The Barbados

  11. [13]

    Stan W. Smith. An experiment in bibliographic mark-up: Parsing metadata for XML export. Proceedings of the 3rd. annual workshop on Librarians and Computers. 2010. doi:99.9999/woot07-S422

    2010

  12. [14]

    Catch me, if you can: Evading network signatures with web-based polymorphic worms

    Matthew Van Gundy and Davide Balzarotti and Giovanni Vigna. Catch me, if you can: Evading network signatures with web-based polymorphic worms. Proceedings of the first USENIX workshop on Offensive Technologies. 2007

    2007

  13. [15]

    Catch me, if you can: Evading network signatures with web-based polymorphic worms

    Matthew Van Gundy and Davide Balzarotti and Giovanni Vigna. Catch me, if you can: Evading network signatures with web-based polymorphic worms. Proceedings of the first USENIX workshop on Offensive Technologies. 2008

    2008

  14. [16]

    Catch me, if you can: Evading network signatures with web-based polymorphic worms

    Matthew Van Gundy and Davide Balzarotti and Giovanni Vigna. Catch me, if you can: Evading network signatures with web-based polymorphic worms. Proceedings of the first USENIX workshop on Offensive Technologies. 2009

    2009

  15. [17]

    Predicate Path expressions

    Sten Andler. Predicate Path expressions. Proceedings of the 6th. ACM SIGACT-SIGPLAN symposium on Principles of Programming Languages. 1979. doi:10.1145/567752.567774

    work page doi:10.1145/567752.567774 1979

  16. [18]

    LOGICS of Programs: AXIOMATICS and DESCRIPTIVE POWER

    David Harel. LOGICS of Programs: AXIOMATICS and DESCRIPTIVE POWER. 1978

    1978

  17. [19]

    Anisi , title =

    David A. Anisi , title =

  18. [20]

    Clarkson

    Kenneth L. Clarkson. Algorithms for Closest-Point Problems (Computational Geometry). 1985

    1985

  19. [21]

    Introduction to Bayesian Statistics

    Harry Thornburg. Introduction to Bayesian Statistics. 2001

    2001

  20. [22]

    CLIFFORD: a Maple 11 Package for Clifford Algebra Computations, version 11

    Rafal Ablamowicz and Bertfried Fauser. CLIFFORD: a Maple 11 Package for Clifford Algebra Computations, version 11. 2007

    2007

  21. [23]

    Stats and Analysis

    Poker-Edge.Com. Stats and Analysis. 2006

    2006

  22. [24]

    A more perfect union

    Barack Obama. A more perfect union. 2008

    2008

  23. [25]

    The fountain of youth

    Joseph Scientist. The fountain of youth. 2009

    2009

  24. [26]

    Solder man

    Dave Novak. Solder man. ACM SIGGRAPH 2003 Video Review on Animation theater Program: Part I - Vol. 145 (July 27--27, 2003). 2003. doi:99.9999/woot07-S422

    2003

  25. [27]

    Interview with Bill Kinder: January 13, 2005

    Newton Lee. Interview with Bill Kinder: January 13, 2005. Comput. Entertain. 2005. doi:10.1145/1057270.1057278

    work page doi:10.1145/1057270.1057278 2005

  26. [28]

    The Enabling of Digital Libraries

    Bernard Rous. The Enabling of Digital Libraries. Digital Libraries. 2008

    2008

  27. [30]

    (new) Finding minimum congestion spanning trees , journal =

    Werneck, Renato and Setubal, Jo\. (new) Finding minimum congestion spanning trees , journal =. 2000 , issn =. doi:10.1145/351827.384253 , acmid =

    work page doi:10.1145/351827.384253 2000

  28. [32]

    and Mei, Alessandro , title =

    Conti, Mauro and Di Pietro, Roberto and Mancini, Luigi V. and Mei, Alessandro , title =. Inf. Fusion , volume =. 2009 , issn =. doi:10.1016/j.inffus.2009.01.002 , acmid =

    work page doi:10.1016/j.inffus.2009.01.002 2009

  29. [33]

    and Hutchful, David K

    Li, Cheng-Lun and Buyuktur, Ayse G. and Hutchful, David K. and Sant, Natasha B. and Nainwal, Satyendra K. , title =. CHI '08 extended abstracts on Human factors in computing systems , year =. doi:10.1145/1358628.1358946 , acmid =

    work page doi:10.1145/1358628.1358946

  30. [34]

    , title =

    Hollis, Billy S. , title =. 1999 , isbn =

    1999

  31. [35]

    Goossens, Michel and Rahtz, S. P. and Moore, Ross and Sutor, Robert S. , title =. 1999 , isbn =

    1999

  32. [36]

    and Rosenberg, Arnold L

    Buss, Jonathan F. and Rosenberg, Arnold L. and Knott, Judson D. , title =. 1987 , source =

    1987

  33. [37]

    CHI '08: CHI '08 extended abstracts on Human factors in computing systems , year =

    , note =. CHI '08: CHI '08 extended abstracts on Human factors in computing systems , year =

  34. [38]

    Algorithms for Closest-Point Problems (Computational Geometry) , year =

    Clarkson, Kenneth Lee , advisor =. Algorithms for Closest-Point Problems (Computational Geometry) , year =

  35. [39]

    SIGCOMM Comput. Commun. Rev. , year =

  36. [40]

    2004 , isbn =

    IEEE TCSC Executive Committee , booktitle =. 2004 , isbn =. doi:http://dx.doi.org/10.1109/ICWS.2004.64 , acmid =

    work page doi:10.1109/icws.2004.64 2004

  37. [41]

    Distributed systems (2nd Ed.) , year =

  38. [42]

    , title =

    Petrie, Charles J. , title =. 1986 , source =

    1986

  39. [43]

    Donald E. Knuth. Seminumerical Algorithms. 1981

    1981

  40. [44]

    E-commerce and cultural values , year =

    Kong, Wei-Chang , Title =. E-commerce and cultural values , year =

  41. [45]

    E-commerce and cultural values , year =

    Kong, Wei-Chang , type =. E-commerce and cultural values , year =

  42. [46]

    Chapter 9 , booktitle =

    Kong, Wei-Chang , editor =. Chapter 9 , booktitle =. 2002 , address =

    2002

  43. [47]

    E-commerce and cultural values , editor =

    Kong, Wei-Chang , title =. E-commerce and cultural values , editor =. 2003 , isbn =

    2003

  44. [48]

    E-commerce and cultural values - (InBook-num-in-chap) , chapter =

    Kong, Wei-Chang , editor =. E-commerce and cultural values - (InBook-num-in-chap) , chapter =. 2004 , address =

    2004

  45. [49]

    E-commerce and cultural values (Inbook-text-in-chap) , chapter =

    Kong, Wei-Chang , editor =. E-commerce and cultural values (Inbook-text-in-chap) , chapter =. 2005 , address =

    2005

  46. [50]

    E-commerce and cultural values (Inbook-num chap) , chapter =

    Kong, Wei-Chang , editor =. E-commerce and cultural values (Inbook-num chap) , chapter =. 2006 , address =

    2006

  47. [51]

    Microelectron

    Mehdi Saeedi and Morteza Saheb Zamani and Mehdi Sedighi , title =. Microelectron. J. , volume =. 2010 , pages =

    2010

  48. [52]

    Mehdi Saeedi and Morteza Saheb Zamani and Mehdi Sedighi and Zahra Sasanian , title =. J. Emerg. Technol. Comput. Syst. , volume =

  49. [53]

    Kirschmer, Markus and Voight, John , title =. SIAM J. Comput. , issue_date =. 2010 , issn =. doi:http://dx.doi.org/10.1137/080734467 , acmid =

    work page doi:10.1137/080734467 2010

  50. [54]

    Hoare, C. A. R. , title =. Structured programming (incoll) , editor =. 1972 , isbn =

    1972

  51. [55]

    History of programming languages I (incoll) , editor =

    Lee, Jan , title =. History of programming languages I (incoll) , editor =. 1981 , isbn =. doi:http://doi.acm.org/10.1145/800025.1198348 , acmid =

    work page doi:10.1145/800025.1198348 1981

  52. [56]

    , title =

    Dijkstra, E. , title =. Classics in software engineering (incoll) , year =

  53. [57]

    , title =

    Wenzel, Elizabeth M. , title =. Multimedia interface design (incoll) , year =. doi:10.1145/146022.146089 , acmid =

    work page doi:10.1145/146022.146089

  54. [58]

    , title =

    Mumford, E. , title =. Critical issues in information systems research (incoll) , year =

  55. [59]

    and Golden, Donald G

    McCracken, Daniel D. and Golden, Donald G. , title =. 1990 , isbn =

    1990

  56. [60]

    The analysis of linear partial differential operators

    H. The analysis of linear partial differential operators. 1985 , PAGES =

    1985

  57. [61]

    IEEE", address =

    A. Adya and P. Bahl and J. Padhye and A.Wolman and L. Zhou , title =. Proceedings of the IEEE 1st International Conference on Broadnets Networks (BroadNets'04) , publisher = "IEEE", address = "Los Alamitos, CA", year =

  58. [62]

    I. F. Akyildiz and W. Su and Y. Sankarasubramaniam and E. Cayirci , title =. Comm. ACM , volume = 38, number = "4", year =

  59. [63]

    I. F. Akyildiz and T. Melodia and K. R. Chowdhury , title =. Computer Netw. , volume = 51, number = "4", year =

  60. [64]

    ACM", address =

    P. Bahl and R. Chancre and J. Dungeon , title =. Proceeding of the 10th International Conference on Mobile Computing and Networking (MobiCom'04) , publisher = "ACM", address = "New York, NY", year =

  61. [65]

    8 (Special Issue on Sensor Networks)

    D. Culler and D. Estrin and M. Srivastava , title =. IEEE Comput. , volume = 37, number = "8 (Special Issue on Sensor Networks)", publisher = "IEEE", address = "Los Alamitos, CA", year =

  62. [66]

    Natarajan and M

    A. Natarajan and M. Motani and B. de Silva and K. Yap and K. C. Chua , title =. Network Architectures , editor =. 960935712

  63. [67]

    Tzamaloukas and J

    A. Tzamaloukas and J. J. Garcia-Luna-Aceves , title =

  64. [68]

    Zhou and J

    G. Zhou and J. Lu and C.-Y. Wan and M. D. Yarvis and J. A. Stankovic , title =

  65. [69]

    Mapping Powerlists onto Hypercubes

    Jacob Kornerup. Mapping Powerlists onto Hypercubes. 1994

    1994

  66. [70]

    Automatic Parallelization for Distributed-Memory Multiprocessing Systems

    Michael Gerndt. Automatic Parallelization for Distributed-Memory Multiprocessing Systems

  67. [71]

    J. E. Archer, Jr. and R. Conway and F. B. Schneider. User recovery and reversal in interactive systems. ACM Trans. Program. Lang. Syst

  68. [72]

    D. D. Dunlop and V. R. Basili. Generalizing specifications for uniformly implemented loops. ACM Trans. Program. Lang. Syst

  69. [73]

    Heering and P

    J. Heering and P. Klint. Towards monolingual programming environments. ACM Trans. Program. Lang. Syst

  70. [74]

    Donald E. Knuth. The book

  71. [75]

    Korach and D

    E. Korach and D. Rotem and N. Santoro. Distributed algorithms for finding centers and medians in networks. ACM Trans. Program. Lang. Syst

  72. [76]

    : A Document Preparation System

    Leslie Lamport. : A Document Preparation System

  73. [77]

    F. Nielson. Program transformations in a denotational setting. ACM Trans. Program. Lang. Syst

  74. [78]

    Brian K. Reid. A high-level approach to computer document formatting. Proceedings of the 7th Annual Symposium on Principles of Programming Languages

  75. [79]

    and Abdelzaher, Tarek F

    Zhou, Gang and Wu, Yafeng and Yan, Ting and He, Tian and Huang, Chengdu and Stankovic, John A. and Abdelzaher, Tarek F. , title =. ACM Trans. Embed. Comput. Syst. , issue_date =. 2010 , issn =. doi:10.1145/1721695.1721705 , acmid =

    work page doi:10.1145/1721695.1721705 2010

  76. [80]

    Operations Research Letters , volume =

    Maxim Sviridenko , title =. Operations Research Letters , volume =

  77. [81]

    The American Economic Review , volume=

    Obviously Strategy-Proof Mechanisms , author=. The American Economic Review , volume=. 2017 , publisher=

    2017

  78. [82]

    Twenty Lectures on Algorithmic Game Theory

    Roughgarden, Tim. Twenty Lectures on Algorithmic Game Theory

  79. [83]

    Nemhauser and Laurence A

    George L. Nemhauser and Laurence A. Wolsey and Marshall L. Fisher , title =. Mathematical Programing , volume =

  80. [84]

    Algorithmica , volume =

    Ashwinkumar Badanidiyuru and Shahar Dobzinski and Sigal Oren , title =. Algorithmica , volume =

Showing first 80 references.