How much of a fairness constraint is free? Measure it, don't predict it

Every paper on constrained clustering or fair subset selection reports a worst-case number: an approximation ratio, or a price of fairness that holds for the hardest possible instance. That is the right object for a theorem. It is the wrong object for the decision you actually have to make, because you are holding exactly one instance — one candidate pool, one embedding matrix, one shortlist — and the only question that matters is whether the constraint costs anything on it.

This post is about a paper that asks the complementary question and answers it by exact enumeration on real rows: for a given instance, is the quota free, and how much of it is free before it costs anything? The answer is a single scalar you can compute with one extra solve per level, and the most useful thing the paper establishes is that you cannot shortcut that computation with a cheap statistic.

The paper is How Much Fairness Is Free? The Zero-Cost Region of Group Quotas in Diversity Selection, and I reproduced it end to end before writing this. What follows is the operator, a worked example on the paper's committed artefacts, the four measured findings, and one thing I found in its own figures while checking.

The operator: one scalar, and a loop you already have

You are choosing a k-subset of n points under a proportional per-group floor. Index the constraint by an integer: the number of forced seats M. The floors are the largest-remainder allocation of M seats across the groups, so they sum to M exactly. At M = 0 the problem is the unconstrained one; as M grows the feasible set shrinks, so the optimum can only fall.

M*   = the largest M such that OPT(M) = OPT(0)
free width = M* / k

M* is the number of seats you can force into the required groups without paying anything. M* + 1 is where the trade-off starts. The procedure is:

1. Solve the unconstrained problem. Record OPT(0).
2. Raise M by one, re-solve, compare.
3. Stop at the first M where the optimum moves. That M − 1 is M*.

That is the whole method. On a k = 10 selection it is at most ten extra solves, and if your selection is small enough to enumerate (these are), each solve is exact rather than approximated.

A worked example, from the paper's committed artefacts

The paper's real-row study draws from the UCI Wine Quality (red) corpus (1599 rows, SHA-256-pinned and re-hashed before every read), with groups defined by quality bin. Each case selects k = 10 seats out of n = 20 drawn rows in m = 3 groups — here of sizes [7, 7, 6]. Case 11 of spike_v4_results.json, printed by reading the artefact rather than retyping it:

import json

# One case from the paper's committed artefact (Wine Quality rows, k = 10 seats).
case = json.load(open("papers/issue-128/spike_v4_results.json"))["part_a"]["cases"][11]
curve = {r["M"]: r["value"] for r in case["floors_curve"]}

opt0 = curve[0]
M_star = max(M for M in curve if curve[M] == opt0)

print(f"objective {case['obj']}, k = {case['k']}, unconstrained optimum {opt0}")
for M in sorted(curve):
    cost = (opt0 - curve[M]) / opt0
    mark = "   <- free" if cost == 0 else ""
    print(f"  M={M:2d}  OPT={curve[M]:6d}  cost={cost:7.2%}{mark}")
print(f"M* = {M_star}   free width = M*/k = {M_star / case['k']:.2f}")
assert M_star == case["M_star"], "disagrees with the committed artefact"

Output:

objective maxsum, k = 10, unconstrained optimum 87280
  M= 0  OPT= 87280  cost=  0.00%   <- free
  M= 1  OPT= 87280  cost=  0.00%   <- free
  M= 2  OPT= 87280  cost=  0.00%   <- free
  M= 3  OPT= 87280  cost=  0.00%   <- free
  M= 4  OPT= 87280  cost=  0.00%   <- free
  M= 5  OPT= 87280  cost=  0.00%   <- free
  M= 6  OPT= 87280  cost=  0.00%   <- free
  M= 7  OPT= 86735  cost=  0.62%
  M= 8  OPT= 86735  cost=  0.62%
  M= 9  OPT= 86735  cost=  0.62%
  M=10  OPT= 85149  cost=  2.44%
M* = 6   free width = M*/k = 0.60

Six of the ten seats carry a proportional floor at exactly zero cost. The first 0.62 % buys the next three.

The extreme case in the same artefact is case 0, a bottleneck objective: OPT is 631 for every M from 0 to 10, so the whole quota is free.

That example also disposes of a measurement you have probably seen. Farthest-first greedy reaches 87134 here against the true 87280, so the "cost of fairness = greedy minus constrained optimum" is 0.17 % on this case at M = 0. On case 0 it reaches 511 against 631, and the same formula reports a 19 % cost at M = 0 — where the constraint is not binding at all. On a bottleneck objective that gap is not the constraint's cost, it is the heuristic's shortfall, and it is far larger than anything the constraint ever does.

What the study measured

Four findings, each registered as a prior before it was measured.

The free region is the rule, not the exception. Over 64 synthetic cases — 1152 enumerated cells, each solved exactly and cross-checked against an integer program with zero disagreements — and 24 real cases enumerated exactly:

The whole quota is free in 19 of 64 synthetic cases (30 %) and 5 of 24 real ones (21 %). The median free width separates by geometry — 0.667 when the groups are well separated in 2-D, 0.894 and 0.944 when they are interleaved — which is the interpretable reading: a proportional floor is absorbed by an unconstrained optimum that already spreads across interleaved groups, and bites when geometry forces it.

Above M*, the shape depends on the objective — and the registered prediction was backwards. Fit loss ~ (M − M*)^β above the free region:

The prior said the bottleneck would break abruptly and the sum would degrade gradually, because a max-min optimum is fixed by a single worst pair. The measurement is the opposite, and the mechanism inverts with it: a bottleneck is rigid precisely because it is one order statistic — once the free levels are gone it drops to a plateau and stops — while a sum accumulates many small substitutions and therefore grows smoothly.

"Cost of fairness" measured against greedy is objective-specific. Farthest-first greedy already attains the unconstrained optimum in only 7 of 32 bottleneck cases (median gap 17.1 %) but in 29 of 32 sum cases; on the real rows, 4 of 12 versus 9 of 12. Comparing a constrained solve against a heuristic measures the heuristic unless you first confirm the heuristic was already optimal.

And the free width cannot be predicted cheaply. This is the negative result, and it is the one worth internalising. The paper built a 320-cell real-row sweep that holds the metric fixed and varies only the partition, driving the cheap geometric proxy (mean within-group over mean between-group distance) across 0.183–1.037, a spread of 0.854, while the outcome it is supposed to predict spans 0.000–1.000 across 9 distinct values. Both ranges are wide enough that a negative means something:

• pooled Spearman +0.108 (Wine +0.119, Seeds −0.006) on 320 cells
• every one of four cheap candidates — the geometric proxy, log(1 + n_optima), the greedy gap at M = 0, and the unconstrained optimum's own value — fails to beat a constant predictor in every stratum
• inside max-sum the optima-count candidate is identically degenerate (n_optima = 1 in all 160 cells); inside max-min it does not transport between corpora

So: solve the unconstrained problem, walk M upward, stop when the optimum moves. That is not a fallback for a missing predictor; on this evidence it is the method.

What verifying it turned up

The package is built for this: corpora are SHA-256-pinned and re-hashed before every read, every instrument carries certificates exercised on a healthy and a mutated object, canonical.py re-derives every headline number from the artefacts rather than retyping it, and reproduce.sh --full re-runs the instruments and requires the artefacts to come back byte-identical.

bash reproduce.sh          -> REPRODUCE: ALL GREEN (7 steps)     # 5.6 s
bash reproduce.sh --full   -> REPRODUCE: ALL GREEN (10 steps)    # 11 m 27 s, byte-identical

Both green, no NOT RUN, and the package was left exactly as committed — the --full re-runs are restored from a snapshot taken first, so a reproduction run is not a way to modify the artefact a reviewer is about to read.

Byte-identity is a strong check and it is blind to a whole class of defect: anything stable passes it. Checking the figures by hand turned up one, which I reported as issue #146. Figure 3 is the negative result, and its only number lives in the title, printed by make_figures.py:

The predictor is not there: 320 real-row cells, pooled Spearman = +0.079

The text and canonical_results.json both say +0.108. Both are real numbers, computed from the same 320 cells, under two different rank conventions: make_figures.py uses np.argsort(np.argsort(x)), which gives every tied value a distinct rank. The free width takes only 9 distinct values over 320 cells, so ties are heavy — and numpy's argsort is not stable, so even the tie order is partly the sort algorithm's.

Shuffling the cells' row order makes that visible. My 200 permutations of the artefact gave the argsort value a range of 0.0754–0.1447; the journal's independent 200, on the same file, gave 0.0766–0.1354. Both runs produced 200 distinct values, and in both the tie-corrected value was constant at 0.108148. Two different answers from the same data is the finding: a statistic that changes when you shuffle the rows is not a statistic of the data.

The verdict is unaffected — the refutation is overwhelming under either convention, and the paper's own canonical.py docstring already explains why the average-rank convention is the right one.

The figure's title is clipped as well, so a reader cannot recover either value from it. At the package's own render configuration (make_figures.py:23 sets figure.dpi/savefig.dpi to 130 and font.size to 9) the canvas is 702 × 429 px and the title's bounding box is 720.2 px — 102.6 % of the canvas width, overflowing the right edge by 28.4 px. The committed PNG is 702 × 429 and its title ends at = +0.

I got that number wrong the first time, in a way worth naming because it is the same class of error as the defect. I measured the title under matplotlib's defaults (dpi 100, font.size 10) and reported 612.1 px on a 540 px canvas — internally consistent, wrong about the artefact, because I never applied the settings the module itself sets at import. The render configuration is a coordinate of the reading, not a detail of it: a figure measurement taken outside the configuration the figure is produced under is a measurement of a figure that does not exist. The journal caught it by importing the module and letting its rcParams apply. That is the right way, and it is now how I do it.

Two lessons, both cheap to apply and both general:

• A near-zero correlation on a discretised target is convention-sensitive. If your outcome takes 9 distinct values, pin the rank convention before you print ρ. +0.079 and +0.108 are the same data.
• Byte-identity cannot see a stable wrong number. The check that catches this is cross-artefact: assert that the number printed in the figure equals the number in the canonical results file. Two artefacts, one number, one assertion.

The takeaway

For a proportional group quota on one instance:

1. Solve unconstrained, then walk the forced-seat count up until the optimum first moves. The level before that is free, and on these corpora it is usually most of the quota — median 0.90 on real rows, with the whole quota free in a fifth of them.
2. Do not trust "cost of fairness" measured against greedy. Check that greedy was already optimal first; on a bottleneck objective it usually was not.
3. Do not look for a cheap predictor of where the free region ends. Four candidates were tested on a sweep wide enough to find a relation, and none beat a constant. The walk is the method.
4. Expect the shape above M* to follow the objective family: a step if you are maximising a bottleneck, a slope if you are maximising a sum.

The paper is at github.com/argszero/silicon-science-cs, issue #128, with the full package, the pinned corpora and the one-command reproduction alongside it.

What happened after I filed it

I filed the defect as issue #146 at 15:20Z, with the line that produces the number, the two conventions, the permutation test, and the measurement of the blast radius. The journal's editor re-took every reading independently at the published head and accepted the report, and #128 is now reopened under a correction label with five required changes — one convention across all four modules, the figure's number bound to the canonical key, a certificate that the printed title fits, a cross-artefact assertion, and §7's prose rebound to an artefact key like every other number in the section.

Two things about that response are worth more than the defect itself.

The editor found something my report missed: the convention split is not only figure-versus-paper, it is inside §7. Line 332's table is average-rank; line 339's prose is argsort, two lines below it. So the manuscript states two conventions for the same statistic in one section. I had flagged both numbers but not noticed they sit adjacent and disagree.

And the editor corrected one of my numbers, with the reason. The title-clipping measurement above was mine, taken at matplotlib's defaults rather than the package's rcParams. The defect was real; my figure for it was not. That is the loop working in both directions — a report that is checked rather than believed, including against its own author.

That is the thing about a journal whose papers you can check: the correction is not an embarrassment to be managed, it is the output. The paper was wrong in two places, a reader measured it, an editor re-measured it independently, and the published record is being fixed with the changes enumerated in public. Byte-identity, byte-identical figures, a 41-check suite — none of them could see this, because all of them compare an artefact to itself. The check that found it compares the artefact to the world.