d4-conf-aaai-2008-0270

The strongest mirror is continuous voting-game equivalence, anchored by Theorem 4 (proved in this paper). The theorem says that deciding whether two given vector weighted voting games have the same winning coalitions is co-NP-complete, even when every weight is \(0\) or \(1\), so both games are monotone.

A plausible regime is a very large federation or membership organization whose members fall into a small number of voting classes. Many members may share the same voting role under both rules being compared. For this comparison, a type is the pair of their complete weight vectors in the two games. If there are \(n\) members but only \(\tau\) such pairs, with \(\tau\ll n\), the society is represented by rational masses \(\mu_t\) summing to \(1\).

Theorem 4’s mirror: Continuous Vector-Game Equivalence. An instance consists of those masses, two rational quota vectors \(b,\hat b\), and type weights \(a_t\in\{0,1\}^k\) and \(\hat a_t\in\{0,1\}^{\ell}\). A coalition is represented by \(x_t\in[0,\mu_t]\), the mass selected from each type. The games accept that coalition respectively when
\[ \sum_t x_t a_t\ge b \quad\text{and}\quad \sum_t x_t\hat a_t\ge \hat b, \]
with inequalities interpreted coordinatewise. Decide whether they accept exactly the same mass coalitions; a NO solution can give a distinguishing vector \(x\).

This is in P, with running time polynomial in \(\tau,k,\ell\), and the input bit length \(L\). To test whether the first game accepts a coalition the second rejects, try each row \(j\) of the second game and test feasibility of \(Ax\ge b\), \(\hat A_jx<\hat b_j\), and \(0\le x\le\mu\); then reverse the games. Each strict inequality can be checked by maximizing a slack variable and testing whether its optimum is positive. Thus the Boolean coalition search becomes a polynomial number of rational LP feasibility checks. I would expect this mirror to be tractable (Class A). It preserves the paper’s underlying question—whether two voting rules define the same winners—and changes the coalition domain to mass selections in an atomless population.

A second anchor tests whether that tractability is only an effect of removing variable dimension. Theorem 5 (proved here) says that equivalence of two ordinary weighted voting games is co-NP-complete even when both games are nonnegative and hence monotone. Its reduction compares games with the same weights \(a_1,\ldots,a_n\), but quotas \(T\) and \(T+1\); they differ exactly when some subset of weights sums to \(T\).

Theorem 5’s mirror: Continuous Scalar-Game Equivalence. Types now have a pair of nonnegative scalar weights \(a_t,\hat a_t\), one for each game, and the two games have rational per-capita quotas \(Q,\hat Q\). For every \(x\in[0,\mu]\), they accept according to whether \(\sum_t a_tx_t\ge Q\) and \(\sum_t\hat a_tx_t\ge\hat Q\). Decide whether these rules agree for all \(x\), returning a distinguishing \(x\) if not. Two LP feasibility checks decide this in polynomial time in \(\tau\) and \(L\). In the reduction’s same-weight special case, partial selection fills the whole interval of attainable total weights from \(0\) to \(\sum_t\mu_ta_t\). The discrete exact-subset-sum witness is no longer needed. This is also Class A, and it shows the continuum removes hardness even in the paper’s one-dimensional setting.

A third useful anchor is Theorem 9 (proved here): both RELEVANCE and MINIMALITY are NP-complete even when all weights are \(0\) or \(1\). Here RELEVANCE asks whether deleting a specified row changes the game, and MINIMALITY asks whether every row is relevant; the paper proves hardness by reduction from VERTEX COVER.

Theorem 9’s mirror: Continuous Row Relevance and Minimality. Given one vector game \(A x\ge b\) on the same type-mass box, ask whether deleting row \(i\) changes the winning mass coalitions; continuous minimality asks whether every row is relevant. Deleting a row can only add winners, so row \(i\) is relevant exactly when there is an \(x\) satisfying all other rows but violating row \(i\): \(A_{-i}x\ge b_{-i}\), \(A_ix<b_i\), and \(0\le x\le\mu\). One strict-feasibility LP per row decides relevance, and checking all rows decides minimality, in time polynomial in \(k,\tau,L\). This is another Class A mirror of a named hardness result.

The finite-to-continuous bridge is explicit: a finite society with \(n_t\) members of type \(t\) has \(\mu_t=n_t/n\), and each discrete coalition gives a mass vector \(x_t=z_t/n\) for integer \(z_t\). The continuous mirror admits every point in the box, including fractional selections unavailable to that finite coalition. That makes it a genuine population continuization, not continuity of the outcome space. The scope here is deliberately limited to the paper’s equivalence and row-deletion results; it does not cover its dimension bounds or Theorem 11’s question about whether a two-vector game has any equivalent one-vector representation.

My weakest point is that a continuous coalition may split a type fractionally, while a finite voter cannot be split. The LP results therefore do not solve the paper’s finite problems. They establish the complexity of the high-multiplicity limit, and leave a concrete bridge question: when does a fractional distinguishing coalition have enough margin to round to a discrete one? For relevance, the corresponding question is when a row’s continuous witness survives finite-population rounding. That limitation is also what makes the comparison informative: it separates hardness caused by indivisible coalitions from hardness that would persist over mass coalitions.