A stochastic optimization algorithm for revenue maximization in a service system with balking customers

Diese Arbeit stellt einen stochastischen Optimierungsalgorithmus vor, der mithilfe einer neuartigen Infinitesimal-Perturbation-Analyse (IPA) den optimalen Preis in einem Einzelschranken-Warteschlangensystem mit balkierenden Kunden allein auf Basis beobachteter effektiver Ankunftsdaten bestimmt, um den erwarteten Umsatz pro Zeiteinheit zu maximieren.

Das Wesentliche

Das Problem: Der überfüllte Friseur und der schlaue Preissetzer

Stellen Sie sich einen sehr beliebten Friseur vor (oder eine beliebte App für Lieferdienste). Der Besitzer möchte so viel Geld wie möglich verdienen. Er hat zwei Hebel:

1. Der Preis: Wie viel kostet der Haarschnitt?
2. Die Wartezeit: Wie lange muss man warten?

Das Problem ist ein klassisches Dilemma:

• Wenn der Preis zu niedrig ist, kommen viele Kunden. Aber dann wird die Schlange so lang, dass die Wartezeit unangenehm wird. Viele Kunden sehen die lange Schlange und gehen wieder: Sie „balken" (sie entscheiden sich gegen den Service). Der Friseur verdient wenig, weil er viele Kunden verjagt hat.
• Wenn der Preis zu hoch ist, kommen nur wenige Kunden. Die Wartezeit ist kurz, aber der Friseur hat zu wenig Umsatz, weil die Stühle leer stehen.

Der Friseur muss also den perfekten Preis finden. Aber er weiß nicht genau, wie die Kunden reagieren. Wenn er den Preis ändert, ändert sich auch, wie viele Leute ankommen und wie lange sie warten. Das ist ein ständiges Hin und Her.

Die Herausforderung: Man sieht nur die „Glücklichen"

In der echten Welt kann der Friseur nicht sehen, wie viele Leute vor der Tür stehen und dann enttäuscht wieder gehen. Er sieht nur die Kunden, die tatsächlich den Laden betreten und sich setzen.

Das ist wie bei einem Restaurant, das nur die Gäste zählt, die reinkommen, aber nicht weiß, wie viele draußen vor der Tür stehen und weggeworfen haben, weil es zu voll war. Der Algorithmus in diesem Papier muss also den perfekten Preis finden, ohne zu wissen, wie viele Leute eigentlich weggegangen sind. Er muss nur aus den Daten derjenigen lernen, die geblieben sind.

Die Lösung: Ein intelligenter „Probier-Stein"

Die Autoren (Bodas, Honnappa, Mandjes und Ravner) haben einen cleveren Algorithmus entwickelt, der wie ein geschickter Tüftler arbeitet.

1. Der „Stochastische Gradientenabstieg" (Der schrittweise Versuch)
Stellen Sie sich vor, Sie sind in einem dunklen Raum und suchen den höchsten Punkt eines Hügels (das ist der maximale Gewinn). Sie können nicht sehen, wo der Gipfel ist.

• Der Algorithmus probiert einen Preis aus.
• Er schaut, wie viel Geld er damit verdient hat.
• Dann macht er eine kleine, vorsichtige Bewegung in eine Richtung (z. B. den Preis leicht erhöhen oder senken).
• Er wiederholt das immer wieder. Mit jedem Schritt wird er klüger und nähert sich dem perfekten Preis an.

2. Die Magie: „Infinitesimal Perturbation Analysis" (IPA)
Das ist der schwierigste Teil der Forschung, aber hier ist die einfache Erklärung:
Normalerweise ist es schwer zu berechnen, wie sich eine winzige Preisänderung auf die gesamte Schlange auswirkt, besonders wenn man nicht sieht, wer weggegangen ist.
Die Autoren haben eine neue Methode erfunden, die wie ein sehr genauer Mikroskop funktioniert. Sie schauen sich den Ablauf im System genau an (wer kommt, wann kommt er, wie lange wartet er) und berechnen aus diesen winzigen Details ab, wie sich der Preis auf den Gewinn auswirkt.

• Die Analogie: Stellen Sie sich vor, Sie steuern ein Schiff im Nebel. Sie sehen nicht den Hafen, aber Sie spüren jede kleine Welle und jeden Windstoß. Diese neue Methode erlaubt es dem Algorithmus, aus diesen kleinen „Wellen" (den Daten der ankommenden Kunden) zu berechnen, wo der Hafen (der optimale Preis) liegt, ohne ihn direkt zu sehen.

Warum ist das so wichtig?

Bisherige Methoden haben oft angenommen, dass man alles über das System weiß (wie viele Kunden warten, wie lange sie bleiben). In der Realität ist das aber selten der Fall.

• Der Vorteil dieses Papiers: Der Algorithmus funktioniert auch dann perfekt, wenn das System „undurchsichtig" ist. Er ignoriert die Leute, die weggehen, und lernt trotzdem aus den Daten derjenigen, die bleiben.
• Das Ergebnis: Der Algorithmus findet schnell den Preis, der das meiste Geld bringt, und passt sich automatisch an, wenn sich die Kundenmenge oder die Wartezeiten ändern.

Zusammenfassung in einem Satz

Die Autoren haben einen cleveren mathematischen „Navigator" entwickelt, der einem Dienstleister hilft, den perfekten Preis zu finden, indem er nur die Daten der Kunden nutzt, die tatsächlich bleiben, und dabei geschickt berechnet, wie sich kleine Preisänderungen auf die versteckte Menge der weggehenden Kunden auswirken.

Es ist wie ein unsichtbarer Assistent, der dem Friseur sagt: „Heute ist es etwas voll, senken wir den Preis ein wenig, um mehr Leute reinzubekommen, aber nicht zu viel, damit die Wartezeit nicht zu lang wird." Und das alles, ohne jemals die Leute zu zählen, die draußen stehen bleiben.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des vorliegenden Papers auf Deutsch:

Titel: Ein stochastischer Optimierungsalgorithmus zur Umsatzmaximierung in einem Service-System mit abweisenden Kunden (Balking)

Autoren: S. A. Bodas, H. Honnappa, M. Mandjes, L. Ravner
Datum: März 2026

---

1. Problemstellung

Das Paper untersucht ein Service-System, das als Ein-Server-Warteschlange (Single-Server Queue) modelliert ist. Das Ziel des Dienstleisters ist die dynamische Maximierung des erwarteten Umsatzes pro Zeiteinheit durch die Anpassung des Eintrittspreises $p$.

Die Komplexität des Problems ergibt sich aus folgenden Faktoren:

• Kundenverhalten (Balking): Kunden entscheiden sich basierend auf dem aktuellen Preis $p$ und dem wahrgenommenen Arbeitsaufwand (Wartezeit) $V$ im System, ob sie dem System beitreten oder es verlassen (balken). Die Beitrittswahrscheinlichkeit wird durch eine Funktion $H_\theta(p, V)$ beschrieben.
• Unvollständige Beobachtbarkeit: Der Dienstleister kann nur die effektiven Ankünfte (Kunden, die tatsächlich beitreten) beobachten. Kunden, die balken, sind unsichtbar. Dies führt zu einem nicht-standardisierten, zustandsabhängigen Ankunftsprozess.
• Zielsetzung: Finde den optimalen Preis $p^*$, der den langfristigen erwarteten Umsatz $\Psi(p)$ maximiert, wobei $\Psi(p) = p \cdot \lambda(p)$ und $\lambda(p)$ die stationäre effektive Ankunftsrate ist.

Das Hauptproblem besteht darin, dass die analytische Form von $\lambda(p)$ und dessen Gradienten in solchen Systemen (insbesondere mit allgemeinen Servicezeiten und Balking) meist nicht geschlossen lösbar ist. Herkömmliche Offline-Methoden scheitern oft an der Notwendigkeit, die Nachfragekurve und Warteschlangen-Primitiven exakt zu kennen.

---

2. Methodik

Die Autoren entwickeln einen Online-Lernalgorithmus auf Basis des Stochastic Gradient Descent (SGD), der den Preis iterativ anpasst, ohne dass eine explizite Kenntnis der Nachfragekurve oder der Servicezeitverteilung vorausgesetzt wird.

A. Modellierung

• System: M/G/1-Warteschlange mit Poisson-Ankünften (Rate $\Lambda$) und allgemeinen Servicezeiten.
• Beitrittsentscheidung: Ein Kunde mit beobachteter Wartezeit $V$ und Preis $p$ tritt mit Wahrscheinlichkeit $H(p, V)$ bei.
• Effektiver Ankunftsprozess: Da das Balking vom Zustand abhängt, ist der Prozess der effektiven Ankünfte kein Poisson-Prozess mehr. Die Zwischenankunftszeiten sind weder exponentialverteilt noch unabhängig.

B. Der Lernalgorithmus (SGD)

Der Algorithmus aktualisiert den Preis $p_k$ in Iteration $k$ gemäß:
$$p_k = \pi_{\mathcal{P}} \left[ p_{k-1} + \eta_k \widehat{\nabla \Psi}(p_{k-1}) \right]$$
wobei $\pi_{\mathcal{P}}$ ein Projektionsoperator ist und $\eta_k$ die Lernrate darstellt.

Der Kern der Methode liegt in der Schätzung des Gradienten $\widehat{\nabla \Psi}(p)$. Da der Umsatz $\Psi(p) = p / E[A_\infty(p)]$ ist (wobei $A_\infty$ die stationäre effektive Zwischenankunftszeit ist), wird der Gradient über die Ableitung des Erwartungswerts der Zwischenankunftszeit berechnet.

C. Infinitesimal Perturbation Analysis (IPA)

Ein entscheidender technischer Beitrag ist die Entwicklung einer neuen IPA-Prozedur:

• Herausforderung: Standard-IPA erfordert oft, dass der Ankunftsprozess unabhängig vom Systemzustand ist. Hier hängt die Ankunftsrate jedoch vom aktuellen Arbeitsaufwand ab.
• Lösung: Die Autoren konstruieren einen Pfad-Gradienten (sample-path gradient) für die effektiven Zwischenankunftszeiten. Sie nutzen eine rekursive Darstellung der inversen Verteilungsfunktion der Ankunftszeiten, um den Gradienten $\nabla_p A_\infty(p)$ direkt aus den beobachteten Daten (Zwischenankunftszeiten und Wartezeiten) zu schätzen.
• Konsistenz: Es wird bewiesen, dass dieser Schätzer konsistent ist und der Erwartungswert des Pfadgradienten dem Gradienten des Erwartungswerts entspricht (unter milden Regularitätsbedingungen).

D. Konvergenzanalyse

Die Analyse stützt sich auf:

1. Kopplungstechniken (Coupling): Um die Konvergenz des Warteschlangensystems zu verschiedenen Anfangszuständen zu beweisen und Transienten zu kontrollieren.
2. Bias- und Varianzanalyse: Es werden obere Schranken für den Bias und die Varianz des Gradientenschätzers hergeleitet. Der Bias decayt mit der Rate $O(\eta_{k-1} (T^*_{k-1})^{-2})$, wobei $T^*_k$ die Größe des Beobachtungsfensters ist.
3. Regret-Analyse: Die kumulative Umsatzverlust (Regret) wird analysiert, um die Effizienz des Algorithmus im Vergleich zum optimalen statischen Preis zu quantifizieren.

---

3. Wichtige Beiträge

1. Neues Modellierungsframework: Integration von Balking-Verhalten direkt in die Umsatzfunktion, ohne separate Strafterme für Warteschlangenverzögerungen zu benötigen. Dies eliminiert die Notwendigkeit, willkürliche Gewichtungsfaktoren zwischen monetärem Umsatz und Wartezeit zu wählen.
2. IPA für zustandsabhängige Ankünfte: Entwicklung eines neuen IPA-Schätzers für effektive Ankunftsraten in Systemen, in denen die Ankunftsrate vom Systemzustand (Warteschlangenlänge) abhängt. Dies ist ein nicht-trivialer Fortschritt gegenüber der klassischen IPA-Theorie.
3. Online-Algorithmus mit theoretischen Garantien: Der vorgeschlagene SGD-Algorithmus konvergiert unter milden Bedingungen fast sicher gegen den optimalen Preis $p^*$. Es werden explizite Regret-Schranken hergeleitet.
4. Robustheit: Der Algorithmus benötigt keine Kenntnis der Servicezeitverteilung oder der genauen Form der Nachfragekurve, sondern nutzt nur beobachtete effektive Ankünfte.

---

4. Ergebnisse

• Konvergenz: Der Algorithmus konvergiert fast sicher zum optimalen Preis $p^*$. Die Konvergenzgeschwindigkeit hängt von der Wahl der Lernrate $\eta_k$ und der Fenstergröße $T^*_k$ ab.
• Regret-Schranke: Unter geeigneten Annahmen (starke Konkavität der Umsatzfunktion) wird eine Regret-Schranke von $O(\sum T^*_k k^{-\alpha/2})$ gezeigt.
• Numerische Experimente:
  • Die Simulationen bestätigen, dass der Algorithmus in verschiedenen Szenarien (unterschiedliche Servicezeitverteilungen wie Exponential- und Gamma-Verteilungen; verschiedene Beitrittsfunktionen) zuverlässig konvergiert.
  • Einfluss der Servicezeit: Eine höhere mittlere Servicezeit führt zu einem höheren optimalen Preis. Eine höhere Varianz der Servicezeit führt zu einem niedrigeren optimalen Preis und einem geringeren maximalen Umsatz.
  • Fenstergröße: Es wurde ein Trade-off identifiziert: Kleinere Fenster ermöglichen häufigere Updates, führen aber zu verrauschten Gradienten. Größere Fenster verbessern die Schätzgenauigkeit, verlangsamen aber die Iterationsrate. Ein logarithmisches oder sublineares Wachstum der Fenstergröße ($T^*_k \sim \log k$ oder $\sqrt{k}$) zeigte sich als effektiv.

---

5. Bedeutung und Ausblick

Dieses Paper liefert einen wichtigen theoretischen und praktischen Beitrag zur dynamischen Preisgestaltung in Warteschlangensystemen.

• Praktische Relevanz: In vielen realen Anwendungen (z. B. Cloud-Dienste, Telekommunikation, Ride-Hailing) sind die genauen Kundenpräferenzen und das Balking-Verhalten unbekannt. Der vorgestellte Algorithmus ermöglicht es Anbietern, Preise autonom und datengetrieben zu optimieren, ohne komplexe Modelle kalibrieren zu müssen.
• Theoretischer Fortschritt: Die Lösung des Problems der "unbeobachteten Balking"-Kunden und die Entwicklung einer IPA-Methode für zustandsabhängige Ankünfte öffnen neue Wege für die Optimierung von Warteschlangensystemen mit unvollständiger Information.
• Zukünftige Forschung: Die Autoren sehen Potenzial in der Erweiterung auf Mehr-Server-Systeme (Multi-Server), wo die Kopplungstechniken komplexer werden, sowie in Szenarien, in denen auch die Parameter der Kundenverteilung (z. B. Geduldsverteilung) unbekannt sind und gemeinsam mit dem Preis gelernt werden müssen (Reinforcement Learning).

Zusammenfassend stellt die Arbeit einen robusten, mathematisch fundierten Ansatz dar, um Umsatz in dynamischen, überlastungsempfindlichen Service-Systemen zu maximieren, indem sie Stochastische Gradientenabstiegsverfahren mit neuartigen Perturbationsanalysen kombiniert.