Incentive-Compatible Selection for One or Two Influentials

The strongest positive case is a typed, high-multiplicity referral-network mirror. It is not a mirror of arbitrary labelled DAGs: it is a mirror for platforms, referral schemes, or citation networks in which many agents occupy a small number of repeated network roles.

The paper contains no numbered \(P\)/\(NP\), FPT, or hardness theorem. Its qualifying anchors are algorithmic mechanism-design results: explicit mechanisms with incentive-compatibility and approximation guarantees. My lead anchor is Theorem 2, proved in this paper; the second is Theorem 8, also proved here.

Take a finite set of network-role types \(\mathcal T\), a rational mass vector \(\mu\in\mathbb Q_{\ge0}^{\mathcal T}\), and a finite DAG \(H\) on \(\mathcal T\). An arc \(a\to b\) means that every agent of role \(a\) follows the corresponding role \(b\). Thus \(H\) is a repeated role-template, and \(\mu_a\) is the fraction of the population in role \(a\). Let

\[ p_\mu(a)=\sum_{b\neq a:\,b\leadsto_H a}\mu_b \]

be the fraction of the population in roles that can reach \(a\), hence the continuous progeny of \(a\). A vanishing \(1/N\) term may be added when exact finite-clone self-counting or tie-breaking is required.

The decision variable is a lottery over at most \(k\) selected role-members. Equivalently, let \(q_a\) be the expected number of selected members of role \(a\), with \(\sum_a q_a\le k\). The objective is

\[ W(q)=\sum_{a\in\mathcal T}q_a p_\mu(a), \]

against the benchmark consisting of the \(k\) largest progeny values. A lottery over roles is implemented by selecting a role according to \(q\) and then selecting a uniformly random member of that role.

The strategic condition is cohort incentive compatibility: a positive-mass role cohort may hide any allowed subset of its outgoing template edges, and its selection probability may not increase. This is the natural extension for a platform where referral policies are controlled by departments, firms, chapters, or other repeated cohorts. Clearing denominators in \(\mu\) gives a finite population of clones, and the continuous objective is the finite expected progeny divided by population size.

My lead problem is \(\mathrm{Cohort\text{-}LM}_{\infty}\), the continuous one-delegate analogue of Theorem 2. Given \((\mathcal T,\mu,H)\), compute the first-influential role set

\[ S^{\mathrm{inf}}_{1,\infty} =\{a\in\mathcal T:\text{after hiding }a\text{'s outgoing edges, fewer than one role outranks }a\}, \]

ordered as \(a_1\succ\cdots\succ a_m\) by \(p_\mu\) and the fixed tie-break rule. For a chosen \(\beta\in[1/2,1]\), output the role lottery

\[ q_{a_m}=\beta,\qquad q_{a_t}=(1-\beta)\log_2\!\left(\frac{p_\mu(a_t)}{p_\mu(a_{t+1})}\right) \quad (t<m), \]

with all other \(q_a=0\). The solution must satisfy \(\sum_a q_a\le1\), cohort IC, and

\[ \frac{W(q)}{\operatorname{OPT}_1(\mu,H)} \ge \min\!\left\{ \frac12\left(\beta+\frac{1-\beta}{\ln 2}\right),\, \beta \right\}. \]

At \(\beta=1/(1+\ln2)\), the target ratio is \(1/(1+\ln2)\). This is precisely the weighted form of the paper’s \(\beta\)-LM calculation; the appearance of logarithms and the integral argument in Theorem 2 already make the mass formulation feel native rather than artificial. Theorem 1 supplies the corresponding incentive-compatibility result, while Theorem 2 supplies the approximation guarantee. Both are proved here.

I expect canonical \(\mathrm{Cohort\text{-}LM}_{\infty}\) evaluation to be Class A. Reachability, progeny values, influential-role computation, and the lottery can all be computed in time polynomial in \(\tau\), the size of \(H\), the bit length of \(\mu\), and the requested output precision. The more interesting open problem is mechanism synthesis: whether the optimal fair cohort-IC ratio remains exactly \(1/(1+\ln2)\), and whether the upper bound imported through Corollary 1 and Zhang et al. [2021] survives this typed continuum.

The second problem is \(\mathrm{Cohort\text{-}LALD}_{\infty}\), mirroring Theorems 7 and 8. Given \((\mathcal T,\mu,H)\), compute both \(S^{\mathrm{inf}}_{1,\infty}\) and \(S^{\mathrm{inf}}_{2,\infty}\), then output the two-delegate lottery prescribed by LALD.

If the two influential sets coincide, write the common set as \(a_1\succ\cdots\succ a_m\). The expected selection counts are

\[ q_{a_m}=1,\qquad q_{a_{m-1}}=\frac{1}{1+\ln2}, \]

and, for \(t<m-1\),

\[ q_{a_t} = \frac{\ln2}{1+\ln2} \log_2\!\left( \frac{p_\mu(a_t)}{p_\mu(a_{t+1})} \right). \]

If \(S^{\mathrm{inf}}_{2,\infty}\setminus S^{\mathrm{inf}}_{1,\infty}\neq\varnothing\), select the last role in \(S^{\mathrm{inf}}_{2,\infty}\) with certainty and use the \(1/(1+\ln2)\)-LM lottery for the other selection. A valid solution is the resulting distribution over role multisets of size at most two, together with the guarantee

\[ \frac{W(q)}{\operatorname{OPT}_2(\mu,H)} \ge \frac{3+\ln2}{4(1+\ln2)}. \]

Theorem 7 proves IC for LALD and Theorem 8 proves this approximation ratio, both in the supplied paper. This is also a plausible Class A candidate for the canonical mechanism: the role-level influential sets require only repeated reachability and ranking computations, and the lottery is explicit. The harder ChoCo questions are whether the guarantee survives under more general typed network kernels, whether the paper’s \(23/27\) upper bound from Theorem 6 transfers, and whether optimizing over all cohort-IC two-selection rules becomes continuum-specifically hard.

The authors should recognize these as their problem rather than an unrelated voting model. The mirror preserves DAGs, progeny, hiding out-edges, influential sets, selecting one or two delegates, incentive compatibility, and the worst-case approximation objective. It changes only the population ontology: many exchangeable agents are represented by role masses, and the selected individual is sampled from the selected role.

The weakest point is strategic semantics. In the original paper, one named agent hides her own edges. In an atomless population, a unilateral deviation has zero mass and may have no effect on aggregate progeny. My mirror therefore uses positive-mass cohort deviations, which is a substantive extension rather than a literal limit of individual IC. It is convincing only in scenarios where network policies are genuinely controlled at the cohort or organizational level. For arbitrary social-media or citation graphs with identity-specific neighborhoods, collapsing agents into finitely many roles loses the very topology on which the paper’s influential sets depend.

Thus I would defend a positive but bounded claim: Theorem 2 gives the strongest lead for a tractable continuous role-mass analogue, and Theorems 7–8 give a natural two-delegate extension. I would not claim that the paper establishes a continuous mirror for general individual-level DAGs, nor would I claim hardness transfer from any result in this paper.