Fundamental Limits and Optimal Methods for Sharp Analytical Causal Bounds in Instrumental Variable Models

1. Problem Statement

The paper addresses the problem of partial identification in Instrumental Variable (IV) models, specifically focusing on deriving sharp analytical bounds for the Average Treatment Effect (ATE) and sharp testable implications (IV inequalities) for discrete outcomes.

• Context: When point identification fails (e.g., due to unobserved confounding), researchers seek the tightest possible range (bounds) for causal effects consistent with observed data and structural assumptions.
• The Conflict:
  • Optimization-based approaches (e.g., Balke-Pearl framework) yield sharp bounds but suffer from rapidly growing computational complexity as the number of outcome values ($n$) increases.
  • Heuristic/Algebraic approaches derive bounds using probability laws and inequalities (e.g., Fréchet inequalities). These are computationally cheaper and interpretable.
• The Core Question: Recent literature conjectured that heuristic algebraic methods could yield sharp analytical bounds with polynomial complexity, avoiding the exponential cost of optimization. This paper investigates whether such a computational separation is possible.

2. Methodology

The authors employ Linear Programming (LP) duality and polyhedral geometry to analyze the structure of the IV model.

• Primal Formulation: The set of full data distributions consistent with observed data and IV assumptions is modeled as a convex polytope $\Gamma(p)$ defined by linear constraints $M^\top q = p, q \geq 0$.
• Dual Formulation:
  • ATE Bounds: The sharp lower and upper bounds for the ATE correspond to the optimal values of the dual LP. The dual feasible region is a polyhedron $H$. Sharp bounds are obtained by maximizing/minimizing linear functionals over the vertices of $H$.
  • Testable Implications: The conditions for the observed data to be compatible with the IV model correspond to the feasibility of the primal. By the Theorem of the Alternative, this is equivalent to satisfying linear inequalities $p^\top r \leq 0$ for all extreme rays $r$ of the dual cone $K = \{r : Mr \leq 0\}$.
• Structural Analysis: Instead of relying on generic vertex enumeration algorithms (which are slow), the authors explicitly characterize the combinatorial structure of the vertices of $H$ and the extreme rays of $K$ using signature vectors (binary vectors encoding the active constraints).

3. Key Contributions

A. Fundamental Lower Bounds on Complexity

The paper proves that the perceived advantage of heuristic algebraic methods is illusory.

• Exponential Growth of Terms: For a discrete outcome with $n$ values, any sharp analytical bound for the ATE must be expressible as a maximum (or minimum) over a collection of linear terms whose cardinality grows exponentially with $n$ (specifically $\Omega(\ell n)$ for multi-valued instruments).
• Exponential Growth of Inequalities: Similarly, the number of necessary and sufficient IV inequalities (testable implications) grows exponentially with $n$.
• Conclusion: No family of polynomial-size linear analytical expressions can yield sharp bounds or a complete set of testable implications in general. The exponential complexity is an intrinsic feature of the IV model, not an artifact of specific algorithms.

B. Explicit Characterization of Sharp Solutions

Despite the exponential lower bound, the authors provide constructive solutions for the binary instrument case ($\ell=2$):

• Sharp ATE Bounds: They define a set of admissible signatures ($S$) and a vertex map ($u(b)$) that establishes a bijection between these signatures and the $M$-distinct vertices of the dual polyhedron. This allows the explicit construction of the sharp bounds as a maximum over $5 \times 4^{n-1} - 2^{n+2} + 4$ terms.
• Sharp IV Inequalities: They characterize the extreme rays of the dual cone $K$, deriving a non-redundant, necessary, and sufficient set of $2^{n+1} - 4$ inequalities. This improves upon previous results (e.g., Bonet 2001, Kédagni & Mourifié 2020) which provided redundant or insufficient sets.

C. Computationally Optimal Algorithms

• The authors developed software (Python/R) that computes these sharp bounds and inequalities with optimal output-sensitive complexity.
• Efficiency: The runtime is linear in the number of terms/inequalities (i.e., $O(\text{exponential})$). This is significantly faster than generic vertex enumeration methods (like causaloptim), which exhibit super-exponential runtime even for moderate $n$.
• Performance: Simulations show the proposed method computes bounds for $n=6$ (where generic methods fail) in milliseconds.

4. Key Results

Metric	Binary Instrument ($\ell=2$)	Multi-valued Instrument ($\ell > 2$)
Sharp ATE Terms	$5 \times 4^{n-1} - 2^{n+2} + 4$	$\ell((\ell-1)^{n-1} - (\ell-1))$
Sharp IV Inequalities	$2^{n+1} - 4$	$(n-1)\ell((\ell-1)^n - (\ell-1))$
Complexity Class	Exponential in $n$	Exponential in $n$

• Table 1 (from paper): Demonstrates the rapid growth. For $n=8$, the number of ATE bound terms is ~80,900, and IV inequalities are 508.
• Theoretical Implication: The gap between the "heuristic" approach and the "optimal" approach is not in complexity class (both are exponential for sharpness) but in the constant factors and the ability to generate the exact set without redundancy.

5. Significance and Impact

1. Settling a Theoretical Debate: The paper definitively refutes the conjecture that sharp analytical bounds can be derived with polynomial complexity. It establishes that exponential complexity is unavoidable for sharpness in discrete IV models.
2. Practical Tractability: By providing an explicit structural characterization (signatures and vertex maps), the authors make the computation of sharp bounds feasible for moderate outcome sizes ($n \approx 6-10$), which were previously intractable using standard polyhedral enumeration tools.
3. Methodological Rigor: The work unifies the derivation of ATE bounds and testable implications under a single dual LP framework, providing a complete and non-redundant characterization of the IV model's constraints.
4. Software Availability: The accompanying open-source code allows researchers to apply these theoretically optimal bounds in practice, bridging the gap between theoretical sharpness and computational feasibility.

In summary, the paper demonstrates that while sharp analytical bounds in IV models are inherently complex (exponential), they can be computed efficiently if one exploits the specific geometric structure of the problem, rather than relying on generic optimization solvers or incomplete heuristic inequalities.