| paper | Proportionality Guarantees in Elections with Interdependent Issues |
| authors | Markus Brill, Evangelos Markakis, Georgios Papasotiropoulos, Jannik Peters |
| venue | IJCAI 2023 |
| filed under | voting · combinatorial |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 4
statement extracted from the paper’s text layer
Given issues with domains \(D_j\), a fixed common dependency graph \(G\) satisfying \(\Delta_{\mathrm{in}}(G)\le k\) for constant \(k\), and a rational distribution \(\mu\) over complete conditional-ballot types \(t\), execute cMES with initial per-unit budget \(m\), mass-weighted payments, largest participating mass as the secondary tie-break, and fixed lexicographic tie-breaking; compute the exact integral outcome \(w\in\prod_j D_j\).
Types are complete pairs \(t=(G,B_t)\) with rational masses \(\mu_t\); the outcome remains integral. The state contains per-type remaining budgets \(b_t\), and a purchase \((I',z)\) minimizes \(p\) subject to \(\sum_{t\in S(I',z)}\mu_t\min\{b_t,p\}=|I'|\), then maximizes participating mass; the task is exact cMES winner determination.
The mirror covers the computational cMES landscape in Theorems 2–5, including hardness under common or heterogeneous dependency structures and tractability under common bounded in-degree or bounded-size components. It leaves Theorem 1, Theorem 6, Proposition 1, the observations, and other proportionality results outside the computational mirror.
The strongest continuous mirror is obtained by continuizing the electorate in the paper’s own conditional MES rule, while leaving the issues and their decisions discrete. The continuous object is therefore not a fractional outcome: it is a distribution over complete conditional-ballot types.
A type \(t\) consists of a dependency graph \(G_t\) together with the full conditional approval ballot \(B_t\). A society is a rational distribution \(\mu\) over such types. This is important: the graph is part of the type, so agents with different dependency structures are not incorrectly merged. The action remains an integral outcome \(w\in\prod_jD_j\), together with the sequence of issue purchases made by cMES.
Call the resulting problem \(\textsc{Mass-cMES-Winner}\). Initially every unit of population has budget \(m\), so type \(t\) has aggregate budget \(\mu_t m\). Normalize the price of fixing one issue to \(1\). At a round, consider every legal purchase of a nonempty set \(I'\) of currently unfixed issues, together with a suboutcome \(z\) on \(I'\). Let \(B(I',z)\) be the types with positive remaining budget whose conditional ballot is satisfied by the proposed partial outcome. If \(b_t\) is the current per-unit remaining budget of type \(t\), its aggregate payment at per-unit price \(p\) is \(\mu_t\min\{b_t,p\}\). The price of the purchase is the \(p\) satisfying
\( \sum_{t\in B(I',z)}\mu_t\min\{b_t,p\}=|I'|. \)
cMES chooses a feasible purchase with minimum \(p\), breaking ties in favour of the largest buyer mass \(\sum_{t\in B(I',z)}\mu_t\), followed by a fixed lexicographic rule. Participating types update \(b_t\leftarrow\max\{0,b_t-p\}\), and the chosen issues are fixed to \(z\). The solution is the exact final outcome \(w\).
This is genuinely the high-multiplicity version of the paper’s rule. Given a discrete election with \(n_t\) voters of type \(t\), set \(\mu_t=n_t/n\). Multiplying the continuous price equation by \(n\) gives precisely the paper’s equation in which each issue costs \(n\). Thus aggregation changes sums over voters into mass-weighted sums, but changes neither conditional satisfaction nor the cMES procedure.
My lead anchor is Theorem 3, proved in this paper by a reduction from 3SAT. It states that, assuming ties are broken in favour of the largest set of buyers, the winning outcome under cMES cannot be computed in polynomial time unless \(P=NP\), even when every voter’s dependency graph has constant maximum in-degree.
The corresponding continuous problem is \(\textsc{Heterogeneous-Mass-cMES-Winner}_{\Delta_{\mathrm{in}}\le4}\): the input has binary issues, rational type masses, arbitrary type-specific dependency graphs with maximum in-degree at most \(4\), and explicit conditional ballots; the task is to compute the exact mass-cMES outcome.
I expect this problem to be Class B: the hardness transfers from the discrete problem. The 3SAT construction has one variable- or clause-voter per constructed role, but that does not prevent a high-multiplicity interpretation. Replicate every such voter \(K\) times, with all copies having the same graph and ballot. Then there are \(N=K(q+r+1)\) agents but only \(\tau=q+r+1\) complete types, with \(N\gg\tau\) for large \(K\). The normalized cMES execution is unchanged. The reduction’s combinatorics live in the issue assignments and conditional dependencies, not in voter identities, so continuization does not dissolve them.
The regime is plausible as a population of repeated stakeholder cohorts: many residents, institutions, or organizational units share one of finitely many standardized conditional policy templates. The templates include both their dependency model and their approvals. The original authors should recognize this as their problem: the conditional ballots, dependencies, budgets, and purchase rule are all preserved exactly.
A second anchor is Theorem 2, also proved in this paper. It states that cMES winner determination remains NP-hard even when all voters have a common dependency graph. The corresponding problem, \(\textsc{Common-Mass-cMES-Winner}\), has a rational distribution over conditional-ballot types, but all types share one dependency graph; binary domains suffice, while the in-degree is unrestricted.
This is again Class B. Replicating each discrete voter into a large cohort preserves the common graph and the entire normalized cMES execution. It is a useful separate anchor because it shows that the hardness in Theorem 3 is not merely caused by voters disagreeing about the dependency structure. Even after the population agrees on the issue architecture, the conditional approval information can encode the hard instance.
My third anchor is Theorem 4, proved here, which gives the positive boundary: if all voters have the same dependency graph and the maximum in-degree is bounded by a constant, then the cMES outcome can be computed in polynomial time.
The continuous question is \(\textsc{Common-Mass-cMES-Winner}_{k}\): the input is as above, all types share a graph \(G\), \(\Delta_{\mathrm{in}}(G)\le k\) for a fixed constant \(k\), and masses are rational; the task is exact winner determination under mass-cMES.
I expect this to be Class A. The paper’s enumeration of local suboutcomes still works: each purchase concerns only a constant-size dependency neighbourhood, so there are polynomially many candidate suboutcomes for fixed \(k\). For each candidate, its price can be found by sorting the current rational budget breakpoints of the \(\tau\) types and evaluating the mass equation above. There are at most \(m\) rounds, and all operations are over explicitly represented types and rational numbers. The paper proves the discrete version; the polynomial-time mass extension would need to be written formally, but its algorithmic mechanism is directly inherited.
This positive result has a natural scenario of its own: a large electorate faces one publicly agreed dependency structure—say, legal or engineering prerequisites among municipal projects—while many agents repeat a finite collection of conditional approval templates. Here the continuum is useful because the relevant quantities are population shares and aggregate purchasing power, while the issue decisions remain ordinary discrete public decisions.
The mirror therefore covers the paper’s computational cMES landscape represented by Theorems 2–4: hardness with a common graph, hardness with bounded local complexity but heterogeneous graphs, and tractability under common bounded local structure. I deliberately do not use Theorem 1 or Theorem 6 as anchors: they are proportionality theorems rather than computational classifications, and the paper’s statement that unconditional PAV winner determination is NP-hard is unnumbered.
The weakest point is that the paper’s reductions use highly engineered voter types, and cMES is procedural rather than the optimizer of one simple global objective. A referee could also question whether “largest number of buyers” should become “largest buyer mass.” I think that objection is manageable: mass is exactly the limit of cardinality after duplicating each type equally, and the programme permits a cohort-based high-multiplicity regime. More importantly, no information is discarded—the complete type includes the dependency graph and the entire conditional ballot. The resulting problem is not an artificially simplified voting problem; it is the paper’s conditional MES rule executed over a continuous society.
The strongest negative case is that the proposed mirror is only a weighted replay of cMES. The paper’s rule already treats voters with identical conditional ballots and dependency graphs symmetrically, so replacing voter counts by rational masses adds no new population-level object. The computation still enumerates issue assignments, maintains one budget state per explicitly listed type, and makes a discrete purchase. There is no continuous optimization or genuinely aggregate decision problem.
That objection is not strong enough under ChoCo’s standard, however. High multiplicity is itself the relevant continuous object, and exact weighted replay is not disqualified merely because it is formally straightforward. The paper has named computational results, and none is already treated continuously. More importantly, each of the three anchors survives the stronger modelling objections.
Theorem 3 is hard to defeat. In its reduction, give every variable- and clause-voter \(K\) identical copies. The resulting population has \(K(q+r+1)\) voters but only \(q+r+1\) complete types. With \(\mu_t=1/(q+r+1)\), the mass-price equation is exactly the replicated discrete cMES execution after rescaling. The fact that the number of types grows with the SAT instance does not invalidate the mirror: ChoCo explicitly allows hardness to live in the type support or in the issue structure, and a high-multiplicity instance may have many types provided each type has many members. The conditional graph and ballot are part of the type, so no relevant information is lost.
One could argue that the reduction’s types are engineered roles rather than natural voter cohorts. But that objection does not survive the better scenario: many residents, institutions, or stakeholder groups can share standardized conditional policy templates, including their dependency interpretation and approval table. The scenario may be artificial, but it is recognizably the paper’s model and gives a legitimate Class B mirror. Its hardness remaining after replication is not an objection; it is precisely the sort of boundary result the programme wants.
Theorem 2 is, if anything, harder to dismiss on modelling grounds. All voters share one dependency graph, so the objection that private dependency structures make multiplicity implausible disappears. Replication creates a society with a common public issue architecture and repeated conditional approval templates. The graph may have large in-degree, but that is a restriction on the computational family, not evidence that population mass is meaningless. The continuous problem remains a well-defined exact winner-determination problem, and the discrete hardness transfers directly.
Theorem 4 supplies the strongest affirmative case and leaves the negative position with very little room. With a common graph and fixed in-degree \(k\), a mass version can enumerate the same \(O(m d^{k+1})\) local purchases. For each candidate purchase, its price is found by sorting the \(\tau\) rational budget breakpoints and solving the weighted water-filling equation. There are at most \(m\) rounds, and rational arithmetic remains polynomially bounded. Thus the continuous problem has a genuine Class A algorithm for arbitrarily large repeated populations, not merely a hardness embedding.
It is fair to say that this algorithm is a weighted implementation of the discrete one rather than a dramatic application of column generation or convex analysis. But “the answer is obtained by a simple inherited algorithm” is not a valid objection here: the programme explicitly treats structural insight plus continuous optimization, and even a well-posed mirror with a comparatively dull answer remains useful. Rejecting this mirror would amount to rejecting the high-multiplicity methodology itself.
So the honest negative case is weak. The three anchors all have legitimate population-mass formulations; identity is irrelevant once the complete conditional ballot is included in the type; and neither common graphs nor bounded-degree cohorts eliminate multiplicity. The only serious criticism is that these mirrors may yield limited new mathematics beyond weighted simulation. That is a criticism of expected payoff, not a convincing claim that no worthwhile continuous mirror exists.
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.