| paper | d4-conf-atal-2014-0344 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable · discrete side: other · adjudication: proved
full proof & adversarial review →
Corollary 1
statement extracted from the paper’s text layer
Given a finite alternative set \(A\), a fixed scoring rule, ranking-and-influence-role types \(T\), rational masses \(\mu_t>0\) summing to \(1\), and rational parameters \(\alpha_t>0\) and \(p_{tt'}\geq 0\) with \(\alpha_t+\sum_{t'\in T}p_{tt'}=1\), let \(v_t(a)\) be type \(t\)'s score for \(a\). Define type utilities by \(u_t(a)=\alpha_t v_t(a)+\sum_{t'\in T}p_{tt'}u_{t'}(a)\). Return any alternative maximizing \(\mathrm{SW}_\mu(a)=\sum_{t\in T}\mu_tu_t(a)\), with running time measured in \(m\), \(\tau=|T|\), and the input bit length \(L\).
A distribution \(\mu\) over types that combine rankings with shared influence roles, a type-level influence matrix \(P=(p_{tt'})\), and self-weights \(\alpha_t\). Solve \(u(a)=(I-P)^{-1}Dv(a)\), where \(D=\operatorname{diag}(\alpha_t)\), then maximize \(\mu^\top u(a)\) over alternatives.
In ordinary friendship networks, agents with the same ranking may have different influence profiles, so the number of exact ranking-and-role types may grow with the population; the proposed role-based setting makes the mirror plausible but does not show how broadly it applies.
fatal: False
Covers global empathetic, score-based winner computation for societies with a finite support of ranking-and-influence-role types; it does not cover arbitrary individual networks, the local empathetic model, or the paper's empirical comparisons.
My lead is Corollary 1, proved in this paper and used to compute winners. The paper has no named hardness or complexity-classification result, so this is an algorithmic formulation anchor. Under the global empathetic model, assuming nonnegative weights, rows of \(W\) sum to \(1\), and every self-loop has positive weight, the social welfare of alternative \(a\) is
\[
\mathrm{sw}_g(a,u^I)=\omega^\top u^I(a),
\qquad
\omega^\top=e^\top(I-W+D)^{-1}D,
\]
where \(D=\operatorname{diag}(w_{jj})\). The mirror I would ask about is the continuous global empathetic winner problem.
An instance has a finite alternative set \(A\), a fixed scoring rule, and a support \(T\) of \(\tau\) voter types. Each type \(t\) has a complete ranking \(\succ_t\), a rational population mass \(\mu_t>0\) with \(\sum_t\mu_t=1\), a rational self-weight \(\alpha_t>0\), and rational weights \(p_{tt'}\geq 0\) for its empathy toward each type \(t'\), with \(\alpha_t+\sum_{t'}p_{tt'}=1\). The weights \(p_{tt'}\) are the total influence type \(t\) places on type \(t'\), not the weight on a particular named neighbor. Let \(v_t(a)\) be the score that type \(t\)’s ranking gives \(a\). Define type utilities by
\[
u_t(a)=\alpha_t v_t(a)+\sum_{t'\in T}p_{tt'}u_{t'}(a).
\]
The question is to return a winner maximizing \(\mathrm{SW}_\mu(a)=\sum_t\mu_tu_t(a)\); any maximizer is a solution. All masses and weights are binary rationals, and the running time is measured in \(m\), \(\tau\), and their bit length \(L\).
This preserves the paper’s global empathy question: each person’s utility for an option depends on intrinsic preference and the utilities of people they care about. It makes the population continuous by using type masses and gives each type a shared network role, expressed by its normalized influence across types. The role is part of the type’s complete description, as the high-multiplicity interpretation requires. A plausible regime is a large municipal electorate choosing among a few candidates or policies: many residents share a ranking and neighborhood or community role, and each role has a stable influence profile over the others. One could have hundreds of thousands of residents but dozens or hundreds of supported preference-and-role types.
I expect this mirror to be Class A, tractable. With \(P=(p_{tt'})\) and \(D=\operatorname{diag}(\alpha_t)\), each alternative’s utilities solve \((I-P)u(a)=Dv(a)\). Since every row of \(P\) sums to \(1-\alpha_t<1\), the system has a unique solution. Exact rational linear algebra for all \(m\) alternatives gives a polynomial-time algorithm in \(m,\tau,L\). The type-level social-welfare weights are \(\mu^\top(I-P)^{-1}D\), the mass-weighted counterpart of Corollary 1’s \(\omega^\top\). This asks for the winning option under the paper’s model; the finite set of options stays discrete.
The mirror covers global empathetic, score-based consensus choice. Further questions include whether the same bounds hold with sparse type-interaction matrices, what happens when some types have zero self-weight, and how winner robustness changes as the masses \(\mu_t\) vary.
The weakest point is that this is a structured high-multiplicity regime, not the paper’s arbitrary individual network: people within a type must share both their ranking and their normalized influence profile. That is plausible for repeated community roles, but restrictive for friendship networks. Also, the paper already gives a polynomial-time method in the number \(n\) of named agents; the mirror’s gain is dependence on \(\tau\ll n\), not a dissolution of discrete hardness. That makes it a sound, fairly modest computational mirror rather than evidence for the programme’s strongest complexity payoff.
The paper gives the proposed mirror less to work with than the proponent suggests. Its named results establish a fixed point and rewrite global social welfare as a weighted sum of intrinsic utilities; they do not state a complexity classification. The winner computation is then ordinary weighted scoring over a finite set of alternatives. So there is no discrete complexity result here whose population dependence the continuous model could clarify.
The stronger version of the proposed mirror is still well-defined: group agents by ranking and by their normalized influence across groups, then solve the resulting type-level fixed-point system. But exact grouping requires more than repeated preferences. Agents in a type must have the same aggregate influence on every other type. In an arbitrary social network, even agents with identical rankings may have different neighborhoods, so the exact type support can grow with the number of agents. The type-level model avoids that only by restricting the networks to ones with an exact block structure.
A continuous graph or graphon model could relax that restriction, but then the network kernel is part of the input and needs a finite representation for a computational question. A finite-step kernel brings us back to the block-type model; a general kernel does not, by itself, specify a finite algorithmic input. Thus the population distribution alone does not carry the paper’s central structure: the individual network does.
That is the strongest objection I see, but it does not defeat every plausible mirror. A large organization with many agents in a small number of preference-and-influence roles could be a sensible high-multiplicity regime, and the resulting continuous winner problem would be clean. The negative case is therefore weak on the universal claim: it shows that the mirror covers a restricted class of networks, not that the class is too implausible to merit study.
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.