Relative Explanations for Contextual Problems with Endogenous Uncertainty: An Application to Competitive Facility Location

Basic Information

• Paper ID: 2506.19155
• Title: Relative Explanations for Contextual Problems with Endogenous Uncertainty: An Application to Competitive Facility Location
• Authors: Jasone Ramírez-Ayerbe, Emma Frejinger (CIRRELT and Department of Computer Science and Operations Research, Université de Montréal)
• Classification: math.OC (Mathematical Optimization and Control)
• Publication Date: October 14, 2025 (arXiv preprint version 3)
• Paper Link: https://arxiv.org/abs/2506.19155v3

Abstract

This paper investigates contextual stochastic optimization problems with endogenous uncertainty, where decisions influence the underlying distribution. To implement such decisions in practice, ensuring their interpretability and trustworthiness is paramount. To this end, the authors compute relative counterfactual explanations, providing practitioners with concrete changes to contextual covariates necessary to satisfy specific constraints on solutions. While relative explanations have been introduced in prior literature, this is, to the authors' knowledge, the first work focusing on binary decision variables and problems with endogenous uncertainty. The authors propose a method using Wasserstein distance as a regularization term, which reduces computational time compared to the unregularized counterpart.

Research Background and Motivation

Problem Context

With the increasing application of machine learning and optimization in decision-making problems, particularly in high-stakes environments such as healthcare, housing allocation, and social services, ensuring the interpretability and trustworthiness of solutions has become critical. Institutions including the European Union, the U.S. White House Office of Science and Technology Policy, and the Canadian government have recognized the growing need for explainability.

Core Issues

1. Endogenous Uncertainty: Decision variables z influence the conditional probability distribution P(y|z,x) of random variables y
2. Explainability Requirements: Understanding how contextual changes lead to decision changes and identifying necessary changes to ensure solutions satisfy specific constraints
3. Practical Application Scenarios: For example, in medical infrastructure planning, local governments may inquire about minimal data changes that would result in opening a facility in their region

Limitations of Existing Approaches

• Existing counterfactual explanations primarily target supervised classification problems
• Lack of research on optimization problems with binary decision variables and endogenous uncertainty
• Traditional methods exhibit high computational complexity and lack effective regularization mechanisms

Core Contributions

1. Extended Research Scope: First application of relative counterfactual explanations to contextual stochastic optimization problems with endogenous uncertainty
2. Generalized Existing Methods: Allows for an expected feasible set D rather than a single target solution, generalizing existing methods based on expert-provided solutions
3. Binary Variable Handling: Addresses relative explanation problems involving binary decision variables
4. Wasserstein Regularization: Employs regularization terms that minimize the distance between distributions induced by counterfactual and factual solutions
5. Computational Efficiency Improvement: The proposed regularization method significantly reduces computational time

Methodology Details

Task Definition

Given a contextual stochastic optimization problem:

z*(x⁰) ∈ argmax_{z∈Z} E_{P(y|z,x⁰)}[r(y,z)]

where:

• z ∈ Z: vector of decision variables
• x⁰ ∈ X ⊆ ℝ^{dx}: continuous contextual covariates (features)
• y: vector of random variables capturing endogenous uncertainty
• P(y|z,x⁰): conditional probability distribution

Relative Counterfactual Explanation Definition

Definition 1.1: For a given factor α ∈ (0,∞] and desired space D, a relative explanation for problem (1) is a new context x such that there exists a feasible solution in D whose expected reward changes by at most a factor of α.

Core Optimization Problem

The computation of relative explanations can be formulated as the following non-convex optimization problem:

L*_free := min_{x∈X,z∈Z} L(x,x⁰)
s.t. E_{P(y|z,x)}[r(y,z)] ≥ α · E_{P(y|z⁰,x⁰)}[r(y,z⁰)]
     z ∈ D

Cost Function and Wasserstein Regularization

The cost function takes the following form:

L(x⁰,x) = J(x⁰,x) + λΩ(x⁰,x)

where:

• J(x⁰,x): dissimilarity component
• Ω(x⁰,x): regularization term using 2-Wasserstein distance

Wasserstein Distance Definition: For two discrete probability distributions P⁰ and P, the squared 2-Wasserstein distance is defined as:

W²₂(P⁰,P) := min_{π∈Π} ∑_{c∈C} ∑_{c'∈C} π_{cc'} δ(c,c')²

subject to constraints:

• ∑{c'∈C} π{cc'} = P⁰(c) ∀c ∈ C
• ∑{c∈C} π{cc'} = P(c') ∀c' ∈ C
• π_{cc'} ≥ 0

Technical Innovations

1. Distribution Distance Regularization: Uses Wasserstein distance to ensure counterfactual distributions remain close to factual distributions
2. Model-Agnostic Lower Bounds: Provides model-agnostic methods for computing lower bounds
3. Sparsity Induction: Achieves sparse solutions through joint application of ℓ₁ norm and Wasserstein regularization

Experimental Setup

Application Scenario: Choice-Based Competitive Facility Location Problem (CFLP)

• Model: Multinomial Logit (MNL) model
• Decision: Select a subset of candidate locations under budget constraints to maximize expected demand capture
• Utility Function: v_ = -0.1θ_ + x_d, where θ_ is distance and x_d is attractiveness score

Dataset Configuration

• Small Example: |N|=4 users, |D|=3 candidate facilities, |E|=2 competing facilities, r=2 open facilities
• Large-Scale Instances:
  • Number of users: 100, 200
  • Number of candidate facilities: 10, 20, 40
  • Budget: 4, 8
  • Competing facilities fixed at 5

Evaluation Metrics

• Computational Time: Average and median solving time
• Wasserstein Distance: W²₂
• Sparsity: Percentage of modified contextual features
• Demand Capture: Factual and counterfactual demand quantities
• ℓ₁ Norm: L1 distance of contextual changes

Implementation Details

• Solver: Gurobi 11.0.1
• Programming Environment: Python 3.11.7
• Computing Platform: Intel Core i9-10980XE processor
• Time Limit: 1 hour
• Regularization Parameters: λ ∈ {0, 0.1, 1}

Experimental Results

Main Findings

1. Significant Computational Efficiency Gains:
   • Average solving time with λ=0.1 substantially reduced compared to λ=0
   • Example: N=100, D=10, r=4, average time 137.92s for λ=0.1 vs 266.49s for λ=0
2. Improved Sparsity:
   • Wasserstein regularization enhances solution sparsity
   • Sparsity with λ=0.1 typically outperforms λ=0 cases
3. Optimality Gap:
   • In instances reaching time limits, unregularized cases exhibit significantly larger optimality gaps

Case Study Analysis

Small Example Results:

• Without Regularization (λ=0): x_=0.350, W²₂=164.917
• With Regularization (λ=0.25): x_=0.479, W²₂=90.849
• Although the regularized version exhibits larger contextual changes, it achieves smaller distribution distance with equivalent sparsity

Experimental Findings

1. Regularization Effects: Moderate Wasserstein regularization not only improves runtime and sparsity but also leads to smoother transitions in demand distributions
2. Computational Complexity: Counterfactual problems inherit the complexity of underlying factual problems, with instances having larger budget r frequently reaching time limits
3. Sparsity Mechanism: Sparse changes are achieved not only through ℓ₁ norm minimization; regularization also encourages the model to concentrate changes in fewer facilities rather than dispersing small modifications

Related Work

Counterfactual Explanations for Optimization Problems

• Bogetoft et al. (2024): Application of concepts to Data Envelopment Analysis (DEA)
• Kurtz et al. (2025): Counterfactual explanations for linear programming, formalizing weak, strong, and relative types
• Korikov Series: Computing weak counterfactual explanations for integer linear programming through inverse optimization

Contextual Optimization Problems

• Forel et al. (2023): Assumes parameters estimated from contextual covariates using random forests or k-NN as predictors
• Vivier-Ardisson et al. (2024): Extension to differentiable classifiers, including neural networks

Distinction from Related Work

1. Objective Setting: Allows expected feasible set D rather than single expert-provided targets
2. Uncertainty Type: Focuses on endogenous uncertainty
3. Variable Types: Handles binary decision variables
4. Regularization Innovation: Introduces Wasserstein distance regularization

Conclusions and Discussion

Main Conclusions

1. Method Effectiveness: Successfully extends counterfactual explanations to contextual stochastic problems with endogenous uncertainty
2. Computational Advantages: Wasserstein regularization significantly improves computational efficiency
3. Solution Quality: Obtains sparser, more interpretable explanations with smoother choice probability transitions

Limitations

1. Continuous Variable Restriction: Current formulation requires contextual covariates to be continuous; extension to categorical covariates remains challenging
2. Solution Non-Uniqueness: Solutions are typically non-unique, potentially leading to stakeholder disagreement and explanation manipulation possibilities
3. Ethical Considerations: Multiple valid counterfactual explanations may raise ethical issues, such as obscuring sensitive contextual features

Future Directions

1. Weak Counterfactuals: Compute weak counterfactuals enforcing new solution optimality rather than relative counterfactuals
2. Distribution Extensions: Extend to other probability distributions
3. Application Domains: Applications in classification optimization and pricing contextual problems
4. Uniqueness Guarantees: Incorporate objective terms ensuring solution uniqueness

In-Depth Evaluation

Strengths

1. Theoretical Contribution: First systematic application of counterfactual explanations to endogenous uncertainty problems with complete theoretical framework
2. Methodological Innovation: Wasserstein regularization introduction is both theoretically grounded and practically effective, significantly improving computational performance
3. Comprehensive Experiments: Full experimental evaluation from small-scale examples to large-scale instances with multidimensional evaluation metrics
4. Practical Value: Selected CFLP application has significant practical importance with actionable results

Weaknesses

1. Limited Applicability: Restricted to continuous contextual variables, limiting method generalizability
2. Insufficient Complexity Analysis: Lacks theoretical analysis of algorithm complexity
3. Parameter Selection: Systematic guidance for choosing Wasserstein regularization parameter λ is absent
4. Incomplete Comparative Experiments: Insufficient comparison with alternative counterfactual explanation methods

Impact

1. Academic Contribution: Opens new research directions in explainability for contextual optimization
2. Practical Value: Provides explainable decision support for facility planning, resource allocation, and related problems
3. Reproducibility: Complete code and instances provided, facilitating reproduction and extension

Applicable Scenarios

1. Facility Planning: Location decisions for medical facilities, schools, and commercial outlets
2. Resource Allocation: Public resource allocation problems requiring explainability
3. Policy Making: Government decision processes requiring transparency and interpretability
4. Business Decisions: Strategic location selection in competitive environments

References

The paper cites 63 relevant references spanning counterfactual explanations, optimization theory, facility location problems, and other important works, providing a solid theoretical foundation for the research.

Overall Assessment: This is a high-quality academic paper achieving good balance between theoretical innovation and practical application. The introduction of Wasserstein regularization is a highlight, offering both theoretical justification and practical computational advantages. Despite certain limitations, it makes important contributions to explainability research in contextual optimization problems.