Competitive Multi-Operator Reinforcement Learning for Joint Pricing and Fleet Rebalancing in AMoD Systems

Diese Arbeit stellt ein Multi-Operator-Reinforcement-Learning-Framework vor, das strategische Preisgestaltung und Flottenumschichtung in wettbewerbsorientierten autonomen Mobilitätsdiensten modelliert und zeigt, wie Wettbewerb durch endogene Nachfragesimulation zu niedrigeren Preisen und anderen Flottenstrategien führt als in Monopolszenarien.

Das Wesentliche

Stellen Sie sich eine große, geschäftige Stadt vor, in der Menschen ständig von A nach B müssen. Früher gab es nur das eigene Auto oder den öffentlichen Bus. Heute gibt es AMoD-Systeme (Autonomous Mobility-on-Demand). Das sind wie ein riesiges Schwarm von selbstfahrenden Taxis, die per App bestellt werden können.

Bisher haben Forscher meist nur über einen einzigen Anbieter nachgedacht, der das ganze System kontrolliert – wie ein Monopolist, der die einzige Tankstelle in der Stadt besitzt. Aber in der Realität wird es viele Anbieter geben, die gegeneinander kämpfen, genau wie Uber, Lyft oder lokale Taxiunternehmen heute.

Diese Studie fragt sich: Was passiert, wenn zwei dieser selbstfahrenden Taxi-Unternehmen in derselben Stadt gegeneinander antreten?

Hier ist die Erklärung der Forschung, übersetzt in eine einfache Geschichte mit Analogien:

1. Das Spiel: Zwei Köche in einer Küche

Stellen Sie sich vor, zwei Köche (die Anbieter) arbeiten in derselben Küche (der Stadt). Beide wollen so viele Gäste (Passagiere) wie möglich bedienen und dabei so viel Geld verdienen wie möglich.

• Die Herausforderung: Jeder Koch muss zwei Dinge entscheiden:
  1. Der Preis: Wie teuer ist das Essen (die Fahrt)?
  2. Die Positionierung: Wo stehen die Kellner (die Autos)? Stehen sie vor dem Restaurant oder weit weg in der Nachbarschaft?

Früher haben Computer-Algorithmen (KIs) gelernt, wie ein einzelner Koch am besten arbeitet. Aber in dieser Studie lassen die Forscher zwei KIs gleichzeitig lernen, während sie sich gegenseitig beobachten.

2. Der Mechanismus: Ein unsichtbarer Tauschmarkt

Wie entscheiden die Kunden, zu welchem Koch sie gehen?
Die Forscher haben eine intelligente Waage eingebaut. Ein Kunde schaut auf:

• Den Preis.
• Wie lange er warten muss.
• Wie viel Geld er selbst verdient (denn wer viel verdient, ist oft bereit, mehr für Zeit zu zahlen).

Wenn Koch A den Preis senkt, laufen die Kunden zu ihm. Aber wenn Koch A alle Kellner in die falsche Gegend schickt, müssen die Kunden trotzdem lange warten, und sie gehen vielleicht zum Konkurrenten oder nehmen das eigene Auto.

3. Die überraschenden Ergebnisse

Die Forscher haben das in echten Städten (San Francisco, Washington D.C., New York) simuliert. Hier sind die wichtigsten Erkenntnisse, einfach erklärt:

A. Der Preis-Krieg senkt die Preise

Wenn nur ein Anbieter da ist (Monopol), kann er die Preise hochhalten. Wenn aber zwei Anbieter kämpfen, senken sie die Preise, um Kunden zu gewinnen.

• Analogie: Es ist wie auf einem Flohmarkt. Wenn nur einer Stände hat, kann er alles teuer verkaufen. Wenn zwei nebeneinander stehen, muss der eine günstiger sein, um Kunden zu locken. Das ist gut für die Kunden, aber härter für die Anbieter.

B. Das "Positionierungs-Dilemma"

In einer monopolistischen Welt (ein Anbieter) wissen die KIs genau, wo die Autos hinmüssen. In der Konkurrenz-Welt ist das schwieriger.

• Das Problem: Wenn Anbieter A denkt, "Ich stelle Autos in den Norden", und Anbieter B macht das Gleiche, stehen plötzlich zu viele Autos im Norden und im Süden ist niemand.
• Die Lösung: Die KIs lernen, sich gegenseitig auszuweichen. Sie entwickeln eine Art "Tanz", bei dem sie ihre Autos strategisch platzieren, ohne sich direkt zu blockieren.

C. Weniger Effizienz, mehr Wartezeit

Leider führt der Wettbewerb nicht immer zu perfekten Ergebnissen. Weil die zwei Anbieter ihre Flotten nicht gemeinsam koordinieren können, entstehen Lücken.

• Analogie: Stellen Sie sich zwei Rettungswagen-Teams vor, die nicht miteinander sprechen. Team A fährt zur falschen Adresse, weil Team B dort schon war, aber Team B wusste nicht, dass Team A kommt. Das Ergebnis: Die Kunden müssen länger warten, obwohl es mehr Autos gibt.

D. Die KIs sind robust

Das Wichtigste: Die Computer-KIs haben es geschafft, trotz des Chaos und der Unsicherheit (man weiß nie genau, was der andere gerade plant) stabile Strategien zu entwickeln. Sie haben gelernt, dass man nicht alles perfekt planen kann, sondern sich an die Bewegungen des Gegners anpassen muss.

4. Was bedeutet das für uns?

• Für die Kunden: Wir werden wahrscheinlich günstigere Fahrten haben, aber vielleicht etwas länger warten müssen, weil die Systeme nicht perfekt aufeinander abgestimmt sind.
• Für die Anbieter: Sie müssen sehr schlau sein. Sie können nicht einfach nur die Preise drücken; sie müssen auch wissen, wo ihre Autos stehen, und dabei den "Tanz" des Konkurrenten mitspielen.
• Für die Städte: Es zeigt, dass wir in Zukunft nicht nur über Technik, sondern über Wettbewerb nachdenken müssen. Ein System, das von einem einzigen Unternehmen kontrolliert wird, ist vielleicht effizienter, aber ein wettbewerbsfähiges System ist fairer und günstiger für uns alle.

Zusammenfassend: Die Studie zeigt, dass selbstfahrende Taxis in einer wettbewerbsorientierten Welt funktionieren werden. Die KIs lernen, wie man in einem chaotischen, wettbewerbsintensiven Markt überlebt, indem sie Preise anpassen und ihre Autos klug verteilen – auch wenn der Konkurrent genau das Gleiche tut. Es ist ein komplexer Tanz, bei dem beide Partner lernen müssen, nicht auf die Füße zu treten, um nicht den Takt zu verlieren.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Competitive Multi-Operator Reinforcement Learning for Joint Pricing and Fleet Rebalancing in AMoD Systems" auf Deutsch:

1. Problemstellung

Autonome Mobility-on-Demand (AMoD)-Systeme versprechen, den urbanen Verkehr durch bedarfsgerechte, erschwingliche Dienste zu revolutionieren. Bisherige Forschungsarbeiten konzentrierten sich jedoch überwiegend auf monopolistische Szenarien (ein einzelner Betreiber), in denen Reinforcement Learning (RL) zur Optimierung von Flotten-Umschichtung (Rebalancing) und Preisen eingesetzt wurde.

In der Realität werden AMoD-Märkte jedoch wettbewerblich sein, mit mehreren Betreibern, die um Passagiere konkurrieren. Diese Konkurrenz führt zu komplexen dynamischen Wechselwirkungen:

• Strategische Preisgestaltung eines Betreibers beeinflusst die Nachfrage des anderen.
• Die Flottenpositionierung muss nicht nur auf die Nachfrage, sondern auch auf die Aktionen des Konkurrenten reagieren.
• Bestehende RL-Ansätze erfassen diese wettbewerblichen Marktmechanismen und die daraus resultierende endogene Nachfrageallokation nicht ausreichend.

Das Ziel der Arbeit ist es, den Einfluss von Wettbewerb auf das Erlernen von Politiken (Policy Learning) zu untersuchen und einen Rahmen für jointes Pricing und Flotten-Umschichtung in einem wettbewerblichen Multi-Operator-Setting zu entwickeln.

2. Methodik

A. Umgebungsmodellierung und Markov-Entscheidungsprozess (MDP)

Die Autoren modellieren das AMoD-System als gerichteten Graphen $G=(V, E)$ mit $N_v$ Regionen. Zwei unabhängige Betreiber ($o \in \{0, 1\}$) steuern jeweils eine Flotte autonomer Fahrzeuge.

• Zustandsraum ($S$): Umfasst die Netzwerktopologie, die Anzahl leerer Fahrzeuge pro Region, Fahrzeuge auf dem Weg, historische Preise (eigene und des Konkurrenten), Warteschlangenlängen und vergangene Nachfrage. Betreiber teilen keine Fahrzeugdaten, können aber die Preise des Konkurrenten beobachten.
• Aktionsraum ($A$): Jeder Betreiber gibt pro Region zwei Aktionen aus:
  1. Preisskalare ($\rho$): Multiplikatoren für historische Basispreise, um dynamische Tarife zu setzen.
  2. Gewünschte Verteilung leerer Fahrzeuge ($w$): Ein Vektor, der die Zielverteilung der Flotte angibt.
• Belohnung ($R$): Der Gewinn pro Betreiber, definiert als Einnahmen aus Fahrten minus Betriebskosten (Fahrtkosten für Passagiere und Kosten für leere Umschichtungsfahrten).

B. Nachfrageallokation und Discrete Choice

Ein zentrales Element ist die Integration eines Discrete Choice Models (Multinomiales Logit-Modell), das die Passagierentscheidung endogen steuert. Passagiere wählen zwischen Operator 0, Operator 1 oder einer Alternative (z. B. öffentliches Nahverkehr/kein Dienst) basierend auf einer Nutzenfunktion $U$:
$$U = \beta_0 - \beta_t \cdot \text{Fahrzeit} - \frac{\bar{v}}{v_k} \cdot \text{Preis}$$
Dabei fließen der Preis, die Fahrzeit und das Einkommen des Passagiers ($v_k$) ein. Dies ermöglicht es, dass die Nachfrageverteilung zwischen den Betreibern dynamisch aus ihren Preis- und Serviceentscheidungen resultiert.

C. Architektur des Reinforcement Learning

• Algorithmus: Es wird ein Multi-Agenten RL-Ansatz (basierend auf A2C - Advantage Actor-Critic) verwendet.
• Netzwerkarchitektur: Jeder Betreiber verfügt über ein eigenes, unabhängiges Actor-Critic-Netzwerk ohne Parameter-Sharing.
  • Encoder: Graph Convolutional Networks (GCN) erfassen die räumlichen Abhängigkeiten im Verkehrsnetz.
  • Actor: Gibt Parameter für Wahrscheinlichkeitsverteilungen aus:
    • Beta-Verteilung für Preisskalare.
    • Dirichlet-Verteilung für die Anteile der Flottenumschichtung.
• Trainingsprozess: Die Agenten lernen simultan in einer simulierten Umgebung mit Echtzeitdaten (Taxis aus SF, DC, NYC).

3. Hauptbeiträge

1. Formulierung eines kompetitiven Dual-Operator-Problems: Erweiterung von RL-Ansätzen für AMoD von monopolistischen auf wettbewerbliche Märkte, bei denen zwei Agenten gleichzeitig Pricing und Rebalancing lernen.
2. Endogene Nachfrageallokation: Integration eines lohnabhängigen Discrete Choice Models in den Lernloop, sodass die Nachfrageverteilung nicht extern vorgegeben, sondern als Ergebnis der strategischen Interaktion entsteht.
3. Empirische Analyse des Wettbewerbs: Nutzung realer Daten aus drei Städten, um zu zeigen, wie Wettbewerb das Verhalten, die Servicequalität und die Markteffizienz im Vergleich zu Monopolen verändert.

4. Ergebnisse und Experimente

Die Experimente wurden in San Francisco, Washington DC und New York City (Manhattan South) durchgeführt und verglichen Monopole (ein Operator) mit wettbewerblichen Szenarien (zwei Operator) unter verschiedenen Kontrollmodi (nur Umschichtung, nur Preis, joint).

• Wettbewerb verändert dominante Strategien:
  • Im Monopol ist die jointe Kontrolle (Preis + Umschichtung) immer überlegen.
  • Im Wettbewerb hängt die beste Strategie von der Nachfragevariabilität ab:
    • In hochvariablen Umgebungen (San Francisco) ist die Flottenumschichtung der entscheidende Wettbewerbsfaktor.
    • In stabilen, dichten Umgebungen (NYC) kann dynamische Preisgestaltung als Mechanismus für implizite Umschichtung fungieren und führt zu den höchsten Gewinnen.
• Auswirkungen auf Preise und Service:
  • Preise: Wettbewerb treibt die Preise signifikant nach unten (bis zu 27 % niedriger als im Monopol), was den Passagieren zugutekommt.
  • Wartezeiten: Durch die fragmentierte Flottenverwaltung steigen die Wartezeiten im Wettbewerb im Vergleich zum Monopol an (Ineffizienz der Aufteilung).
  • Gewinne: Der Gesamtgewinn im Wettbewerb ist meist niedriger als im Monopol (z. B. -15,2 % in SF), da die Fragmentierung die Effizienz der Angebot-Nachfrage-Matching verschlechtert.
• Robustheit des RL: Die Lernbasierten Ansätze sind robust gegenüber der zusätzlichen Stochastik durch den Wettbewerb. Die Agenten konvergieren zu stabilen Politiken, auch wenn sie die Strategien des Konkurrenten nur teilweise beobachten können.
• Sensitivitätsanalysen:
  • Flottengröße: Größere Flotten führen zu niedrigeren Preisen, aber ab einer bestimmten Größe sinken die marginalen Gewinne aufgrund steigender Umschichtungskosten.
  • Asymmetrie: Bei ungleicher Flottengröße (z. B. 1:9) reduziert sich der direkte Preiswettbewerb; der kleinere Betreiber erhöht die Preise, der größere unterbietet.
  • Einkommensheterogenität: Betreiber verlagern ihre Flotten strategisch in Gebiete mit höherem Einkommen und passen die Preise entsprechend an (höhere Zahlungsbereitschaft).

5. Bedeutung und Fazit

Diese Arbeit zeigt, dass die Annahme eines monopolistischen Marktes in der AMoD-Forschung irreführend sein kann. Wettbewerb verändert die optimalen Lernstrategien fundamental:

• Für Betreiber: Es ist entscheidend, nicht nur die eigene Nachfrage, sondern auch die Reaktionen des Konkurrenten zu antizipieren. Eine reine Optimierung der Flottenverteilung reicht im Wettbewerb oft nicht aus; Preisstrategien gewinnen an Bedeutung.
• Für die Gesellschaft: Wettbewerb führt zu niedrigeren Preisen für Verbraucher, kann aber aufgrund der ineffizienteren Ressourcenallokation (fragmentierte Flotten) zu längeren Wartezeiten führen.
• Für die Forschung: Die Studie belegt, dass Multi-Agenten-RL effektiv eingesetzt werden kann, um komplexe, wettbewerbliche Märkte zu modellieren, und liefert einen Rahmen für zukünftige Untersuchungen zu kollusivem Verhalten oder asymmetrischen Lernarchitekturen.

Zusammenfassend liefert das Paper einen robusten, datengestützten Rahmen, um die Dynamik zukünftiger autonomer Mobilitätsmärkte zu verstehen und zu optimieren.