| paper | d4-conf-aaai-2021-0057 |
| 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 in \(O(m\tau L^2+(m+k)\tau^2L)\) bit operations. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given candidates \(C\), a committee limit \(k\), and an ordered support of \(\tau\) complete types, where type \(t_i\) has a strict ranking of \(C\), consistent rational misrepresentation costs \(\rho_i(c)\), and rational mass \(\mu_i>0\) with \(\sum_{i=1}^{\tau}\mu_i=1\), assume the rankings are single-crossing in support order. Find a committee \(W\subseteq C\), \(|W|\le k\), and representatives \(a_i\in W\) minimizing \(\sum_{i=1}^{\tau}\mu_i\rho_i(a_i)\).
A distribution over ordered, complete preference-cost types; choose a committee and one minimizing representative per type, minimizing total mass-weighted dissatisfaction. The weighted dynamic program has \(O(\tau m k)\) operations and polynomial exact bit complexity in the input length.
The mirror covers Theorem 1’s line single-crossing result. It does not claim continuous analogues for the paper’s faster line algorithms or its tree and grid results.
My strongest positive case is narrow: Theorem 1, proved in this paper, gives an exact continuous mirror for the line single-crossing problem. It states that, with \(n\) voters, \(m\) candidates and committee size \(k\), an optimal Chamberlin–Courant solution can be computed in \(O(nmk)\) time. The paper’s numbered results do not give a hardness anchor for this restricted problem. The NP-completeness of unrestricted CC-Winner is cited in the preliminaries, but it is not a numbered result from this paper, so I would not use it as one.
I would call the mirror Continuous Single-Crossing CC-Winner. An instance has a candidate set \(C\) of size \(m\), a committee limit \(k\), and an ordered support \(t_1,\ldots,t_\tau\). Each type \(t_i\) has a strict ranking of \(C\), a nonnegative rational misrepresentation value \(\rho_i(c)\) for each candidate \(c\), consistent with that ranking, and a positive rational mass \(\mu_i\), with \(\sum_i\mu_i=1\). The ranking sequence is single-crossing: for each candidate pair, their relative order changes at most once along the list. The type includes the full ranking and misrepresentation vector; the support list retains each type’s place in the line order. Let \(L\) be the encoding length of the masses and costs.
The question is to choose a committee \(W\subseteq C\), with \(|W|\le k\), and a representative \(a_i\in W\) for each type, minimizing
\[
\sum_{i=1}^{\tau}\mu_i\rho_i(a_i).
\]
Equivalently, minimize \(\sum_i\mu_i\min_{c\in W}\rho_i(c)\). A solution is the committee and a minimizing representative for each type. Individuals still receive an ordinary candidate representative; only their aggregate contribution to dissatisfaction is measured by mass.
A credible regime is a large electorate choosing a small representative assembly from a shared candidate slate. Residents lie along an ideological line, and a comparatively small number of complete ballot and misrepresentation types occur there. For instance, millions of residents might occupy a few hundred ordered Borda-ranking types. The mass of a type is its population share. This is plausible when cohorts share the same preferences and costs, and the relevant comparison is their proportion of the population rather than their individual identities.
The mirror preserves the authors’ underlying optimization question: choose a size-bounded committee to minimize utilitarian misrepresentation, subject to the same single-crossing structure. Its expected class is tractable, Class A. The dynamic program behind Theorem 1 ranges over voter positions, candidate indices and committee sizes. With types as the positions, its additive terms become \(\mu_i\rho_i(c)\); the single-crossing structure and canonical assignments that make the recurrence work are unchanged. This suggests \(O(\tau m k)\) dynamic-programming operations and polynomial exact bit complexity in \(m,\tau,k,L\). A discrete profile with \(n_i\) voters of type \(t_i\) maps directly to \(\mu_i=n_i/n\), while rational masses can be expanded to a finite profile using a common denominator. The continuous input therefore expresses high multiplicity succinctly, without changing the committee problem.
This case covers Theorem 1’s line single-crossing result, including consistent type-specific misrepresentation costs. It does not claim a mirror for the tree or grid results. Further questions include whether the Borda case admits a faster exact algorithm in \(\tau\), and how much the single-crossing condition can be relaxed before the continuous problem becomes hard.
The weakest point is that Theorem 1 already solves its discrete, line-restricted problem in polynomial time. This mirror does not demonstrate that continuum modelling makes discrete hardness disappear. It does, however, give the same problem a natural high-multiplicity input regime: its complexity can depend on the number of distinct complete types rather than the population size.
The strongest case against this mirror is that it looks like a weighted version of Theorem 1: every rational mass vector can be expanded into a finite electorate, and the paper’s dynamic program already solves the underlying line restricted problem. That makes the mirror conservative, but it does not defeat it. The expansion can be exponentially larger than the binary encoding of the masses, and the programme explicitly treats a succinct distribution over types as the high multiplicity problem.
The stronger version of the mirror is coherent. Put the complete voter types in single crossing order, give each type mass \(\mu_i\), and minimize \(\sum_i \mu_i\rho_i(a_i)\). Canonical assignments ensure that identical types need not be split between representatives. In Theorem 1’s recurrence, replace each voter’s cost term \(\rho(v_i,c)\) with \(\mu_i\rho_i(c)\). The interval structure remains, giving \(O(\tau m k)\) dynamic programming operations and polynomial bit complexity. A large electorate choosing a small committee, with residents sharing a modest number of ordered Borda ranking types, is a plausible instance regime; for Borda, the single crossing order has at most \(1+\binom{m}{2}\) distinct rankings.
So the usual objections do not hold: the theorem is a named computational result, the objective aggregates dissatisfaction rather than tracking identities, and mass does not make the objective vanish. I cannot make an honest negative case that rules out this mirror. Its weakness is only that the continuous algorithm appears to follow directly from the discrete recurrence, so the case for programme time is less compelling as a new technical challenge than as a clean high multiplicity formulation.
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.