Linear Programming For Sharp Causal Bounds

From Partial Information to an Optimization Problem

When treatment is not randomized, the observed data reveal only one potential outcome for each unit: the outcome under the treatment actually received. If potential outcomes have finite support, the unknown population distribution can be represented by finitely many probabilities. Observed-data facts and stated assumptions then become constraints on those probabilities. A linear objective can select the smallest or largest causal effect compatible with all the constraints.

This formulation is useful when several restrictions must be imposed together. Instead of deriving separate bounds by hand and combining them informally, one writes down the full feasible set and optimizes over it. The result is sharp relative to the specified support, observed distribution, and restrictions: no compatible population has an effect outside the resulting interval, and each endpoint is attained by a compatible population.

The observed-data probabilities are \(p_{d,y}=P(D=d,Y=y)\), where \(Y=Y(D)\) is the observed outcome. Consistency, \(Y=Y(D)\), implies the constraints \(p_{0,y}=\sum_{y_1}q_{0,y,y_1}\) for \(y\in\mathcal{S}_0\), and \(p_{1,y}=\sum_{y_0}q_{1,y_0,y}\) for \(y\in\mathcal{S}_1\). The sums range over the unobserved potential outcome. These equations match the observed distribution but do not reveal the missing potential outcomes.

A general linear program has the form \(Aq=b,\ Cq\leq h,\ q\geq0\), with any required normalization included. Observed-data equations form part of \(Aq=b\). Additional restrictions may set some probabilities to zero, impose linear inequalities, or specify linear moments. For example, monotone treatment response, \(Y(1)\geq Y(0)\), sets \(q_{d,y_0,y_1}=0\) whenever \(y_1<y_0\). A known mean of a potential outcome is also linear in \(q\).

To find the lower endpoint, minimize \(\sum (y_1-y_0)q_{d,y_0,y_1}\) subject to all constraints. To find the upper endpoint, maximize the same expression over that same feasible set. The treatment probability is already represented in the \(q\)'s; it should not be used to reweight the objective a second time.

Why the Endpoints Are Sharp

The optimization is not just a convenient way to calculate conservative limits. It represents all distributions allowed by the model. The justification has two directions.

Moreover, every value between the endpoints is attainable. If \(q_L\) and \(q_U\) are feasible endpoint distributions, then \(q_\lambda=\lambda q_L+(1-\lambda)q_U\) is feasible for \(0\leq\lambda\leq1\), because the constraints are linear. Its objective is the same convex combination of the two endpoint values. Thus the identified set for the ATE is the entire interval between the program's minimum and maximum.

Adding Restrictions Without Losing the Linear Structure

An assumption tightens bounds only if it removes some otherwise feasible distributions. In a finite-support model, many restrictions can be represented directly by deleting cells or adding linear constraints. The mathematical effect is to shrink the feasible set; the scientific question is whether the restriction is credible for the population and setting.

For example, monotone treatment response for binary outcomes allows only the potential-outcome pairs \((Y(0),Y(1))=(0,0),(0,1),(1,1)\). It rules out the pair \((1,0)\). This restriction is not learned from the observed table alone; it is an additional assumption. The next example shows how it changes the program and the endpoint calculation.

The same construction accommodates external benchmarks or other linear moment information. A constraint such as \(E[Y(0)]=m_0\) becomes \(\sum_{d,y_0,y_1}y_0q_{d,y_0,y_1}=m_0\). It is important to encode the benchmark for the relevant population and variable: a conditional mean for controls is not interchangeable with a population mean of \(Y(0)\). The following example adds a hypothetical population benchmark to the unrestricted model.

Practical Checks, Alternatives, and Limits

Before interpreting endpoints, verify that the program describes the intended population and restrictions. Check that the observed cell probabilities are nonnegative and sum to one; confirm that each observed outcome is assigned to the potential outcome revealed by the treatment actually received; and check that the support includes every possible value allowed by the model. If additional constraints make the feasible set empty, at least one input, support choice, or assumption is incompatible with the others. Infeasibility is a diagnostic, not evidence that an optimizer has discovered causal information.

Numerical solvers can report an approximate optimum. Inspect constraint residuals, nonnegativity violations, and the reported feasibility and optimality tolerances. Recompute the objective from the returned \(q\)'s. On small problems, direct enumeration of feasible cells or hand algebra provides a useful check. A solver's endpoint alone does not identify a unique joint distribution: several different feasible distributions can attain the same endpoint.

For a simple problem, direct algebra may be quicker and easier to audit than software. Linear programming becomes valuable when many outcome levels, treatment groups, covariates, or benchmark restrictions create a large system that is difficult to reduce by hand. It can combine restrictions transparently, but it cannot rescue an unsupported assumption or turn an invalid benchmark into valid evidence.

The finite-support condition is substantive. A continuous outcome cannot be represented exactly by a finite list of support values unless the model itself justifies that restriction; discretizing it changes the problem and may change the bounds. Also, a linear program produces identified endpoints conditional on its supplied population probabilities and assumptions. Sampling uncertainty in estimated cell probabilities requires separate inferential treatment. The bounds do not, by themselves, quantify that uncertainty or establish that the assumptions are credible.

A common mistake is to treat an optimizer's endpoint as a point estimate of the causal effect, or to call it sharp without checking the model. The endpoint is the most extreme effect among distributions satisfying the encoded constraints. Sharpness is relative to those constraints and the stated support; if a relevant assumption was omitted, or an unjustified restriction was imposed, the resulting interval may not answer the intended causal question.