d4-conf-aaai-2018-0671

A credible regime is a large public consultation choosing a \(k\)-member advisory council from a fixed slate. A voter’s type is their approval set \(A_t\subseteq C\); two voters share a type exactly when they approve the same candidates. With a recurring set of ballot patterns, the number of residents \(n\) can be far larger than the number of supported types \(\tau\). The committee stays discrete; the population becomes a distribution of approval types. That puts the representation question itself on population mass: a group of size \(\ell n/k\) becomes a group with mass at least \(\ell/k\).

My mirror is \(\textsf{Cont-PJR-Check}\). An instance is a candidate set \(C\), a committee size \(k\), a committee \(W\subseteq C\) with \(|W|=k\), and \(\tau\) distinct approval types \(A_t\subseteq C\) with positive binary-rational masses \(\mu_t\) summing to \(1\). Ask whether \(W\) satisfies this condition: for every \(\ell\in\{1,\ldots,k\}\) and every subpopulation described by masses \(0\le\nu_t\le\mu_t\), if \(\sum_t\nu_t\ge\ell/k\) and the types with \(\nu_t>0\) have at least \(\ell\) commonly approved candidates, then those types collectively approve at least \(\ell\) members of \(W\). A “no” solution can be given as \(\ell\) and a subset \(Q\) of types such that \(\sum_{t\in Q}\mu_t\ge\ell/k\), \(\left|\bigcap_{t\in Q}A_t\right|\ge\ell\), and \(\left|W\cap\bigcup_{t\in Q}A_t\right|<\ell\).

The anchor is Theorem 3, proved in this paper: given a finite election, target size \(k\), and size-\(k\) committee \(W\), it is coNP-complete to decide whether \(W\) provides PJR. The paper proves the hardness by reducing from BALANCED BICLIQUE, whose hardness is the cited source result.

This is a particularly direct mirror of that theorem. From a finite election, set \(\mu_t\) to the fraction of voters with ballot \(A_t\). A violating continuous group may take only part of a type’s mass, but including all of that type changes neither the group’s common approvals nor its collective approvals of \(W\); it only increases the group’s mass. So every continuous violation yields a discrete one by including all voters of its supported types. A discrete violation conversely gives a continuous one. Thus PJR checking agrees exactly on every finite election and its normalized distribution.

I therefore expect hardness to transfer: \(\textsf{Cont-PJR-Check}\) is coNP-complete in the input size, including \(m\), \(\tau\), and the rational bit length \(L\). A violation certificate is just \(\ell\) and \(Q\), which can be checked in polynomial time; Theorem 3 supplies hardness through the exact correspondence. The biclique structure lies in the candidate and approval-pattern combinatorics, not in large voter counts. And any rational profile can be realized with arbitrarily many voters per type by replicating its voters, leaving \(\mu\) and \(\tau\) unchanged. This is a Class B mirror: a genuine population-distribution question whose discrete hardness survives.

The scope here is only Theorem 3’s PJR verification result. I am not claiming a continuous restatement of the paper’s EJR algorithms or its other results. Natural follow-on questions concern the parameterized landscape of the mirror: enumerating the \(2^\tau\) subsets of supported types already gives an FPT algorithm in \(\tau\); one could seek sharper bounds or compare that parameterization with the paper’s results in \(m\) and \(n\).

The weakest point is also the source of the clean correspondence: for this axiom, splitting a type’s mass gives no new approval pattern, so continuum checking cannot relax the discrete combinatorics. That makes this a modest mirror rather than a tractability gain. But it is still the population-as-distribution question, with PJR’s quota naturally expressed as mass, and the exact discrete-to-continuous agreement is a meaningful boundary result rather than a novelty collision.