pith. sign in

arxiv: 2512.02427 · v2 · submitted 2025-12-02 · 💻 cs.GT · cs.DS

Risk-Sensitive Online Selection with Bounded Adaptivity

Hossein Nekouyan , Bo Sun , Raouf Boutaba , Xiaoqi Tan This is my paper

Pith reviewed 2026-05-17 03:17 UTC · model grok-4.3

classification 💻 cs.GT cs.DS
keywords risk-sensitive online algorithmsconditional value-at-riskbounded adaptivityposted-price mechanismsonline primal-dualadversarial selectionrandomized algorithmstail risk control
0
0 comments X

The pith

A single random seed coordinates posted prices to improve lower-tail CVaR performance under bounded adaptivity.

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

The paper studies online adversarial selection where a decision maker must allocate a fixed number of resource units to arriving buyers using posted prices. It adds two requirements that are usually treated separately: performance must be reliable in bad random outcomes as measured by conditional value-at-risk, and the pricing policy can be updated only a limited number of times. The central construction is a mechanism that draws one shared random seed and uses it to set prices consistently across time periods. This shared seed produces a monotonic ordering among the possible price sequences, which concentrates outcomes away from the worst tail while staying inside the update limit. The same framework also supplies competitive ratios for both static and dynamic pricing and is tested on airline data to show tighter welfare distributions.

Core claim

We present a correlated posted-price mechanism that uses a single random seed to coordinate pricing decisions across time. This correlation induces a monotonic ordering of pricing profiles across sample paths, improving lower-tail performance while respecting the adaptivity constraint. The analysis develops a risk-sensitive randomized online primal-dual framework tailored to CVaR objectives and reveals a systematic trade-off between allowable adaptivity, risk sensitivity, and competitive performance.

What carries the argument

Correlated posted-price mechanism that shares one random seed across time steps to induce a monotonic ordering of pricing profiles across sample paths.

If this is right

  • Competitive guarantees hold for both static and dynamic pricing across multiple regimes of the problem parameters.
  • A clear trade-off emerges between the number of allowed policy updates, the degree of risk sensitivity, and the resulting competitive ratio.
  • Empirical tests on airline pricing data show improved welfare concentration and reduced tail behavior compared with uncorrelated baselines.

Where Pith is reading between the lines

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

  • The single-seed correlation idea could be tested in other online problems such as dynamic matching or inventory replenishment to limit downside outcomes.
  • Varying the number of shared seeds might reveal a tunable knob between full adaptivity and strict tail-risk control.
  • Real systems with update costs might adopt this structure to achieve reliable worst-case behavior without frequent re-optimization.

Load-bearing premise

Coordinating pricing decisions via a single random seed induces a monotonic ordering of pricing profiles that meaningfully improves lower-tail CVaR performance without violating the bounded-adaptivity constraint.

What would settle it

A concrete sequence of buyer valuations where the single-seed mechanism either produces a worse CVaR value than independent per-period randomization or requires more policy updates than the allowed bound.

Figures

Figures reproduced from arXiv: 2512.02427 by Bo Sun, Hossein Nekouyan, Raouf Boutaba, Xiaoqi Tan.

Figure 1
Figure 1. Figure 1: The performance comparison of the r-static, r-dynamic, and d-dynamic algorithms on a specific instance of the kSelection-(𝛿, Δ) problem, whose formal definition is provided in Section 2. The algorithms are characterized as follows: (i) the r-static algorithm, developed in [30], employs a single randomized price; (ii) the r-dynamic algorithm, introduced in [20], utilizes 𝑘 independent random seeds to genera… view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of cPPM-𝝓 with Δ = 2 (i.e., dynamic pricing with three total price levels), total units 𝑘 = 10, and reservation vector {𝑞1 = 𝑞2 = 3, 𝑞3 = 4}. When a random seed 𝑅 ∼ U (0, 1) is sampled, the three prices 𝑝1, 𝑝2, and 𝑝3 are generated according to the pricing functions 𝜙1, 𝜙2, and 𝜙3, respectively. By construction, the pricing functions satisfy 𝐿 = 𝜙1 (0) ≤ 𝜙1 (1) = 𝜙2 (0) ≤ 𝜙2 (1) = 𝜙3 (0) ≤ 𝜙3 … view at source ↗
Figure 3
Figure 3. Figure 3: Worst-case CVaR𝛿-CR of cPPM-𝝓 for 𝛿 ∈ {0.2, 0.6, 0.9} with 𝐿 = 1, 𝑈 = 100, and 𝑘 ranging from 3 to 100. The pricing functions are designed according to Theorem 3. • For all 𝑖 ∈  1, 2, . . . ,  𝑘 𝛼 DP 𝛿  , the pricing function is a constant: 𝜙𝑖(𝑥) = 𝐿. • For 𝑖 =  𝑘 𝛼 DP 𝛿  + 1, the pricing function 𝜙𝑖(𝑥) is defined as 𝜙𝑖(𝑥) =    𝐿 𝑥 ∈ [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Worst-case CVaR𝛿-CR of cPPM-𝝓 for 𝛿 ∈ {0.2, 0.4, 0.8} with 𝐿 = 1, 𝑈 = 100, and 𝑘 = 40, where the design of the pricing functions are according to Theorem 4, and we have max𝑖, 𝑗 |𝑞𝑖 − 𝑞 𝑗 | ≤ 1. the optimal online algorithm proposed by [36] determines the fractional allocation ˆ𝑥𝑡 for buyer 𝑡, given their valuation 𝑣𝑡 , according to the following utility maximization rule: 𝑥ˆ𝑡 = arg max 𝑥∈ [0,1] ( 𝑣𝑡𝑥 − 𝑘 ∫… view at source ↗
read the original abstract

Designing randomized online algorithms that perform reliably not only in expectation but also under unfavorable realizations of randomness is a fundamental challenge in online decision-making. In this paper, we study this challenge in online adversarial selection, where a decision maker allocates $k$ units of a resource to sequentially arriving buyers through posted prices. We focus on two intertwined considerations that are often overlooked simultaneously: tail-risk sensitivity and bounded adaptivity, where tail risk is measured using conditional value-at-risk (CVaR) and bounded adaptivity limits the number of allowable policy updates over time. Our main contribution is a correlated posted-price mechanism that uses a single random seed to coordinate pricing decisions across time. This correlation induces a monotonic ordering of pricing profiles across sample paths, improving lower-tail performance while respecting the adaptivity constraint. More broadly, our results highlight correlation as a mechanism for controlling tail risk in randomized online algorithms. Using this framework, we derive competitive guarantees for several regimes of the problem under both static and dynamic pricing. Our analysis develops a risk-sensitive randomized online primal-dual framework tailored to CVaR objectives and reveals a systematic trade-off between allowable adaptivity, risk sensitivity, and competitive performance. Experiments on real airline pricing data further illustrate the empirical impact of correlated pricing on welfare concentration and tail behavior.

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 / 2 minor

Summary. The paper studies risk-sensitive online adversarial selection with bounded adaptivity, where a decision maker allocates k units via posted prices to sequentially arriving buyers. It focuses on CVaR for tail risk and limits on policy updates. The main contribution is a correlated posted-price mechanism using a single random seed to coordinate decisions across time, inducing a monotonic ordering of pricing profiles across sample paths to improve lower-tail CVaR performance while respecting the adaptivity bound. The authors develop a risk-sensitive randomized online primal-dual framework for CVaR objectives, derive competitive guarantees for static and dynamic pricing regimes, and present experiments on airline pricing data showing impacts on welfare concentration and tail behavior.

Significance. If the central construction and analysis hold, the paper would offer a technically interesting approach to controlling tail risk in randomized online algorithms via correlation under adaptivity constraints. The risk-sensitive primal-dual framework and the identified trade-off between adaptivity, risk sensitivity, and competitive ratio could inform mechanism design in online resource allocation. The empirical results on real data provide some practical grounding, though their strength depends on the details of the data-handling and evaluation protocol.

major comments (2)
  1. [Abstract / main contribution] Abstract and main contribution paragraph: the claim that a single shared random seed produces a monotonic ordering of pricing profiles across sample paths, improving CVaR lower-tail performance while obeying the bounded-adaptivity constraint, is load-bearing for the central result. The skeptic's concern is valid on the given text: nothing shows that monotonicity is preserved when an adversarial arrival sequence forces an early policy update on one sample path but not another, both using the same seed. A concrete argument or proof that the limited number of updates suffices to maintain the ordering for every adversarial valuation sequence is required; without it the competitive guarantees for CVaR cannot be verified.
  2. [Framework description] Risk-sensitive randomized online primal-dual framework section: the abstract states that the framework is 'tailored to CVaR objectives' and yields competitive guarantees, yet provides no indication of how the CVaR objective is incorporated into the dual updates or how the single-seed correlation is analyzed within the primal-dual argument. If the performance bounds are derived only with respect to quantities internal to the same framework, the guarantees risk circularity and require an independent benchmark or external comparison to be convincing.
minor comments (2)
  1. [Abstract] The abstract would benefit from explicit statements of the competitive ratios obtained in the static and dynamic pricing regimes and the precise adaptivity bound (e.g., number of updates allowed).
  2. [Experiments] Experiments on airline data: the description mentions 'empirical impact' but does not specify the data-handling rules, number of runs, or error bars; adding these would improve reproducibility.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review of our manuscript. We address the major comments point by point below and indicate the revisions we plan to make.

read point-by-point responses

  1. Referee: [Abstract / main contribution] Abstract and main contribution paragraph: the claim that a single shared random seed produces a monotonic ordering of pricing profiles across sample paths, improving CVaR lower-tail performance while obeying the bounded-adaptivity constraint, is load-bearing for the central result. The skeptic's concern is valid on the given text: nothing shows that monotonicity is preserved when an adversarial arrival sequence forces an early policy update on one sample path but not another, both using the same seed. A concrete argument or proof that the limited number of updates suffices to maintain the ordering for every adversarial valuation sequence is required; without it the competitive guarantees for CVaR cannot be verified.

    Authors: We agree that an explicit argument for monotonicity preservation under adversarial arrivals is required. In the revised manuscript we will add a dedicated lemma (with full proof) showing that the shared seed forces synchronous update triggers across paths up to the adaptivity bound; any divergence is limited by the update budget, and the pricing functions remain ordered by construction of the single-seed mechanism. This lemma will be referenced from the abstract and main contribution paragraph. revision: yes

  2. Referee: [Framework description] Risk-sensitive randomized online primal-dual framework section: the abstract states that the framework is 'tailored to CVaR objectives' and yields competitive guarantees, yet provides no indication of how the CVaR objective is incorporated into the dual updates or how the single-seed correlation is analyzed within the primal-dual argument. If the performance bounds are derived only with respect to quantities internal to the same framework, the guarantees risk circularity and require an independent benchmark or external comparison to be convincing.

    Authors: We will expand the framework section to make the CVaR incorporation explicit: the dual update is modified to use a CVaR-adjusted subgradient that weights tail realizations according to the risk level. The single-seed correlation is analyzed by coupling sample paths and bounding the joint distribution directly in the primal-dual potential. To remove any appearance of circularity we will add a direct comparison of the resulting ratios against the classical (non-CVaR) online primal-dual benchmark from the literature. revision: yes

Circularity Check

0 steps flagged

No circularity: claims rest on independent mechanism design and analysis

full rationale

The abstract and provided excerpts describe a new correlated posted-price mechanism using a single random seed to induce monotonic ordering, followed by derivation of competitive guarantees via a risk-sensitive randomized online primal-dual framework. No equations, fitted parameters renamed as predictions, or self-citations are quoted that reduce the central result to its own inputs by construction. The monotonicity and CVaR improvement are presented as consequences of the mechanism design rather than tautological redefinitions, and the analysis is described as developing a tailored framework with explicit trade-offs, making the derivation self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, the paper introduces no explicit free parameters, new physical entities, or ad-hoc axioms beyond standard domain assumptions of online adversarial selection.

axioms (1)
  • domain assumption Standard assumptions of adversarial buyer arrivals and limited resource units hold for the online selection problem.
    Invoked implicitly to define the setting in which the correlated mechanism operates.

pith-pipeline@v0.9.0 · 5529 in / 1397 out tokens · 42666 ms · 2026-05-17T03:17:43.323354+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

38 extracted references · 38 canonical work pages

  1. [1]

    Ball and Maurice Queyranne

    Michael O. Ball and Maurice Queyranne. Toward robust revenue management: Competitive analysis of online booking.Operations Research, 57(4):950–963, 2009

    work page 2009

  2. [2]

    Single-leg revenue management with advice

    Santiago Balseiro, Christian Kroer, and Rachitesh Kumar. Single-leg revenue management with advice. InProceedings of the 24th ACM Conference on Economics and Computation, EC ’23, page 207, New York, NY, USA, 2023. Association for Computing Machinery

    work page 2023

  3. [3]

    Optimal thompson sampling strategies for support-aware cvar bandits

    Dorian Baudry, Romain Gautron, Emilie Kaufmann, and Odalric Maillard. Optimal thompson sampling strategies for support-aware cvar bandits. In Marina Meila and Tong Zhang, editors,Proceedings of the 38th International Conference on Machine Learning, volume 139 ofProceedings of Machine Learning Research, pages 716–726. PMLR, 18–24 Jul 2021

    work page 2021

  4. [4]

    Parametric demand learning with limited price explorations in a backlog stochastic inventory system.IISE Transactions, 51(6):605–613, 2019

    Boxiao Chen and Xiuli Chao. Parametric demand learning with limited price explorations in a backlog stochastic inventory system.IISE Transactions, 51(6):605–613, 2019

    work page 2019

  5. [5]

    Technical note—data-based dynamic pricing and inventory control with censored demand and limited price changes.Operations Research, 68(5):1445–1456, 2020

    Boxiao Chen, Xiuli Chao, and Yining Wang. Technical note—data-based dynamic pricing and inventory control with censored demand and limited price changes.Operations Research, 68(5):1445–1456, 2020

    work page 2020

  6. [6]

    Technical note—dynamic pricing and demand learning with limited price experimentation.Operations Research, 65(6):1722–1731, 2017

    Wang Chi Cheung, David Simchi-Levi, and He Wang. Technical note—dynamic pricing and demand learning with limited price experimentation.Operations Research, 65(6):1722–1731, 2017

    work page 2017

  7. [7]

    Risk-sensitive and robust decision- making: a cvar optimization approach

    Yinlam Chow, Aviv Tamar, Shie Mannor, and Marco Pavone. Risk-sensitive and robust decision- making: a cvar optimization approach. InProceedings of the 29th International Conference on Neural Information Processing Systems - Volume 1, NIPS’15, page 1522–1530, Cambridge, MA, USA, 2015. MIT Press

    work page 2015

  8. [8]

    Risk-sensitive online algorithms (ex- tended abstract)

    Nicolas Christianson, Bo Sun, Steven Low, and Adam Wierman. Risk-sensitive online algorithms (ex- tended abstract). In Shipra Agrawal and Aaron Roth, editors,Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 ofProceedings of Machine Learning Research, pages 1140–1141. PMLR, 30 Jun–03 Jul 2024

    work page 2024

  9. [9]

    Posted price mechanisms and optimal threshold strategies for random arrivals.Mathematics of Operations Research, 46(4):1452–1478, 2021

    Jos ´e Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. Posted price mechanisms and optimal threshold strategies for random arrivals.Mathematics of Operations Research, 46(4):1452–1478, 2021. 25

    work page 2021

  10. [10]

    Devanur, Kamal Jain, and Robert D

    Nikhil R. Devanur, Kamal Jain, and Robert D. Kleinberg. Randomized primal-dual analysis of ranking for online bipartite matching. SODA ’13, page 101–107, USA, 2013. Society for Industrial and Applied Mathematics

    work page 2013

  11. [11]

    Cvar optimization for mdps: Existence and computation of optimal policies

    Rui Ding and Eugene Feinberg. Cvar optimization for mdps: Existence and computation of optimal policies. 50(2):39–41, August 2022

    work page 2022

  12. [12]

    Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.Control- ling Tail Risk in Online Ski-Rental, pages 4247–4263

    work page

  13. [13]

    An economics-based analysis of ranking for online bipartite matching

    Alon Eden, Michal Feldman, Amos Fiat, and Kineret Segal. An economics-based analysis of ranking for online bipartite matching. InSymposium on Simplicity in Algorithms (SOSA), pages 107–110. SIAM, 2021

    work page 2021

  14. [14]

    Dynamic pricing with menu costs: Approximation schemes and applications to grocery retail.Manufacturing & Service Operations Management, 27(4):1087–1106, 2025

    Jacob Feldman and Danny Segev. Dynamic pricing with menu costs: Approximation schemes and applications to grocery retail.Manufacturing & Service Operations Management, 27(4):1087–1106, 2025

    work page 2025

  15. [15]

    Online contention resolution schemes with applications to bayesian selection problems.SIAM Journal on Computing, 50(2):255–300, 2021

    Moran Feldman, Ola Svensson, and Rico Zenklusen. Online contention resolution schemes with applications to bayesian selection problems.SIAM Journal on Computing, 50(2):255–300, 2021

    work page 2021

  16. [16]

    An Introduction in Discrete Time

    Hans F ¨ollmer and Alexander Schied.Stochastic Finance. An Introduction in Discrete Time. 5th revised and extended edition.De Gruyter, 5th revised and extended edition edition, 2025

    work page 2025

  17. [17]

    Improved online correlated selection.CoRR, abs/2106.04224, 2021

    Ruiquan Gao, Zhongtian He, Zhiyi Huang, Zipei Nie, Bijun Yuan, and Yan Zhong. Improved online correlated selection.CoRR, abs/2106.04224, 2021

    work page arXiv 2021

  18. [18]

    Real-time optimization of person- alized assortments.Management Science, 60(6):1532–1551, 2014

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

    work page 2014

  19. [19]

    T. P. Hill and Robert P. Kertz. Comparisons of stop rule and supremum expectations of i.i.d. random variables.The Annals of Probability, 10(2):336–345, 1982

    work page 1982

  20. [20]

    Posted price mechanisms for online allocation with diseconomies of scale

    Hossein Nekouyan Jazi, Bo Sun, Raouf Boutaba, and Xiaoqi Tan. Posted price mechanisms for online allocation with diseconomies of scale. InProceedings of the ACM Web Conference 2025 (WWW ’25), New York, NY, USA, April 2025. ACM

    work page 2025

  21. [21]

    Optimal algorithms for k-search with application in option pricing

    Julian Lorenz, Konstantinos Panagiotou, and Angelika Steger. Optimal algorithms for k-search with application in option pricing. InProceedings of the 15th Annual European Conference on Algorithms, ESA’07, page 275–286, Berlin, Heidelberg, 2007. Springer-Verlag

    work page 2007

  22. [22]

    Randomized rounding approaches to online allocation, sequencing, and matching, 2024

    Will Ma. Randomized rounding approaches to online allocation, sequencing, and matching, 2024

    work page 2024

  23. [23]

    Algorithms for online matching, assortment, and pricing with tight weight-dependent competitive ratios.Oper

    Will Ma and David Simchi-Levi. Algorithms for online matching, assortment, and pricing with tight weight-dependent competitive ratios.Oper. Res., 68(6):1787–1803, November 2020

    work page 2020

  24. [24]

    On policies for single-leg revenue management with limited demand information.Operations Research, 69(1):207–226, 2021

    Will Ma, David Simchi-Levi, and Chung-Piaw Teo. On policies for single-leg revenue management with limited demand information.Operations Research, 69(1):207–226, 2021

    work page 2021

  25. [25]

    Competitive analysis of online revenue management with two hierarchical resources and multiple fare classes.PLOS ONE, 17(10):1–11, 10 2022

    Guanqun Ni. Competitive analysis of online revenue management with two hierarchical resources and multiple fare classes.PLOS ONE, 17(10):1–11, 10 2022

    work page 2022

  26. [26]

    The i.i.d

    Sebastian Perez-Salazar, Mohit Singh, and Alejandro Toriello. The i.i.d. prophet inequality with limited flexibility.Mathematics of Operations Research, 0(0):null, 0. 26

    work page

  27. [27]

    Ruszczynski

    Alexander Shapiro, Darinka Dentcheva, and A. Ruszczynski. Lectures on stochastic programming: Modeling and theory. 2009

    work page 2009

  28. [28]

    Springer, New York, NY, 1 edition, 2011

    Hal Smith.An Introduction to Delay Differential Equations with Applications to the Life Sciences, volume 57 ofTexts in Applied Mathematics. Springer, New York, NY, 1 edition, 2011

    work page 2011

  29. [29]

    Online risk-averse submodular maximization

    Tasuku Soma and Yuichi Yoshida. Online risk-averse submodular maximization. In Zhi-Hua Zhou, editor,Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 2988–2994. International Joint Conferences on Artificial Intelligence Organization, 8 2021. Main Track

    work page 2021

  30. [30]

    Static pricing for online selection problem and its variants

    Bo Sun, Hossein Nekouyan Jazi, Xiaoqi Tan, and Raouf Boutaba. Static pricing for online selection problem and its variants. InThe 20th Conference on Web and Internet Economics, WINE 2024, Edinburgh, United Kingdom Proceedings ,December 2-5, 2024. Springer, 2024

    work page 2024

  31. [31]

    Lui, Don Towsley, and Danny H.K

    Bo Sun, Lin Yang, Mohammad Hajiesmaili, Adam Wierman, John C.S. Lui, Don Towsley, and Danny H.K. Tsang. The online knapsack problem with departures. InAbstract Proceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS ’23, page 59–60, New York, NY, USA, 2023. Association for Computing Machinery

    work page 2023

  32. [32]

    Distributionally-aware explo- ration for CVaR bandits

    Alex Tamkin, Ramtin Keramati, Christoph Dann, and Emma Brunskill. Distributionally-aware explo- ration for CVaR bandits. InNeurIPS 2019 Workshop on Safety and Robustness in Decision-making, Vancouver, Canada, Dec 2019. 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Workshop

    work page 2019

  33. [33]

    Mechanism design for online resource allocation: A unified approach.Proc

    Xiaoqi Tan, Bo Sun, Alberto Leon-Garcia, Yuan Wu, and D.H.K Tsang. Mechanism design for online resource allocation: A unified approach.Proc. ACM Meas. Anal. Comput. Syst. (SIGMETRICS ’20), 4(2), June 2020

    work page 2020

  34. [34]

    Threshold policies with tight guarantees for online selection with convex costs.ACM Transactions on Economics and Computation, 13(2):1–49, 2025

    Xiaoqi Tan, Siyuan Yu, Raouf Boutaba, and Alberto Leon-Garcia. Threshold policies with tight guarantees for online selection with convex costs.ACM Transactions on Economics and Computation, 13(2):1–49, 2025

    work page 2025

  35. [35]

    Zbaracki, Mark Ritson, Daniel Levy, Shantanu Dutta, and Mark Bergen

    Mark J. Zbaracki, Mark Ritson, Daniel Levy, Shantanu Dutta, and Mark Bergen. Managerial and customer costs of price adjustment: Direct evidence from industrial markets.The Review of Economics and Statistics, 86(2):514–533, 2004

    work page 2004

  36. [36]

    Budget constrained bidding in keyword auctions and online knapsack problems

    Yunhong Zhou, Deeparnab Chakrabarty, and Rajan Lukose. Budget constrained bidding in keyword auctions and online knapsack problems. InProceedings of the 17th International Conference on World Wide Web, WWW ’08, page 1243–1244, New York, NY, USA, 2008. Association for Computing Machinery. 27 A Proof of Lemma 1 Let𝐵 (𝑟2 ) 𝑡 be the set of buyers to whom a un...

    work page 2008

  37. [37]

    Fix any𝑟∈ [0,1]and suppose𝑦 (𝑟) 𝑡 ′ < 𝑞 1 at the arrival of𝑡 ′. Since|𝐵 ∗ 2|=𝑞 2 ≥𝑞 1, and each buyer in𝐵 ∗ 2 has valuation at least𝜙 1(1)while the posted price for the first𝑞 1 units is𝜙 1(𝑅) ≤𝜙 1(1)(as𝜙 1 is increasing), every buyer in𝐵 ∗ 2 accepts the price for those first𝑞 1 units. Thus these𝑞 1 units are fully sold by the arrival of the last buyer in𝐵 ∗

    work page

  38. [38]

    1− 1 𝛼 𝑒 𝛼(𝑤−𝑟 ∗ ) + 1 𝛼 − 𝑘 𝛼𝑞 𝑖∗ 1−𝑒 −𝛼𝑟 ∗ 𝑞𝑖∗ 𝑘 − 𝑘 𝛼𝑞 𝑖∗ −1 𝑒−𝛼𝑟 ∗ 𝑞𝑖∗ 𝑘 −𝑒 −𝛼 𝑟 ∗ 𝑞𝑖∗ 𝑘 +(1−𝑟 ∗ ) 𝑞𝑖∗ −1 𝑘 # ≥𝜙 𝐴+𝑟 ∗ 𝑞𝑖∗ 𝑘

    Repeating the same argument inductively for all𝑖≤𝑖 ∗ yields, for any𝑟∈ [0,1],𝑦 (𝑟) ≥ Í𝑖∗ −1 𝑖=1 𝑞𝑖, as claimed. C Continuation of the Proof of Theorem 1 Let us now continue the proof of the feasibility of the dual constraints for each buyer𝑡by considering the remaining cases. Case II:𝑖=𝑖 ∗ and𝜙 −1 𝑖 (𝑣 𝑡 )> 𝑟 ∗. In this case, we consider the following two...

    work page