Unified Sharp Bounds on Probabilities of Causation

Introduction

Many decisions turn on how a particular individual would respond to different treatments, not on how the population responds on average. A retailer may want to know whether a customer would buy at one price but not at another; a marketer may want to know whether someone would answer an e-mail campaign but ignore a phone call. Questions of this kind are probabilities of causation (PoCs) [10]. They concern a unit’s outcomes under several treatments at once, and since we never observe more than one of these for the same unit, PoCs are in general not point-identified. Experimental data $P(y_i\mid x_j)$ and observational data $P(x_j,y_i)$ only determine an interval, and the quantity of interest is the sharp interval, i.e. the set of all values consistent with the data.

When treatment and outcome are binary, the sharp bounds have long been known [14]. They were derived with Balke’s linear-programming method [2, 1] and later proved analytically [7, 8]. Once the variables take more than two values, things get harder. Balke’s program still applies, but it needs one variable for every pair of response type and received treatment, which for $n$-valued variables means $n^n \cdot n$ variables. It can therefore only be solved for small $n$, and it gives no closed form. Zhang et al. [2022] solve an optimisation problem for each instance, and Li and Pearl [2024] give recursive bounds that are valid but not sharp. Shu et al. [2026] derived closed-form bounds for four families of PoCs, PNS($k$), PSub($k,p$), PRep($k,q$) and PN($k,p,q$), and showed that equivalence classes and relabelling reduce general discrete PoCs to these four. They proved the bounds valid in every dimension and checked numerically that they are sharp for three- and four-valued variables, but whether they are sharp in general was left as a conjecture. The difficulty is that a direct proof has to handle the vertices of a polytope whose dimension grows faster than exponentially in $n$.

Contributions.

• We prove that the closed-form bounds of Shu et al. [2026] for PNS($k$), PSub($k,p$), PRep($k,q$) and PN($k,p,q$) are sharp in every dimension.

• We prove two lemmas that make the sharpness proof manageable. The first reduces Balke’s program from $n^n \cdot n$ variables to $2^k \cdot n$, and the second reduces the $2^k$ candidate cuts for the lower bound to just $k+2$.

• We show that all four families, together with their relabellings, are special cases of one general formula, which gives the sharp bounds for any such query in closed form.

Section 4 gives the full proof for PNS$(k)$, and extends it to the other three families. Section 5 combines all four into a single theorem.

Preliminaries

This section recalls the definitions of probabilities of causation and the notation of structural causal models (SCMs) [5, 6]. Readers who know SCMs can skip it.

In an SCM, counterfactuals have a precise meaning. The statement “$Y$ would have been $y$ had $X$ been $x$” is written $Y_x = y$, where the subscript $x$ refers to a hypothetical intervention. To keep the notation short, we write $y_x$, $y_{x'}$, $y'_x$ and $y'_{x'}$ for the events $Y_x = y$, $Y_{x'} = y$, $Y_x = y'$ and $Y_{x'} = y'$. Throughout, $X$ is the treatment and $Y$ the outcome. Unless stated otherwise, experimental data are causal effects such as $P(y_x)$, and observational data are joint probabilities such as $P(x,y)$.

When $X$ and $Y$ are binary, we write $x$ and $x'$ for $X = \mathrm{true}$ and $X = \mathrm{false}$, and $y$ and $y'$ for $Y = \mathrm{true}$ and $Y = \mathrm{false}$. Pearl [ [10] defined three basic probabilities of causation.

Definition 1 (Probabilities of causation [10]).

PNS is the probability that $y$ responds to $x$ in both directions: $y$ occurs with $x$ and fails to occur without it. It therefore captures both the sufficiency and the necessity of $x$ for $y$. Tian and Pearl [ [14] obtained tight bounds on PN, PS and PNS with Balke’s linear-programming method [2], and Li and Pearl [ [7, 8] later proved these bounds analytically.

Now let $X$ and $Y$ each take $n$ values. Li and Pearl [ [9] named four multi-valued probabilities of causation, PNS, PSub, PRep and PN, and gave recursive bounds for them. Shu et al. [ [13] kept the names but rewrote each quantity so that the $j$-th counterfactual always pairs $y_j$ with $x_j$:

with $k \le n$ and $p \ne j$ for $1 \le j \le k$. Here PNS$(k)$ is the probability that the same individual would have outcome $y_j$ under $x_j$ for every $j = 1,\ldots,k$. Shu et al. [ [13] derived closed-form bounds for all four quantities, and by their equivalence-class and replaceability theorems, any discrete PoC can be brought into one of these four forms. We refer to Shu et al. [ [13] for the bounds and the two theorems, in this paper we prove that the bounds are sharp.

Notation and Definition

The treatment $X$ takes values $x_1,\ldots,x_n$ and the outcome $Y$ takes values $y_1,\ldots,y_n$; as in Shu et al. [ [13], unequal cardinalities are handled by padding values of probability zero. We write $[n] = \{1,\ldots,n\}$. The index $i$ runs over outcomes and $j,\ell$ over treatments; $p$ denotes an additional treatment and $q$ an additional outcome.

We work in structural causal models without further structural assumptions, and we reason with events throughout. With a slight abuse of notation, we write $x_j$ for the event $\{X = x_j\}$, i.e. that the unit received treatment $x_j$, and $y_i$ for the event $\{Y = y_i\}$, i.e. that the outcome was $y_i$. The counterfactual event $y_{i x_j}$ means “under $x_j$ the outcome would be $y_i$”; for fixed $j$ these events form a partition. If we arrange the observational probabilities $\mathbb{P}(x_j,y_i)$ in a table with one column per treatment and one row per outcome, the event $x_j$ is the $j$-th column and each entry $Q_{ij} := (x_j,y_i)$ is a cell; as for $b_{ij}$, the first index of $Q$ is the row and the second the column. The columns partition the sample space, so $\mathbb{P}(E)=\sum_j\mathbb{P}(E,x_j)$ for every event $E$.

We now introduce new notations for probabilities:

The two kinds of data are linked by consistency [5, 11, 12]: a unit that received $x_j$ has outcome $y_i$ exactly when its potential outcome under $x_j$ is $y_i$, i.e. $x_j\cap y_{i x_j}=x_j\cap y_i$. Hence

A compatible model is a joint law of a response type $R=(R_1,\ldots,R_n)\in[n]^n$, where $R_j:=Y_{x_j}$, and a received treatment $X\in[n]$, with $\mathbb{P}(R_j=i)=a_{ij}$ and $\mathbb{P}(R_j=i,X=j)=b_{ij}$; the observed outcome is $R_X$. Let $\mathcal{M}$ be the set of compatible models, assumed non-empty.

A value $r=(r_1,\ldots,r_n)\in[n]^n$ of $R$ is also called a response type; it lists an individual’s outcome under every treatment ($r_\ell=i$ means $y_{i x_\ell}$ holds). It is a function from treatments to outcomes, so there are $n^n$ types.

Let’s fix $1\le k\le n$ and put

By (2), $A_j\cap x_j$ is the observed cell $Q_{jj}=(x_j,y_j)$, so $\beta_j$ is the only observed part of $A_j$. But $A_j$ is defined for every individual, whichever treatment it actually received, so it also has mass outside column $x_j$. This mass is $d_j=\mathbb{P}(A_j\setminus x_j)=\mathbb{P}(A_j)-\mathbb{P}(A_j,x_j)$, and it is spread over the other columns $x_\ell$, $\ell\ne j$. We write

for the mass of $A_j$ in column $x_\ell$. Thus $m_{jj}=\beta_j$, $\sum_{\ell\ne j}m_{j\ell}=d_j$ and $0\le m_{j\ell}\le c_\ell$. Only the diagonal entry $m_{jj}$ is observed; for $\ell\ne j$, $m_{j\ell}$ is not determined by the data.

Each of the four families PNS, PSub, PRep and PN has the form $\theta=\mathbb{P}(S,G)$ for some factual event $G$, i.e. a union of cells:

with $p>k$. Here $\Omega$ denotes the whole sample space. Queries with other target outcomes reduce to these by relabelling. Let $\Theta:=\{\theta(M):M\in\mathcal{M}\}$.

Let $\mathcal{G}:=\{(i,\ell):Q_{i\ell}\subseteq G\}$ be the set of cells that make up the factual event $G$ (all cells for PNS, column $p$ for PSub, row $q$ for PRep, the single cell $Q_{qp}$ for PN); a pair $(i,\ell)\in\mathcal{G}$ refers to row $i$ (the observed outcome) and column $\ell$ (the received treatment). For a response type $r\in[n]^n$, let

record which of the targets $A_1,\ldots,A_k$ it satisfies. Call a triple $(W,i,\ell)$, with $W\subseteq[k]$ and $i,\ell\in[n]$, consistent if, whenever $\ell\le k$, $\ell\in W\Longleftrightarrow i=\ell$. This consistency: a unit that received $x_\ell$ ($\ell\le k$) satisfies $A_\ell$ if and only if its observed outcome is $y_\ell$.

This inequality is the key to the lower bound: in Lemma 14 it rules out all candidate lower bounds except the three in Theorem 7.

The two programs. Recall that $\mathcal{G}=\{(i,\ell):Q_{i\ell}\subseteq G\}$ is the set of cells that make up the factual event $G$ (all cells for PNS, column $p$ for PSub, row $q$ for PRep, the single cell $Q_{qp}$ for PN). A compatible model is determined by the joint probabilities $\mathbb{P}(R=r,X=\ell)$ [1, 14].

Balke’s program treats each of them as a variable $h_1(r,\ell)\geq0$, one for every response type $r\in[n]^n$ and received treatment $\ell\in[n]$, i.e. $n^n\cdot n$ variables:

An experimental constraint sums over all received treatments, so it only involves the response type $r$. An observational constraint looks at a single column, so it also needs the received treatment $\ell$. We cannot drop $\ell$ because the observational data cannot be written down without it, and they do carry information. If treatment were assigned independently of the response type, as in a randomized trial, then $b_{ij}=c_j a_{ij}$ and the observational data would tell nothing new. They help only when the choice of treatment depends on the response type, i.e. under confounding.

The reduced program has one variable $h_2(W,i,\ell)\geq0$ for every consistent triple, i.e. at most $2^k\cdot n^2$ variables:

Recall that $[n]=\{1,\ldots,n\}$. The reduced program keeps the experimental constraints only for $a_{jj}$ ($j\leq k$), and keeps all observational constraints $\sum_W h_2(W,i,\ell)=b_{i\ell}$. It drops every $a_{ij}$ with $i\neq j$, or when $j>k$.

For $j\leq k$, these constraints and consistency give three more identities. The column $x_j$ has mass $c_j$, the part of it inside $A_j$ has mass $\beta_j$, and the rest has mass $c_j-\beta_j$:

The feasible set of (5) is a polytope and $\theta$ is linear, so $\Theta=[\min\Theta,\max\Theta]$ and the sharp bounds are the two optima of (5). Shu et al. [2026] used this program to check sharpness numerically for $n\leq4$.

The last sentence holds because they both describe the same thing. In an admissible system, the events $A_1,\ldots,A_k$ cut each cell $Q_{i\ell}$ into pieces. Each piece is labelled by the set $W\subseteq[k]$ of events that contain it, and $h_2(W,i,\ell)$ is its mass. Conversely, cutting the cells according to a feasible $h_2$ gives an admissible system, see Appendix.

Proof idea. Both inclusions are constructive (see Appendix). Merging: given a feasible $h_1$, grouping the response types by $W(r)$ and by the observed outcome gives a feasible $h_2$ with the same value. Splitting: given a feasible $h_2$, we keep $W$, the observed outcome and the received treatment of each block fixed, and draw every other coordinate $r_j$ independently from an explicit distribution built from the data. The constraints of (6) are exactly what makes the result satisfy all constraints of (5).

The proof of Corollary 5 is in Appendix. The corollary also shortens the equivalence-class arguments of Shu et al. [ [13]: adding outcome or treatment values of probability zero leaves $(\alpha,\beta,c)$ unchanged up to empty columns.

Sharpness principle. Soundness and attainability together give sharpness.

Proof. By Lemma 4, $U$ is a valid upper bound: $\theta(M)\le U$ for all $M\in\mathcal{M}$. Suppose some $U'$ satisfied (H1) $\theta(M)\le U'$ for every $M\in\mathcal{M}$ and (H2) $U'<U$. The attaining system gives, via Lemma 4, a model $M_0\in\mathcal{M}$ with $\theta(M_0)=U$, and (H1) applied to $M_0$ gives $U\le U'<U$, a contradiction. The lower bound is symmetric.

Main results

In this section, we first prove sharpness of the bounds on PNS($k$) and then extend it to the other three families.

Problem Statement

Soundness of the bounds for all four families, PNS, PSub, PRep and PN, was proved by Shu et al. [ [13]. We prove completeness, which together with soundness shows that the bounds are sharp.

We restate the PNS($k$) theorem in our notation below.

We write $U_3$ over subsets $I$ to make clear that its indices are distinct. A repeated index would give an invalid bound.

The upper bound proof

By Lemma 4 we can work with admissible systems, and by Lemma 6 the proof splits into two parts, soundness (Corollary 9) and attainability (Lemma 11). Soundness was shown by Shu et al. [2026]; we re-derive it here because the same three properties drive the construction in Lemma 11. Throughout, let $\theta_\ell:= \mathbb{P}(S, x_\ell)$ denote the part of $\theta$ that lies in column $\ell$.

Proof. (Prop1) The columns $x_1,\ldots,x_n$ partition the space, so $S$ is the disjoint union of the sets $S \cap x_\ell$. (Prop2) For $j \le k$, $S \subseteq A_j$ gives $S \cap x_j \subseteq A_j \cap x_j$, which has mass $\beta_j$. For $\ell> k$, $S \cap x_\ell\subseteq x_\ell$, which has mass $c_\ell$. (Prop3) By (Prop1), $\theta- \theta_j = \mathbb{P}(S \setminus x_j)$. Since $S \subseteq A_j$, $S \setminus x_j \subseteq A_j \setminus x_j$, which has mass $\alpha_j - \beta_j = d_j$.

Proof. We derive each of the three upper bounds in Theorem 7 from Proposition 8.

• $U_1$. By (Prop1) and (Prop2), $\theta= \sum_{j \le k} \theta_j + \sum_{\ell> k} \theta_\ell\le\sum_{j \le k} \beta_j + \sum_{\ell> k} c_\ell= U_1$.

• $U_2$. By (Prop3) and (Prop2), $\theta\le\theta_j + d_j \le\beta_j + d_j = \alpha_j$ for every $j \le k$. Hence $\theta\le\min_{j \le k} \alpha_j = U_2$.

• $U_3$. Let $I \subseteq[k]$ with $|I| \ge2$. Summing (Prop3) over $j \in I$ gives $|I|\theta- \sum_{j \in I}\theta_j \le\sum_{j \in I}d_j$. By (Prop1) and $\theta_\ell\ge0$ (Prop2), $\sum_{j \in I}\theta_j \le\theta$. Hence $(|I|-1)\theta\le\sum_{j \in I}d_j$, i.e. $\theta\le\frac{1}{|I|-1}\sum_{j \in I}d_j$. Minimising over $I$ gives $\theta\le U_3$.

Therefore $\theta\le\min\{U_1,U_2,U_3\} = U$.

Proof. The interval $[\underline{\theta_j},\overline{\theta_j}]$ is exactly the range allowed for $\theta_j$ by Proposition 8: the upper end comes from (Prop2), and for $j \le k$ the lower end comes from (Prop3), $\theta_j \ge\theta-d_j$, together with $\theta_j \ge0$.

If every interval is non-empty, the sum $\sum_j \theta_j$ with $\theta_j \in[\underline{\theta_j},\overline{\theta_j}]$ takes exactly the values in $[\sum_j\underline{\theta_j},\sum_j\overline{\theta_j}]$. Hence a solution exists if and only if the following three conditions hold.

• Every interval is non-empty. For $j > k$ this is automatic. For $j \le k$, $(\theta-d_j)^+ \le\beta_j \Longleftrightarrow\theta\le\beta_j+d_j=\alpha_j$. So this condition is $\theta\le U_2$.

• The upper ends are large enough: $\theta\le\sum_j\overline{\theta_j}=\sum_{j \le k}\beta_j+\sum_{j > k}c_j=U_1$.

• The lower ends are small enough: $\sum_j\underline{\theta_j}=\sum_{j \le k}(\theta-d_j)^+ \le\theta$. Since $\sum_{j \le k}(x_j)^+=\max_{I\subseteq[k]}\sum_{j\in I}x_j$, this says $|I|\theta-\sum_{j\in I}d_j\le\theta$, i.e. $(|I|-1)\theta\le\sum_{j\in I}d_j$, for every $I\subseteq[k]$. This is automatic for $|I|\le1$, and for $|I|\ge2$ it is $\theta\le U_3$.

The three conditions together are $\theta\le\min\{U_1,U_2,U_3\}=U$.

Proof. Set $\theta:= U$ (a target the construction must hit, not an assumption).

Step 1 (how much of $S$ lies in each column). By Lemma 10, choose $\theta_1,\ldots,\theta_n$ with $\theta_\ell\in[\underline{\theta_\ell},\overline{\theta_\ell}]$ and $\sum_\ell\theta_\ell=U$.

Step 2 (how much of each $A_j$ lies in each column). For $j\le k$ let $m_{jj}:=\beta_j$ and choose $m_{j\ell}\in[\theta_\ell,c_\ell]$ for $\ell\ne j$, summing to $d_j$. This is possible because each interval is non-empty ($\theta_\ell\le\overline{\theta_\ell}\le c_\ell$), the lower ends are small enough ($\sum_{\ell\ne j}\theta_\ell=U-\theta_j\le d_j$, since $\theta_j\ge\underline{\theta_j}=(U-d_j)^+$), and the upper ends are large enough ($\sum_{\ell\ne j}c_\ell=1-c_j\ge d_j$ by $(\star)$). Moreover $m_{jj}=\beta_j=\overline{\theta_j}\ge\theta_j$. Hence $\theta_\ell\le m_{j\ell}\le c_\ell$ for all $j,\ell$, and $\sum_\ell m_{j\ell}=\beta_j+d_j=\alpha_j$.

Step 3 (arrangement inside each column). In column $\ell$ place a block $K_\ell$ of mass $\theta_\ell$. For $\ell\le k$ put $K_\ell$ inside $Q_{\ell\ell}$ (possible since $\theta_\ell\le\beta_\ell$) and set $A_\ell\cap x_\ell:=Q_{\ell\ell}$. For every $j\ne\ell$, let $A_j$ contain $K_\ell$, and on $x_\ell\setminus K_\ell$ let $A_j$ occur independently with probability $(m_{j\ell}-\theta_\ell)/(c_\ell-\theta_\ell)\in[0,1]$. Then $\mathbb{P}(A_j\cap x_\ell)=m_{j\ell}$ for all $j,\ell$, so $\mathbb{P}(A_j)=\alpha_j$ and $A_j\cap x_j=Q_{jj}$: the system is admissible. Every $A_j$ contains every block, so $\theta\ge\sum_\ell\theta_\ell=U$. By Corollary 9, $\theta\le U$. Hence $\theta=U$.

By Lemma 6, $\max\Theta=U$, so the upper bound of PNS($k$) is sharp.

The lower bound proof

For the upper bound we could build a maximiser directly, by putting as much mass as possible into the intersection. The lower bound is harder. If we push $A_1,\ldots,A_k$ apart in one column, their mass has to go to other columns, where it may overlap with another event, so we cannot treat the columns one at a time. We therefore take a dual approach. In Section 4.3.1, Fréchet bounds in each column turn the problem into a flow problem. Section 4.3.2 then uses max-flow/min-cut to write the minimum as a maximum over cuts, and Section 4.3.3 shows that only $k+2$ of these cuts can be positive.

For $k=1$, $\theta=\alpha_1$ is identified and $L=U=\alpha_1$. So we will only consider cases when $k\ge2$ below.

Column-wise Fréchet

Recall that the column $x_\ell$ has mass $c_\ell=\mathbb{P}(x_\ell)=\sum_i b_{i\ell}$, the total mass of its cells $Q_{i\ell}=(x_\ell,y_i)$, $i\in[n]$.

Proof. Let $N_i:=x_\ell\setminus G_i$ be the complement of $G_i$ inside the column. By De Morgan and the union bound, $\mathbb{P}\left(\bigcap_i G_i\right)=c_\ell-\mathbb{P}\left(\bigcup_i N_i\right)\ge c_\ell-\sum_i(c_\ell-g_i)$. For the converse, view the column as a circle of circumference $c_\ell$ and lay $N_1,\ldots,N_r$ end to end as arcs of lengths $c_\ell-g_i$ (Figure 1). If they fit, they are disjoint and the bound is an equality. Otherwise they wrap around and together cover the whole circle, so every point lies in some $N_i$ and $\bigcap_iG_i=\varnothing$. If some $G_i$ must equal a union of cells (for instance $A_j\cap x_j=(x_j,y_j)$ when $j\le k$), its complement $N_i$ is the union of the remaining cells of the column; since only the masses of the cells are prescribed, we place these cells side by side on the arc assigned to $N_i$, whose length equals their total mass. Finally, distinct columns are disjoint, so the arrangements in different columns do not interact and can be chosen simultaneously.

By pigeonhole the complements fit disjointly iff the bracket is non-negative, so $(\cdot)^+$ is not an artificial truncation. As in § 4.2, the inequality holds for every arrangement and gives the bound, and a suitable arrangement attains it.

Flow and cuts

For the lower bounds with $k\ge2$ we use the transportation set $\mathcal{T}:=\{m\in\mathbb{R}^{k\times n}:m_{jj}=\beta_j,\sum_{\ell\ne j}m_{j\ell}=d_j,\ 0\le m_{j\ell}\le c_\ell\}$. Recall that $d_j=\alpha_j-\beta_j=\mathbb{P}(A_j\setminus x_j)=\mathbb{P}(A_j)-\mathbb{P}(A_j\cap x_j)$ is the mass of $A_j$ outside its own column $x_j$. In the table $m$, row $j$ describes how $A_j$ is spread over the columns: its diagonal entry is $m_{jj}=\beta_j$, and its off-diagonal entries $m_{j\ell}$, $\ell\ne j$, must add up to exactly $d_j$. We also use the column inflow $e_\ell:=\sum_{j\le k,\ j\ne\ell}m_{j\ell}$, the mass that the other rows place in column $\ell$; summing over all off-diagonal cells by rows or by columns gives $D:=\sum_\ell e_\ell=\sum_jd_j$.

In the proof of the lower bound, Lemma 12 will give, for each column $\ell$, a lower bound of the form $(e_\ell-f_\ell)^+$, where $f_\ell\ge0$ depends only on the data; for PNS$(k)$ it is $f_\ell=(k-1)c_\ell-\beta_\ell\mathbf{1}\{\ell\le k\}$. We call $f_\ell$ the free capacity of column $\ell:$ inflow up to $f_\ell$ costs nothing, and each unit beyond it adds one to $\theta$. The lower bound is therefore a minimisation of $\sum_\ell(e_\ell-f_\ell)^+$ over the transportation set. The next lemma, stated for arbitrary $f_1,\ldots,f_n\ge0$, rewrites this minimisation as a maximisation over the $2^k$ subsets $J\subseteq[k]$.

$j \in J$ with $j \ne\ell$, and at most $f_\ell$ altogether. So $\Delta(J)$ is the part of the rows in $J$ that cannot be absorbed for free, and each $\Delta(J)$ is a lower bound on the cost. In the proof, $J$ appears as the set of rows on the source side of a cut.

Proof. Consider the network of Figure 2, in which the source feeds row $j$ with capacity $d_j$, row $j$ feeds column $\ell\ne j$ with capacity $c_\ell= \mathbb{P}(x_\ell)$ (since $m_{j\ell} = \mathbb{P}(A_j \cap x_\ell) \le c_\ell$), and column $\ell$ feeds the sink with capacity $f_\ell$. Let $\varphi$ be the value of a maximum flow. Since $(e-f)^+ = e-\min(e,f)$ and $\sum_\ell e_\ell= D$, every $m \in\mathcal{T}$ satisfies $\sum_\ell(e_\ell-f_\ell)^+ = D-\sum_\ell\min(e_\ell,f_\ell)$.

every $m \in\mathcal{T}$ has cost at least $D-\varphi$. Fix $m \in\mathcal{T}$. We turn it into a flow by letting row $j$ send to column $\ell\ne j$ the amount

that is, the inflows of column $\ell$ are scaled down by the common factor $\lambda_\ell\in[0,1]$. This flow respects every capacity: row $j$ ships $\sum_{\ell\ne j}\eta_{j\ell}\le\sum_{\ell\ne j}m_{j\ell}=d_j$; on each arc $\eta_{j\ell}\le m_{j\ell}\le c_\ell$; and column $\ell$ receives $\sum_{j\ne\ell}\eta_{j\ell}=\lambda_\ell e_\ell=\min(e_\ell,f_\ell)\le f_\ell$. Its value is $\sum_\ell\min(e_\ell,f_\ell)$, and $\varphi$ is the largest value of any flow, so

some $m \in\mathcal{T}$ has cost at most $D-\varphi$. Take a maximum flow, and let $\eta_{j\ell}\ge0$ be the amount it sends from row $j$ to column $\ell\ne j$. Write

for the total amount row $j$ ships and the total amount column $\ell$ receives, respectively. So that $\sum_\ell\varphi_\ell=\varphi$, and the capacities give $\eta_j\le d_j$, $\eta_{j\ell}\le c_\ell$ and $\varphi_\ell\le f_\ell$.

Completing the flow to a table $m \in\mathcal{T}$. Row $j$ must place $d_j$ in the columns $\ell\ne j$, and the flow already places $\eta_j$ there. The room left in its cells is

by $(\star)$. So we can choose $m_{j\ell}\in[\eta_{j\ell},c_\ell]$ for $\ell\ne j$ with $\sum_{\ell\ne j}m_{j\ell}=d_j$; together with $m_{jj}:=\beta_j$ this gives $m\in\mathcal{T}$.

Bounding its cost. Since $m_{j\ell}\ge\eta_{j\ell}$, the inflow of column $\ell$ satisfies $e_\ell\ge\varphi_\ell$, and $\varphi_\ell\le f_\ell$. Hence $(e_\ell-f_\ell)^+\le e_\ell-\varphi_\ell$: if $e_\ell\ge f_\ell$, then $e_\ell-f_\ell\le e_\ell-\varphi_\ell$; if $e_\ell<f_\ell$, then $0\le e_\ell-\varphi_\ell$. Summing over $\ell$,

Computing $\varphi$ by a minimum cut. A cut splits the nodes into a source side and a sink side, and its capacity is the total capacity of the arcs that go from the source side to the sink side. Let $J\subseteq[k]$ be the set of rows on the source side.

• Each row $j\notin J$ is on the sink side, so the arc from the source to row $j$ is cut, at cost $d_j$.

• Each column $\ell$ is placed on the cheaper side. On the source side, its arc to the sink is cut, at cost $f_\ell$. On the sink side, the arcs into it from the rows of $J$ are cut; there are $|J\setminus\{\ell\}|$ of them (the number of elements of $J\setminus\{\ell\}$), each of capacity $c_\ell$, at total cost $|J\setminus\{\ell\}|\times c_\ell$.

The cheapest cut with row set $J$ therefore has capacity $\sum_{j\notin J}d_j+\sum_\ell\min(|J\setminus\{\ell\}|\times c_\ell,f_\ell)$. By the max-flow/min-cut theorem [3], $\varphi$ equals the minimum of this over $J$. Since $D-\sum_{j\ne\ell}d_j=\sum_{j\in J}d_j$,

Lemma 13 expresses the lower bound as a maximum over all $2^k$ sets $J \subseteq[k]$, whereas the published bounds list three expressions; the gap is closed by $(\star)$ alone. We now show that, when $f_\ell\ge(k-2)c_\ell$ for every $\ell$, every set $J$ with $|J| \le k-2$ gives $\Delta(J) \le0$. Since $\Delta(\varnothing)=0$, such sets never attain the maximum, and it suffices to consider the $k+2$ sets $J=\varnothing$, $J=[k]\setminus\{i\}$ ($i\le k$) and $J=[k]$.

Proof. Let $|J|\le k-2$. For every column $\ell$ we have $|J\setminus\{\ell\}|\le|J|\le k-2$, so $|J\setminus\{\ell\}|\times c_\ell\le(k-2)c_\ell\le f_\ell$, and each minimum in $\Delta(J)$ equals $|J\setminus\{\ell\}|\times c_\ell$. Since $|J\setminus\{\ell\}|=|J|-1$ for $\ell\in J$ and $|J\setminus\{\ell\}|=|J|$ for $\ell\notin J$, and $\sum_\ell c_\ell=1$,

Hence

where the last inequality is by applying $(\star)$.

Proof of the lower bound

Now, let’s finish the proof of the sharpness of lower bound.

Reduction to a flow. By Lemma 12 in column $\ell$, applied to the events $A_j\cap x_\ell$ ($j\le k$),

Equality holds for a suitable arrangement, simultaneously in all columns. Hence $\min\Theta=\min_{m\in\mathcal{T}}\sum_\ell(e_\ell-f_\ell)^+$, where every $m\in\mathcal{T}$ is realised by some admissible system. We have $f_\ell\ge(k-2)c_\ell\ge0$ because $\beta_\ell\le c_\ell$. By Lemmas 13 and 14, $\min\Theta=\max\{0,\Delta([k]\setminus\{i\})_{i\le k},\Delta([k])\}$.

Evaluating the two cut families. By Lemma 14, every $J$ with $|J|\le k-2$ has $\Delta(J)\le0$, so apart from $\Delta(\varnothing)=0$, only sets with at least $k-1$ elements can give a positive value. These are $J=[k]\setminus\{i\}$ for $i\le k$, and $J=[k]$. Recall that $\Delta(J)=\sum_{j\in J}d_j-\sum_\ell\min\left(|J\setminus\{\ell\}|\times c_\ell,f_\ell\right)$ with $f_\ell=(k-1)c_\ell-\beta_\ell\mathbf{1}_{\{\ell\le k\}}$, and that $\sum_\ell c_\ell=1$.

• $J=[k]\setminus\{i\}$ for some $i\le k$. We compute the minimum column by column:

  • for $\ell=i$, $|J\setminus\{\ell\}|=k-1$ and the minimum is $(k-1)c_i-\beta_i=f_i$;

  • for $\ell\le k$, $\ell\ne i$, $|J\setminus\{\ell\}|=k-2$ and $f_\ell\ge(k-2)c_\ell$, so the minimum is $(k-2)c_\ell$;

  • for $\ell>k$, $|J\setminus\{\ell\}|=k-1$ and $f_\ell=(k-1)c_\ell$, so the minimum is $(k-1)c_\ell$.

Adding these up gives $(k-1)\sum_\ell c_\ell-\sum_{j\le k,\ j\ne i}c_j-\beta_i=(k-1)-\sum_{j\le k,\ j\ne i}c_j-\beta_i$.

Hence, using $d_j=\alpha_j-\beta_j$,

• $J=[k]$. We also compute column by column:

  • for $\ell\le k$, $|J\setminus\{\ell\}|=k-1$ and the minimum is $(k-1)c_\ell-\beta_\ell=f_\ell$;

  • for $\ell>k$, $|J\setminus\{\ell\}|=k$ and the minimum is $\min(kc_\ell,(k-1)c_\ell)=(k-1)c_\ell$.

Adding these up gives $(k-1)-\sum_{j\le k}\beta_j$, hence

Together with $\Delta(\varnothing)=0$, these are exactly the three terms of $L$: $\Delta(\varnothing)=0=L_1$, $\Delta([k])=L_2$, and $\max_{i\le k}\Delta([k]\setminus\{i\})=L_3$. Thus $\min\Theta=L$, and with § 4.2, Theorem 7 is proved.

The other three families

The same argument works for targets of the form $\mathbb{P}(S,G)$ when $G \ne\Omega$. By Lemma 4, we apply admissible systems again. We restate the bounds of Shu et al. [ [13] in our notation, and give the full proofs in Appendix. Throughout, we use the canonical form, in which $p > k$.

PSub$(k,p)$ and PN$(k,p,q)$. $G=x_p$ for PSub, and $G=(x_p,y_q)=Q_{qp}\subseteq x_p$ for PN. We write $\gamma:=\mathbb{P}(G)$, so $\gamma=c_p$ for PSub and $\gamma=b_{qp}$ for PN by consistency. The target is $\theta=\mathbb{P}(S,G)$, and the bounds are

PRep$(k,q)$. The target is $\theta=\mathbb{P}(S,y_q)$. By consistency, only the cells of row $q$ in column $q$ (if $q\leq k$) and in the columns $\ell>k$ can meet $S$; their total mass is

and the bounds are

For PRep$(k,q)$ with $k=1$, the max-flow argument of § 4.3 does not apply, since the free capacity $f_q=-\beta_q$ is negative, but sharpness still holds and follows from Theorem 17. The full proofs of sharpness for these three families are given in the appendix.

So far each target form pairs $x_j$ with $y_j$. A general query may pair $x_j$ with any outcome, for example $\mathbb{P}(y_{3}x_{1},y_{1}x_{2})$. Shu et al. [ [13] obtain its bounds from the canonical ones by substitution: for a target $y_i x_j$, they use $\mathbb{P}(y_i x_j)$ in place of $\mathbb{P}(y_jx_j)$ and $\mathbb{P}(x_j,y_i)$ in place of $\mathbb{P}(x_j,y_j)$.

A complete proof follows from Theorem 17; see Appendix.

Unified results

In this section, we extend our main result and summarize the four families into one theorem.

The sharp bounds of the four families (Theorem 7 for PNS$(k)$ and (9)--(11) for the other three), are four instances of a single statement. The four families differ only in the factual event $G$, and the proofs above use $G$ in one place: through the part of $G$ in each column that can still meet $S$ once consistency is taken into account. The statement below also allows arbitrary target outcomes, so it covers relabelled queries as well.

The general notation. Here, we keep $G$ to be a factual event, and change the target outcome to $i_1,\ldots,i_k\in[n]$, we allow $i_u=i_v$ for $u,v\in[k]$ and $u\ne v$. We also change the notation of $A_j$ we defined in § 3 as

According to this new $A_j$, we have

and keep $d_j=\alpha_j-\beta_j$, $c_j=\mathbb{P}(x_j)$ and $s_j=1-c_j-d_j$.

With the new $\alpha_j$ and $\beta_j$, we have $s_j=(1-a_{i_jj})-(c_j-b_{i_jj})$, which involves the other rows $i\ne i_j$ of column $j$. By consistency, $b_{ij}\le a_{ij}$ for every $i$ and $j$, summing over these rows gives $s_j=\sum_{i\ne i_j}(a_{ij}-b_{ij})\ge0$, so $(\star)$ still holds. The proof of Lemma 4 also remains valid with the target outcome $j$ replaced by $i_j$ throughout, so $\Theta$ is still the set of values of admissible systems with the change of notation $A_j\cap x_j=Q_{i_jj}$.

For a target column $x_j$ with $j\le k$. Every unit in this column received $x_j$, so by consistency its outcome under $x_j$ is simply its observed outcome. We let $E_j$ denote when $A_j$ holds, and let $F_j$ denote when $A_j$ fails on the rest of the column,

Let

Then $\theta$ can be rewritten as $\theta=\mathbb{P}(S,C)$, since no unit in $F_j$ can be in $S$, so we can drop $F_j$ from $G$ and the value of $\theta$ stays the same. Write

for the mass of $C$ in column $\ell$, and $\gamma:=\mathbb{P}(C)=\sum_\ell\gamma_\ell$. In a target column only $E_j$ can remain, so $\gamma_j=\beta_j$ if $E_j\subseteq G$ and $\gamma_j=0$ otherwise. In a column $\ell>k$ nothing is dropped, $C=G$, so $\gamma_\ell$ is just the mass of $G$ in that column.

When $k=1$, the term $U_3$ is absent and $L_3=\gamma_1$.

The theorem depends on $G$ only through the vector $(\gamma_1,\ldots,\gamma_n)$, which records where $G$ survives consistency. For the canonical families $(i_j=j,p>k)$:

family	$G$	$\gamma_j$ ($j\le k$)	$\gamma_\ell$ ($\ell>k$)	$\gamma=\mathbb{P}(C)$
PNS($k$)	$\Omega$	$\beta_j$	$c_\ell$	$\sum_{j\le k}\beta_j+\sum_{\ell>k}c_\ell$
PSub($k,p$)	$x_p$	$0$	$c_p\mathbf{1}\{\ell=p\}$	$c_p$
PN($k,p,q$)	$(x_p,y_q)$	$0$	$b_{qp}\mathbf{1}\{\ell=p\}$	$b_{qp}$
PRep($k,q$)	$y_q$	$\beta_q\mathbf{1}\{j=q\}$	$b_{q\ell}$	$T=\beta_q\mathbf{1}\{q\le k\}+\sum_{\ell>k}b_{q\ell}$

For PSub and PN, $\gamma$ is the $\gamma=\mathbb{P}(G)$ of (9), and for PRep it is $T$.

Substituting these values into Theorem 17 and using $\sum_\ell c_\ell=1$ recovers four families. For PSub, PN and PRep the term $U_3$ is redundant, since an average of the $d_j$ over $I$ is never smaller than $\min_j d_j$, and every $L_3$ term with $\gamma_i=0$ is non-positive.

The proof of Theorem 17 is given in Appendix.

Conclusion

We have proved the conjecture of Shu et al. [ [13]: their closed-form bounds are sharp in all dimensions. The proof also explains why the bounds take the form they do. The upper bounds are exactly the conditions under which the mass of $S$ can be spread over the columns, and the lower bounds come from the only cuts that can bind. We further derived single formula that contains all four families as special cases. Together with the equivalence classes of Shu et al. [ [13], it gives sharp bounds for any discrete PoC in every dimension. Our results use only experimental and observational data, with no further assumptions. Additional assumptions such as monotonicity, or extra information such as covariates could tighten the bounds and can be a future research direction.