Abstract
In Bayesian mechanism design, Border’s theorem provides a powerful characterization of feasible interim allocation rules for single-item auctions, enabling efficient optimization. This paper investigates the possibility of extending this theorem to more complex environments, such as multi-item auctions and public projects. By leveraging the lens of computational complexity, the authors demonstrate that exact, computationally useful generalizations of Border’s theorem are unlikely to exist for these settings. Specifically, they show that finding such a characterization would imply the collapse of the polynomial hierarchy, as computing optimal revenue in these environments is #P-hard. Furthermore, the paper establishes a novel mathematical link between public project mechanisms and the Chow parameters of Boolean functions.
Introduction
A central challenge in Bayesian mechanism design is the exponential dimensionality of the problem space. To design an optimal auction, one must theoretically map every possible combination of bidder types to an outcome. To circumvent this, economists rely on "interim allocation rules"—the probability that a specific bidder receives an item, marginalized over the types of all other bidders. This reduction transforms an exponential problem into a linear one.
However, this reduction introduces a feasibility problem: not every set of interim probabilities corresponds to a valid, implementable ex-post auction. Border’s theorem (1991) solved this for single-item auctions by providing a set of linear inequalities to verify feasibility. For decades, a major open question has been whether a similar "Generalized Border’s Theorem" exists for more complex settings like public projects or multi-item auctions. This paper provides a definitive, complexity-theoretic answer to that question.
The Complexity of Feasibility
The authors first formalize what constitutes a "computationally useful" generalization of Border's theorem. A theorem is considered useful if it provides a system of linear inequalities that allows a researcher to recognize and test valid interim rules in polynomial time.
Using the Ellipsoid method, the authors establish a link between the existence of such a theorem and the complexity of optimization. They prove that if a computationally useful Border’s theorem exists for a given setting, then the problem of computing the optimal expected revenue (OptRev) or optimal expected welfare (OptWel) must reside within the complexity class $\text{P}^{\text{NP}}$. This class represents problems solvable in polynomial time given an oracle for NP-complete problems.
#P-Hardness and the Impossibility of Generalization
The core of the paper’s argument lies in proving that OptRev and OptWel are significantly harder than $\text{P}^{\text{NP}}$. Through a series of complexity reductions from known #P-complete problems (such as #Partition and #stConnectivity), the authors demonstrate that:
- OptRev is #P-hard for Boolean public projects, even under the simplest conditions (uniform distributions and binary valuations).
- OptWel is #P-hard for settings involving single-minded bidders, multi-item unit-demand auctions, and graphical matroids.
Because #P-hard problems are believed to lie outside $\text{P}^{\text{NP}}$, the existence of an exact, efficient Border’s theorem for these settings would cause the polynomial hierarchy to collapse. This suggests that the barrier to generalizing Border’s theorem is not a lack of mathematical ingenuity, but a fundamental limit of computation.
The Bridge to Boolean Functions
Beyond the impossibility results, the paper uncovers a deep structural connection between mechanism design and the Fourier analysis of Boolean functions. The authors show that the space of feasible interim allocation rules for a Boolean public project is mathematically identical to the space of feasible "Chow parameters" (the degree-0 and degree-1 Fourier coefficients) for bounded Boolean functions.
This equivalence allows the authors to export hardness results to the field of learning theory. They prove that testing whether a vector belongs to the Chow parameter polytope ($C_n$) is #P-hard. Geometrically, they characterize the vertices of this polytope, showing they correspond strictly to threshold functions (halfspaces). This implies that the "Chow parameters problem"—reconstructing a halfspace from its parameters—is likely intractable in its exact form.
Conclusion and Future Directions
The findings of this paper redefine the boundaries of what is possible in algorithmic mechanism design. By proving that exact characterizations are #P-hard, the authors provide a rigorous justification for the recent shift toward approximate Border’s theorems.
While exact solutions are computationally out of reach, the pursuit of approximation remains a fertile ground for research. Additionally, the bridge built between auction theory and Boolean functions suggests that tools from Fourier analysis may continue to yield insights into the limits of mechanism design and vice versa.
Summary updated