Verstehen von Posted Prices durch Prophet Inequalities

• Antragsteller: Professor Dr. Thomas Kesselheim
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 437739576

Prophet Inequalities bieten einen Rahmen für probabilistische Analysen von Online-Algorithmen und -Mechanismen. Sie haben ihren Ursprung in der Optimal-Stopping Theory, in der es darum geht, eine Folge von Zahlen beim Erreichen des höchsten Wertes zu stoppen. Ein Algorithmus kennt im Voraus die Wahrscheinlichkeitsverteilungen, aus denen die Zahlen gezogen werden. Seine Auswahl wird mit der im Nachhinein optimalen Wahl verglichen, das heißt, was ein hypothetischer Prophet getan hätte, der die Zukunft kennt.In den letzten Jahren wurden zahlreiche Erweiterungen für kombinatorische Nebenbedingungen wie Matroide und kombinatorische Auktionen vorgestellt. Ein Grund für das aktuelle Interesse ist, dass solche Algorithmen als Posted-Price-Mechanismen eine besonders überzeugende Anwendung finden. Im Fall einer kombinatorischen Auktion werden den Gütern feste Preise zugewiesen; die Käufer erscheinen nacheinander und jedem Käufer wird diejenige Menge aus verbleibenden Gütern zugewiesen, mit dem der Nutzen maximiert wird. Im Kontext des Algorithmic Mechanism Design entsprechen sie einfachen, suboptimalen, anreizkompatiblen Mechanismen mit nachweisbaren Approximationsgarantien.In bisherigen Arbeiten hergeleitete Garantien sind von Natur aus pessimistisch: Die übliche Annahme ist, dass die Wahrscheinlichkeitsverteilungen beliebig sein können. Obere und untere Schranken stimmen in vielen Fällen nur aufgrund von Randfällen überein. Aus diesem Grund möchten wir in diesem Projekt verstehen, welche Auswirkungen die Wahl der Verteilungen hat. Dies gibt uns nicht nur die Möglichkeit, bessere Garantien und ein genaueres Bild zu erhalten, sondern auch die Chance, zu verstehen, warum Prophet Inequalities überhaupt gelten. Zum Beispiel erweist sich bei allgemeinen Verteilungen der einfachste Fall als derjenige mit den schlechtesten Garantien. Bis jetzt ist nicht klar, ob dies ein Artefakt der Worst-Case-Analyse oder ein allgemeines Muster ist.Im Einzelnen werden wir uns zunächst eingeschränkten Klassen von Wahrscheinlichkeitsverteilungen widmen. Wir konzentrieren uns auf Fälle, die gut motiviert und in wirtschaftswissenschaftlichen Kontexten etabliert sind. Für diese können wir stärkere Garantien herleiten. Ein verwandtes Ziel ist es, Verteilungen zu charakterisieren, die bessere Garantien ermöglichen. Abschließend werden wir Problemstellungen mit reduzierter Kenntnis über die Wahrscheinlichkeitsverteilungen betrachten, wie zum Beispiel dem Zugriff auf einzelne Samples. Die Unterscheidung zwischen Verteilungen ermöglicht es uns, auch hier ein genaueres Bild zu entwickeln.

• DFG-Verfahren: Sachbeihilfen