| paper | d4-conf-ijcai-2015-0021 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: \(O(\tau m k)\) arithmetic operations and \(O(\tau m k L^2)\) bit operations for binary-rational table input. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 4.4
statement extracted from the paper’s text layer
Given candidates \(A\), an integer \(k\), distinct ranking types \(T\) with positive binary-rational masses \(\mu_t\) summing to \(1\), a tree \(H\) on \(T\) such that for every candidate pair each preference side is connected in \(H\), and a common polynomial-time-computable rational positional dissatisfaction function \(\rho\), find a committee \(S\subseteq A\) with \(|S|\le k\) and allocations \(x_{t,c}\ge 0\), zero for \(c\notin S\), with \(\sum_{c\in S}x_{t,c}=\mu_t\), minimizing \(\sum_{t\in T}\sum_{c\in S}x_{t,c}\rho(\operatorname{pos}_t(c))\).
A tree-single-crossing society of ranking types with rational masses; choose up to \(k\) representatives and assign each type’s mass among them to minimize total mass-weighted dissatisfaction.
The paper proves only the unweighted algorithm; a polynomial-time bound in \((m,\tau,L)\) for binary-encoded rational masses remains an extension to establish, and scaling masses into explicit voters may take exponential time.
fatal: False
Covers the common positional-dissatisfaction utilitarian subcase of the tree-single-crossing Chamberlin–Courant result in Theorem 4.4; it leaves the egalitarian case, recognition algorithm, Condorcet-domain results, and median-graph extension untouched.
My lead is a continuous high-multiplicity version of Theorem 4.4, proved in this paper. The theorem says that for every polynomial-time-computable dissatisfaction function, every positive \(k\), and both utilitarian and egalitarian Chamberlin–Courant, a polynomial-time algorithm finds an optimal \(k\)-assignment when the input profile is single-crossing with respect to some tree. I would mirror its utilitarian case. The paper has no numbered computational hardness result that offers a comparable anchor.
Call the mirror Tree-Single-Crossing Utilitarian Chamberlin–Courant\(_\infty\). An instance has a candidate set \(A\), a positive integer \(k\le |A|\), and a finite support \(T\) of distinct ranking types. Type \(t\) has a strict ranking \(\succ_t\) and mass \(\mu_t>0\), with rational masses summing to \(1\). Use a common rational-valued, polynomial-time-computable positional dissatisfaction function \(\rho\), nondecreasing with rank. The instance also supplies a tree \(H\) on \(T\) such that, for every pair \(a,b\in A\), each of \(\{t:a\succ_t b\}\) and \(\{t:b\succ_t a\}\) is connected in \(H\).
Choose a committee \(S\subseteq A\) with \(|S|\le k\), and allocate each type’s mass among representatives in \(S\): \(x_{t,c}\ge 0\), \(x_{t,c}=0\) for \(c\notin S\), and \(\sum_{c\in S}x_{t,c}=\mu_t\). Minimize
\[
\sum_{t\in T}\sum_{c\in S}x_{t,c}\,\rho(\operatorname{pos}_t(c)).
\]
A solution is an optimal committee and mass allocation. For a fixed committee, this is exactly the population-weighted Chamberlin–Courant objective. The variables record how the represented population is distributed; since there are no representative-capacity limits, an optimum can assign each type wholly to one best committee member, with splitting needed only to describe ties.
A plausible regime is a large membership organization, municipality, or electorate choosing a representative committee. Many people share rankings over candidates, so the number of people can be much larger than the number \(\tau=|T|\) of distinct types. The tree captures a structured set of policy or constituency positions: for each pair of candidates, the supporters of either ordering form a connected part of the type tree. Each type is a complete description for this model, and its mass is its population share. That makes the problem recognizable as Chamberlin–Courant over a continuous society, rather than continuity introduced into the outcomes.
I expect Class A. The paper’s tree dynamic program sums dissatisfaction over voters. In its utilitarian recurrence, replace each voter’s term by that type’s \(\mu_t\)-weighted term. With the type tree supplied, the number of tree nodes is \(\tau\), so the algorithm should take polynomial time in \(m,\tau,k,L\), where \(L\) covers the binary encodings of masses and dissatisfaction values. This weighted dynamic-programming claim is my extension of Theorem 4.4, not a result proved in the paper. For rational masses, clearing denominators gives a finite electorate with repeated types; its total dissatisfaction differs from the per-capita objective only by a positive scale factor, so the optimal committees correspond exactly.
This case covers the utilitarian, tree-single-crossing winner-determination result in Theorem 4.4. It does not cover the paper’s recognition algorithm, its Condorcet-domain results, or Chamberlin–Courant on median graphs, which the paper leaves open. Natural next questions are whether the weighted algorithm extends from trees to median graphs, and whether the tree witness can be inferred with a running-time guarantee in \((m,\tau,L)\).
The weak point is that this is a high-multiplicity algorithmic mirror, not an example where continuous mass dissolves a discrete hardness result. The anchored restricted problem is already polynomial in the explicit voter count \(n\); the proposed gain is dependence on the compressed support size and binary mass encoding. Also, the paper does not prove the weighted version. Still, that is a direct and plausible high-multiplicity extension of the exact computational problem the authors study.
The strongest case against this anchor is about research priority: Theorem 4.4 already has a tree dynamic program, and the proposed mirror appears to change each voter’s contribution into a mass-weighted contribution. Because there are no representative-capacity constraints, assigning a type’s mass can be handled through the same subtree recurrence; fractional splitting adds nothing essential. The main new guarantee would be polynomial dependence on support size and binary mass length. That may be a useful high-multiplicity result, but it is a narrower contribution than a mirror that exposes a new pricing problem or a tractability boundary.
That argument does not defeat the mirror, though. The paper’s objective depends on rankings and dissatisfaction, not voter identities; grouping identical complete types loses no information. A tree on the support is a natural version of the paper’s tree restriction, and the programme explicitly treats high-multiplicity compression as a worthwhile computational question. Rational masses can also be scaled to repeated voters, though that scaling may be exponential in their bit length. A weighted dynamic program with polynomial dependence on \((m,\tau,L)\) would address precisely that gap.
So I cannot make an honest case that this anchor fails in every scenario. The weighted algorithm is an extension rather than a theorem proved in the paper, and it may be technically routine. But those are weak objections to its value, not fundamental obstacles to a continuous-population mirror. The case against is weak here: Theorem 4.4 survives.
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.