Answer: Always constructible in polynomial time in \(m,\tau,k,q,L\), with at most \(k(\tau-1)+1\) supported panels.
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor every 𝑞∈[𝑘], FairGreedyCapture𝑘 is fair and in the ex post 6-𝑞-core.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational metric \(d:T\times T\to\mathbb{Q}_{\ge0}\), rational distribution \(\mu\), panel size \(k\), and \(q\in[k]\), construct a distribution \(\lambda\) over typed panels \(p\) of size \(k\) such that \(\mathbb{E}_{\lambda}[p_t]=k\mu_t\) for every \(t\), and every supported \(p\) satisfies \(V_{\mu,q}(p,p',6)<r/k\) for every typed alternative panel \(p'\) of size \(r\), where \(V_{\mu,q}(p,p',\alpha)=\sum_t\mu_t\mathbf{1}[c_q(t,p)>\alpha c_q(t,p')]\).
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; the number of available representative types is \(m=\tau\).
Input also includes a rational metric \(d:T\times T\to\mathbb{Q}_{\ge0}\), a positive unary-encoded panel size \(k\), and an integer \(1\le q\le k\). Let \(L\) be the total input bit length.
A typed panel of size \(s\) is a vector \(p\in\mathbb{Z}_{\ge0}^{T}\) with \(\sum_t p_t=s\); repeated types represent distinct citizens of that type, with no finite availability cap.
For \(s\ge q\), let \(c_q(t,p)\) be the \(q\)-th smallest distance in the multiset containing \(p_u\) copies of \(d(t,u)\) for each \(u\in T\); distance ties do not affect this value.
Define \(V_{\mu,q}(p,p',\alpha)=\sum_{t\in T}\mu_t\mathbf{1}[c_q(t,p)>\alpha c_q(t,p')]\).
The required object is a finite rational distribution \(\lambda\) over size-\(k\) typed panels, represented by its positive-probability panels and probabilities, satisfying \(\mathbb{E}_{\lambda}[p_t]=k\mu_t\) for every \(t\).
Every panel \(p\) with positive probability must satisfy \(V_{\mu,q}(p,p',6)<r/k\) for every typed alternative \(p'\) of every integer size \(q\le r\le k\).
Can such a distribution always be constructed in polynomial time in \(m,\tau,k,q,L\), or is this construction problem NP-hard?
For finite populations, FairGreedyCapture runs in polynomial time and produces a fair distribution whose supported panels satisfy the factor-\(6\) ex post core condition simultaneously for all \(1\le q\le k\). [Ebadian–Micha](https://arxiv.org/html/2406.00913v1).
No result settling this exact support-encoded mass construction problem was identified in the sources checked.
The distribution can always be constructed in polynomial time in \(m,\tau,k,q,L\). The construction below produces at most \(k(\tau-1)+1\) positive-probability panels. Moreover, every supported panel satisfies the required condition simultaneously for all \(1\le q\le k\).
We use the ball-growing idea of [Ebadian–Micha’s FairGreedyCapture](https://arxiv.org/html/2406.00913v1), but work directly with type masses. Unlimited repetition of types permits an elementary distribution construction in place of matching individual citizens. We prove correctness and polynomial bit complexity explicitly.
For \(v\in T\) and \(R\ge0\), define the closed ball
\(B(v,R)=\{t\in T:d(v,t)\le R\}\).
Initialize residual amounts \(y_t=k\mu_t\). Their total is \(k\). We construct a nonnegative matrix \(X\) with \(k\) rows and \(\tau\) columns.
At each step:
Use fixed orders to resolve all choices. Step 2 can be implemented greedily by allocating the smaller of the current residual amount and the row’s remaining capacity.
Whenever a row remains to be constructed, the total residual amount is a positive integer and hence at least one. A ball containing all types is therefore eligible. Each row removes exactly one unit, so the procedure constructs exactly \(k\) rows and exhausts all residual amounts. Consequently,
\(\sum_{t\in T}X_{j,t}=1\quad\text{for every }j,\qquad \sum_{j=1}^{k}X_{j,t}=k\mu_t\quad\text{for every }t.\)
Write \(v_j,\rho_j\) for the chosen center and radius of row \(j\). Then
\(X_{j,t}>0\ \Longrightarrow\ d(v_j,t)\le\rho_j.\)
Because residual amounts only decrease, the chosen radii are nondecreasing.
Lemma. Let \(C\subseteq B(a,R)\), where \(a\in T\) and \(R\ge0\). If \(k\sum_{t\in C}\mu_t\ge q\), then at least \(q\) distinct rows satisfy both:
Proof. Consider the state immediately after all rows with radius at most \(R\) have been constructed.
At that state,
\(\sum_{t\in B(a,R)}y_t<1.\)
Indeed, if all rows have been constructed, every residual amount is zero. Otherwise, a residual amount of at least one in this ball would make a radius at most \(R\) eligible, contradicting the fact that the next chosen radius exceeds \(R\). The minimum eligible radius is attained at an input distance, so this argument also applies when \(R\) is not itself an input distance.
Suppose only \(h\le q-1\) of the constructed rows allocate positive amount from \(C\). Each row removes at most one unit from \(C\). Thus its remaining amount is at least
\(\sum_{t\in C}y_t =k\sum_{t\in C}\mu_t-\sum_{j:\rho_j\le R}\sum_{t\in C}X_{j,t} \ge q-h\ge1.\)
Since \(C\subseteq B(a,R)\), this contradicts the preceding strict inequality. This proves the lemma.
Fix an ordering \(T=\{t_1,\ldots,t_\tau\}\). For each row \(j\), define cumulative sums
\(b_{j,0}=0,\qquad b_{j,i}=\sum_{\ell=1}^{i}X_{j,t_\ell}\quad(1\le i\le\tau).\)
Thus \(b_{j,\tau}=1\). Collect all distinct cumulative sums and sort them:
\(0=a_0<a_1<\cdots<a_N=1.\)
There are at most \(k(\tau-1)\) interior cumulative sums, so
\(N\le k(\tau-1)+1.\)
For each interval \([a_{\ell-1},a_\ell)\), assign row \(j\) the unique type \(t_i\) satisfying
\(b_{j,i-1}\le a_{\ell-1}<b_{j,i}.\)
Such a type exists and is unique; zero-length row intervals are skipped. All cumulative sums are breakpoints, so the entire interval receives the same assignment in every row.
Let \(p^\ell_t\) count the rows assigned type \(t\), and give this panel probability
\(\lambda_\ell=a_\ell-a_{\ell-1}>0.\)
Merge identical panels by adding their probabilities. The resulting distribution has at most \(N\) panels, each of size \(k\), and its probabilities sum to one.
For any row \(j\), the total probability of assigning it type \(t\) equals the length of its corresponding interval, namely \(X_{j,t}\). Therefore,
\(\mathbb{E}_{\lambda}[p_t]=\sum_{j=1}^{k}X_{j,t}=k\mu_t.\)
Every panel produced also has a row assignment \(s_1,\ldots,s_k\) satisfying \(X_{j,s_j}>0\). Although different rows may choose the same type, they contribute distinct representative occurrences, as allowed by the task.
Fix any supported panel \(p\), any \(q\in\{1,\ldots,k\}\), and any alternative \(p'\) of size \(r\), where \(q\le r\le k\).
Suppose, toward a contradiction, that
\(V_{\mu,q}(p,p',6)\ge r/k.\)
Define
\(S=\{t\in T:c_q(t,p)>6c_q(t,p')\}.\)
Then \(\sum_{t\in S}\mu_t\ge r/k>0\), so \(S\) is nonempty.
Label the \(r\) representative occurrences of \(p'\), retaining their types as locations. For each \(t\in S\), choose a set \(Q_t\) of its \(q\) nearest occurrences, resolving ties arbitrarily but consistently.
Partition \(S\) as follows. Among the remaining types, choose an anchor \(a\) maximizing \(c_q(a,p')\). Its group consists of all remaining types \(t\) for which \(Q_t\cap Q_a\ne\varnothing\). Remove this group and repeat.
Write the resulting groups as \(C_1,\ldots,C_h\), with anchors \(a_1,\ldots,a_h\). The anchors’ occurrence sets are pairwise disjoint: a later anchor sharing an occurrence with an earlier anchor would already have been removed. Since every anchor uses \(q\) occurrences,
\(hq\le r,\qquad h\le\lfloor r/q\rfloor.\)
Some group \(C\), with anchor \(a\), therefore satisfies
\(\sum_{t\in C}\mu_t\ge \frac{\sum_{t\in S}\mu_t}{h}\ge\frac{r}{kh}\ge\frac{q}{k}.\)
Put \(A=c_q(a,p')\). For every \(t\in C\), the maximizing choice of anchor gives \(c_q(t,p')\le A\). Choose an occurrence in \(Q_t\cap Q_a\), with type \(u\). By the triangle inequality,
\(d(a,t)\le d(a,u)+d(u,t)\le c_q(a,p')+c_q(t,p')\le2A.\)
Thus
\(C\subseteq B(a,2A),\qquad k\sum_{t\in C}\mu_t\ge q.\)
This reasoning includes the case \(A=0\).
Apply the lemma from Section 2 to \(C\subseteq B(a,2A)\). It supplies \(q\) distinct rows with \(\rho_j\le2A\), each allocating positive amount to some \(t_j\in C\).
Use a row assignment \(s_1,\ldots,s_k\) that generates \(p\). For each of those rows, both \(t_j\) and \(s_j\) belong to its allocation ball. Hence
\(d(a,s_j) \le d(a,t_j)+d(t_j,v_j)+d(v_j,s_j) \le2A+2\rho_j \le6A.\)
These \(q\) distinct rows give \(q\) distinct representative occurrences in \(p\), even if some have identical types. Therefore,
\(c_q(a,p)\le6A=6c_q(a,p').\)
But the anchor \(a\) belongs to \(C\subseteq S\), where the reverse strict inequality holds. This is a contradiction.
Consequently,
\(V_{\mu,q}(p,p',6)<r/k.\)
The supported panel, the value of \(q\), and the alternative were arbitrary. Thus every supported panel satisfies all required inequalities simultaneously.
Write each input mass as \(\mu_t=A_t/B_t\), with positive integer denominator \(B_t\), and define
\(D=\prod_{t\in T}B_t.\)
The binary length of \(D\) is at most the sum of the input denominator lengths, hence \(O(L)\). Every initial residual amount \(k\mu_t\) is an integer multiple of \(1/D\).
Implement each row allocation using only comparisons, subtraction, and the minimum operation. Every residual amount and matrix entry remains an integer multiple of \(1/D\). Residual numerators are bounded by \(kD\), and row-entry numerators by \(D\), so their bit lengths are \(O(L+\log k)\).
To find a minimum eligible radius efficiently, pre-sort the types by distance from every center. For each row and each center, scan that ordering until the cumulative residual amount reaches one. If it never does, the center has no eligible radius. Otherwise, the distance at which the threshold is first reached is that center’s minimum eligible radius, including all ties at that distance. Take the smallest radius over the centers.
This requires \(O(\tau^2)\) arithmetic operations per row after sorting. Sorting, constructing \(k\) rows, and comparing rational distances all take polynomial bit time.
The cumulative sums and output probabilities also have denominator \(D\), with numerators bounded by \(D\). There are at most \(k(\tau-1)+1\) output panels, each encoded by \(\tau\) counts between zero and \(k\). Thus the explicit output has polynomial bit length.
No population expansion is performed. Since \(m=\tau\) and \(k\) is unary encoded, the entire construction runs in polynomial time in the requested parameters.
⟨structured verdict parsed — rendered above⟩
The argument is correct and resolves the construction problem in polynomial time. It also establishes the stronger claim that the same distribution satisfies the condition simultaneously for every \(1\le q\le k\). I found no major or minor mathematical issues.
Before constructing row \(j\), the total residual amount is \(k-j+1\), which is at least one. Because \(T\) is finite, a sufficiently large ball around any center contains all types and is eligible. The minimum eligible radius is attained among the finitely many input distances.
An eligible ball contains enough residual amount to construct a row of total weight one by the stated greedy procedure. Each allocation preserves nonnegativity and removes exactly one unit. After \(k\) rows, the residual total is zero; nonnegativity then implies that every residual coordinate is zero. Thus both asserted matrix identities hold:
\[
\sum_t X_{j,t}=1,\qquad \sum_j X_{j,t}=k\mu_t.
\]
The support implication \(X_{j,t}>0\Rightarrow d(v_j,t)\le\rho_j\) follows directly from the allocation rule.
The monotonicity of the radii is also justified: decreasing residual amounts cannot make a previously ineligible ball eligible.
Since the radii are nondecreasing, the rows with radius at most \(R\) form a prefix, possibly empty or containing every row.
Immediately after that prefix, the residual amount in \(B(a,R)\) is strictly less than one. If all rows are complete, this follows from exhaustion. Otherwise, an amount of at least one would make a radius at most \(R\) eligible and contradict the next selected radius. This reasoning remains valid when \(R\) is not an input distance.
If only \(h\le q-1\) rows in the prefix touch \(C\), those rows remove at most \(h\) units from \(C\). Consequently,
\[
\sum_{t\in C}y_t
\ge k\sum_{t\in C}\mu_t-h
\ge q-h
\ge1.
\]
The inclusion \(C\subseteq B(a,R)\) contradicts the strict residual bound. The lemma is fully established, including its boundary case \(k\sum_{t\in C}\mu_t=q\).
Every row’s cumulative sums are nondecreasing, start at zero, and end at one. For each breakpoint \(a_{\ell-1}<1\), exactly one positive-length row interval contains it under the stated half-open convention. Repeated cumulative sums therefore cause no ambiguity.
Since all cumulative sums are global breakpoints, the row assignments remain constant throughout each interval. Its positive length is a valid probability, and the interval lengths sum to one.
For row \(j\) and type \(t\), the total probability of assigning \(t\) to that row is precisely \(X_{j,t}\). Summing over rows gives the required equality
\[
\mathbb E_\lambda[p_t]=k\mu_t.
\]
The bound of \(k(\tau-1)+1\) intervals is correct. Merging identical panels preserves probabilities, expectations, and the existence of a generating row assignment. Every selected type has positive allocation in its row.
Under the assumed violation, \(S\) has mass at least \(r/k>0\), so it is nonempty. Each set \(Q_t\) exists because \(p'\) has \(r\ge q\) occurrences. Every occurrence in \(Q_t\) lies at distance at most \(c_q(t,p')\), including when distances tie.
Each group contains its anchor, so the grouping process partitions \(S\) into a positive number \(h\) of nonempty groups. The anchor occurrence sets are pairwise disjoint: an anchor sharing an occurrence with a previously selected anchor would have been removed in that earlier group. Therefore \(hq\le r\).
The mass bound for some group follows correctly:
\[
\sum_{t\in C}\mu_t
\ge \frac{\sum_{t\in S}\mu_t}{h}
\ge \frac{r}{kh}
\ge \frac qk.
\]
When its anchor \(a\) was chosen, every member of \(C\) was still available. The maximizing rule thus gives \(c_q(t,p')\le A\), where \(A=c_q(a,p')\). A shared occurrence and the triangle inequality yield \(d(a,t)\le2A\). Hence the two hypotheses needed for the allocation lemma are satisfied.
The lemma supplies \(q\) distinct rows of radius at most \(2A\), each touching \(C\). For each such row, both its selected representative type \(s_j\) and its witness type \(t_j\in C\) lie in its allocation ball. The displayed estimate is valid:
\[
d(a,s_j)
\le d(a,t_j)+d(t_j,v_j)+d(v_j,s_j)
\le2A+2\rho_j
\le6A.
\]
Distinct rows correspond to distinct representative occurrences, even when their types coincide. Thus the estimate supplies the \(q\) occurrences required to conclude \(c_q(a,p)\le6A\).
Since the anchor belongs to \(S\), this contradicts its defining strict inequality. Starting from \(V_{\mu,q}(p,p',6)\ge r/k\) therefore proves the required strict conclusion \(V_{\mu,q}(p,p',6)<r/k\).
No division by \(A\) occurs, so \(A=0\) is covered.
The construction is independent of \(q\). The correctness argument applies to every supported panel, every integer \(1\le q\le k\), and every typed alternative of each permitted size \(q\le r\le k\). This establishes the simultaneous claim.
Unlimited repetition is used consistently in both the distribution construction and occurrence counting. The cases \(\tau=1\), \(k=1\), \(q=k\), and equality at the blocking threshold require no exceptions to the argument.
The common denominator \(D=\prod_t B_t\) has binary length \(O(L)\). All residual amounts, matrix entries, cumulative sums, and probabilities remain multiples of \(1/D\). The stated numerator bounds give polynomial bit lengths.
Sorting distances around each center and scanning the resulting order finds the minimum eligible radius correctly. Ties do not invalidate the scan: when the threshold is reached, the closed ball at that distance contains every scanned type and all remaining tied types.
The allocation uses \(O(k\tau^2)\) arithmetic operations after sorting, on numbers of polynomial bit length. Breakpoint sorting, panel construction, and merging are likewise polynomial. The explicit support bound and count encodings establish polynomial output length.
The cited FairGreedyCapture work supplies motivation only; the write-up invokes no external theorem whose hypotheses or conclusion remain unverified.
No additional clarification or repair is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.