Beyond Worst-Case Budget-Feasible Mechanism Design
summary
Presents a simple randomized mechanism that partitions sellers, learns a best lottery of two take-it-or-leave-it payments on each half, and offers samples from the opposite half until spending B/2 on each side. Proves this mechanism is instance-optimal among uniform mechanisms, achieves strictly better than 1 − 1/e expected competitive ratio for any nontrivial budget distribution, is optimal under budget-smoothed analysis, and shows a robust upper bound of 0.854 for the worst-case market.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:26Problem setup
- 2:20An example mechanism
- 3:57Standard performance measure for mechanism
- 5:24Worst-case optimality doesn't generalize to typical case
- 7:18Benchmark class of mechanisms
- 9:47Instance optimality against uniform mechanisms
- 10:44Our mechanism in a nutshell
- 13:15A middle ground to compare with non- uniform mechanisms
- 15:33Our results for budget-smoothed analysis
- 16:48Technical overview - instance optimality
- 17:35Technical overview-budget-smoothed analysis
related talks
01h 10mComplexity and Algorithmic Game Theory II
01h 10mOn Algorithmic Game Theory II
20m(Almost) Perfect Discrete Iterative Load Balancing
01h 01mComplexity and Algorithmic Game Theory I
58mLower Bound Issues in Computational Social Choice
52mOn Algorithmic Game Theory I
33mManaging High-Bandwidth Memory is a Parallel Scheduling Problem
32mCompetitive Data Structure Dynamization