Avoiding Cascading Failures for Time-of-Use Pricing
Talkat Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016) · 2016-09-19..09-23·
summary
Set static per-slot prices from the expected LP and dual prices so the expected demand per slot is below capacity, then prove that with a small multiplicative capacity slack (polylog in 1/ε) the online greedy arrivals obtain (1−ε) of the offline optimum. Proof builds a tree-of-trees reduction to capture all worst-case routings and uses a stochastic domination lemma to replace correlated forwards by independent arrivals; works even for adversarial arrival order and truthful, price-taking jobs.
AI-written summary · about
chapters (13)
- 0:00Avoiding cascading failures for time-of-use pricing
- 1:15Prophet inequality setting
- 4:16Example 2
- 6:09Online matching problem (cloud setting)
- 7:25The heart of the problem
- 10:05The hopping/forwarding process
- 11:40The hopping graph
- 13:14Easy case 1
- 17:59Idea of proof
- 21:27Formal version of part (0) Notation
- 22:43Reduction to Single Tree
- 28:37Reduction to cloud setting
- 29:10Related Work (incomplete)
related talks
40mA Bayesian Approach to Online Resource Allocation
48mA Simple Condition for Constant Regret in Online Decision-Making
29mLearning Outcomes in Queueing Systems
27mLearning and Optimization of Static and Dynamic Appointments
40mApproximation Algorithms for Optimization under Uncertainty
43mLearning about Auctions
01h 14mCompetitive Analysis Meets Stochastic Input: Secretary Problems And Prophet Inequalities
56mCompetitive Analysis of Online Algorithms (Part 1)