| paper | d4-journals-jair-2008-0005 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable, with exact preservation of all ties. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 7.6
Given a finite type set \(T\), binary-rational masses \(\mu_i\) summing to one, and a link matrix \(A\) where \(A_{ij}=1\) means every member of type \(i\) links to every member of type \(j\), compute the exact weak order of the types. Let \(D\) be the least common denominator of the masses and define \(d_j=D\sum_i\mu_iA_{ij}\). Rank types by the scores \(q_j=0\) when \(j\) has no predecessor type, and otherwise \(q_j=(d_j+\max_{i:A_{ij}=1}q_i)/(D+1)\), including ties.
A reputation network represented by a finite set of cohorts with masses \(\mu_i\), where links depend on source and destination types. Each cohort is a type, \(A\) specifies its links, and the decision is the weak order induced by the recursive in-degree scores \(q_j\).
The block model makes each participant link to an entire cohort, so link counts grow with population size and may poorly represent the sparse, identity-specific networks that motivate the paper; the proponent acknowledges the restriction but does not establish how common or useful this regime is.
fatal: False
Mirrors Proposition 7.6 for \(r(k)=k\) on type-structured block networks. It leaves the axiomatic impossibility results and the approval-voting representation theorem outside the mirror.
The strongest honest case is the recursive in-degree algorithm in Proposition 7.6, proved in this paper. It states that Algorithm 1 outputs the vertices in the order defined by the recursive in-degree ranking system \(\mathrm{RID}_r\), for a monotone nondecreasing rank function \(r\) with \(r(i)\le i\), and runs in \(O(|V||E|)\) time. This is an algorithmic anchor; the paper gives no named NP-hardness or other complexity-hardness result. Theorem 5.1 is an axiomatic impossibility result, not a computational complexity result.
Here is a concrete high-multiplicity setting for mirroring Proposition 7.6. Consider a large reputation or directory network in which participants fall into a small number \(\tau\) of cohorts. A type \(i\) has mass \(\mu_i\), and its link pattern is a row of a matrix \(A\): \(A_{ij}=1\) means every participant of type \(i\) links to every participant of type \(j\). The type description is complete for this model: members of a cohort have the same outgoing links. This fits the paper’s premise that the agents being ranked are also the agents providing votes. Since those sets coincide in the paper, making the population continuous also makes the ranked objects continuous; that is a consequence of its model, not a switch to a continuous outcome space.
Lead question — Continuous Recursive In-Degree Ranking. The input is a finite type set \(T\), positive binary-rational masses \(\mu_i\) summing to one, and a directed type-link matrix \(A\). Let \(D\) be a common denominator of the masses, so the corresponding finite block network has \(D\mu_i\) participants of type \(i\). For each type \(j\), set
\[
d_j = D\sum_i \mu_i A_{ij}.
\]
Using the paper’s recursive in-degree rule with \(r(k)=k\), compute the exact weak order of the types given by scores
\[
q_j =
\begin{cases}
0, & \text{if } j \text{ has no predecessor type},\\[2mm]
\dfrac{d_j+\max_{i:A_{ij}=1}q_i}{D+1}, & \text{otherwise}.
\end{cases}
\]
A solution is the resulting weak order, including ties. This is the ranking the paper’s rule gives to the corresponding block-expanded graph, expressed without listing its \(D\) participants. There is no optimization objective in the paper’s problem: the decision is which ordering the ranking rule assigns. The recurrence is the fixed-point form supplied by Proposition 7.4; the named complexity anchor remains Proposition 7.6.
I expect this mirror to be tractable. The quotient keeps the recursive predecessor comparison that defines the paper’s problem, while reducing the state space to \(\tau\) types. The recurrence is a discounted Bellman equation on that type graph, with rational coefficients whose bit lengths are controlled by the mass input. That suggests an exact polynomial-time solution using a linear-programming formulation over the \(\tau\) type states. The regime would be a network with far more participants than cohorts—say, millions of accounts or pages and tens or hundreds of role-based types. Members of a type must genuinely share the modeled link pattern; that is the high-multiplicity assumption, not a loss introduced by the mirror.
This covers the paper’s computational result for computing \(\mathrm{RID}_r\), in particular the \(r(k)=k\) case above. It does not mirror the axiomatic impossibility results or the approval-voting representation theorem: those are questions about axioms and characterizations, outside this programme’s computational scope.
The weak point is the block structure. The mirror treats every type-level link as a link to every member of the destination cohort, while the paper permits arbitrary directed graphs. Many real networks are sparse and have identity-specific links, so this is a restricted instance regime, not a general limit of every graph. Still, it preserves the paper’s central computational object—the recursive ranking of agents from incoming votes—and supplies a credible high-multiplicity scenario for it. The case is therefore a focused algorithmic mirror, rather than evidence that continuization dissolves a hardness result in this paper.
Proposition 7.6 is a genuine computational anchor: it gives an \(O(|V||E|)\) algorithm for the recursive in-degree ranking. The paper’s other main results are axiomatic, so they do not supply stronger computational mirrors.
The best objection is that the algorithm ranks vertices in a named network. A vertex is both a reviewer and an object being reviewed, and the result depends on its particular incoming links and on the ranks of those particular predecessors. To make many vertices one type, the type must preserve all of that relevant structure. The proposed block model does so only by making every member of a source type link to every member of each selected destination type. With \(N\) agents, that gives each agent \(\Theta(N)\) links and creates \(\Theta(N^2)\) edges. That is a poor fit for the paper’s motivating page and reputation networks, where links generally name particular pages or people and do not grow with the whole population. Keeping links sparse instead leaves agents with different named neighborhoods, so type masses and a type-link matrix no longer determine the ranking.
A graphon-style extension could model identity-specific links in the limit, but it would need a link relation over a continuum of identities, generally not a finite list of types with rational masses. Restricting it back to finitely many blocks restores the symmetry, but then the output ranks blocks: everyone inside a block has the same structural role and score. The substantive problem has shifted from ranking individual pages or people to ranking a small set of designed cohorts. That may be a useful model for some institutional systems, but it is a narrow setting, not an evident high-multiplicity regime of the paper’s main network problem.
This does not defeat the block mirror outright. Dense, type-structured endorsement networks are possible, and the authors might recognize their ranking problem in that setting. The negative case is therefore weak at its hardest point: it shows that the proposed mirror relies on a special network regime, but cannot honestly rule out a worthwhile mirror in that regime.
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.