pith. sign in

arxiv: 2606.26651 · v1 · pith:UAKGXGVUnew · submitted 2026-06-25 · 💻 cs.GT

Learning Anonymous Pricing for Online Resource Allocation

Yifeng Teng , Yifan Wang This is my paper

Pith reviewed 2026-06-26 02:12 UTC · model grok-4.3

classification 💻 cs.GT
keywords online resource allocationanonymous pricingdual pricinglearning from samplespricing queriessocial welfaresample complexity
0
0 comments X

The pith

A polynomial number of samples suffices to learn the classic dual pricing algorithm, and polynomial pricing queries suffice to learn a near-optimal anonymous pricing algorithm for online resource allocation.

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

The paper establishes that anonymous pricing can be learned efficiently for the online resource allocation problem, where agents arrive in unknown order requesting resources with limited supplies and the goal is to maximize total social welfare. It addresses limitations of prior dynamic pricing methods that assign different prices to different agents and require advance knowledge of arrival order. Using access to value distributions via samples, a polynomial number suffices to learn the dual pricing algorithm. Using pricing queries instead, a polynomial number suffices to learn a near-optimal anonymous scheme in which every agent draws its price vector from one fixed distribution.

Core claim

For online resource allocation with m resource types, n heterogeneous agents, and requests that consume vectors in [0,1]^m while generating agent-specific values, a polynomial number of samples from the value distributions is enough to learn the classic dual pricing algorithm, and a polynomial number of pricing queries is enough to learn a near-optimal anonymous pricing algorithm in which the pricing vector presented to each agent is drawn independently from one predetermined distribution.

What carries the argument

The anonymous pricing algorithm in which the item pricing vector faced by each agent is drawn from the same predetermined distribution.

If this is right

  • Anonymous pricing avoids assigning different prices to different agents and does not require knowing the arrival order in advance.
  • Near-optimal social welfare remains achievable under the constraint that all agents face prices from one shared distribution.
  • The classic dual pricing algorithm itself becomes learnable from polynomially many samples.
  • Query access to value distributions provides an alternative learning route that also requires only polynomially many interactions.

Where Pith is reading between the lines

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

  • The result suggests that fairness constraints can be imposed on online allocation mechanisms while retaining polynomial learnability.
  • It raises the question of whether the same polynomial bounds extend when distributions are correlated rather than independent.
  • Practical deployment would require checking whether the learned prices remain stable when the actual arrival sequence deviates from the modeled order.

Load-bearing premise

The value distributions of the agents are independent and can be accessed via samples or pricing queries.

What would settle it

An explicit family of value distributions and resource constraints for which any algorithm that outputs a near-optimal anonymous pricing scheme requires a super-polynomial number of samples or queries in the input parameters.

read the original abstract

We study the online resource allocation problem, where a seller sequentially receives independent requests for $m$ types of resources with limited supplies from $n$ heterogeneous agents arriving in an unknown order. Each request from an agent can be fulfilled in different ways, with resource consumption in $[0,1]^m$, and generates different values for the agent. The objective of the seller is to maximize the social welfare, which is the sum of the values obtained from each agent. Recently, Ghuge, Singla, and Wang [GSW STOC'25] studied the learnability of the online resource allocation problem with heterogeneous agents and proposed a learnable pricing algorithm using only a single sample. However, their core algorithm is a dynamic pricing algorithm, which may introduce fairness concerns, as different agents face different prices. Furthermore, the algorithm crucially needs to know the arrival order of the agents in advance. To address these issues, in this paper, we study the learnability of anonymous pricing algorithms for online resource allocation using samples and queries to agents' value distributions. First, we show that a polynomial number of samples suffices to learn the classic dual pricing algorithm. Second, we show that a polynomial number of pricing queries suffices to learn a near-optimal anonymous pricing algorithm, in which the item pricing vector faced by each agent is drawn from the same predetermined distribution.

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

1 major / 1 minor

Summary. The paper claims that in the online resource allocation problem with heterogeneous agents arriving in unknown order, a polynomial number of samples from agents' value distributions suffices to learn the classic dual pricing algorithm, and a polynomial number of pricing queries suffices to learn a near-optimal anonymous pricing algorithm in which every agent faces an item pricing vector drawn from the same fixed distribution.

Significance. If the polynomial bounds hold under a well-defined access model, the results establish learnability of fair (anonymous) pricing mechanisms for online welfare maximization without requiring known arrival order, extending prior work on dynamic pricing while addressing fairness concerns.

major comments (1)
  1. [Model and problem formulation (likely §2–3)] The formal definition of the sample and pricing-query oracles (including timing relative to sequential arrivals and whether an offline preprocessing phase is permitted) is not provided. This is load-bearing for the central polynomial-complexity claims, as the online resource constraints and unknown arrival order may restrict when independent samples or queries can be obtained without violating the problem setting.
minor comments (1)
  1. [Abstract] The abstract refers to 'the classic dual pricing algorithm' without a brief inline definition or pointer to its standard formulation.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the constructive comment regarding the model and oracle definitions. We address the point below and will revise the manuscript to incorporate the requested clarifications.

read point-by-point responses

  1. Referee: [Model and problem formulation (likely §2–3)] The formal definition of the sample and pricing-query oracles (including timing relative to sequential arrivals and whether an offline preprocessing phase is permitted) is not provided. This is load-bearing for the central polynomial-complexity claims, as the online resource constraints and unknown arrival order may restrict when independent samples or queries can be obtained without violating the problem setting.

    Authors: We agree that the formal definitions of the sample and pricing-query oracles require explicit specification, including their timing and the allowance for an offline phase. In the revised manuscript, we will add a dedicated subsection (likely in §2) that formally defines both oracles. The definitions will state that the oracles are available exclusively during an offline preprocessing phase prior to the start of the online arrival process. In this phase, independent samples can be drawn from the agents' value distributions and pricing queries can be made, with no resource allocation or online constraints active. After learning the dual pricing or the near-optimal anonymous pricing distribution, the online phase proceeds with sequential arrivals in unknown order, applying the learned mechanism without additional queries. This model is standard in the literature on learning in mechanism design and preserves the online resource constraints and unknown-order setting during the allocation phase. We will also include a brief discussion of why this separation is without loss of generality for the polynomial sample and query complexity claims. revision: yes

Circularity Check

0 steps flagged

No significant circularity; claims rest on standard learning theory

full rationale

The paper claims that a polynomial number of samples suffices to learn the dual pricing algorithm and that a polynomial number of pricing queries suffices to learn a near-optimal anonymous pricing algorithm. These are standard learnability statements in an online allocation setting with independent value distributions. No equations, fitted parameters, or self-referential definitions appear in the abstract or description that would reduce a prediction to its input by construction. The citation to [GSW STOC'25] (overlapping author) is used only to contrast dynamic vs. anonymous pricing and to note prior limitations on order knowledge; it is not invoked as a uniqueness theorem or load-bearing premise for the new polynomial bounds. The derivation chain is therefore self-contained against external benchmarks and receives a normal non-finding.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based on abstract only; no free parameters, axioms, or invented entities are explicitly stated. The claims rest on standard assumptions of independent value distributions and query access that are not detailed.

pith-pipeline@v0.9.1-grok · 5762 in / 1168 out tokens · 19297 ms · 2026-06-26T02:12:20.918364+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

175 extracted references · 24 canonical work pages

  1. [1]

    Time-uniform Chernoff bounds via nonnegative supermartingales , author=

  2. [2]

    2012 , publisher=

    Convergence of stochastic processes , author=. 2012 , publisher=

    2012

  3. [3]

    The American Mathematical Monthly , volume=

    Partition of space , author=. The American Mathematical Monthly , volume=. 1943 , publisher=

    1943

  4. [4]

    Single-Sample and Robust Online Resource Allocation , booktitle =

    Rohan Ghuge and Sahil Singla and Yifan Wang , editor =. Single-Sample and Robust Online Resource Allocation , booktitle =. 2025 , url =. doi:10.1145/3717823.3718246 , timestamp =

    work page doi:10.1145/3717823.3718246 2025

  5. [5]

    Saeed Alaei , title =

  6. [6]

    Theory of computing , volume=

    The multiplicative weights update method: a meta-algorithm and applications , author=. Theory of computing , volume=. 2012 , publisher=

    2012

  7. [7]

    Journal of computer and system sciences , volume=

    A decision-theoretic generalization of on-line learning and an application to boosting , author=. Journal of computer and system sciences , volume=. 1997 , publisher=

    1997

  8. [8]

    Dynamic Placement in Refugee Resettlement , journal =

    Narges Ahani and Paul G. Dynamic Placement in Refugee Resettlement , journal =

  9. [9]

    Stochastic analyses for online combinatorial optimization problems , booktitle =

    Naveen Garg and Anupam Gupta and Stefano Leonardi and Piotr Sankowski , editor =. Stochastic analyses for online combinatorial optimization problems , booktitle =

  10. [10]

    Alberto Vera and Siddhartha Banerjee and Itai Gurvich , title =. Oper. Res. , volume =

  11. [11]

    Kowalski and Piotr Krysta and Jan Olkowski , title =

    Kiarash Banihashem and MohammadTaghi Hajiaghayi and Dariusz R. Kowalski and Piotr Krysta and Jan Olkowski , title =. Proceedings of SODA , pages =

  12. [12]

    Schapire and Aleksandrs Slivkins , title =

    Nicole Immorlica and Karthik Abinav Sankararaman and Robert E. Schapire and Aleksandrs Slivkins , title =. J

  13. [13]

    Ravi , title =

    Marco Molinaro and R. Ravi , title =. Math. Oper. Res. , volume =

  14. [14]

    Huber , title =

    Peter J. Huber , title =. The Annals of Mathematical Statistics , number =

  15. [15]

    47th International Colloquium on Automata, Languages, and Programming,

    Paritosh Garg and Sagar Kale and Lars Rohwedder and Ola Svensson , title =. 47th International Colloquium on Automata, Languages, and Programming,

  16. [16]

    47th International Colloquium on Automata, Languages, and Programming,

    Thomas Kesselheim and Marco Molinaro , title =. 47th International Colloquium on Automata, Languages, and Programming,

  17. [17]

    Echenique and N

    F. Echenique and N. Immorlica and V. V. Vazirani , place=. Online and Matching-Based Market Design , publisher=

  18. [18]

    2023 , publisher=

    Algorithmic high-dimensional robust statistics , author=. 2023 , publisher=

    2023

  19. [19]

    Karp and Umesh V

    Richard M. Karp and Umesh V. Vazirani and Vijay V. Vazirani , editor =. An Optimal Algorithm for On-line Bipartite Matching , booktitle =

  20. [20]

    Journal of Machine Learning Research , volume=

    The two-sided game of googol , author=. Journal of Machine Learning Research , volume=

  21. [21]

    Mathematics of Operations Research , volume=

    Sample-driven optimal stopping: From the secretary problem to the iid prophet inequality , author=. Mathematics of Operations Research , volume=. 2024 , publisher=

    2024

  22. [22]

    Devanur and Kamal Jain , editor =

    Nikhil R. Devanur and Kamal Jain , editor =. Online matching with concave returns , booktitle =

  23. [23]

    Prophet Inequalities Require Only a Constant Number of Samples , booktitle =

    Andr. Prophet Inequalities Require Only a Constant Number of Samples , booktitle =

  24. [24]

    Proceedings of SODA , pages =

    Haim Kaplan and David Naori and Danny Raz , title =. Proceedings of SODA , pages =

  25. [25]

    Single-Sample Prophet Inequalities via Greedy-Ordered Selection , booktitle =

    Constantine Caramanis and Paul D. Single-Sample Prophet Inequalities via Greedy-Ordered Selection , booktitle =

  26. [26]

    Proceedings of SODA 2022 , pages =

    Haim Kaplan and David Naori and Danny Raz , title =. Proceedings of SODA 2022 , pages =

    2022

  27. [27]

    Wang and S

    Aviad Rubinstein and Jack Z. Wang and S. Matthew Weinberg , title =. Proceedings of ITCS , series =

  28. [28]

    Prophet Inequalities for

    Jos. Prophet Inequalities for. Proceedings of EC , pages =

  29. [29]

    C. J. Argue and Alan M. Frieze and Anupam Gupta and Christopher Seiler , title =. Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS , year =

    2022

  30. [30]

    Matthew Weinberg , title =

    Pablo Daniel Azar and Robert Kleinberg and S. Matthew Weinberg , title =. Proceedings of SODA , pages =

  31. [31]

    Data-Driven Algorithm Design , booktitle =

    Maria. Data-Driven Algorithm Design , booktitle =

  32. [32]

    Online Algorithms for Covering and Packing Problems with Convex Objectives , booktitle =

    Yossi Azar and Niv Buchbinder and T. Online Algorithms for Covering and Packing Problems with Convex Objectives , booktitle =

  33. [33]

    Proceedings of

    Niv Buchbinder and Joseph Naor , title =. Proceedings of

  34. [34]

    A Constant Factor Prophet Inequality for Online Combinatorial Auctions , booktitle =

    Jos. A Constant Factor Prophet Inequality for Online Combinatorial Auctions , booktitle =

  35. [35]

    Dynkin, E. B. , journal =

  36. [36]

    Krengel and L

    U. Krengel and L. Sucheston , title =. Bulletin of the American Mathematical Society , volume =

  37. [37]

    Krengel and L

    U. Krengel and L. Sucheston , title =. Advances in Probability and Related Topics , volume =

  38. [38]

    SIGecom Exch

    Brendan Lucier , title =. SIGecom Exch. , volume =

  39. [39]

    Ashwinkumar Badanidiyuru and Robert Kleinberg and Aleksandrs Slivkins , title =. J

  40. [40]

    Devanur , title =

    Shipra Agrawal and Nikhil R. Devanur , title =. Oper. Res. , volume =

  41. [41]

    Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science , pages=

    Throughput-competitive on-line routing , author=. Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science , pages=. 1993 , organization=

    1993

  42. [42]

    Mathematics of Operations Research , volume=

    Online primal-dual algorithms for covering and packing , author=. Mathematics of Operations Research , volume=. 2009 , publisher=

    2009

  43. [43]

    Random-Order Models , booktitle =

    Anupam Gupta and Sahil Singla , editor =. Random-Order Models , booktitle =

  44. [44]

    Balseiro and Haihao Lu and Vahab Mirrokni , title =

    Santiago R. Balseiro and Haihao Lu and Vahab Mirrokni , title =. Oper. Res. , volume =

  45. [45]

    Alberto Vera and Siddhartha Banerjee , title =. Manag. Sci. , volume =

  46. [46]

    2006 , publisher=

    The theory and practice of revenue management , author=. 2006 , publisher=

    2006

  47. [47]

    Operations Research , volume=

    An approximation algorithm for network revenue management under nonstationary arrivals , author=. Operations Research , volume=. 2020 , publisher=

    2020

  48. [48]

    Proceedings of FOCS , year =

    Sepehr Assadi and Sahil Singla , title =. Proceedings of FOCS , year =

  49. [49]

    Proceedings of

    Sepehr Assadi and Thomas Kesselheim and Sahil Singla , title =. Proceedings of

  50. [50]

    An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions , booktitle =

    Paul D. An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions , booktitle =

  51. [51]

    An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions , booktitle =

    Thomas Kesselheim and Klaus Radke and Andreas T. An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions , booktitle =

  52. [52]

    Proceedings of the 13th

    Saeed Alaei and MohammadTaghi Hajiaghayi and Vahid Liaghat , title =. Proceedings of the 13th

  53. [53]

    11th Innovations in Theoretical Computer Science Conference,

    Domagoj Bradac and Anupam Gupta and Sahil Singla and Goran Zuzic , title =. 11th Innovations in Theoretical Computer Science Conference,

  54. [54]

    Foundations and Trends

    The design of competitive online algorithms via a primal--dual approach , author=. Foundations and Trends. 2009 , publisher=

    2009

  55. [55]

    Management Science , volume=

    Real-time optimization of personalized assortments , author=. Management Science , volume=. 2014 , publisher=

    2014

  56. [56]

    2024 , eprint=

    Online Contention Resolution Schemes for Network Revenue Management and Combinatorial Auctions , author=. 2024 , eprint=

    2024

  57. [57]

    Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs , journal =

    Paul D. Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs , journal =

  58. [58]

    Mathematical Programming , title =

    Correa, Jos. Mathematical Programming , title =. 2023 , bdsk-url-1 =. doi:10.1007/s10107-023-02027-2 , id =

    work page doi:10.1007/s10107-023-02027-2 2023

  59. [59]

    Aranyak Mehta , title =. Found. Trends Theor. Comput. Sci. , volume =. 2013 , url =. doi:10.1561/0400000057 , timestamp =

    work page doi:10.1561/0400000057 2013

  60. [60]

    Vazirani and Vijay V

    Aranyak Mehta and Amin Saberi and Umesh V. Vazirani and Vijay V. Vazirani , title =. J

  61. [61]

    Anupam Gupta and Marco Molinaro , title =. Math. Oper. Res. , volume =

  62. [62]

    Primal Beats Dual on Online Packing LPs in the Random-Order Model , journal =

    Thomas Kesselheim and Klaus Radke and Andreas T. Primal Beats Dual on Online Packing LPs in the Random-Order Model , journal =

  63. [63]

    Devanur and Thomas P

    Nikhil R. Devanur and Thomas P. Hayes , title =. Proceedings 10th

  64. [64]

    Operations Research , volume=

    A dynamic near-optimal algorithm for online linear programming , author=. Operations Research , volume=. 2014 , publisher=

    2014

  65. [65]

    Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract) , booktitle =

    Gruia C. Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract) , booktitle =. 2007 , url =. doi:10.1007/978-3-540-72792-7\_15 , timestamp =

    work page doi:10.1007/978-3-540-72792-7 2007

  66. [66]

    Streeter , title =

    Daniel Golovin and Andreas Krause and Matthew J. Streeter , title =. CoRR , volume =. 2014 , url =. 1407.1082 , timestamp =

    Pith/arXiv arXiv 2014

  67. [67]

    Wang , editor =

    Tim Roughgarden and Joshua R. Wang , editor =. An Optimal Learning Algorithm for Online Unconstrained Submodular Maximization , booktitle =. 2018 , url =

    2018

  68. [68]

    Wang and Fransisca Susan and Ashwinkumar Badanidiyuru , editor =

    Rad Niazadeh and Negin Golrezaei and Joshua R. Wang and Fransisca Susan and Ashwinkumar Badanidiyuru , editor =. Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization , booktitle =. 2021 , url =. doi:10.1145/3465456.3467571 , timestamp =

    work page doi:10.1145/3465456.3467571 2021

  69. [69]

    Nicholas J. A. Harvey and Christopher Liaw and Tasuku Soma , editor =. Improved Algorithms for Online Submodular Maximization via First-order Regret Bounds , booktitle =. 2020 , url =

    2020

  70. [70]

    2015 , url =

    Niv Buchbinder and Moran Feldman and Joseph Naor and Roy Schwartz , title =. 2015 , url =. doi:10.1137/130929205 , timestamp =

    work page doi:10.1137/130929205 2015

  71. [71]

    Levy and Robert E

    Moran Feldman , editor =. Guess Free Maximization of Submodular and Linear Sums , booktitle =. 2019 , url =. doi:10.1007/978-3-030-24766-9\_28 , timestamp =

    work page doi:10.1007/978-3-030-24766-9 2019

  72. [72]

    Learning Theory 2003 , author =

    Adam Tauman Kalai and Santosh S. Vempala , title =. J. Comput. Syst. Sci. , volume =. 2005 , url =. doi:10.1016/j.jcss.2004.10.016 , timestamp =

    work page doi:10.1016/j.jcss.2004.10.016 2005

  73. [73]

    Regret in Online Combinatorial Optimization , journal =

    Jean. Regret in Online Combinatorial Optimization , journal =. 2014 , url =. doi:10.1287/moor.2013.0598 , timestamp =

    work page doi:10.1287/moor.2013.0598 2014

  74. [74]

    Combinatorial bandits , journal =

    Nicol. Combinatorial bandits , journal =. 2012 , url =. doi:10.1016/j.jcss.2012.01.001 , timestamp =

    work page doi:10.1016/j.jcss.2012.01.001 2012

  75. [75]

    Combinatorial Bandits Revisited , booktitle =

    Richard Combes and Mohammad Sadegh Talebi and Alexandre Prouti. Combinatorial Bandits Revisited , booktitle =. 2015 , url =

    2015

  76. [76]

    , year =

    Peter Auer and Nicol. The Nonstochastic Multiarmed Bandit Problem , journal =. 2002 , url =. doi:10.1137/S0097539701398375 , timestamp =

    work page doi:10.1137/s0097539701398375 2002

  77. [77]

    Papadimitriou and Tristan Pollner and Amin Saberi and David Wajc , editor =

    Christos H. Papadimitriou and Tristan Pollner and Amin Saberi and David Wajc , editor =. Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities , booktitle =. 2021 , url =. doi:10.1145/3465456.3467613 , timestamp =

    work page doi:10.1145/3465456.3467613 2021

  78. [78]

    The Invisible Hand of Dynamic Market Pricing , booktitle =

    Vincent Cohen. The Invisible Hand of Dynamic Market Pricing , booktitle =. 2016 , url =. doi:10.1145/2940716.2940730 , timestamp =

    work page doi:10.1145/2940716.2940730 2016

  79. [79]

    Max-Min Greedy Matching , booktitle =

    Alon Eden and Uriel Feige and Michal Feldman , editor =. Max-Min Greedy Matching , booktitle =. 2019 , url =. doi:10.4230/LIPIcs.APPROX-RANDOM.2019.7 , timestamp =

    work page doi:10.4230/lipics.approx-random.2019.7 2019

  80. [80]

    Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark , booktitle =

    Mark Braverman and Mahsa Derakhshan and Antonio Molina Lovett , editor =. Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark , booktitle =. 2022 , url =. doi:10.1145/3490486.3538315 , timestamp =

    work page doi:10.1145/3490486.3538315 2022

Showing first 80 references.