| paper | Sampling Ex-Post Group-Fair Rankings |
| authors | Sruthi Gorantla, Amit Deshpande, Anand Louis |
| venue | IJCAI 2023 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4.1
statement extracted from the paper’s text layer
Given rational masses \(\mu=(\mu_{j,r})\) over finitely many protected-group and merit types \(t=(j,r)\), their within-group type order, \(k\), and a quota map producing integer bounds \(L_j(\mu),U_j(\mu)\), output an exact sample from \(D_\mu\): choose \(x\) uniformly from \(\{x\in\mathbb Z_{\ge0}^{\ell}:\sum_jx_j=k,\ L_j(\mu)\le x_j\le U_j(\mu)\}\), then choose uniformly a group word with counts \(x_j\) and apply the canonical within-group type fill; return infeasibility if the set is empty.
A high-multiplicity applicant pool with types \(t=(j,r)\), mass \(\mu_t\), protected groups, and within-group merit tiers; no cross-group scores; decision variables \(X\) and \(Y\) are group counts and slot assignments; the objective is exact or \(\delta\)-approximate sampling from the canonical ex-post-fair law.
The mass vector affects computation mainly through rounded group quotas, while repeated merit tiers alter the paper’s strict individual-ranking semantics, so a full distribution over named-item rankings is not preserved.
fatal: False
The mirror covers Theorems 4.1 and 4.2 for mass-defined quotas and uses Theorem 3.4’s law as its sampling target; it leaves prefix-random-walk heuristics, noisy in-group rankings, utility-maximizing re-ranking, experiments, and open problems uncovered.
Yes, but the honest case is an extension of the paper’s model rather than a literal replacement of every finite item by divisible mass. My lead is the exact-sampling result, Theorem 4.1; Theorem 4.2 gives a useful second, approximate-sampling anchor.
The natural population is a large applicant or student pool. Let a type be \(t=(j,r)\), where \(j\in[\ell]\) is the protected group and \(r\) is a finite, decision-relevant in-group merit tier. The type is complete: applicants of the same type are indistinguishable to the ranking rule. The society is a rational mass vector \(\mu=(\mu_{j,r})\), with group mass \(\mu_j=\sum_r\mu_{j,r}\). A realistic regime has millions of applicants but only a modest number \(\tau=\sum_j |Q_j|\) of group-and-tier types: for example, recurring cohorts of applicants with the same qualification band and protected-group attribute.
The ranker receives only the in-group priority order of the tiers. There is no cross-group score comparison. It must produce a randomized ranking of \(k\) interview or admission slots. The quota policy may be proportional, for example
\[ \lambda_j=\max\{0,\mu_j-\varepsilon_j^-\}, \qquad u_j=\min\{1,\mu_j+\varepsilon_j^+\}, \]
with the number of slots assigned to group \(j\) constrained by
\[ \lambda_j k\leq x_j\leq u_j k. \]
Equivalently, the instance supplies the induced integer bounds \(L_j,U_j\). The population is continuous here; the output remains a discrete top-\(k\) ranking. Thus the randomization is inherited from the paper and is not being misrepresented as the continuization.
My lead problem is Mass-Ex-Post Group-Fair Top-\(k\) Sampling.
An instance consists of rational type masses \(\mu_{j,r}\), the within-group tier orders, an integer \(k\), and rational representation bounds whose induced integer limits are \(L_j,U_j\). Define
\[ \mathcal X(\mu)= \left\{ x\in\mathbb Z_{\geq 0}^{\ell}: \sum_{j=1}^{\ell}x_j=k,\; L_j\leq x_j\leq U_j \right\}. \]
The required output is a random group assignment \(Y=(Y_1,\ldots,Y_k)\) generated as follows:
A solution is an exact sampler whose output distribution is precisely this distribution \(D_\mu\), or an infeasibility certificate if \(\mathcal X(\mu)=\varnothing\). The objective is therefore not utility maximization: it is exact implementation of the paper’s canonical noncommittal, ex-post-fair law. Every output ranking satisfies the group bounds, while every feasible group representation is equally likely.
This is recognizably the authors’ problem. It preserves their three essential ingredients: only within-group rankings are trusted, every realized ranking is ex-post group-fair, and uncertainty about inter-group comparisons is handled by uniform randomization rather than fabricated scores. Their recruitment example already supplies the natural high-multiplicity setting: a common pool with very many applicants, a small number of protected groups, and repeated hiring processes with limited top-\(k\) opportunities.
The rational-clone bridge is also clean, modulo the natural quotient over equal-type identities. Clear denominators in \(\mu\), create \(N\mu_{j,r}\) clones of every type, and take \(N\) large enough that each positive-mass group has at least \(U_j\) available applicants. The resulting finite instance has the same feasible group representations and exactly the same distribution over group assignments. A fixed tie refinement can recover named representatives, but permutations among equal-type clones are irrelevant to the paper’s fairness predicate. This is a genuine high-multiplicity regime, not merely a weighted restatement.
The computational anchor is Theorem 4.1, proved in this paper. It states that Algorithm 1 samples a uniform random group-fair representation in time \(O(k^2\ell)\). The same dynamic program solves Mass-Ex-Post Group-Fair Top-\(k\) Sampling after replacing the finite population counts by rational mass-induced quota bounds. The running time is naturally output-sensitive: producing a \(k\)-slot ranking already requires \(\Omega(k)\) output. I therefore expect this mirror to be Class A, tractable. The paper’s DP is precisely the kind of finite-dimensional counting structure that survives high multiplicity.
This anchor generates several worthwhile follow-up questions: can the exact sampler handle arbitrary prefix bounds \(L_{ij},U_{ij}\) rather than only one top-\(k\) constraint; can one obtain a sampler whose dependence is polynomial in \(\log k\) when the output is represented compactly; and how does one couple the samples as \(\mu\) changes slightly?
A second, supporting anchor is Theorem 4.2, also proved in the paper, although its implementation invokes the cited convex-body sampling machinery of Cousins and Vempala. The corresponding problem is Interior-Mass Approximate Group-Fair Sampling.
The instance is the same, with an accuracy parameter \(\delta>0\), but it is restricted to quota systems having the paper’s interior-slack parameter \(\Delta\). The requirement is to output a top-\(k\) ranking whose distribution is within total variation distance \(\delta\) of \(D_\mu\). Internally, the algorithm forms the polytope
\[ K_\mu= \left\{ x\in\mathbb R^\ell: \sum_jx_j=k,\; L_j\leq x_j\leq U_j \right\}, \]
samples in an expanded version of this polytope, rounds to a lattice representation, rejects infeasible points, and then samples the group word uniformly conditional on the rounded representation.
Theorem 4.2 gives the expected oracle-call bound under its stated \(\delta\)- and \(\Delta\)-conditions; in particular, for constant \(\delta<e^{-2}\) and \(\Delta=\Omega(\ell^{1.5})\), the expected number of calls is constant and each call takes \(O^*(k^2\ell^2)\) time. The continuous mirror is again expected to be Class A, especially in the practically important regime where representation quotas have genuine slack rather than being razor-tight.
This second anchor matters because it connects the paper to the programme’s continuous-optimization motivation. The population mass \(\mu\) defines the quota geometry, while convex sampling supplies an efficient approximate implementation. But the polytope is only an internal algorithmic device: the population, not the output space, is the continuous object.
The scope should remain narrow. These mirrors cover Theorems 4.1 and 4.2 and the distributional foundation supplied by Theorem 3.4. They do not claim to cover the heuristic prefix-random-walk method in Section 4.3, the empirical results, or the paper’s open problem about noisy in-group rankings. Those extensions are plausible research questions, but they are not already established by the paper.
The weakest point is that the original paper ranks individually named items with a complete in-group order, whereas the mirror groups applicants into repeated types and treats within-type identities as irrelevant. If the authors regard every individual position in the in-group list as essential, then this is not a direct mirror. It is an author-recognizable high-multiplicity extension: repeated applicant cohorts, canonical within-group priority, and the same ex-post group-fair ranking law. The case also uses applicants rather than voters as the continuous population, which is natural for ranking-as-opportunity-allocation but weaker than a literal voter-profile interpretation.
That weakness does not undermine the lead result. The paper’s actual fairness predicate is group representation in the top ranks, and its sampling law depends on group counts and in-group order—not on the names of individual applicants. In precisely the large-pool, few-type regime where a continuous population is sensible, Theorem 4.1 gives a direct polynomial-time Class-A mirror.
The negative case turns on a structural dilemma that affects both proposed anchors. The paper does contain named computational results, so “no computational result” is not available. The problem is that its computation is about ranking individually ordered items, whereas the proposed mirror makes the ranked population interchangeable.
In the paper, an assignment \(y\) determines the actual ranking because, if group \(j\) receives \(x_j\) positions, those positions are filled by the first \(x_j\) named items in group \(j\)’s in-group order. That order is not incidental: it is exactly Axiom 3.1. Hence a complete type must include the item’s position, or an equivalent decision-relevant merit rank. But then the top \(k\) positions in each group are distinct types. If the population grows while \(k\) is fixed, the duplicated mass lies in the irrelevant tail and the selected items remain essentially singletons. If \(k\) grows with the population, the model needs a continuum of rank quantiles rather than the paper’s finite ordered lists.
The proposed cohort type \(t=(j,r)\) avoids this only by replacing the paper’s strict in-group ranking with merit tiers. Multiple applicants of type \((j,r)\) are tied, so the paper’s axiom no longer determines their ranking. A fixed tie-breaking order does not solve this: it makes clone identity and clone position relevant again, contrary to the claim that the applicants are the same type. Random tie-breaking changes the output distribution. Thus the denominator-clearing “clone” construction preserves the group-assignment word, but not the paper’s distribution over rankings of individuals.
If one deliberately discards individual identities and asks only for a random group word, Theorem 4.1 does transfer—but then the proposed continuous society has almost disappeared. Once the quota bounds \(L_j,U_j\) have been computed, the dynamic program does not use \(\mu\), the within-group type masses, or the number of applicants. All societies inducing the same integer bounds become the same instance. This is a quota sampler parameterized by real-valued inputs, not a computational problem whose population is continuous. The paper’s complete ranking object has been removed precisely to obtain the transfer.
There is also no canonical limit that repairs this. With fixed \(k\), a continuous population supplies an unlimited reservoir of candidates but contributes no mass to the finite selected ranking. With \(k\) proportional to population size, the output must become a ranking or group-assignment process over rank quantiles. The paper’s “uniform over integer representations, then uniform over finite words” does not specify such a process. Different population denominators and rounding conventions give different finite laws, while a uniform law over infinite rankings is not supplied by Theorem 4.1. Defining a new process would be a legitimate research direction, but it would no longer be the theorem’s continuous counterpart.
Theorem 4.2 does not avoid this objection. Its polytope
\[ K=\left\{x\in\mathbb{R}^{\ell}: \sum_jx_j=k,\; L_j\leq x_j\leq U_j \right\} \]
is a relaxation of the representation-count output space. The population is not being sampled or optimized over; the continuous object is the internal lattice-sampling geometry. That is precisely outcome/output-space continuity, not population continuization. Moreover, its interior-slack parameter \(\Delta\) is a lattice quantity depending on \(k\), integer bounds, and rounding. It has no invariant meaning for a society distribution. Replacing the lattice law by uniform sampling from the continuous polytope would produce a different distribution and abandon the paper’s ex-post discrete ranking law.
The same issue defeats a stronger prefix-based version. For finite \(k\), prefix constraints merely produce another finite constrained-word sampler. For a positive-mass continuum of ranks, one needs a new probability measure on measurable group-assignment paths and a new interpretation of in-group ordering. The paper’s local interchange axiom does not provide that model.
Theorem 3.4 cannot rescue the proposal either. It is an axiomatic characterization of a distribution over finite representations and finite permutations; the population distribution does not enter its statement. A continuous analogue would require replacing finite uniformity by a choice of measure on mass vectors and ranking processes. That may be worthwhile, but it is a new axiomatic model rather than a mirror of the paper’s computational result.
The honest weakness in this negative case is that a large applicant-pool model with tied merit cohorts is perfectly plausible in practice. If ChoCo accepts “mass determines group quotas, while the output is only a group word” as sufficient, then the proponent has a narrow Class-A extension. My objection is that this extension either forgets the paper’s central individual-ranking object or leaves the continuous population computationally inert. Under the programme’s stricter requirement that the population itself be the continuous object, neither Theorem 4.1 nor Theorem 4.2 supplies a 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.