assign ANON records to RAW records under a global one-to-one constraint

[match_greedy()] lets every ANON record grab its own best RAW record independently, so one popular RAW record can be claimed by many ANON records. If the attacker knows that the two data sets describe the *same* people – one row each – that is a wasted constraint. `match_optimal()` spends it: it chooses the assignment minimising the *total* score over all ANON records at once, subject to no RAW record being used twice. This is the linear sum assignment problem, solved exactly by the Hungarian algorithm.

Usage

match_optimal(
  scores,
  sampling_rate = 1,
  seed = 0L,
  dummy_cost = NULL,
  solver = "clue",
  block = NULL,
  warn_size = 1000L,
  max_size = 5000L,
  confidence = c("margin", "tie"),
  min_confidence = 0,
  tolerance = reid_tie_tolerance()
)

Arguments

scores: a score table with columns RAW_ROW_NUMBER, ANON_ROW_NUMBER and SCORE, as produced by a `score_*()` function or [combine_scores()]. Its `score_type` attribute decides the orientation. Candidate pairs absent from the table are treated as forbidden, never as free.
sampling_rate: fraction of ANON records assumed to have their true RAW counterpart present in `scores`, in (0, 1]. The default 1 is the classic "same people on both sides" assumption. Lower it when only part of the population overlaps.
seed: integer seed (default 0L) used to shuffle rows and columns before solving, so that the choice among equal-cost optimal assignments depends on the seed rather than on incidental row order. NULL uses the ambient RNG stream.
dummy_cost: cost of declining to guess. NULL (default) derives it from the data as the `n_real / n_anon` quantile of the per-ANON best score, so that roughly the expected number of records is matched. Give a number to set the rejection threshold explicitly; it is interpreted on the minimised score scale, shifted so the smallest score in `scores` is 0.
solver: name of the linear-assignment backend (see [reid_lsap_solvers()]). Only "clue" is available today.
block: optional vector of length `nrow(scores)` splitting the candidate pairs into independent sub-problems. Every candidate pair of a given ANON record must fall in the same block.
warn_size: problem size (the larger matrix dimension) above which a runtime warning is issued (default 1000). NULL disables it.
max_size: problem size above which this stops with an error instead of running for many minutes (default 5000). NULL disables the guard.
confidence: how to fill the CONFIDENCE column: `"margin"` (default since Issue #44, eccentricity) or `"tie"` (`1 / tie size`). See [reid_confidence()] and the "Changed defaults" section of [match_greedy()]. Note that this is a know about the one-to-one constraint; a record the constraint pushed off its first choice still reports the confidence of that first choice under `"margin"`.
min_confidence: decline to guess below this confidence (default 0). Applied on top of any declining the padding already did.
tolerance: relative tolerance for deciding that two candidate scores are tied, default `sqrt(.Machine$double.eps)` (Issue #61), so that `match_optimal()` and [match_greedy()] agree on what "tied" means. It applies to **both** the reported CONFIDENCE and the assignment itself; see "Why the tolerance reaches the solver" below. Pass 0 for the exact comparison used before #108.

Value

a data frame with the same four columns as [match_greedy()] – ANON_ROW_NUMBER, RAW_ROW_NUMBER, CONFIDENCE, RESULT – one row per ANON record, ordered by ANON_ROW_NUMBER. `RAW_ROW_NUMBER` is NA for a record the assignment declined to guess.

Details

Because the constraint is real information, the resulting success rate is a better upper bound on attacker capability than the greedy one – *but only while the one-to-one premise actually holds*. Read the next section before reporting a number from this function.

When the one-to-one premise does not hold – measured

If only part of the population appears on both sides – the release is a sample, or the attacker's background knowledge covers only some people – then some ANON records have no correct answer available at all. Forcing *those* records to take a RAW record anyway does not merely waste a guess: the assignment is exclusive, so a record with no true match occupies the RAW record that some other ANON record needed, and the damage propagates.

This was measured (150 RAW x 150 ANON, two numeric attributes, Gaussian noise sd 3, 20 seeds; script in the Issue #15 verification log):

overlap	greedy	optimal, no padding	optimal, padded
150/150	0.571	0.656	0.656
120/150	0.437	0.357	0.401
90/150	0.329	0.225	0.237
60/150	0.227	0.156	0.124
30/150	0.117	0.070	0.038

Two things to take from that. First, a false one-to-one premise is *worse than useless*: from 120/150 downwards `match_optimal()` reports a lower success rate than [match_greedy()] on the same data. A tool whose job is to find risk must not be run in a configuration where it under-reports, so **use [match_greedy()] as the reference whenever the overlap is partial or unknown** (docs/lessons-learned.md section 2). Second, padding does *not* restore the raw success rate to the greedy level – that was the expected outcome and the measurement rejected it. What padding buys is precision: at 90/150 overlap it lifts precision among the records actually guessed from 0.228 to about 0.39, at a coverage of `sampling_rate`.

`sampling_rate` is how a partial overlap is declared. It is the fraction of ANON records believed to have their true RAW counterpart present in `scores`. The cost matrix is padded with that many dummy "no guess" columns, priced at `dummy_cost`, and an ANON record whose best real candidate is worse than `dummy_cost` takes the dummy instead: it is reported with `RAW_ROW_NUMBER = NA`, `CONFIDENCE = 0` and `RESULT = FALSE`. With the default `dummy_cost` the fraction of records actually guessed comes out at `sampling_rate`.

Dummy columns are also added whenever there are fewer RAW records than ANON records, since a one-to-one assignment is otherwise infeasible.

The premise *does* hold when ANON is a strict subsample of RAW (every ANON record has its counterpart in the attacker's knowledge). There `match_optimal()` never loses, but its advantage shrinks as the subsample does, because a smaller ANON side leaves more spare RAW records and the exclusivity constraint binds less. Measured deltas over greedy, 40 seeds: +0.089 at 150 of 150, +0.031 at 100 of 150, +0.014 at 60 of 150 and -0.003 (not distinguishable from zero) at 30 of 150.

The size of the gain also depends on how much signal the score carries. At full overlap with 150 people and two numeric attributes, the advantage was +0.039 at noise sd 1, +0.097 at sd 3, and indistinguishable from zero from sd 8 upwards – once almost nobody is identifiable, there is no structure for the constraint to exploit.

Cost and practical limits

Two separate walls, and only one of them is the solver's fault.

* **Time.** The Hungarian algorithm is `O(n^3)`. Measured on dense random matrices with `clue::solve_LSAP()`: n = 500 about 0.2 s, n = 1000 about 1.7 s, n = 2000 about 17 s, n = 3000 about 63 s. Doubling `n` costs roughly ten times as much. `match_optimal()` warns above `warn_size` (default 1000) and refuses above `max_size` (default 5000, which would run for many minutes). * **Memory.** The cost matrix is `n_anon x n_raw` dense, and so is the candidate table feeding it: 10,000 people is 1e8 pairs (about 1.5 GB), 100,000 people is 1e10 (about 149 GB). No solver fixes that; only candidate blocking does, and that is out of scope here.

`block` is the escape hatch in the meantime: it splits the problem into independent sub-problems. Splitting is not free – the one-to-one constraint then only holds *within* a block, so the same RAW record may be used in two blocks and the result is optimal per block, not globally. Pass blocks that genuinely cannot contain each other's true matches (same region, same birth year, ...) and the loss is nil; pass arbitrary ones and it is an approximation. Either way the choice is the caller's and visible.

Why the tolerance reaches the solver

Issue #61 gave this function a `tolerance` and applied it only to the reported CONFIDENCE, reasoning that "perturbing the solver's input to make a report unit-invariant could change which assignment is optimal". Issue #108 measured that reasoning and it runs the wrong way round.

The cost the solver minimises is a *sum*, so an instance can be degenerate – two different assignments costing exactly the same in real arithmetic – while every individual candidate score is distinct. Leaving the raw costs in place does not preserve neutrality there; it hands the choice to the last bit, and hands it *deterministically*. Measured on 60 independent 2x2 blocks in which matching straight across and matching crosswise are exactly equally good (true success rate 0.5), 7.1e-15 of representation noise – the gap between `42.3 - 41.2` and `43.4 - 42.3` – moved the reported rate to **0.0000** when it fell on the true pairs and to **1.0000** when it fell on the decoys, over 20 seeds each. Applying the tolerance gives 0.5175 in both, the same as the exactly-tied table. [match_greedy()] reported 0.5100 on all three, because #61 had already fixed it there.

Both directions are wrong and one of them is the quiet one (`docs/lessons-learned.md` section 2). Snapping the costs restores the tie, and the row/column shuffle then breaks it on the seed, which is the same rule the rest of the package uses.

The residual risk the old comment named is real but bounded: snapping moves each cost by at most `tolerance` relative, so it can only reorder assignments already separated by less than that – which is rounding noise, not evidence. Checked on eight two-attribute fixtures (30 records, Gaussian noise sd 3) the assignment is identical with `tolerance = 0` and with the default. Pass `tolerance = 0` to get the pre-#108 behaviour back.

**This does not make the assignment unit-invariant, and #108 does not claim it does.** The tolerance is defined within one ANON record's candidate list, while the degeneracy of an assignment problem is a property of sums *across* records, so a near-tie built from within-record gaps larger than `tolerance` survives. Re-expressing the same 1-D data in 1/10 units changed the returned assignment in 18 of 200 (seed, trial) cells with `tolerance = 0` and in 28 of 200 with the default – *more*, not fewer. Every one of those 56 cases achieved an identical total cost: they are alternative optima, and there are more of them precisely because the rounding noise is no longer resolving them falsely. What the tolerance fixes is that the reported rate is now right in expectation; which optimum comes back still depends on the seed and on the backend, and the extra run-to-run spread is what [reid_evaluate()]'s `success_sd` is for.

Examples

raw <- data.frame(ROW_NUMBER = 1:5, V = c(10, 20, 30, 40, 50))
d <- join_raw_anon_data(raw, raw)
match_optimal(score_num(d, "V"))
#>   ANON_ROW_NUMBER RAW_ROW_NUMBER CONFIDENCE RESULT
#> 1               1              1  0.6324555   TRUE
#> 2               2              2  0.8770580   TRUE
#> 3               3              3  1.1952286   TRUE
#> 4               4              4  0.8770580   TRUE
#> 5               5              5  0.6324555   TRUE