Answer: \(\mathrm{NP}\)-hard, even with \(\tau=2\) and both masses equal to \(\tfrac12\).
Theorem 12 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe EMar and EBar problems restricted to the case when the agent seeking manipulation or bribery, respectively, has a two-level preference are ΣP 2 -complete. The proof of this result follows from Theorems 5 and 9 or, more precisely from simplified characterizations they provide for the case when an agent attempting manipulation or bribery has a two-level preference.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a binary-rational distribution \(\mu\) over compact preference-statement types on \(D=2^U\), with beneficiary type \(b\) having a two-level preference, does there exist a target type \(t\ne b\), a valid report \(q\), and a binary-rational mass \(x\) with \(0<x\le\mu_t\) such that \(\mu'=\mu-x\mathbf e_t+x\mathbf e_q\) and \(\operatorname{Opt}(\mu')\succ_{\rm ar,b}\operatorname{Opt}(\mu)\)? Here Pareto dominance is determined by all types of positive mass, and \(\succ_{\rm ar,b}\) is the beneficiary's strict average-rank comparison.
Let \(U\) be a finite set of \(m\) Boolean attributes and \(D=2^U\). A valid preference statement is \(p=\varphi_1>\cdots>\varphi_k\), with propositional formulas over \(U\) whose disjunction is tautological; outcomes are ordered by the index of the first formula they satisfy, with equal indices tied.
A society is given by its support: a list of \(\tau\) distinct preference-statement types with positive binary-rational masses \(\mu_s\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
A designated support type \(b\) has exactly two nonempty indifference classes \(B_1\succ_b B_2\). For a nonempty outcome set \(Z\), define \(\operatorname{ar}_b(Z)=(|Z\cap B_1|+2|Z\cap B_2|)/|Z|\), and \(X\succ_{\mathrm{ar},b}Y\) iff \(\operatorname{ar}_b(X)<\operatorname{ar}_b(Y)\).
For any society \(\nu\), let \(\operatorname{Opt}(\nu)\) be its Pareto-optimal outcomes, using every positive-mass type's preorder; masses do not weight dominance, and all undominated outcomes are retained.
The decision problem asks whether there exist a support type \(t\ne b\), any valid preference statement \(q\) over \(U\), and a binary-rational \(x\) with \(0<x\le\mu_t\), such that \(\mu'=\mu-x\mathbf e_t+x\mathbf e_q\) satisfies \(\operatorname{Opt}(\mu')\succ_{\mathrm{ar},b}\operatorname{Opt}(\mu)\). Here \(\mathbf e_s\) is unit mass at type \(s\); \(q\) may be an existing or new type, with no imposed length or level bound.
Is this continuous existence-of-bribery decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For finite lists of agents with these compact preferences and a two-level beneficiary, existence of average-rank bribery is \(\Sigma_2^{\mathrm P}\)-complete; with explicitly enumerated outcome strata it is polynomial-time solvable. [Source](https://www.cs.uky.edu/ai/mani.pdf)
No result settling this precise mass-transfer problem was located in the literature search.
The problem is \(\mathrm{NP}\)-hard, even when \(\tau=2\), both masses are \(\tfrac12\), and each input preference statement contains only two formulas. The reduction uses an existing type as the replacement statement.
Let \(\varphi\) be a propositional formula over a set \(V\) of \(n\) variables. Introduce one new attribute \(z\), and set \(U=V\cup\{z\}\), so \(m=n+1\).
Construct the designated beneficiary and the other support type as follows:
\(b=(\neg z)>(z)\),
\(t=(z\land\varphi)>\neg(z\land\varphi)\).
Assign masses \(\mu_b=\mu_t=\tfrac12\).
Both statements are valid because their two formulas are complementary. The beneficiary has exactly two nonempty indifference classes:
\(B_1=\{d:z(d)=0\}\), and \(B_2=\{d:z(d)=1\}\).
The types are distinct as preorders. If \(\varphi\) is satisfiable, some outcome in \(B_2\) is strictly preferred by \(t\) to every outcome in \(B_1\), reversing \(b\)'s comparison. If \(\varphi\) is unsatisfiable, \(t\) ties every outcome, whereas \(b\) has two nonempty classes. An empty first class for \(t\) in this latter case is permitted by the stated validity condition.
Write \(s\) for the number of satisfying assignments of \(\varphi\), and define
\(H=\{d:z(d)=1\text{ and }\varphi(d|_V)\text{ is true}\}\).
Thus \(|B_1|=2^n\) and \(|H|=s\).
We use the usual definition: an outcome dominates another when every active type weakly prefers it and at least one active type strictly prefers it.
We claim that \(\operatorname{Opt}(\mu)=B_1\cup H\).
These cases exhaust all outcomes, proving the claim. Therefore,
\(\operatorname{ar}_b(\operatorname{Opt}(\mu))=\dfrac{2^n+2s}{2^n+s}=1+\dfrac{s}{2^n+s}\).
In particular, this average is strictly greater than \(1\) exactly when \(\varphi\) is satisfiable.
If \(\varphi\) is satisfiable, choose \(q=b\) and \(x=\mu_t=\tfrac12\). This is an allowed binary-rational transfer, and the resulting society has only \(b\) as an active type.
Its Pareto-optimal set is exactly \(B_1\): its members are mutually tied, and each strictly dominates every member of \(B_2\). Hence its average rank is \(1\), strictly below the original average. The constructed instance is a yes-instance.
If \(\varphi\) is unsatisfiable, the original average rank is already \(1\). For every nonempty outcome set \(Z\),
\(\operatorname{ar}_b(Z)=1+\dfrac{|Z\cap B_2|}{|Z|}\geq 1\).
Every resulting society has a nonempty Pareto-optimal set: strict Pareto dominance is an irreflexive, transitive relation on the finite, nonempty outcome domain, so an undominated outcome exists. Thus no replacement statement and no allowed transfer amount can produce an average below \(1\). The constructed instance is a no-instance.
We have proved the required equivalence for the full existential problem, including arbitrary replacement statements and partial transfers.
If the SAT input has bit length \(\ell\), the construction takes \(O(\ell)\) time under standard encodings and produces \(m=n+1\), \(\tau=2\), and total input length \(L=O(\ell)\). Therefore it is a polynomial many-one reduction from SAT.
Consequently, the decision problem is \(\mathrm{NP}\)-hard. A polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The argument is correct and resolves the assigned decision problem: it establishes $\mathrm{NP}$-hardness by a polynomial many-one reduction from SAT. No mathematical gaps or false steps were found.
The constructed statements are
$$
b=(\neg z)>(z),\qquad
t=(z\land\varphi)>\neg(z\land\varphi).
$$
Each statement is valid because its formulas are complementary and therefore cover every outcome.
The beneficiary’s two classes are nonempty: every assignment to the original variables has extensions with $z=0$ and $z=1$. Both masses are positive binary rationals and sum to $1$.
The support types are distinct in both cases:
An empty first class for $t$ is permitted: the task imposes the two-nonempty-class condition only on $b$. Thus the construction always produces an admissible instance with $\tau=2$.
All three parts of the claimed characterization are correct.
For an outcome in $B_1$, any dominator must also lie in $B_1$ to satisfy $b$’s weak preference requirement. Both types tie all outcomes within $B_1$, so no strict dominance is possible.
For an outcome in $H$, any dominator must also lie in $H$ to satisfy $t$’s weak preference requirement. Both types tie all outcomes within $H$, so again no strict dominance is possible. When $H$ is empty, this assertion is vacuous.
Every outcome in $B_2\setminus H$ is dominated by any outcome in $B_1$: $b$ strictly prefers the latter, and $t$ assigns both its second rank.
These sets exhaust the domain, establishing
$$
\operatorname{Opt}(\mu)=B_1\cup H.
$$
Since the union is disjoint, $|B_1|=2^n$, and $|H|=s$, the average-rank computation is correct:
$$
\operatorname{ar}_b(\operatorname{Opt}(\mu))
=\frac{2^n+2s}{2^n+s}
=1+\frac{s}{2^n+s}.
$$
The denominator is positive, and the expression exceeds $1$ exactly when $s>0$.
The choices $q=b$ and $x=\mu_t=\tfrac12$ are expressly allowed. They remove $t$ and leave $b$ with total mass $1$.
With only $b$ active, precisely the outcomes in $B_1$ are Pareto-optimal. Their average rank is $1$, strictly below the original average when $\varphi$ is satisfiable. This proves the required existential direction.
When $\varphi$ is unsatisfiable, the original average rank is $1$. The displayed bound
$$
\operatorname{ar}_b(Z)=1+\frac{|Z\cap B_2|}{|Z|}\geq1
$$
holds for every nonempty outcome set.
The nonemptiness justification is also valid. Each valid statement induces a total preorder; consequently, strict Pareto dominance is irreflexive and transitive. On the finite, nonempty outcome domain, it has an undominated outcome.
The lower bound therefore applies to every resulting society, regardless of the replacement statement or transfer amount. This establishes the universal impossibility needed for the no-direction.
The construction copies $\varphi$ only a constant number of times and introduces one attribute and constant-size mass data. Under standard encodings, its claimed $O(\ell)$ construction time and $L=O(\ell)$ output size are justified.
The equivalence proves a polynomial many-one reduction from SAT, hence $\mathrm{NP}$-hardness even with fixed support size $\tau=2$. The proof does not claim an upper bound or completeness result, neither of which is required by the task.
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.