| paper | Judgment Aggregation with Rationality and Feasibility Constraints |
| authors | U. Endriss |
| venue | ATAL 2018 |
| filed under | frontier · ja |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\), returning all tied winners in both formulations. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite alternative set \(X\) and a rational distribution \(\mu\) over complete ranking types \(r\in X!\), represented by its nonzero support, return all \(x\in X\) maximizing \(B_\mu(x)=\sum_r\mu_r|\{y\in X:x\succ_r y\}|\); equivalently, return the \(Winner\)-feasible judgments maximizing expected agreement under \(\mathrm{max\text{-}sum}\).
Types are complete rankings \(r\in X!\), with mass \(\mu_r\); the decision is \(x\) or its corresponding \(Winner\)-judgment, and the objective is expected Borda score \(B_\mu(x)\), equivalently expected agreement.
The opponent correctly notes that the paper does not state a separate running-time theorem and that the explicit-support mirrors collapse to finitely many aggregate statistics; this leaves the computational contribution modest, but the proponent does not fully resolve whether the simulation theorem alone meets the computational-result gate.
fatal: False
The mirror directly covers Theorems 3–5 through mass-weighted Borda, Copeland, and Uncovered Set computation. It leaves the logical characterization in Theorem 2 and the remaining aggregation-rule embeddings without separate computational mirrors.
The strongest positive case is a qualified yes: this paper has a clean continuous-population mirror, especially for its preference-embedding results. It is a Class A baseline rather than a dramatic hardness result. The paper contains no named theorem asserting \(\mathrm{NP}\)-hardness, membership in \(\mathrm{P}\), or fixed-parameter tractability. I therefore will not pretend that its references to Kemeny’s intractability are complexity anchors belonging to this paper. The anchors below are named computational characterisations proved in the paper itself: Theorems 3, 4, and 5. Theorem 3 is the strongest.
The natural regime is a large electorate voting over a fixed slate \(X\) of alternatives. A type is a complete ranking \(r\in X!\), since that is everything the paper uses about a voter. The mass \(\mu_r\) is the fraction of voters with ranking \(r\). This is plausible for a large election or participatory platform in which voters cluster around a modest number of ideological, party, or recommendation-template rankings: millions of voters, but perhaps only dozens or hundreds of distinct ranking types. The continuous object is only the electorate. Alternatives, rankings, judgments, and the eventual winner remain discrete.
A finite profile with \(n_r\) voters of type \(r\) maps exactly to \(\mu_r=n_r/n\). Thus the continuous version is not an analogy: every sum over voters becomes a weighted sum over types, and all relevant comparisons are preserved. The type is complete for the model; there are no omitted individual prices or attributes.
The lead anchor is Theorem 3, proved in this paper. It states that, on profiles of judgments satisfying the rationality constraint \(Ranking\), the aggregation rule \(\mathrm{max\text{-}sum}(\cdot,Winner)\) simulates the Borda rule. More explicitly, among the \(m\) feasible \(Winner\)-judgments \(J_x\), it selects those maximizing \(\sum_i |Eq(J_x,J_i)|\); the paper proves that this is exactly equivalent to selecting alternatives maximizing their Borda scores \(\sum_i |\{y:x\succ_i y\}|\).
The corresponding problem is Continuous Winner-Borda Aggregation. An instance consists of a finite alternative set \(X\), a rational distribution \(\mu\) over ranking types \(r\in X!\), represented by its nonzero support, and the induced ranking judgment for each type. For each \(x\in X\), define \(b_r(x)=|\{y\in X:x\succ_r y\}|\). The task is to return every \(x\) maximizing \(B_\mu(x)=\sum_r\mu_r b_r(x)\). Equivalently, choose a feasible \(Winner\)-judgment \(J_x\) maximizing expected agreement \(\sum_r\mu_r|Eq(J_x,J_r)|\). Ties are returned as a set.
This is exactly the paper’s problem with the population multiplicities compressed into masses. The factor relating expected agreement to \(B_\mu(x)\) is the same constant-plus-\(2B_\mu(x)\) calculation used in the proof of Theorem 3. The expected classification is Class A: with explicit support, all \(B_\mu(x)\) can be computed in polynomial time. For a finite profile, the continuous answer is identical to the discrete Borda answer.
The second anchor is Theorem 4, also proved here. It states that, on \(Ranking\)-rational profiles, \(\mathrm{max\text{-}num}(\cdot,Winner)\) simulates Copeland: it selects the alternatives that win the largest number of pairwise majority contests.
The corresponding problem is Continuous Winner-Copeland Aggregation. The input is \(X\) and a rational distribution \(\mu\) over complete rankings, with the promise that no pair has exactly half the mass on each side, matching the paper’s odd-\(n\) assumption. Define \(x\succ_\mu^M y\) when \(\sum_{r:x\succ_r y}\mu_r>1/2\). The task is to return every \(x\) maximizing \(|\{y:x\succ_\mu^M y\}|\). This is the mass version of the paper’s max-num objective and is again Class A under explicit support: compute all pairwise masses and then count wins.
The third anchor is Theorem 5, proved here. It states that, on \(Ranking\)-rational profiles, \(\mathrm{max\text{-}set}(\cdot,Winner)\) simulates the Uncovered Set. The relevant feasible judgments are compared by inclusion of their agreement sets with the majority judgment, and the top alternatives of the inclusion-maximal judgments are precisely the uncovered alternatives.
The corresponding problem is Continuous Winner-Uncovered Aggregation. Given \(X\) and \(\mu\), define \(D_\mu(x)=\{y:x\succ_\mu^M y\}\). Return every alternative \(x\) for which \(D_\mu(x)\) is not strictly contained in \(D_\mu(y)\) for any other \(y\). This is the continuous Uncovered Set, equivalently the set of tops extracted from the inclusion-maximal \(Winner\)-judgments. It is also Class A with explicit support: compute the majority relation and compare the \(m\) dominance sets.
These are not novelty collisions. The paper works with a finite indexed profile \(J=(J_1,\ldots,J_n)\); it never makes the society itself a distribution over types, never treats type multiplicities as the input object, and never asks for algorithms in terms of the number of distinct types and their masses. A known weighted implementation of Borda or Copeland would be supporting prior art, not a reason to reject the mirror.
The paper’s Theorem 2 gives additional support. It says that the majority rule guarantees \(\Gamma'\)-feasible outcomes on \(\Gamma\)-rational profiles exactly when \(\Gamma\models\Gamma'\) and \((\Gamma,\Gamma')\) is simple. Its population mirror is immediate: take a distribution over \(\Gamma\)-rational judgment types, define the coordinatewise mass-majority judgment, and ask whether every such distribution yields a \(\Gamma'\)-feasible outcome. Under the no-tie promise, the proof transfers from voter counts to measures; the counterexample in the proof simply uses masses such as \(1/3\). This shows that the paper’s central rationality/feasibility distinction also survives continuization, not merely its voting examples.
The further ChoCo questions are more interesting than these baseline winners: replace \(Winner\) by a richer feasibility constraint, retain \(\mathrm{max\text{-}sum}\), and study weighted feasible judgment aggregation over a distribution of types; represent \(\mu\) succinctly and ask whether the required expectations or majority relations can still be computed; or add a mass-transfer action with costs \(\gamma(r,r')\) and ask for the minimum reassignment needed to make a target alternative win. Those are genuine continuous-population optimisation problems. The paper’s Table 1 points toward them, but the paper does not provide named complexity theorems for those variants.
The weakest point is that the three anchored mirrors are almost deliberately easy. The output space under \(Winner\) has only \(m\) candidates, so replacing voter sums by mass-weighted sums produces no new hardness phenomenon. This paper therefore does not demonstrate that discrete hardness dissolves, nor does it give a pricing problem comparable to the programme’s swap-bribery examples. Its value is narrower: it supplies an exact, author-recognisable Class A foundation in which high multiplicity is meaningful, the finite-to-continuous correspondence is literal, and richer constrained or control variants can be posed without changing the underlying social-choice question.
The strongest negative case is that this paper contains no computational problem whose population is itself an object. Theorems 3–5 are representation theorems: they show that particular finite judgment-aggregation rules reproduce Borda, Copeland, and the Uncovered Set. They do not state a complexity result, an algorithmic optimization problem, or a population-sensitive decision problem. The paper’s references to Kemeny’s intractability cannot repair this: that hardness result is not proved here.
Theorem 3 is therefore not a genuine continuization anchor. For a distribution \(\mu\) over rankings, the proposed mirror computes
\[ B_\mu(x)=\sum_r \mu_r\,|\{y:x\succ_r y\}|. \]
The paper’s agreement objective is merely a constant plus \(2B_\mu(x)\). Thus the entire distribution is observed only through \(m\) aggregate score values. Whether \(\mu\) is a finite weighted profile, an ideological distribution, or an atomless measure over utility functions makes no difference: it can be pushed forward to the finitely many rankings, and then reduced again to these score totals. The proposed problem is weighted Borda tabulation, not a new continuous-population computational question.
The obvious rescue would be to let mass move between ranking types, attach conversion costs, and ask for the least reassignment making a target alternative win. But that introduces every substantive ingredient absent from the paper: a target, admissible conversions, costs, budgets, and a notion of intervention. It may define an interesting new ChoCo problem, but it is not a mirror of Theorem 3. The paper gives no principled choice among these additions, so this is a new bribery or control paper inspired by the embedding, not a continuous version of the result.
Theorem 4 fares no better. Its outcome depends only on the pairwise majority matrix
\[ p_\mu(x,y)=\sum_{r:x\succ_r y}\mu_r, \]
followed by thresholding at \(1/2\) and counting wins. Every distribution inducing the same \(\binom{m}{2}\) pairwise masses is indistinguishable to the theorem. A continuous ideological space therefore collapses to a finite weighted tournament. The proposed “Continuous Winner-Copeland Aggregation” is a change from voter counts to weighted pairwise counts, not a population-continuation that exposes a new computational object.
Theorem 5 is even more directly collapsed. The Uncovered Set is computed from the same finite majority tournament through the sets
\[ D_\mu(x)=\{y:p_\mu(x,y)>1/2\}. \]
The max-set agreement comparison adds no population-level structure: it is just an alternative encoding of inclusion relations among these finite dominance sets. A richer distribution over voters cannot matter unless the aggregation rule is changed to use information that the paper deliberately ignores.
Theorem 2 does not rescue the case. Its continuous analogue quantifies over distributions of satisfying Boolean judgments and takes coordinatewise mass majorities. The proof already uses finite mixtures—indeed, masses such as \(1/3\)—and the characterization is a logical condition on \(\Gamma\) and \(\Gamma'\), not a computational question about a society. Asking for the complexity of arbitrary propositional constraints would be a complexity-of-logic problem, not a continuization of this paper’s population.
This is not an objection that high multiplicity is nonsensical. Large electorates with repeated rankings are perfectly plausible, and I am not treating existing high-multiplicity work as a novelty collision. The problem is narrower: for every faithful type space, the paper’s rules factor through finitely many aggregate statistics. Adding identity, location, arrival time, private costs, or other attributes either has no effect and is quotiented away, or changes the problem into something the paper does not study.
So the proponent’s three anchors establish only that the paper admits obvious weighted-profile restatements. They do not establish a worthwhile continuous computational mirror. The universal claim cannot be proved in a modelling domain, and a separately designed mass-transfer variant might become interesting, but that would be a new ChoCo problem rather than a continuation of any named result in this paper.
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.