TL;DR
This paper investigates whether Border's theorem—a foundational result in mechanism design used to efficiently characterize feasible auction rules—can be generalized to broader settings like multi-item auctions or public projects. The authors prove that finding exact, computationally useful generalizations is impossible for most standard environments (assuming standard complexity class separations) because computing optimal revenue in these settings is #P-hard. Along the way, they uncover a surprising mathematical equivalence between optimal auctions for public projects and the Chow parameters of Boolean functions.
What Problem Does This Paper Address?
In Bayesian mechanism design, describing an auction mechanism usually requires exponential space because you have to map every possible combination of bidder types to an outcome. To make this mathematically and computationally tractable, economists use "interim allocation rules"—the average probability a bidder gets an item given their specific type, marginalized over everyone else's types. This reduces the problem size from exponential to linear.
However, there's a catch: not all interim rules are "feasible" (i.e., they don't all correspond to a valid, implementable ex-post auction). Border's theorem (1991) provides a clean set of linear inequalities to check if an interim rule is feasible, but it only applies to single-item auctions. For decades, researchers have wanted to generalize Border's theorem to multi-item auctions, public projects, and other complex settings to easily optimize mechanisms. This paper asks: Is a computationally useful, exact generalization of Border's theorem even possible for these broader settings?
Methods
The authors approach this economic problem through the lens of theoretical computer science and computational complexity:
- Defining a "Generalized Border's Theorem": They formalize what it means for a theorem to be "computationally useful." It must provide a system of linear inequalities where valid rules can be efficiently recognized and tested in polynomial time.
- The Ellipsoid Method Argument: They prove that if a generalized Border's theorem exists for a setting, then the problem of computing the optimal expected revenue (
OptRev) or welfare (OptWel) of a mechanism must belong to the complexity class $\text{P}^{\text{NP}}$ (problems solvable in polynomial time with an oracle for NP problems). - Complexity Reductions: They demonstrate that
OptRevandOptWelare actually #P-hard for very simple settings (like Boolean public projects or single-minded bidders) by reducing known #P-complete problems (like#Partitionand#stConnectivity) to them. - Boolean Function Analysis: They map the public project mechanism design problem directly to the Fourier analysis of Boolean functions, specifically optimizing over "Chow parameters" (degree-0 and degree-1 Fourier coefficients).
Datasets
Not discussed in the paper. (This is a theoretical computer science and algorithmic game theory paper that relies on mathematical proofs rather than empirical datasets).
Key Insights and Ideas
- The Complexity Barrier: The lack of a generalized Border's theorem isn't due to a lack of mathematical cleverness; it is blocked by a fundamental computational complexity barrier. Unless $\#\text{P} \subseteq \text{P}^{\text{NP}}$ (which would cause the polynomial hierarchy to collapse—a highly unlikely scenario in computer science), exact generalized Border's theorems cannot exist.
- Hardness of "Solved" Problems: Computing the expected revenue of an optimal mechanism is #P-hard even when the optimal mechanism itself is trivial to describe and execute. For example, Myerson's optimal auction tells us exactly what to do (maximize virtual welfare), but calculating exactly how much money that auction will make on average is computationally intractable.
- A Bridge to Boolean Functions: The space of feasible interim allocation rules for a Boolean public project is mathematically identical to the space of feasible Chow parameters for bounded Boolean functions. This creates a fascinating bridge between classical auction theory and Fourier analysis.
- Approximation is Unavoidable: Because exact characterizations are #P-hard, the recent trend in algorithmic game theory of finding approximate Border's theorems is not just a stepping stone—it is a necessary compromise.
Key Results
OptRevis #P-hard for the Boolean public project setting, even when the valuation distribution is uniform and every player only has two possible valuations.OptWelis #P-hard for single-minded bidders (even when bundles only contain two items), multi-item unit-demand auctions, and graphical matroids.- Chow Parameter Hardness: Testing whether a given vector belongs to the polytope of valid Chow parameters ($C_n$), or optimizing a linear function over this polytope, is #P-hard.
- Geometric Characterization: The vertices of the Chow parameter polytope $C_n$ are in a strict one-to-one correspondence with halfspaces (threshold functions).
Limitations and Future Work
Limitations: The impossibility results rely on standard, widely believed complexity assumptions (specifically that $\#\text{P} \not\subseteq \text{P}^{\text{NP}}$). If these assumptions were somehow proven false, the barrier would dissolve. Furthermore, the paper strictly rules out exact characterizations, leaving the door open for approximate solutions.
Future Work: The authors note that their negative results strongly validate the pursuit of approximate Border's theorems for algorithmic mechanism design. Additionally, their findings shed light on the "Chow parameters problem" in learning theory (reconstructing a halfspace from its Chow parameters). The #P-hardness of testing membership in the Chow polytope suggests that the exact version of the Chow parameters problem is likely intractable, pointing researchers toward focusing entirely on approximate reconstruction algorithms.
Summary updated