Pith. sign in

REVIEW 3 major objections 6 minor 62 references

Efficiency, Feasibility, and Incentive-Awareness in Constrained Online Resource Allocation

T0 review · 3 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper argues constrained online resource allocation can tolerate strategic agents at no polynomial-order cost: Õ(√T) regret matching the non-strategic lower bound, exact long-term constraints, and near-truthful reports in equilibrium.

desk verdict A serious paper with a genuinely new mechanism and a plausible high-level story, but the PBE proof has a load-bearing gap involving the cost-feasibility rejection rule, and several smaller mechanical errors need fixing before the main theorem is credible for Algorithm 2 as stated. read the letter →

arxiv 2507.09473 v2 pith:4HWE45P3 submitted 2025-07-13 cs.GT cs.LGstat.ML

Yan Dai , Negin Golrezaei , Patrick Jaillet This is my paper · ORCID
classification cs.GTcs.LGstat.ML MSC 91B3268W2791A26
keywords onlineresourceallocationprimal-dualalgorithmsstrategicagentsincentivecompatibilityperfectBayesianequilibriumoptimisticlearningregretboundslong-termconstraints
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper asks whether a planner can allocate a scarce reusable resource — think cloud GPUs or mobile health units — to self-interested agents who may misreport their private valuations, while simultaneously maximizing social welfare, obeying multi-dimensional long-term cost constraints, and keeping agents roughly honest. The authors argue that the standard primal-dual method, the workhorse of constrained online allocation, is fragile in such strategic settings: agents learn to distort their reports to move future 'shadow prices' (dual variables) in their favor. Their incentive-aware mechanism neutralizes this manipulation with three coordinated ingredients — epoch-based lazy dual updates, VCG-style payments, and randomized exploration rounds that impose an immediate utility loss on liars. With a new optimistic online-learning subroutine that resolves a fixed-point dependency between prices and allocations, the mechanism achieves $\widetilde{O}(\sqrt{T})$ social-welfare regret with exactly zero long-term constraint violation, matching the $\Omega(\sqrt{T})$ lower bound of the non-strategic problem. The upshot, if the main theorem holds, is that protecting against strategic behavior need not cost efficiency, provided agents discount the future.

What carries the argument

Three components carry the argument. (1) Epoch-based lazy updates: the dual variable $\lambda_\ell$ is fixed for the whole epoch $E_\ell$, so any single misreport has limited and delayed influence on future shadow prices. (2) A boosted second-price payment rule: the winner pays their dual-weighted cost plus the runner-up's adjusted report, making truthful reporting weakly dominant in the one-shot epoch game (Lemma B.1, Theorem B.2). (3) Randomized exploration rounds: with probability $1/|E_\ell|$ the mechanism offers a uniformly random price to a random agent, giving any misreport an expected immediate loss of order $(u-v)^2/(K|E_\ell|)$; Lemma B.3 shows this outweighs the $\gamma$-discounted future benefit of manipulating the next dual, so large misreports occur in only $\widetilde{O}(1)$ rounds per epoch. The dual-side novelty is O-FTRL-FP (Eq. (6)), which adds an optimistic prediction term $\widetilde{g}_\ell(\lambda_\ell)^\top \lambda$ — an estimate of the coming epoch's loss built from past reports — to the FTRL objective. Because the prediction depends on $\lambda_\ell$ through an argmax, the update is a fixed-point problem: the paper proves existence of approximate fixed points via a partition-of-unity (Brouwer) argument under an approximate-continuity condition (Lemmas C.4, C.5), and then bounds the three stability errors — allocation mismatch, empirical estimation, and untruthful reports (Lemmas C.6–C.8).

What would settle it

Run the mechanism with nearly patient agents ($\gamma = 1$ or $\gamma = 1 - 1/T$), let them learn their reports with a high-capacity algorithm over thousands of repetitions, and measure whether large misreports persist and whether the average regret stays at $\widetilde{O}(\sqrt{T})$. A sharper targeted check comes from the paper's own Lemma B.3: in the two-agent identical-value example of Example 4, evaluate the inequality that must hold between the exploration loss ($1/(2K|E_\ell|^3)$) and the discounted manipulation benefit; the regime where $\gamma^{s_{\ell+1}}/(1-\gamma)$ exceeds that loss is precisely where the paper's proof no longer guarantees near-truthfulness.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 3.2 (formalized as Theorem A.2): under Assumptions 1 and 3, Algorithm 2 with the O-FTRL-FP dual update guarantees the existence of a Perfect Bayesian Equilibrium strategy profile $\pi^*$ under which the social-welfare regret relative to the offline optimal allocation is $R_T(\pi^*, \text{Algorithm 2}) = \widetilde{O}(\sqrt{T})$ and the long-term constraint violation is $B_T = 0$. The regret rate matches, up to logarithmic factors, the $\Omega(\sqrt{T})$ lower bound for the non-strategic version of the problem, so incentive compatibility comes at essentially no polynomial-order cost. The near-truthfulness of the equilibrium is what unlocks the faster rate: agents rarely misreport by more than $1/|E_\ell|$, so the planner can treat historical reports as approximately true signals, predict the loss of any candidate dual vector, and run an optimistic online learner. Plain FTRL cannot reach this rate, because the epoch structure needed for incentive compatibility triggers an $\Omega(T^{2/3})$ switching-cost barrier (Theorem 4.4) that only breaks once the losses acquire an almost-i.i.d. structure from truthful reports.

Load-bearing premise

The load-bearing premise is Assumption 1: every agent maximizes a $\gamma$-discounted payoff over the whole game, for a fixed discount factor $\gamma \in (0,1)$, and the guarantee degrades if agents are nearly patient, because the bound on the future benefit of manipulating the next epoch's dual is proportional to $\gamma^{s_{\ell+1}}/(1-\gamma)$, which diverges as $\gamma \to 1$, so the fixed exploration penalty no longer outweighs manipulation and the near-truthful equilibrium is not established.

Editorial extensions

If this is right

  • A planner can add robustness to strategic misreporting at no polynomial-order cost: $\widetilde{O}(\sqrt{T})$ regret with exact constraint satisfaction, against the $\Omega(\sqrt{T})$ lower bound in the truthful-agent benchmark.
  • Because agents are near-truthful in equilibrium, the planner's historical reports become trustworthy samples, which is what makes optimistic dual prediction possible and upgrades the rate from $T^{2/3}$ to $\sqrt{T}$.
  • The mechanism satisfies long-term constraints exactly ($B_T = 0$), since any allocation that would push cumulative cost past the budget is rejected immediately.
  • The epoch-based lazy update is necessary for incentives and sufficient for learning only in combination with exploration; the paper formalizes the trade-off as an $\Omega(T^{2/3})$ low-switching barrier for plain FTRL.
  • The framework extends to multi-unit multi-demand allocation, so the design principles carry beyond one-item-per-round settings.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The stabilise-then-predict recipe — freeze prices, punish deviations, then exploit the cleaner signal for optimistic learning — likely transfers to other settings where learning and incentives conflict, such as repeated auctions with budgets or procurement with strategic suppliers.
  • The O-FTRL-FP subroutine is a reusable primitive: an optimistic learner for decision-dependent, discontinuous loss predictions, applicable beyond mechanism design wherever the loss gradient depends on the chosen action through an argmax.
  • For nearly patient agents the paper's guarantees are silent; a testable extension would scale the exploration probability with $1/(1-\gamma)$ and check numerically how the regret constant degrades as $\gamma \to 1$.
  • The simulation suggests a stronger conjecture than the theorem: Q-learning agents not only live alongside a truthful equilibrium but converge to it; measuring convergence rates under different exploration schedules would settle this.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper studies repeated allocation of a single indivisible resource among K strategic agents over T rounds, under d long-term cost constraints. Agents hold private values and observe public costs; the planner knows neither value nor cost distributions. The authors propose the Incentive-Aware Primal-Dual (IAPD) framework combining epoch-based lazy dual updates, VCG-style adjusted payments, randomized exploration rounds, and a cumulative-cost rejection safeguard. Two dual-update rules are analyzed: FTRL and a novel Optimistic FTRL with Fixed Points (O-FTRL-FP). The paper claims, under a γ-impatient agent model and a smooth-cost assumption, the existence of a Perfect Bayesian Equilibrium with near-truthful reports, zero long-term constraint violation, and regret Õ(T^{2/3}) for FTRL and Õ(√T) for O-FTRL-FP, the latter matching the non-strategic lower bound up to polylogarithmic factors.

Significance. If correct, the √T regret guarantee under strategic behavior would be a notable contribution, indicating that incentive compatibility can be obtained at negligible asymptotic cost in constrained online allocation. The O-FTRL-FP fixed-point oracle is a novel and interesting technical device, and the appendix provides an extensive proof skeleton with several sophisticated concentration arguments (e.g., Lemmas C.4–C.8). The numerical study is a further strength. However, the main equilibrium theorem relies on an incentive analysis that explicitly excludes the mechanism's own feasibility-rejection rule when evaluating deviations, and this gap must be closed before the central claims are fully supported.

major comments (3)
  1. [Appendix B.2, Lemma B.3 and proof of Theorem B.5] The incentive analysis is conducted in the 'epoch-ℓ game with exploration rounds' specified by Lines 4 to 12 of Algorithm 2, i.e., without the cumulative-cost rejection rule in Lines 13–14. The proof of Theorem B.5 argues that Line 14 'has no effect' because of the stopping time T_v, but T_v is defined using the equilibrium path allocations. A unilateral deviation can change the cumulative cost process, so Line 14 can trigger at a round t ≤ T_v (where T_v is evaluated under π*) and reject the tentative allocation. When a tentative allocation is rejected, the agent receives utility 0 rather than v−p, so the exploration-round penalty −(u−v)²/(2K|E_ℓ|) used in the proof of Lemma B.3 is not incurred. Consequently, the key inequality preceding Eq. (17) is not justified for Algorithm 2 as stated, and the existence of the PBE π* asserted in Theorem B.5 (and used in Theorems 3.1 and 3.2) is not established. The proof needs to handle deviations that cause earlier triggering of Line 14, or the mechanism must be modified so that the rejection rule does not remove the exploration penalty.
  2. [Algorithm 2, Line 12 vs. Section 2.1 and Lemma B.1] Line 12 of Algorithm 2 allocates to argmax_i ũ_{t,i} with the maximization implicitly over agents i ∈ [K], while the analysis (Lemma B.1, the definition of e_i*_t in Eq. (13), and the benchmark in Eq. (2)) uses argmax over {0}∪[K], treating forfeiture as a dummy agent with zero value and zero cost. If the mechanism cannot forfeit in standard rounds, the payment becomes the second-highest among the K agents rather than max(0, second-highest), and the truthfulness argument in Lemma B.1 no longer applies. The algorithm should explicitly include the dummy option in the argmax, with forfeiture when the dummy wins, or the analysis must be reworked for a mechanism restricted to [K].
  3. [Appendix A.1, Theorem A.1] The theorem statement sets L = T^{1/3} and epoch length |E_ℓ| = T/L = T^{2/3}, but the proof's balancing step states 'Setting L = T^{2/3} and |E_ℓ| = T^{1/3}' and the subsequent regret calculation uses that choice. The statement should be corrected to L = T^{2/3}, |E_ℓ| = T^{1/3} to match the proof and the claimed Õ(T^{2/3}) regret. As written, the formal statement is internally inconsistent.
minor comments (6)
  1. [Appendix A.2, Theorem A.2] The definition of M_ℓ in Theorem A.2 depends on parameters ε and δ that are not specified in the theorem statement. The proof later sets ε = 1/(√T K²ε_c) and δ = 1/(6dT); these values (or an explicit statement that they are arbitrary constants) should be included in the theorem statement so that the regret bound is well-defined.
  2. [Section 4.2.5] The text 'more preciously' should read 'more precisely'.
  3. [Appendix B.2, Eq. (20)] In the displayed inequality in the proof of Theorem B.5, the term '3|E_ℓ|/|E_ℓ|' is equal to 3 and appears to be a typographical artifact; it should be written as the additive constant 3 from the union bound over the three failure events.
  4. [Algorithm 2, Line 14] When Line 14 rejects the tentative allocation by setting i_t = 0, the payment p_{t,i_t} for the tentative winner is not explicitly set to zero. The pseudocode should state that the payment is also canceled to avoid ambiguity.
  5. [Eq. (14)] In the definition of the stopping time T_v, the term '+1' should be written as the vector 1 ∈ R^d (or explicitly 'coordinate-wise +1') to avoid confusion between scalar and vector addition.
  6. [General] The title in the running header ('Efficiency, Feasibility, and Incentive-Awareness in Constrained Online Resource Allocation') differs from the title on the first page and in the abstract ('Incentive-Aware Dynamic Resource Allocation under Long-Term Cost Constraints'). The paper should use one consistent title.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the regret target is not an input to the equilibrium or fixed-point construction; self-citations are non-load-bearing.

full rationale

Walking the derivation chain, the main claims are not circular. The O-FTRL-FP update in Eq. (6) defines the predictor e_g_l(lambda_l) from historical reports and costs, and then solves a fixed-point problem; the paper explicitly proves the existence of (approximate) fixed points via Lemma C.4 and the approximate-continuity Lemma C.5, rather than assuming the predictor equals the true loss gradient. The near-truthfulness guarantee used in the regret analysis is derived independently in Lemma B.3 from the exploration-round penalty (u-v)^2/(2K|E_l|) and gamma-impatience; it does not import the O(sqrt(T)) regret bound as an input. Theorem B.5 constructs a PBE pi* that is independent of the dual-update subroutine, so Theorem C.3 can legitimately use it to bound the stability terms. The only self-citations are the gamma-impatient model in Assumption 1 (attributed to Golrezaei et al. 2021a, 2023) and a motivating remark that Lemmas B.3/B.4 are inspired by that line of work, but the paper does not rely on those citations as theorems; it provides its own proofs adapted to the cost-constrained setting. The skeptic's concern about Line 14's rejection rule erasing exploration penalties is a potential gap in the equilibrium proof, but it is not a circular reduction: a missing case in a proof is different from a conclusion being assumed as an input. No equation in the paper is defined in terms of the claimed regret, and no fitted parameter is renamed as a prediction. Overall, the derivation is self-contained apart from routine citations of standard online-learning tools.

Assumptions & free parameters 4 free parameters · 7 assumptions · 0 invented entities

No constants are fitted to data. The free parameters are standard algorithm tuning choices. The central claim rests on behavioral and distributional assumptions (γ-impatience, i.i.d. smooth costs) and on an assumed fixed-point oracle. The paper introduces no new physical or mathematical entities beyond the O-FTRL-FP algorithmic subroutine.

free parameters (4)
  • Epoch schedule for FTRL (L, |E_ℓ|) = Statement says L=T^(1/3), |E_ℓ|=T^(2/3); proof uses L=T^(2/3), |E_ℓ|=T^(1/3)
    Tuned to balance the Õ(L) PrimalAlloc term against the sqrt(Σ|E_ℓ|²) DualVar term; the formal statement and proof are inconsistent.
  • Epoch schedule for O-FTRL-FP (L, |E_ℓ|) = L=ceil(log T), |E_ℓ|=2^(ℓ-1)
    Doubling schedule in Theorem A.2 that keeps |E_ℓ|/Σ_{ℓ'<ℓ}|E_ℓ'| bounded by 2, which is used in the optimistic regret bound.
  • Learning rates η_ℓ = FTRL: η_ℓ ∝ (Σ|E_ℓ'|²)^(-1/2); O-FTRL-FP: η_ℓ ∝ (Σ|E_ℓ'|)^(-1/2)
    Classical FTRL/O-FTRL step-size choices, selected to minimize the final regret bounds.
  • Exploration probability and price distribution = 1/|E_ℓ| per round; p ~ Unif[0,1]
    The exploration probability creates an immediate expected loss of at least Ω(1/|E_ℓ|³) for a misreport of size 1/|E_ℓ|, which is the key deterrent in Lemma B.3.
assumptions (7)
  • domain assumption γ-impatient agents: each agent i maximizes E[Σ_{t=1}^T γ^t (v_{t,i} - p_{t,i}) 1[i_t=i]] for a fixed unknown γ∈(0,1).
    Assumption 1, Eq. (1). Discounting bounds the future gain from manipulating dual variables in Lemma B.3; as γ→1 the bound diverges and the guarantee disappears.
  • domain assumption Values and costs are i.i.d. across agents and rounds from fixed unknown distributions V_i and C_i.
    Section 2.1. Gives the near-i.i.d. loss structure in Claim 4.5 and justifies the statistical concentration arguments in Lemmas C.6-C.8.
  • domain assumption Smooth costs: for each i and each λ∈Λ, the density of λ^T c_i is uniformly bounded by ϵ_c.
    Assumption 3. Used in Lemma B.4 and Lemma D.3 to guarantee that small misreports rarely flip the argmax allocation; fails for deterministic or atomic cost distributions.
  • domain assumption Agents know the value and cost distributions and the mechanism; the planner does not know the distributions.
    Section 2.2. Needed to define PBE; the paper notes this is the hardest case for the planner.
  • standard math Standard results: FTRL and O-FTRL regret bounds, multiplicative Azuma-Hoeffding, vector Bernstein, Brouwer fixed point theorem, and partition of unity.
    Lemmas D.1-D.5 and Lemma C.4; used as black boxes without proof.
  • ad hoc to paper The planner can compute an (η_ℓ L_ℓ)-approximate fixed point of Eq. (6).
    Algorithm 4 requires solving a discontinuous fixed-point problem. Lemma C.4 proves existence non-constructively via Brouwer and partition of unity, but no efficient algorithm is provided; the Section 5 approximation Eq. (12) is not proven to preserve the regret guarantee.
  • ad hoc to paper Payments may be negative and do not enter the social welfare objective.
    Section 2.2. This conflicts with the money-burning framing in Section 1.1; negative payments are subsidies and would normally be a welfare cost.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficiency, Feasibility, and Incentive-Awareness in Constrained Online Resource Allocation." pith.science (2026). https://pith.science/paper/4HWE45P3

@misc{pith2026250709473,
  author       = {Pith},
  title        = {Pith review of: Efficiency, Feasibility, and Incentive-Awareness in Constrained Online Resource Allocation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4HWE45P3}},
  note         = {Machine review of arXiv:2507.09473}
}
abstract

We study the dynamic allocation of indivisible resources to strategic agents under long-term constraints, where the planner aims to maximize social welfare, satisfy multiple constraints, and elicit near-truthful reports. We find standard primal-dual methods fragile in this setting: agents easily manipulate their reports to distort dual variables, sacrificing social efficiency for individual utility. To address this, we propose the Incentive-Aware Primal-Dual (IAPD) framework. On the primal side, we integrate three components to suppress manipulation: a VCG-based payment neutralizes immediate misreporting benefits, while epoch-based lazy updates and random exploration together ensure potential future gains are outweighed by immediate penalties. On the dual side, to overcome a learning barrier due to lazy updates -- which we call the "price of incentives" -- we design a novel optimistic online learning algorithm, O-FTRL-FP. It utilizes a fixed-point oracle to resolve the circular dependency between optimistic dual variables and the resulting allocations. Ultimately, our mechanism attains $\tilde{\mathcal O}(\sqrt T)$ social welfare regret, satisfies all long-term constraints, and induces a near-truthful equilibrium. It also smoothly generalizes to multi-unit multi-demand allocation problems. Notably, this $\tilde{\mathcal O}(\sqrt T)$ regret near-matches the non-strategic $\Omega(\sqrt T)$ lower bound, demonstrating that incentive-awareness can be accommodated at nearly no cost.

Figures

Figures reproduced from arXiv: 2507.09473 by the authors.

Figure 1
Figure 1. We simulate a T-round game for 1000 trials, during which agents use Q-learning to optimize their reporting strategy. Under the vanilla primal-dual algorithm of Balseiro et al. (2023), agents learn to frequently misreport their values, resulting in reduced social welfare and low budget utilization (blue). In contrast, under our incentive-aware mechanism, agents gradually learn to report truthfully, leading to signifi… view at source ↗
Figure 2
Figure 2. From dual-optimal to actual allocations: fixing dual [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Vanilla Primal-Dual, Algorithm 2 with FTRL, and Algorithm 2 with O-FTRL-FP Approximation of the Fixed-Point Problem. Since the minimization in Eq. (11) can be computationally costly to solve, we also give the following alternative approximation of Eq. (10): λℓ = argmin λ∈Λ X ℓ ′<ℓ X τ∈Eℓ ′ (ρ − cτ,iτ ) Tλ + geℓ(λ) Tλ + 1 ηℓ Ψ(λ), (12) where we replace the original geℓ(λℓ) with geℓ(λ). The rationale of this approxima… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

62 extracted references · 53 canonical work pages

  1. [1]

    Patient mix optimisation and stochastic resource requirements: A case study in cardiothoracic surgery planning

    Ivo Adan, Jos Bekkers, Nico Dellaert, Jan Vissers, and Xiaoting Yu. Patient mix optimisation and stochastic resource requirements: A case study in cardiothoracic surgery planning. Health care management science, 12: 0 129--141, 2009

    work page 2009

  2. [2]

    A dynamic near-optimal algorithm for online linear programming

    Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. A dynamic near-optimal algorithm for online linear programming. Operations Research, 62 0 (4): 0 876--890, 2014

    2014

  3. [3]

    Learning prices for repeated auctions with strategic buyers

    Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Learning prices for repeated auctions with strategic buyers. Advances in neural information processing systems, 26, 2013

    work page 2013

  4. [4]

    Repeated contextual auctions with strategic buyers

    Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Repeated contextual auctions with strategic buyers. Advances in Neural Information Processing Systems, 27, 2014

    work page 2014

  5. [5]

    Uniformly bounded regret in the multisecretary problem

    Alessandro Arlotto and Itai Gurvich. Uniformly bounded regret in the multisecretary problem. Stochastic Systems, 9 0 (3): 0 231--260, 2019

    2019

  6. [6]

    A difficulty in the concept of social welfare

    Kenneth J Arrow. A difficulty in the concept of social welfare. Journal of political economy, 58 0 (4): 0 328--346, 1950

    work page 1950

  7. [7]

    Bandits with knapsacks

    Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knapsacks. Journal of the ACM (JACM), 65 0 (3): 0 1--55, 2018

    2018

  8. [8]

    Learning in repeated auctions with budgets: Regret minimization and equilibrium

    Santiago R Balseiro and Yonatan Gur. Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Science, 65 0 (9): 0 3952--3968, 2019

    work page 2019

Show all 62 references
  1. [9]

    Multiagent mechanism design without money

    Santiago R Balseiro, Huseyin Gurkan, and Peng Sun. Multiagent mechanism design without money. Operations Research, 67 0 (5): 0 1417--1436, 2019

    2019

  2. [10]

    The best of many worlds:: Dual mirror descent for online allocation problems

    Santiago R Balseiro, Haihao Lu, and Vahab Mirrokni. The best of many worlds:: Dual mirror descent for online allocation problems. Operations Research, 71 0 (1): 0 101--119, 2023

    2023

  3. [11]

    Robust pseudo-markets for reusable public resources

    Siddhartha Banerjee, Giannis Fikioris, and Eva Tardos. Robust pseudo-markets for reusable public resources. In Proceedings of the 24th ACM Conference on Economics and Computation, pages 241--241, 2023

    2023

  4. [12]

    To spend or to gain: Online learning in repeated karma auctions

    Damien Berriaud, Ezzat Elokda, Devansh Jalota, Emilio Frazzoli, Marco Pavone, and Florian D \"o rfler. To spend or to gain: Online learning in repeated karma auctions. arXiv preprint arXiv:2403.04057, 2024

    2024 arXiv

  5. [13]

    Convex analysis and optimization, volume 1

    Dimitri Bertsekas, Angelia Nedic, and Asuman Ozdaglar. Convex analysis and optimization, volume 1. Athena Scientific, 2003

    2003

  6. [14]

    Near-optimal mechanisms for resource allocation without monetary transfers

    Moise Blanchard and Patrick Jaillet. Near-optimal mechanisms for resource allocation without monetary transfers. arXiv preprint arXiv:2408.10066, 2024

    2024 arXiv

  7. [15]

    Market-oriented cloud computing: Vision, hype, and reality for delivering it services as computing utilities

    Rajkumar Buyya, Chee Shin Yeo, and Srikumar Venugopal. Market-oriented cloud computing: Vision, hype, and reality for delivering it services as computing utilities. In 2008 10th IEEE international conference on high performance computing and communications, pages 5--13. Ieee, 2008

    2008

  8. [16]

    Online learning with knapsacks: the best of both worlds

    Matteo Castiglioni, Andrea Celli, and Christian Kroer. Online learning with knapsacks: the best of both worlds. In International Conference on Machine Learning, pages 2767--2783. PMLR, 2022

    2022

  9. [17]

    Regret analysis of bilateral trade with a smoothed adversary

    Nicol \`o Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Regret analysis of bilateral trade with a smoothed adversary. Journal of Machine Learning Research, 25 0 (234): 0 1--36, 2024 a

    2024

  10. [18]

    The role of transparency in repeated first-price auctions with unknown valuations

    Nicol \`o Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. The role of transparency in repeated first-price auctions with unknown valuations. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 225--236, 2024 b

    2024

  11. [19]

    Multipart pricing of public goods

    Edward H Clarke. Multipart pricing of public goods. Public choice, pages 17--33, 1971

    1971

  12. [20]

    Positive results for mechanism design without money

    Richard Cole, Vasilis Gkatzelis, and Gagan Goel. Positive results for mechanism design without money. In Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems, pages 1165--1166, 2013

    2013

  13. [21]

    Non-monetary mechanism design without distributional information: Using scarce audits wisely

    Yan Dai, Moise Blanchard, and Patrick Jaillet. Non-monetary mechanism design without distributional information: Using scarce audits wisely. arXiv preprint arXiv:2502.08412, 2025

    2025 arXiv

  14. [22]

    Bandits with switching costs: T 2/3 regret

    Ofer Dekel, Jian Ding, Tomer Koren, and Yuval Peres. Bandits with switching costs: T 2/3 regret. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 459--467, 2014

    2014

  15. [23]

    The adwords problem: online keyword matching with budgeted bidders under random permutations

    Nikhil R Devanur and Thomas P Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM conference on Electronic commerce, pages 71--78, 2009

    2009

  16. [24]

    Near optimal online algorithms and fast approximation algorithms for resource allocation problems

    Nikhil R Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A Wilkens. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. Journal of the ACM (JACM), 66 0 (1): 0 1--41, 2019

    2019

  17. [25]

    Adaptive subgradient methods for online learning and stochastic optimization

    John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12 0 (7), 2011

    2011

  18. [26]

    Smoothed analysis of online non-parametric auctions

    Naveen Durvasula, Nika Haghtalab, and Manolis Zampetakis. Smoothed analysis of online non-parametric auctions. In Proceedings of the 24th ACM Conference on Economics and Computation, pages 540--560, 2023

    2023

  19. [27]

    Online stochastic packing applied to display ad allocation

    Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S Mirrokni, and Cliff Stein. Online stochastic packing applied to display ad allocation. In European Symposium on Algorithms, pages 182--194. Springer, 2010

    2010

  20. [28]

    Online resource sharing via dynamic max-min fairness: efficiency, robustness and non-stationarity

    Giannis Fikioris, Siddhartha Banerjee, and \'E va Tardos. Online resource sharing via dynamic max-min fairness: efficiency, robustness and non-stationarity. arXiv preprint arXiv:2310.08881, 2023

    2023 arXiv

  21. [29]

    Learning in repeated multiunit pay-as-bid auctions

    Rigel Galgana and Negin Golrezaei. Learning in repeated multiunit pay-as-bid auctions. Manufacturing & Service Operations Management, 27 0 (1): 0 200--229, 2025

    2025

  22. [30]

    A. Gibbard. Manipulation of voting schemes: A general result. Econometrica, 41 0 (4): 0 587--601, 1973

    1973

  23. [31]

    Real-time optimization of personalized assortments

    Negin Golrezaei, Hamid Nazerzadeh, and Paat Rusmevichientong. Real-time optimization of personalized assortments. Management Science, 60 0 (6): 0 1532--1551, 2014

    2014

  24. [32]

    No-regret learning in price competitions under consumer reference effects

    Negin Golrezaei, Patrick Jaillet, and Jason Cheuk Nam Liang. No-regret learning in price competitions under consumer reference effects. Advances in Neural Information Processing Systems, 33: 0 21416--21427, 2020

    2020

  25. [33]

    Dynamic incentive-aware learning:: Robust pricing in contextual auctions

    Negin Golrezaei, Adel Javanmard, and Vahab Mirrokni. Dynamic incentive-aware learning:: Robust pricing in contextual auctions. Operations Research, 69 0 (1): 0 297--314, 2021 a

    2021

  26. [34]

    Boosted second price auctions: Revenue optimization for heterogeneous bidders

    Negin Golrezaei, Max Lin, Vahab Mirrokni, and Hamid Nazerzadeh. Boosted second price auctions: Revenue optimization for heterogeneous bidders. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 447--457, 2021 b

    2021

  27. [35]

    Incentive-aware contextual pricing with non-parametric market noise

    Negin Golrezaei, Patrick Jaillet, and Jason Cheuk Nam Liang. Incentive-aware contextual pricing with non-parametric market noise. In International Conference on Artificial Intelligence and Statistics, pages 9331--9361. PMLR, 2023

    2023

  28. [36]

    The remarkable robustness of the repeated fisher market

    Artur Gorokh, Siddhartha Banerjee, and Krishnamurthy Iyer. The remarkable robustness of the repeated fisher market. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 562--562, 2021 a

    2021

  29. [37]

    From monetary to nonmonetary mechanism design via artificial currencies

    Artur Gorokh, Siddhartha Banerjee, and Krishnamurthy Iyer. From monetary to nonmonetary mechanism design via artificial currencies. Mathematics of Operations Research, 46 0 (3): 0 835--855, 2021 b

    2021

  30. [38]

    Incentives in teams

    Theodore Groves. Incentives in teams. Econometrica: Journal of the Econometric Society, pages 617--631, 1973

    1973

  31. [39]

    Strategy-proof allocation of multiple items between two agents without payments or priors

    Mingyu Guo and Vincent Conitzer. Strategy-proof allocation of multiple items between two agents without payments or priors. In AAMAS, pages 881--888, 2010

    2010

  32. [40]

    How the experts algorithm can help solve lps online

    Anupam Gupta and Marco Molinaro. How the experts algorithm can help solve lps online. Mathematics of Operations Research, 41 0 (4): 0 1404--1431, 2016

    2016

  33. [41]

    On strategy-proof allocation without payments or priors

    Li Han, Chunzhi Su, Linpeng Tang, and Hongyang Zhang. On strategy-proof allocation without payments or priors. In International Workshop on Internet and Network Economics, pages 182--193. Springer, 2011

    2011

  34. [42]

    Catch me if you can: Combatting fraud in artificial currency based government benefits programs

    Devansh Jalota, Matthew Tsao, and Marco Pavone. Catch me if you can: Combatting fraud in artificial currency based government benefits programs. arXiv preprint arXiv:2402.16162, 2024

    2024 arXiv

  35. [43]

    Dynamic reserve prices for repeated auctions: Learning from bids

    Yash Kanoria and Hamid Nazerzadeh. Dynamic reserve prices for repeated auctions: Learning from bids. In Web and Internet Economics: 10th International Conference, volume 8877, page 232. Springer, 2014

    2014

  36. [44]

    Primal beats dual on online packing lps in the random-order model

    Thomas Kesselheim, Klaus Radke, Andreas Tonnis, and Berthold Vocking. Primal beats dual on online packing lps in the random-order model. SIAM Journal on Computing, 47 0 (5): 0 1939--1964, 2018

    1939

  37. [45]

    Sub-sampled cubic regularization for non-convex optimization

    Jonas Moritz Kohler and Aurelien Lucchi. Sub-sampled cubic regularization for non-convex optimization. In International Conference on Machine Learning, pages 1895--1904. PMLR, 2017

    1904

  38. [46]

    A nearly linear-time ptas for explicit fractional packing and covering linear programs

    Christos Koufogiannakis and Neal E Young. A nearly linear-time ptas for explicit fractional packing and covering linear programs. Algorithmica, 70: 0 648--674, 2014

    2014

  39. [47]

    Simple and fast algorithm for binary integer and online linear programming

    Xiaocheng Li, Chunlin Sun, and Yinyu Ye. Simple and fast algorithm for binary integer and online linear programming. Mathematical Programming, 200 0 (2): 0 831--875, 2023

    2023

  40. [48]

    Cardinal bayesian allocation mechanisms without transfers

    Antonio Miralles. Cardinal bayesian allocation mechanisms without transfers. Journal of Economic Theory, 147 0 (1): 0 179--206, 2012

    2012

  41. [49]

    The geometry of online packing linear programs

    Marco Molinaro and Ramamoorthi Ravi. The geometry of online packing linear programs. Mathematics of Operations Research, 39 0 (1): 0 46--59, 2014

    2014

  42. [50]

    J.R. Munkres. Topology. Featured Titles for Topology. Prentice Hall, Incorporated, 2000. ISBN 9780131816299. URL https://books.google.com/books?id=XjoZAQAAIAAJ

    2000

  43. [51]

    Truthful greedy mechanisms for dynamic virtual machine provisioning and allocation in clouds

    Mahyar Movahed Nejad, Lena Mashayekhy, and Daniel Grosu. Truthful greedy mechanisms for dynamic virtual machine provisioning and allocation in clouds. IEEE transactions on parallel and distributed systems, 26 0 (2): 0 594--603, 2014

    2014

  44. [52]

    A modern introduction to online learning

    Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912.13213, 2019

    1912 arXiv

  45. [53]

    Online learning with predictable sequences

    Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, pages 993--1019. PMLR, 2013

    2013

  46. [54]

    Satterthwaite

    N.A. Satterthwaite. Strategy-proofness and A rrow's conditions: E xistence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10 0 (2): 0 187--217, 1975

    1975

  47. [55]

    Determining location and size of medical departments in a hospital network: A multiobjective decision support approach

    Christian Stummer, Karl Doerner, Axel Focke, and Kurt Heidenberger. Determining location and size of medical departments in a hospital network: A multiobjective decision support approach. Health care management science, 7: 0 63--71, 2004

    2004

  48. [56]

    Near-optimal primal-dual algorithms for quantity-based network revenue management

    Rui Sun, Xinshang Wang, and Zijie Zhou. Near-optimal primal-dual algorithms for quantity-based network revenue management. arXiv preprint arXiv:2011.06327, 2020

    2011 arXiv

  49. [57]

    Counterspeculation, auctions, and competitive sealed tenders

    William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16 0 (1): 0 8--37, 1961

    1961

  50. [58]

    Q-learning

    Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8: 0 279--292, 1992

    1992

  51. [59]

    Probability with martingales

    David Williams. Probability with martingales. Cambridge university press, 1991

    1991

  52. [60]

    Online fair allocation with best-of-many-worlds guarantees

    Zongjun Yang, Luofeng Liao, Yuan Gao, and Christian Kroer. Online fair allocation with best-of-many-worlds guarantees. arXiv preprint arXiv:2408.02403, 2024

    2024 arXiv

  53. [61]

    Online allocation and learning in the presence of strategic agents

    Steven Yin, Shipra Agrawal, and Assaf Zeevi. Online allocation and learning in the presence of strategic agents. Advances in Neural Information Processing Systems, 35: 0 6333--6344, 2022

    2022

  54. [62]

    Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits

    Julian Zimmert and Tor Lattimore. Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits. In Conference on Learning Theory, pages 3285--3312. PMLR, 2022

    2022

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.