The Convergence of Iterative Delegations in Liquid Democracy in a Social Network (d4-conf-sagt-2019-0003)

Given a finite type set \(T\), positive rational masses \(\mu\in\mathbb{Q}_{>0}^{T}\) with \(\sum_{t\in T}\mu_t=1\), and for each type \(t\) a strict order over \(\{\mathsf{self},\mathsf{abstain}\}\cup\{\mathsf{guru}(u):u\in T\}\), decide whether there exists a type-homogeneous complete-network delegation profile. Each type's entire mass votes, abstains, or delegates to a type; iterating these type actions determines each type's guru type, with delegation cycles producing abstention. Require pointwise, equivalently typewise, Nash stability: no agent of type \(t\) can improve by voting, abstaining, or delegating to an agent of any other type.

A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), summing to \(1\). Each type is nonatomic; \(\tau\) is the support size, not the number of possible types.
Each type \(t\) has an unrestricted strict order \(\succ_t\) over \(\{\mathsf{self},\mathsf{abstain}\}\cup\{\mathsf{guru}(u):u\in T\}\). Voting personally yields \(\mathsf{self}\); representation by another voter of type \(u\) yields \(\mathsf{guru}(u)\), including when \(u=t\).
A type-homogeneous profile assigns each type's entire mass one action: vote, abstain, or delegate to a type \(u\ne t\). The network is complete between distinct types. Following type actions ends at a voting type or at abstention; every chain entering a delegation cycle also produces abstention.
Write \(h_d(t)\) for the terminal voting type, or \(\bot\) for abstention. The current outcome of type \(t\) is \(\mathsf{self}\) if it votes, \(\mathsf{abstain}\) if \(h_d(t)=\bot\), and \(\mathsf{guru}(h_d(t))\) otherwise.
An individual deviation leaves every other agent's action fixed. Voting yields \(\mathsf{self}\), abstaining yields \(\mathsf{abstain}\), and delegating to another type \(u\) yields \(\mathsf{guru}(h_d(u))\) if \(h_d(u)\ne\bot\), otherwise \(\mathsf{abstain}\). This includes representation by another voter of the deviator's own type when that type votes. A profile is Nash-stable if no type strictly prefers any such deviation outcome to its current outcome.
Is deciding whether a Nash-stable type-homogeneous profile exists solvable in polynomial time, or is it NP-hard? State running times in \(m=\tau+2\), the number of outcome symbols per order, \(\tau\), and the total input bit length \(L\).
For finite societies with unrestricted strict preferences, equilibrium existence is NP-complete even on complete social networks. No result settling this exact nonatomic problem is established here.

Result

The problem is \(\mathrm{NP}\)-complete, even when every type ranks \(\mathsf{self}\) above both \(\mathsf{abstain}\) and \(\mathsf{guru}(t)\). The proof below applies directly to the stated nonatomic deviation semantics.

1. Exact characterization by the voting set

For a profile, let \(S\subseteq T\) be its set of voting types. Write \(g_u=\mathsf{guru}(u)\), \(s=\mathsf{self}\), and \(a=\mathsf{abstain}\).

Lemma. A Nash-stable profile with voting set \(S\) exists if and only if both conditions hold:

• For every \(t\in S\), we have \(s\succ_t a\) and \(s\succ_t g_u\) for every \(u\in S\).
• For every \(t\notin S\), either \(a\succ_t s\), or there exists \(u\in S\) with \(g_u\succ_t s\).

Proof. Fix any profile whose voting set is \(S\). The outcomes available to an individual of any type \(t\) are exactly
\(\{s,a\}\cup\{g_u:u\in S\}\).

Indeed, voting and abstaining supply \(s\) and \(a\). Every voting type \(u\ne t\) can be reached by direct delegation. If \(t\in S\), the stipulated deviation to another voter of type \(t\) also supplies \(g_t\). Conversely, every delegation outcome is either abstention or representation by a voting type.

Because preferences are strict, stability requires the current outcome to be the unique most preferred member of this set.

For \(t\in S\), its current outcome is \(s\), giving condition 1. For \(t\notin S\), its current outcome differs from \(s\), so some available outcome must rank above \(s\), giving condition 2.

For sufficiency, make every type in \(S\) vote. For each \(t\notin S\), choose its most preferred outcome in
\(\{a\}\cup\{g_u:u\in S\}\).
Condition 2 ensures that this outcome ranks above \(s\). If the chosen outcome is \(a\), let \(t\) abstain; otherwise, let it delegate directly to the corresponding \(u\in S\). Since \(t\notin S\), this delegation is permitted.

All delegations now terminate immediately at voters. Each voter receives its most preferred available outcome by condition 1, and each nonvoter does so by construction. Thus the profile is Nash-stable. \(\square\)

This characterization handles arbitrary input orders, including those placing \(g_t\) above \(s\).

2. Membership in \(\mathrm{NP}\) and running times

A certificate is the voting set \(S\), encoded by \(\tau\) bits. The lemma supplies a verifier without requiring delegation chains in the certificate.

Precompute inverse ranks for all \(\tau\) orders, each containing \(m=\tau+2\) symbols. Conditions 1 and 2 then require at most \(\tau^2\) constant-time rank comparisons.

On a standard word RAM, with words large enough for input indices:

• Reading the input and preparing ranks takes \(O(L+\tau m)\) time.
• Checking a voting set after preprocessing takes \(O(\tau^2)\) time.
• The complete certificate verifier takes \(O(L+\tau m)\) time.
• Enumerating all voting sets decides existence in \(O(L+2^\tau\tau m)\) time.

Equivalently, the last bound is \(O(L+2^{m-2}(m-2)m)\). The rank table uses \(O(\tau m)\) words. These bounds imply polynomial certificate verification in the total input bit length \(L\).

Masses do not appear in the stability conditions: their positivity supports the stated nonatomic interpretation, but their numerical values do not affect any comparison.

3. Reduction from directed kernel existence

For a finite loopless digraph \(D=(V,E)\), a kernel is a set \(S\subseteq V\) satisfying:

• Independence: no arc has both endpoints in \(S\).
• Absorption: every \(v\notin S\) has an outgoing arc to some vertex in \(S\).

Kernel existence is \(\mathrm{NP}\)-complete for finite loopless digraphs. The standard satisfiability construction is recalled below; see [Chvátal’s account](https://users.encs.concordia.ca/~chvatal/kernel.html).

Given such a digraph, create one type for each vertex. For type \(t\), impose the strict order
\(\{g_u:(t,u)\in E\}\succ_t s\succ_t a\succ_t\{g_u:(t,u)\notin E\}\),
ordering each displayed block arbitrarily but strictly.

Thus
\(g_u\succ_t s\) if and only if \((t,u)\in E\).
Because the graph is loopless, \(s\succ_t g_t\).

Let \(N=|V|=\tau\). To ensure valid masses even if “binary rational” means dyadic rational, put \(k=\lceil\log_2N\rceil\). Give the first \(N-1\) types mass \(2^{-k}\), and the last type mass
\((2^k-N+1)2^{-k}\).
All masses are positive, sum to \(1\), and have \(O(\log N)\)-bit encodings.

Apply the lemma:

• For \(t\in S\), condition 1 says precisely that no outgoing arc from \(t\) ends in \(S\).
• For \(t\notin S\), condition 2 requires an outgoing arc into \(S\), since every type prefers \(s\) to \(a\).

Consequently, the constructed society has a Nash-stable type-homogeneous profile if and only if \(D\) has a kernel.

The construction outputs \(\tau m\) preference symbols and \(O(\tau\log\tau)\) mass bits. With binary type identifiers, its total output length is \(O(\tau m\log m)\), and it is computable in polynomial time. The delegation network is complete, as required; the digraph encodes preferences, not network restrictions.

4. Explicit satisfiability gadget

For completeness, the kernel source problem has the following reduction from \(\mathrm{3SAT}\).

For each variable \(x_i\), introduce vertices \(x_i,\neg x_i\) and both arcs between them. For each clause \(C_j\), introduce a directed triangle \(c_{j,0}\to c_{j,1}\to c_{j,2}\to c_{j,0}\). From every triangle vertex, add arcs to all literals occurring in \(C_j\). Add no other arcs.

Independence and absorption force exactly one vertex from each variable pair into any kernel: both are forbidden, while neither leaves the pair unabsorbed.

Suppose a clause has no selected literal. Its triangle cannot contain two selected vertices, since every pair is adjacent. It cannot contain none, since absorption then fails. If it contains exactly \(c_{j,k}\), vertex \(c_{j,k+1}\), with indices modulo \(3\), has no outgoing arc into the kernel. Thus every clause must contain a selected literal.

Conversely, a satisfying assignment selects one literal per variable and no triangle vertices. This set is independent, absorbs each unselected literal through its opposite, and absorbs every triangle vertex through a satisfying literal. It is a kernel.

The graph is loopless and has \(2n+3q\) vertices for \(n\) variables and \(q\) clauses.

5. Conclusion

Combining polynomial certificate verification with the reduction proves \(\mathrm{NP}\)-completeness. Therefore a polynomial-time algorithm in \(L\) exists only if \(\mathrm{P}=\mathrm{NP}\).

The conclusion follows from the exact nonatomic model, including access to another voter of one’s own type; it does not rely on transferring the finite-society equilibrium theorem.

⟨structured verdict parsed — rendered above⟩

The argument establishes NP-completeness in substance. The voting-set characterization and both reductions are correct under the stated nonatomic deviation semantics. There is one minor domain omission: the graph-to-society construction must explicitly restrict its source to nonempty graphs.

• Voting-set characterization: correct.

For a fixed voting set \(S\), voting and abstaining always make \(s\) and \(a\) available. Every \(u\in S\) distinct from the deviating type is reachable by direct delegation. When the deviating type itself belongs to \(S\), the task expressly permits representation by another voter of that type, making \(g_t\) available as well.

Conversely, under the stipulated deviation semantics, delegation can yield only abstention or representation by a type already in \(S\). Thus the available outcome set is exactly
\[ \{s,a\}\cup\{g_u:u\in S\}. \]
Strict preferences make its maximum unique.

For voters, requiring this maximum to be \(s\) gives condition 1, including the necessary comparison against \(g_t\). For nonvoters, the current outcome belongs to this set and differs from \(s\). Stability therefore requires an available outcome strictly above \(s\), exactly as expressed in condition 2.

The sufficiency construction is valid: every nonvoter chooses its best outcome among abstention and representation by voters. Condition 2 places that outcome above \(s\). Direct delegation is permitted because the delegating type lies outside \(S\), while its recipient lies inside \(S\). The resulting profile has exactly the claimed voting set and gives every type its best available outcome.

The lemma also handles \(S=\varnothing\): condition 2 then requires every type to prefer abstention to voting, and the construction makes every type abstain.

• Certificate verification and running times: correct.

A voting set uses \(\tau\) certificate bits. With inverse preference ranks, condition 1 requires at most \(\tau|S|\) relevant comparisons, and condition 2 requires at most \(\tau|S|\) further comparisons. Consequently, the stated \(O(\tau^2)\) verification bound is valid.

Since \(m=\tau+2\), this verification cost is absorbed by \(O(\tau m)\). The complete bound \(O(L+\tau m)\) correctly includes input reading and preprocessing. Enumerating all \(2^\tau\) voting sets gives the stated bound
\[ O(L+2^\tau\tau m) = O(L+2^{m-2}(m-2)m). \]
The rank-table space bound \(O(\tau m)\) words is also correct. These are explicitly word-RAM bounds, and the resulting certificate verification is polynomial in \(L\).

Mass values play no role in the preference comparisons or deviation outcomes specified by the task. Omitting them from the stability conditions is justified.

• Reduction from kernel existence: correct for nonempty source graphs.

The displayed preference blocks partition all guru symbols and place precisely the outgoing neighbors above \(s\). Ordering within each block strictly produces valid unrestricted strict orders. Looplessness puts \(g_t\) below \(s\), while the construction also puts \(a\) below \(s\), establishing the advertised restriction.

For selected types, condition 1 excludes every arc whose two endpoints belong to \(S\). This is precisely kernel independence. For unselected types, \(a\succ_t s\) is false, so condition 2 requires an outgoing arc into \(S\). This is precisely absorption. Both directions of the claimed equivalence follow.

For \(N\geq1\), the mass construction is valid. Its last numerator satisfies
\[ 1\leq 2^k-N+1\leq 2^k, \]
and the masses sum to
\[ (N-1)2^{-k}+(2^k-N+1)2^{-k}=1. \]
In particular, \(N=1\) gives a single mass equal to \(1\). The encoding-size and polynomial-construction claims are valid.

Minor issue: the source is described as an arbitrary finite loopless digraph, which allows \(N=0\). Then \(\lceil\log_2N\rceil\) is undefined, and the construction cannot produce the task’s required nonempty society. The minimum clarification is to state that the reduction uses nonempty loopless digraphs and that the satisfiability source is restricted to instances with at least one variable. This is a routine domain restriction; it does not require a new hardness argument.

• Explicit satisfiability gadget: correct.

Each literal vertex has only its opposite literal as an outgoing neighbor. Independence forbids selecting both members of a variable pair, while absorption forbids selecting neither. Exactly one is therefore selected.

If a clause has no selected literal, its triangle can contain at most one selected vertex because every pair has an arc between them. Selecting none violates absorption. If exactly \(c_{j,k}\) is selected, then \(c_{j,k+1}\) has only its successor and clause literals as outgoing neighbors; none is selected. Absorption again fails. Thus every clause has a selected literal.

Conversely, the literal set supplied by a satisfying assignment is independent, absorbs every unselected literal through its opposite, and absorbs every triangle vertex through a selected clause literal. The graph is loopless, and its stated vertex count is correct.

The cited [Chvátal account](https://users.encs.concordia.ca/~chvatal/kernel.html) confirms the kernel definition, NP-completeness claim, and this gadget construction. The write-up also supplies the necessary reduction explicitly, so its substantive correctness does not depend on an unexplained citation.

• Conclusion: justified, subject only to the minor domain clarification.

Polynomial certificate verification establishes membership in NP. The verified reductions establish NP-hardness for the exact nonatomic model, including access to another voter of one’s own type. The finite-society theorem is not used. The conclusion about a polynomial-time algorithm implying \(\mathrm{P}=\mathrm{NP}\) follows.

⟨structured verdict parsed — rendered above⟩