| paper | d4-conf-ijcai-2019-0897 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The sole anchor is Theorem 3.5 from Celis et al., which this paper cites as prior work rather than proves. The paper's own integer program formulations are used in experiments, but appear as equations rather than a numbered theorem, lemma, corollary, or proposition stating a computational result. The fluid feasibility model is a plausible extension, but it cannot supply the required result of this paper.
fails bit a — no named computational result to mirror
The proposed fluid model covers prefix-diversity feasibility, corresponding to cited background hardness; it leaves this paper's utility objective, in-group fairness measures, and leximin balancing aside.
The positive case is narrow, but it has a real anchor. The paper itself gives no numbered computational theorem; its named hardness anchor is Theorem 3.5, which it cites from Celis, Straszak, and Vishnoi rather than proving. That theorem says that deciding whether a ranking satisfies upper-bound constraints on how many items with each property may occur in each prefix is NP-hard when an item may have \(\Delta\ge 3\) properties. The bound applies at every prefix of the ranking. The cited theorem treats upper bounds, while Yang et al. formulate diversity constraints as lower bounds. For a prefix of length \(p\), however, an upper bound \(U_{p,v}\) on a property is equivalent to a lower bound \(p-U_{p,v}\) on its binary complement. So the hardness instance can be expressed in the lower-bound language of this paper. [Celis, Straszak, and Vishnoi, *Ranking with Fairness Constraints*](https://arxiv.org/abs/1704.06840)
My lead mirror is Fluid Prefix-Feasibility. Picture a large patient-recruitment pool: millions of people, but only a modest number \(\tau\) of recurring demographic signatures, such as combinations of race and age. Rank a fraction \(\kappa\) of the pool for outreach, with representation requirements at specified rank fractions. For this feasibility question, a type is a person’s complete pattern of relevant group memberships; scores are omitted because the hardness anchor asks only whether the constraints can be met. The mass \(\mu_t\) is the fraction of the pool with type \(t\). Here the number of people is large while the number of supported types is small.
Precisely, the input is supported types \(T\), rational masses \(\mu_t\) summing to \(1\), a target ranked mass \(\kappa\), rational cutpoints \(0=r_0<\cdots<r_q=\kappa\), and lower-quota curves \(g_v\) for each group label \(v\), specified by rational values at those cutpoints and interpolated linearly between them. The question is whether mass can be assigned across the ranked interval \([0,\kappa]\) so that no type uses more than its supply and every prefix \(r\) contains at least \(g_v(r)\) mass from group \(v\). A solution can be given by rates \(\alpha_{t,j}\ge 0\): the share of rank band \(j\) occupied by type \(t\). They must satisfy \(\sum_t\alpha_{t,j}=1\), \(\sum_j(r_j-r_{j-1})\alpha_{t,j}\le\mu_t\), and, at each cutpoint \(r_j\), \(\sum_{h\le j}(r_h-r_{h-1})\sum_{t:v\in t}\alpha_{t,h}\ge g_v(r_j)\). With constant rates on each band, linear quota curves make the cutpoint checks sufficient throughout each band.
This is an LP, polynomial in \(\tau\), the number of labels and cutpoints, and the input bit length. I expect this mirror to be tractable: the discrete hardness can disappear when each candidate is an infinitesimal share of an atomless type population and the selected ranking length scales with population size. The mass allocation is the decision variable; the anchor has no utility objective to carry over.
The case is plausible because it keeps the paper’s central constraint structure—overlapping groups, ranked prefixes, and feasibility—and the paper itself motivates representative selection of patients. But the main concession is substantial: the model ranks a fraction of the population, not a fixed number \(k\) of indivisible people. That scaling is what makes mass meaningful here, and it is where the authors or a referee could say the mirror has moved too far from their problem. This is also a limited-scope mirror: it covers the cited feasibility hardness, not the paper’s score maximization, ratio and aggregate in-group fairness measures, or leximin balancing.
The natural next questions are whether the utility-maximizing ranking and leximin balancing also admit tractable mass formulations, and how large the finite-population rounding loss is when converting a feasible fluid ranking back to an integral ranked list.
The strongest negative point is that Fluid Prefix-Feasibility is not a mirror of a computational result established by this paper. Yang, Gkatzelis, and Stoyanovich introduce fairness measures, give integer-program formulations, and report experiments. The NP-hardness result they mention is Theorem 3.5 of Celis et al., cited to explain why their optimization problems are difficult; it is not their theorem. So the proponent has found a plausible continuous question for a problem in the paper’s background, but not an anchor in the paper’s results. If the task is to identify a worthwhile mirror *of this paper*, that is a real mismatch.
That mismatch does not defeat the proposed model on its own merits. The stronger version is quite natural: take types to include both group memberships and scores, let a fixed fraction of a large candidate pool receive ranks by percentile, and express utility, prefix quotas, and the two in-group fairness measures over type masses. A large recruitment pool with recurring demographic and score profiles is a credible high-multiplicity regime. Scaling the ranked mass with the pool size gives nontrivial representation constraints, and treating ranks as percentiles is a reasonable co-modification. The programme’s criteria give no basis for dismissing that model just because it changes the answer or makes the problem tractable.
So I cannot honestly defend the universal claim that there is no worthwhile continuous mirror in any scenario. The negative case is narrow: the proponent’s one anchor is borrowed from prior work, and their feasibility model drops this paper’s scores, fairness measures, and balancing objective. That is enough to reject it as a mirror of a result *proved by this paper*; it is not enough to show that a continuous extension of the paper’s ranking and balancing problem would be unworthy.
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.