Certifying Group Stability When Reviewer Bids Are Biased

Conference peer review is a matching market. Papers need reviewers, reviewers state which papers they want through bids, and the conference's assignment algorithm pairs them. Recent work treats fairness in this market as a stability question: no sub-community of researchers should be able to break away, review only each other's papers, and all end up better off. An algorithm that rules this out does so at a real cost to the worst-served papers. But the whole tradeoff is measured on paper–reviewer affinity scores built partly from self-reported bids, and bids are known to misstate reviewer expertise. We propose to measure and optimize the stability–fairness tradeoff against the range of affinities consistent with the data, rather than against the reported numbers. The central construction is a "certainly blocking" coalition: a breakaway group that would gain under every plausible true affinity, not only under the reported one.

The claim in two sentences. Much of what current evaluations count as a stability violation, or as an unfairness cost, may not be identified at all once bid bias is taken seriously. An assignment that forbids only coalitions that certainly block can spend the remaining freedom raising a guaranteed floor on the review quality of the worst-served paper. This keeps the part of stability that actually protects the conference from secession while recovering much of the fairness that exact stability gives up.

What the literature establishes and where it stops

The stability side comes from Group Fairness in Peer Review. It defines group fairness as membership in the core, meaning no coalition of author-reviewers can secede and do better. Its CoBRA algorithm runs a top-trading-cycles phase, in which agents repeatedly trade along cycles of mutual top choices, followed by a greedy filling phase. On CVPR 2017 it drives the core violation rate from nearly 100% under the standard similarity-maximizing assignment (TPMS) and the egalitarian assignment (PR4A) to 0%. TPMS core violation factors reach 3.134. The same paper reports that CoBRA degrades egalitarian welfare, meaning the minimum assignment quality over papers, relative to PR4A. It treats affinities as exact, truthful inputs. This paper supplies both our method (CoBRA is the algorithm we modify) and our motivation (the tradeoff it exposes is the one we revisit).

The self-report side comes from Counterfactual Evaluation of Peer-Review Assignment Policies. It uses the randomness that anti-collusion assignment introduces to evaluate alternative weightings of bids versus text similarity on TPDP '21 and AAAI '22. When bids and assignments are not enough to pin down outcomes, it computes partial-identification bounds on review quality under monotonicity and Lipschitz assumptions. Monotonicity says a higher bid or similarity never means lower quality. Lipschitz smoothness says similar profiles give similar quality. The paper finds that shifting weight toward text similarity (from 0.75 to 0.9 on TPDP) improves predicted expertise, which is evidence that bids misstate suitability. It does not consider stability or fairness. We reuse its bounding machinery to build our set of plausible affinities.

Three further papers constrain the design. Wisdom and Foolishness of Noisy Matching Markets shows that heavy-tailed noise in evaluations can make a stable market behave like a uniform lottery. Noise does not reliably average out, so plugging in estimates is not automatically safe. Stable Matching with Ties: Approximation Ratios and Learning shows that ties force a choice between strict stability and large utility losses for some agents. Our construction turns statistical uncertainty into exactly such ties, so its "stability trap" warns that how ties are resolved matters. A First Look at Selection Bias in Preference Elicitation for Recommendation shows that elicited preferences are skewed toward familiar and popular items. Inverse propensity scoring, which reweights each observed report by one over its probability of being reported, helps substantially. That suggests the dominant bid distortion is structured selection, not symmetric noise, and it also gives us a point-estimate baseline.

Core Claim

Let $\mathcal{A}$ be the set of affinity matrices consistent with observed bids, text similarity and review outcomes under the monotonicity and Lipschitz assumptions. A coalition $S$ certainly blocks an assignment $M$ if, for every $a \in \mathcal{A}$, $S$ has an internal reassignment that strictly improves every member's utility. It possibly blocks $M$ if this holds for some $a \in \mathcal{A}$. We seek

$$ \max_{M} \; \min_{a \in \mathcal{A}} \; \min_{p} \; u_p(M; a) \quad \text{subject to no coalition certainly blocking } M, $$

where $u_p(M;a)$ is the total affinity of paper $p$'s assigned reviewers under $a$. The objective is the certified egalitarian floor: the worst-served paper's quality under the least favorable plausible affinities.

We make three predictions. First, a large share of the TPMS and PR4A violations reported on exact affinities are only possible, not certain. Second, requiring "no certain blocking" is much weaker than exact core stability, and this slack raises the certified floor. Third, when the set $\mathcal{A}$ is very tight, the method should reduce to CoBRA. When it is very loose, it should reduce toward PR4A. Its value lies in the realistic middle.

Research Program

We first build $\mathcal{A}$. On data with bids, we adapt the counterfactual paper's linear programs to output per-pair intervals $[\underline{a}_{pr}, \overline{a}_{pr}]$ rather than policy-level bounds. On CVPR 2017, CVPR 2018 and ICLR 2018, which have similarity scores but no bids, we construct semi-synthetic markets. We treat the released affinities as ground truth and generate biased bids from them using two distortion models. The first is popularity-driven selection of the kind documented in the preference elicitation paper. The second is top-truncation, modeled on the loss-averse reporting in Modeling reputation-based behavioral biases in school choice, where reviewers under-bid on papers they fear they will not get. We then re-derive $\mathcal{A}$ from the biased bids plus similarity. This is the only way to have ground truth, and it also addresses a problem in the counterfactual paper's own outcome measure: its review-quality outcomes include self-reported expertise and confidence, which are themselves self-reports.

Next we modify CoBRA. Paper $p$ certainly prefers reviewer $r$ to $r'$ when $\underline{a}_{pr} > \overline{a}_{pr'}$. This makes each paper's ranking of reviewers an interval order, and incomparable pairs become ties. We run top-trading cycles only on certain preferences. We then replace the greedy filling phase with a linear program that resolves ties by maximizing the worst-case floor, using a max–min over the interval endpoints.

Pairwise dominance makes certain blocking a sufficient condition rather than an exact test. On TPDP-sized instances (95 papers, 35 reviewers) we therefore check certain and possible blocking exactly with a mixed-integer program. This measures how much the pairwise shortcut loses. Throughout we keep CoBRA's one-author-per-paper assumption, so that differences from CoBRA come from uncertainty handling alone.

Baselines

The naive reference point is TPMS run on reported affinities. It is what conferences deploy, and its violation rate is already reported, which lets us check our reproduction. PR4A is the fairness-first reference; it maximizes the minimum paper quality and ignores stability.

The strongest existing method on this question is CoBRA on reported affinities. Group Fairness in Peer Review reports a 0% core violation rate on CVPR 2017, against nearly 100% for TPMS and PR4A. We found no reported number on Lacuna for CoBRA's egalitarian welfare, only the qualitative degradation relative to PR4A, so we will measure it ourselves. The second strong competitor is plug-in debiasing: estimate a single affinity matrix with inverse propensity scoring and run CoBRA on it. On Yahoo! R3 with 25 clusters, MF-IPS lowers MAE from 1.3041 to 0.8327 (A First Look at Selection Bias in Preference Elicitation for Recommendation), so point-estimate debiasing is a serious threat. The third is a randomized assignment with per-pair probability caps, the anti-collusion design the counterfactual paper exploits. It represents the idea that a lottery already hedges uncertainty.

All methods receive identical affinity inputs and identical load and quota constraints. Any tuned parameter, such as the propensity model or the interval widths, gets the same held-out tuning budget.

We will count the proposal as winning if it does two things on the semi-synthetic CVPR and ICLR markets. It must keep the true core violation rate, measured on ground truth, no worse than plug-in CoBRA. And it must raise the true egalitarian floor by a margin exceeding the seed-to-seed standard deviation.

Two ablations isolate the key ingredient. The first swaps the robust filling phase for CoBRA's greedy phase while keeping interval-order top-trading cycles. The second shrinks the intervals to their midpoints, which recovers plug-in CoBRA.

Why not just…?

Why not just drop bids and assign on text similarity? The counterfactual paper's result favors this for average expertise. But the CVPR runs in the group fairness paper are essentially similarity-based, and they still show nearly 100% core violations under TPMS and a real stability–fairness gap under CoBRA. Removing bids therefore does not remove the tradeoff. Similarity is also only a proxy with its own errors. We include a similarity-only condition in the semi-synthetic runs. If it matches our method on the true floor and true violations, that is a genuine negative result, and we would report it as such.

Why not just debias the bids and run CoBRA on the estimate? This is the real threat. When bias is mild and light-tailed, a good point estimate may be enough. Wisdom and Foolishness of Noisy Matching Markets suggests plug-in stability fails when errors are heavy-tailed. Propensity estimates are also known to have high variance when propensities are misspecified. We sweep both the bias strength and the tail of the residual error. Our prediction is that plug-in CoBRA matches our method in the light-tailed regime and falls behind in the heavy-tailed one. If it never falls behind, the interval machinery is unnecessary.

Why not just randomize the assignment? Randomization hedges against uncertainty but ignores which coalitions would actually secede. The Pareto-noise regime in the noisy-markets paper shows that lottery-like outcomes throw away the signal. We run the capped randomized assignment as a baseline and report both its expected true floor and its true violation rate.

Proposed Experiments

The decisive semi-synthetic experiment runs on CVPR 2017, CVPR 2018 and ICLR 2018 with both distortion models, three bias strengths and twenty seeds. For each method we report the true core violation rate and violation factor on ground-truth affinities, the true and certified egalitarian floors, and the fraction of reported violations that are certain versus merely possible.

The real-data experiment uses TPDP '21 and, if bid data remain accessible, AAAI '22. Access to the bid data is a risk, and the TPDP analysis stands alone if AAAI '22 is unavailable. Here we report certified quantities only, since ground truth is absent, and use exact mixed-integer checks on TPDP.

Two checks would settle the question. If fewer than a modest fraction of TPMS violations are possible-but-not-certain, the premise that current evaluations overstate the tradeoff fails. If the robust filling phase gives no floor gain over greedy filling at matched certain-violation rates, the mechanism fails. Either outcome is publishable as a statement about how much the reported peer-review stability–fairness tradeoff depends on trusting self-reported bids.