| paper | Improved Rank Aggregation Under Fairness Constraint |
| authors | Diptarka Chakraborty, Himika Das, Sanjana Dey, Alvin Hong Yao Yan |
| venue | IJCAI 2025 |
| filed under | voting · weighted-tournaments |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 5
statement extracted from the paper’s text layer
Given a rational distribution \(\mu\) over complete rankings \(\pi\in S_d\), candidate groups \(G_1,\ldots,G_g\), parameters \(\bar\alpha,\bar\beta\), and \(k\), find \(L\subseteq[d]\) with \(|L|=k\) and \(\lfloor\alpha_i k\rfloor\le |L\cap G_i|\le\lceil\beta_i k\rceil\) for every \(i\), minimizing \(B_\mu(L)=\sum_{x\in L}\sum_{y\notin L}\Pr_{\pi\sim\mu}[y\prec_\pi x]\).
Types are complete rankings \(\pi\in S_d\) with rational masses \(\mu_\pi\); the decision variable is the candidate set \(L\), and the objective is the expected Kendall cost of placing \(L\) above its complement, \(B_\mu(L)\).
Theorem 5 uses \(\mu\) only through pairwise marginals and optimizes a candidate set, so its population role is compression rather than population-side intervention; this bounds novelty but not well-posedness.
fatal: False
The mirror covers Theorem 5 exactly and the pairwise cross-block stage underlying Theorem 7; it leaves the full weighted-input transfer of Theorem 7 and the generic Theorem 10 framework unestablished.
The strongest positive case is a direct high-multiplicity mirror of fair rank aggregation. My lead anchor is Theorem 7; Theorem 5 is a particularly clean exact subproblem supporting it. Both are proved in this paper. Theorem 9, which supplies the unconstrained PTAS used by Theorem 7, is cited from Mathieu and Schudy.
A voter type is a complete ranking \(\pi\in S_d\) of the \(d\) candidates. A continuous society is a rational distribution \(\mu\) over these types. Concretely, the input may be given as distinct rankings \(\pi^1,\ldots,\pi^r\) with rational masses \(\lambda_1,\ldots,\lambda_r\), where \(\sum_j\lambda_j=1\). The candidates remain discrete, as do their protected groups \(G_1,\ldots,G_g\), the top-\(k\) cutoff, and the output ranking.
This is a genuine high-multiplicity regime. If \(n_\pi\) voters submit ranking \(\pi\), then \(\mu_\pi=n_\pi/n\), and
\[ \Phi_\mu(\sigma) = \sum_{\pi\in S_d}\mu_\pi K(\pi,\sigma) = \frac{1}{n}\sum_{\ell=1}^{n}K(\pi^\ell,\sigma). \]
Thus clearing denominators recovers the discrete instance exactly, up to the irrelevant factor \(n\). Duplicating voters does not change the continuous instance. The model is therefore not fractionalizing rankings or candidate allocations; it is compressing repeated ranking types.
A plausible regime is a large admissions, hiring, scholarship, or recommendation platform that aggregates rankings from millions of users, assessors, or institutional decision contexts over a fixed slate of candidates. Many users may follow the same rubric, policy template, or stable preference profile, producing perhaps \(n=10^6\) ranking providers but only \(r=10^2\) distinct complete rankings. The paper’s experimental panels of \(7\) and \(25\) voters are not themselves convincing high-multiplicity examples, but this larger repeated-profile setting is a natural application of exactly the same mathematical problem.
My lead continuous problem is Mass Fair Rank Aggregation. Given \(\mu\), candidate groups \(G_i\), parameters \(\bar\alpha,\bar\beta\), and \(k\), find a ranking \(\sigma\in S_d\) such that its top-\(k\) set satisfies
\[ \lfloor \alpha_i k\rfloor \le |G_i\cap \{\sigma(1),\ldots,\sigma(k)\}| \le \lceil \beta_i k\rceil \]
for every group \(i\), while minimizing
\[ \Phi_\mu(\sigma) = \mathbb{E}_{\pi\sim\mu}[K(\pi,\sigma)]. \]
A \((2+\varepsilon)\)-solution is a fair ranking \(\widehat\sigma\) satisfying
\[ \Phi_\mu(\widehat\sigma) \le (2+\varepsilon) \min_{\sigma\text{ fair}}\Phi_\mu(\sigma). \]
This is plainly the paper’s problem with voter multiplicities replaced by masses. The fairness constraint remains exactly the authors’ candidate-side top-\(k\) constraint, and the Kendall objective remains exactly their objective after normalization.
The expected classification is Class A for approximation. The paper’s proof constructs
\[ w(a,b)=\Pr_{\pi\sim\mu}[a\prec_\pi b], \]
which is precisely the continuous version of \(n_{ab}/n\) in Section 4. The first stage already operates on this weighted tournament, not on voter identities. The second stage is weighted rank aggregation on the two induced candidate subsets. Consequently, Theorem 7 strongly suggests a \((2+\varepsilon)\)-approximation polynomial in \(d\), the number of represented types \(r\), the encoding length of the masses, and \(1/\varepsilon\).
The qualification is important: Theorem 7 itself is stated for an explicit unweighted set \(S\) of rankings, and the paper does not state the required rationally weighted version of the cited Theorem 9. Proving that weighted-input PTAS interface is the main remaining step. I would therefore call this an honest direct mirror with an algorithmic extension obligation, rather than claim that Theorem 7 already proves the continuous result.
The supporting anchor is Theorem 5, proved here. Its continuous counterpart is Mass Colorful Top-\(k\) Block Selection. Given the same society \(\mu\), choose a set \(L\subseteq [d]\) with \(|L|=k\), satisfying the same group bounds, to minimize
\[ B_\mu(L) = \sum_{x\in L}\sum_{y\notin L} \Pr_{\pi\sim\mu}[y\prec_\pi x]. \]
This is the expected Kendall cost of the block ranking that places every candidate in \(L\) above every candidate outside \(L\). It is exactly the cross-partition term used in the proof of Theorem 7, not a newly invented fairness problem.
Theorem 5 applies directly to the pairwise-probability tournament induced by \(\mu\). Its algorithm sorts candidates by weighted in-degree, equivalently expected rank, while respecting the group lower and upper bounds. It therefore solves Mass Colorful Top-\(k\) Block Selection exactly in \(O(d^2)\) time once the pairwise probabilities are available, or in \(O(rd^2)\) time when they are computed from an \(r\)-type support list. This is the strongest part of the case: it is an exact Class A continuous mirror, and the paper has already supplied the structural theorem needed for it.
These mirrors cover the paper’s central approximation result and the exact weighted-tournament subproblem behind it. They do not attempt to continuize the ranking output, the candidate groups, or the top-\(k\) constraint. They also do not claim that Theorem 10’s generic fairness meta-algorithm automatically extends to arbitrary mass distributions.
The natural follow-up questions are whether the cited PTAS admits a clean rationally weighted formulation; whether exact Mass Fair Rank Aggregation remains NP-hard under compact type support; whether the \(2+\varepsilon\) guarantee can be improved to a PTAS; and whether Theorem 5 extends to several ordered fair blocks rather than one top-\(k\) block.
The weakest point is the unproved weighted-PTAS step in the lead mirror. A second weakness is sociological: the paper’s own datasets contain very few ranking providers, so the high-multiplicity scenario must come from a different but recognizable application. The case nevertheless survives because Theorem 5 already gives an exact continuous result, and because the paper itself reduces its main algorithm to pairwise population frequencies. The mass model preserves the rankings, the candidate-side fairness predicate, the Kendall objective, and the rational-clone correspondence; it does not merely make an easier fractional problem tractable.
I do not think an honest universal negative case survives this paper. The strongest objection is that the proposed mirror is merely a weighted reformulation: rank aggregation has no individual-level intervention, history, or identity-sensitive constraint, and the fairness condition concerns candidates rather than voters. Thus the population continuum changes only the weights in the objective. That makes the mirror less conceptually novel, but it is not a valid objection under ChoCo’s rules: high-multiplicity compression is explicitly part of the programme, and a dull continuous answer remains a legitimate computational question.
Theorem 7 is a direct mirror. Let \(\mu\) be a rational distribution over complete rankings. Then
\[ \Phi_\mu(\sigma)=\sum_{\pi}\mu_\pi K(\pi,\sigma) \]
is exactly the normalized discrete objective after clearing denominators. The candidate groups, top-\(k\) fairness constraints, feasible rankings, and Kendall distances are unchanged. Nothing identity-sensitive is being erased. A realistic regime is a large platform receiving millions of ranking reports generated by a relatively small number of rubrics, templates, or stable preference profiles.
The missing weighted version of the cited PTAS is a genuine technical obligation, but not a negative verdict. Avoiding denominator expansion is precisely the sort of high-multiplicity algorithmic question the programme is meant to expose. Failure of that extension would be a result about the mirror, not evidence that the mirror is meaningless.
Theorem 5 is even harder to defeat. With
\[ w_\mu(a,b)=\Pr_{\pi\sim\mu}[a\prec_\pi b], \]
its colorful partition objective becomes
\[ B_\mu(L)= \sum_{x\in L}\sum_{y\notin L}w_\mu(y,x), \]
the expected Kendall cost of placing all of \(L\) above its complement. The theorem already solves this weighted problem exactly by sorting candidates by weighted in-degree subject to the group bounds. The pairwise weights can be computed from a compact support representation of \(\mu\), and clearing denominators recovers the finite instance exactly.
One could say that Theorem 5 is candidate-side combinatorics rather than population computation, or that the mass distribution is only a compressed sample of reports. But those are descriptions of why the continuous gain may be modest, not grounds for rejecting the mirror. The paper has a named computational anchor, a faithful rational-clone interpretation, a plausible high-multiplicity regime, and an exact weighted theorem. The negative case is therefore weak: at most it can downgrade Theorem 7 from an established result to an extension obligation, while Theorem 5 remains a confirmed worthwhile mirror.
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.