| paper | Computing the Best Policy that Survives a Vote |
| authors | — |
| venue | AAMAS 2023 |
| filed under | voting · combinatorial |
| judged by | gpt-5.6-terra / high (triple__gpt-5.6-terra__high__ctx2r8-rejudge1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 19
statement extracted from the paper’s text layer
Given \(t\) binary issues, a rational distribution \(\mu\) over ballot types \(v\in\{0,1\}^t\), and \(k\), decide whether there is a policy \(p\in\{0,1\}^t\) with \(d_H(p,q)\le t-k\) and \(B_\mu(p)\ge0\), where \(q\) is coordinatewise issue-wise majority and \(B_\mu\) is mass of supporters minus mass of opponents; compute such a policy for \(k=\lfloor t/2\rfloor+1\).
A high-multiplicity referendum society: each complete ballot \(v\in\{0,1\}^t\) has mass \(\mu_v\), policies remain binary vectors \(p\), and feasibility is the weighted support balance \(B_\mu(p)\ge0\) while the objective maximizes agreement with issue-wise majority \(q\).
The mirror covers the guaranteed polynomial-time policy construction of Theorem 19 and the better-than-halfway NP-hardness boundary of Theorem 4; it leaves the paper's symmetry lemmas and related structural results as supporting machinery.
The positive case is unusually strong here, because the paper’s object already has a natural high-multiplicity reading: a large electorate considering a common binary policy agenda. The right continuous object is not a fractional policy. The policy remains an integral vector; it is the electorate that becomes a distribution.
My lead question is Continuous Surviving Policy. An instance consists of an agenda of \(t\) binary issues and a rational distribution \(\mu\) over ballot types \(T\subseteq\{0,1\}^t\), where \(\mu_v\) is the fraction of the population with complete opinion vector \(v\). The issue-wise-majority policy \(q\in\{0,1\}^t\) is determined coordinatewise from \(\mu\), with the paper’s fixed tie convention. For a proposed policy \(p\), type \(v\) supports it if \(d_H(v,p)<t/2\), opposes it if \(d_H(v,p)>t/2\), and abstains otherwise. Thus its continuous balance is
\[ B_\mu(p)=\sum_{v\in T}\mu_v\bigl(\mathbf 1[d_H(v,p)<t/2]-\mathbf 1[d_H(v,p)>t/2]\bigr). \]
Given \(k\), ask whether there is a policy \(p\) with \(B_\mu(p)\geq0\) and at least \(k\) coordinate agreements with \(q\), equivalently \(d_H(p,q)\leq t-k\). A solution is that policy; the optimization version maximizes its agreement with \(q\). This is exactly the paper’s question with counts replaced by population shares, not a softened or different objective.
The most convincing regime is a nationwide or regional referendum platform, rather than the paper’s board-of-directors illustration. A government, party, civic assembly, or advocacy coalition has a survey-derived distribution of politically coherent ballot types across a large common agenda: for example, urban environmental-progressive voters, rural conservative voters, labour-oriented voters, and finer issue-position segments. Millions of citizens may be represented by hundreds or thousands of observed complete ballot types. The planner wants a platform that stays close to coordinatewise public majorities, yet will not be defeated when citizens evaluate the platform as a whole. Fractions are the honest quantities: one does not say that precisely 446,873 people hold a type when the relevant information is that 23.1% do. The type is complete for this task—same answers on all agenda issues—and there is no need to pretend that arbitrary named citizens are interchangeable.
For this lead question, Theorem 19 is the central anchor, proved in this paper: it gives a deterministic polynomial-time algorithm computing a non-losing policy with more than \(t/2\) ones after normalizing the IWM policy to all ones, and a winning policy when \(\Delta>0\). Its continuous counterpart should be:
Continuous Halfway Surviving Policy. Given rational \(\mu\), compute a policy \(p\) with \(d_H(p,q)\leq\lfloor(t-1)/2\rfloor\) and \(B_\mu(p)\geq0\); if the aggregate issue-wise margin is nonzero, compute one with \(B_\mu(p)>0\).
I expect this to be Class A, and not merely by analogy. The proof behind Theorems 12, 14, and 19 is voterwise and linear in the electorate. Replacing each voter’s contribution by a nonnegative rational type mass preserves the expectation identity and the conditional-expectation derandomization. Duplicate ballots need not be expanded: every evaluation becomes a weighted sum over the supported types, using exact rational arithmetic. Hence the expected running time should be polynomial in \(t\), the number of represented ballot types, and the input bit length of their masses. Theorem 14, also proved here, supplies the matching existence statement; Theorem 19 supplies the algorithmic content.
This is a genuine continuization gain in formulation and input representation. A profile with ten million voters but 500 ballot types is represented by 500 rational weights, while the outcome still must satisfy an exact whole-population approval constraint. The integral policy is not an embarrassment: continuization concerns the society, and policy choices here are inherently binary legislative packages.
There is also a crisp negative boundary, worth treating as a second anchor rather than hiding. Theorem 4, proved here, states that \((\lfloor t/2\rfloor+2)\)-Win-OR-Tie-PRop is NP-hard, including when both the number of voters and issues are odd (and also when the voter count is even and the issue count odd). Its continuous form is:
Continuous Better-than-Halfway Surviving Policy. Given rational \(\mu\) and \(k\ge\lfloor t/2\rfloor+2\), decide whether a policy \(p\) satisfies \(B_\mu(p)\ge0\) and agrees with \(q\) on at least \(k\) issues.
I expect Class B: hardness transfers. Every discrete profile maps exactly to rational masses \(\mu_v=n_v/n\), and multiplying all voter multiplicities changes neither \(\mu\) nor the answer. More substantively, the reduction in Theorem 3 encodes Independent Set through the agenda variables and the choice of policy, not through indivisible unit masses of voters. Its combinatorics live in the issues/agenda, precisely the kind of hardness that continuization should not dissolve. Theorem 4 therefore becomes a particularly clean boundary for the programme: a continuous society makes the guaranteed “halfway” compromise tractable, but does not make a better policy computationally easy.
The likely further questions are good ones rather than repairs: Does the weighted version of Theorem 19 admit a strongly polynomial or practically efficient implementation? What happens with type-specific support thresholds or issue weights, both extensions the paper itself suggests? Does NP-hardness persist for a fixed small number of ballot types, or is that the parameter regime where continuous optimization can buy more?
The weakest point is empirical, not mathematical: complete \(t\)-bit opinion patterns can proliferate rapidly as an agenda becomes fine-grained, so a high-multiplicity representation is not equally credible for every referendum. It is strongest for a stable, shared agenda and survey or administrative segmentation, and weak for a small deliberative board or a one-off bespoke agenda. That limitation does not undermine the mirror: the national-platform regime is plainly one the authors would recognize as their policy-survival problem, and it is exactly where proportions rather than named voter counts are most natural.
I cannot make a credible universal negative case here. The paper has two genuine computational anchors, and its basic object—many citizens evaluating one common binary agenda—has an unusually clean high-multiplicity regime.
The closest objection to the Theorem 19 mirror is that it is not a rich “continuous optimization” problem: the policy remains a vertex of \(\{0,1\}^t\), and the population enters only through weighted sums. Rational masses can be cleared to recover an ordinary finite profile, so this is a homogeneous weighted formulation rather than a new limit phenomenon. At most, that supports a prioritisation claim: the continuous theorem is likely a short weighted corollary of the paper’s conditional-expectation proof, not a new technical frontier.
But it does not defeat the mirror. The proof is voterwise and linear, so replacing duplicated rows by rational type masses is exactly legitimate; exact arithmetic stays polynomial in the support size and bit length. More importantly, a national referendum or party-platform setting supplies the requisite multiplicity without artifice. Complete ballot vectors are indeed complete types for this model. The familiar practical caveat—that fine agendas may create many observed ballot types—limits the regime, but cannot erase the plainly plausible stable-agenda regime.
Theorem 4 survives even more decisively. Its proposed continuous version is well posed on the same weighted society, and every discrete profile maps to rational masses while preserving issue-wise majority, support balance, and feasibility. One can say that the hardness is agenda-driven and hence will transfer, but that is explicitly a meaningful Class B boundary, not a reason the question is unworthy. Nor is there an identity-based objection: the rule uses no feature of a voter beyond the complete opinion vector, so aggregation loses nothing the problem needs.
A stronger re-modelling does not rescue the negative position. One may enrich a type with an issue-weight vector or an individual acceptance threshold, but that merely defines promising extensions; it does not invalidate the homogeneous complete-ballot regime already captured by the paper. Conversely, insisting that real citizens have idiosyncratic saliences attacks the paper’s equal-issue model itself, not its high-multiplicity version.
So the honest adverse verdict is narrow: this is probably not where ChoCo will discover its most characteristic LP/pricing machinery, because the weighted extension of Theorem 19 appears immediate and Theorem 4 transfers directly. It should perhaps be treated as a clean foundational example rather than a flagship open problem. That is not enough to reject it. The proponent’s Theorem 19 anchor survives, and Theorem 4 provides a particularly useful tractable-versus-hard boundary.
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.