Multi-Dimensional and Non-Linear Mechanism Design and Approximation II
summary
A reduction maximizes the sum of single-agent revenues subject to interim feasibility constraints (Border-style inequalities) and shows an ex ante relaxation yields a marginal-revenue based approximation to the multi-agent optimum. Feasibility is characterized via a max-flow/min-cut construction, and symmetric problems admit the highest-quantile-wins ex post rule. For unit-demand uniform[0,1]^2 the paper proves the favorite-item projection is optimal. Multi-dimensional virtual values arise from Rochet integration by parts plus a reverse-engineered path choice to make the pointwise maximizer incentive compatible.
AI-written summary · about
chapters (10)
- 0:00Multi to single reductions
- 3:01Revenue linearity basics
- 8:56Approximate reductions
- 13:42Interim reduction theory
- 22:30Interim feasibility analysis
- 31:06Symmetric case properties
- 38:41Asymmetric feasibility
- 47:15Unit demand preferences
- 52:59Optimal item projection
- 1:01:56Multi-dimensional virtuals
related talks
51mMin-max Optimization: From Complexity to Algorithms
01h 04mSubmodularity: Theory and Applications II
12mEquilibrium Computation and the Foundations of Multi-Agent Machine Learning
25mPipeline Interventions
01h 11mA Theory of Multi-objective Machine Learning
01h 04mSubmodularity: Theory and Applications I
01h 00mMin-Max Optimization from a Dynamical Systems Viewpoint
57mComputationally Efficient Alternatives to Nonconvex-Nonconcave Min-Max Optimization