d4-conf-ecai-2025-0165

The best case is an exact high-multiplicity mirror of the paper’s sequential rules. The society becomes a distribution over approval ballots; candidates and committees remain discrete. This is population continuization, not outcome-space continuity. The natural regime is a large platform or participatory vote where many people share an approval set. With \(q\) people in each ballot cohort, the population can be \(q\) times the number of ballot types. The paper’s own interest in large elections makes that regime plausible.

My lead is Mass-seq-CC Winner, anchored by Theorem 7, proved in this paper. The theorem says that computing the seq-CC winning committee is P-hard (hence presumed inherently sequential), via a logspace reduction from OVR. OVR repeatedly deletes a highest-degree vertex, breaking ties lexicographically, and asks whether at least \(r\) vertices remain after a specified vertex \(v\) is deleted. The reduction makes graph vertices candidates, graph edges approval ballots for their two endpoints, and sets the committee size to \(m-r\), where \(m\) is the number of graph vertices. The target candidate is \(v\). Seq-CC’s successive choices then match the successive highest-degree deletions.

Here is the continuous problem. An instance is a candidate set \(C\) with a fixed lexicographic order, a committee size \(k\), and a finite list of approval types \(A\subseteq C\) with positive binary-rational masses \(\mu_A\) summing to \(1\). Starting from \(W=\varnothing\), repeatedly add the candidate maximizing
\[ \Delta(c\mid W)=\sum_{A:\,A\cap W=\varnothing,\ c\in A}\mu_A, \]
breaking ties lexicographically, until \(|W|=k\). The requested solution is the resulting committee \(W\); equivalently, one can ask whether a specified candidate belongs to it.

The reduction transfers directly: assign mass \(1/|E(G)|\) to each edge ballot. A candidate’s marginal mass is exactly its remaining degree divided by \(|E(G)|\), so every choice, including ties, matches the OVR deletion order. This gives P-hardness for the continuous problem. It is a particularly clean mirror because the authors’ rule already chooses the candidate supported by the largest *number* of newly represented voters; replacing that count by newly represented mass preserves the question. The result should be classified as hardness transferring from the discrete problem, not as continuum-specific hardness. The rule can still be simulated in polynomial time on rational masses, but exact computation is unlikely to be parallelizable unless \(\mathrm{NC}=\mathrm{P}\).

This reduction also has a high-multiplicity realization: take \(q\) agents with each edge ballot. There are \(q|E(G)|\) people but only \(|E(G)|\) ballot types, and the distribution remains the same. The support grows with the graph, so this is not a claim of hardness at fixed support size; it is hardness even when each type represents arbitrarily many people.

A second, distinct mirror is Mass-MES First-Phase Winner, anchored by Theorem 12, also proved here. It says that computing the committee selected by the first phase of the Method of Equal Shares is P-hard, through a logspace reduction from LFMIS on 3-regular graphs. The paper constructs a candidate for each graph vertex, an approval ballot for each edge, and \(m\) filler candidates, each with three singleton-ballot voters. It sets \(k=3m/2\). The graph candidates’ supporters and the filler candidates’ supporters each have three voters, so initially they all have the same MES price. When a graph candidate is elected, the shared edge-ballot supporters lose their budgets; adjacent graph candidates then cannot afford election, while nonadjacent ones remain eligible. Lexicographic order makes the selected graph candidates match the LFMIS. The paper proves the 3-regular restriction in Lemma 21, building on the cited LFMIS hardness result.

For the continuous version, the instance is \(C,k,\mu\) as above. Give each type \(A\) a per-unit-mass budget \(b_A\), initially \(k\). A candidate \(c\) is feasible when
\[ \sum_{A:\,c\in A}\mu_A b_A\geq 1. \]
For each feasible candidate, let \(\rho_c\) be the least value satisfying
\[ \sum_{A:\,c\in A}\mu_A\min(b_A,\rho_c)=1. \]
Elect a feasible candidate with minimum \(\rho_c\), breaking ties lexicographically, and update \(b_A\) to \(\max(0,b_A-\rho_c)\) for approving types. Continue until \(k\) candidates have been selected or no candidate is feasible. The solution is the selected first-phase committee.

This budget scale is the natural normalization for a unit-mass society: total initial budget is \(k\), matching the discrete total of \(n\) voters each given \(k/n\). In the reduction, put mass \(1/n\) on each edge type and \(3/n\) on each filler’s singleton type, where \(n=9m/2\). Then each candidate has supporter mass \(3/n\), and its initial budget is \(k\), so its supporters can pay exactly \(1\). Electing a graph candidate exhausts the budget on its incident edge types, reproducing the LFMIS eligibility rule. Replicating each original voter \(q\) times leaves these masses unchanged while making the population arbitrarily large relative to the support.

This second problem also falls under hardness transfer: the uniform-mass construction carries the discrete P-hardness into the continuous model. It broadens the case beyond greedy coverage: MES’s changing budgets can still be represented by a small state per approval type, without treating named voters as distinct. I would keep the scope to these two results—Theorem 7’s seq-CC and Theorem 12’s first phase of MES—not claim a mirror for every rule in Theorem 1 or for the paper’s structured-domain results.

The weakest point is that Mass-MES must interpret per-voter budgets as budget *density* over normalized population mass. That is a co-modification of the accounting, though it preserves the discrete rule exactly under high-multiplicity scaling. More generally, these mirrors do not expose a continuous-optimization shortcut: their main value is to show that the sequential computation survives the move to population mass. A further question is whether restrictions on support or ballot structure—such as single-peaked or single-crossing approval types—can make either mass problem parallelizable, and whether parameterizing by the number of types yields useful exact or approximate algorithms.