Recourse Feasibility

The foundational rule of feasible recourse: immutable features cannot be changed. A counterfactual suggesting a user alter their age or place of birth is invalid. Algorithms must hard-code these constraints into the optimization process, treating them as non-modifiable axes in the feature space. This transforms the search from an unconstrained perturbation problem into a constrained optimization within a valid action set.

Feasibility requires a causal model of the world. Changing a feature like 'education level' should cascade to update dependent features like 'income' according to a Structural Causal Model (SCM). Without causal reasoning, a counterfactual might suggest increasing income without changing education, creating an unrealistic or impossible scenario. Causal constraints ensure the counterfactual respects the data-generating process.

The action set formally defines the permissible interventions. It specifies:

• Mutable features: Variables the user can change (e.g., savings amount).
• Directionality: Whether a feature can only increase (e.g., age) or decrease (e.g., debt).
• Step size: The granularity of change (e.g., integer constraints for 'number of dependents'). This specification prevents the generation of mathematically minimal but practically useless advice.

A feasible counterfactual must be plausible, meaning it lies within the high-density region of the training data distribution. Using Mahalanobis distance instead of Euclidean distance helps achieve this by accounting for feature correlations. A counterfactual that crosses the decision boundary but falls in a zero-probability region of the data manifold is an adversarial artifact, not a viable path for recourse.

A feasible recommendation must be robust to model retraining. If a user implements a change only to find the updated model still rejects them, the recourse was fragile. Feasibility engineering often involves searching for counterfactuals that are not just on the decision boundary but are deeply embedded within the target class region, ensuring the prediction remains stable across minor model updates.

Feasibility extends beyond mathematical constraints to user-centric capabilities. A recommendation to 'increase capital gains by $50,000' is actionable for some but not all. Advanced feasibility frameworks incorporate personalized cost functions that weigh feature changes by the difficulty or financial burden they impose on a specific individual, ensuring the recourse is not just possible, but practically achievable for the end-user.

A formal specification of the permissible modifications a user can make to each feature, defining the boundary between actionable and non-actionable changes. The action set is the foundational constraint for feasible recourse.

• Components: Per-feature mutability flags, direction of change (increase/decrease), and cost functions
• Example: For loan applications, 'income' may be increasable but 'credit history length' is immutable
• Integration: Encoded directly into counterfactual generation algorithms to ensure output feasibility

A protected input attribute that cannot be changed and must be held constant when generating counterfactual explanations. Immutable features are the hard constraints of recourse feasibility.

• Common examples: Age, place of birth, race, gender, historical events
• Causal immutability: Some features are immutable due to temporal logic—you cannot change the past
• Legal immutability: Protected attributes under regulations like GDPR or the EU AI Act must never be used to prescribe changes

A hard rule encoded into a counterfactual generation algorithm that prevents the modification of immutable features or enforces causal monotonicity. Feasibility constraints ensure generated explanations respect the laws of physics and society.

• Types: Immutability constraints, directional constraints (e.g., age only increases), causal constraints from SCMs
• Enforcement: Applied as optimization constraints or post-hoc filtering during counterfactual search
• Trade-off: Tighter constraints may increase counterfactual distance but guarantee real-world applicability

The property that a counterfactual recommendation remains valid and flips the prediction even after the underlying model is retrained or slightly updated. Recourse robustness addresses the temporal dimension of feasibility.

• Problem: A counterfactual valid today may fail tomorrow if the model is updated
• Measurement: Probability that a recourse action remains valid across model retraining runs
• Mitigation: Robust recourse algorithms generate counterfactuals that cross the decision boundary with sufficient margin, accounting for model uncertainty

A counterfactual instance that lies within the high-density region of the training data distribution, ensuring the explanation is realistic and not an adversarial artifact. Plausibility is a critical dimension of feasibility.

• Why it matters: A counterfactual suggesting a 25-year-old earn $500,000/year is mathematically valid but implausible
• Measurement: Density estimation using Gaussian mixture models or autoencoder reconstruction error
• Distance metrics: Mahalanobis distance accounts for feature correlations better than Euclidean distance for plausibility assessment