d4-conf-ecai-2024-0151 (d4-conf-ecai-2024-0151)

Given an agenda \(\Phi\), integrity constraint \(\Gamma\), target literal \(\ell\), budget \(\beta\), and rational fixed and eligible masses over complete \(\Gamma\)-consistent judgment sets, decide whether eligible mass can be transferred between judgment types so that at most \(\beta\) mass changes and every continuous Young outcome contains \(\ell\). The resulting mass at type \(K\) is \(\mu'_K=\mu^{\mathrm{fixed}}_K+\sum_J x_{J,K}\), where transfers satisfy \(\sum_{J'}x_{J,J'}=\mu^{\mathrm{eligible}}_J\) and \(\sum_{J\ne J'}x_{J,J'}\le\beta\). Continuous Young outcomes are all complete \(\Gamma\)-consistent judgment sets extending the strict-majority set of any maximum-mass retained subdistribution \(\rho\le\mu'\) whose majority set is \(\Gamma\)-consistent.

Let \(X\) contain \(m\ge1\) propositional issues, \(\Phi=X\cup\{\neg x:x\in X\}\), and let the input integrity constraint \(\Gamma\) be a propositional formula, possibly using auxiliary variables. Write \(\mathcal J\) for all judgment sets containing exactly one literal per issue and satisfying \(\Gamma\wedge\bigwedge_{a\in J}a\); consistency means satisfiability, including existential assignment of auxiliary variables.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here each listed \(J\in\mathcal J\) has nonnegative fixed and eligible masses \(f_J,e_J\), with \(f_J+e_J>0\) and \(\sum_J(f_J+e_J)=1\); unlisted types have zero input mass. The support size \(\tau\) is not the number of possible types. Let \(L\) be the total input bit length, including \(\Gamma\), masses, and budget.
Given \(\ell\in\Phi\) and a binary rational budget \(\beta\ge0\), an admissible change uses nonnegative real transfers \(x_{J,K}\), from initially eligible types to any \(K\in\mathcal J\), satisfying \(\sum_{K\in\mathcal J}x_{J,K}=e_J\) and \(\sum_J\sum_{K\ne J}x_{J,K}\le\beta\). The resulting mass is \(\mu'_K=f_K+\sum_Jx_{J,K}\).
For a nonnegative real retained subdistribution \(0\le\rho\le\mu'\), define \(M(\rho)=\{a\in\Phi:\sum_{K:a\in K}\rho_K>\tfrac12\sum_K\rho_K\}\). Ties contribute neither literal; the zero subdistribution is allowed. Among all retained subdistributions with \(\Gamma\)-consistent \(M(\rho)\), maximize \(\sum_K\rho_K\).
The continuous Young outcomes are all \(H\in\mathcal J\) extending \(M(\rho)\) for any such maximizer, with every maximizer and every consistent completion included.

Is deciding whether an admissible change makes every continuous Young outcome contain \(\ell\) solvable in polynomial time in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?

For finite societies, Young manipulation and bribery with a specified set of eligible agents are \(\Sigma_2^p\)-complete, even for a single target literal ([Conati et al., 2024](https://www.cs.helsinki.fi/u/mjarvisa/papers/cnhj.ecai24.pdf)).
No result settling this exact continuous transfer problem was located in the literature search.

Result

The problem is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions. This holds even with:

• exactly six input types;
• no auxiliary variables in \(\Gamma\);
• budget and total eligible mass both equal to \(1/20\);
• explicitly given consistent types containing each of \(p\) and \(\neg p\);
• an initial society that does not already guarantee the target.

Thus a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).

1. Maximizers exist

For any resulting distribution \(\mu'\), write \(R=\sum_K\rho_K\). For a complete consistent judgment \(H\), the condition \(M(\rho)\subseteq H\) is equivalent to
\[ \sum_{K:a\in K}\rho_K\ge R/2 \qquad\text{for every }a\in H. \]
Indeed, these inequalities say precisely that no literal opposite to one in \(H\) has a strict majority.

A partial judgment \(M(\rho)\) is \(\Gamma\)-consistent exactly when it has some completion \(H\in\mathcal J\): a satisfying assignment of \(\Gamma\wedge\bigwedge_{a\in M(\rho)}a\) supplies that completion, including any auxiliary-variable assignment.

Consequently, the feasible retained subdistributions form a finite union, over \(H\in\mathcal J\), of closed polytopes inside the bounded box \(0\le\rho\le\mu'\). This union contains the zero subdistribution and is compact. The retained-mass objective therefore attains its maximum, and every maximizer has at least one consistent completion.

2. Reduction from satisfiability

Let \(F(y_1,\ldots,y_n)\) be a Boolean formula whose satisfiability is to be decided. We may assume \(n\ge1\), adding an unused variable if necessary.

Set
\[ X=\{p,r,s,y_1,\ldots,y_n\}, \qquad \Gamma=\neg p\vee\neg r\vee\neg s\vee F(y_1,\ldots,y_n). \]
The target is \(\ell=p\).

We identify complete judgments with their truth assignments. Let \(\mathbf0\) and \(\mathbf1\) denote the assignments setting every \(y_j\) to zero and one, respectively. The six input types and their masses are:

| Type | \(p\) | \(r\) | \(s\) | Assignment to the \(y_j\) | Fixed mass | Eligible mass |
|---|---|---|---|---|---|---|
| \(A_0\) | \(1\) | \(0\) | \(1\) | \(\mathbf0\) | \(1/8\) | \(0\) |
| \(A_1\) | \(1\) | \(0\) | \(1\) | \(\mathbf1\) | \(1/8\) | \(0\) |
| \(B_0\) | \(1\) | \(1\) | \(0\) | \(\mathbf0\) | \(1/8\) | \(0\) |
| \(B_1\) | \(1\) | \(1\) | \(0\) | \(\mathbf1\) | \(1/8\) | \(0\) |
| \(C_0\) | \(0\) | \(1\) | \(1\) | \(\mathbf0\) | \(9/40\) | \(1/40\) |
| \(C_1\) | \(0\) | \(1\) | \(1\) | \(\mathbf1\) | \(9/40\) | \(1/40\) |

Set \(\beta=1/20\).

Every listed type satisfies \(\Gamma\), independently of \(F\): the \(A_i\) satisfy \(\neg r\), the \(B_i\) satisfy \(\neg s\), and the \(C_i\) satisfy \(\neg p\). Their total mass is
\[ 4(1/8)+2(9/40+1/40)=1. \]
Their total eligible mass is \(1/20\).

The construction has \(m=n+3\), \(\tau=6\), constant-size rational masses, and polynomial total encoding length. There are no auxiliary variables.

3. The initial society is unsuccessful

Initially, the masses supporting \(p,r,s\) are respectively
\[ 1/2,\qquad 3/4,\qquad 3/4. \]
Each \(y_j\) has supporting mass \(1/2\), because each pair of types has equal masses.

Thus the full society has majority judgment
\[ M(\mu)=\{r,s\}. \]
This is consistent: either \(C_i\) completes it. Retaining the full mass is therefore feasible and optimal. Because \(C_i\) contains \(\neg p\), the initial outcomes do not all contain \(p\).

4. Satisfiable formulas yield successful changes

Suppose \(F\) is satisfiable. Transfer all eligible mass of \(C_i\) to \(A_i\), for each \(i\in\{0,1\}\):
\[ x_{C_i,A_i}=1/40. \]
Every source-row constraint is satisfied, and the transferred mass is \(1/20=\beta\). The destinations are consistent types already present in the input.

The resulting total masses of the three pairs are
\[ \mu'(A_0)+\mu'(A_1)=3/10,\qquad \mu'(B_0)+\mu'(B_1)=1/4,\qquad \mu'(C_0)+\mu'(C_1)=9/20. \]
Hence the masses supporting \(p,r,s\) are
\[ 11/20,\qquad 7/10,\qquad 3/4, \]
respectively. Each \(y_j\) still has supporting mass \(1/2\), since the transfers preserve equality within each pair. Therefore
\[ M(\mu')=\{p,r,s\}. \]

Under \(p=r=s=1\), the constraint \(\Gamma\) reduces to \(F\). Our satisfiability assumption consequently makes \(M(\mu')\) consistent. Retaining mass \(1\) is feasible and optimal.

Furthermore, any retained subdistribution of mass \(1\) must equal \(\mu'\): the nonnegative differences \(\mu'_K-\rho_K\) sum to zero. Thus every maximizer has majority judgment \(\{p,r,s\}\), and every consistent completion contains \(p\). The change is successful.

5. Unsatisfiable formulas exclude every successful change

Suppose now that \(F\) is unsatisfiable. Then every consistent complete judgment satisfies
\[ \neg p\vee\neg r\vee\neg s. \]
Consider any admissible change, including arbitrary splitting into new consistent destination types.

A bound on retained mass admitting a target-positive completion

The fixed mass supporting \(\neg r\) is exactly \(1/4\), from the \(A_i\). Since the total eligible mass is \(1/20\), after any change,
\[ \sum_{K:\neg r\in K}\mu'_K\le 1/4+1/20=3/10. \]
Likewise,
\[ \sum_{K:\neg s\in K}\mu'_K\le3/10. \]

Let \(\rho\le\mu'\) have retained mass \(R\), and suppose \(M(\rho)\) has a consistent completion \(H\) containing \(p\). Consistency forces \(H\) to contain \(\neg r\) or \(\neg s\).

If \(\neg r\in H\), then \(r\notin M(\rho)\), because \(H\) extends \(M(\rho)\). Thus the retained mass supporting \(r\) is at most \(R/2\), so the retained mass supporting \(\neg r\) is at least \(R/2\). Consequently,
\[ R/2 \le\sum_{K:\neg r\in K}\rho_K \le\sum_{K:\neg r\in K}\mu'_K \le3/10, \]
giving \(R\le3/5\). The case \(\neg s\in H\) gives the same bound.

Therefore every retained subdistribution admitting a consistent completion containing \(p\) has mass at most \(3/5\).

An invariant feasible retained mass of \(9/10\)

After every change, all fixed masses remain available. Define \(\rho^*\) by retaining
\[ \rho^*_{A_i}=\rho^*_{B_i}=9/80, \qquad \rho^*_{C_i}=9/40, \qquad i\in\{0,1\}, \]
and zero at every other type. These amounts do not exceed the respective fixed masses, so \(\rho^*\le\mu'\) after every change.

Its total mass is
\[ R^*=4(9/80)+2(9/40)=9/10. \]
The retained supporting masses are
\[ p:\ 9/20,\qquad r:\ 27/40,\qquad s:\ 27/40,\qquad y_j:\ 9/20. \]
Thus \(p\) and every \(y_j\) tie, whereas \(r\) and \(s\) have strict majorities:
\[ M(\rho^*)=\{r,s\}. \]
This majority judgment has the consistent completion \(C_0\). Hence the optimum retained mass is at least \(9/10\).

Since \(9/10>3/5\), no maximizing retained subdistribution can admit a consistent completion containing \(p\). By Section 1, maximizers and their completions exist. In fact, every continuous Young outcome contains \(\neg p\), after every admissible change.

6. Conclusion

The constructed instance admits a successful change if and only if \(F\) is satisfiable. This proves \(\mathrm{NP}\)-hardness of the exact continuous transfer problem.

The proof handles arbitrary real transfers and every maximizing subdistribution and completion. It does not establish a matching complexity upper bound, which is unnecessary for the requested hardness conclusion.

⟨structured verdict parsed — rendered above⟩

The proof correctly establishes \(\mathrm{NP}\)-hardness of the stated continuous transfer problem. All computations and quantifiers check out, including arbitrary real transfers, all maximizing retained subdistributions, and all consistent completions. No major or minor issues were found.

1. Existence and characterization of maximizers

For each issue, retained support for its two literals sums to the total retained mass \(R\). Consequently, for a complete judgment \(H\), the inequalities
\[ \sum_{K:a\in K}\rho_K\ge R/2\qquad(a\in H) \]
are exactly equivalent to the absence of a strict majority for any literal opposite to \(H\). This proves the claimed equivalence with \(M(\rho)\subseteq H\), including ties and \(R=0\).

The completion characterization of consistency is also correct when auxiliary variables occur: a satisfying assignment supplies the issue literals of a complete judgment and the required auxiliary-variable values.

There are finitely many complete judgments because there are finitely many issues. For each consistent \(H\), the retained distributions satisfying these inequalities form a closed, bounded polytope. Their finite union is compact. It is nonempty because the valid input supplies consistent judgments, and the zero subdistribution satisfies every inequality. The continuous retained-mass objective therefore attains its maximum. Every feasible maximizer has a consistent completion.

This is an existence argument; it does not incorrectly claim that enumerating those polytopes is polynomial time.

2. Validity and size of the reduction

The reduction produces exactly six distinct types. The assumption \(n\ge1\) ensures that the assignments \(\mathbf0\) and \(\mathbf1\) differ within each pair; different pairs differ on \(p,r,s\).

Every input type satisfies \(\Gamma\), irrespective of \(F\), through the stated disjunct. All masses are nonnegative, every listed type has positive total mass, and
\[ 4(1/8)+2(9/40+1/40)=1. \]
The eligible mass and budget both equal \(1/20\).

The construction has \(n+3\) issues, six explicitly encoded types, constant-size rational masses, and a constraint containing one copy of \(F\). Its encoding length and construction time are polynomial in the SAT input length. Adding an unused variable preserves satisfiability.

3. Initial outcomes

The initial support totals are correctly computed:
\[ p:1/2,\qquad r:3/4,\qquad s:3/4,\qquad y_j:1/2. \]
Thus \(M(\mu)=\{r,s\}\). This majority judgment has the consistent completions \(C_i\), which contain \(\neg p\).

Retaining the entire distribution achieves the largest possible mass, namely \(1\). Therefore a target-negative outcome exists initially, as claimed.

4. Satisfiable case

The proposed transfers exhaust each positive eligible source row. All other transfers may be zero, satisfying the zero-eligible rows as well. Both destinations are valid, distinct from their sources, and the total moved mass equals the budget.

The resulting pair masses are correctly computed as \(3/10,1/4,9/20\). They give
\[ p:11/20,\qquad r:7/10,\qquad s:3/4. \]
Equality of the masses within each pair keeps every \(y_j\) tied. Hence \(M(\mu')=\{p,r,s\}\).

Under these three literals, \(\Gamma\) reduces to \(F\), so satisfiability of \(F\) makes the full retained distribution feasible. Its retained mass is \(1\).

The uniqueness assertion at retained mass \(1\) is valid: finitely many nonnegative differences \(\mu'_K-\rho_K\) with sum zero must all vanish. Consequently, every maximizer equals \(\mu'\), and every consistent completion contains \(p\). This proves success with the required universal quantification over outcomes.

5. Unsatisfiable case

If \(F\) is unsatisfiable, every consistent judgment containing \(p\) must contain \(\neg r\) or \(\neg s\).

The fixed support for either \(\neg r\) or \(\neg s\) is exactly \(1/4\). All eligible mass together is only \(1/20\), so each resulting support is at most \(3/10\), regardless of transfer destinations or splitting.

If a retained distribution of mass \(R\) admits a consistent completion containing \(p\), one of those negative literals belongs to that completion. Its opposite therefore cannot have a strict retained majority, requiring retained support for the negative literal of at least \(R/2\). The bound
\[ R/2\le3/10 \]
correctly gives \(R\le3/5\).

The proposed invariant distribution \(\rho^*\) is componentwise bounded by the fixed masses and thus remains available after every change. Its calculations are correct:
\[ R^*=9/10,\qquad p:9/20,\qquad r:s:27/40,\qquad y_j:9/20. \]
Accordingly, its majority judgment is \(\{r,s\}\), with consistent completion \(C_0\). Every resulting distribution therefore has optimum retained mass at least \(9/10\).

Since \(9/10>3/5\), no maximizer can admit a consistent completion containing \(p\). Maximizers and completions exist by Section 1; completeness then forces every outcome to contain \(\neg p\). This excludes every admissible successful change.

6. Complexity conclusion

The construction is a polynomial-time many-one reduction from propositional satisfiability: satisfiable formulas yield yes-instances, and unsatisfiable formulas yield no-instances. It establishes the requested hardness conclusion, including all advertised restrictions. A matching upper bound is not needed to resolve the task’s hardness alternative.

⟨structured verdict parsed — rendered above⟩