| paper | d4-conf-aaai-2021-0918 |
| 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 in \(m,\tau,L\); a \(\mathrm{BSP}\) allocation always exists. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 7
statement extracted from the paper’s text layer
Given candidates \(C\), a finite support \(T\subseteq 2^C\) of approval types with rational masses \(\mu_A\geq 0\) summing to \(1\), and a rational mass price \(p>0\), find a BSP committee and supporting allocation, with no prescribed committee size. Choose \(W\subseteq C\), prices \(\rho_c\in[0,1]\), and masses \(x_{A,U}\geq 0\) for \(A\in T\) and \(U\subseteq W\cap A\), where \(\sum_U x_{A,U}=\mu_A\), each used bundle costs at most one, and \(\rho_c\sum_{A,U:c\in U}x_{A,U}=p\) for each \(c\in W\). Require BSP stability: no coalition formed from submasses of the \((A,U)\) cohorts can switch to newly proposed candidates \(W'\subseteq C\setminus W\), use balanced per-candidate prices, stay within each participant’s unit budget, make every participant weakly prefer the new utility/payment pair under the paper’s utility-first and lower-payment tie-break, and raise strictly more than \(p\) for every proposed candidate.
The population is a rational distribution over approval sets; each type’s mass may split across use patterns for the selected committee. The outcome remains a subset of candidates, with balanced per-user prices and the paper’s coalition-stability condition extended to mass.
The mirror concerns Theorem 7’s variable-size BSP search and does not claim its polynomial-time guarantee transfers to rational masses. It leaves exact-\(k\) search, the SP results, fairness implications, Lindahl-equilibrium results, nonexistence results, and experiments outside its scope.
The strongest positive case is a narrow mirror of balanced stable priceability (BSP). The paper gives no named NP-hardness result to anchor a hardness-dissolution question. Its best computational anchor is Theorem 7, proved in this paper, with proofs deferred to the supplement: given an election and a price \(p\), one can verify in polynomial time whether a supplied committee is BSP, and one can find a BSP committee in polynomial time. Theorem 7’s search clause does not promise a committee of any prescribed size \(k\).
A plausible regime is a large city choosing public facilities or projects. Millions of residents each approve a subset of the options, but many share the same approval set: neighborhoods or organized groups may produce \(\tau\) distinct ballot types, with \(\tau\) far smaller than the population. A type is an approval set \(A\subseteq C\); its mass \(\mu_A\) is the fraction of residents with that ballot. The committee remains a subset of candidates. Only the voter population becomes continuous.
Call the resulting problem Mass-BSP Search. Its input is a candidate set \(C\), a support \(T\subseteq 2^C\) with rational masses \(\mu_A\geq 0\) summing to \(1\), and a rational normalized candidate price \(p>0\). Normalizing matters: if the original election has \(n\) voters and each candidate must collect \(p_0\), the corresponding mass price is \(p=p_0/n\).
A solution is a committee \(W\subseteq C\), a per-user price \(\rho_c\in[0,1]\) for each \(c\in W\), and masses \(x_{A,U}\geq 0\) for each \(A\in T\) and \(U\subseteq W\cap A\). Here \(x_{A,U}\) is the mass of type \(A\) who uses exactly the candidates in \(U\). Require
\[
\sum_{U\subseteq W\cap A}x_{A,U}=\mu_A,\qquad
\sum_{c\in U}\rho_c\leq 1\ \text{whenever }x_{A,U}>0,
\]
and, for each \(c\in W\),
\[
\rho_c\sum_{A,U:\,c\in U}x_{A,U}=p.
\]
Thus each person has a unit budget, users of a candidate pay the same amount for it, and each chosen candidate collects the specified mass-scaled price. The solution must also be stable in the paper’s BSP sense: there is no coalition of mass that can jointly propose \(W'\subseteq C\setminus W\), pay a common per-user price \(\sigma_c\) for each proposed candidate, and have every participant weakly prefer the change under the paper’s utility-first, lower-payment tie-break, while raising strictly more than \(p\) for every candidate in \(W'\). A coalition may split each type-and-use cohort further among choices of which current uses to drop and which new approved candidates to use. The absence of any such blocking mass is part of the solution condition.
My working expectation is Class A: a weighted version of the paper’s BSP characterization and Rule X machinery may operate directly on rational type masses, with running time polynomial in \(m,\tau,L\). This is a conjecture for the continuous problem, not a consequence of Theorem 7. The paper’s algorithm runs on explicit voters; a polynomial bound in voter count does not by itself give a bound in the bit length of compressed rational masses. Further questions include whether the exact-\(k\) Mass-BSP problem is tractable, whether continuous solutions correspond to limits of finite elections, and how strict blocking behaves under those limits.
The soft spot is also the main scope limit: Theorem 7 does not guarantee a committee of the desired size \(k\), and the paper separately reports that feasible BSP committees need not exist. I would therefore offer Mass-BSP Search as the mirror of its stated algorithmic result, while treating exact-\(k\) search as a separate question. This case covers the BSP computation only; it does not claim that the paper’s core, proportionality, or Lindahl-equilibrium results have been continuized. The paper’s nonexistence theorems are not computational hardness anchors.
The strongest case against is that Theorem 7’s search task has a narrower practical meaning than the Mass-BSP proposal suggests. It takes a candidate price \(p\) and finds a BSP committee, but guarantees no prescribed size \(k\). The paper’s central election problem is to choose exactly \(k\) candidates. A city choosing a fixed number of facilities would therefore need a different question—such as whether an exact-\(k\) BSP committee exists, or how to find a near-BSP committee of size \(k\). Theorem 7 does not settle that problem.
That objection does not defeat the proposed mirror, though. The variable-size search is itself the paper’s named computational result, and a mirror need only anchor on one result. The Mass-BSP formulation preserves that search problem and changes the population representation. The paper’s nonexistence results do not make it unworthy: they leave open the computational question of what can be found when exact size is required.
The more substantive concern is scientific payoff. Voters here have only approval sets and identical unit budgets; for rational masses, clearing denominators gives a finite replicated election with the same types. BSP’s characterization and Rule X connection make it plausible that the finite algorithm could be implemented directly on weighted approval cohorts. If so, the continuous version may amount to a compressed implementation of an existing algorithm, rather than a new optimization landscape. But the paper’s polynomial bound in the explicit voter count does not establish a polynomial bound in \((m,\tau,L)\): clearing denominators can produce an electorate exponential in the mass bit length. A weighted implementation is plausible, not proved. That leaves a real high-multiplicity computational question.
So I cannot honestly make a strong case that no worthwhile continuous mirror exists. The best objection is that the anchored search has endogenous committee size and its weighted extension may be modest. Neither rules out the natural Mass-BSP question, and the fixed-\(k\) alternative is a separate, still-open extension rather than a reason to reject the anchor. The proposed mirror survives the negative case.
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.