Spiegazioni Relative per Problemi Contestuali con Incertezza Endogena: Un'Applicazione alla Localizzazione di Strutture Competitive

Informazioni Fondamentali

• ID Articolo: 2506.19155
• Titolo: Relative Explanations for Contextual Problems with Endogenous Uncertainty: An Application to Competitive Facility Location
• Autori: Jasone Ramírez-Ayerbe, Emma Frejinger (CIRRELT e Dipartimento di Informatica e Ricerca Operativa, Université de Montréal)
• Classificazione: math.OC (Ottimizzazione e Controllo Matematico)
• Data di Pubblicazione: 14 ottobre 2025 (versione 3 del preprint arXiv)
• Collegamento Articolo: https://arxiv.org/abs/2506.19155v3

Riassunto

Questo articolo affronta problemi di ottimizzazione stocastica contestuale con incertezza endogena, dove le decisioni influenzano la distribuzione sottostante. Per implementare tali decisioni nella pratica, è essenziale garantire che i risultati siano interpretabili e affidabili. A tal fine, gli autori calcolano spiegazioni controffattuali relative, fornendo ai professionisti cambiamenti concreti nelle covariate contestuali necessari per soddisfare vincoli specifici. Sebbene le spiegazioni relative siano state introdotte nella letteratura precedente, questo è, a conoscenza degli autori, il primo lavoro che si concentra su variabili decisionali binarie e problemi con incertezza endogena. Gli autori propongono un metodo che utilizza la distanza di Wasserstein come termine di regolarizzazione, il quale riduce il tempo di calcolo rispetto all'approccio non regolarizzato corrispondente.

Contesto di Ricerca e Motivazione

Contesto del Problema

Con l'aumento dell'applicazione dell'apprendimento automatico e dell'ottimizzazione nei problemi decisionali, in particolare in ambienti ad alto rischio come l'assistenza sanitaria, l'allocazione abitativa e i servizi sociali, garantire l'interpretabilità e l'affidabilità delle soluzioni è diventato cruciale. Istituzioni come l'Unione Europea, l'Ufficio della Politica Scientifica e Tecnologica della Casa Bianca e il governo canadese hanno riconosciuto la crescente necessità di interpretabilità.

Problemi Fondamentali

1. Incertezza Endogena: La variabile decisionale z influenza la distribuzione di probabilità condizionata P(y|z,x) della variabile casuale y
2. Esigenza di Interpretabilità: Comprendere come i cambiamenti contestuali portano a cambiamenti decisionali e quali modifiche sono necessarie affinché la soluzione soddisfi vincoli specifici
3. Scenari di Applicazione Pratica: Ad esempio, nella pianificazione dell'infrastruttura medica, i governi locali potrebbero chiedere quale sia il cambiamento minimo nei dati che porterebbe all'apertura di un centro nella loro regione

Limitazioni dei Metodi Esistenti

• Le spiegazioni controffattuali esistenti si concentrano principalmente su problemi di classificazione supervisionata
• Mancanza di ricerca su problemi di ottimizzazione con variabili decisionali binarie e incertezza endogena
• I metodi tradizionali hanno elevata complessità computazionale e mancano di meccanismi di regolarizzazione efficaci

Contributi Fondamentali

1. Estensione dell'Ambito di Ricerca: Prima applicazione di spiegazioni controffattuali relative a problemi di ottimizzazione stocastica contestuale con incertezza endogena
2. Generalizzazione dei Metodi Esistenti: Consente un insieme di soluzioni desiderate D piuttosto che una singola soluzione target, generalizzando i metodi esistenti basati su soluzioni fornite da esperti
3. Gestione di Variabili Binarie: Affronta il problema delle spiegazioni relative nel contesto di variabili decisionali binarie
4. Regolarizzazione di Wasserstein: Utilizza un termine di regolarizzazione che minimizza la distanza tra le distribuzioni indotte dalle soluzioni controffattuali e fattuali
5. Miglioramento dell'Efficienza Computazionale: Il metodo di regolarizzazione proposto riduce significativamente il tempo di calcolo

Dettagli Metodologici

Definizione del Compito

Dato un problema di ottimizzazione stocastica contestuale:

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

dove:

• z ∈ Z: vettore di variabili decisionali
• x⁰ ∈ X ⊆ ℝ^{dx}: covariate contestuali continue (caratteristiche)
• y: vettore di variabili casuali che catturano l'incertezza endogena
• P(y|z,x⁰): distribuzione di probabilità condizionata

Definizione di Spiegazione Controffattuale Relativa

Definizione 1.1: Per un dato fattore α ∈ (0,∞] e uno spazio desiderato D, una spiegazione relativa del problema (1) è un nuovo contesto x tale che esiste una soluzione ammissibile in D il cui cambio nella ricompensa attesa è al massimo α volte.

Problema di Ottimizzazione Centrale

Il calcolo della spiegazione relativa può essere formulato come il seguente problema di ottimizzazione non convessa:

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

Funzione di Costo e Regolarizzazione di Wasserstein

La funzione di costo assume la seguente forma:

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

dove:

• J(x⁰,x): componente di dissimilarità
• Ω(x⁰,x): termine di regolarizzazione, utilizzando la distanza 2-Wasserstein

Definizione della Distanza di Wasserstein: Per due distribuzioni di probabilità discrete P⁰ e P, il quadrato della distanza 2-Wasserstein è definito come:

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

soggetto ai vincoli:

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

Punti di Innovazione Tecnica

1. Regolarizzazione della Distanza Distributiva: Utilizzo della distanza di Wasserstein per garantire che la distribuzione controffattuale rimanga vicina a quella fattuale
2. Limite Inferiore Indipendente dal Modello: Metodo indipendente dal modello per fornire limiti inferiori computazionali
3. Induzione della Sparsità: Realizzazione congiunta della sparsità attraverso la norma ℓ₁ e la regolarizzazione di Wasserstein

Configurazione Sperimentale

Scenario di Applicazione: Problema di Localizzazione di Strutture Competitive Basato sulla Scelta (CFLP)

• Modello: Modello Logit Multinomiale (MNL)
• Decisione: Selezione di un sottoinsieme di siti candidati sotto vincoli di budget per massimizzare la cattura della domanda attesa
• Funzione di Utilità: v_ = -0.1θ_ + x_d, dove θ_ è la distanza e x_d è il punteggio di attrattività

Configurazione dei Dataset

• Esempio Piccolo: |N|=4 utenti, |D|=3 strutture candidate, |E|=2 strutture competitive, r=2 strutture aperte
• Istanze su Larga Scala:
  • Numero di utenti: 100, 200
  • Numero di strutture candidate: 10, 20, 40
  • Budget: 4, 8
  • Strutture competitive fisse: 5

Metriche di Valutazione

• Tempo di Calcolo: Tempo medio e mediano di risoluzione
• Distanza di Wasserstein: W²₂
• Sparsità: Percentuale di caratteristiche contestuali modificate
• Cattura della Domanda: Quantità di domanda fattuale e controffattuale
• Norma ℓ₁: Distanza L1 del cambiamento contestuale

Dettagli di Implementazione

• Risolutore: Gurobi 11.0.1
• Ambiente di Programmazione: Python 3.11.7
• Piattaforma di Calcolo: Processore Intel Core i9-10980XE
• Limite di Tempo: 1 ora
• Parametri di Regolarizzazione: λ ∈ {0, 0.1, 1}

Risultati Sperimentali

Risultati Principali

1. Miglioramento Significativo dell'Efficienza Computazionale:
   • Riduzione sostanziale del tempo medio di risoluzione con λ=0.1 rispetto a λ=0
   • Esempio: N=100, D=10, r=4, tempo medio con λ=0.1 di 137.92s vs 266.49s con λ=0
2. Miglioramento della Sparsità:
   • La regolarizzazione di Wasserstein migliora la sparsità della soluzione
   • Con λ=0.1 la sparsità è generalmente superiore al caso λ=0
3. Gap di Ottimalità:
   • Nelle istanze che raggiungono il limite di tempo, il gap di ottimalità nel caso non regolarizzato è notevolmente maggiore

Analisi di Caso

Risultati dell'Esempio Piccolo:

• Senza Regolarizzazione (λ=0): x_=0.350, W²₂=164.917
• Con Regolarizzazione (λ=0.25): x_=0.479, W²₂=90.849
• La versione regolarizzata, sebbene presenti un cambiamento contestuale maggiore, mostra una distanza distributiva inferiore e la stessa sparsità

Scoperte Sperimentali

1. Effetto della Regolarizzazione: Una regolarizzazione di Wasserstein moderata non solo migliora il tempo di esecuzione e la sparsità, ma porta anche a una transizione più fluida della distribuzione della domanda
2. Complessità Computazionale: Il problema controffattuale eredita la complessità del problema fattuale sottostante; le istanze con budget r maggiore spesso raggiungono il limite di tempo
3. Meccanismo di Sparsità: La sparsità dei cambiamenti non è realizzata solo minimizzando la norma ℓ₁; la regolarizzazione incoraggia inoltre il modello a concentrare i cambiamenti in poche strutture piuttosto che distribuire piccole modifiche

Lavori Correlati

Spiegazioni Controffattuali per Problemi di Ottimizzazione

• Bogetoft et al. (2024): Applicazione del concetto all'Analisi Envolvente dei Dati (DEA)
• Kurtz et al. (2025): Spiegazioni controffattuali per la programmazione lineare, formalizzando tre tipi: deboli, forti e relativi
• Serie di Lavori di Korikov: Calcolo di spiegazioni controffattuali deboli per la programmazione lineare intera attraverso l'ottimizzazione inversa

Problemi di Ottimizzazione Contestuale

• Forel et al. (2023): Presuppone che i parametri siano stimati dalle covariate contestuali, utilizzando foreste casuali o k-NN come predittori
• Vivier-Ardisson et al. (2024): Estensione a classificatori differenziabili, incluse reti neurali

Distinzioni di questo Articolo dai Lavori Correlati

1. Impostazione dell'Obiettivo: Consente un insieme desiderato di soluzioni D piuttosto che un singolo target fornito da esperti
2. Tipo di Incertezza: Concentrazione sull'incertezza endogena
3. Tipo di Variabili: Gestione di variabili decisionali binarie
4. Innovazione nella Regolarizzazione: Introduzione della regolarizzazione con distanza di Wasserstein

Conclusioni e Discussione

Conclusioni Principali

1. Efficacia del Metodo: Estensione riuscita delle spiegazioni controffattuali a problemi stocastici contestuali con incertezza endogena
2. Vantaggi Computazionali: La regolarizzazione di Wasserstein migliora significativamente l'efficienza computazionale
3. Qualità della Soluzione: Ottenimento di spiegazioni più sparse e interpretabili, con transizioni di probabilità di scelta più fluide

Limitazioni

1. Restrizione alle Variabili Continue: La formulazione attuale richiede che le covariate contestuali siano di tipo continuo; l'estensione a covariate categoriche rimane una sfida
2. Non Unicità della Soluzione: Le soluzioni tipicamente non sono uniche, il che potrebbe portare a disaccordi tra gli stakeholder e alla possibilità di manipolare le spiegazioni
3. Considerazioni Etiche: Molteplici spiegazioni controffattuali valide potrebbero sollevare questioni etiche, come il mascheramento di caratteristiche contestuali sensibili

Direzioni Future

1. Controffattuali Deboli: Calcolo di controffattuali deboli che forzano l'ottimalità della nuova soluzione piuttosto che spiegazioni relative
2. Estensione Distributiva: Estensione ad altre distribuzioni di probabilità
3. Domini di Applicazione: Applicazione in problemi di ottimizzazione classificatoria e determinazione dei prezzi
4. Garanzie di Unicità: Incorporamento di termini obiettivo che garantiscono l'unicità della soluzione

Valutazione Approfondita

Punti di Forza

1. Contributo Teorico: Prima applicazione sistematica di spiegazioni controffattuali a problemi con incertezza endogena, con un quadro teorico completo
2. Innovazione Metodologica: L'introduzione della regolarizzazione di Wasserstein è ben motivata teoricamente e produce effetti pratici significativi, migliorando notevolmente le prestazioni computazionali
3. Sperimentazione Completa: Esperimenti comprensivi da esempi su piccola scala a istanze su larga scala, con metriche di valutazione multidimensionali
4. Valore Pratico: L'applicazione CFLP scelta ha significato pratico importante e i risultati sono operativi

Insufficienze

1. Ambito di Applicabilità Limitato: Applicabilità solo a variabili contestuali continue, limitando l'universalità del metodo
2. Analisi di Complessità Insufficiente: Mancanza di analisi teorica della complessità dell'algoritmo
3. Selezione dei Parametri: Mancanza di guida sistematica per la scelta del parametro di regolarizzazione λ di Wasserstein
4. Esperimenti Comparativi: Confronti insufficienti con altri metodi di spiegazione controffattuale

Impatto

1. Contributo Accademico: Apertura di una nuova direzione di ricerca per l'interpretabilità dell'ottimizzazione contestuale
2. Valore Pratico: Fornitura di supporto decisionale interpretabile per problemi reali come la localizzazione di strutture e l'allocazione di risorse
3. Riproducibilità: Fornitura di codice completo e istanze, facilitando la riproduzione e l'estensione

Scenari di Applicabilità

1. Pianificazione di Strutture: Decisioni di localizzazione per strutture mediche, scuole e punti commerciali
2. Allocazione di Risorse: Problemi di allocazione di risorse pubbliche che richiedono trasparenza e interpretabilità
3. Formulazione di Politiche: Processi decisionali governativi che necessitano di trasparenza e interpretabilità
4. Decisioni Commerciali: Selezione strategica della localizzazione in ambienti competitivi

Bibliografia

L'articolo cita 63 riferimenti correlati, coprendo molteplici campi incluse spiegazioni controffattuali, teoria dell'ottimizzazione e problemi di localizzazione di strutture, fornendo una base teorica solida per la ricerca.

Valutazione Complessiva: Questo è un articolo accademico di alta qualità che raggiunge un buon equilibrio tra innovazione teorica e applicazione pratica. L'introduzione della regolarizzazione di Wasserstein è un punto saliente, ben motivato teoricamente e con vantaggi computazionali pratici. Nonostante alcune limitazioni, l'articolo fornisce contributi importanti alla ricerca sull'interpretabilità dei problemi di ottimizzazione contestuale.