| paper | Egalitarian Judgment Aggregation |
| authors | Sirin Botan, Ronald de Haan, M. Slavkovik, Z. Terzopoulou |
| venue | ATAL 2021 |
| filed under | voting · theory |
| 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: \(\Theta_2^p\)-complete under polynomial-time many-to-one reductions; \(\mathrm{NP}\)-hard even when \(m=\tau=2\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 6
statement extracted from the paper’s text layer
Given an agenda \(\Phi\), its admissible judgment set \(\mathcal J(\Phi)\), and a rational finite-support distribution \(\mu\) over \(\mathcal J(\Phi)\), define \(\rho_\mu(K)=\max_{J\in\operatorname{supp}(\mu)}H(J,K)-\min_{J\in\operatorname{supp}(\mu)}H(J,K)\). Decide whether \(\min_{K\in\mathcal J(\Phi)}\rho_\mu(K)\) is divisible by \(4\).
Types are complete admissible judgments \(J\in\mathcal J(\Phi)\); the society is given by rational masses \(\mu_J\) summing to \(1\); the decision variable is an integral admissible collective judgment \(K\); and the objective is the support-range inequity \(\rho_\mu(K)\), with the parity predicate applied to its minimum.
The mirror is support-only: changing positive masses without changing \(\operatorname{supp}(\mu)\) never changes the problem, so it is a compressed high-multiplicity boundary case rather than a mass-sensitive continuum.
fatal: False
The mirror covers MaxEq outcome determination and its decision predicates in Propositions 6 and 7, while leaving the axiomatic, strategyproofness, MaxHam, and ASP results without separate continuous mirrors.
The strongest honest case is a high-multiplicity continuous version of the paper’s MaxEq outcome problem. My lead is a direct mirror of Proposition 7.
Let \(\Phi\) be an agenda and \(\mathcal J(\Phi)\) its logically admissible judgments. Replace the finite profile by an atomless population whose agents have types \(J\in\mathcal J(\Phi)\). A type is a complete judgment vector, since Hamming preferences are determined entirely by that vector. Let \(\mu_J\in\mathbb Q_{\ge 0}\) be the fraction of society with type \(J\), with \(\sum_J\mu_J=1\). Every individual still submits an integral judgment, and the collective outcome \(K\) must still lie in \(\mathcal J(\Phi)\); only the population has been continuized.
For \(K\in\mathcal J(\Phi)\), define its continuous inequity by
\[ \rho_\mu(K) = \max_{J:\mu_J>0} H(J,K) - \min_{J:\mu_J>0} H(J,K). \]
Equivalently,
\[ \rho_\mu(K) = \max_{J,J':\mu_J,\mu_{J'}>0} \left|H(J,K)-H(J',K)\right|. \]
The continuous MaxEq outcome problem is to output some
\[ K\in\arg\min_{K'\in\mathcal J(\Phi)}\rho_\mu(K'). \]
This is a genuine population mirror rather than outcome-space continuity: \(\mu\) is continuous mass over voter types, while judgments and the collective outcome remain binary and logically constrained.
A plausible regime is a large public consultation or organisational policy process involving millions of agents but only a modest number \(\tau\) of recurring judgment types: professional cohorts, institutional roles, or stable stakeholder blocs that agree on the same complete pattern of judgments over a set of linked policy issues. Thus \(n\gg\tau\). The type distribution is the meaningful object: \(\mu_J\) records what fraction of the population holds each admissible position, while named agent identities disappear.
The high-multiplicity dictionary is exact. Given a finite profile \((J_1,\ldots,J_n)\), set
\[ \mu_J=\frac{|\{i:J_i=J\}|}{n}. \]
Then for every outcome \(K\),
\[ \rho_\mu(K) = \max_i H(J_i,K)-\min_i H(J_i,K), \]
which is exactly the objective minimized by MaxEq. Conversely, a rational \(\mu\) can be expanded using a common denominator into a finite profile. The expansion may be exponentially longer if masses are binary encoded, but semantically it is the same high-multiplicity population. This is not a collision with the paper: the paper has finite profiles indexed by individual agents, whereas the mirror makes the population distribution itself the input object.
The lead anchor is Proposition 7, proved in this paper. In the main text it states that, given an agenda \(\Phi\) and profile \(\mathcal J\), deciding whether there exists a judgment \(J^*\in\mathcal J(\Phi)\) satisfying
\[ \max_{J',J''\in\mathcal J} \left|H(J^*,J')-H(J^*,J'')\right|=0 \]
is NP-complete. Moreover, NP-hardness holds even when the agenda consists of logically independent issues, so \(\mathcal J(\Phi)=\{0,1\}^m\).
Its continuous mirror is Continuous MaxEq-Zero:
Given \(\Phi\) and a rational finite-support distribution \(\mu\) over \(\mathcal J(\Phi)\), decide whether there exists \(K\in\mathcal J(\Phi)\) such that
\[ > \rho_\mu(K)=0. > \]
A yes-solution is such a judgment \(K\).
This asks whether the population has a logically admissible collective judgment that places every positive-mass type at exactly the same Hamming distance. It is not an average-distance or fractional-judgment problem. By assigning positive mass to the judgment types in the paper’s reduction, Proposition 7 transfers directly. The expected classification is therefore Class B: hardness survives continuization, and in fact survives even when the agenda has no logical dependencies. The combinatorics live in the issue space and the choice of \(K\), not in the number of named individuals.
A second, stronger-complexity mirror comes from Proposition 6, also proved in the paper. In the main-text numbering, it states that, given \(\Phi\) and a profile \(\mathcal J\), deciding whether
\[ \min_{J^*\in\mathcal J(\Phi)} \max_{J',J''\in\mathcal J} \left|H(J^*,J')-H(J^*,J'')\right| \]
is divisible by \(4\) is \(\Theta_2^p\)-complete. The appendix appears to renumber this statement, but Proposition 6 is its label in the main computational section.
The corresponding problem is Continuous MaxEq-Parity:
Given \(\Phi\) and rational finite-support \(\mu\), let
\[ > \rho^*(\mu)=\min_{K\in\mathcal J(\Phi)}\rho_\mu(K). > \]
Decide whether \(\rho^*(\mu)\) is divisible by \(4\).
The same normalization of a finite profile into type masses preserves \(\rho^*(\mu)\) exactly. Hence the expected classification is again Class B, with the paper’s \(\Theta_2^p\)-hardness transferring to the continuous population formulation. This is useful because it shows that the mirror preserves not merely NP-hard feasibility, but an optimization-sensitive level of the polynomial hierarchy.
Finally, Theorem 3, proved in the paper, states that the outcome-determination problem for MaxEq is \(\mathrm{FPNP}[\log,\mathrm{wit}]\)-complete under polynomial-time Levin reductions. Its input is an agenda \(\Phi\) and profile \(\mathcal J=(J_1,\ldots,J_n)\), and its task is to output some \(J^*\in\operatorname{MaxEq}(\mathcal J)\). The paper proves membership by binary-searching for the minimum inequity using logarithmically many FNP witness-oracle queries, and hardness by reducing from finding a satisfying assignment that maximizes the number of true variables.
Its mirror is Continuous MaxEq-Outcome:
Given an agenda \(\Phi\) and rational finite-support distribution \(\mu\), output some
\[ > K\in\arg\min_{K'\in\mathcal J(\Phi)}\rho_\mu(K'). > \]
This should inherit the same \(\mathrm{FPNP}[\log,\mathrm{wit}]\)-completeness, because aggregating equal judgments into masses is lossless for MaxEq and the paper’s reductions can be given positive rational mass on every constructed type. It is therefore another Class B problem, not a continuum-specific hardness result.
The authors should recognise all three mirrors as their problems: the agenda, logical consistency constraints, Hamming distances, egalitarian objective, and admissible collective judgments are unchanged. Only the finite list of agents is replaced by a distribution over indistinguishable types. I would not claim that the paper’s axiomatic results, strategyproofness results, or ASP encodings automatically yield additional continuous mirrors; the computational scope here is specifically Section 5’s outcome determination results.
The weak point is that MaxEq is support-egalitarian rather than mass-weighted. Once \(\mu_J>0\), the exact value of \(\mu_J\) does not affect \(\rho_\mu\); a tiny positive-mass type counts just as much as a large one. That is inherited from the paper’s max/min objective, which is already unchanged by duplicating agents. If ChoCo requires population mass to affect the objective continuously, this mirror will look like a compressed high-multiplicity representation rather than a new LP-style relaxation. I think it remains a legitimate mirror because egalitarianism is precisely intended to protect every represented type from being diluted by a majority, and because the paper’s discrete problem is exactly recovered. But its contribution is a clean Class B boundary case: continuization is natural here, yet it does not dissolve the computational hardness.
Natural follow-up questions are whether mass-sensitive variants based on quantiles or tolerated exceptional mass become tractable, whether the problems admit useful approximation schemes, and how their complexity changes when parameterized by the number of positive-mass types \(\tau\), the number of issues \(m\), or a succinct representation of \(\mu\).
The strongest negative case is semantic, not complexity-theoretic: the proposed mirror never makes population mass computationally relevant. MaxEq already quotients away multiplicity before any continuum is introduced.
For a finite profile \(P=(J_1,\ldots,J_n)\), let \(S(P)=\{J_i:i\le n\}\). For every admissible outcome \(K\),
\[ \max_i H(J_i,K)-\min_i H(J_i,K) = \max_{J\in S(P)}H(J,K)-\min_{J\in S(P)}H(J,K). \]
Likewise, for a distribution \(\mu\), writing \(S_\mu=\{J:\mu_J>0\}\),
\[ \rho_\mu(K) = \max_{J\in S_\mu}H(J,K)-\min_{J\in S_\mu}H(J,K). \]
Thus two societies with the same support but radically different population fractions have exactly the same outcomes. A type representing \(0.0001\%\) of the population is treated identically to one representing \(99\%\). The atomless construction does not change this: its push-forward onto the finite type space is still just a measure whose values are discarded after taking support.
This is not an objection that “continuization does not make the problem easier.” It is more basic: the proposed computational object is not a distribution over a population in any operative sense. It is a finite set of judgment types with redundant positive weights. The original MaxEq problem already has precisely that quotient structure.
This defeats the Proposition 7 mirror. Continuous MaxEq-Zero asks whether some \(K\) is equidistant from every positive-mass type. But replacing \(\mu\) by the profile containing one copy of each type in \(S_\mu\) leaves the problem unchanged. Conversely, every finite profile can be replaced by the uniform distribution on its distinct judgments. Proposition 7 therefore transfers, but only because its hard instances can be read as support sets with no multiplicity whatsoever. The reduction establishes hardness of choosing a logically admissible \(K\), not a computational phenomenon involving a continuous society.
The same problem is even clearer for Proposition 6. The value
\[ \rho^*(\mu)=\min_K \rho_\mu(K) \]
is always an integer, regardless of whether the population fractions are arbitrary rationals. Changing all masses while preserving their positivity cannot change whether \(\rho^*(\mu)\) is divisible by \(4\). Calling this a continuous parity problem gives the measure no role at all. It is a support-set version of the paper’s original integer predicate.
Theorem 3 does not repair the issue. With an explicit finite-support representation, the continuous outcome problem and the paper’s finite-profile outcome problem are polynomially interconvertible: deduplicate the profile, or create one voter per positive-mass type. The output sets are identical. If \(\mu\) is instead given by a succinct circuit, formula, or oracle, then determining which types have positive mass may itself be difficult; but that is complexity caused by the chosen representation of the measure, not by continuizing the population, and it need not inherit the theorem’s \(\mathrm{FPNP}[\log,\mathrm{wit}]\)-completeness.
A stronger proposed mirror would have to make mass matter. Natural candidates would minimize an expected disparity such as
\[ \mathbb E_{J,J'\sim\mu} \left[ \left|H(J,K)-H(J',K)\right| \right], \]
or use quantiles, permitting an exceptional \(\varepsilon\)-fraction of the population to be ignored. Those are potentially interesting computational problems, but they are not MaxEq. They abandon the paper’s defining equity requirement that no pair of participating agents have a larger satisfaction gap than necessary. A tiny minority is deliberately protected by MaxEq; weighting by mass deliberately permits it to be diluted. Adding weighted Hamming distances or further type attributes has the same status: it creates a new judgment-aggregation model rather than a population continuization of the paper’s results.
The consultation story is plausible as a story about recurring stakeholder positions. What it supports, however, is a finite set of represented positions, not a computationally meaningful distribution. The paper’s egalitarian principle treats each represented type as a constituency, irrespective of its size. That may be normatively defensible, but it means the continuous population axis has disappeared from every one of the three proposed anchors.
This negative case is not airtight. The programme might deliberately count a support-based, essential-supremum formulation as a valid Class B boundary case, and the authors could reasonably recognise the stakeholder interpretation. But then the proponent has shown a formally valid encoding of MaxEq, not a worthwhile continuization in the programme’s stronger sense. The honest objection is that all three anchors are degenerate population mirrors: their hardness survives, but the population itself has not been made continuous in any substantive computational way.
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.