Robust Recourse for Binary Allocation Problems

We present the problem of algorithmic recourse for the setting of binary allocation problems. In this setting, the optimal allocation does not depend only on the prediction model and the individual's features, but also on the current available resources, decision maker's objective and other individuals currently applying for the resource.Specifically, we focus on 0-1 knapsack problems and in particular the use case of lending. We first provide a method for generating counterfactual explanations and then address the problem of recourse invalidation due to changes in allocation variables. Finally, we empirically compare our method with perturbation-robust recourse and show that our method can provide higher validity at a lower cost.