| paper | The Convergence of Iterative Delegations in Liquid Democracy in a Social Network |
| authors | B. Escoffier, Hugo Gilbert, Adèle Pass-Lanneau |
| venue | SAGT 2019 |
| filed under | frontier · opinion-networks |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\) · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
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 finite type distribution \((T,\mu)\), type preferences over self, abstention, and guru types, and a type-level action \(\delta:T\to T\cup\{\mathsf{vote},\mathsf{abstain}\}\); the objective is feasibility of a stable \(\delta\), with every voting guru type carrying positive mass.
The literal atomless almost-everywhere formulation admits null-measure voting gurus and makes a directed \(3\)-cycle appear stable; it therefore needs pointwise type-level stability, positive-mass active guru types, and finite type-level delegation chains.
fatal: False
The mirror covers Theorem 1 and its complete-network kernel characterization, but not Theorems 2–12, the tree dynamic programs, or the convergence results.
The strongest honest case is a narrow but genuine mirror of the paper’s complete-network equilibrium problem.
My lead anchor is Theorem 1, proved in this paper: EX is NP-complete even when the social network is complete. EX takes a preference profile \(P\) and a social network \(\mathcal{G}_{\mathtt{SN}}\), and asks whether there exists a Nash-stable delegation function. The proof uses the paper’s Proposition 1: on a complete network, a set of gurus \(K\) is realizable exactly when \(K\) contains no abstainer and is a kernel of the delegation-acceptability digraph—independent, and absorbing every non-abstainer. The proof then invokes the cited NP-completeness of directed-kernel existence, but Theorem 1 itself is established here.
The continuous mirror I would propose is Type-Continuous Complete-Network Equilibrium Existence.
An instance consists of a finite set of voter types \(T\), a rational mass distribution \(\mu\in\mathbb{Q}_{\ge 0}^{T}\) with \(\sum_{t\in T}\mu_t=1\), and, for each type \(t\), a strict preference order over \(\mathsf{self}\), \(\mathsf{abstain}\), and guru classes \(\mathsf{guru}(u)\) for \(u\in T\). A type is complete: all agents of type \(t\) have the same preferences and the same access rights. The population is the atomless space \(\Omega=\bigsqcup_{t\in T}\Omega_t\), where \(\Omega_t\) has mass \(\mu_t\). The social network is complete: every two distinct agents may delegate directly to one another.
The action variable is a measurable delegation function \(d\). Each agent may vote, abstain, or delegate to another agent. Gurus are obtained by following delegation chains, with cycles treated as abstention as in the paper. An admissible profile requires every chain to reach a voter, abstention, or finite cycle. A solution is a profile \(d\) such that almost every agent has no strictly profitable unilateral change. The objective is feasibility: does such a stable profile exist?
This is a natural high-multiplicity regime. One plausible setting is a very large online liquid-democracy community in which members fall into a small number of recurring trust or competence types. For example, there may be millions of members but only \(\tau\) preference archetypes, each ranking guru classes rather than named individuals. The type description includes the ranking over guru classes, the preference for voting or abstaining, and the fact that everyone is reachable in the platform. Thus \(N\) may be arbitrarily larger than \(\tau\), while the input describes only \(\mu\) and the type preferences.
The hardness transfers directly. Given a loop-free digraph \(D=(T,A)\), create one population type for each vertex, give every type positive mass—for example \(\mu_t=1/|T|\)—and use a complete social network. Type \(t\) regards \(\mathsf{guru}(u)\) as better than voting exactly when \((t,u)\in A\); voting is better than abstaining and better than every non-acceptable guru. A type-\(t\) agent strictly prefers voting to being represented by another type-\(t\) agent.
If \(K\) is a kernel of \(D\), every agent of a type in \(K\) votes, and every other type delegates directly to its preferred acceptable type in \(K\). This is stable: no two active types accept one another, and every inactive type has an acceptable active guru.
Conversely, in any stable continuous profile, let \(K\) be the types containing voters. Two types in \(K\) cannot have an arc between them, since the source type would prefer to delegate to the other active type. Every type outside \(K\) must have an arc to \(K\); otherwise its agents would prefer to vote rather than accept any available guru. Hence \(K\) is a kernel. The continuous problem therefore remains NP-hard even with uniform masses and arbitrarily many agents per type. In the finite type-level formulation, \(K\) is also a polynomial certificate, so NP-completeness is the expected classification.
I would classify this as Class B: hardness transfers. The reduction’s combinatorics live in the type-level acceptability relation, not in population multiplicity. That is not a failure of the mirror: it answers exactly whether the paper’s equilibrium-existence hardness survives when a large society is represented by a distribution over repeated voter types.
The original authors should recognize this as their problem. The delegation action, transitivity, guru formation, unilateral deviations, complete network, and Nash-stability condition are unchanged. Only the population representation changes from named voters to masses of agents sharing complete preference types. This is not outcome-space continuity: every individual still makes an integral choice to vote, abstain, or delegate; only the society is represented continuously.
The scope is intentionally limited to Theorem 1 and its kernel characterization. I would not claim that the paper’s tree dynamic programs automatically continuize: replacing every tree vertex by a positive-mass type changes the network structure and needs a separate model. Nor would I use the convergence theorems as anchors, since they are qualitative rather than computational complexity results.
The main weakness is that the mirror deliberately removes identity-specific preferences. If the authors insist that a voter’s ranking of gurus must distinguish every named individual, then a small type space is no longer appropriate. Moreover, the resulting hardness is essentially hardness over the number of types, not over the total population. That makes this a transfer result rather than an example where continuity dissolves discrete hardness. Still, the objection is precisely the high-multiplicity objection itself; in a plausible archetype-based liquid-democracy platform, type-level guru preferences are defensible.
Natural follow-ups include weighted minimum dissatisfaction, minimizing abstaining mass, membership of a designated guru type, and convergence of mass-level delegation dynamics. For example, dissatisfaction could be \(D(d)=\sum_{t\in T}\mu_t\operatorname{rk}_t(g_d(t))\), and abstention could be the total mass \(\lambda(\{\omega:g_d(\omega)=0\})\). A further programme-level question is whether finite populations with \(q\) copies of every type converge, as \(q\to\infty\), exactly to the continuous equilibrium problem above.
The strongest objection is to the proposed mirror’s atomless equilibrium notion, not to the underlying idea.
In the paper, gurus are named individuals, and every voter’s deviation is checked. In an atomless population, however, a single voter can be a guru for a positive mass while herself having measure zero. If stability is required only almost everywhere, the kernel argument fails. For a directed \(3\)-cycle of types \(a,b,c\), choose one null agent of each type to vote, and let almost every \(a\)-agent delegate to the \(b\)-agent, almost every \(b\)-agent to the \(c\)-agent, and almost every \(c\)-agent to the \(a\)-agent. Every positive-mass agent receives her preferred guru, while the three unstable root agents are ignored. Thus the continuous instance has an a.e. equilibrium although the type digraph has no kernel.
The obvious repairs are substantial: require pointwise rather than a.e. stability, forbid zero-mass gurus, require positive voting mass for every active guru type, and exclude infinite delegation chains. Alternatively, impose type-homogeneous strategies. Those conditions restore a kernel-style theorem, but they also reveal the conceptual cost: the model is no longer the paper’s identity-sensitive game. It is a new anonymous game in which “guru \(u\)” has been replaced by “guru of type \(u\).” The paper’s arbitrary preferences over named gurus and its individual delegation structure have been quotiented away.
That is a real criticism of the proponent’s formulation, but it does not defeat the best mirror. A large platform with recurring trust or competence archetypes is a plausible high-multiplicity regime, and the authors’ own examples—geographic, cultural, political, or religious reasons for choosing gurus—support such a quotient. With positive-mass active guru types, the complete-network problem is a legitimate continuous-population version, and Theorem 1’s kernel hardness transfers. The fact that the masses do not affect feasibility is not an admissible objection: it is still a well-posed Class B question.
So the honest negative case is weak. I can reject the stated a.e. construction, but not the repaired type-level mirror. Theorem 1 remains a genuine surviving anchor, and I would not claim that this paper has no worthwhile continuous mirror.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.