RECOURSE AS A CONTRACT: CERTIFYING REALIZED RECOURSE UNDER BEHAVIORAL AND MODEL DRIFT

Algorithmic recourse recommends changes intended to reverse an unfavorable decision, but a recommendation need not be implemented exactly, and the classifier may change before the individual returns. The relevant deployment question is therefore not whether the prescribed action remains valid, but whether the realized response will be accepted by the model in force at the realized return time. We formalize this requirement as a recourse contract: a high-confidence upper bound on terminal recourse failure. In practice, behavioral responses to recommendations and model evolution are typically observed in separate, unpaired data sources. Consequently, their marginal distributions may be estimable while the dependence between them, which determines terminal risk, is not. We characterize this partial-identification problem sharply, showing that the best coupling-robust set certificate attains the worst-case endpoint of the identified risk interval, and that this endpoint can become vacuous under a Strassen-type coupling condition. We then develop finite-sample contracts that remain valid for arbitrary dependence between the two channels and for action-dependent return times. We also establish a distribution-free certification floor of order $\log (1/\delta )/\min \{N,n_d\}$, showing that limited model history creates an intrinsic barrier to strong guarantees, and identify a complementary tension between recommendation effectiveness and the transferability of behavioral evidence. Experiments on controlled synthetic environments and temporally evolving LendingClub classifiers show that independence-based and model-only certificates can substantially understate realized risk, while our contracts remain valid and expose when the available data are insufficient to support a nontrivial guarantee.