Answer: \(\mathrm{NP}\)-hard; nevertheless fixed-parameter tractable in \(\tau\), with bit running time \(2^{O(\tau)}\operatorname{poly}(m,L)\).
Corollary 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere is an FPT algorithm for computing RSD(R)(a) with param- eter T = # of agent types. The running time is O(|R| + mT · 2T).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite alternative set \(A\), a support \(\mathcal T\) of complete weak preference orders, positive binary rational masses \(\mu_t\) summing to \(1\), and a target \(a\in A\), draw an independent exponential clock of rate \(\mu_t\) for each type \(t\). Process types in clock order, replacing the feasible set \(B\) by \(\max_{R_t}(B)\) at each step, then select uniformly from the final feasible set. Compute the exact probability that the selected alternative is \(a\).
Let \(A\) be a nonempty finite set of \(m\) alternatives and let \(a\in A\). A society is given by its support: a list \(\mathcal T\) of \(\tau\) distinct complete weak preference orders \(R_t\), each with positive binary rational mass \(\mu_t\), where \(\sum_{t\in\mathcal T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible orders; let \(L\) be the total input bit length.
Draw one independent exponential clock of rate \(\mu_t\) for each type \(t\). Starting with \(B=A\), process every type once in increasing clock order, replacing \(B\) by its most-preferred elements under \(R_t\). Select uniformly from the final \(B\), including when distinct alternatives are tied by every type. Clock ties have probability zero. Let \(p(a)\) be the resulting selection probability.
Is computing \(p(a)\) exactly polynomial-time solvable in \(m,\tau,L\), or is it NP-hard?
If it is NP-hard, is it nevertheless fixed-parameter tractable with parameter \(\tau\), in time \(f(\tau)\operatorname{poly}(m,L)\)?
For discrete voting RSD, which uniformly orders individual agents, exact probability computation is FPT in the number \(T\) of agent types, with stated running time \(O(nm+mT2^T)\). [Aziz–Mestre](https://arxiv.org/abs/1403.0974)
Discrete exact probability computation is \(\#\mathrm P\)-complete, and comparison with an input rational threshold \(q\in(0,1)\) is NP-hard. [Aziz–Brandt–Brill](https://pub.dss.in.tum.de/brandt-research/rsd.pdf)
No result settling this exact exponential-clock support model was located.
Proven result. Exact computation is \(\mathrm{NP}\)-hard. Nevertheless, it is fixed-parameter tractable in the support size \(\tau\), with bit running time \(2^{O(\tau)}\operatorname{poly}(m,L)\). The proof below handles arbitrary complete weak orders and the stipulated uniform selection from the final surviving set.
1. The exponential ordering law.
Multiplying all clock rates by the same positive constant leaves their ordering distribution unchanged. Thus we may use any positive weights \(w_t\) proportional to the masses. Write \(W(U)=\sum_{t\in U}w_t\).
For independent exponential clocks, after an ordered prefix containing precisely the types in \(S\), the probability that the next type is \(t\notin S\) is
\(\displaystyle \frac{w_t}{W(\mathcal T\setminus S)}.\)
Indeed, among independent clocks with rates \(w_u\), the probability that \(t\) rings first is
\(\displaystyle \int_0^\infty w_t e^{-W(U)x}\,dx=\frac{w_t}{W(U)}.\)
Conditional on that first clock and its time, the residual waiting times of the other clocks remain independent exponentials with their original rates, by memorylessness. Iterating gives the asserted conditional law.
2. A direct hardness reduction.
We reduce from the standard \(\mathrm{NP}\)-complete Set Cover decision problem: given a nonempty universe \(U\), distinct nonempty subsets \(S_1,\ldots,S_n\), and an integer \(1\leq k\leq n\), determine whether at most \(k\) subsets cover \(U\). These restrictions preserve hardness: empty and duplicate subsets can be deleted, the bound can be capped at the remaining number of subsets, and trivial cases can be handled separately.
Set
\(\displaystyle h=\lceil\log_2 n\rceil,\qquad b=1+(k+1)h,\qquad M=2^b.\)
Then \(M\geq 2n^{k+1}>n\).
Construct the alternatives \(A=U\cup\{a\}\). For each subset \(S_i\), introduce a type with the two indifference classes
\(\displaystyle R_i:\quad \{a\}\cup(U\setminus S_i)\ \succ\ S_i.\)
Introduce one additional type, called the blocker, with order
\(\displaystyle R_0:\quad U\ \succ\ \{a\}.\)
Give these types masses
\(\displaystyle \mu_i=\frac1M\quad(1\leq i\leq n),\qquad \mu_0=\frac{M-n}{M}.\)
All masses are positive dyadic rationals and sum to one. The orders are distinct: distinct subsets give distinct top classes, and the blocker's top class excludes \(a\). Thus this is a valid support of size \(\tau=n+1\).
Use the threshold
\(\displaystyle q=M^{-k}\in(0,1).\)
The construction has polynomial bit length. In particular, \(b=O(k\log(n+1))\), and the denominator of \(q\) has \(kb+1\) bits.
By common scaling, the ordering law is that of rates \(1\) for the subset types and rate \(M-n\) for the blocker.
Before the blocker acts, if the processed subset types have indices \(I\), the surviving set is exactly
\(\displaystyle B=\{a\}\cup\left(U\setminus\bigcup_{i\in I}S_i\right).\)
This follows inductively because each subset type retains \(a\) and removes precisely its subset's elements from the current set.
Consequently:
Therefore \(p(a)\) is exactly the probability that the subsets preceding the blocker cover \(U\). The uniform final tie-breaking rule causes no complication: whenever \(a\) survives, the final set is \(\{a\}\).
Suppose first that a cover of size \(r\leq k\) exists. Fix an ordering of those \(r\) subset types. The probability that they occupy the first \(r\) positions, in that order, is
\(\displaystyle \prod_{j=0}^{r-1}\frac1{M-j}\ \geq\ M^{-r}\ \geq\ M^{-k}=q.\)
On this event they eliminate all of \(U\), so \(p(a)\geq q\).
Conversely, suppose no cover of size at most \(k\) exists. Selection of \(a\) requires at least \(k+1\) subset types to precede the blocker. Hence
\(\displaystyle p(a)\leq\prod_{j=0}^{k}\frac{n-j}{M-j} \leq\left(\frac nM\right)^{k+1} =\frac{n^{k+1}}M\,q \leq\frac q2.\)
For the second inequality, each factor satisfies \((n-j)/(M-j)\leq n/M\), since \(M\geq n\). If \(k=n\), the event is impossible and the product has a zero factor, so the same bound holds.
Thus
\(\displaystyle \text{a cover of size at most }k\text{ exists}\quad\Longleftrightarrow\quad p(a)\geq q.\)
This proves that threshold comparison is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions, even with dichotomous orders and dyadic masses. Exact computation would permit this comparison, so exact computation is \(\mathrm{NP}\)-hard and cannot be polynomial-time solvable unless \(\mathrm P=\mathrm{NP}\).
3. A subset dynamic program.
Fix the queried alternative \(a\). For each type \(t\), define
\(\displaystyle I_t=\{x\in A:x\sim_t a\},\qquad H_t=\{x\in A:x\succ_t a\}.\)
For \(S\subseteq\mathcal T\), define
\(\displaystyle C_S=\bigcap_{t\in S}I_t,\qquad C_\varnothing=A.\)
We first establish the state description needed by the algorithm:
Whenever \(a\) survives a prefix whose processed types are precisely \(S\), its current surviving set is \(C_S\).
Initially this holds. Suppose it holds for \(S\), and type \(t\notin S\) acts. Because \(a\in C_S\) and the order is complete, \(a\) survives this step exactly when
\(\displaystyle C_S\cap H_t=\varnothing.\)
Under this condition, \(a\) is most preferred in \(C_S\). The most-preferred elements are precisely those tied with it, namely
\(\displaystyle C_S\cap I_t=C_{S\cup\{t\}}.\)
This proves the state description by induction.
Let \(F(S)\) be the probability that the first \(|S|\) clock positions contain exactly \(S\), and that \(a\) survives these positions. Initialize \(F(\varnothing)=1\) and every other entry to zero. Process subsets in increasing cardinality. For every \(t\notin S\) satisfying \(C_S\cap H_t=\varnothing\), perform
\(\displaystyle F(S\cup\{t\})\ \mathrel{+}=\ F(S)\frac{w_t}{W(\mathcal T\setminus S)}.\)
This recurrence is exact. Every surviving prefix has a uniquely determined predecessor and last type. The clock-order law supplies the transition probability, while admissibility depends only on \(S\), by the proved state description.
At completion, let
\(\displaystyle c=|C_{\mathcal T}|.\)
This is positive because \(a\in C_{\mathcal T}\). Whenever \(a\) survives all types, the final set is exactly \(C_{\mathcal T}\). Therefore the requested probability is
\(\displaystyle p(a)=\frac{F(\mathcal T)}c.\)
The division by \(c\) implements the required uniform selection, including alternatives tied with \(a\) by every type.
The sets \(C_S\) can be computed by successive intersections. Checking all admissible transitions takes \(O(m\tau2^\tau)\) elementary membership checks, and the recurrence uses \(O(\tau2^\tau)\) rational arithmetic operations.
4. Bit complexity and fixed-parameter tractability.
An arithmetic-operation bound alone does not establish the requested bit-time bound. We therefore bound all rational sizes.
Write each input mass as \(\mu_t=u_t/v_t\), with positive binary integers, and set
\(\displaystyle D=\prod_{t\in\mathcal T}v_t,\qquad w_t=u_t(D/v_t).\)
These are positive integer weights, and \(\sum_t w_t=D\). Since the denominator encodings are part of the input, \(D\) has \(O(L)\) bits.
Consider the integer
\(\displaystyle Q=\prod_{\varnothing\ne U\subseteq\mathcal T}W(U).\)
Every nonempty subset weight lies between \(1\) and \(D\), so \(Q\) has \(O(2^\tau L)\) bits.
The probability of any specified ordered prefix has denominator dividing \(Q\): its denominator factors are weights of successively smaller remaining subsets, each occurring at most once. Every \(F(S)\) is a sum of such prefix probabilities, so its reduced denominator also divides \(Q\). Moreover, \(0\leq F(S)\leq1\), which bounds its reduced numerator by the same bit length.
Thus, reducing fractions after each update keeps stored entries within \(O(2^\tau L)\) bits. The final division by \(c\leq m\) adds at most \(O(\log m)\) bits. Standard integer arithmetic and fraction reduction take polynomial time in these lengths.
Combining this with the operation counts yields
\(\displaystyle 2^{O(\tau)}\operatorname{poly}(m,L)\)
bit operations. This proves fixed-parameter tractability in \(\tau\).
5. Connection with discrete voting RSD.
The connection is exact. Give every individual agent in a discrete population an independent rate-one exponential clock. Their ordering is uniform over agent permutations. If type \(t\) has \(n_t\) agents, its earliest clock is exponential of rate \(n_t\); these earliest clocks are independent across types.
After a type first acts, the surviving set lies within one of that type's indifference classes. Every later occurrence of the same type therefore leaves the set unchanged. Deleting those later occurrences preserves the outcome.
Consequently, discrete RSD induces precisely the present clock model with masses \(n_t/\sum_s n_s\). This also transfers the discrete exact-computation hardness result of [Aziz–Brandt–Brill, Theorem 2](https://pub.dss.in.tum.de/brandt-research/rsd.pdf). For arbitrary rational masses, the integer weights above give an equivalent population, but that population may be exponentially large in \(L\); the subset algorithm avoids constructing it.
⟨structured verdict parsed — rendered above⟩
The output resolves both questions in substance: its direct reduction establishes NP-hardness, and its dynamic program establishes fixed-parameter tractability in \(\tau\), with bit running time \(2^{O(\tau)}\operatorname{poly}(m,L)\).
I found no false central step or substantive gap. Two minor clarifications are needed: explicitly making the constructed alternative \(a\) fresh, and stating the scope of the supplementary discrete RSD theorem accurately.
The scaling assertion is correct: multiplying all rates by the same positive constant preserves the distribution of their ordering.
For a nonempty remaining set \(U\), the displayed integral correctly computes the first-clock probability:
\[
\frac{w_t}{W(U)}.
\]
All weights are positive, so its denominator is positive.
The use of exponential memorylessness is valid. Conditional on the first clock and its ringing time, the other residual waiting times are independent exponentials with their original rates. Consequently, the next-type distribution depends only on the remaining types, even after conditioning on a specified ordered prefix.
Finding: Correct.
The stated restrictions on Set Cover preserve NP-hardness. Removing empty or duplicate sets preserves the existence of a cover within the bound, and the excluded trivial instances can be decided directly.
The construction should explicitly require \(a\notin U\). Its notation and subsequent reasoning plainly intend a fresh alternative, so this is a minor omission.
The constants satisfy the claimed bounds. Since \(2^h\geq n\),
\[
M=2^{1+(k+1)h}\geq 2n^{k+1}>n.
\]
This also holds when \(n=1\), where \(h=0\) and \(M=2\).
The preference classes are nonempty: every subset type has \(a\) in its top class and the nonempty set \(S_i\) in its bottom class; the blocker has the nonempty universe in its top class. Distinct subsets give distinct orders, and the blocker differs from every subset type.
The masses are positive dyadic rationals summing to one. The construction and threshold have polynomial encoding length because \(k\leq n\), \(b=O(k\log(n+1))\), and \(M^k=2^{bk}\).
Before the blocker acts, the displayed surviving-set formula is correct. Each processed subset type retains \(a\) and removes precisely the elements of its subset that remain.
If these subsets cover \(U\), the surviving set is \(\{a\}\), which every subsequent type retains. Otherwise, the blocker eliminates \(a\), which can never re-enter the surviving set.
Thus the identification of \(p(a)\) with the probability of a cover appearing before the blocker is exact. Final uniform tie-breaking does not affect this reduction.
For a fixed ordered cover of size \(r\leq k\), the probability of that exact initial prefix is
\[
\prod_{j=0}^{r-1}\frac{1}{M-j}.
\]
The denominators correctly account for the removal of one rate-one subset type at each step. Each factor is at least \(M^{-1}\), giving the asserted lower bound \(p(a)\geq q\).
Without a cover of size at most \(k\), selection requires at least \(k+1\) subset types before the blocker. The probability of that event is correctly expressed by
\[
\prod_{j=0}^{k}\frac{n-j}{M-j}.
\]
For the relevant indices, all denominators are positive, and the factorwise bound follows from \(M\geq n\). The resulting upper bound is indeed \(q/2\).
When \(k=n\), the event is impossible; the zero final numerator correctly represents this boundary case.
Therefore the equivalence with \(p(a)\geq q\) is valid. The reduction establishes many-one NP-hardness of threshold comparison. An exact rational output permits comparison with \(q\), so the claimed NP-hardness of exact computation follows.
Finding: Correct, with the minor freshness clarification.
The induction is valid for complete weak orders. Conditional on \(a\) surviving the processed types \(S\), the current set is exactly \(C_S\).
Because \(a\in C_S\), the next type retains \(a\) precisely when \(C_S\) contains no alternative strictly preferred to \(a\). Under that condition, its maximal elements are exactly those tied with \(a\), yielding \(C_{S\cup\{t\}}\).
This justifies using the processed subset as the state, despite different processing orders potentially having different survival outcomes.
The definition of \(F(S)\) correctly includes both the first-position set and survival. The transition probability depends only on the remaining types, while admissibility depends only on \(S\). Consequently, combining probabilities of surviving prefixes into one entry loses no information needed for subsequent transitions.
Every individual ordered prefix has a unique predecessor and final type, so the recurrence neither omits nor double-counts surviving prefixes.
The set \(C_{\mathcal T}\) contains \(a\), so \(c\geq1\). On every fully surviving order, it is the final set. Hence division by \(c\) correctly handles uniform selection, including alternatives tied by every type.
The stated membership-check and rational-operation bounds are consistent with enumerating all subset/type transitions.
The algorithm also handles \(m=1\) and \(\tau=1\). Zero-probability states cause no difficulty, and every denominator used for a transition is positive.
Finding: Correct.
The common-denominator construction is valid even if the input fractions are not reduced. The normalization of the masses implies \(\sum_t w_t=D\), and \(D\) has \(O(L)\) bits.
Every nonempty subset weight is an integer between \(1\) and \(D\). Therefore the product \(Q\) has the claimed \(O(2^\tau L)\) bit length.
For an ordered prefix, the denominator factors correspond to distinct remaining subsets. Their product divides \(Q\). Summing prefix probabilities preserves a reduced denominator dividing \(Q\). Since \(F(S)\) is a probability, its reduced numerator has the same bit-length bound.
Reducing after each update is sufficient. The temporary products and sums formed during one update also have bit lengths bounded by a constant multiple of the stored-entry and weight lengths. Fraction reduction therefore does not invalidate the complexity estimate.
The final division adds at most \(O(\log m)\) bits. A polynomial arithmetic cost in \(O(2^\tau L)\), multiplied by the stated number of operations, remains \(2^{O(\tau)}\operatorname{poly}(m,L)\).
Finding: Correct. The output establishes bit-time FPT, not merely an arithmetic-operation bound.
The probabilistic correspondence is correct. Independent rate-one clocks uniformly order the individuals. Minima over disjoint type groups are independent exponentials with rates equal to the type counts.
The deletion of repeated type occurrences is also valid: after its first action, the surviving set lies in one indifference class of that type, and subsequent refinements remain within that class.
The supplementary citation needs a scope clarification. [Aziz–Brandt–Brill, Theorem 2](https://pub.dss.in.tum.de/brandt-research/rsd.pdf) establishes exact-probability counting hardness in the voting setting, even for dichotomous preferences, using a polynomial-time Turing reduction. The paper assumes that no distinct alternatives are tied by every agent.
The prover does not explicitly state that restriction or the polynomial-time grouping of identical individual orders into distinct support types. This is a minor presentation gap: the cited domain is a subclass of the present task, and the independently verified direct reduction already establishes the required hardness.
Neither clarification requires new mathematics.
⟨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.