因果概率的一致紧致界

# Unified Sharp Bounds on Probabilities of Causation
Source: [https://arxiv.org/html/2610.27398](https://arxiv.org/html/2610.27398)
Ang LiAffiliation:xs24a@fsu\.edu, angli@cs\.fsu\.edu

###### Abstract

Probabilities of causation \(PoCs\) have developed steadily, from the binary measures first introduced by Pearl to the non\-binary setting recently studied by Shu et al\. As the theory has matured, PoCs have found applications in a growing range of areas, including personalized medicine, marketing and legal attribution\. Shu et al\. proposed closed\-form bounds for multi\-valued treatments and outcomes and proved them valid, but left their sharpness in high dimensions open\. We close this gap with a mathematical proof\. We further show thatPNS\\mathrm\{PNS\},PSub\\mathrm\{PSub\},PRep\\mathrm\{PRep\}andPN\\mathrm\{PN\}are all special cases of a single, more general formula\. Combined with their equivalence classes, this settles the question of sharp bounds for discrete PoCs from experimental and observational data: in every dimension, they are given in closed form by a single theorem\.

## 1Introduction

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\)\([Pearl, 1999](https://arxiv.org/html/2610.27398#bib.bib4)\)\. 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ℙ⁡\(yixj\)\\mathbb\{P\}\(y\_\{\{i\}\_\{x\_\{j\}\}\}\)and observational dataℙ⁡\(xj,yi\)\\mathbb\{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\([Tian and Pearl, 2000](https://arxiv.org/html/2610.27398#bib.bib5)\)\. They were derived with Balke’s linear\-programming method\([Balke, 1995](https://arxiv.org/html/2610.27398#bib.bib2);[Balke and Pearl, 1997](https://arxiv.org/html/2610.27398#bib.bib3)\)and later proved analytically\([Li and Pearl, 2019](https://arxiv.org/html/2610.27398#bib.bib8);[Li and Pearl, 2022](https://arxiv.org/html/2610.27398#bib.bib9)\)\. 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 fornn\-valued variables meansnn⋅nn^\{n\}\\cdot nvariables\. It can therefore only be solved for smallnn, and it gives no closed form\.[Zhang et al\. \(2022\)](https://arxiv.org/html/2610.27398#bib.bib11)solve an optimisation problem for each instance, and[Li and Pearl \(2024\)](https://arxiv.org/html/2610.27398#bib.bib10)give recursive bounds that are valid but not sharp\.[Shu et al\. \(2026\)](https://arxiv.org/html/2610.27398#bib.bib1)derived closed\-form bounds for four families of PoCs,PNS⁡\(k\)\\mathrm\{PNS\}\(k\),PSub⁡\(k,p\)\\mathrm\{PSub\}\(k,p\),PRep⁡\(k,q\)\\mathrm\{PRep\}\(k,q\)andPN⁡\(k,p,q\)\\mathrm\{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 innn\.

##### Contributions\.

- •We prove that the closed\-form bounds of[Shu et al\. \(2026\)](https://arxiv.org/html/2610.27398#bib.bib1)forPNS⁡\(k\)\\mathrm\{PNS\}\(k\),PSub⁡\(k,p\)\\mathrm\{PSub\}\(k,p\),PRep⁡\(k,q\)\\mathrm\{PRep\}\(k,q\)andPN⁡\(k,p,q\)\\mathrm\{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 fromnn⋅nn^\{n\}\\cdot nvariables to2k⋅n2^\{k\}\\cdot n, and the second reduces the2k2^\{k\}candidate cuts for the lower bound to justk\+2k\+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](https://arxiv.org/html/2610.27398#S4)gives the full proof forPNS⁡\(k\)\\mathrm\{PNS\}\(k\), and extends it to the other three families\. Section[5](https://arxiv.org/html/2610.27398#S5)combines all four into a single theorem\.

## 2Preliminaries

This section recalls the definitions of probabilities of causation and the notation of structural causal models \(SCMs\)\([Galles and Pearl, 1998](https://arxiv.org/html/2610.27398#bib.bib6);[Halpern, 2000](https://arxiv.org/html/2610.27398#bib.bib7)\)\. Readers who know SCMs can skip it\.

In an SCM, counterfactuals have a precise meaning\. The statement “YYwould have beenyyhadXXbeenxx” is writtenYx=yY\_\{x\}=y, where the subscriptxxrefers to a hypothetical intervention\. To keep the notation short, we writeyxy\_\{x\},yx′y\_\{x^\{\\prime\}\},yx′y^\{\\prime\}\_\{x\}andyx′′y^\{\\prime\}\_\{x^\{\\prime\}\}for the eventsYx=yY\_\{x\}=y,Yx′=yY\_\{x^\{\\prime\}\}=y,Yx=y′Y\_\{x\}=y^\{\\prime\}andYx′=y′Y\_\{x^\{\\prime\}\}=y^\{\\prime\}\. Throughout,XXis the treatment andYYthe outcome\. Unless stated otherwise, experimental data are causal effects such asP⁡\(yx\)P\(y\_\{x\}\), and observational data are joint probabilities such asP⁡\(x,y\)P\(x,y\)\.

WhenXXandYYare binary, we writexxandx′x^\{\\prime\}forX=trueX=\\text\{true\}andX=falseX=\\text\{false\}, andyyandy′y^\{\\prime\}forY=trueY=\\text\{true\}andY=falseY=\\text\{false\}\.[Pearl \(1999\)](https://arxiv.org/html/2610.27398#bib.bib4)defined three basic probabilities of causation\.

###### Definition 1\(Probabilities of causation\([Pearl, 1999](https://arxiv.org/html/2610.27398#bib.bib4)\)\)\.

PN=ΔP⁡\(yx′′∣x,y\),PS=ΔP⁡\(yx∣y′,x′\),PNS=ΔP⁡\(yx,yx′′\)\.\\text\{PN\}\\mathrel\{\\stackrel\{\{\\scriptstyle\\scriptscriptstyle\\Delta\}\}\{\{=\}\}\}P\(y^\{\\prime\}\_\{x^\{\\prime\}\}\\mid x,y\),\\qquad\\text\{PS\}\\mathrel\{\\stackrel\{\{\\scriptstyle\\scriptscriptstyle\\Delta\}\}\{\{=\}\}\}P\(y\_\{x\}\\mid y^\{\\prime\},x^\{\\prime\}\),\\qquad\\text\{PNS\}\\mathrel\{\\stackrel\{\{\\scriptstyle\\scriptscriptstyle\\Delta\}\}\{\{=\}\}\}P\(y\_\{x\},y^\{\\prime\}\_\{x^\{\\prime\}\}\)\.

PNS is the probability thatyyresponds toxxin both directions:yyoccurs withxxand fails to occur without it\. It therefore captures both the sufficiency and the necessity ofxxforyy\.[Tian and Pearl \(2000\)](https://arxiv.org/html/2610.27398#bib.bib5)obtained tight bounds on PN, PS and PNS with Balke’s linear\-programming method\([Balke, 1995](https://arxiv.org/html/2610.27398#bib.bib2)\), and[Li and Pearl \(2019\)](https://arxiv.org/html/2610.27398#bib.bib8);[Li and Pearl \(2022\)](https://arxiv.org/html/2610.27398#bib.bib9)later proved these bounds analytically\.

Now letXXandYYeach takennvalues\.[Li and Pearl \(2024\)](https://arxiv.org/html/2610.27398#bib.bib10)named four multi\-valued probabilities of causation, PNS, PSub, PRep and PN, and gave recursive bounds for them\.[Shu et al\. \(2026\)](https://arxiv.org/html/2610.27398#bib.bib1)kept the names but rewrote each quantity so that thejj\-th counterfactual always pairsyjy\_\{j\}withxjx\_\{j\}:

PNS⁡\(k\)\\displaystyle\\mathrm\{PNS\}\(k\)=P⁡\(y1x1,…,ykxk\)\\displaystyle=P\(\{y\_\{1\}\}\_\{x\_\{1\}\},\\ldots,\{y\_\{k\}\}\_\{x\_\{k\}\}\)\(probability of necessity and sufficiency\),\\displaystyle\\text\{\(probability of necessity and sufficiency\)\},PSub⁡\(k,p\)\\displaystyle\\mathrm\{PSub\}\(k,p\)=P⁡\(y1x1,…,ykxk,xp\)\\displaystyle=P\(\{y\_\{1\}\}\_\{x\_\{1\}\},\\ldots,\{y\_\{k\}\}\_\{x\_\{k\}\},x\_\{p\}\)\(probability of substitute\),\\displaystyle\\text\{\(probability of substitute\)\},PRep⁡\(k,q\)\\displaystyle\\mathrm\{PRep\}\(k,q\)=P⁡\(y1x1,…,ykxk,yq\)\\displaystyle=P\(\{y\_\{1\}\}\_\{x\_\{1\}\},\\ldots,\{y\_\{k\}\}\_\{x\_\{k\}\},y\_\{q\}\)\(probability of replacement\),\\displaystyle\\text\{\(probability of replacement\)\},PN⁡\(k,p,q\)\\displaystyle\\mathrm\{PN\}\(k,p,q\)=P⁡\(y1x1,…,ykxk,xp,yq\)\\displaystyle=P\(\{y\_\{1\}\}\_\{x\_\{1\}\},\\ldots,\{y\_\{k\}\}\_\{x\_\{k\}\},x\_\{p\},y\_\{q\}\)\(probability of necessity\),\\displaystyle\\text\{\(probability of necessity\)\},withk≤nk\\leq nandp≠jp\\neq jfor1≤j≤k1\\leq j\\leq k\. HerePNS⁡\(k\)\\mathrm\{PNS\}\(k\)is the probability that the same individual would have outcomeyjy\_\{j\}underxjx\_\{j\}for everyj=1,…,kj=1,\\dots,k\.[Shu et al\. \(2026\)](https://arxiv.org/html/2610.27398#bib.bib1)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\. \(2026\)](https://arxiv.org/html/2610.27398#bib.bib1)for the bounds and the two theorems, in this paper we prove that the bounds are sharp\.

## 3Notation and Definition

The treatmentXXtakes valuesx1,…,xnx\_\{1\},\\dots,x\_\{n\}and the outcomeYYtakes valuesy1,…,yny\_\{1\},\\dots,y\_\{n\}; as in[Shu et al\. \(2026\)](https://arxiv.org/html/2610.27398#bib.bib1), unequal cardinalities are handled by adding values of probability zero\. We write\[n\]=\{1,…,n\}\[n\]=\\\{1,\\dots,n\\\}\. The indexiiruns over outcomes andj,ℓj,\\ellover treatments;ppdenotes an additional treatment andqqan 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 writexjx\_\{j\}for the event\{X=xj\}\\\{X=x\_\{j\}\\\}, i\.e\. that the unit received treatmentxjx\_\{j\}, andyiy\_\{i\}for the event\{Y=yi\}\\\{Y=y\_\{i\}\\\}, i\.e\. that the observed outcome isyiy\_\{i\}\. The counterfactual eventyixjy\_\{\{i\}\_\{x\_\{j\}\}\}means “underxjx\_\{j\}the outcome would beyiy\_\{i\}”; for fixedjjthese events form a partition\. If we arrange the observational probabilitiesℙ⁡\(xj,yi\)\\mathbb\{P\}\(x\_\{j\},y\_\{i\}\)in a table with one column per treatment and one row per outcome, the eventxjx\_\{j\}is thejj\-th*column*and each entryQi​j:=\(xj,yi\)Q\_\{ij\}:=\(x\_\{j\},y\_\{i\}\)is a*cell*; as forbi​jb\_\{ij\}, the first index ofQQis the row and the second the column\. The columns partition the sample space, soℙ⁡\(E\)=∑jℙ⁡\(E,xj\)\\mathbb\{P\}\(E\)=\\sum\_\{j\}\\mathbb\{P\}\(E,x\_\{j\}\)for every eventEE\.

We now introduce new notations for probabilities:

ai​j=ℙ⁡\(yixj\)\(experimental\),bi​j=ℙ⁡\(xj,yi\)\(observational\),cj=ℙ⁡\(xj\)=∑ibi​j,a\_\{ij\}=\\mathbb\{P\}\(y\_\{\{i\}\_\{x\_\{j\}\}\}\)\\ \\ \\text\{\(experimental\)\},\\quad b\_\{ij\}=\\mathbb\{P\}\(x\_\{j\},y\_\{i\}\)\\ \\ \\text\{\(observational\)\},\\quad c\_\{j\}=\\mathbb\{P\}\(x\_\{j\}\)=\\textstyle\\sum\_\{i\}b\_\{ij\},\(1\)The two kinds of data are linked by*consistency*\([Galles and Pearl, 1998](https://arxiv.org/html/2610.27398#bib.bib6);[Pearl, 2009](https://arxiv.org/html/2610.27398#bib.bib15);[Pearl, 2010](https://arxiv.org/html/2610.27398#bib.bib14)\): a unit that receivedxjx\_\{j\}has outcomeyiy\_\{i\}exactly when its potential outcome underxjx\_\{j\}isyiy\_\{i\}, i\.e\.xj∩yixj=xj∩yix\_\{j\}\\cap y\_\{\{i\}\_\{x\_\{j\}\}\}=x\_\{j\}\\cap y\_\{i\}\. Hence

bi​j=ℙ⁡\(Qi​j\)=ℙ⁡\(xj,yixj\)\.b\_\{ij\}=\\mathbb\{P\}\(Q\_\{ij\}\)=\\mathbb\{P\}\\big\(x\_\{j\},y\_\{\{i\}\_\{x\_\{j\}\}\}\\big\)\.\(2\)
A*compatible model*is a joint law of a response typeR=\(R1,…,Rn\)∈\[n\]nR=\(R\_\{1\},\\dots,R\_\{n\}\)\\in\[n\]^\{n\}, whereRj:=YxjR\_\{j\}:=Y\_\{x\_\{j\}\}, and a received treatmentX∈\[n\]X\\in\[n\], withℙ⁡\(Rj=i\)=ai​j\\mathbb\{P\}\(R\_\{j\}=i\)=a\_\{ij\}andℙ⁡\(Rj=i,X=j\)=bi​j\\mathbb\{P\}\(R\_\{j\}=i,X=j\)=b\_\{ij\}; the observed outcome isRXR\_\{X\}\. Letℳ\\mathcal\{M\}be the set of compatible models, assumed non\-empty\.

A valuer=\(r1,…,rn\)∈\[n\]nr=\(r\_\{1\},\\dots,r\_\{n\}\)\\in\[n\]^\{n\}ofRRis also called a response type; it lists an individual’s outcome under every treatment \(rℓ=ir\_\{\\ell\}=imeansyixℓy\_\{\{i\}\_\{x\_\{\\ell\}\}\}holds\)\. It is a function from treatments to outcomes, so there arennn^\{n\}types\.

Let’s fix1≤k≤n1\\leq k\\leq nand put

Aj:=yjxj,\\displaystyle A\_\{j\}:=y\_\{\{j\}\_\{x\_\{j\}\}\},\\quadS:=⋂j≤kAj,\\displaystyle S:=\\textstyle\\bigcap\_\{j\\leq k\}A\_\{j\},αj:=aj​j,\\displaystyle\\alpha\_\{j\}:=a\_\{jj\},\\quadβj:=bj​j,\\displaystyle\\beta\_\{j\}:=b\_\{jj\},dj:=αj−βj,\\displaystyle d\_\{j\}:=\\alpha\_\{j\}\-\\beta\_\{j\},\\quadsj:=1−cj−dj\.\\displaystyle s\_\{j\}:=1\-c\_\{j\}\-d\_\{j\}\.\(3\)
By \([2](https://arxiv.org/html/2610.27398#S3.E2)\),Aj∩xjA\_\{j\}\\cap x\_\{j\}*is*the observed cellQj​j=\(xj,yj\)Q\_\{jj\}=\(x\_\{j\},y\_\{j\}\), soβj\\beta\_\{j\}is the only observed part ofAjA\_\{j\}\. ButAjA\_\{j\}is defined for every individual, whichever treatment it actually received, so it also has mass outside columnxjx\_\{j\}\. This mass isdj=ℙ⁡\(Aj∖xj\)=ℙ⁡\(Aj\)−ℙ⁡\(Aj,xj\)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 columnsxℓx\_\{\\ell\},ℓ≠j\\ell\\neq j\. We write

mj​ℓ:=ℙ⁡\(Aj,xℓ\)m\_\{j\\ell\}:=\\mathbb\{P\}\(A\_\{j\},x\_\{\\ell\}\)for the mass ofAjA\_\{j\}in columnxℓx\_\{\\ell\}\. Thusmj​j=βjm\_\{jj\}=\\beta\_\{j\},∑ℓ≠jmj​ℓ=dj\\sum\_\{\\ell\\neq j\}m\_\{j\\ell\}=d\_\{j\}and0≤mj​ℓ≤cℓ0\\leq m\_\{j\\ell\}\\leq c\_\{\\ell\}\. Only the diagonal entrymj​jm\_\{jj\}is observed; forℓ≠j\\ell\\neq j,mj​ℓm\_\{j\\ell\}is not determined by the data\.

Each of the four familiesPNS\\mathrm\{PNS\},PSub\\mathrm\{PSub\},PRep\\mathrm\{PRep\}andPN\\mathrm\{PN\}has the formθ=ℙ⁡\(S,G\)\\theta=\\mathbb\{P\}\(S,G\)for some factual eventGG, i\.e\. a union of cells:

PNS⁡\(k\):G=Ω,\\displaystyle\\mathrm\{PNS\}\(k\)\{:\}\\ G=\\Omega,PSub⁡\(k,p\):G=xp,\\displaystyle\\mathrm\{PSub\}\(k,p\)\{:\}\\ G=x\_\{p\},\\PRep⁡\(k,q\):G=yq,\\displaystyle\\mathrm\{PRep\}\(k,q\)\{:\}\\ G=y\_\{q\},PN⁡\(k,p,q\):G=\(xp,yq\),\\displaystyle\\mathrm\{PN\}\(k,p,q\)\{:\}\\ G=\(x\_\{p\},y\_\{q\}\),\(4\)withp\>kp\>k\. HereΩ\\Omegadenotes the whole sample space\. Queries with other target outcomes reduce to these by relabelling\. LetΘ:=\{θ⁡\(M\):M∈ℳ\}\\Theta:=\\\{\\theta\(M\):M\\in\\mathcal\{M\}\\\}\.

Let𝒢:=\{\(i,ℓ\):Qi​ℓ⊆G\}\\mathcal\{G\}:=\\\{\(i,\\ell\):Q\_\{i\\ell\}\\subseteq G\\\}be the set of cells that make up the factual eventGG\(all cells forPNS\\mathrm\{PNS\}, columnppforPSub\\mathrm\{PSub\}, rowqqforPRep\\mathrm\{PRep\}, the single cellQq​pQ\_\{qp\}forPN\\mathrm\{PN\}\); a pair\(i,ℓ\)∈𝒢\(i,\\ell\)\\in\\mathcal\{G\}refers to rowii\(the observed outcome\) and columnℓ\\ell\(the received treatment\)\. For a response typer∈\[n\]nr\\in\[n\]^\{n\}, let

W⁡\(r\):=\{j≤k:rj=j\}⊆\[k\]W\(r\):=\\\{j\\leq k:\\ r\_\{j\}=j\\\}\\subseteq\[k\]record which of the targetsA1,…,AkA\_\{1\},\\dots,A\_\{k\}it satisfies\. Call a triple\(W,i,ℓ\)\(W,i,\\ell\), withW⊆\[k\]W\\subseteq\[k\]andi,ℓ∈\[n\]i,\\ell\\in\[n\],*consistent*if, wheneverℓ≤k\\ell\\leq k,ℓ∈W⇔i=ℓ\\ell\\in W\\iff i=\\ell\. This is consistency: a unit that receivedxℓx\_\{\\ell\}\(ℓ≤k\\ell\\leq k\) satisfiesAℓA\_\{\\ell\}if and only if its observed outcome isyℓy\_\{\\ell\}\.

###### Lemma 2\.

For everyj≤kj\\leq k,

sj=1−cj−dj≥0\.s\_\{j\}=1\-c\_\{j\}\-d\_\{j\}\\ \\geq\\ 0\.\(⋆\\star\)

###### Proof\.

Sincebi​j=ℙ⁡\(xj,yixj\)≤ℙ⁡\(yixj\)=ai​jb\_\{ij\}=\\mathbb\{P\}\(x\_\{j\},y\_\{\{i\}\_\{x\_\{j\}\}\}\)\\leq\\mathbb\{P\}\(y\_\{\{i\}\_\{x\_\{j\}\}\}\)=a\_\{ij\},∑iai​j=1\\sum\_\{i\}a\_\{ij\}=1and∑ibi​j=cj\\sum\_\{i\}b\_\{ij\}=c\_\{j\},

sj=\(1−aj​j\)−\(cj−bj​j\)=∑i≠jai​j−∑i≠jbi​j=∑i≠j\(ai​j−bi​j\)≥0\.∎s\_\{j\}=\(1\-a\_\{jj\}\)\-\(c\_\{j\}\-b\_\{jj\}\)=\\sum\_\{i\\neq j\}a\_\{ij\}\-\\sum\_\{i\\neq j\}b\_\{ij\}=\\sum\_\{i\\neq j\}\(a\_\{ij\}\-b\_\{ij\}\)\\ \\geq\\ 0\.\\qed

This inequality is the key to the lower bound: in Lemma[14](https://arxiv.org/html/2610.27398#Thmtheorem14)it rules out all candidate lower bounds except the three in Theorem[7](https://arxiv.org/html/2610.27398#Thmtheorem7)\.

###### Definition 3\.

An*admissible system*is a probability space with a partition into cellsQi​ℓQ\_\{i\\ell\},i,ℓ∈\[n\]i,\\ell\\in\[n\], whereQi​ℓQ\_\{i\\ell\}plays the role of the observed cell\(xℓ,yi\)\(x\_\{\\ell\},y\_\{i\}\)and hasℙ⁡\(Qi​ℓ\)=bi​ℓ\\mathbb\{P\}\(Q\_\{i\\ell\}\)=b\_\{i\\ell\}; columnsxℓ:=⋃iQi​ℓx\_\{\\ell\}:=\\bigcup\_\{i\}Q\_\{i\\ell\}; and eventsA1,…,AkA\_\{1\},\\dots,A\_\{k\}withℙ⁡\(Aj\)=αj\\mathbb\{P\}\(A\_\{j\}\)=\\alpha\_\{j\}andAj∩xj=Qj​jA\_\{j\}\\cap x\_\{j\}=Q\_\{jj\}, the last condition playing the role of consistency\. The*value*of an admissible system isθ=ℙ⁡\(S,G\)\\theta=\\mathbb\{P\}\(S,G\), computed in that system, withGGread as the corresponding union of cells \(i\.e\.G=xpG=x\_\{p\}inPSub⁡\(k,p\)\\mathrm\{PSub\}\(k,p\)\)\. As before,mj​ℓ=ℙ⁡\(Aj,xℓ\)m\_\{j\\ell\}=\\mathbb\{P\}\(A\_\{j\},x\_\{\\ell\}\)denotes the mass ofAjA\_\{j\}in columnxℓx\_\{\\ell\}\.

##### The two programs\.

Recall that𝒢=\{\(i,ℓ\):Qi​ℓ⊆G\}\\mathcal\{G\}=\\\{\(i,\\ell\):Q\_\{i\\ell\}\\subseteq G\\\}is the set of cells that make up the factual eventGG\(all cells forPNS\\mathrm\{PNS\}, columnppforPSub\\mathrm\{PSub\}, rowqqforPRep\\mathrm\{PRep\}, the single cellQq​pQ\_\{qp\}forPN\\mathrm\{PN\}\)\. A compatible model is determined by the joint probabilitiesℙ⁡\(R=r,X=ℓ\)\\mathbb\{P\}\(R=r,X=\\ell\)\([Balke and Pearl, 1997](https://arxiv.org/html/2610.27398#bib.bib3);[Tian and Pearl, 2000](https://arxiv.org/html/2610.27398#bib.bib5)\)\.

*Balke’s program*treats each of them as a variableh1​\(r,ℓ\)≥0h\_\{1\}\(r,\\ell\)\\geq 0, one for every response typer∈\[n\]nr\\in\[n\]^\{n\}and received treatmentℓ∈\[n\]\\ell\\in\[n\], i\.e\.nn⋅nn^\{n\}\\cdot nvariables:

max/min\\displaystyle\\max/\\minθ\(h1\):=∑r:W⁡\(r\)=\[k\]∑ℓ𝟏\{\(rℓ,ℓ\)∈𝒢\}h1\(r,ℓ\)\\displaystyle\\theta\(h\_\{1\}\):=\\sum\_\{r:\\,W\(r\)=\[k\]\}\\ \\sum\_\{\\ell\}\\mathbf\{1\}\\\{\(r\_\{\\ell\},\\ell\)\\in\\mathcal\{G\}\\\}\\,h\_\{1\}\(r,\\ell\)\(5\)s\.t\.\\displaystyle\\text\{s\.t\.\}∑r:rj=i∑ℓh1\(r,ℓ\)=ai​j,∑r:rj=ih1\(r,j\)=bi​j\(i,j∈\[n\]\)\.\\displaystyle\\sum\_\{r:\\,r\_\{j\}=i\}\\ \\sum\_\{\\ell\}h\_\{1\}\(r,\\ell\)=a\_\{ij\},\\qquad\\sum\_\{r:\\,r\_\{j\}=i\}h\_\{1\}\(r,j\)=b\_\{ij\}\\qquad\(i,j\\in\[n\]\)\.
An experimental constraint sums over all received treatments, so it only involves the response typerr\. An observational constraint looks at a single column, so it also needs the received treatmentℓ\\ell\. We cannot dropℓ\\ellbecause 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, thenbi​j=cj​ai​jb\_\{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 variableh2​\(W,i,ℓ\)≥0h\_\{2\}\(W,i,\\ell\)\\geq 0for every consistent triple, i\.e\. at most2k⋅n22^\{k\}\\cdot n^\{2\}variables:

max/min\\displaystyle\\max/\\minθ⁡\(h2\):=∑\(i,ℓ\)∈𝒢h2​\(\[k\],i,ℓ\)\\displaystyle\\theta\(h\_\{2\}\):=\\sum\_\{\(i,\\ell\)\\in\\mathcal\{G\}\}h\_\{2\}\(\[k\],i,\\ell\)\(6\)s\.t\.\\displaystyle\\text\{s\.t\.\}∑W∋j∑i,ℓh2​\(W,i,ℓ\)=αj\(j≤k\),∑Wh2​\(W,i,ℓ\)=bi​ℓ\(i,ℓ∈\[n\]\)\.\\displaystyle\\sum\_\{W\\ni j\}\\ \\sum\_\{i,\\ell\}h\_\{2\}\(W,i,\\ell\)=\\alpha\_\{j\}\\quad\(j\\leq k\),\\qquad\\sum\_\{W\}h\_\{2\}\(W,i,\\ell\)=b\_\{i\\ell\}\\quad\(i,\\ell\\in\[n\]\)\.
Recall that\[n\]=\{1,…,n\}\[n\]=\\\{1,\\dots,n\\\}\. The reduced program keeps the experimental constraints only foraj​ja\_\{jj\}\(j≤kj\\leq k\), and keeps all observational constraints∑Wh2​\(W,i,ℓ\)=bi​ℓ\\sum\_\{W\}h\_\{2\}\(W,i,\\ell\)=b\_\{i\\ell\}\. It drops everyai​ja\_\{ij\}withi≠ji\\neq j, or whenj\>kj\>k\.

Forj≤kj\\leq k, these constraints and consistency give three more identities\. The columnxjx\_\{j\}has masscjc\_\{j\}, the part of it insideAjA\_\{j\}has massβj\\beta\_\{j\}, and the rest has masscj−βjc\_\{j\}\-\\beta\_\{j\}:

∑W∑ih2​\(W,i,j\)=cj,∑W∋j∑ih2​\(W,i,j\)=bj​j=βj,∑W∌j∑ih2​\(W,i,j\)=cj−βj\.\\sum\_\{W\}\\sum\_\{i\}h\_\{2\}\(W,i,j\)=c\_\{j\},\\ \\sum\_\{W\\ni j\}\\sum\_\{i\}h\_\{2\}\(W,i,j\)=b\_\{jj\}=\\beta\_\{j\},\\ \\sum\_\{W\\not\\ni j\}\\sum\_\{i\}h\_\{2\}\(W,i,j\)=c\_\{j\}\-\\beta\_\{j\}\.\(7\)
The feasible set of \([5](https://arxiv.org/html/2610.27398#S3.E5)\) is a polytope andθ\\thetais linear, soΘ=\[min⁡Θ,max⁡Θ\]\\Theta=\[\\min\\Theta,\\max\\Theta\]and the sharp bounds are the two optima of \([5](https://arxiv.org/html/2610.27398#S3.E5)\)\.[Shu et al\. \(2026\)](https://arxiv.org/html/2610.27398#bib.bib1)used this program to check sharpness numerically forn≤4n\\leq 4\.

###### Lemma 4\(Reduction\)\.

For each of the four families, Balke’s program \([5](https://arxiv.org/html/2610.27398#S3.E5)\) and reduced program \([6](https://arxiv.org/html/2610.27398#S3.E6)\) attain exactly the same set of values ofθ\\theta\. In particular they have the same maximum and the same minimum, so the sharp bounds can be computed from the reduced program\. Equivalently,Θ\\Thetaequals the set of values of admissible systems\.

The last sentence holds because they both describe the same thing\. In an admissible system, the eventsA1,…,AkA\_\{1\},\\dots,A\_\{k\}cut each cellQi​ℓQ\_\{i\\ell\}into pieces\. Each piece is labelled by the setW⊆\[k\]W\\subseteq\[k\]of events that contain it, andh2​\(W,i,ℓ\)h\_\{2\}\(W,i,\\ell\)is its mass\. Conversely, cutting the cells according to a feasibleh2h\_\{2\}gives an admissible system, see Appendix\.

###### Proof idea\.

Both inclusions are constructive \(see Appendix\)\.*Merging*: given a feasibleh1h\_\{1\}, grouping the response types byW⁡\(r\)W\(r\)and by the observed outcome gives a feasibleh2h\_\{2\}with the same value\.*Splitting*: given a feasibleh2h\_\{2\}, we keepWW, the observed outcome and the received treatment of each block fixed, and draw every other coordinaterjr\_\{j\}independently from an explicit distribution built from the data\. The constraints of \([6](https://arxiv.org/html/2610.27398#S3.E6)\) are exactly what makes the result satisfy all constraints of \([5](https://arxiv.org/html/2610.27398#S3.E5)\)\. ∎

###### Corollary 5\.

ForPNS⁡\(k\)\\mathrm\{PNS\}\(k\),𝒢\\mathcal\{G\}contains all cells, so onlyh2​\(W,ℓ\):=∑ih2​\(W,i,ℓ\)h\_\{2\}\(W,\\ell\):=\\sum\_\{i\}h\_\{2\}\(W,i,\\ell\)matters, and the reduced program is equivalent to

max/min\\displaystyle\\max/\\min∑ℓh2​\(\[k\],ℓ\)\\displaystyle\\textstyle\\displaystyle\\sum\_\{\\ell\}h\_\{2\}\(\[k\],\\ell\)\(8\)s\.t\.\\displaystyle\\text\{s\.t\.\}∑W∋j∑ℓh2​\(W,ℓ\)=αj,\\displaystyle\\textstyle\\displaystyle\\sum\_\{W\\ni j\}\\sum\_\{\\ell\}h\_\{2\}\(W,\\ell\)=\\alpha\_\{j\},∑W∋jh2​\(W,j\)=βj\(j≤k\),\\displaystyle\\sum\_\{W\\ni j\}h\_\{2\}\(W,j\)=\\beta\_\{j\}\\quad\(j\\leq k\),\\∑Wh2​\(W,ℓ\)=cℓ\(ℓ∈\[n\]\),\\displaystyle\\textstyle\\displaystyle\\sum\_\{W\}h\_\{2\}\(W,\\ell\)=c\_\{\\ell\}\\quad\(\\ell\\in\[n\]\),with2k⋅n2^\{k\}\\cdot nvariables\. The sharp bounds onPNS⁡\(k\)\\mathrm\{PNS\}\(k\)are therefore functions of\(α1,…,αk𝐶𝐿𝑂𝑆𝐸,\(\\alpha\_\{1\},\\dots,\\alpha\_\{k\},β1,…,\\beta\_\{1\},\\dots,𝑂𝑃𝐸𝑁βk,c1,…,cn\)\\beta\_\{k\},c\_\{1\},\\dots,c\_\{n\}\)alone, data sharing these2​k\+n2k\+nnumbers yield the same program as in \([8](https://arxiv.org/html/2610.27398#S3.E8)\)\.

The proof of Corollary[5](https://arxiv.org/html/2610.27398#Thmtheorem5)is in Appendix\. The corollary also shortens the equivalence\-class arguments of[Shu et al\. \(2026\)](https://arxiv.org/html/2610.27398#bib.bib1): adding outcome or treatment values of probability zero leaves\(α,β,c\)\(\\alpha,\\beta,c\)unchanged up to empty columns\.

##### Sharpness principle\.

Soundness and attainability together give sharpness\.

###### Lemma 6\(Sharpness\)\.

If every admissible system has value≤U\\leq Uand equality holds for at least one admissible system, thenmax⁡Θ=U\\max\\Theta=Uis a sharp upper bound\. The same holds with≥L\\geq L, andmin⁡Θ=L\\min\\Theta=Lis a sharp lower bound\.

###### Proof\.

By Lemma[4](https://arxiv.org/html/2610.27398#Thmtheorem4),UUis a valid upper bound:θ⁡\(M\)≤U\\theta\(M\)\\leq Ufor allM∈ℳM\\in\\mathcal\{M\}\. Suppose someU′U^\{\\prime\}satisfied \(H1\)θ⁡\(M\)≤U′\\theta\(M\)\\leq U^\{\\prime\}for everyM∈ℳM\\in\\mathcal\{M\}and \(H2\)U′<UU^\{\\prime\}<U\. The attaining system gives, via Lemma[4](https://arxiv.org/html/2610.27398#Thmtheorem4), a modelM0∈ℳM\_\{0\}\\in\\mathcal\{M\}withθ⁡\(M0\)=U\\theta\(M\_\{0\}\)=U, and \(H1\) applied toM0M\_\{0\}givesU≤U′<UU\\leq U^\{\\prime\}<U, a contradiction\. The lower bound is symmetric\. ∎

## 4Main results

In this section, we first prove sharpness of the bounds onPNS⁡\(k\)\\mathrm\{PNS\}\(k\)and then extend it to the other three families\.

### 4\.1Problem Statement

Soundness of the bounds for all four families,PNS\\mathrm\{PNS\},PSub\\mathrm\{PSub\},PRep\\mathrm\{PRep\}andPN\\mathrm\{PN\}, was proved by[Shu et al\. \(2026\)](https://arxiv.org/html/2610.27398#bib.bib1)\. We prove completeness, which together with soundness shows that the bounds are sharp\.

We restate thePNS⁡\(k\)\\mathrm\{PNS\}\(k\)theorem in our notation below\.

###### Theorem 7\(PNS⁡\(k\)\\mathrm\{PNS\}\(k\)\)\.

Forθ=ℙ⁡\(y1x1,…,ykxk\)\\theta=\\mathbb\{P\}\(y\_\{\{1\}\_\{x\_\{1\}\}\},\\dots,y\_\{\{k\}\_\{x\_\{k\}\}\}\),Θ=\[L,U\]\\Theta=\[L,U\], where

L\\displaystyle L=max⁡\{0⏟L1,∑j≤kαj−\(k−1\)⏟L2,maxi≤k⁡\[βi\+∑j≤k,j≠i\(αj\+cj−βj\)−\(k−1\)\]⏟L3\},\\displaystyle=\\max\\Big\\\{\\underbrace\{0\}\_\{L\_\{1\}\},\\ \\underbrace\{\\textstyle\\sum\_\{j\\leq k\}\\alpha\_\{j\}\-\(k\-1\)\}\_\{L\_\{2\}\},\\ \\underbrace\{\\max\_\{i\\leq k\}\\big\[\\beta\_\{i\}\+\\textstyle\\sum\_\{j\\leq k,\\,j\\neq i\}\(\\alpha\_\{j\}\+c\_\{j\}\-\\beta\_\{j\}\)\-\(k\-1\)\\big\]\}\_\{L\_\{3\}\}\\Big\\\},U\\displaystyle U=min⁡\{∑j≤kβj\+∑ℓ\>kcℓ⏟U1,minj≤k⁡αj⏟U2,minI⊆\[k\],\|I\|≥2⁡1\|I\|−1​∑j∈Idj⏟U3\}\.\\displaystyle=\\min\\Big\\\{\\underbrace\{\\textstyle\\sum\_\{j\\leq k\}\\beta\_\{j\}\+\\sum\_\{\\ell\>k\}c\_\{\\ell\}\}\_\{U\_\{1\}\},\\ \\underbrace\{\\min\_\{j\\leq k\}\\alpha\_\{j\}\}\_\{U\_\{2\}\},\\ \\underbrace\{\\min\_\{I\\subseteq\[k\],\\,\|I\|\\geq 2\}\\tfrac\{1\}\{\|I\|\-1\}\\textstyle\\sum\_\{j\\in I\}d\_\{j\}\}\_\{U\_\{3\}\}\\Big\\\}\.

We writeU3U\_\{3\}over subsetsIIto make clear that its indices are distinct\. A repeated index would give an invalid bound\.

### 4\.2The upper bound proof

By Lemma[4](https://arxiv.org/html/2610.27398#Thmtheorem4)we can work with admissible systems, and by Lemma[6](https://arxiv.org/html/2610.27398#Thmtheorem6)the proof splits into two parts, soundness \(Corollary[9](https://arxiv.org/html/2610.27398#Thmtheorem9)\) and attainability \(Lemma[11](https://arxiv.org/html/2610.27398#Thmtheorem11)\)\. Soundness was shown by[Shu et al\. \(2026\)](https://arxiv.org/html/2610.27398#bib.bib1); we re\-derive it here because the same three properties drive the construction in Lemma[11](https://arxiv.org/html/2610.27398#Thmtheorem11)\. Throughout, letθℓ:=ℙ⁡\(S,xℓ\)\\theta\_\{\\ell\}:=\\mathbb\{P\}\(S,x\_\{\\ell\}\)denote the part ofθ\\thetathat lies in columnℓ\\ell\.

###### Proposition 8\.

Every admissible system satisfies:

1. \(Prop1\)∑ℓ=1nθℓ=θ\\sum\_\{\\ell=1\}^\{n\}\\theta\_\{\\ell\}=\\theta;
2. \(Prop2\)0≤θj≤βj0\\leq\\theta\_\{j\}\\leq\\beta\_\{j\}forj≤kj\\leq k, and0≤θℓ≤cℓ0\\leq\\theta\_\{\\ell\}\\leq c\_\{\\ell\}forℓ\>k\\ell\>k;
3. \(Prop3\)θ−θj≤dj\\theta\-\\theta\_\{j\}\\leq d\_\{j\}forj≤kj\\leq k\.

###### Proof\.

\(Prop1\) The columnsx1,…,xnx\_\{1\},\\dots,x\_\{n\}partition the space, soSSis the disjoint union of the setsS∩xℓS\\cap x\_\{\\ell\}\. \(Prop2\) Forj≤kj\\leq k,S⊆AjS\\subseteq A\_\{j\}givesS∩xj⊆Aj∩xjS\\cap x\_\{j\}\\subseteq A\_\{j\}\\cap x\_\{j\}, which has massβj\\beta\_\{j\}\. Forℓ\>k\\ell\>k,S∩xℓ⊆xℓS\\cap x\_\{\\ell\}\\subseteq x\_\{\\ell\}, which has masscℓc\_\{\\ell\}\. \(Prop3\) By \(Prop1\),θ−θj=ℙ⁡\(S∖xj\)\\theta\-\\theta\_\{j\}=\\mathbb\{P\}\(S\\setminus x\_\{j\}\)\. SinceS⊆AjS\\subseteq A\_\{j\},S∖xj⊆Aj∖xjS\\setminus x\_\{j\}\\subseteq A\_\{j\}\\setminus x\_\{j\}, which has massαj−βj=dj\\alpha\_\{j\}\-\\beta\_\{j\}=d\_\{j\}\. ∎

###### Corollary 9\(Soundness\)\.

Every admissible system satisfiesθ≤U\\theta\\leq U\.

###### Proof\.

We derive each of the three upper bounds in Theorem[7](https://arxiv.org/html/2610.27398#Thmtheorem7)from Proposition[8](https://arxiv.org/html/2610.27398#Thmtheorem8)\.

- •*U1U\_\{1\}\.*By \(Prop1\) and \(Prop2\),θ=∑j≤kθj\+∑ℓ\>kθℓ≤∑j≤kβj\+∑ℓ\>kcℓ=U1\\theta=\\sum\_\{j\\leq k\}\\theta\_\{j\}\+\\sum\_\{\\ell\>k\}\\theta\_\{\\ell\}\\leq\\sum\_\{j\\leq k\}\\beta\_\{j\}\+\\sum\_\{\\ell\>k\}c\_\{\\ell\}=U\_\{1\}\.
- •*U2U\_\{2\}\.*By \(Prop3\) and \(Prop2\),θ≤θj\+dj≤βj\+dj=αj\\theta\\leq\\theta\_\{j\}\+d\_\{j\}\\leq\\beta\_\{j\}\+d\_\{j\}=\\alpha\_\{j\}for everyj≤kj\\leq k\. Henceθ≤minj≤k⁡αj=U2\\theta\\leq\\min\_\{j\\leq k\}\\alpha\_\{j\}=U\_\{2\}\.
- •*U3U\_\{3\}\.*LetI⊆\[k\]I\\subseteq\[k\]with\|I\|≥2\|I\|\\geq 2\. Summing \(Prop3\) overj∈Ij\\in Igives\|I\|​θ−∑j∈Iθj≤∑j∈Idj\|I\|\\,\\theta\-\\sum\_\{j\\in I\}\\theta\_\{j\}\\leq\\sum\_\{j\\in I\}d\_\{j\}\. By \(Prop1\) andθℓ≥0\\theta\_\{\\ell\}\\geq 0\(Prop2\),∑j∈Iθj≤θ\\sum\_\{j\\in I\}\\theta\_\{j\}\\leq\\theta\. Hence\(\|I\|−1\)​θ≤∑j∈Idj\(\|I\|\-1\)\\,\\theta\\leq\\sum\_\{j\\in I\}d\_\{j\}, i\.e\.θ≤1\|I\|−1​∑j∈Idj\\theta\\leq\\frac\{1\}\{\|I\|\-1\}\\sum\_\{j\\in I\}d\_\{j\}\. Minimising overIIgivesθ≤U3\\theta\\leq U\_\{3\}\.

Thereforeθ≤min⁡\{U1,U2,U3\}=U\\theta\\leq\\min\\\{U\_\{1\},U\_\{2\},U\_\{3\}\\\}=U\. ∎

###### Lemma 10\(Column allocation\)\.

Letθ≥0\\theta\\geq 0, and for every columnj∈\[n\]j\\in\[n\]put

θ¯j:=\{\(θ−dj\)\+,j≤k,0,j\>k,θ¯j:=\{βj,j≤k,cj,j\>k\.\\underline\{\\theta\}\_\{j\}:=\\begin\{cases\}\(\\theta\-d\_\{j\}\)^\{\+\},&j\\leq k,\\\\ 0,&j\>k,\\end\{cases\}\\qquad\\overline\{\\theta\}\_\{j\}:=\\begin\{cases\}\\beta\_\{j\},&j\\leq k,\\\\ c\_\{j\},&j\>k\.\\end\{cases\}There existθ1,…,θn\\theta\_\{1\},\\dots,\\theta\_\{n\}withθj∈\[θ¯j,θ¯j\]\\theta\_\{j\}\\in\[\\underline\{\\theta\}\_\{j\},\\overline\{\\theta\}\_\{j\}\]for everyjjand∑j=1nθj=θ\\sum\_\{j=1\}^\{n\}\\theta\_\{j\}=\\thetaif and only ifθ≤U\\theta\\leq U\.

###### Proof\.

The interval\[θ¯j,θ¯j\]\[\\underline\{\\theta\}\_\{j\},\\overline\{\\theta\}\_\{j\}\]is exactly the range allowed forθj\\theta\_\{j\}by Proposition[8](https://arxiv.org/html/2610.27398#Thmtheorem8): the upper end comes from \(Prop2\), and forj≤kj\\leq kthe lower end comes from \(Prop3\),θj≥θ−dj\\theta\_\{j\}\\geq\\theta\-d\_\{j\}, together withθj≥0\\theta\_\{j\}\\geq 0\.

If every interval is non\-empty, the sum∑jθj\\sum\_\{j\}\\theta\_\{j\}withθj∈\[θ¯j,θ¯j\]\\theta\_\{j\}\\in\[\\underline\{\\theta\}\_\{j\},\\overline\{\\theta\}\_\{j\}\]takes exactly the values in\[∑jθ¯j,∑jθ¯j\]\\big\[\\sum\_\{j\}\\underline\{\\theta\}\_\{j\},\\ \\sum\_\{j\}\\overline\{\\theta\}\_\{j\}\\big\]\. Hence a solution exists if and only if the following three conditions hold\.

- •*Every interval is non\-empty\.*Forj\>kj\>kthis is automatic\. Forj≤kj\\leq k,\(θ−dj\)\+≤βj⇔θ≤βj\+dj=αj\(\\theta\-d\_\{j\}\)^\{\+\}\\leq\\beta\_\{j\}\\iff\\theta\\leq\\beta\_\{j\}\+d\_\{j\}=\\alpha\_\{j\}\. So this condition isθ≤U2\\theta\\leq U\_\{2\}\.
- •*The upper ends are large enough:*θ≤∑jθ¯j=∑j≤kβj\+∑j\>kcj=U1\\theta\\leq\\sum\_\{j\}\\overline\{\\theta\}\_\{j\}=\\sum\_\{j\\leq k\}\\beta\_\{j\}\+\\sum\_\{j\>k\}c\_\{j\}=U\_\{1\}\.
- •*The lower ends are small enough:*∑jθ¯j=∑j≤k\(θ−dj\)\+≤θ\\sum\_\{j\}\\underline\{\\theta\}\_\{j\}=\\sum\_\{j\\leq k\}\(\\theta\-d\_\{j\}\)^\{\+\}\\leq\\theta\. Since∑j≤k\(xj\)\+=max⁡∑j∈II⊆\[k\]⁡xj\\sum\_\{j\\leq k\}\(x\_\{j\}\)^\{\+\}=\\max\_\{I\\subseteq\[k\]\}\\sum\_\{j\\in I\}x\_\{j\}, this says\|I\|​θ−∑j∈Idj≤θ\|I\|\\,\\theta\-\\sum\_\{j\\in I\}d\_\{j\}\\leq\\theta, i\.e\.\(\|I\|−1\)​θ≤∑j∈Idj\(\|I\|\-1\)\\,\\theta\\leq\\sum\_\{j\\in I\}d\_\{j\}, for everyI⊆\[k\]I\\subseteq\[k\]\. This is automatic for\|I\|≤1\|I\|\\leq 1, and for\|I\|≥2\|I\|\\geq 2it isθ≤U3\\theta\\leq U\_\{3\}\.

The three conditions together areθ≤min⁡\{U1,U2,U3\}=U\\theta\\leq\\min\\\{U\_\{1\},U\_\{2\},U\_\{3\}\\\}=U\. ∎

###### Lemma 11\(Attainability\)\.

There exists an admissible system withθ=U\\theta=U\.

###### Proof\.

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

*Step 1 \(how much ofSSlies in each column\)\.*By Lemma[10](https://arxiv.org/html/2610.27398#Thmtheorem10), chooseθ1,…,θn\\theta\_\{1\},\\dots,\\theta\_\{n\}withθℓ∈\[θ¯ℓ,θ¯ℓ\]\\theta\_\{\\ell\}\\in\[\\underline\{\\theta\}\_\{\\ell\},\\overline\{\\theta\}\_\{\\ell\}\]and∑ℓθℓ=U\\sum\_\{\\ell\}\\theta\_\{\\ell\}=U\.

*Step 2 \(how much of eachAjA\_\{j\}lies in each column\)\.*Forj≤kj\\leq kletmj​j:=βjm\_\{jj\}:=\\beta\_\{j\}and choosemj​ℓ∈\[θℓ,cℓ\]m\_\{j\\ell\}\\in\[\\theta\_\{\\ell\},c\_\{\\ell\}\]forℓ≠j\\ell\\neq j, summing todjd\_\{j\}\. This is possible because each interval is non\-empty \(θℓ≤θ¯ℓ≤cℓ\\theta\_\{\\ell\}\\leq\\overline\{\\theta\}\_\{\\ell\}\\leq c\_\{\\ell\}\), the lower ends are small enough \(∑ℓ≠jθℓ=U−θj≤dj\\sum\_\{\\ell\\neq j\}\\theta\_\{\\ell\}=U\-\\theta\_\{j\}\\leq d\_\{j\}, sinceθj≥θ¯j=\(U−dj\)\+\\theta\_\{j\}\\geq\\underline\{\\theta\}\_\{j\}=\(U\-d\_\{j\}\)^\{\+\}\), and the upper ends are large enough \(∑ℓ≠jcℓ=1−cj≥dj\\sum\_\{\\ell\\neq j\}c\_\{\\ell\}=1\-c\_\{j\}\\geq d\_\{j\}by \([⋆‣2](https://arxiv.org/html/2610.27398#S3.Ex11)\)\)\. Moreovermj​j=βj=θ¯j≥θjm\_\{jj\}=\\beta\_\{j\}=\\overline\{\\theta\}\_\{j\}\\geq\\theta\_\{j\}\. Henceθℓ≤mj​ℓ≤cℓ\\theta\_\{\\ell\}\\leq m\_\{j\\ell\}\\leq c\_\{\\ell\}for allj,ℓj,\\ell, and∑ℓmj​ℓ=βj\+dj=αj\\sum\_\{\\ell\}m\_\{j\\ell\}=\\beta\_\{j\}\+d\_\{j\}=\\alpha\_\{j\}\.

*Step 3 \(arrangement inside each column\)\.*In columnℓ\\ellplace a blockKℓK\_\{\\ell\}of massθℓ\\theta\_\{\\ell\}\. Forℓ≤k\\ell\\leq kputKℓK\_\{\\ell\}insideQℓ​ℓQ\_\{\\ell\\ell\}\(possible sinceθℓ≤βℓ\\theta\_\{\\ell\}\\leq\\beta\_\{\\ell\}\) and setAℓ∩xℓ:=Qℓ​ℓA\_\{\\ell\}\\cap x\_\{\\ell\}:=Q\_\{\\ell\\ell\}\. For everyj≠ℓj\\neq\\ell, letAjA\_\{j\}containKℓK\_\{\\ell\}, and onxℓ∖Kℓx\_\{\\ell\}\\setminus K\_\{\\ell\}letAjA\_\{j\}occur independently with probability\(mj​ℓ−θℓ\)/\(cℓ−θℓ\)∈\[0,1\]\(m\_\{j\\ell\}\-\\theta\_\{\\ell\}\)/\(c\_\{\\ell\}\-\\theta\_\{\\ell\}\)\\in\[0,1\]\. Thenℙ⁡\(Aj∩xℓ\)=mj​ℓ\\mathbb\{P\}\(A\_\{j\}\\cap x\_\{\\ell\}\)=m\_\{j\\ell\}for allj,ℓj,\\ell, soℙ⁡\(Aj\)=αj\\mathbb\{P\}\(A\_\{j\}\)=\\alpha\_\{j\}andAj∩xj=Qj​jA\_\{j\}\\cap x\_\{j\}=Q\_\{jj\}: the system is admissible\.

EveryAjA\_\{j\}contains every block, soθ≥∑ℓθℓ=U\\theta\\geq\\sum\_\{\\ell\}\\theta\_\{\\ell\}=U\. By Corollary[9](https://arxiv.org/html/2610.27398#Thmtheorem9),θ≤U\\theta\\leq U\. Henceθ=U\\theta=U\. ∎

By Lemma[6](https://arxiv.org/html/2610.27398#Thmtheorem6),max⁡Θ=U\\max\\Theta=U, so the upper bound ofPNS⁡\(k\)\\mathrm\{PNS\}\(k\)is sharp\.

### 4\.3The 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 pushA1,…,AkA\_\{1\},\\dots,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](https://arxiv.org/html/2610.27398#S4.SS3.SSS1), Fréchet bounds in each column turn the problem into a flow problem\. Section[4\.3\.2](https://arxiv.org/html/2610.27398#S4.SS3.SSS2)then uses max\-flow/min\-cut to write the minimum as a maximum over cuts, and Section[4\.3\.3](https://arxiv.org/html/2610.27398#S4.SS3.SSS3)shows that onlyk\+2k\+2of these cuts can be positive\.

Fork=1k=1,θ=α1\\theta=\\alpha\_\{1\}is identified andL=U=α1L=U=\\alpha\_\{1\}\. So we will only consider cases whenk≥2k\\geq 2below\.

#### 4\.3\.1Column\-wise Fréchet

Recall that the columnxℓx\_\{\\ell\}has masscℓ=ℙ⁡\(xℓ\)=∑ibi​ℓc\_\{\\ell\}=\\mathbb\{P\}\(x\_\{\\ell\}\)=\\sum\_\{i\}b\_\{i\\ell\}, the total mass of its cellsQi​ℓ=\(xℓ,yi\)Q\_\{i\\ell\}=\(x\_\{\\ell\},y\_\{i\}\),i∈\[n\]i\\in\[n\]\.

N1N\_\{1\}N2N\_\{2\}N3N\_\{3\}⋂iGi\\bigcap\_\{i\}G\_\{i\}fit:ℙ⁡\(⋂iGi\)=∑igi−2​cℓ\\mathbb\{P\}\(\\bigcap\_\{i\}G\_\{i\}\)=\\sum\_\{i\}g\_\{i\}\-2c\_\{\\ell\}overlapN1N\_\{1\}N2N\_\{2\}N3N\_\{3\}wrap:⋂iGi=∅\\bigcap\_\{i\}G\_\{i\}=\\varnothingFigure 1:Lemma[12](https://arxiv.org/html/2610.27398#Thmtheorem12)in one column of masscℓc\_\{\\ell\}, witht=3t=3\. We place the complementsNiN\_\{i\}one after another on a circle of circumferencecℓc\_\{\\ell\}\. If they fit, they do not overlap and the union bound holds with equality\. If they do not fit, they wrap around and cover the whole column, so the intersection is empty\.###### Lemma 12\(Column\-wise Fréchet\([Fréchet, 1951](https://arxiv.org/html/2610.27398#bib.bib13)\)\)\.

Fix a columnxℓx\_\{\\ell\}and letG1,…,Gt⊆xℓG\_\{1\},\\dots,G\_\{t\}\\subseteq x\_\{\\ell\}be events\. Thenℙ⁡\(⋂iGi\)≥∑iℙ⁡\(Gi\)−\(r−1\)​cℓ\\mathbb\{P\}\(\\bigcap\_\{i\}G\_\{i\}\)\\geq\\sum\_\{i\}\\mathbb\{P\}\(G\_\{i\}\)\-\(r\-1\)\\,c\_\{\\ell\}\. Conversely, for any massesgi∈\[0,cℓ\]g\_\{i\}\\in\[0,c\_\{\\ell\}\]there is an arrangement insidexℓx\_\{\\ell\}withℙ⁡\(Gi\)=gi\\mathbb\{P\}\(G\_\{i\}\)=g\_\{i\}andℙ⁡\(⋂iGi\)=\(∑igi−\(r−1\)​cℓ\)\+\\mathbb\{P\}\(\\bigcap\_\{i\}G\_\{i\}\)=\(\\sum\_\{i\}g\_\{i\}\-\(r\-1\)\\,c\_\{\\ell\}\)^\{\+\}\. If someGiG\_\{i\}must be a union of cells, this is still possible, and arrangements in different columns can be chosen independently\.

###### Proof\.

LetNi:=xℓ∖GiN\_\{i\}:=x\_\{\\ell\}\\setminus G\_\{i\}be the complement ofGiG\_\{i\}inside the column\. By De Morgan and the union bound,ℙ⁡\(⋂iGi\)=cℓ−ℙ⁡\(⋃iNi\)≥cℓ−∑i\(cℓ−gi\)\\mathbb\{P\}\(\\bigcap\_\{i\}G\_\{i\}\)=c\_\{\\ell\}\-\\mathbb\{P\}\(\\bigcup\_\{i\}N\_\{i\}\)\\geq c\_\{\\ell\}\-\\sum\_\{i\}\(c\_\{\\ell\}\-g\_\{i\}\)\. For the converse, view the column as a circle of circumferencecℓc\_\{\\ell\}and layN1,…,NrN\_\{1\},\\dots,N\_\{r\}end to end as arcs of lengthscℓ−gic\_\{\\ell\}\-g\_\{i\}\(Figure[1](https://arxiv.org/html/2610.27398#S4.F1)\)\. 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 someNiN\_\{i\}and⋂iGi=∅\\bigcap\_\{i\}G\_\{i\}=\\varnothing\. If someGiG\_\{i\}must equal a union of cells \(for instanceAj∩xj=\(xj,yj\)A\_\{j\}\\cap x\_\{j\}=\(x\_\{j\},y\_\{j\}\)whenj≤kj\\leq k\), its complementNiN\_\{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 toNiN\_\{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 Section[4\.2](https://arxiv.org/html/2610.27398#S4.SS2), the inequality holds for every arrangement and gives the bound, and a suitable arrangement attains it\.

#### 4\.3\.2Flow and cuts

For the lower bounds withk≥2k\\geq 2we use the transportation set𝒯:=\{m∈ℝk×n:mj​j=βj,∑ℓ≠jmj​ℓ=dj,0≤mj​ℓ≤cℓ\}\\mathcal\{T\}:=\\\{m\\in\\mathbb\{R\}^\{k\\times n\}:m\_\{jj\}=\\beta\_\{j\},\\ \\sum\_\{\\ell\\neq j\}m\_\{j\\ell\}=d\_\{j\},\\ 0\\leq m\_\{j\\ell\}\\leq c\_\{\\ell\}\\\}\. Recall thatdj=αj−βj=ℙ⁡\(Aj∖xj\)=ℙ⁡\(Aj\)−ℙ⁡\(Aj,xj\)d\_\{j\}=\\alpha\_\{j\}\-\\beta\_\{j\}=\\mathbb\{P\}\(A\_\{j\}\\setminus x\_\{j\}\)=\\mathbb\{P\}\(A\_\{j\}\)\-\\mathbb\{P\}\(A\_\{j\},x\_\{j\}\)is the mass ofAjA\_\{j\}outside its own columnxjx\_\{j\}\. In the tablemm, rowjjdescribes howAjA\_\{j\}is spread over the columns: its diagonal entry ismj​j=βjm\_\{jj\}=\\beta\_\{j\}, and its off\-diagonal entriesmj​ℓm\_\{j\\ell\},ℓ≠j\\ell\\neq j, must add up to exactlydjd\_\{j\}\. We also use the column infloweℓ:=∑j≤k,j≠ℓmj​ℓe\_\{\\ell\}:=\\sum\_\{j\\leq k,\\,j\\neq\\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 givesD:=∑ℓeℓ=∑jdjD:=\\sum\_\{\\ell\}e\_\{\\ell\}=\\sum\_\{j\}d\_\{j\}\.

In the proof of the lower bound, Lemma[12](https://arxiv.org/html/2610.27398#Thmtheorem12)will give, for each columnℓ\\ell, a lower bound of the form\(eℓ−fℓ\)\+\(e\_\{\\ell\}\-f\_\{\\ell\}\)^\{\+\}, wherefℓ≥0f\_\{\\ell\}\\geq 0depends only on the data; forPNS⁡\(k\)\\mathrm\{PNS\}\(k\)it isfℓ=\(k−1\)cℓ−βℓ𝟏\{ℓ≤k\}f\_\{\\ell\}=\(k\-1\)c\_\{\\ell\}\-\\beta\_\{\\ell\}\\mathbf\{1\}\\\{\\ell\\leq k\\\}\. We callfℓf\_\{\\ell\}the*free capacity*of columnℓ\\ell: inflow up tofℓf\_\{\\ell\}costs nothing, and each unit beyond it adds one toθ\\theta\. The lower bound is therefore a minimisation of∑ℓ\(eℓ−fℓ\)\+\\sum\_\{\\ell\}\(e\_\{\\ell\}\-f\_\{\\ell\}\)^\{\+\}over the transportation set\. The next lemma, stated for arbitraryf1,…,fn≥0f\_\{1\},\\dots,f\_\{n\}\\geq 0, rewrites this minimisation as a maximisation over the2k2^\{k\}subsetsJ⊆\[k\]J\\subseteq\[k\]\.

ssA1A\_\{1\}A2A\_\{2\}A3A\_\{3\}x1x\_\{1\}x2x\_\{2\}x3x\_\{3\}x4x\_\{4\}ttd1d\_\{1\}d2d\_\{2\}d3d\_\{3\}f1f\_\{1\}f2f\_\{2\}f3f\_\{3\}f4f\_\{4\}capacitycℓc\_\{\\ell\}Figure 2:The network of Lemma[13](https://arxiv.org/html/2610.27398#Thmtheorem13)fork=3k=3,n=4n=4\. EachAjA\_\{j\}must place massdj=ℙ⁡\(Aj∖xj\)d\_\{j\}=\\mathbb\{P\}\(A\_\{j\}\\setminus x\_\{j\}\)in the columnsxℓx\_\{\\ell\},ℓ≠j\\ell\\neq j, at mostcℓc\_\{\\ell\}in each\. There is no edge fromAjA\_\{j\}toxjx\_\{j\}, because inside its own columnAjA\_\{j\}is fixed to the cell of massβj\\beta\_\{j\}\. Columnxℓx\_\{\\ell\}can absorb up tofℓf\_\{\\ell\}for free, and any inflow beyond that adds toθ\\theta\.###### Lemma 13\(Max\-flow/min\-cut\)\.

Letf1,…,fn≥0f\_\{1\},\\dots,f\_\{n\}\\geq 0\. For a set of rowsJ⊆\[k\]J\\subseteq\[k\], put

Δ⁡\(J\):=∑j∈Jdj−∑ℓ=1nmin⁡\(\|J∖\{ℓ\}\|×cℓ,fℓ\)\.\\Delta\(J\):=\\sum\_\{j\\in J\}d\_\{j\}\-\\sum\_\{\\ell=1\}^\{n\}\\min\\big\(\|J\\setminus\\\{\\ell\\\}\|\\times c\_\{\\ell\},\\ f\_\{\\ell\}\\big\)\.Then

min⁡∑ℓ=1nm∈𝒯⁡\(eℓ−fℓ\)\+=maxJ⊆\[k\]⁡Δ⁡\(J\)\.\\min\_\{m\\in\\mathcal\{T\}\}\\ \\sum\_\{\\ell=1\}^\{n\}\\big\(e\_\{\\ell\}\-f\_\{\\ell\}\\big\)^\{\+\}=\\max\_\{J\\subseteq\[k\]\}\\Delta\(J\)\.

HereJJis any set of rows, i\.e\. of targetsAjA\_\{j\}\. The rows inJJmust send out∑j∈Jdj\\sum\_\{j\\in J\}d\_\{j\}in total, while columnℓ\\ellcan absorb free of cost at mostmin⁡\(\|J∖\{ℓ\}\|×cℓ,fℓ\)\\min\(\|J\\setminus\\\{\\ell\\\}\|\\times c\_\{\\ell\},f\_\{\\ell\}\)of it: at mostcℓc\_\{\\ell\}from each rowj∈Jj\\in Jwithj≠ℓj\\neq\\ell, and at mostfℓf\_\{\\ell\}altogether\. SoΔ⁡\(J\)\\Delta\(J\)is the part of the rows inJJthat cannot be absorbed for free, and eachΔ⁡\(J\)\\Delta\(J\)is a lower bound on the cost\. In the proof,JJappears as the set of rows on the source side of a cut\.

###### Proof\.

Consider the network of Figure[2](https://arxiv.org/html/2610.27398#S4.F2), in which the source feeds rowjjwith capacitydjd\_\{j\}, rowjjfeeds columnℓ≠j\\ell\\neq jwith capacitycℓ=ℙ⁡\(xℓ\)c\_\{\\ell\}=\\mathbb\{P\}\(x\_\{\\ell\}\)\(sincemj​ℓ=ℙ⁡\(Aj∩xℓ\)≤cℓm\_\{j\\ell\}=\\mathbb\{P\}\(A\_\{j\}\\cap x\_\{\\ell\}\)\\leq c\_\{\\ell\}\), and columnℓ\\ellfeeds the sink with capacityfℓf\_\{\\ell\}\. Letφ\\varphibe the value of a maximum flow\. Since\(e−f\)\+=e−min⁡\(e,f\)\(e\-f\)^\{\+\}=e\-\\min\(e,f\)and∑ℓeℓ=D\\sum\_\{\\ell\}e\_\{\\ell\}=D, everym∈𝒯m\\in\\mathcal\{T\}satisfies∑ℓ\(eℓ−fℓ\)\+=D−∑ℓmin⁡\(eℓ,fℓ\)\\sum\_\{\\ell\}\(e\_\{\\ell\}\-f\_\{\\ell\}\)^\{\+\}=D\-\\sum\_\{\\ell\}\\min\(e\_\{\\ell\},f\_\{\\ell\}\)\.

*min⁡∑ℓm∈𝒯⁡\(eℓ−fℓ\)\+≥D−φ\\min\_\{m\\in\\mathcal\{T\}\}\\sum\_\{\\ell\}\(e\_\{\\ell\}\-f\_\{\\ell\}\)^\{\+\}\\geq D\-\\varphi: everym∈𝒯m\\in\\mathcal\{T\}has cost at leastD−φD\-\\varphi\.*Fixm∈𝒯m\\in\\mathcal\{T\}\. We turn it into a flow by letting rowjjsend to columnℓ≠j\\ell\\neq jthe amount

ηj​ℓ:=mj​ℓ​λℓ,λℓ:=\{min⁡\(eℓ,fℓ\)/eℓ,eℓ\>0,0,eℓ=0,\\eta\_\{j\\ell\}:=m\_\{j\\ell\}\\,\\lambda\_\{\\ell\},\\qquad\\lambda\_\{\\ell\}:=\\begin\{cases\}\\min\(e\_\{\\ell\},f\_\{\\ell\}\)/e\_\{\\ell\},&e\_\{\\ell\}\>0,\\\\ 0,&e\_\{\\ell\}=0,\\end\{cases\}that is, the inflows of columnℓ\\ellare scaled down by the common factorλℓ∈\[0,1\]\\lambda\_\{\\ell\}\\in\[0,1\]\. This flow respects every capacity: rowjjships∑ℓ≠jηj​ℓ≤∑ℓ≠jmj​ℓ=dj\\sum\_\{\\ell\\neq j\}\\eta\_\{j\\ell\}\\leq\\sum\_\{\\ell\\neq j\}m\_\{j\\ell\}=d\_\{j\}; on each arcηj​ℓ≤mj​ℓ≤cℓ\\eta\_\{j\\ell\}\\leq m\_\{j\\ell\}\\leq c\_\{\\ell\}; and columnℓ\\ellreceives∑j≠ℓηj​ℓ=λℓ​eℓ=min⁡\(eℓ,fℓ\)≤fℓ\\sum\_\{j\\neq\\ell\}\\eta\_\{j\\ell\}=\\lambda\_\{\\ell\}e\_\{\\ell\}=\\min\(e\_\{\\ell\},f\_\{\\ell\}\)\\leq f\_\{\\ell\}\. Its value is∑ℓmin⁡\(eℓ,fℓ\)\\sum\_\{\\ell\}\\min\(e\_\{\\ell\},f\_\{\\ell\}\), andφ\\varphiis the largest value of any flow, so

∑ℓ\(eℓ−fℓ\)\+=D−∑ℓmin⁡\(eℓ,fℓ\)≥D−φ\.\\sum\_\{\\ell\}\(e\_\{\\ell\}\-f\_\{\\ell\}\)^\{\+\}=D\-\\sum\_\{\\ell\}\\min\(e\_\{\\ell\},f\_\{\\ell\}\)\\geq D\-\\varphi\.
*min⁡∑ℓm∈𝒯⁡\(eℓ−fℓ\)\+≤D−φ\\min\_\{m\\in\\mathcal\{T\}\}\\sum\_\{\\ell\}\(e\_\{\\ell\}\-f\_\{\\ell\}\)^\{\+\}\\leq D\-\\varphi: somem∈𝒯m\\in\\mathcal\{T\}has cost at mostD−φD\-\\varphi\.*Take a maximum flow, and letηj​ℓ≥0\\eta\_\{j\\ell\}\\geq 0be the amount it sends from rowjjto columnℓ≠j\\ell\\neq j\. Write

ηj:=∑ℓ≠jηj​ℓ,φℓ:=∑j≠ℓηj​ℓ\\eta\_\{j\}:=\\sum\_\{\\ell\\neq j\}\\eta\_\{j\\ell\},\\qquad\\qquad\\varphi\_\{\\ell\}:=\\sum\_\{j\\neq\\ell\}\\eta\_\{j\\ell\}for the total amount rowjjships and the total amount columnℓ\\ellreceives, respectively\. So that∑ℓφℓ=φ\\sum\_\{\\ell\}\\varphi\_\{\\ell\}=\\varphi, and the capacities giveηj≤dj\\eta\_\{j\}\\leq d\_\{j\},ηj​ℓ≤cℓ\\eta\_\{j\\ell\}\\leq c\_\{\\ell\}andφℓ≤fℓ\\varphi\_\{\\ell\}\\leq f\_\{\\ell\}\.

*Completing the flow to a tablem∈𝒯m\\in\\mathcal\{T\}\.*Rowjjmust placedjd\_\{j\}in the columnsℓ≠j\\ell\\neq j, and the flow already placesηj\\eta\_\{j\}there\. The room left in its cells is

∑ℓ≠j\(cℓ−ηj​ℓ\)=\(1−cj\)−ηj≥dj−ηj\\sum\_\{\\ell\\neq j\}\(c\_\{\\ell\}\-\\eta\_\{j\\ell\}\)=\(1\-c\_\{j\}\)\-\\eta\_\{j\}\\geq d\_\{j\}\-\\eta\_\{j\}by \([⋆‣2](https://arxiv.org/html/2610.27398#S3.Ex11)\)\. So we can choosemj​ℓ∈\[ηj​ℓ,cℓ\]m\_\{j\\ell\}\\in\[\\eta\_\{j\\ell\},c\_\{\\ell\}\]forℓ≠j\\ell\\neq jwith∑ℓ≠jmj​ℓ=dj\\sum\_\{\\ell\\neq j\}m\_\{j\\ell\}=d\_\{j\}; together withmj​j:=βjm\_\{jj\}:=\\beta\_\{j\}this givesm∈𝒯m\\in\\mathcal\{T\}\.

*Bounding its cost\.*Sincemj​ℓ≥ηj​ℓm\_\{j\\ell\}\\geq\\eta\_\{j\\ell\}, the inflow of columnℓ\\ellsatisfieseℓ≥φℓe\_\{\\ell\}\\geq\\varphi\_\{\\ell\}, andφℓ≤fℓ\\varphi\_\{\\ell\}\\leq f\_\{\\ell\}\. Hence\(eℓ−fℓ\)\+≤eℓ−φℓ\(e\_\{\\ell\}\-f\_\{\\ell\}\)^\{\+\}\\leq e\_\{\\ell\}\-\\varphi\_\{\\ell\}: ifeℓ≥fℓe\_\{\\ell\}\\geq f\_\{\\ell\}, theneℓ−fℓ≤eℓ−φℓe\_\{\\ell\}\-f\_\{\\ell\}\\leq e\_\{\\ell\}\-\\varphi\_\{\\ell\}; ifeℓ<fℓe\_\{\\ell\}<f\_\{\\ell\}, then0≤eℓ−φℓ0\\leq e\_\{\\ell\}\-\\varphi\_\{\\ell\}\. Summing overℓ\\ell,

∑ℓ\(eℓ−fℓ\)\+≤∑ℓeℓ−∑ℓφℓ=D−φ\.\\sum\_\{\\ell\}\(e\_\{\\ell\}\-f\_\{\\ell\}\)^\{\+\}\\ \\leq\\ \\sum\_\{\\ell\}e\_\{\\ell\}\-\\sum\_\{\\ell\}\\varphi\_\{\\ell\}\\ =\\ D\-\\varphi\.
*Computingφ\\varphiby 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\. LetJ⊆\[k\]J\\subseteq\[k\]be the set of rows on the source side\.

- •Each rowj∉Jj\\notin Jis on the sink side, so the arc from the source to rowjjis cut, at costdjd\_\{j\}\.
- •Each columnℓ\\ellis placed on the cheaper side\. On the source side, its arc to the sink is cut, at costfℓf\_\{\\ell\}\. On the sink side, the arcs into it from the rows ofJJare cut; there are\|J∖\{ℓ\}\|\|J\\setminus\\\{\\ell\\\}\|of them \(the number of elements ofJ∖\{ℓ\}J\\setminus\\\{\\ell\\\}\), each of capacitycℓc\_\{\\ell\}, at total cost\|J∖\{ℓ\}\|×cℓ\|J\\setminus\\\{\\ell\\\}\|\\times c\_\{\\ell\}\.

The cheapest cut with row setJJtherefore has capacity∑j∉Jdj\+∑ℓmin⁡\(\|J∖\{ℓ\}\|×cℓ,fℓ\)\\sum\_\{j\\notin J\}d\_\{j\}\+\\sum\_\{\\ell\}\\min\(\|J\\setminus\\\{\\ell\\\}\|\\times c\_\{\\ell\},f\_\{\\ell\}\)\. By the max\-flow/min\-cut theorem\([Ford and Fulkerson, 1956](https://arxiv.org/html/2610.27398#bib.bib12)\),φ\\varphiequals the minimum of this overJJ\. SinceD−∑j∉Jdj=∑j∈JdjD\-\\sum\_\{j\\notin J\}d\_\{j\}=\\sum\_\{j\\in J\}d\_\{j\},

D−φ=maxJ⊆\[k\]⁡\[∑j∈Jdj−∑ℓmin⁡\(\|J∖\{ℓ\}\|×cℓ,fℓ\)\]=maxJ⊆\[k\]⁡Δ⁡\(J\)\.D\-\\varphi=\\max\_\{J\\subseteq\[k\]\}\\Big\[\\sum\_\{j\\in J\}d\_\{j\}\-\\sum\_\{\\ell\}\\min\\big\(\|J\\setminus\\\{\\ell\\\}\|\\times c\_\{\\ell\},\\ f\_\{\\ell\}\\big\)\\Big\]=\\max\_\{J\\subseteq\[k\]\}\\Delta\(J\)\.∎

Lemma[13](https://arxiv.org/html/2610.27398#Thmtheorem13)expresses the lower bound as a maximum over all2k2^\{k\}setsJ⊆\[k\]J\\subseteq\[k\], whereas the published bounds list three expressions; the gap is closed by \([⋆‣2](https://arxiv.org/html/2610.27398#S3.Ex11)\) alone\. We now show that, whenfℓ≥\(k−2\)​cℓf\_\{\\ell\}\\geq\(k\-2\)\\,c\_\{\\ell\}for everyℓ\\ell, every setJJwith\|J\|≤k−2\|J\|\\leq k\-2givesΔ⁡\(J\)≤0\\Delta\(J\)\\leq 0\. SinceΔ⁡\(∅\)=0\\Delta\(\\varnothing\)=0, such sets never attain the maximum, and it suffices to consider thek\+2k\+2setsJ=∅J=\\varnothing,J=\[k\]∖\{i\}J=\[k\]\\setminus\\\{i\\\}\(i≤ki\\leq k\) andJ=\[k\]J=\[k\]\.

###### Lemma 14\(Small cuts\)\.

Iffℓ≥\(k−2\)​cℓf\_\{\\ell\}\\geq\(k\-2\)\\,c\_\{\\ell\}for everyℓ\\elland\|J\|≤k−2\|J\|\\leq k\-2, thenΔ\(J\)=−∑j∈Jsj≤0\\Delta\(J\)=\-\\sum\_\{j\\in J\}s\_\{j\}\\leq 0\.

###### Proof\.

Let\|J\|≤k−2\|J\|\\leq k\-2\. For every columnℓ\\ellwe have\|J∖\{ℓ\}\|≤\|J\|≤k−2\|J\\setminus\\\{\\ell\\\}\|\\leq\|J\|\\leq k\-2, so\|J∖\{ℓ\}\|×cℓ≤\(k−2\)​cℓ≤fℓ\|J\\setminus\\\{\\ell\\\}\|\\times c\_\{\\ell\}\\leq\(k\-2\)\\,c\_\{\\ell\}\\leq f\_\{\\ell\}, and each minimum inΔ⁡\(J\)\\Delta\(J\)equals\|J∖\{ℓ\}\|×cℓ\|J\\setminus\\\{\\ell\\\}\|\\times c\_\{\\ell\}\. Since\|J∖\{ℓ\}\|=\|J\|−1\|J\\setminus\\\{\\ell\\\}\|=\|J\|\-1forℓ∈J\\ell\\in Jand\|J∖\{ℓ\}\|=\|J\|\|J\\setminus\\\{\\ell\\\}\|=\|J\|forℓ∉J\\ell\\notin J, and∑ℓcℓ=1\\sum\_\{\\ell\}c\_\{\\ell\}=1,

∑ℓ=1n\|J∖\{ℓ\}\|×cℓ=\|J\|−∑j∈Jcj\.\\sum\_\{\\ell=1\}^\{n\}\|J\\setminus\\\{\\ell\\\}\|\\times c\_\{\\ell\}=\|J\|\-\\sum\_\{j\\in J\}c\_\{j\}\.Hence

Δ\(J\)=∑j∈Jdj−\|J\|\+∑j∈Jcj=∑j∈J\(dj\+cj−1\)=−∑j∈Jsj≤0,\\Delta\(J\)=\\sum\_\{j\\in J\}d\_\{j\}\-\|J\|\+\\sum\_\{j\\in J\}c\_\{j\}=\\sum\_\{j\\in J\}\(d\_\{j\}\+c\_\{j\}\-1\)=\-\\sum\_\{j\\in J\}s\_\{j\}\\leq 0,where the last inequality is by applying \([⋆‣2](https://arxiv.org/html/2610.27398#S3.Ex11)\)\. ∎

#### 4\.3\.3Proof of the lower bound

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

*Reduction to a flow\.*By Lemma[12](https://arxiv.org/html/2610.27398#Thmtheorem12)in columnℓ\\ell, applied to the eventsAj∩xℓA\_\{j\}\\cap x\_\{\\ell\}\(j≤kj\\leq k\),

θℓ≥\(∑jmj​ℓ−\(k−1\)cℓ\)\+=\(eℓ−fℓ\)\+,fℓ:=\(k−1\)cℓ−βℓ𝟏\{ℓ≤k\}\.\\theta\_\{\\ell\}\\ \\geq\\ \\big\(\\textstyle\\sum\_\{j\}m\_\{j\\ell\}\-\(k\-1\)c\_\{\\ell\}\\big\)^\{\+\}=\(e\_\{\\ell\}\-f\_\{\\ell\}\)^\{\+\},\\qquad f\_\{\\ell\}:=\(k\-1\)c\_\{\\ell\}\-\\beta\_\{\\ell\}\\mathbf\{1\}\\\{\\ell\\leq k\\\}\.Equality holds for a suitable arrangement, simultaneously in all columns\. Hencemin⁡Θ=min⁡∑ℓm∈𝒯⁡\(eℓ−fℓ\)\+\\min\\Theta=\\min\_\{m\\in\\mathcal\{T\}\}\\sum\_\{\\ell\}\(e\_\{\\ell\}\-f\_\{\\ell\}\)^\{\+\}, where everym∈𝒯m\\in\\mathcal\{T\}is realised by some admissible system\. We havefℓ≥\(k−2\)​cℓ≥0f\_\{\\ell\}\\geq\(k\-2\)c\_\{\\ell\}\\geq 0becauseβℓ≤cℓ\\beta\_\{\\ell\}\\leq c\_\{\\ell\}\. By Lemmas[13](https://arxiv.org/html/2610.27398#Thmtheorem13)and[14](https://arxiv.org/html/2610.27398#Thmtheorem14),min⁡Θ=max⁡\{0,Δ​\(\[k\]∖\{i\}\)i≤k,Δ⁡\(\[k\]\)\}\\min\\Theta=\\max\\\{0,\\Delta\(\[k\]\\setminus\\\{i\\\}\)\_\{i\\leq k\},\\Delta\(\[k\]\)\\\}\.

*Evaluating the two cut families\.*By Lemma[14](https://arxiv.org/html/2610.27398#Thmtheorem14), everyJJwith\|J\|≤k−2\|J\|\\leq k\-2hasΔ⁡\(J\)≤0\\Delta\(J\)\\leq 0, so apart fromΔ⁡\(∅\)=0\\Delta\(\\varnothing\)=0, only sets with at leastk−1k\-1elements can give a positive value\. These areJ=\[k\]∖\{i\}J=\[k\]\\setminus\\\{i\\\}fori≤ki\\leq k, andJ=\[k\]J=\[k\]\. Recall thatΔ⁡\(J\)=∑j∈Jdj−∑ℓmin⁡\(\|J∖\{ℓ\}\|×cℓ,fℓ\)\\Delta\(J\)=\\sum\_\{j\\in J\}d\_\{j\}\-\\sum\_\{\\ell\}\\min\\big\(\|J\\setminus\\\{\\ell\\\}\|\\times c\_\{\\ell\},\\ f\_\{\\ell\}\\big\)withfℓ=\(k−1\)cℓ−βℓ𝟏\{ℓ≤k\}f\_\{\\ell\}=\(k\-1\)c\_\{\\ell\}\-\\beta\_\{\\ell\}\\mathbf\{1\}\\\{\\ell\\leq k\\\}, and that∑ℓcℓ=1\\sum\_\{\\ell\}c\_\{\\ell\}=1\.

- •J=\[k\]∖\{i\}J=\[k\]\\setminus\\\{i\\\}for somei≤ki\\leq k\. We compute the minimum column by column: - –forℓ=i\\ell=i,\|J∖\{ℓ\}\|=k−1\|J\\setminus\\\{\\ell\\\}\|=k\-1and the minimum is\(k−1\)​ci−βi=fi\(k\-1\)c\_\{i\}\-\\beta\_\{i\}=f\_\{i\}; - –forℓ≤k\\ell\\leq k,ℓ≠i\\ell\\neq i,\|J∖\{ℓ\}\|=k−2\|J\\setminus\\\{\\ell\\\}\|=k\-2andfℓ≥\(k−2\)​cℓf\_\{\\ell\}\\geq\(k\-2\)c\_\{\\ell\}, so the minimum is\(k−2\)​cℓ\(k\-2\)c\_\{\\ell\}; - –forℓ\>k\\ell\>k,\|J∖\{ℓ\}\|=k−1\|J\\setminus\\\{\\ell\\\}\|=k\-1andfℓ=\(k−1\)​cℓf\_\{\\ell\}=\(k\-1\)c\_\{\\ell\}, so the minimum is\(k−1\)​cℓ\(k\-1\)c\_\{\\ell\}\. Adding these up gives\(k−1\)​∑ℓcℓ−∑j≤k,j≠icj−βi=\(k−1\)−∑j≤k,j≠icj−βi\(k\-1\)\\sum\_\{\\ell\}c\_\{\\ell\}\-\\sum\_\{j\\leq k,\\,j\\neq i\}c\_\{j\}\-\\beta\_\{i\}=\(k\-1\)\-\\sum\_\{j\\leq k,\\,j\\neq i\}c\_\{j\}\-\\beta\_\{i\}\. Hence, usingdj=αj−βjd\_\{j\}=\\alpha\_\{j\}\-\\beta\_\{j\}, Δ⁡\(\[k\]∖\{i\}\)=βi\+∑j≤k,j≠i\(dj\+cj\)−\(k−1\)=βi\+∑j≤k,j≠i\(αj\+cj−βj\)−\(k−1\)\.\\Delta\(\[k\]\\setminus\\\{i\\\}\)=\\beta\_\{i\}\+\\sum\_\{j\\leq k,\\,j\\neq i\}\(d\_\{j\}\+c\_\{j\}\)\-\(k\-1\)=\\beta\_\{i\}\+\\sum\_\{j\\leq k,\\,j\\neq i\}\(\\alpha\_\{j\}\+c\_\{j\}\-\\beta\_\{j\}\)\-\(k\-1\)\.
- •J=\[k\]J=\[k\]\. We also compute column by column: - –forℓ≤k\\ell\\leq k,\|J∖\{ℓ\}\|=k−1\|J\\setminus\\\{\\ell\\\}\|=k\-1and the minimum is\(k−1\)​cℓ−βℓ=fℓ\(k\-1\)c\_\{\\ell\}\-\\beta\_\{\\ell\}=f\_\{\\ell\}; - –forℓ\>k\\ell\>k,\|J∖\{ℓ\}\|=k\|J\\setminus\\\{\\ell\\\}\|=kand the minimum ismin⁡\(k​cℓ,\(k−1\)​cℓ\)=\(k−1\)​cℓ\\min\(kc\_\{\\ell\},\(k\-1\)c\_\{\\ell\}\)=\(k\-1\)c\_\{\\ell\}\. Adding these up gives\(k−1\)−∑j≤kβj\(k\-1\)\-\\sum\_\{j\\leq k\}\\beta\_\{j\}, hence Δ⁡\(\[k\]\)=∑j≤kdj−\(k−1\)\+∑j≤kβj=∑j≤kαj−\(k−1\)\.\\Delta\(\[k\]\)=\\sum\_\{j\\leq k\}d\_\{j\}\-\(k\-1\)\+\\sum\_\{j\\leq k\}\\beta\_\{j\}=\\sum\_\{j\\leq k\}\\alpha\_\{j\}\-\(k\-1\)\.

Together withΔ⁡\(∅\)=0\\Delta\(\\varnothing\)=0, these are exactly the three terms ofLL:Δ⁡\(∅\)=0=L1\\Delta\(\\varnothing\)=0=L\_\{1\},Δ⁡\(\[k\]\)=L2\\Delta\(\[k\]\)=L\_\{2\}, andmaxi≤k⁡Δ⁡\(\[k\]∖\{i\}\)=L3\\max\_\{i\\leq k\}\\Delta\(\[k\]\\setminus\\\{i\\\}\)=L\_\{3\}\. Thusmin⁡Θ=L\\min\\Theta=L, and with Section[4\.2](https://arxiv.org/html/2610.27398#S4.SS2), Theorem[7](https://arxiv.org/html/2610.27398#Thmtheorem7)is proved\.

### 4\.4The other three families

The same argument works for targets of the formℙ⁡\(S,G\)\\mathbb\{P\}\(S,G\)whenG≠ΩG\\neq\\Omega\. By Lemma[4](https://arxiv.org/html/2610.27398#Thmtheorem4), we apply admissible systems again\. We restate the bounds of[Shu et al\. \(2026\)](https://arxiv.org/html/2610.27398#bib.bib1)in our notation, and give the full proofs in Appendix\. Throughout, we use the canonical form, in whichp\>kp\>k\.

##### PSub⁡\(k,p\)\\mathrm\{PSub\}\(k,p\)andPN⁡\(k,p,q\)\\mathrm\{PN\}\(k,p,q\)\.

G=xpG=x\_\{p\}forPSub\\mathrm\{PSub\}, andG=\(xp,yq\)=Qq​p⊆xpG=\(x\_\{p\},y\_\{q\}\)=Q\_\{qp\}\\subseteq x\_\{p\}forPN\\mathrm\{PN\}\. We writeγ:=ℙ⁡\(G\)\\gamma:=\\mathbb\{P\}\(G\), soγ=cp\\gamma=c\_\{p\}forPSub\\mathrm\{PSub\}andγ=bq​p\\gamma=b\_\{qp\}forPN\\mathrm\{PN\}by consistency\. The target isθ=ℙ⁡\(S,G\)\\theta=\\mathbb\{P\}\(S,G\), and the bounds are

max⁡\{0,∑j≤k\(αj\+cj−βj\)\+γ−k\}≤θ≤min⁡\{γ,minj≤k⁡dj\}\.\\max\\Big\\\{0,\\ \\sum\_\{j\\leq k\}\(\\alpha\_\{j\}\+c\_\{j\}\-\\beta\_\{j\}\)\+\\gamma\-k\\Big\\\}\\ \\leq\\ \\theta\\ \\leq\\ \\min\\Big\\\{\\gamma,\\ \\min\_\{j\\leq k\}d\_\{j\}\\Big\\\}\.\(9\)

##### PRep⁡\(k,q\)\\mathrm\{PRep\}\(k,q\)\.

The target isθ=ℙ⁡\(S,yq\)\\theta=\\mathbb\{P\}\(S,y\_\{q\}\)\. By consistency, only the cells of rowqqin columnqq\(ifq≤kq\\leq k\) and in the columnsℓ\>k\\ell\>kcan meetSS; their total mass is

T:=βq𝟏\{q≤k\}\+∑ℓ\>kbq​ℓ,T:=\\beta\_\{q\}\\mathbf\{1\}\\\{q\\leq k\\\}\+\\sum\_\{\\ell\>k\}b\_\{q\\ell\},and the bounds are

θ\\displaystyle\\theta≥max\{0,∑j≤k\(αj\+cj−βj\)\+T−k,1\{q≤k\}\[βq\+∑j≤k,j≠q\(αj\+cj−βj\)−k\+1\]\},\\displaystyle\\ \\geq\\ \\max\\Big\\\{0,\\ \\sum\_\{j\\leq k\}\(\\alpha\_\{j\}\+c\_\{j\}\-\\beta\_\{j\}\)\+T\-k,\\ \\mathbf\{1\}\\\{q\\leq k\\\}\\Big\[\\beta\_\{q\}\+\\\!\\\!\\sum\_\{j\\leq k,\\,j\\neq q\}\\\!\\\!\(\\alpha\_\{j\}\+c\_\{j\}\-\\beta\_\{j\}\)\-k\+1\\Big\]\\Big\\\},\(10\)θ\\displaystyle\\theta≤min\{T,αq\(ifq≤k\),minj≤k,j≠qdj\}\.\\displaystyle\\ \\leq\\ \\min\\Big\\\{T,\\ \\ \\alpha\_\{q\}\\ \\text\{\(if $q\\leq k$\)\},\\ \\ \\min\_\{j\\leq k,\\,j\\neq q\}d\_\{j\}\\Big\\\}\.\(11\)
###### Theorem 15\.

For any compatible data and any admissibleppandqq, the bounds \([9](https://arxiv.org/html/2610.27398#S4.E9)\) onPSub⁡\(k,p\)\\mathrm\{PSub\}\(k,p\)andPN⁡\(k,p,q\)\\mathrm\{PN\}\(k,p,q\)and the bounds \([10](https://arxiv.org/html/2610.27398#S4.E10)\)–\([11](https://arxiv.org/html/2610.27398#S4.E11)\) onPRep⁡\(k,q\)\\mathrm\{PRep\}\(k,q\)are sharp for everyk≥1k\\geq 1\.

ForPRep⁡\(k,q\)\\mathrm\{PRep\}\(k,q\)withk=1k=1, the max\-flow argument of Section[4\.3](https://arxiv.org/html/2610.27398#S4.SS3)does not apply, since the free capacityfq=−βqf\_\{q\}=\-\\beta\_\{q\}is negative, but sharpness still holds and follows from Theorem[17](https://arxiv.org/html/2610.27398#Thmtheorem17)\. The full proofs of sharpness for these three families are given in the appendix\.

So far each target form pairsxjx\_\{j\}withyjy\_\{j\}\. A general query may pairxjx\_\{j\}with any outcome, for exampleℙ⁡\(y3x1,y1x2\)\\mathbb\{P\}\(y\_\{\{3\}\_\{x\_\{1\}\}\},y\_\{\{1\}\_\{x\_\{2\}\}\}\)\.[Shu et al\. \(2026\)](https://arxiv.org/html/2610.27398#bib.bib1)obtain its bounds from the canonical ones by substitution: for a targetyixjy\_\{\{i\}\_\{x\_\{j\}\}\}, they useℙ⁡\(yixj\)\\mathbb\{P\}\(y\_\{\{i\}\_\{x\_\{j\}\}\}\)in place ofℙ⁡\(yjxj\)\\mathbb\{P\}\(y\_\{\{j\}\_\{x\_\{j\}\}\}\)andℙ⁡\(xj,yi\)\\mathbb\{P\}\(x\_\{j\},y\_\{i\}\)in place ofℙ⁡\(xj,yj\)\\mathbb\{P\}\(x\_\{j\},y\_\{j\}\)\.

###### Proposition 16\.

Substitution gives the sharp bounds forPNS⁡\(k\)\\mathrm\{PNS\}\(k\),PSub⁡\(k,p\)\\mathrm\{PSub\}\(k,p\)andPN⁡\(k,p,q\)\\mathrm\{PN\}\(k,p,q\)\. ForPRep⁡\(k,q\)\\mathrm\{PRep\}\(k,q\), it gives the sharp bounds when at most one target has the formyqxjy\_\{\{q\}\_\{x\_\{j\}\}\}\. Theorem[17](https://arxiv.org/html/2610.27398#Thmtheorem17)covers the remaining case, in which more than one target has the formyqxjy\_\{\{q\}\_\{x\_\{j\}\}\}, for example when bothyqx1y\_\{\{q\}\_\{x\_\{1\}\}\}andyqx2y\_\{\{q\}\_\{x\_\{2\}\}\}appear\.

A complete proof follows from Theorem[17](https://arxiv.org/html/2610.27398#Thmtheorem17); see Appendix\.

## 5Unified 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](https://arxiv.org/html/2610.27398#Thmtheorem7)forPNS⁡\(k\)\\mathrm\{PNS\}\(k\)and \([9](https://arxiv.org/html/2610.27398#S4.E9)\)–\([11](https://arxiv.org/html/2610.27398#S4.E11)\) for the other three\), are four instances of a single statement\. The four families differ only in the factual eventGG, and the proofs above useGGin one place: through the part ofGGin each column that can still meetSSonce 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 keepGGto be a factual event, and change the target outcome toi1,…,ik∈\[n\]i\_\{1\},\\dots,i\_\{k\}\\in\[n\], we allowiu=ivi\_\{u\}=i\_\{v\}foru,v∈\[k\]u,v\\in\[k\]andu≠vu\\neq v\. We also change the notation ofAjA\_\{j\}we defined in Section[3](https://arxiv.org/html/2610.27398#S3)as

Aj:=yijxj\.A\_\{j\}:=y\_\{\{i\_\{j\}\}\_\{x\_\{j\}\}\}\.According to this newAjA\_\{j\}, we have

S:=⋂j≤kAj,θ:=ℙ⁡\(S,G\),αj:=aij​j,βj:=bij​j,\\qquad S:=\\textstyle\\bigcap\_\{j\\leq k\}A\_\{j\},\\qquad\\theta:=\\mathbb\{P\}\(S,G\),\\qquad\\alpha\_\{j\}:=a\_\{i\_\{j\}j\},\\qquad\\beta\_\{j\}:=b\_\{i\_\{j\}j\},and keepdj=αj−βjd\_\{j\}=\\alpha\_\{j\}\-\\beta\_\{j\},cj=ℙ⁡\(xj\)c\_\{j\}=\\mathbb\{P\}\(x\_\{j\}\)andsj=1−cj−djs\_\{j\}=1\-c\_\{j\}\-d\_\{j\}\.

With the newαj\\alpha\_\{j\}andβj\\beta\_\{j\}, we havesj=\(1−aij​j\)−\(cj−bij​j\)s\_\{j\}=\(1\-a\_\{i\_\{j\}j\}\)\-\(c\_\{j\}\-b\_\{i\_\{j\}j\}\), which involves the other rowsi≠iji\\neq i\_\{j\}of columnjj\. By consistency,bi​j≤ai​jb\_\{ij\}\\leq a\_\{ij\}for everyiiandjj, summing over these rows givessj=∑i≠ij\(ai​j−bi​j\)≥0s\_\{j\}=\\sum\_\{i\\neq i\_\{j\}\}\(a\_\{ij\}\-b\_\{ij\}\)\\geq 0, so \([⋆‣2](https://arxiv.org/html/2610.27398#S3.Ex11)\) still holds\. The proof of Lemma[4](https://arxiv.org/html/2610.27398#Thmtheorem4)also remains valid with the target outcomejjreplaced byiji\_\{j\}throughout, soΘ\\Thetais still the set of values of admissible systems with the change of notationAj∩xj=Qij​jA\_\{j\}\\cap x\_\{j\}=Q\_\{i\_\{j\}\\,j\}\.

For a target columnxjx\_\{j\}withj≤kj\\leq k\. Every unit in this column receivedxjx\_\{j\}, so by consistency its outcome underxjx\_\{j\}is simply its observed outcome\. We letEjE\_\{j\}denote whenAjA\_\{j\}holds, and letFjF\_\{j\}denote whenAjA\_\{j\}fails on the rest of the column,

Ej:=Qij​j=\(xj,yij\),Fj:=xj∖Ej\.E\_\{j\}:=Q\_\{i\_\{j\}\\,j\}=\(x\_\{j\},y\_\{i\_\{j\}\}\),\\qquad F\_\{j\}:=x\_\{j\}\\setminus E\_\{j\}\.Let

C:=G∖⋃j≤kFj\.C:=G\\setminus\\textstyle\\bigcup\_\{j\\leq k\}F\_\{j\}\.Thenθ\\thetacan be rewritten asθ=ℙ⁡\(S,C\)\\theta=\\mathbb\{P\}\(S,C\), since no unit inFjF\_\{j\}can be inSS, so we can dropFjF\_\{j\}fromGGand the value ofθ\\thetastays the same\. Write

γℓ:=ℙ⁡\(C,xℓ\)\\gamma\_\{\\ell\}:=\\mathbb\{P\}\(C,x\_\{\\ell\}\)for the mass ofCCin columnℓ\\ell, andγ:=ℙ⁡\(C\)=∑ℓγℓ\\gamma:=\\mathbb\{P\}\(C\)=\\sum\_\{\\ell\}\\gamma\_\{\\ell\}\. In a target column onlyEjE\_\{j\}can remain, soγj=βj\\gamma\_\{j\}=\\beta\_\{j\}ifEj⊆GE\_\{j\}\\subseteq Gandγj=0\\gamma\_\{j\}=0otherwise\. In a columnℓ\>k\\ell\>knothing is dropped,C=GC=G, soγℓ\\gamma\_\{\\ell\}is just the mass ofGGin that column\.

###### Theorem 17\(Unified form\)\.

In every compatible pair of tables, for everyk≥1k\\geq 1, all target outcomesi1,…,iki\_\{1\},\\dots,i\_\{k\}and every factual eventGG,Θ=\[LG,UG\]\\Theta=\[L\_\{G\},U\_\{G\}\], where

LG\\displaystyle L\_\{G\}=max\{0⏟L1,γ−∑j≤ksj⏟L2,maxi≤k⁡\(γi−∑j≤k,j≠isj\)⏟L3\},\\displaystyle=\\max\\Big\\\{\\ \\underbrace\{0\}\_\{L\_\{1\}\},\\ \\ \\underbrace\{\\gamma\-\\textstyle\\sum\_\{j\\leq k\}s\_\{j\}\}\_\{L\_\{2\}\},\\ \\ \\underbrace\{\\max\_\{i\\leq k\}\\big\(\\gamma\_\{i\}\-\\textstyle\\sum\_\{j\\leq k,\\,j\\neq i\}s\_\{j\}\\big\)\}\_\{L\_\{3\}\}\\ \\Big\\\},UG\\displaystyle U\_\{G\}=min\{γ⏟U1,minj≤k⁡\(dj\+γj\)⏟U2,minI⊆\[k\],\|I\|≥2⁡1\|I\|−1​∑j∈Idj⏟U3\}\.\\displaystyle=\\min\\Big\\\{\\ \\underbrace\{\\gamma\}\_\{U\_\{1\}\},\\ \\ \\underbrace\{\\min\_\{j\\leq k\}\\,\(d\_\{j\}\+\\gamma\_\{j\}\)\}\_\{U\_\{2\}\},\\ \\ \\underbrace\{\\min\_\{I\\subseteq\[k\],\\,\|I\|\\geq 2\}\\tfrac\{1\}\{\|I\|\-1\}\\textstyle\\sum\_\{j\\in I\}d\_\{j\}\}\_\{U\_\{3\}\}\\ \\Big\\\}\.Whenk=1k=1, the termU3U\_\{3\}is absent andL3=γ1L\_\{3\}=\\gamma\_\{1\}\.

The theorem depends onGGonly through the vector\(γ1,…,γn\)\(\\gamma\_\{1\},\\dots,\\gamma\_\{n\}\), which records whereGGsurvives consistency\. For the canonical families \(ij=ji\_\{j\}=j,p\>kp\>k\):

ForPSub\\mathrm\{PSub\}andPN\\mathrm\{PN\},γ\\gammais theγ=ℙ⁡\(G\)\\gamma=\\mathbb\{P\}\(G\)of \([9](https://arxiv.org/html/2610.27398#S4.E9)\), and forPRep\\mathrm\{PRep\}it isTT\.

Substituting these values into Theorem[17](https://arxiv.org/html/2610.27398#Thmtheorem17)and using∑ℓcℓ=1\\sum\_\{\\ell\}c\_\{\\ell\}=1recovers four families\. ForPSub\\mathrm\{PSub\},PN\\mathrm\{PN\}andPRep\\mathrm\{PRep\}the termU3U\_\{3\}is redundant, since an average of thedjd\_\{j\}overIIis never smaller thanminj⁡dj\\min\_\{j\}d\_\{j\}, and everyL3L\_\{3\}term withγi=0\\gamma\_\{i\}=0is non\-positive\.

The proof of Theorem[17](https://arxiv.org/html/2610.27398#Thmtheorem17)is given in Appendix\.

## 6Conclusion

We have proved the conjecture of[Shu et al\. \(2026\)](https://arxiv.org/html/2610.27398#bib.bib1): 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 ofSScan 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\. \(2026\)](https://arxiv.org/html/2610.27398#bib.bib1), 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\.

## References

- Balke \(1995\)A\. A\. BalkeProbabilistic counterfactuals: semantics, computation, and applications\.Ph\.D\. Thesis,University of California, Los Angeles\.Cited by:[§1](https://arxiv.org/html/2610.27398#S1.p2.1),[§2](https://arxiv.org/html/2610.27398#S2.p4.1)\.
- Balke and Pearl \(1997\)A\. Balke and J\. PearlBounds on treatment effects from studies with imperfect compliance\.Journal of the American Statistical Association92\(439\),pp\. 1171–1176\.Cited by:[§1](https://arxiv.org/html/2610.27398#S1.p2.1),[§3](https://arxiv.org/html/2610.27398#S3.SS0.SSS0.Px1.p1.1)\.
- Ford and Fulkerson \(1956\)L\. R\. Ford and D\. R\. FulkersonMaximal flow through a network\.Canadian Journal of Mathematics8,pp\. 399–404\.Cited by:[§4\.3\.2](https://arxiv.org/html/2610.27398#S4.SS3.SSS2.p10.1.1)\.
- Fréchet \(1951\)M\. FréchetSur les tableaux de corrélation dont les marges sont données\.Annales de l’Université de Lyon, Section A14,pp\. 53–77\.Cited by:[Lemma 12](https://arxiv.org/html/2610.27398#Thmtheorem12)\.
- Galles and Pearl \(1998\)D\. Galles and J\. PearlAn axiomatic characterization of causal counterfactuals\.Foundations of Science3,pp\. 151–182\.Cited by:[§2](https://arxiv.org/html/2610.27398#S2.p1.1),[§3](https://arxiv.org/html/2610.27398#S3.p3.2)\.
- Halpern \(2000\)J\. Y\. HalpernAxiomatizing causal reasoning\.Journal of Artificial Intelligence Research12,pp\. 317–337\.Cited by:[§2](https://arxiv.org/html/2610.27398#S2.p1.1)\.
- Li and Pearl \(2019\)A\. Li and J\. PearlUnit selection based on counterfactual logic\.InProceedings of the Twenty\-Eighth International Joint Conference on Artificial Intelligence \(IJCAI\),Cited by:[§1](https://arxiv.org/html/2610.27398#S1.p2.1),[§2](https://arxiv.org/html/2610.27398#S2.p4.1)\.
- Li and Pearl \(2022\)A\. Li and J\. PearlUnit selection with causal diagram\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.36,pp\. 5765–5772\.Cited by:[§1](https://arxiv.org/html/2610.27398#S1.p2.1),[§2](https://arxiv.org/html/2610.27398#S2.p4.1)\.
- Li and Pearl \(2024\)A\. Li and J\. PearlProbabilities of causation with nonbinary treatment and effect\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.38,pp\. 20465–20472\.Cited by:[§1](https://arxiv.org/html/2610.27398#S1.p2.1),[§2](https://arxiv.org/html/2610.27398#S2.p5.1)\.
- Pearl \(1999\)J\. PearlProbabilities of causation: three counterfactual interpretations and their identification\.Synthese121,pp\. 93–149\.Cited by:[§1](https://arxiv.org/html/2610.27398#S1.p1.1),[§2](https://arxiv.org/html/2610.27398#S2.p3.1),[Definition 1](https://arxiv.org/html/2610.27398#Thmtheorem1)\.
- Pearl \(2009\)J\. PearlCausality\.Cambridge university press\.Cited by:[§3](https://arxiv.org/html/2610.27398#S3.p3.2)\.
- Pearl \(2010\)J\. PearlOn the consistency rule in causal inference: axiom, definition, assumption, or theorem?\.Epidemiology21\(6\),pp\. 872–875\.Cited by:[§3](https://arxiv.org/html/2610.27398#S3.p3.2)\.
- Shuet al\.\(2026\)X\. Shu, S\. Wang, and A\. LiIdentification of probabilities of causation: from recursive to closed\-form bounds\.InProceedings of the Thirty\-Fifth International Joint Conference on Artificial Intelligence,IJCAI\-2026,pp\. 4063–4070\.External Links:[Link](http://dx.doi.org/10.24963/ijcai.2026/452),[Document](https://dx.doi.org/10.24963/ijcai.2026/452)Cited by:[1st item](https://arxiv.org/html/2610.27398#S1.I1.i1.p1.1),[§1](https://arxiv.org/html/2610.27398#S1.p2.1),[§2](https://arxiv.org/html/2610.27398#S2.p5.1),[§2](https://arxiv.org/html/2610.27398#S2.p5.2),[§3](https://arxiv.org/html/2610.27398#S3.SS0.SSS0.Px1.p11.1),[§3](https://arxiv.org/html/2610.27398#S3.SS0.SSS0.Px1.p8.1),[§3](https://arxiv.org/html/2610.27398#S3.p1.1),[§4\.1](https://arxiv.org/html/2610.27398#S4.SS1.p1.1),[§4\.2](https://arxiv.org/html/2610.27398#S4.SS2.p1.1),[§4\.4](https://arxiv.org/html/2610.27398#S4.SS4.SSS0.Px2.p3.1),[§4\.4](https://arxiv.org/html/2610.27398#S4.SS4.p1.1),[§6](https://arxiv.org/html/2610.27398#S6.p1.1)\.
- Tian and Pearl \(2000\)J\. Tian and J\. PearlProbabilities of causation: bounds and identification\.Annals of Mathematics and Artificial Intelligence28\(1–4\),pp\. 287–313\.Cited by:[§1](https://arxiv.org/html/2610.27398#S1.p2.1),[§2](https://arxiv.org/html/2610.27398#S2.p4.1),[§3](https://arxiv.org/html/2610.27398#S3.SS0.SSS0.Px1.p1.1)\.
- Zhanget al\.\(2022\)J\. Zhang, J\. Tian, and E\. BareinboimPartial counterfactual identification from observational and experimental data\.InInternational Conference on Machine Learning \(ICML\),pp\. 26548–26558\.Cited by:[§1](https://arxiv.org/html/2610.27398#S1.p2.1)\.