Algorithmic Mechanism Design with Investment
summary
Shows that many fast approximation algorithms can drop from near‑optimal allocation performance to 0% once strategic investments are allowed, and proves the investment worst case is always deterministic. Introduces the condition confirming negative externalities and the class XCONE, proves non‑bossy algorithms are XCONE, and modifies the BKV FPTAS (rounding + dynamic programming) into an XCONE FPTAS for knapsack that preserves the 1−ε allocative guarantee for investment problems.
AI-written summary · about
chapters (11)
- 0:00Workshop introduction
- 2:55Algorithmic mechanism design
- 6:36Packing problems and notation
- 11:34Main findings overview
- 16:31Monotonicity and pricing
- 19:31Examples and applications
- 21:52Investment incentive proofs
- 28:04Worst case analysis
- 32:19FPtas evaluation
- 37:55Confirming externalities
- 43:44Robust algorithms and outlook
related talks
44mOnline Advertisements and Online Algorithms
59mMechanism Design with Limited Commitment
25mBudget Pacing in Repeated Auctions: Regret and Efficiency without Convergence
01h 03mConstructing Generic Algorithms: Principles and Practice
59mExact Performance Verification of First‑Order Methods in Parametric Convex Optimization
14mSelectively-Amortized Resource Bounding
50mDiversity in Matching Markets
32mDynamic Matching Models