| paper | d4-conf-ijcai-2016-0166 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Proposition 3 is a numbered structural result, not a computational one, and the paper's polynomial-time statement is unnumbered and attributed to Wu and Zhang. Theorem 17 establishes truthfulness, not an algorithm or complexity result. The proposed cohort problem is coherent, but it cannot supply the missing computational anchor.
fails bit a — no named computational result to mirror
The proposed cohort model covers bottleneck decomposition only; it does not mirror Theorem 17's truthfulness result or Corollary 16's utility monotonicity.
The strongest honest positive case is narrow: the paper’s bottleneck-decomposition computation has a plausible population mirror. Its central truthfulness theorem does not provide a qualifying computational anchor.
The nearest anchor is Proposition 3, cited from Wu and Zhang (2007). It says the bottleneck decomposition is unique; its ratios satisfy \(0<\alpha_1<\cdots<\alpha_k\le 1\); if \(\alpha_i=1\), then \(i=k\) and \(B_k=C_k\), while otherwise \(B_i\) is independent and disjoint from \(C_i\); and every candidate pair \((B,C)\) in the residual graph has \(w(C)/w(B)\ge\alpha_i\), with equality only when \(B\subseteq B_i\) and \(C\subseteq C_i\). The paper’s surrounding text also says the decomposition can be computed in polynomial time by parametric maximum flow. That algorithmic claim is cited, not proved here. Strictly, Proposition 3 states structural properties rather than a complexity classification, so this is a near miss under the stated anchor rule.
The natural high-multiplicity setting is a large resource-exchange network with a small number of recurring network roles. Let \(H=(T,E_H)\) be a finite undirected role graph. Each type \(t\in T\) comprises a fraction \(\mu_t\) of the peers, with \(\sum_t\mu_t=1\), and each peer of type \(t\) has the same per-capita resource \(r_t>0\). Types include the role’s full neighbor pattern and resource amount. Every peer in role \(t\) can exchange with every peer in an adjacent role \(s\). The population can be huge while the number of types \(\tau=|T|\) stays small.
A concrete candidate question is Cohort Bottleneck Decomposition: given \(H\), the binary-rational masses \(\mu_t\), and per-capita resources \(r_t\), compute the unique bottleneck decomposition of this population network, returning each pair \((B_i,C_i)\) and ratio
\[
\alpha_i=\frac{\sum_{s\in C_i}\mu_s r_s}{\sum_{t\in B_i}\mu_t r_t}.
\]
Here \(B_i\) is a maximal minimizing set in the current residual role graph, and \(C_i\) is its neighbor set there; remove \(B_i\cup C_i\) and continue. A solution is the complete ordered decomposition. This is an exact computation problem, with expansion ratio as the objective at each stage.
The quotient by roles is exact for this scenario: selecting any positive mass of a role already brings in its full neighboring cohorts, so adding the rest of that role leaves the neighbor set unchanged and weakly lowers the ratio. Thus a bottleneck set need not split a type. The weighted role graph has capacities \(\mu_t r_t\), giving a plausible polynomial-time algorithm in \(\tau\) and the input bit length \(L\), without expanding the population. This is the conditional lead, and its expected direction is tractable (Class A). A next question is whether the associated BD allocation can also be represented and computed exactly with type-level mass flows.
The fit is plausible for computing the mechanism’s bottleneck structure: the paper’s agents exchange divisible resources over a graph, and the proposed scenario compresses repeated network roles while retaining their relevant connections. It covers that algorithmic subproblem only. It does not mirror the main result, Theorem 17, proved here: for every agent \(u\), every fixed profile \(x_{-u}\) of other agents’ reports, and every allowed report \(x_u\in(0,w_u]\), the utility satisfies
\[
U_u(w_u,x_{-u})\ge U_u(x_u,x_{-u}).
\]
Corollary 16 gives the underlying monotonicity: \(U_u(x_u)\) is nondecreasing in \(x_u\) with \(x_{-u}\) fixed. These are incentive properties, not complexity classifications.
That gap is the weakest point. In the proposed population model, a deviation by one infinitesimal peer has vanishing influence. Replacing it with a whole type’s joint report creates a coalition-manipulation question, which Theorem 17 does not settle. So the paper offers a credible, narrow algorithmic extension around bottleneck decomposition, but no strong continuous mirror of its central truthfulness result.
The paper’s only plausible computational anchor is Proposition 3, but it gives structural properties of a bottleneck decomposition, not a complexity result. The polynomial-time claim appears in the preliminaries and is attributed to Wu and Zhang (2007). This paper’s own main result, Theorem 17, is a truthfulness claim. So the proposed mirror is not a continuous version of a computational result established here.
The cohort model is coherent. In a dense blow-up of a finite role graph, any positive mass selected from a role brings in all its neighboring cohorts. Adding the rest of that role increases the denominator without changing the neighborhood, so a minimizing set can be taken to be a union of roles. The resulting decomposition is exactly a weighted finite-graph problem, with role capacities \(\mu_t r_t\). That is a sensible high-multiplicity resource-exchange model, but it does not give this paper a computational result to mirror: its continuous calculation is the role-graph decomposition already described in the cited algorithmic work.
Trying to retain sparse peer-to-peer networks creates a different problem. In bounded-degree network sequences, the limiting mass of any individual’s neighborhood vanishes, so a population measure alone loses the incidences that determine bottlenecks. Retaining those incidences keeps the finite network structure in the input; allowing a continuum of distinct network roles instead makes network structure itself continuous, beyond the paper’s population question.
Theorem 17 offers no stronger computational anchor. A single infinitesimal peer’s report has no effect on the aggregate bottleneck partition in a nonatomic limit. Giving a positive-mass cohort a joint report preserves that effect, but changes the strategic object to coalition manipulation, which the theorem does not address.
The negative case is strongest against treating this paper as a computational-mirror candidate. It is weaker as a claim that no worthwhile continuous bottleneck problem could arise: the dense cohort model is respectable, but it is an adjacent problem rather than a mirror of this paper’s contribution.
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.