Strategyproof Scheduling with Predictions
summary
Paper designs a strategyproof scheduling mechanism called scaled greedy that caps per-job scaling to avoid worst-case blowups, proving it is strategyproof, 3-consistent and 2n-robust (more generally 2+γ consistent and 1+1/γ · n robust). Key ideas: compute predicted optimal assignment, scale other machines’ reported times to make predicted winner cheapest but cap total scaling per machine to control robustness. Also gives an error-tolerant variant with approximation 3η^2 when prediction error ≤ η̂ and O(η̂^2 n) otherwise.
AI-written summary · about
chapters (9)
- 0:00Intro
- 1:25HM DESIGN WITH PREDICTIONS
- 2:33C SCHEDULING PROBLEM
- 8:47C SCHEDULING WITH PREDICTIONS
- 11:55OPTIMAL CONSISTENCY
- 14:45GREEDY V1- UNBOUNDED ROBUSTNESS
- 17:08BOUNDING INDIVIDUAL SCALAR
- 19:24BOUNDING THE SUM OF THE SCALAR
- 22:24SM DESIGN WITH PREDICTIONS
related talks
01h 04mParallel Game Engine Design
25mReal Algebraic Geometry in Computational Game Theory
15mTeamwork Makes The Von Neumann Work: Two Team Zero Sum Games
57mOptimising Data Building In Game Development
48mInformation Collection Through Strategic Agents
31mLearning in Games with Best-Response Oracles
33mKarp Plays a Game
47mMaintaining development costs while meeting the growing expectations of consumers