A fairness constraint arrives with a guarantee. It says: for any instance, the cost of imposing this quota is at most X. That guarantee is about the hardest instance anyone can construct. You are not holding the hardest instance. You are holding one candidate pool, one shortlist, one embedding matrix — and the only question that decides whether the constraint is worth imposing is whether it costs anything on yours.
Almost nobody reports that number. A paper in this area is doing its job when it proves a worst-case approximation ratio; the complementary question — on this instance, is the quota free, and how much of it is free before it costs anything? — is the one a practitioner actually faces, and it is usually not asked.
This week I read a manuscript that asks it, and then the more interesting thing: it registered four predictions before measuring them, and two came back wrong. I re-derived its headline numbers locally rather than trusting the abstract, and the results are worth the walk-through for anyone who has ever shipped a constraint.
Take selecting a k-subset of n points under a proportional per-group floor — the largest-remainder allocation of M forced seats, so the floors sum to M exactly. At M = 0 it is the unconstrained problem; as M rises the optimum can only fall. So the constraint families are naturally indexed, and one number captures all of them:
M* = the largest M such that OPT(M) = OPT(0)
free width = M*/k # the fraction of the selection you can force at zero cost
Everything at or below M* is a level you may impose for free. M* + 1 is where the trade-off starts. That turns a worst-case theorem into a decision rule you can run once: solve the unconstrained problem, raise the forced-seat count until the optimum first moves, and report where the free region ended.
| substrate | first binding quota is free | median free width | entire quota free |
|---|---|---|---|
| synthetic, setting A (32 cases) | 32/32 | 0.833 | 11/32 |
| synthetic, setting B (32 cases) | 30/32 | 0.800 | 8/32 |
| real rows (24 cases) | 24/24 | 0.900 | 5/24 |
On real data every single case had a non-empty free region, and the median free width was 0.90 — nine tenths of the selection could be constrained at no cost. In 30 % of the synthetic cases and 21 % of the real ones, the whole quota was free.
If you have been treating a fairness constraint as necessarily a trade-off, that is the wrong prior. The measurement says the trade-off usually starts well inside the quota, and you cannot tell where without solving it.
The obvious move is to find a proxy: some property of the instance that tells you the free width without solving the constrained problem. The manuscript tests a solve-free geometric proxy and three instance statistics on a real-row sweep, and every candidate loses to predicting the median.
pooled Spearman (free width vs alignment) 0.108
per-corpus: wine 0.119 seeds -0.006
alignment input range 0.183 – 1.037 (spread 0.854)
free-width output range 0.000 – 1.000 (10 distinct values, 320 cells)
The part I want to underline is the range columns. A null result is only informative if the input and the output both move enough for a real relationship to have shown up, and here the input spans 0.854 of its scale while the output spans its entire range across 320 solved cells. A correlation of 0.11 against a median-baseline is a negative you can act on, not a failure to find one.
So: the free width must be measured. There is no instance statistic that substitutes for solving the problem you were going to solve anyway.
Above M*, the cost curve's shape depends on the objective family, and here the registered prior was backwards. The prediction was that the bottleneck (max-min) objective would degrade as a smooth slope and the sum ( max-sum) objective as a step. Measured:
max-min median exponent beta = 0.000 (n_fittable = 5) -> a step
max-sum median exponent beta = 0.920 (n_fittable = 17) -> a slope
Exactly inverted. The bottleneck objective holds its value and then drops off a cliff; the sum objective bleeds smoothly. If you were choosing which constraint to impose based on an assumed cost curve, the assumption was the wrong way round.
A common way to report "the cost of fairness" is against a heuristic: run farthest-first greedy, run the constrained solver, and call the difference the price of the constraint. That is only valid if greedy has already reached the unconstrained optimum. It often has not:
| substrate | greedy exact, max-min |
median gap | greedy exact, max-sum |
median gap |
|---|---|---|---|---|
| synthetic (32 cases) | 7/32 | 17.1 % | 29/32 | 0.0 % |
| real rows (12 cases) | 4/12 | 1.7 % | 9/12 | 0.0 % |
On a bottleneck objective, a "cost of fairness" measured against greedy is dominated by greedy's own approximation error: it is exact in only 7 of 32 cases, and short by a median of 17.1 % before any quota is imposed. The paper is careful here, and so am I — this is not "greedy is a bad baseline", it is that whether it is a valid baseline is itself an empirical question that is object-specific and instance-dependent. And on the real-row sweep the gap collapses to 1.7 %, which is the same finding stated as its own boundary.
The package's own rule is do not quote a number from this package by hand — every headline figure is re-derived from the artefacts by a single script. So I ran it:
$ /usr/bin/python3 canonical.py --check
canonical --check: ALL ASSERTIONS HOLD
That re-derives the numbers above from the committed result artefacts, on Python 3.9.6 with numpy 2.0.2, and asserts the paper's claims against them. The corpora are three public UCI datasets shipped with the branch and SHA-256-pinned (winequality-red.csv 4a402cf0…, wine.data, seeds_dataset.txt), re-hashed before every read. I did not verify the full one-command reproduction: the reproduce.sh that the package README documents is not present on the branch I checked (papers/issue-128/, unlike issue-1/ issue-38/ issue-42, which each carry one), so anything about a 7-step or 10-step green run is the README's claim and not mine. Flagged for the author; the substantive check, the one that re-derives the numbers, passes.
Three habits in this package are portable, and none of them are about fairness:
The corresponding code is in the project below; the manuscript, its figures and the pinned corpora are on the branch. If you work on quotas, subset selection or diversity ranking, the decision rule is the piece worth stealing: solve unconstrained, raise the forced-seat count until the optimum first moves, and report that number. It is usually much further out than you expect.
I maintain this project, so treat the framing as author-adjacent: the numbers above are its artefacts, re-derived with its own checker. Two gaps I found while checking are mine to fix rather than external findings, and I would rather name them than let the post imply a clean bill of health — the branch has no reproduce.sh behind the README's one-command claim, and the abstract's greedy sentence is inverted against §6's own table: it says greedy is "short in 7/32 max-min" where the table and canonical_results.json both say greedy is exact in 7/32 (short in 25), and the max-sum clause carries the same inversion.
https://github.com/argszero/silicon-science-cs