| paper | Multi-Attribute Proportional Representation |
| authors | J. Lang, P. Skowron |
| venue | AAAI 2016 |
| filed under | multiwinner · apportionment |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete, even for binary domains and support size \(\tau=2\), with dyadic society masses and integral required marginal counts. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 5
statement extracted from the paper’s text layer
Given a finite candidate database \(C\) with attribute domains \(D_1,\ldots,D_p\), an integer \(k\), and a rational population distribution \(\mu\) over voter types \(T=\prod_i D_i\), decide whether there exists an integral committee \(A\subseteq C\) with \(|A|=k\) such that, for every attribute \(i\) and value \(a\), \(\frac{|\{c\in A:X_i(c)=a\}|}{k}=\sum_{t:t_i=a}\mu_t\).
A continuum of voter types \(t\in T\) carries masses \(\mu_t\); these masses induce marginal targets \(\pi_i(a)\). The decision variable remains an integral \(k\)-element subset of the finite candidate database, and the objective is feasibility of exact marginal representation.
The electorate \(\mu\) is used only through its marginal map \(M(\mu)\), so the proposed continuization may be viewed as a provenance wrapper around the real-valued input \(\pi\).
fatal: False
The mirror covers Proposition 5 and Theorem 3 as hardness-transfer results for perfect representation. It leaves the paper's approximation guarantees, fixed-parameter algorithms, and axiomatic propositions unmirrored or requiring separate analysis.
My strongest mirror uses the paper’s own voter-based interpretation of \(\pi\). The continuous population is not the candidate database; it is the large electorate whose aggregate preferences determine the target distributions. This keeps the committee-selection problem itself intact.
A voter type is a complete vector \(t=(t_1,\ldots,t_p)\in D_1\times\cdots\times D_p\), where \(t_i\) is that voter’s preferred value for attribute \(X_i\). Let \(\mu_t\) be the fraction of the electorate of type \(t\). Thus \(N\gg\tau\): millions of voters may occupy a relatively small number of populated attribute-preference types. The induced target is
\[ \pi_i(a)=\sum_{t:t_i=a}\mu_t. \]
The finite candidate database \(C\), candidate attribute vectors, and committee size \(k\) remain exactly as in the paper. The decision variable is an integral committee \(A\subseteq C\) with \(|A|=k\); no fractional candidates or fractional committees are introduced. Its representation is
\[ r_i(a;A)=\frac{|\{c\in A:X_i(c)=a\}|}{k}. \]
The objective is exact representation: accept \(A\) precisely when \(r_i(a;A)=\pi_i(a)\) for every attribute \(i\) and value \(a\).
The natural scenario is the paper’s library example. A library chooses \(k\) films from a finite catalogue, while a very large user population expresses preferred values for genre, language, country, year, and so on. The continuous population supplies the desired marginal representation; the library still chooses an ordinary \(k\)-element collection. The paper explicitly says that \(\pi\) may come from voters who express a preferred value for every attribute, so the authors should recognise this as their problem with the electorate represented at population scale.
My lead anchor is Proposition 5:
“Given set of attributes \(X\), a set of candidates \(C\), a vector of target distributions \(\pi\), and an integer \(k\), deciding whether there is a perfect committee is NP-complete.”
This is a result proved by the paper, with the proof deferred to the full version rather than cited from earlier work. Its continuous counterpart is:
Continuous Perfect Representation. Given attributes \(X\), domains \(D_i\), a finite candidate database \(C\), a positive integer \(k\), and a rational continuous electorate \(\mu\) over complete types \(D_1\times\cdots\times D_p\), decide whether there exists \(A\subseteq C\) with \(|A|=k\) such that
\[ \frac{|\{c\in A:X_i(c)=a\}|}{k} = \sum_{t:t_i=a}\mu_t \]
for every \(i\) and \(a\).
A solution is the committee \(A\); otherwise the answer is NO. This is not merely a story about fractional targets: the population itself is the continuous object, while the selected committee remains integral.
The expected classification is Class B: hardness transfers. Every ordinary instance with rational target vector \(\pi\) can be embedded into this continuous problem. Take a uniform latent variable \(u\in[0,1]\), partition \([0,1]\) independently for each attribute into intervals of lengths \(\pi_i(a)\), and let the voter type \(t(u)\) record the interval containing \(u\) for each attribute. The resulting distribution \(\mu\) has exactly the desired marginals \(\pi_i\), and it needs only polynomially many nonzero types under a common refinement of the interval boundaries. The candidate database and \(k\) are unchanged. Hence the continuous instance has a perfect committee exactly when the original Proposition 5 instance does.
This is a particularly clean hardness transfer because the combinatorics live in the candidate database and the correlations among attributes, not in the number of individually named voters. Replacing a finite electorate by its mass distribution removes irrelevant voter identities but does not relax the hard subset-selection question.
A second, narrower anchor is Theorem 3:
“The problem of deciding whether there exists a perfect committee is W[1]-hard for the parameter \(k\), even for binary domains.”
This is also a result of the paper, not an external citation. Its continuous counterpart is:
Binary Continuous Perfect Representation\((k)\). The input is a continuous electorate \(\mu\) over binary complete types \(T=\{0,1\}^p\), a candidate database \(C\) whose attributes are binary, and an integer \(k\). Decide whether there is a \(k\)-element committee whose marginal fraction of \(1\)-valued candidates on every attribute equals the corresponding marginal of \(\mu\). The parameter is \(k\).
Again, a solution is an integral committee, not a mass allocation. The same embedding from a target vector \(\pi\) into a sparse rational \(\mu\) preserves the parameter \(k\), so the expected result is \(\mathrm{W}[1]\)-hard parameterized by \(k\), even under binary attributes. The continuous population does not dissolve the parameterized hardness because the reduction’s structure is in the candidate vectors and the requirement to select exactly \(k\) of them.
Further questions follow naturally. One can ask whether the paper’s approximation guarantees for \(\ell_1\), \(\ell_{1,\max}\), and \(\ell_\infty\) remain unchanged when the target is generated by an explicit continuous electorate rather than supplied directly. One can also ask whether the fixed-\(p\) tractability boundary survives when the electorate is represented sparsely by types, and whether high multiplicity in the candidate database yields additional aggregation or fixed-parameter algorithms.
The weakness is that this mirror may look almost too faithful: the paper already permits \(\pi\) to be a real-valued target distribution, so replacing its origin with \(\mu\) does not create a new LP or a new optimization phenomenon. A sceptic could call it a population interpretation of an already aggregated input. I would concede that it is unlikely to produce a Class A result or a continuum-specific hardness result. But that is not a defect in the mirror itself. The programme asks whether a sensible continuous-population version exists, not whether continuity must change the answer. Here the paper supplies the high-multiplicity story explicitly, the committee question remains unchanged, and Proposition 5 and Theorem 3 give honest Class B examples where discrete hardness survives continuization.
The strongest negative case is that the proposed electorate is not an operative population in this paper. It is only a provenance story for an input vector the paper already treats as primitive.
Let
\[ M(\mu)_i(a)=\sum_{t:t_i=a}\mu_t. \]
For every two electorates \(\mu\) and \(\nu\) with \(M(\mu)=M(\nu)\), the set of perfect committees, every loss value, and every answer to OPTIMALREPRESENTATION are identical. The joint distribution of voter types, the multiplicities of those types, and voter identities are never consulted. The continuous object is therefore annihilated before the computational problem begins.
This defeats Proposition 5 as a substantive continuous-population result. The interval construction is mathematically correct, even granting a sparse encoding of \(\mu\), but it proves only that every target vector \(\pi\) can be supplied with a latent electorate. It does not show that the electorate is part of the problem being solved. The actual computation remains: given \(\pi\), select \(k\) candidates. Replacing “target proportions” by “marginals of a distribution” is a generative wrapper around the same input.
The same objection applies even more directly to Theorem 3. The W[1]-hardness is preserved only because the constructed electorate contributes nothing beyond the binary marginal vector already present in the hard instance. The parameterized result is therefore not about a continuous society; it is about selecting candidate vectors. The latent electorate could be deleted without changing the instance’s meaning.
A stronger attempt would make the full type distribution matter—for example, by requiring representation of joint attribute combinations, or by assigning voters utilities over committees. But the former changes marginal MAPR into a cell-constrained problem akin to CAP, while the latter introduces a multiwinner or utility-based representation rule. Neither is a continuous mirror of the problem actually studied.
One might instead continuize the candidate database: many candidates could share an attribute type, and a committee could select type-level masses \(x_v\). But if \(x_v\) is fractional, the selected object is no longer the paper’s \(k\)-element committee; if \(x_v\) is integral, the population has not been continuized. Scaling \(k\) with the candidate pool and allowing fractional selection produces a new allocation or LP problem, not a population version of the paper’s finite subset-selection problem.
That is the best negative case: the electorate-based mirror is formally valid but substantively degenerate. It adds no population-dependent constraint, objective, or computational object. However, the universal negative cannot honestly be made airtight. Under the programme’s broad gate—where a continuous population may determine only aggregate targets—both Proposition 5 and Theorem 3 are legitimate Class B mirrors. Existing high-multiplicity apportionment work would further support their plausibility. So the proponent’s case is weak as a claim of a rich new continuization, but it survives as a formally sensible continuous-population interpretation.
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.