Individual fairness audit against a Lipschitz constraint

Dwork et al.'s condition is that similar individuals receive similar treatment, made precise as a Lipschitz constraint on the map from individuals to outcomes: |h(x) - h(x')| <= L d(x, x') for every pair. A pair violates it when the score gap exceeds L times the distance. The audit reports the worst offending pair, the violation count, and the smallest L that would make the given scores admissible, L_required = max |h(x) - h(x')| / d(x, x'), the Lipschitz seminorm of h on the observed pairs.

Usage

Objfair(h_values, x_pairs, L = 1, metric = NULL)

Arguments

h_values: Scores assigned by the classifier, one per person.
x_pairs: Two-column matrix of 0-based index pairs to audit.
L: Lipschitz constant, non-negative.
metric: Distance for each pair, or NULL for all ones.

Value

List with estimate, L_required, n_violations, violation_rate, max_gap, max_pair_i, max_pair_j, fair, L, n, n_pairs.

Details

Pairs at distance zero are handled separately: two individuals the metric cannot tell apart must receive the SAME score, so any gap is a violation and no finite L repairs it. Dividing by zero there would report Inf for a genuine violation and NaN for a compliant identical pair, which is the wrong way round.

Pairs are scanned in the order supplied and the running maximum uses a STRICT comparison, so a tie keeps the earlier pair in both language arms.

References

Dwork, C., Hardt, M., Pitassi, T., Reingold, O. & Zemel, R. (2012). Fairness through awareness. Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, 214-226. doi:10.1145/2090236.2090255

Examples

V <- c(1, 2, 3, 4, 5, 6, 7, 8)
M <- matrix(c(1, 2, 3, 4, 5, 6), nrow = 2)
Objfair(V, M)
#> $estimate
#> [1] 3
#> 
#> $L_required
#> [1] 3
#> 
#> $n_violations
#> [1] 3
#> 
#> $violation_rate
#> [1] 1
#> 
#> $max_gap
#> [1] 3
#> 
#> $max_pair_i
#> [1] 1
#> 
#> $max_pair_j
#> [1] 4
#> 
#> $fair
#> [1] 0
#> 
#> $L
#> [1] 1
#> 
#> $n
#> [1] 8
#> 
#> $n_pairs
#> [1] 3
#> 
#> $method
#> [1] "Individual fairness audit (Dwork et al. 2012)"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"