Why Use Linear Programming for Partial Identification?
When a model does not identify a single value of a target parameter, the data and assumptions may still restrict it to a range. A useful way to calculate that range is to list the possible latent response types, assign an unknown population share to each type, and translate everything known about the observed data into constraints on those shares. If the target is a linear function of the shares, finding its smallest and largest feasible values is a linear program.
This approach is valuable because it makes the logic of a bound explicit. The decision variables represent possible latent populations; the constraints encode what those populations must reproduce in the observed data and what restrictions they must satisfy; and the objective represents the target. The resulting extrema are sharp when they are attainable by distributions of latent types that satisfy all the constraints.
From Latent Types to a Linear Program
Begin by defining the possible types so that each unit belongs to exactly one type. Their shares must therefore be nonnegative and sum to one. Next, express each observable event as a sum of the shares of the types that would produce that event. These equations connect the latent population to the observed distribution. Restrictions such as monotone response, known type-share limits, or equality across particular types can add more linear constraints.
In general, write the feasible set as \(Aq=b,\; Gq\le h,\; q\ge0\). Here \(q\) is the vector of type shares, \(Aq=b\) collects equality restrictions, and \(Gq\le h\) collects inequality restrictions. The condition that the shares sum to one is included among the equalities. For target \(L(q)=c^\mathsf{T}q\), solve one program to minimize \(L(q)\) and another to maximize it.
Observed probabilities are often estimated from a sample and then used as inputs to this calculation. The optimization describes the identified range under those input probabilities and restrictions; it does not, by itself, account for sampling uncertainty in the inputs. In this tutorial, the numerical examples treat the stated probabilities as fixed.
Worked Example: Bounding the Share Who Benefit
Worked Example: Bounding the Share Who Benefit
Consider a hypothetical randomized experiment with a binary treatment and a binary outcome. Let \(Y_0\) and \(Y_1\) denote a unit’s potential outcome without and with treatment. Suppose the observed outcome success rates are \(0.40\) in the control arm and \(0.60\) in the treatment arm. Random assignment and consistency allow these rates to be interpreted as the marginal probabilities \(P(Y_0=1)=0.40\) and \(P(Y_1=1)=0.60\). The joint distribution of the two potential outcomes remains unknown.
There are four latent response types, indexed by \((Y_0,Y_1)\). Let their shares be \(q_{00},q_{01},q_{10},q_{11}\). The target is the share who benefit, \(q_{01}=P(Y_0=0,Y_1=1)\). The type shares must satisfy
and the two observed marginal rates impose
Set \(t=q_{11}\). The constraints then give \(q_{10}=0.40-t\), \(q_{01}=0.60-t\), and, from the sum-to-one condition, \(q_{00}=t\). Nonnegativity requires \(t\ge0\), \(t\le0.40\), and \(t\le0.60\), so the full feasible range is \(0\le t\le0.40\). Consequently, \(q_{01}=0.60-t\) is smallest at \(t=0.40\) and largest at \(t=0\):
Both endpoints are attainable. At the lower endpoint, \((q_{00},q_{01},q_{10},q_{11})=(0.40,0.20,0,0.40)\); at the upper endpoint, the shares are \((0,0.60,0.40,0)\). Each distribution is nonnegative, sums to one, and reproduces both observed marginal rates. Thus the bound is sharp. Under the stated assumptions, the data are compatible with a share benefiting as low as 20% or as high as 60%; they do not identify a single share.
Why Attainable Endpoints Establish Sharpness
A linear-program solution is a sharp bound only if it describes the most extreme value that is compatible with the model—not merely an extreme value within an incorrectly specified set of constraints. The key justification has two parts. First, every population distribution allowed by the model must map to a feasible vector of type shares. Second, every feasible vector must correspond to a population distribution that satisfies the observed-data and model restrictions.
For a finite type list, the feasible set is defined by linear equalities and inequalities and nonnegative shares summing to one. It is closed and bounded, so if it is nonempty, a linear objective attains both its minimum and maximum. To establish that the resulting endpoints are sharp, check that the optimized type shares are feasible and that their target values equal the reported endpoints. If either endpoint cannot be attained by any compatible distribution, the reported interval is not sharp.
List mutually exclusive latent states that determine the observables and target.
Write one equation for each relevant observed probability, then add normalization, nonnegativity, and justified model restrictions.
Minimize and maximize the target; substitute each endpoint solution back into every constraint.
Worked Example: Adding a Linear Restriction
Worked Example: Adding a Linear Restriction
Return to the hypothetical experiment with \(P(Y_0=1)=0.40\) and \(P(Y_1=1)=0.60\). Suppose an additional, externally justified restriction states that at least \(0.30\) of the population has a stable outcome, meaning \(Y_0=Y_1\). This is an additional assumption about the joint distribution; it does not follow from the two observed marginal rates alone.
In type-share notation, stability means membership in type \(00\) or \(11\), so the new constraint is \(q_{00}+q_{11}\ge0.30\). As in the first example, the observed-data equations imply \(q_{00}=q_{11}=t\), \(q_{01}=0.60-t\), and \(q_{10}=0.40-t\). The new restriction becomes \(2t\ge0.30\), or \(t\ge0.15\). Nonnegativity still requires \(t\le0.40\), giving \(0.15\le t\le0.40\).
The target \(q_{01}=0.60-t\) is largest at \(t=0.15\) and smallest at \(t=0.40\), so the sharp bounds under this added restriction are
For the upper endpoint, \(t=0.15\) gives shares \((q_{00},q_{01},q_{10},q_{11})=(0.15,0.45,0.25,0.15)\). They sum to one, yield control success \(q_{10}+q_{11}=0.40\), yield treatment success \(q_{01}+q_{11}=0.60\), and have stable share \(0.15+0.15=0.30\). For the lower endpoint, \(t=0.40\) gives \((0.40,0.20,0,0.40)\); these shares satisfy the same observed probabilities and have stable share \(0.80\). Feasibility at both endpoints verifies sharpness. The narrower interval is conditional on the added restriction, not a consequence of the observed rates alone.
Feasibility Is a Substantive Check
A linear program can be infeasible: no vector of type shares may satisfy every encoded condition. Infeasibility is informative. It can indicate incompatible observed probabilities, a structural restriction contradicted by those probabilities, or a mistake in the type definitions or constraint equations. It is not a bound of zero width and should not be repaired by silently dropping a constraint.
Worked Example: Diagnosing an Infeasible Restriction
Suppose a hypothetical randomized experiment reports \(P(Y_0=1)=0.65\) and \(P(Y_1=1)=0.55\). Consider imposing monotone treatment response, \(Y_1\ge Y_0\) for every unit. For binary outcomes this rules out type \(10\), so \(q_{10}=0\).
The observed margins require \(q_{10}+q_{11}=0.65\), hence \(q_{11}=0.65\). They also require \(q_{01}+q_{11}=0.55\), hence \(q_{01}=0.55-0.65=-0.10\). This violates \(q_{01}\ge0\), so the linear program has no feasible solution.
The contradiction can also be seen by subtracting the two observed-margin equations:
Under monotone response, \(q_{10}=0\), making the difference equal to \(q_{01}\ge0\). But the stated rates give \(0.55-0.65=-0.10\). Therefore the observed margins and the monotonicity restriction cannot all hold together. A careful analysis would check the inputs and the restriction rather than report a sharp bound from an empty feasible set.
Common Mistakes and Practical Checks
- Optimizing the wrong quantity. The objective coefficients must represent the target for each type. For example, the share who benefit assigns coefficient one to type \(01\) and zero to the other types; it is not the same target as an average treatment effect.
- Forgetting normalization or nonnegativity. Without \(\sum_j q_j=1\) and \(q_j\ge0\), the variables may no longer represent population shares.
- Confusing observed margins with a joint distribution. The two marginal success rates constrain type shares, but generally do not determine them all. Additional restrictions must be stated and justified.
- Calling numerical extrema sharp without checking feasibility. Substitute the endpoint type shares into every equality and inequality, including the added structural restrictions.
- Treating infeasibility as evidence for a preferred conclusion. It means the encoded conditions have no common solution; revisit their compatibility before interpreting any bound.
Check Your Understanding
Use the type-share formulation to answer the following questions.
- In the first worked example, which two constraints encode the observed success rates in the treatment and control arms?
- Why does demonstrating feasible type distributions at both endpoints help establish sharpness?
- In the second example, express the minimum-stability restriction using the type shares, and explain why it narrows the feasible range of \(t\).
- Under monotone treatment response for binary outcomes, which latent type is ruled out?
- If a linear program is infeasible, name two possible sources of the conflict that should be checked before interpreting the result.