Multi-votes Election Control by Selecting Rules

We prove the theorem by reducing from Dominating Set problem, which given a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ and an integer $k^{\prime}$ where $|\mathcal{V}|=m^{\prime}$ and $|\mathcal{E}|=n^{\prime}$, asks for a size-$\leq k^{\prime}$ vertex subset $\mathcal{V^{\prime}}\subseteq\mathcal{V}$ where $\forall v\in\mathcal{V},\exists v^{\prime}\in\mathcal{V^{\prime}},v\in N[v^{\prime}]$. It is known that Dominating set problem is NP-hard and is W[2]-hard with respect to the size of $\mathcal{V^{\prime}}$ [24]. We construct an MECSR instance $(E=(C,V,R,t),\alpha,d)$ from $(\mathcal{G}=(\mathcal{V},\mathcal{E}),k^{\prime})$ as follows.

For each vertex $v_{i}\in\mathcal{V},i\in[m^{\prime}]$, we construct a voter $V_{i}$ and a rule $r_{i}$, $V=\bigcup_{i=1}^{m^{\prime}}V_{i}$, $R=\bigcup_{i=1}^{m^{\prime}}r_{i}$. There are $k^{\prime}$ layers in total, $t=k^{\prime}$. For each voter $V_{i},i\in[m^{\prime}]$, we construct $k^{\prime}$ votes, $V_{i}=\bigcup_{j=1}^{k^{\prime}}v_{i}^{j}$. The satisfaction of vote $v_{i}^{j}(j\in[k^{\prime}])$ with rule $r_{k}$ is set to 1, if the corresponding vertices $v_{i}$ and $v_{k}$ satisfy $v_{i}\in N[v_{k}]$ in $\mathcal{G}$, ${\tt Sat}(v_{i}^{j},r_{k})=1$; otherwise, the satisfaction is set to 0, ${\tt Sat}(v_{i}^{j},r_{k})=0$.

Note that all $t=k^{\prime}$ votes of one voter are the same. Let $d:=1$, $\alpha:=n^{\prime}$. Now we prove that there is a size-$k^{\prime}$ dominating set in $\mathcal{G}$ if and only if there is a rule assignment solution of MECSR problem with sum-model.

“$\Longrightarrow$”: If there is a size-$\leq k^{\prime}$ dominating set $DS$ in $\mathcal{G}$, $|DS|\leq k^{\prime}$ and $\forall v\in\mathcal{V},\exists v^{\prime}\in DS,v\in N[v^{\prime}]$. Let $R^{\prime}$ be the set of rules corresponding to the vertices in $DS$, $|R^{\prime}|\leq k^{\prime}$, that is, $\forall v_{i}\in DS,r_{i}\in R^{\prime}$. For each vertex $v_{i}\in DS$, $r_{i}$ is assigned to one layer. It means each rule in $R^{\prime}$ is assigned to one layer. Since all the $k^{\prime}$ votes of one voter are same, the assignment order of the chosen $k^{\prime}$ rules has no effect on the satisfaction of each voter. Since each vertex $v_{i}\in\mathcal{V}$ is adjacent to at least one vertex $v_{k}\in DS$, it means for each voter the satisfaction of at least one layer with the rule $r_{k}$ is 1, that is $\exists r_{k}\in R^{\prime},{\tt Sat}(p,v_{i}^{j},r_{k})=1$. So, for each voter $V_{i}$, the total satisfaction of $V_{i}$ is at least $d=1$:

Therefore, the MECSR instance has a rule assignment to make $p$ being the possible winner of the election.

“$\Longleftarrow$”: Suppose there is a rule assignment of MECSR, where the satisfaction of each voter $V_{i}$ is at least $d=1$. Let $R^{\prime}$ be the set of rules of the rule assignment, $|R^{\prime}|\leq k^{\prime}$ and $r_{j^{\prime}}\in R^{\prime}$ is the rule assigned to $j-$th layer. Then, for each voter $V_{i}$, it must hold ${\tt Sat}(V_{i})=\sum_{j=1}^{k^{\prime}}{\tt Sat}(v_{i}^{j},r_{j^{\prime}})\geq d=1$. Since the satisfaction for a voter of each layer can only be $1$ or $0$, there must be a layer where the satisfaction is $1$ with the assigned rule $r_{j^{\prime}}$. It means:

So, for each voter $V_{i}$, the corresponding vertex $v_{i}$ must hold $v_{i}\in[v_{j^{\prime}}]$ with satisfying ${\tt Sat}(v_{i}^{j},r_{j^{\prime}})=1$. Therefore, the set of vertices corresponding to the rules in $R^{\prime}$ is a size-$\leq k^{\prime}$ dominating set of $\mathcal{G}$. This completes the proof of this theorem.

We prove the theorem by reducing from Dominating Set problem. We construct an MECSR instance $(E=(C,V,R,t),\alpha,d)$ from $(\mathcal{G}=(\mathcal{V},\mathcal{E}),k^{\prime})$ as follows.

For each vertex $v_{i}\in\mathcal{V}(i\in[m^{\prime}])$, we construct a voter $V_{i}$. We also construct another voter $V_{m^{\prime}+1}$, $V=\bigcup_{i\in[m^{\prime}+1]}V_{i}$. There are two rules, $r_{1}$ and $r_{2}$, $R=\{r_{1},r_{2}\}$, and $2m^{\prime}$ layers, $t=2m^{\prime}$. The satisfaction of each vote is set as follows:

• •

  For the $j-$th layer with $j\in[m^{\prime}]$:

  • –

    ${\tt Sat}(v_{i}^{j},r_{1})=1$, $i\in[m^{\prime}]$ and $v_{i}\in N[v_{j}]$;

  • –

    ${\tt Sat}(v_{i}^{j},r_{1})=0$, $i\in[m^{\prime}]$ and $v_{i}\notin N[v_{j}]$;

  • –

    ${\tt Sat}(v_{i}^{j},r_{2})=0$, $i\in[m^{\prime}]$;

  • –

    ${\tt Sat}(v_{i}^{j},r_{1})=0$, ${\tt Sat}(v_{i}^{j},r_{2})=1$, $i=m^{\prime}+1$.

• •

  For the $j-$th layer with $j\in[m^{\prime}+1,2m^{\prime}-1]$:

  • –

    ${\tt Sat}(v_{i}^{j},r_{1})={\tt Sat}(v_{i}^{j},r_{2})=1$, $i\in[m^{\prime}]$;

  • –

    ${\tt Sat}(v_{i}^{j},r_{1})={\tt Sat}(v_{i}^{j},r_{2})=1$, $i=m^{\prime}+1$ and $j\in[m^{\prime}+1,m^{\prime}+k^{\prime}]$;

  • –

    ${\tt Sat}(v_{i}^{j},r_{1})={\tt Sat}(v_{i}^{j},r_{2})=0$, $i=m^{\prime}+1$ and $j\in[m^{\prime}+k^{\prime}+1,2m^{\prime}-1]$;

• •

  For the $j-$th layer with $j=2m^{\prime}$:

  • –

    ${\tt Sat}(p,v_{i}^{2m^{\prime}},r_{1})={\tt Sat}(p,v_{i}^{2m^{\prime}},r_{2})=0$, $i\in[m^{\prime}+1]$.

Let $\alpha:=m^{\prime}+1$, $d:=m^{\prime}$. Now, we show that the Dominating set instance has a size-$\leq k^{\prime}$ dominating set if and only if there is a rule assignment of $r_{1}$ and $r_{2}$ of MECSR instance with sum-model such that $\forall i\in[m^{\prime}+1]$, $\sum_{j=1}^{2m^{\prime}}{\tt Sat}(v_{i}^{j})\geq m^{\prime}$.

“$\Longrightarrow$”: Suppose that there exists a size-$\leq k^{\prime}$ dominating set $\mathcal{V^{\prime}}$ in $\mathcal{G}$. For $j\in[m^{\prime}]$, $r_{1}$ is assigned to the $k^{\prime}$ layers corresponding to the vertices in $\mathcal{V^{\prime}}$, while $r_{2}$ is assigned to the other layers. For example, if $v_{2}$ is in $V^{\prime}$, $r_{1}$ is assigned to the second layer; otherwise, $v_{2}$ is not in $V^{\prime}$, $r_{2}$ is assigned to the second layer. For $j\in[m^{\prime}+1,2m^{\prime}]$, the allocation of $r_{1}$ and $r_{2}$ is random. Since $k^{\prime}$ layers corresponding to the vertices in $\mathcal{V^{\prime}}$ are assigned with rule $r_{1}$, and $m-k^{\prime}$ layers are assigned with rule $r_{2}$, it holds:

• •

  When $j\in[m^{\prime}]$:

  • –

    $\sum\limits_{v_{j}\in V^{\prime}}{\tt Sat}(v_{i}^{j},r)=\sum\limits_{v_{j}\in V^{\prime}}{\tt Sat}(v_{i}^{j},r_{1})+\sum\limits_{v_{j}\notin V^{\prime}}{\tt Sat}(v_{i}^{j},r_{2})\geq 1+0=1$, $i\in[m^{\prime}]$;

  • –

    $\sum\limits_{v_{j}\in V^{\prime}}{\tt Sat}(v_{i}^{j},r)=\sum\limits_{v_{j}\in V^{\prime}}{\tt Sat}(v_{i}^{j},r_{1})+\sum\limits_{v_{j}\notin V^{\prime}}{\tt Sat}(v_{i}^{j},r_{2})=0+(m^{\prime}-k^{\prime})=m^{\prime}-k^{\prime}$, $i=[m^{\prime}+1]$.

• •

  When $j\in[m^{\prime}+1,2m^{\prime}]$:

  • –

    $\sum\limits_{j\in[m^{\prime}+1,2m^{\prime}]}{\tt Sat}(v_{i}^{j},r)=\sum\limits_{j\in[m^{\prime}+1,2m^{\prime}-1]}{\tt Sat}(v_{i}^{j},r)+{\tt Sat}(v_{i}^{2m^{\prime}},r)=m^{\prime}-1+0=m^{\prime}-1$, $i\in[m^{\prime}]$;

  • –

    $\sum\limits_{j\in[m^{\prime}+1,2m^{\prime}]}{\tt Sat}(v_{i}^{j},r)=\sum\limits_{j\in[m^{\prime}+1,m^{\prime}+k]}{\tt Sat}(v_{i}^{j},r)+\sum\limits_{j\in[m^{\prime}+k^{\prime}+1,2m^{\prime}]}{\tt Sat}(v_{i}^{j},r)=k^{\prime}+0=k^{\prime}$, $i=m^{\prime}+1$.

• •

  For the $j-$th layer with $j=2m^{\prime}$:

  • –

    ${\tt Sat}(p,v_{i}^{2m^{\prime}},r_{1})={\tt Sat}(p,v_{i}^{2m^{\prime}},r_{2})=0$, $i\in[m^{\prime}+1]$.

Note that, the satisfaction $v_{i}^{j}$ remains constant regardless of the $r_{1}$ or $r_{2}$ is assigned to $j-$th layer, when $j\in[m^{\prime}+1,2m^{\prime}]$. So, we can get:

• •

  ${\tt Sat}(V_{i})=\sum\limits_{j\in[m^{\prime}]}{\tt Sat}(v_{i}^{j},r)+\sum\limits_{j\in[m^{\prime}+1,2m^{\prime}]}{\tt Sat}(v_{i}^{j},r)\geq 1+m^{\prime}-1=m^{\prime}=d$, $i\in[m^{\prime}]$

• •

  ${\tt Sat}(V_{i})=\sum\limits_{j\in[m^{\prime}]}{\tt Sat}(v_{i}^{j},r)+\sum\limits_{j\in[m^{\prime}+1,2m^{\prime}]}{\tt Sat}(v_{i}^{j},r)\geq 1+m^{\prime}-1=m^{\prime}=d$, $i=[m^{\prime}+1]$

Therefore, the total satisfaction of $v_{i}^{j}$ is at least $m^{\prime}$ for all $i\in[m^{\prime}+1]$, $j\in[m^{\prime}+1,2m^{\prime}]$.

“$\Longleftarrow$”: Suppose there is a rule assignment of MECSR, where the satisfaction of each voter $V_{i}$ is at least $m^{\prime}$. According to the votes of $V_{m^{\prime}+1}$, the total satisfaction of $v_{m^{\prime}+1}^{j}$ is always $k^{\prime}$ regardless of $r_{1}$ or $r_{2}$ is assigned to the $j$-th layer, $j\in[m^{\prime}+1,2m^{\prime}]$. That is:

${\tt Sat}(p,v_{m^{\prime}+1}^{j},r_{1})={\tt Sat}(p,v_{m^{\prime}+1}^{j},r_{2})$. To reach the threshold $d=m^{\prime}$, for the $j$-th layer, $j\in[m^{\prime}]$, at most $k^{\prime}$ layers can be assigned with $r_{1}$. For the voters of $V_{i}$, $i\in[m^{\prime}]$, it always holds:

• •

  $\sum\limits_{j\in[m^{\prime}+1,2m^{\prime}]}{\tt Sat}(v_{i}^{j},r)+\sum\limits_{j\in[m^{\prime}+1,2m^{\prime}-1]}{\tt Sat}(v_{i}^{2m^{\prime}},r)=m^{\prime}-1$, $i\in[m^{\prime}]$

• •

  $\sum\limits_{j\in[m^{\prime}+1,2m^{\prime}]}{\tt Sat}(v_{i}^{j},r)=\sum\limits_{j\in[m^{\prime}+1,m^{\prime}+k^{\prime}]}{\tt Sat}(v_{i}^{j},r)+\sum\limits_{j\in[m^{\prime}+k^{\prime}+1,2m^{\prime}]}{\tt Sat}(v_{i}^{j},r)\\ =k^{\prime}+0=k^{\prime}$, $i=[m^{\prime}+1]$

Therefore, for each $j$-th layer with $j\in[m^{\prime}]$, at least one layer is assigned with $r_{1}$ to receive the satisfaction of $1$ for $V_{i}(i\in[m^{\prime}])$, and at most $k^{\prime}$ layers can be assigned with $r_{1}$ to ensure that the total satisfaction $\sum\limits_{j\in[m^{\prime}]}{\tt Sat}(v_{m^{\prime}+1}^{j},r)\geq m^{\prime}-k^{\prime}$. Since the $j$-th layer ($j\in[m^{\prime}]$) corresponds to the vertex $v_{j}$ in the graph $\mathcal{G}$, we have ${\tt Sat}(v_{i}^{j},r_{1})=1$ only when the corresponding vertex $v_{i}\in N[v_{j}]$, where $N[v_{j}]$ represents the neighborhood set of $v_{j}$. Therefore, the instance $(E=(C,V,R,t),\alpha,d)$ has a solution of rule assignment if and only if the graph $(\mathcal{G}=(\mathcal{V},\mathcal{E}),k^{\prime})$ has a size-$\leq k^{\prime}$ dominating set.

We prove this theorem by giving a reduction from 3-Set Packing, which given a set of elements $X$, $X=\bigcup_{i\in[m^{\prime}]}x_{i}$, a set of sets $\mathcal{S}$, $\mathcal{S}=\bigcup_{i\in[n^{\prime}]}\mathcal{S}_{i}$, where $\forall i\in[n^{\prime}]$,$\mathcal{S}_{i}\subset X$, $|\mathcal{S}_{i}|=3$, and asks for a size-$k^{\prime}$ subset $\mathcal{S}^{\prime}$ of $\mathcal{S}$ that $\forall\mathcal{S}_{i},\mathcal{S}_{i^{\prime}}\in\mathcal{S}^{\prime}$, $\mathcal{S}_{i}\cap\mathcal{S}_{i^{\prime}}=\emptyset$. It is known that 3-set packing is NP-hard and is W[1]-hard with respect to $k^{\prime}$. We construct an MECSR instance $(E=(C,V,R,t),\alpha,d)$ from $((X,\mathcal{S}),k^{\prime})$ where $|X|=m^{\prime}$ and $|\mathcal{S}|=n^{\prime}$ as follows:

For each element $x_{i}\in X$, we construct a voter $V_{i}$, $V=\bigcup_{i\in[m^{\prime}]}V_{i}$. There are totally $k^{\prime}$ layers, $t=k^{\prime}$, $V_{i}=\bigcup_{j\in[k^{\prime}]}v_{i}^{j}$. For each set $\mathcal{S}_{i}\in\mathcal{S}$, we construct a rule $r_{k}$, $R=\bigcup_{k\in[n^{\prime}]}\{r_{i}\}$. For each vote $v_{i}^{j}(j\in[k^{\prime}])$ and rule $r_{k}$, if the corresponding element $x_{i}\in\mathcal{S}_{k}$, ${\tt Sat}(v_{i}^{j},r_{k})$ is set to $1$; otherwise, ${\tt Sat}(v_{i}^{j},r_{k})$ is set to $0$.

Note that the $k^{\prime}$ votes of one voter are all the same. Let $\alpha:=3k^{\prime}$, $d:=1$. Now we prove that there is a size-$k^{\prime}$ subset $\mathcal{S}^{\prime}$ if and only if there is a solution of MECSR instance with sum-model.

“$\Longrightarrow$”: Suppose that there is a size-$k^{\prime}$ subset $\mathcal{S}^{\prime}\subset\mathcal{S}$, where $\forall\mathcal{S}_{i},\mathcal{S}_{i^{\prime}}\in\mathcal{S}^{\prime}$, $\mathcal{S}_{i}\cap S_{i^{\prime}}=\emptyset$. Let $\mathcal{S}^{\prime}=\{\mathcal{S}_{\beta 1},\mathcal{S}_{\beta 2},\cdots,\mathcal{S}_{\beta k^{\prime}}\}$. For the $j-$th layer, the rule $r_{\beta j}$ is assigned. Let $R^{\prime}$ be the set of rules corresponding to the sets in $S^{\prime}$. In this way, $\forall x_{i}\in\mathcal{S}_{\beta j}\subset\mathcal{S}^{\prime}(j\in[k^{\prime}])$, the satisfaction of vote $v_{i}^{j}$ with rule $r_{\beta j}$ is $1$, ${\tt Sat}(v_{i}^{j},r_{\beta j})=1$. So, the satisfaction of the voter $V_{i}$ which corresponds to the element $x_{i}$ in $\mathcal{S}^{\prime}$ is at least $1$, that is, ${\tt Sat}(p,V_{i})\geq{\tt Sat}(p,v_{i}^{j},r_{\beta j})\geq 1=d$. There are exactly $3k^{\prime}$ elements in the set of $\mathcal{S}^{\prime}$, because each two sets in $\mathcal{S}^{\prime}$ do not share a common element and each set contains exactly $3$ elements, $|\mathcal{S}_{i}|=|\mathcal{S}_{i^{\prime}}|=3$. That is, there are at least $\alpha=3k^{\prime}$ voters whose satisfaction is at least $d=1$. Therefore, if $((X,\mathcal{S}),k^{\prime})$ has a size-$k^{\prime}$ subset $\mathcal{S}^{\prime}$ of $\mathcal{S}$ satisfying $\forall\mathcal{S}_{i},\mathcal{S}_{i^{\prime}}\in\mathcal{S}^{\prime}$, $\mathcal{S}_{i}\cap\mathcal{S}_{i^{\prime}}=\emptyset$, MECSR instance has a solution of rule assignment $R^{\prime}$.

“$\Longleftarrow$”: Suppose that there is an assignment of rules for each layer in which there are at least $\alpha=3k^{\prime}$ voters whose satisfaction is at least $d=1$. Let $r_{\gamma j}\in R$ be the rule assigned to $j-$th layer, $j\in[k^{\prime}]$. For each satisfied voter $V_{i}$, it must hold ${\tt Sat}(V_{i})=\sum_{j\in[k^{\prime}]}{\tt Sat}(v_{i}^{j},r_{\gamma j})\geq 1=d$. It means that there are at least one vote $v_{i}^{j}$ satisfying ${\tt Sat}(v_{i}^{j},r_{\gamma j})=1$. Without loss of generality, let the $j^{\prime}-$th layer satisfies ${\tt Sat}(v_{i}^{j^{\prime}},r_{\gamma j^{\prime}})=1$, $(j^{\prime}\in[k^{\prime}])$. In this way, the corresponding element $x_{i}$ must be in the set $S_{\gamma j^{\prime}}$. Since there are $k^{\prime}$ layers and at least $\alpha=3k^{\prime}$ satisfied voters, the corresponding elements must be in the $k^{\prime}$ corresponding sets. Because each set $\mathcal{S}_{i}$ contains exactly $3$ elements, $\forall i\in[n^{\prime}],|\mathcal{S}_{i}|=3$. So, there are exactly $3k^{\prime}$ elements in exact $k^{\prime}$ sets, denote the set of the $k^{\prime}$ sets as $S^{\prime}$. Therefore, if MECSR instance has a solution of rule assignment, $((X,\mathcal{S}),k^{\prime})$ has a size-$k^{\prime}$ subset $\mathcal{S}^{\prime}$ of $\mathcal{S}$ satisfying $\forall\mathcal{S}_{i},\mathcal{S}_{i^{\prime}}\in\mathcal{S}^{\prime}$, $\mathcal{S}_{i}\cap\mathcal{S}_{i^{\prime}}=\emptyset$. This completes the proof of this theorem.

We firstly prove the result that MECSR problem with sum-model is NP-hard even if there are only 2 voters, $n:=2$, by reducing Partition problem to MECSR. Given a set $X$ of $n^{\prime}$ elements, where each element $x_{i}\in X$ is associated with a value $s_{i}\in S$, the problem asks for a partition of elements in $X$ into two disjoint subsets $X_{1}$ and $X_{2}$, $X=X_{1}\cup X_{2}$, $X_{1}\cap X_{2}=\emptyset$, such that the sum of values assigned to the elements in $X_{1}$ is equal to the sum of values assigned to the elements in $X_{2}$, $\sum_{x_{i}\in X_{1}}s_{i}=\sum_{x_{i^{\prime}}\in X_{2}}s_{i^{\prime}}$. It is well-known that Partition problem is NP-hard [26]. We construct an MECSR instance $(E=(C,V,R,t),\alpha,d)$ from $({X},S)$ as follows:

We construct two voters $V_{1}$, $V_{2}$ and two rules $r_{1}$, $r_{2}$, $V=V_{1}\bigcup V_{2}$, $R=\{r_{1},r_{2}\}$. There are $n^{\prime}$ layers in total, $t:=n^{\prime}$. For each layer of voter $V_{1}$, the satisfaction of vote $v_{1}^{j}(j\in[n^{\prime}])$ with $r_{1}$ is set to $s_{j}$, and the satisfaction of vote $v_{1}^{j}$ with $r_{2}$ is set to 0. For each layer of voter $V_{2}$, the satisfaction of vote $v_{2}^{j}$ with rule $r_{1}$ is set to 0, and the satisfaction of vote $v_{2}^{j}$ with rule $r_{2}$ is set to $s_{j}$.

Note that for the $j-$th layer, if the rule $r_{1}$ is chosen, then the satisfaction of $V_{1}$ is improved by $s_{j}$; otherwise, the rule of $r_{2}$ is chosen, and the satisfaction of $V_{2}$ is improved by $s_{j}$. We set $\alpha:=2$, $d:=\frac{1}{2}N=\sum_{x_{i}\in X}s_{i}$. It means each layer can be assigned with $r_{1}$ or $r_{2}$, corresponding to the assignment of elements to either $X_{1}$ or $X_{2}$; and $V_{1}$ and $V_{2}$ are both satisfied with a value $d=\frac{1}{2}N$, corresponding to partition $X$ into $X_{1}$, $X_{2}$, and the total value of elements in $X_{1}$ and $X_{2}$ are both $d=\frac{1}{2}N$. Therefore, there is a partition for $(X,S)$ if and only if there is a solution of $(E=(C,V,R,t),\alpha,d)$.

Next, we show the reason of why MECSR problem is W[2]-hard with respect to the number of voter $n$ when $n\leq t$. According to the proof of Theorem 3.1, when $n=m^{\prime}$ ($m^{\prime}$ is the number of vertex) and $t=k^{\prime}$ ($k^{\prime}$ is the size of dominating set), MECSR problem is w[2]-hard with respect to the number of layers $t$. We can do the following modifications to the proof in Theorem 3.1:

• •

  Add $\lambda$ layers for each voter($\lambda\geq m^{\prime}-k^{\prime}$);

• •

  Set the satisfaction of vote $v_{i}^{j}$ with each rule is 0, ${\tt Sat}(v_{i}^{j},r)=0,i\in[m^{\prime}],j\in[k^{\prime}+1,k^{\prime}+\lambda],r\in R$.

Let $R^{\prime}:=R,d^{\prime}:=d,t^{\prime}=t+\lambda\geq m^{\prime}$, and $(E^{\prime}=(C^{\prime},V^{\prime},R^{\prime},t^{\prime}),\alpha^{\prime},d^{\prime})$ be the modified MECSR instance. It holds $n=m^{\prime}\leq k^{\prime}+\lambda=t^{\prime}$. Since the added layers have no influence on the the solution of this problem (the satisfaction of each added layers is 0). So, the modified instance $(E^{\prime}=(C^{\prime},V^{\prime},R^{\prime},t^{\prime}),\alpha^{\prime},d^{\prime})$ has a solution if and only if the original instance $(E=(C,V,R,t),\alpha,d)$ has a rule assignment solution. This means MECSR is w[2]-hard with respect to the number of $t$ when $n\leq t$. Since if a problem is FPT with respect to $n$, this problem must be FPT with repect to $t$ when $n\leq t$. Therefore, MECSR problem is W[2]-hard with respect to the number of $n$ when $n\leq t$.

In the following, we show the FPT result when $n>t$. Firstly, we can enumerate all conditions whose satisfaction achieve the threshold $d$. The number of all conditions is $2^{n}$, and we consider the conditions of voters when the number of satisfied voter is at least $\alpha$. For each of this condition, we construct an ILP formulation. Let $V^{\prime}$ be the set of voter whose satisfaction is at least $d$. We say two rules are of the same type if they can make the same voters satisfied in $j-$th layer($j\in[t]$). Let $RT$ be the set of all rule types. There are $n$ voters and $t$ layers in total, so there are at most $2^{n}\times t$ different rule types, $|RT|\leq 2^{n}\times t$. For each rule type $rt\in RT$, let $n_{rt}$ be the number of rules in $R$ of type $rt$. Let $f(j,rt)$ be the set of index of the voters whose satisfaction of vote $v_{i}^{j}$ is 1 with the rule $r$ of type $rt$, $i\in f(j,rt)$, ${\tt Sat}(v_{i}^{j},r)=1$. If $i\in f(j,rt)$, we define $h(i,j,rt)=1$; otherwise $h(i,j,rt)=0$. In the following, we define the variables of ILP. For each rule type $rt$, we define an integer variable $x_{j,rt}$, where $x_{j,rt}\in\{0,1\}$ that $x_{j,rt}=c$ means there are $c$ rules of type $rt$ assigned to $j-$th layer. The ILP instance consists of the following constraints:

The first equality guarantees that for each layer, there is exactly one rule assigned to this layer. The second inequality means the chosen rules can make all voters in $V^{\prime}$ satisfied. Therefore, the solution of the ILP instance gives a rule assignment to make all voter in $V^{\prime}$ satisfied. The number of the variable is in $O(2^{n}\times t\times t)$. For each condition, we construct such an ILP and there are totally $2^{n}$ conditions. Since $n>t$, we can solve this problem in $O^{*}(2^{n}\times 2^{n}\times n\times n)$. Therefore, the MECSR problem is FPT with respect to $n$ when $n>t$. This completes the proof of this theorem.