Optimizing Recourse Under Predictive Multiplicity
Organizations: Drexel University
Abstract
Algorithmic recourse identifies modifications that can change an unfavorable model prediction into a favorable one. Under predictive multiplicity, similarly performing models can disagree on individual predictions, so recourse valid for one model may fail for another. We formulate robust recourse under predictive multiplicity as a budget-constrained minimization of the worst-case validity loss across a competing set of models, which can include models with different architectures or from different hypothesis classes. We propose an oracle-efficient algorithm called ORPM and prove sufficient conditions for its convergence. We evaluate ORPM on one synthetic and five real datasets, and competing sets consist of linear, neural, mixed, and decision-tree models. Our experiments show decreasing optimization-gap bounds and high validity in many tested settings, with favorable performance against baselines designed for specific model classes or architectures. We also quantify how requiring a common action across competing models changes recourse success at a given budget and examine disparities in this success across demographic groups.
Figures & tables
Appendix figures & tables11 assets
Supplementary material from the paper’s appendix.
Appendix
| Dataset | Features before encoding | Model input features | Observations | Favorable label in source data | Immutable features |
|---|---|---|---|---|---|
| Synthetic | 2 | 2 | 2,000 ∗ | (generated positive class) | None |
| COMPAS | 7 | 7 | 6,392 | two_year_recid (no recorded two-year recidivism) | Age ( age ); sex ( sex=female ) |
| Polish | 64 | 64 | 864 | Recorded target | None |
| German | 20 | 67 | 600 | Local (good credit) | Age ( Attribute13 ); dependents ( Attribute18 ); personal status/sex (all Attribute9 indicators); foreign-worker status (all Attribute20 indicators) |
| Give Me Some Credit | 10 | 10 | 120,269 | SeriousDlqin2yrs (no serious delinquency within two years) | Age ( age ); number of dependents ( NumberOfDependents ) |
| Folktables (ACSIncome) | 10 | 10 | 195,665 | target (annual personal income >\50{,}000$ ) | Age ( AGEP ); marital status ( MAR ); place of birth ( POBP ); relationship to householder ( RELP ); sex ( SEX ); race ( RAC1P ) |
Algorithmic Recourse
Algorithmic recourse studies actionable changes that can help people obtain favorable outcomes from automated decisions.
See all 30 papers