Online Algorithmen für Bayes'sches Überzeugen

• Antragsteller: Professor Dr. Martin Hoefer
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 514505843

Das grundlegende Problem im Informationsentwurf oder Bayes'schen Überzeugen besteht darin, dass ein informierter Agent (Sender) Informationen mit einem uninformierten Agenten (Empfänger) teilt, um den Empfänger zu überzeugen, eine Entscheidung im Sinne des Senders zu wählen. Bayes'sches Überzeugen ist ein sehr populäres Gebiet in der Ökonomie mit vielen Anwendungen. Die algorithmischen Aspekte sind dagegen bisher nicht gut verstanden. In diesem Projekt vertiefen wir das algorithmische Verständnis von Problemen im Kontext von Bayes'schem Überzeugen. Wir konzentrieren uns auf Online-Modelle, in denen Akquise und Teilen der Information graduell und gleichzeitig ablaufen. Das Ziel ist, optimale und fast-optimale Überzeugungsstrategien für den Sender zu analysieren und effizient zu berechnen. Die Online-Modelle sind eng mit Modellen aus dem Optimal Stopping verwandt, insbesondere mit kombinatorischen Sekretärproblemen und prophetischen Ungleichungen. Hierbei kann der Empfänger mehrere Aktionen unter kombinatorischen Einschränkungen wählen. Wir konzentrieren uns dabei insbesondere auf Packprobleme wie Rucksack oder Matching. Das Ziel ist, die Komplexität von Empfehlungsstrategien zu untersuchen, mit denen der Sender seine erwartete Utility maximiert, während er dem Empfänger einen Anreiz gibt, die empfohlene Aktion auszuwählen. Daneben untersuchen wir mit Hilfe von kompetitiver Analyse, wie man gute Empfehlungsstrategien berechnen kann, die einen beschränkten Verlust garantieren zu optimalen Strategien im Offline-Modell (mit Kenntnis der Zukunft). Insbesondere ist dabei von Interesse, ob es "Black-Box"-Reduktionen gibt, mit denen man gute Online-Algorithmen zur Berechnung von guten Online-Empfehlungsstrategien nutzen kann. Unsere Resultate werden algorithmische Werkzeuge für Empfehlungsprobleme neu entwickeln und erweitern.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Israel
• ausländischer Mitantragsteller: Professor Rann Smorodinsky, Ph.D.