Answer: —
Theorem 5.8 — class: algorithmic
For 𝜏= 1 𝑚, let 𝑐1 and 𝑐2 be the two candidates with highest number of approvals, then the randomized rule 𝑓 that (1) with probability 1/2, selects (𝑐1,𝑐2) as finalists, (2) and with probability 1/2, selects the pair (𝑐1,𝑐′) with a random candidate 𝑐′ ∈𝐶\ {𝑐1,𝑐2} as finalists, achieves a distortion of at most 4𝑚. We conclude by noting the optimal distortion attainable using randomized rules in approval voting with majority runoff.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), threshold \(\tau=1/m\), and a rational finite-support society \(\mu\in\Delta(T)\) whose types specify unit-sum utilities, approval sets, and consistent rankings, compute the winner distribution of the Theorem 5.8 randomized majority-runoff rule and establish its worst-case mean-welfare distortion over all such societies.
Let \(m=|C|\ge 3\) and \(\tau=1/m\). A type \(t\in T\) consists of unit-sum utilities \(u_t:C\to\mathbb{Q}_{\ge 0}\) and a strict ranking \(\succ_t\) consistent with \(u_t\). Its rational mass is \(\mu_t\), with \(\sum_t \mu_t=1\). Type \(t\) approves \(c\) iff \(u_t(c)\ge \tau\).
The approval score of \(c\) is \(A(c)=\sum_{t: c \text{ approved by } t} \mu_t\). Let \(c_1, c_2\) be the two highest-scoring candidates, breaking ties by a fixed candidate order. With probability \(1/2\) use finalists \(\{c_1, c_2\}\); with probability \(1/2\) use \(\{c_1, c'\}\), where \(c'\) is uniform in \(C\setminus\{c_1, c_2\}\). In each runoff, elect the finalist preferred by greater total mass; resolve an exact tie by the fixed order. For outcome distribution \(x\), define \(SW(c)=\sum_t \mu_t u_t(c)\), \(SW(x)=\sum_c x(c)SW(c)\), and distortion \(\max_c SW(c)/SW(x)\).
Target: Is evaluating this continuous approval-majority-runoff rule and determining its worst-case mean-welfare distortion over finite rational type societies solvable in polynomial time, or is it NP-hard?
Known discrete result: for finite voter profiles at \(\tau=1/m\), this randomized finalist-selection rule has distortion at most \(4m\) (Theorem 5.8 of Ebadian, Latifian, and Shah, 2023).
For an explicitly listed finite rational type society, both the outcome distribution and its distortion are exactly computable in polynomial time. Thus the natural instance-evaluation problem is in $\mathrm{FP}$, and its threshold decision version is in $\mathrm{P}$.
For the universal worst-case distortion, let
$$ D_m=\sup_{\mathcal S} \frac{\max_{c\in C}\operatorname{SW}_{\mathcal S}(c)} {\operatorname{SW}_{\mathcal S}(x_{\mathcal S})}, $$
where the supremum ranges over all finite rational type societies with $m$ candidates. Then
$$ m-1\le D_m\le 4m. $$
Consequently, $D_m=\Theta(m)$. The upper bound follows exactly, not approximately, from the cited discrete theorem. The exact value of $D_m$ is not determined by the available argument.
Let $N=|T|$, and let $L$ be the total binary encoding length of the candidate list, utilities, rankings, and rational masses.
For each candidate $c$, compute
$$ A(c)=\sum_{t\in T}\mu_t\mathbf 1[u_t(c)\ge 1/m]. $$
Sorting candidates by the pair $(-A(c),\text{fixed-order position of }c)$ determines $c_1,c_2$.
For every $d\ne c_1$, compute the pairwise mass
$$ P(c_1,d)=\sum_{t\in T}\mu_t\mathbf 1[c_1\succ_t d]. $$
Let $w(d)$ denote the winner of the runoff between $c_1$ and $d$: it is $c_1$ when $P(c_1,d)>1/2$, it is $d$ when $P(c_1,d)<1/2$, and an equality is resolved by the fixed order. The outcome distribution is therefore
$$ x(c)= \frac12\mathbf 1[w(c_2)=c] + \frac{1}{2(m-2)} \sum_{d\in C\setminus\{c_1,c_2\}} \mathbf 1[w(d)=c]. $$
Finally compute
$$ S(c)=\sum_{t\in T}\mu_tu_t(c),\qquad W=\sum_{c\in C}x(c)S(c), $$
and return
$$ \operatorname{dist}(\mathcal S)=\frac{\max_{c\in C}S(c)}{W}. $$
These calculations require $O(Nm+m\log m)$ rational arithmetic operations. Exact addition, multiplication, and comparison of the input rationals have polynomial bit complexity: even an unreduced product of all input denominators has bit length at most the sum of their bit lengths, hence $O(L)$.
The denominator $W$ is positive. Indeed, every type approves at least one candidate because its utilities sum to one, so
$$ \sum_{c\in C}A(c)\ge 1 \quad\text{and hence}\quad A(c_1)\ge \frac1m. $$
Thus $S(c_1)\ge A(c_1)/m>0$. If $c_1$ wins the first runoff, that branch already gives positive welfare. If $c_2$ wins and $A(c_2)>0$, then $S(c_2)\ge A(c_2)/m>0$. Finally, if $A(c_2)=0$, every candidate other than $c_1$ has zero approval score. Every type must consequently approve $c_1$, and consistency implies that every type ranks $c_1$ above $c_2$; hence $c_1$ wins that runoff.
Therefore the associated decision problem
$$ \text{“is }\operatorname{dist}(\mathcal S)\ge K\text{?”} $$
for rational $K$ also belongs to $\mathrm P$.
Consider any finite rational type society. Choose a positive integer $Q$ such that
$$ n_t=Q\mu_t $$
is an integer for every $t$. Construct an unweighted finite profile containing $n_t$ identical voters of type $t$.
For every candidate $c$, its discrete approval count is
$$ q(c)=\sum_{t:c\text{ approved by }t}n_t =Q A(c). $$
Thus approval-score comparisons and all approval ties are preserved. Similarly, for every pair $a,b$, the number of voters preferring $a$ to $b$ is
$$ Q\sum_{t:a\succ_t b}\mu_t, $$
so every strict majority and exact pairwise tie is preserved. The two finalist-selection branches and their runoff winners are therefore identical in the mass society and in the expanded profile.
Discrete total welfare satisfies
$$ \operatorname{SW}_{\mathrm{disc}}(c) =\sum_t n_tu_t(c) =Q\operatorname{SW}_{\mathrm{mass}}(c). $$
Hence both the optimal welfare and the outcome welfare are multiplied by $Q$, and the distortion ratio is unchanged.
The expansion may contain exponentially many voters relative to the binary encoding of the masses, so it is not the evaluation algorithm. It is only a transfer argument.
Theorem 5.8 of the cited [AAMAS paper](https://www.ifaamas.org/Proceedings/aamas2023/pdfs/p1752.pdf) applies to the resulting finite profile and gives distortion at most $4m$. Consequently,
$$ D_m\le 4m. $$
We prove $D_m\ge m-1$.
Write the candidates as
$$ C=\{z,d_1,\ldots,d_{m-1}\}, $$
and let
$$ R=\sum_{j=1}^{m-1}j=\frac{m(m-1)}2. $$
Choose sufficiently small positive rational numbers $\epsilon,\delta,\eta$, and put $p=1/2-\epsilon$. There are two types.
The first type has mass $p$ and utilities
$$ u_H(z)=1-\delta,\qquad u_H(d_j)=\frac{\delta j}{R}. $$
Taking $\delta<1/2$ ensures
$$ u_H(d_j)\le \frac{2\delta}{m}<\frac1m, $$
so this type approves only $z$.
The second type has mass $1-p$ and utilities
$$ u_L(z)=0,\qquad u_L(d_j)= \frac{1+\eta j}{(m-1)+\eta R}. $$
For sufficiently small $\eta>0$, every $u_L(d_j)>1/m$. Thus this type approves every $d_j$ and does not approve $z$. All displayed utilities are distinct within each relevant group, so rankings can be chosen strictly in decreasing utility order.
The approval scores are
$$ A(z)=p<\frac12,\qquad A(d_j)=1-p>\frac12. $$
Therefore $c_1,c_2$ are both among the $d_j$. Moreover, if $z$ is ever paired with $c_1$, the mass $1-p>1/2$ strictly prefers $c_1$ to $z$. Hence $z$ never wins, and the rule's outcome is supported entirely on $\{d_1,\ldots,d_{m-1}\}$.
The welfare values are
$$ S(z)=p(1-\delta) $$
and
$$ S(d_j)= p\frac{\delta j}{R} + (1-p)\frac{1+\eta j}{(m-1)+\eta R}. $$
Along any rational sequence with $\epsilon,\delta,\eta\to0^+$,
$$ S(z)\longrightarrow\frac12, \qquad S(d_j)\longrightarrow\frac{1}{2(m-1)} $$
uniformly over $j$. For sufficiently small parameters, $z$ is the welfare-optimal candidate. Since the outcome is a distribution over the $d_j$,
$$ S(x)\longrightarrow\frac{1}{2(m-1)}. $$
It follows that the corresponding distortion converges to $m-1$. Therefore
$$ D_m\ge m-1. $$
Combining the bounds gives
$$ m-1\le D_m\le4m, $$
and hence $D_m=\Theta(m)$.
There are two different questions:
Thus there is no NP-hardness in evaluating the stated rule on an explicit rational type society. What remains unresolved is only the exact universal extremal value, not instance evaluation.
⟨structured verdict parsed — rendered above⟩
The response establishes two genuine results:
However, it does not answer the target’s second complexity question: no polynomial-time algorithm or NP-hardness result is given for determining the universal worst-case distortion. The response itself acknowledges this. The appropriate status is therefore partial.
The approval-score computation is correct. Exact rational comparison determines $c_1,c_2$, including the prescribed fixed-order tie-breaking.
For each possible second finalist $d$, the quantity
$$ P(c_1,d)=\sum_{t:c_1\succ_t d}\mu_t $$
correctly determines the majority winner because the total mass is $1$ and rankings are strict. The displayed formula for $x(c)$ correctly represents both finalist-selection branches.
The welfare calculations and distortion ratio are also correct.
The bit-complexity argument is sufficient in substance. A sum of input-denominator bit lengths is polynomial in the total input length, so exact rational arithmetic does not cause an exponential bit-length blowup. Reduction to lowest terms, if required for the output encoding, is routine polynomial-time arithmetic.
The proof that $W>0$ is valid for positive-mass types:
The sentence “every type must consequently approve $c_1$” is slightly too strong if zero-mass listed types are permitted. Such types do not affect approval scores. This does not affect the conclusion about $W$.
Thus the explicit-instance function problem is in $\mathrm{FP}$, and the stated rational-threshold decision problem is in $\mathrm P$.
The common-denominator expansion is correct. Since $\sum_t\mu_t=1$, the expanded profile contains exactly $Q$ voters. Approval counts satisfy
$$ q(c)=QA(c), $$
so all approval comparisons and ties are preserved. Pairwise counts are likewise multiplied by $Q$, preserving strict majorities and exact ties.
Candidate welfare is multiplied uniformly by $Q$, so the distortion ratio is unchanged.
The cited theorem does state that precisely this randomized finalist-selection rule at $\tau=1/m$ has distortion at most $4m$. The paper also explicitly permits arbitrary resolution of exact majority ties, so the fixed-order convention is compatible with the theorem. See [Theorem 5.8 and the majority-runoff convention](https://www.ifaamas.org/Proceedings/aamas2023/pdfs/p1752.pdf).
Therefore the conclusion $D_m\le4m$ is justified.
The two utility vectors are correctly normalized:
$$ 1-\delta+\sum_{j=1}^{m-1}\frac{\delta j}{R}=1 $$
and
$$ \sum_{j=1}^{m-1}\frac{1+\eta j}{(m-1)+\eta R}=1. $$
For type $H$,
$$ u_H(d_j)\le\frac{2\delta}{m}<\frac1m $$
when $\delta<1/2$, while $u_H(z)>1/m$ for sufficiently small $\delta$. Hence this type approves only $z$.
For type $L$, every $d_j$ exceeds $1/m$ for sufficiently small positive $\eta$, while $z$ is not approved. The strict rankings required by the problem can indeed be chosen consistently because the displayed utilities are distinct.
The approval scores are consequently correct. All $d_j$ have score $1-p>1/2$, while $z$ has score $p<1/2$, so both top-scoring candidates are among the $d_j$.
Whenever $z$ faces $c_1$, the type-$L$ mass $1-p>1/2$ prefers $c_1$ to $z$. Thus $z$ cannot be elected, and every possible winner belongs to $\{d_1,\ldots,d_{m-1}\}$.
The welfare limits are correct and uniform over the finite set of indices $j$. At the limiting values, $z$ has welfare $1/2$, whereas every $d_j$ has welfare $1/(2(m-1))$. Since $m\ge3$, this is a strict gap, so $z$ remains optimal for sufficiently small parameters. Consequently the distortion approaches $m-1$.
Thus $D_m\ge m-1$ and $D_m=\Theta(m)$ are established.
The response does not determine whether computing the universal worst-case distortion is polynomial-time solvable or NP-hard. It supplies only upper and lower bounds and then declares that an exact complexity problem has not been specified.
That observation is reasonable as a warning about the wording, but it does not resolve the target. At minimum, the response would need to select a precise interpretation—such as a threshold language with inputs $m$ and rational $K$—and classify that problem. No such classification is attempted.
The final statement that “there is no NP-hardness” should also be limited to saying that explicit-instance evaluation lies in $\mathrm P$. Membership in $\mathrm P$ does not unconditionally prove non-NP-hardness unless a reduction notion and the usual separation assumption are stated.
⟨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.