Answer: The decision problem is in \(\mathrm{P}\). A minimizing deterministic winner and its exact worst-case distortion are polynomial-time computable. For every fixed \(\Theta\), \(\sup_\mu V(\Theta,\mu)=D_\Theta\); mass admissibility guarantees this bound, and the displayed weighted rule satisfies admissibility and attains the bound globally.
Theorem 25 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateWeighted Majority Rule \ref{rule_general} satisfies Condition \ref{cond_general}, and therefore achieves the optimal distortion for two candidates with preference strength information.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given two candidates \(P,Q\), thresholds \(1\leq\tau_1<\cdots<\tau_m\), and rational masses \(\mu(A_l),\mu(B_l),\mu(U)\), choose a deterministic winner using only those masses and determine the minimum worst-case distortion over all metric-consistent latent completions, including whether the mass version of Condition 18 and Weighted Majority Rule 4 achieves \(D_\Theta\).
Let \(\Theta=(\tau_1,\ldots,\tau_m)\), with \(m\geq1\) and finite binary rational thresholds \(1\leq\tau_1<\cdots<\tau_m\), and let \(P,Q\) be distinct candidates.
A society is given by its support: the list of the \(\tau\) reported types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Masses sum to \(1\); absent types have mass zero. Let \(L\) be the total input bit length, and state running times in \(m,\tau,L\) and any additional input parameters.
A latent completion places an atomless population in an arbitrary metric space with \(P,Q\), allowing different locations within each reported type and coincident locations for different voters; candidate distances are measurable and integrable. A voter reports a preferred candidate consistent with weak distance preference, resolving equal distances to either candidate, and has strength \(s\) equal to distance to the other candidate divided by distance to the preferred candidate, with \(s=\infty\) when the latter distance is zero.
Type \(A_l\) reports \(P\) and \(\tau_l\leq s<\tau_{l+1}\); type \(B_l\) reports \(Q\) with the same interval. The last interval has no upper bound. Type \(U\) has \(s<\tau_1\) and reveals no preferred candidate; necessarily \(\mu(U)=0\) when \(\tau_1=1\). Write \(a_l=\mu(A_l)\), \(b_l=\mu(B_l)\).
For a completion \(K\), define \(SC_K(X)=\int d(v,X)\,d\mu(v)\), \(R_X(\Theta,\mu)=\sup_K SC_K(X)/\min\{SC_K(P),SC_K(Q)\}\), and \(V(\Theta,\mu)=\min_{X\in\{P,Q\}}R_X(\Theta,\mu)\). A zero denominator gives ratio \(1\) if the selected cost is zero and \(\infty\) otherwise.
Define \(D_\Theta=\max\bigl(\{\tau_1,(\tau_m+2)/\tau_m\}\cup\{(\tau_l\tau_{l+1}+2\tau_{l+1}-1)/(\tau_l\tau_{l+1}+1):1\leq l<m\}\bigr)\), and choose \(k\) with \(\tau_k\leq D_\Theta<\tau_{k+1}\), taking \(\tau_{m+1}=\infty\).
Put \(c_l=(D_\Theta\tau_l-1)/(\tau_l+1)\). Put \(h_l=(\tau_{l+1}-D_\Theta)/(\tau_{l+1}+1)\) for \(l<k\), \(h_l=(\tau_{l+1}-D_\Theta)/(\tau_{l+1}-1)\) for \(k\leq l<m\), and \(h_m=1\). The mass admissibility condition permits \(P\) only if \(\sum_l c_la_l\geq\sum_l h_lb_l\), and permits \(Q\) only if \(\sum_l c_lb_l\geq\sum_l h_la_l\).
The weighted rule assigns weight \(c_l+h_l\) to types \(A_l,B_l\), weight zero to \(U\), and selects \(P\) iff \(\sum_l(c_l+h_l)a_l\geq\sum_l(c_l+h_l)b_l\), breaking score ties toward \(P\).
Is deciding \(V(\Theta,\mu)\leq r\), for an input binary rational \(r\geq1\), in \(\mathrm{P}\) or \(\mathrm{NP}\)-hard, and can a minimizing deterministic winner and its worst-case distortion be computed in polynomial time?
For each fixed \(\Theta\), is \(\sup_\mu V(\Theta,\mu)=D_\Theta\), do rules satisfying the mass admissibility condition guarantee this bound, and does the displayed weighted rule satisfy that condition and attain the bound?
For finite electorates, the displayed weighted rule satisfies the displayed admissibility condition and achieves the optimal global distortion \(D_\Theta\); its rational weighted scores can be evaluated in polynomial time. [Abramowitz, Anshelevich, and Zhu](https://arxiv.org/pdf/1906.10562)
No prior result settling precisely this mass-completion problem was located in the literature search.
The decision problem is in \(\mathrm{P}\). A minimizing deterministic winner and its exact worst-case distortion can be computed in polynomial time.
For every fixed \(\Theta\),
\[ \sup_\mu V(\Theta,\mu)=D_\Theta. \]
Every rule satisfying the mass admissibility condition guarantees distortion at most \(D_\Theta\). The displayed weighted rule satisfies that condition, including its prescribed tie-breaking, and its global worst-case distortion is exactly \(D_\Theta\).
The finite-electorate counterpart appears in [Abramowitz, Anshelevich, and Zhu, Condition 18 and Theorem 19](https://arxiv.org/pdf/1906.10562). We prove the mass-completion statements directly below.
Because \(P,Q\) are distinct points of a metric space, their distance is positive. Rescaling each completion preserves types and distortion, so we normalize \(d(P,Q)=1\).
Write \(x=d(v,P)\) and \(y=d(v,Q)\). The triangle inequalities imply
\[ x,y\geq0,\qquad x+y\geq1,\qquad |x-y|\leq1. \]
For \(r\geq1\), define
\[ C_t(r)=\frac{rt-1}{t+1}, \]
and, for finite \(u>1\),
\[ H_u(r)= \begin{cases} \dfrac{u-r}{u-1},&1\leq r<u,\\[4pt] \dfrac{u-r}{u+1},&r\geq u. \end{cases} \qquad H_\infty(r)=1. \]
At \(r=u\), both expressions give zero.
We first establish the following exact one-voter suprema:
| Reported type | Supremum of \(x-ry\) |
|---|---|
| \(A_l\) | \(-C_{\tau_l}(r)\) |
| \(B_l\) | \(H_{\tau_{l+1}}(r)\) |
| \(U\), when \(\tau_1>1\) | \(H_{\tau_1}(r)\) |
Here and below \(\tau_{m+1}=\infty\).
Suppose \(x>0\), and put \(s=y/x\). For type \(A_l\), \(s\geq t=\tau_l\). Since \(x+y\geq1\),
\[ x\geq\frac1{s+1}. \]
The coefficient \(1-rs\) is nonpositive, so
\[ x-ry=x(1-rs) \leq\frac{1-rs}{s+1} \leq\frac{1-rt}{t+1}. \]
The last inequality follows because the derivative of \((1-rs)/(s+1)\) is \(-(r+1)/(s+1)^2<0\).
Equality is attained on the real line with \(P=0,Q=1\), at voter location \(1/(t+1)\). Its strength is exactly \(t\), which belongs to the reported interval.
The remaining possibility is \(x=0\). Then the triangle inequalities force \(y=1\), and the voter can belong only to \(A_m\). Its objective value is \(-r\), which is smaller than \(-C_t(r)\). Thus the stated supremum holds for every \(A_l\).
When \(y>0\), put \(s=x/y\). The triangle inequalities give
\[ y\geq\frac1{s+1}, \qquad y\leq\frac1{s-1}\quad\text{when }s>1. \]
Consequently,
\[ x-ry=y(s-r)\leq g_r(s), \]
where
\[ g_r(s)= \begin{cases} \dfrac{s-r}{s+1},&0<s\leq r,\\[4pt] \dfrac{s-r}{s-1},&s>r. \end{cases} \]
This function is nondecreasing. Its derivatives on the two branches are respectively
\[ \frac{r+1}{(s+1)^2}>0, \qquad \frac{r-1}{(s-1)^2}\geq0. \]
For \(r>1\), the branches meet at zero. For \(r=1\), there is an upward jump from \(g_1(1)=0\) to \(g_1(s)=1\) for \(s>1\), which also preserves monotonicity.
For \(B_l\) with finite upper endpoint \(u=\tau_{l+1}\), taking \(s\uparrow u\) therefore gives the upper bound \(H_u(r)\). This bound is approached by actual voters on the real line:
In both cases choose \(s\in[\tau_l,u)\). Thus the strict upper endpoint causes no discrepancy between the stated supremum and the allowed completions.
For \(B_m\),
\[ x-ry=(x-y)-(r-1)y\leq1. \]
The value \(1\) is attained at \(Q\), where \(x=1,y=0\) and strength is infinite.
When \(\tau_1>1\), a voter is of type \(U\) exactly when both distances are positive and
\[ \frac1{\tau_1}<\frac{x}{y}<\tau_1. \]
The same bound using \(g_r(x/y)\), together with locations of strength \(s\uparrow\tau_1\), proves that the supremum is \(H_{\tau_1}(r)\).
When \(\tau_1=1\), type \(U\) is absent by the hypotheses.
Put \(\sigma=\mu(U)\), and define
\[ \Phi_P(r)= -\sum_{l=1}^m a_l C_{\tau_l}(r) +\sum_{l=1}^m b_l H_{\tau_{l+1}}(r) +\sigma H_{\tau_1}(r), \]
where the last term is omitted when \(\tau_1=1\). Define \(\Phi_Q(r)\) by exchanging all \(a_l,b_l\).
The one-voter bounds imply that every normalized completion satisfies
\[ SC_K(P)-rSC_K(Q)\leq\Phi_P(r). \]
This bound is also the exact supremum. To see this, use the real-line locations from Section 2, choosing an arbitrarily close approximation to the supremum for each supported type. Partition the atomless probability space \([0,1]\), with Lebesgue measure, into intervals of the prescribed masses, and map each interval to its chosen voter location.
These are valid atomless-population completions: coincident locations are explicitly allowed, and candidate distances are measurable and integrable. There are only finitely many locations. Since the masses sum to one, approximating every one-voter supremum within \(\varepsilon\) approximates their weighted sum within \(\varepsilon\). Hence
\[ \sup_K\bigl(SC_K(P)-rSC_K(Q)\bigr)=\Phi_P(r), \]
with the supremum taken over normalized completions. Reflection gives the corresponding identity for \(Q\).
For every completion,
\[ SC_K(P)+SC_K(Q)\geq1. \]
Thus both costs cannot vanish. For finite \(r\geq1\), the ratio convention in the question gives the exact equivalence
\[ \frac{SC_K(P)}{\min\{SC_K(P),SC_K(Q)\}}\leq r \quad\Longleftrightarrow\quad SC_K(P)\leq rSC_K(Q). \]
Indeed, if \(P\) has the smaller cost its ratio is one; if \(Q\) has the smaller positive cost, the equivalence is ordinary division; and if \(SC_K(Q)=0\), the selected cost is positive and both conditions fail.
It follows that
\[ R_P(\Theta,\mu)\leq r \quad\Longleftrightarrow\quad \Phi_P(r)\leq0, \]
and symmetrically for \(Q\). Therefore
\[ V(\Theta,\mu)\leq r \quad\Longleftrightarrow\quad \Phi_P(r)\leq0\ \text{or}\ \Phi_Q(r)\leq0. \]
This already gives an exact polynomial-time decision procedure.
Each \(\Phi_X\) is continuous and piecewise affine on \([1,\infty)\). Its breakpoints belong to the input threshold list.
For \(P\), every supported type except \(B_m\) contributes a strictly negative slope on every affine piece. Specifically, the slope magnitudes are
\[ \frac{\tau_l}{\tau_l+1} \quad\text{for }A_l, \qquad \frac1{\tau_{l+1}-1}\ \text{or}\ \frac1{\tau_{l+1}+1} \quad\text{for finite-upper-endpoint }B_l, \]
with the analogous expressions for \(U\). Type \(B_m\) contributes the constant \(1\).
Consequently:
On each affine interval, write
\[ \Phi_P(r)=\alpha-\beta r. \]
When \(b_m<1\), \(\beta>0\), and its candidate root is the rational number \(\alpha/\beta\). Enumerating the at most \(m+1\) intervals and checking which contains this candidate computes \(R_P\) exactly. Apply the same procedure to \(Q\); its exceptional infinite case is \(a_m=1\).
The two infinite cases cannot occur simultaneously. Thus \(V\) is always a finite rational. Comparing the computed candidate risks and returning a candidate with smaller risk gives a minimizing deterministic winner.
Only supported types need to be scanned. The decision procedure uses \(O(m+\tau+1)\) rational operations, including preprocessing. Computing both exact risks by interval enumeration uses
\[ O\bigl((m+1)(\tau+1)\bigr) \]
rational operations.
All arithmetic can be performed with polynomially bounded encodings; in fact \(O(L)\) bits suffice. To verify this, write a threshold as \(p/q\). The affine coefficients involve only mass rationals and factors such as
\[ \frac{p}{p+q},\qquad \frac{q}{p+q},\qquad \frac{p}{p-q},\qquad \frac{q}{p-q}. \]
In a coefficient sum, each input mass occurs once, and each threshold supplies only a constant number of denominator factors. Their product has \(O(L)\) bits, so the reduced sums, roots, and comparison operands do as well.
Using elementary exact rational arithmetic, conservative bit-operation bounds are therefore
\[ O\bigl((m+\tau+1)L^3\bigr) \]
for decision, and
\[ O\bigl((m+1)(\tau+1)L^3\bigr) \]
for computing a minimizing winner and its exact distortion. For decision, \(L\) includes the encoding of \(r\). There is no dependence on the number of possible voters or on a common denominator interpreted as an electorate size.
Write \(D=D_\Theta\). By definition \(D\geq\tau_1\), and \(D>1\) because \((\tau_m+2)/\tau_m>1\).
The coefficients in the question are precisely
\[ c_l=C_{\tau_l}(D), \qquad h_l=H_{\tau_{l+1}}(D). \]
Indeed, when \(l<k\), \(\tau_{l+1}\leq D\), giving the denominator \(\tau_{l+1}+1\); when \(k\leq l<m\), \(\tau_{l+1}>D\), giving the denominator \(\tau_{l+1}-1\). The last coefficient is \(H_\infty(D)=1\).
Define
\[ F_P=\sum_l c_l a_l-\sum_l h_l b_l, \qquad F_Q=\sum_l c_l b_l-\sum_l h_l a_l. \]
The displayed admissibility condition permits exactly the candidates whose corresponding \(F_X\) is nonnegative.
Because \(D\geq\tau_1\), the unreported contribution satisfies \(H_{\tau_1}(D)\leq0\) whenever it is present. Thus
\[ \Phi_P(D)=-F_P+\sigma H_{\tau_1}(D)\leq-F_P. \]
If \(P\) is permitted, \(\Phi_P(D)\leq0\), hence \(R_P\leq D\). The identical argument proves \(R_Q\leq D\) whenever \(Q\) is permitted.
Every rule satisfying the mass admissibility condition therefore guarantees distortion at most \(D_\Theta\).
We first prove
\[ c_l\geq h_l\qquad\text{for every }l. \]
For \(l<m\), put \(t=\tau_l\) and \(u=\tau_{l+1}\). If \(D\geq u\), then \(C_t(D)>0\) and \(H_u(D)\leq0\), so the inequality holds.
If \(D<u\), direct subtraction gives
\[ C_t(D)-H_u(D) = \frac{(tu+1)D-(tu+2u-1)}{(t+1)(u-1)}. \]
The denominator is positive, and the numerator is nonnegative because
\[ D\geq\frac{tu+2u-1}{tu+1}. \]
For the last interval,
\[ c_m-h_m = \frac{D\tau_m-\tau_m-2}{\tau_m+1} \geq0 \]
by the tail term in the definition of \(D\).
Now let \(W\) be the weighted score difference:
\[ W=\sum_l(c_l+h_l)(a_l-b_l). \]
The two admissibility quantities satisfy
\[ F_P-F_Q=W, \qquad F_P+F_Q=\sum_l(c_l-h_l)(a_l+b_l)\geq0. \]
If \(W\geq0\), including a score tie, then
\[ F_P=\frac{(F_P+F_Q)+W}{2}\geq0. \]
Thus the prescribed choice of \(P\) is permitted. If \(W<0\), then
\[ F_Q=\frac{(F_P+F_Q)-W}{2}>0, \]
so the prescribed choice of \(Q\) is permitted.
This also proves that at least one candidate is always admissible.
The weights are positive. When \(D<u\), this follows from \(c_l>0\) and \(h_l>0\). When \(D\geq u\),
\[ c_l+h_l = \frac{(D+1)(tu-1)}{(t+1)(u+1)}>0. \]
The last weight is \(c_m+1>0\). Computing \(D\), the coefficients, and the support-weighted scores takes \(O(m+\tau+1)\) rational operations and polynomial bit time.
We exhibit rational-mass profiles for every potentially maximal term defining \(D_\Theta\). Each construction uses an atomless population mapped to finitely many locations on the real line.
Suppose \(\tau_1>1\), and let all mass be of type \(U\).
For any \(1\leq s<\tau_1\), put every voter at \(s/(s+1)\), with \(P=0,Q=1\). Then
\[ \frac{SC(P)}{SC(Q)}=s. \]
Reflection gives the reverse ratio for the same reported profile. Hence both candidate risks are at least \(\tau_1\).
Conversely, every unreported voter satisfies \(x<\tau_1y\) and \(y<\tau_1x\). Integration gives both candidate risks at most \(\tau_1\). Therefore
\[ V(\Theta,\mu)=\tau_1. \]
When \(\tau_1=1\), this profile is unavailable, but its term cannot determine \(D_\Theta\), since \(D_\Theta>1\).
Fix \(l<m\), put \(t=\tau_l,u=\tau_{l+1}\), and take
\[ a_l=b_l=\frac12, \]
with all other masses zero.
Choose \(s\in[t,u)\) with \(s>1\). Put the \(A_l\) population at \(1/(t+1)\), and the \(B_l\) population at \(s/(s-1)\). These strengths are respectively \(t\) and \(s\). Their social-cost ratio is
\[ \frac{SC(P)}{SC(Q)} = \frac{\frac1{t+1}+\frac{s}{s-1}} {\frac{t}{t+1}+\frac1{s-1}} = \frac{ts+2s-1}{ts+1}. \]
Letting \(s\uparrow u\) shows that \(R_P\) is at least
\[ d_l=\frac{tu+2u-1}{tu+1}. \]
Reflection preserves the reported masses, so \(R_Q\geq d_l\) as well.
We can also identify these risks exactly. The calculations
\[ d_l-1=\frac{2(u-1)}{tu+1}>0, \qquad u-d_l=\frac{(u-1)(tu-1)}{tu+1}>0 \]
show that \(1<d_l<u\). Substituting into the coefficient difference from Section 6 yields
\[ C_t(d_l)=H_u(d_l). \]
Thus \(\Phi_P(d_l)=\Phi_Q(d_l)=0\), and Section 3 gives
\[ R_P=R_Q=V=d_l. \]
The upper strength endpoint need not be attained: the definition uses a supremum.
Put \(t=\tau_m\), and take \(a_m=b_m=1/2\).
Place the \(A_m\) population at \(1/(t+1)\), and the \(B_m\) population at \(Q\). The strengths are \(t\) and infinity, and
\[ \frac{SC(P)}{SC(Q)} = \frac{\frac1{t+1}+1}{\frac{t}{t+1}} = \frac{t+2}{t}. \]
Reflection again preserves the profile. At \(r=(t+2)/t\), we have \(C_t(r)=H_\infty(r)=1\), so both \(\Phi\)-tests equal zero. Hence
\[ R_P=R_Q=V=\frac{\tau_m+2}{\tau_m}. \]
Sections 5–6 provide a permitted weighted-rule winner of risk at most \(D_\Theta\) for every society. Therefore
\[ V(\Theta,\mu)\leq D_\Theta \qquad\text{for every valid }\mu. \]
Section 7 gives a rational-mass society attaining each relevant term in the finite maximum defining \(D_\Theta\). Choosing a society corresponding to a maximal term proves the stronger statement
\[ \max_{\mu\text{ valid rational masses}}V(\Theta,\mu)=D_\Theta. \]
On that society every deterministic choice has worst-case distortion at least \(D_\Theta\). Consequently the displayed weighted rule, and every everywhere-defined rule satisfying the mass admissibility condition, has global worst-case distortion exactly \(D_\Theta\).
⟨structured verdict parsed — rendered above⟩
The prover’s output resolves all parts of the task. The argument is correct and rigorous as written; I found no major or minor mathematical issues requiring repair.
Normalizing \(d(P,Q)=1\) is valid because distinct candidates have positive distance, and scaling preserves preference strengths, reported types, integrability, and distortion.
The inequalities
\(x+y\geq1\) and \(|x-y|\leq1\)
follow from the triangle inequalities. The proof uses these as necessary constraints and supplies actual real-line realizations for its extremal constructions. It therefore does not rely on an unstated realization theorem.
Types \(A_l\). The sign of \(1-rs\) is correctly handled: \(r\geq1\) and \(s\geq\tau_l\geq1\) imply that this coefficient is nonpositive. Consequently, multiplying the lower bound on \(x\) reverses the relevant inequality exactly as written. The derivative calculation is correct, and the location \(1/(\tau_l+1)\) realizes the claimed supremum.
When \(\tau_l=1\), this location has equal candidate distances, and reporting \(P\) is allowed by the task’s tie convention. The separate case \(x=0\) is correctly restricted to \(A_m\), and its value \(-r\) is strictly below the stated supremum.
Types \(B_l\). Both bounds on \(y\) follow from the normalized triangle inequalities. The proof selects the appropriate bound according to the sign of \(s-r\). Both derivative calculations are correct. The exceptional behavior at \(r=1\) is explicitly addressed: the upward jump at \(s=1\) preserves monotonicity.
For finite upper endpoints, the locations supplied have the stated strengths and objective values. Taking \(s\uparrow\tau_{l+1}\) respects the strict endpoint and proves a supremum rather than falsely claiming attainment. For \(B_m\), the upper bound \(1\) is valid and attained at \(Q\).
Type \(U\). The characterization
\(1/\tau_1<x/y<\tau_1\)
correctly includes both possible weak preferences. Zero candidate distance would give infinite strength and therefore cannot occur in \(U\). The same optimization applies on this domain, and the supplied locations approach the claimed supremum. The case \(\tau_1=1\) is correctly omitted.
Integrating the pointwise bounds is justified by the assumed measurability and integrability.
The reverse inequality for the supremum is also established. There are finitely many supported types, each can be approximated at a real-line location, and all such locations coexist with the same normalized candidates. Partitioning an atomless population into the prescribed masses is valid. Mapping several voters to the same location is expressly permitted by the task.
The error estimate is correct: approximating each supported one-voter supremum within \(\varepsilon\) produces total error at most \(\varepsilon\), because the masses sum to one. Thus the identities involving \(\Phi_P\) and \(\Phi_Q\) are exact.
The inequality
\(SC_K(P)+SC_K(Q)\geq1\)
excludes simultaneous zero costs.
For finite \(r\geq1\), the claimed equivalence between the distortion bound and
\(SC_K(P)\leq rSC_K(Q)\)
correctly handles all possibilities:
Taking the supremum therefore yields exactly the stated \(\Phi\)-tests. In particular, the proof correctly uses a nonpositive supremum; it does not require attainment of the extremal completion.
The continuity and piecewise affine structure follow from the displayed formulas for \(C_t\) and \(H_u\). At a finite breakpoint \(r=u\), both branches of \(H_u\) equal zero.
The slope claims are correct. Every positive-mass contribution other than \(B_m\) has strictly negative slope for \(\Phi_P\). Accordingly:
The symmetric statements for \(Q\) are valid. The two infinite cases cannot coexist because the masses sum to one. Hence the minimum risk is always finite and rational.
Enumerating the affine intervals and testing their rational roots is sufficient. Roots at shared endpoints cause no ambiguity because the function is continuous.
The operation counts correctly depend on the support size, not an expanded electorate:
\(O(m+\tau+1)\) rational operations for decision and
\(O((m+1)(\tau+1))\) for exact optimization.
The encoding argument is adequate. In reduced coefficient sums, mass denominators and the finitely many threshold-derived denominator factors admit a common denominator of \(O(L)\) bits. Numerators, roots, and comparisons likewise retain \(O(L)\)-bit encodings. With elementary exact rational arithmetic, the displayed conservative bit bounds
\(O((m+\tau+1)L^3)\) and
\(O((m+1)(\tau+1)L^3)\)
are justified. The proof explicitly includes the encoding of \(r\) in \(L\) for decision.
The identification
\(c_l=C_{\tau_l}(D_\Theta)\) and
\(h_l=H_{\tau_{l+1}}(D_\Theta)\)
is correct, including thresholds equal to \(D_\Theta\) and the last interval.
Since \(D_\Theta\geq\tau_1\), the \(U\)-contribution is nonpositive. Thus admissibility implies the corresponding \(\Phi\)-test is nonpositive and guarantees risk at most \(D_\Theta\). The proof correctly treats admissibility as a sufficient condition; it does not claim it is necessary for that risk bound.
I checked the subtraction formula for \(c_l-h_l\). Its numerator, denominator, and sign are correct. The last-interval calculation is also correct. Consequently,
\(F_P+F_Q\geq0\).
The identity \(F_P-F_Q=W\) then proves admissibility of the selected candidate. In particular, when \(W=0\), \(F_P\geq0\), so the specified tie-breaking toward \(P\) is covered.
The positivity calculations for the weights are correct, including when some \(h_l\) are negative. Computing the coefficients and rational scores requires polynomial bit time.
Unreported term. The all-\(U\) profile is valid when \(\tau_1>1\). Its supplied completions approach ratio \(\tau_1\), and reflection leaves the reported profile unchanged. The pointwise inequalities give the matching upper bound. When \(\tau_1=1\), this unavailable construction is unnecessary because \(D_\Theta>1\).
Finite-interval terms. The symmetric profile \(a_l=b_l=1/2\) has valid rational masses. Both locations have the claimed types, including when \(\tau_l=1\). The social-cost ratio simplifies correctly to
\((ts+2s-1)/(ts+1)\).
Both calculations establishing \(1<d_l<u\) are correct. Their strict signs hold because \(u>t\geq1\). Substitution into the coefficient difference gives
\(C_t(d_l)=H_u(d_l)\), so the exact distortion tests provide the matching upper bound. The limiting construction provides the lower bound for both candidates.
Last interval. The location at \(Q\) has infinite strength and is permitted in \(B_m\). The ratio calculation gives \((t+2)/t\), and the corresponding coefficient equality is correct. Reflection preserves the symmetric reported masses.
Thus every relevant term in the defining maximum has a valid rational-mass profile with exactly that value of \(V\).
The weighted rule provides the universal upper bound. Selecting a profile corresponding to a maximal term gives the matching lower bound for every deterministic choice. This establishes the claimed maximum over rational-mass societies, and therefore the requested supremum.
The final assertion about every everywhere-defined admissible rule follows: admissibility supplies its upper bound, while the maximal-term profile supplies its lower bound regardless of its selected candidate.
The literature attribution is consistent with [Condition 18 and Theorem 19 of the cited paper](https://arxiv.org/pdf/1906.10562). The mass-completion proof is independent of that finite-electorate result, so no transfer theorem or unverified hypothesis is needed.
No corrective feedback is necessary. All requested conclusions are established, including exact polynomial-time computation and sharpness for each fixed threshold list.
⟨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.