Relative Erklärungen für kontextuelle Probleme mit endogener Unsicherheit: Eine Anwendung auf konkurrierende Standortplanung

Grundinformationen

• Paper-ID: 2506.19155
• Titel: Relative Explanations for Contextual Problems with Endogenous Uncertainty: An Application to Competitive Facility Location
• Autoren: Jasone Ramírez-Ayerbe, Emma Frejinger (CIRRELT und Department of Computer Science and Operations Research, Université de Montréal)
• Klassifizierung: math.OC (Mathematische Optimierung und Kontrolle)
• Veröffentlichungsdatum: 14. Oktober 2025 (arXiv-Preprint Version 3)
• Paper-Link: https://arxiv.org/abs/2506.19155v3

Zusammenfassung

Dieses Paper untersucht kontextuelle stochastische Optimierungsprobleme unter endogener Unsicherheit, bei denen Entscheidungen die zugrunde liegende Verteilung beeinflussen. Um solche Entscheidungen in der Praxis umzusetzen, ist es entscheidend, dass die Ergebnisse interpretierbar und vertrauenswürdig sind. Zu diesem Zweck berechnen die Autoren relative kontrafaktische Erklärungen, die Praktikern konkrete Änderungen der kontextuellen Kovariaten liefern, die erforderlich sind, um Lösungen bestimmten Nebenbedingungen zu genügen. Während relative Erklärungen in der bisherigen Literatur eingeführt wurden, ist dies nach Kenntnis der Autoren die erste Arbeit, die sich auf binäre Entscheidungsvariablen und Probleme mit endogener Unsicherheit konzentriert. Die Autoren schlagen eine Methode vor, die die Wasserstein-Distanz als Regularisierungsterm verwendet und die Rechenzeit im Vergleich zu nicht regularisierten Entsprechungen reduziert.

Forschungshintergrund und Motivation

Problemhintergrund

Mit der zunehmenden Anwendung von maschinellem Lernen und Optimierung bei Entscheidungsproblemen, insbesondere in risikoreichen Entscheidungsumgebungen wie Gesundheitswesen, Wohnungsverteilung und Sozialdienstleistungen, wird die Gewährleistung der Interpretierbarkeit und Vertrauenswürdigkeit von Lösungen zunehmend kritisch. Institutionen wie die Europäische Union, das Office of Science and Technology Policy des Weißen Hauses und die kanadische Regierung erkennen den wachsenden Bedarf an Interpretierbarkeit an.

Kernprobleme

1. Endogene Unsicherheit: Entscheidungsvariablen z beeinflussen die bedingte Wahrscheinlichkeitsverteilung P(y|z,x) der Zufallsvariablen y
2. Anforderungen an Interpretierbarkeit: Verständnis dafür, wie kontextuelle Änderungen zu Entscheidungsänderungen führen und welche Änderungen erforderlich sind, damit Lösungen bestimmte Nebenbedingungen erfüllen
3. Praktische Anwendungsszenarien: Beispielsweise können Kommunalverwaltungen bei der medizinischen Infrastrukturplanung fragen, welche minimalen Datenänderungen dazu führen würden, dass ein Zentrum in ihrer Region eröffnet wird

Einschränkungen bestehender Methoden

• Bestehende kontrafaktische Erklärungen konzentrieren sich hauptsächlich auf überwachte Klassifizierungsprobleme
• Mangel an Forschung zu Optimierungsproblemen mit binären Entscheidungsvariablen und endogener Unsicherheit
• Traditionelle Methoden haben hohe Rechenkomplexität und mangelnde effektive Regularisierungsmechanismen

Kernbeiträge

1. Erweiterung des Forschungsumfangs: Erste Anwendung relativer kontrafaktischer Erklärungen auf kontextuelle stochastische Optimierungsprobleme unter endogener Unsicherheit
2. Verallgemeinerung bestehender Methoden: Ermöglicht erwartete machbare Mengen D statt einzelner Zielösungen und verallgemeinert bestehende Methoden basierend auf von Experten bereitgestellten Lösungen
3. Behandlung binärer Variablen: Löst relative Erklärungsprobleme im Kontext binärer Entscheidungsvariablen
4. Wasserstein-Regularisierung: Verwendet Regularisierungsterme, die die Distanz zwischen kontrafaktischen und faktischen Verteilungen minimieren
5. Verbesserung der Recheneffizienz: Die vorgeschlagene Regularisierungsmethode reduziert die Rechenzeit erheblich

Methodische Details

Aufgabendefinition

Gegeben ein kontextuelles stochastisches Optimierungsproblem:

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

wobei:

• z ∈ Z: Vektor der Entscheidungsvariablen
• x⁰ ∈ X ⊆ ℝ^{dx}: Kontinuierliche kontextuelle Kovariaten (Merkmale)
• y: Vektor der Zufallsvariablen, der endogene Unsicherheit erfasst
• P(y|z,x⁰): Bedingte Wahrscheinlichkeitsverteilung

Definition relativer kontrafaktischer Erklärungen

Definition 1.1: Für einen gegebenen Faktor α ∈ (0,∞] und erwartete Menge D ist eine relative Erklärung des Problems (1) ein neuer Kontext x, so dass eine machbare Lösung in D existiert, deren erwartete Belohnung sich um höchstens das α-fache ändert.

Kernoptimierungsproblem

Die Berechnung relativer Erklärungen kann als folgendes nicht-konvexes Optimierungsproblem formuliert werden:

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

Kostenfunktion und Wasserstein-Regularisierung

Die Kostenfunktion hat folgende Form:

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

wobei:

• J(x⁰,x): Unähnlichkeitskomponente
• Ω(x⁰,x): Regularisierungsterm unter Verwendung der 2-Wasserstein-Distanz

Wasserstein-Distanz-Definition: Für zwei diskrete Wahrscheinlichkeitsverteilungen P⁰ und P ist das Quadrat der 2-Wasserstein-Distanz definiert als:

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

unter den Nebenbedingungen:

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

Technische Innovationen

1. Verteilungsdistanz-Regularisierung: Verwendung der Wasserstein-Distanz zur Gewährleistung der Nähe zwischen kontrafaktischer und faktischer Verteilung
2. Modellunabhängige Untergrenzen: Modellunabhängige Methode zur Berechnung von Untergrenzen
3. Sparsität-Induktion: Gemeinsame Realisierung von Sparsität durch ℓ₁-Norm und Wasserstein-Regularisierung

Experimentelle Einrichtung

Anwendungsszenario: Wahl-basiertes Konkurrenz-Standortplanungsproblem (CFLP)

• Modell: Multinomiales Logit-Modell (MNL)
• Entscheidung: Auswahl einer Teilmenge von Kandidatenstandorten unter Budgetbeschränkung zur Maximierung der erwarteten Nachfrageerreichung
• Nutzenfunktion: v_ = -0.1θ_ + x_d, wobei θ_ die Distanz und x_d die Attraktivitätsbewertung ist

Datensatz-Konfiguration

• Kleines Beispiel: |N|=4 Benutzer, |D|=3 Kandidateneinrichtungen, |E|=2 konkurrierende Einrichtungen, r=2 zu öffnende Einrichtungen
• Großskalige Instanzen:
  • Benutzeranzahl: 100, 200
  • Kandidateneinrichtungen: 10, 20, 40
  • Budget: 4, 8
  • Konkurrierende Einrichtungen: 5 (fest)

Bewertungsmetriken

• Rechenzeit: Durchschnittliche und mittlere Lösungszeit
• Wasserstein-Distanz: W²₂
• Sparsität: Prozentsatz der geänderten kontextuellen Merkmale
• Nachfrageerreichung: Faktische und kontrafaktische Nachfragemengen
• ℓ₁-Norm: L1-Distanz kontextueller Änderungen

Implementierungsdetails

• Solver: Gurobi 11.0.1
• Programmierumgebung: Python 3.11.7
• Rechnerplattform: Intel Core i9-10980XE Prozessor
• Zeitlimit: 1 Stunde
• Regularisierungsparameter: λ ∈ {0, 0.1, 1}

Experimentelle Ergebnisse

Hauptergebnisse

1. Signifikante Verbesserung der Recheneffizienz:
   • Durchschnittliche Lösungszeit bei λ=0.1 deutlich geringer als bei λ=0
   • Beispiel: N=100, D=10, r=4: durchschnittliche Zeit λ=0.1 ist 137.92s vs. λ=0 ist 266.49s
2. Verbesserung der Sparsität:
   • Wasserstein-Regularisierung verbessert die Sparsität der Lösungen
   • Sparsität bei λ=0.1 ist typischerweise besser als bei λ=0
3. Optimierungslücke:
   • Bei Instanzen, die das Zeitlimit erreichen, ist die Optimierungslücke ohne Regularisierung deutlich größer

Fallstudie

Ergebnisse des kleinen Beispiels:

• Ohne Regularisierung (λ=0): x_=0.350, W²₂=164.917
• Mit Regularisierung (λ=0.25): x_=0.479, W²₂=90.849
• Die regularisierte Version hat zwar größere kontextuelle Änderungen, aber kleinere Verteilungsdistanz und gleiche Sparsität

Experimentelle Erkenntnisse

1. Regularisierungseffekt: Moderate Wasserstein-Regularisierung verbessert nicht nur Laufzeit und Sparsität, sondern führt auch zu sanfteren Übergängen in der Nachfrageverteilung
2. Rechenkomplexität: Das kontrafaktische Problem erbt die Komplexität des zugrunde liegenden faktischen Problems; Instanzen mit größerem Budget r erreichen häufig das Zeitlimit
3. Sparsitätsmechanismus: Sparsität wird nicht nur durch Minimierung der ℓ₁-Norm erreicht; die Regularisierung ermutigt das Modell auch, Änderungen auf weniger Einrichtungen zu konzentrieren statt kleine Änderungen zu verteilen

Verwandte Arbeiten

Kontrafaktische Erklärungen für Optimierungsprobleme

• Bogetoft et al. (2024): Anwendung des Konzepts auf Data Envelopment Analysis (DEA)
• Kurtz et al. (2025): Kontrafaktische Erklärungen für lineare Programmierung mit Formalisierung schwacher, starker und relativer Typen
• Korikov-Serie: Berechnung schwacher kontrafaktischer Erklärungen für ganzzahlige lineare Programme durch inverse Optimierung

Kontextuelle Optimierungsprobleme

• Forel et al. (2023): Annahme, dass Parameter aus kontextuellen Kovariaten geschätzt werden, unter Verwendung von Random Forests oder k-NN als Prädiktoren
• Vivier-Ardisson et al. (2024): Erweiterung auf differenzierbare Klassifizierer, einschließlich neuronaler Netze

Unterschiede zu verwandten Arbeiten

1. Zielformulierung: Ermöglicht erwartete machbare Mengen D statt einzelner von Experten bereitgestellter Ziele
2. Unsicherheitstyp: Konzentration auf endogene Unsicherheit
3. Variablentyp: Behandlung binärer Entscheidungsvariablen
4. Regularisierungsinnovation: Einführung der Wasserstein-Distanz-Regularisierung

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

1. Methodische Effektivität: Erfolgreiche Erweiterung kontrafaktischer Erklärungen auf kontextuelle stochastische Probleme mit endogener Unsicherheit
2. Rechenvorteil: Wasserstein-Regularisierung verbessert die Recheneffizienz erheblich
3. Lösungsqualität: Erreichung sparserer und interpretierbarer Erklärungen mit sanfteren Wahrscheinlichkeitsänderungen

Einschränkungen

1. Beschränkung auf kontinuierliche Variablen: Die aktuelle Formulierung erfordert kontinuierliche kontextuelle Kovariaten; die Erweiterung auf kategorische Kovariaten bleibt eine Herausforderung
2. Nicht-Eindeutigkeit der Lösung: Lösungen sind typischerweise nicht eindeutig, was zu Meinungsverschiedenheiten zwischen Interessenträgern und Manipulationsmöglichkeiten führen kann
3. Ethische Überlegungen: Mehrere gültige kontrafaktische Erklärungen können ethische Probleme aufwerfen, wie das Verbergen sensibler kontextueller Merkmale

Zukünftige Richtungen

1. Schwache Kontrafaktische: Berechnung schwacher kontrafaktischer Erklärungen, die die Optimalität neuer Lösungen erzwingen, statt relativer Erklärungen
2. Verteilungserweiterungen: Erweiterung auf andere Wahrscheinlichkeitsverteilungen
3. Anwendungsfelder: Anwendung in kombinatorischen Optimierungs- und Preisgestaltungsproblemen
4. Eindeutigkeitsgarantien: Einbeziehung von Zielkomponenten zur Gewährleistung der Lösungseindeutigkeit

Tiefgreifende Bewertung

Stärken

1. Theoretischer Beitrag: Erste systematische Anwendung kontrafaktischer Erklärungen auf Probleme mit endogener Unsicherheit mit vollständigem theoretischem Rahmen
2. Methodische Innovation: Die Einführung der Wasserstein-Regularisierung hat sowohl theoretische Grundlagen als auch praktische Effekte und verbessert die Rechenleistung erheblich
3. Umfassende Experimente: Vollständige Experimente von kleinen Beispielen bis zu großskaligen Instanzen mit mehrdimensionalen Bewertungsmetriken
4. Praktischer Wert: Die gewählte CFLP-Anwendung hat wichtige praktische Bedeutung und die Ergebnisse sind handlungsorientiert

Schwächen

1. Begrenzte Anwendbarkeit: Nur für kontinuierliche kontextuelle Variablen geeignet, was die Universalität der Methode einschränkt
2. Unzureichende Komplexitätsanalyse: Mangel an theoretischer Analyse der Algorithmuskomplexität
3. Parameterauswahl: Mangel an systematischer Anleitung zur Auswahl des Wasserstein-Regularisierungsparameters λ
4. Unzureichende Vergleichsexperimente: Vergleich mit anderen kontrafaktischen Erklärungsmethoden könnte umfassender sein

Auswirkungen

1. Akademischer Beitrag: Eröffnet neue Forschungsrichtungen für die Interpretierbarkeit kontextueller Optimierung
2. Praktischer Wert: Bietet interpretierbare Entscheidungsunterstützung für praktische Probleme wie Standortplanung und Ressourcenverteilung
3. Reproduzierbarkeit: Bereitstellung vollständiger Code und Beispiele erleichtert Reproduktion und Erweiterung

Anwendungsszenarien

1. Standortplanung: Standortwahl für medizinische Einrichtungen, Schulen und Geschäftsnetzwerke
2. Ressourcenverteilung: Öffentliche Ressourcenverteilungsprobleme, die Transparenz und Interpretierbarkeit erfordern
3. Politische Entscheidungsfindung: Regierungsentscheidungsprozesse, die Transparenz erfordern
4. Geschäftsentscheidungen: Strategische Standortwahl in Wettbewerbsumgebungen

Literaturverzeichnis

Das Paper zitiert 63 relevante Arbeiten, die wichtige Werke in den Bereichen kontrafaktische Erklärungen, Optimierungstheorie und Standortplanungsprobleme abdecken und eine solide theoretische Grundlage für die Forschung bieten.

Gesamtbewertung: Dies ist ein hochqualitatives akademisches Paper, das ein gutes Gleichgewicht zwischen theoretischer Innovation und praktischer Anwendung erreicht. Die Einführung der Wasserstein-Regularisierung ist ein Highlight, das nicht nur theoretisch fundiert ist, sondern auch praktische Rechenvorteile bringt. Trotz einiger Einschränkungen leistet es wichtige Beiträge zur Forschung über die Interpretierbarkeit kontextueller Optimierungsprobleme.