Source-linked AI summary
Open problem: Computing the optimal deterministic budget-balanced mechanism
Vincent Conitzer
TL;DR
The paper asks whether the optimal deterministic mechanism can be computed in polynomial time under ex-post individual rationality, strategy-proofness, and strong budget balance. It frames the question as a mixed-integer program and contrasts it with tractable randomized cases and hardness in related deterministic settings.
Problem
Can expected-social-welfare-maximizing deterministic mechanisms satisfying ex-post individual rationality, dominant-strategy incentive compatibility, and strong budget balance be computed in polynomial time?
Source: §1 · p. 1Method
The formulation represents deterministic outcome selection and agent payments as variables in a mixed-integer linear program with the stated mechanism constraints.
Source: §1 · p. 1Results
Takeaways & Limitations
Randomization yields polynomial-time linear programs for constant-agent finite problems, while deterministic mechanisms can be hard in some settings and VCG is tractable without strong budget balance.
Source: §2 · pp. 1–2The formulation assumes a constant number of agents and explicitly enumerated finite type and outcome sets with rational-valued utilities.
Source: §1 · p. 1
Abstract
from arXiv · showhide
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.
1 The problem
The section formulates welfare-maximizing deterministic mechanism design as a polynomial-time question under ex-post individual rationality, dominant-strategy incentive compatibility, and strong budget balance.
1 The problem
- The model has a constant-size set of agents, explicitly enumerated finite type sets with priors, finite outcomes, and rational-valued utilities.The mechanism selects an outcome and payments as functions of reported types.Source: §1 · p. 1
- Can the optimal deterministic mechanism maximizing expected social welfare be computed in polynomial time while satisfying ex-post IR, dominant-strategy incentive compatibility, and strong budget balance?The formulation uses a deterministic outcome choice and payment variables.Source: §1 · p. 1
- Variants include ex-interim individual rationality, Bayes-Nash incentive compatibility, and weak budget balance, where surplus is burned rather than given to an outside party.Source: §1 · p. 1
2 Further background
The section contrasts deterministic mechanism-design complexity with tractable randomized formulations and highlights settings where deterministic optimization is already hard or easy.
2 Further background
- For a constant number of agents, allowing randomization makes these explicitly represented finite problems polynomial-time solvable through a linear program.The linear program drops the integrality constraints.Source: §2 · p. 1
- Without payments, welfare-optimal deterministic mechanisms are NP-hard even with one reporting agent; without strong budget balance, VCG makes the problem polynomial when payments do not reduce welfare.Source: §2 · p. 2
- Treating a mechanism’s surplus as a welfare loss leads to nontrivial problems, including variants studied by Guo and Conitzer (2009), Moulin (2009), Guo and Conitzer (2008), and de Clippel et al. (2009).Source: §2 · p. 2