Open problem: Computing the optimal deterministic budget-balanced mechanism
arXiv:2610.08795
Abstract
This is an open problem originally posed during the program "Economics and Computation" held in the Fall 2015 semester at the Simons Institute for the Theory of Computing. It asks whether, in automated mechanism design, it is possible to compute the optimal deterministic budget-balanced mechanism in polynomial time. Some variants, also open to my knowledge, are also discussed.