Algorithms for bayesian persuasion and delegated search
Authors:   , Hahn Niklas 
Published: May 2022

In dieser Dissertation betrachten wir Algorithmen für strategische Kommunikation mit Commitment Power zwischen zwei rational agierenden Parteien mit eigenen Interessen. Wenn eine Partei Commitment Power besitzt, so legt sie sich im Vorhinein auf eine Handlungsstrategie fest und macht diese öffentlich bekannt. Beide Parteien besitzen gewisse Grundinformation über den Zustand der Welt. Die erste Partei (S) hat die Möglichkeit, diesen direkt zu beobachten. Die zweite Partei (R) trifft jedoch eine Entscheidung durch die Wahl einer von n Aktionen mit für sie unbekanntem Typ. Dieser Typ bestimmt die (verschiedenen) nicht-negativen Nutzwerte für S und R. Folglich versucht S durch das Senden bestimmter Signale die Handlungen von R zu beeinflussen. Sollte keine Aktion gewählt werden, erhalten beide Parteien einen Wert 0. Wir betrachten zwei verschiedene Grundszenarien. Im ersten Teil behandeln wir Bayesian Persuasion, im zweiten Teil Delegated Search. In Bayesian Persuasion besitzt S Commitment Power. Das bedeutet, dass S sich auf ein Signalschema φ festlegen und dieses Schema R kommunizieren muss. Das Schema φ beschreibt, in welcher Situation welche Signale gesendet werden. Erst danach erhält S Informationen über den wahren Zustand der Welt. Daraufhin empfängt R die entsprechenden Signale, bestimmt durch φ, und trifft eine Entscheidung für eine der Aktionen. Da die Signale jedoch auf dem bekannten Schema φ basieren, kann R durch Bedingung auf die empfangenen Signale eine Aktualisierung der Annahmen über den Zustand der Welt durchführen und diese zusätzliche Information in die Entscheidung für eine der Aktionen einfließen lassen. Dies muss S folglich für das Design von φ berücksichtigen. R wird keinen Empfehlungen für bestimmte Aktionen folgen, wenn diese nur vorteilhaft für S, nicht jedoch für R selbst sind. Wir betrachten das Problem aus der Sicht von S und versuchen also, Signalschemata zu entwickeln, die einen möglichst großen Nutzen für S garantieren. Wir betrachten sowohl den Offline- als auch den Online-Fall von Bayesian Persuasion. Im Offline-Fall erfährt S den kompletten Zustand der Welt und schickt daraufhin ein Signal an R. Wir betrachten ein Szenario mit einer beschränkten Anzahl k ≤ n Signale, sodass S (eventuell) keine Möglichkeit hat, ein Signal für jede einzelne der Aktionen zu senden. Wir beschreiben einen Algorithmus, der für verschiedene symmetrische Instanzen in Polynomialzeit ein optimales Signalschema berechnen kann, selbst, wenn S nur Zugang zu k verschiedenen Signalen hat. Weiterhin betrachten wir eine Teilmenge der Instanzen, in denen die Typen der Aktionen unabhängig voneinander aus bekannten Verteilungen gezogen werden. Für diese beschreiben wir Approximationsalgorithmen, die in Polynomialzeit ein Signalschema berechnen, welches einen konstanten Faktor im Vergleich zum Ergebnis eines optimalen Schemas garantiert. Auch hier gilt das Resultat, wenn S nur k ≤ n Signale zur Verfügung stehen. Abschließend zeigen wir, mit welchen Verlusten S zu rechnen hat, wenn nur k anstelle von n Signalen zur Verfügung stehen. Im Online-Fall werden die Typen der Aktionen nacheinander aufgedeckt und S muss zu jeder Aktion ein Signal versenden. R muss sofort auf die Signale reagieren. Wenn eine Aktion gewählt wird, endet der Prozess. Ansonsten wird der Typ der nächsten Aktion aufgedeckt und vorherige Aktionen können nicht mehr gewählt werden. Als Richtwert für unsere Online-Signalschemata verwenden wir das beste Offline-Signalschema. Zunächst betrachten wir ein Szenario, bei dem die Typen der Aktionen unabhängig voneinander aus bekannten Verteilungen gezogen werden. Hierzu zeigen wir, wie ein optimales Signalschema in Polynomialzeit bestimmt werden kann. Allerdings gibt es Beispiele, bei denen S im Online-Fall keinen positiven Approximationsfaktor im Vergleich zum Offline-Fall erzielen kann. Wir betrachten daraufhin eine Teilmenge von Instanzen, für die ein einfaches Signalschema einen konstanten Approximationsfaktor garantiert und zeigen, dass dieser Faktor optimal ist. Weiterhin betrachten wir einen Online-Fall, bei dem die Typen der Aktionen nicht aus einer bekannten Verteilung gezogen werden, sondern unbekannt sind. Die einzige Information ist, dass sie in uniform zufälliger Reihenfolge aufgedeckt werden. Wir betrachten 16 verschiedene Fälle mit unterschiedlichem Level an Information für S und R sowie unterschiedlichen Zielfunktionen für die beiden Parteien. Für fast alle Szenarien zeigen wir effiziente Algorithmen, die ein Signalschema berechnen, was eine konstante Approximationsgarantie im Bezug auf das jeweilige Offline-Schema aufweist. Für die verbleibenden Fälle zeigen wir, dass ein solches Schema nicht existieren kann. Für die meisten Fälle zeigen wir passende obere Schranken zu unseren Approximationsgarantien. Im zweiten Teil betrachten wir eine Online-Variante von Delegated Search. Hier besitzt nun R und nicht mehr S Commitment Power. Wir nehmen an, dass die Typen der n Aktion aus a priori bekannten, unabhängigen Verteilungen gezogen werden. Bevor S die realisierten Typen der Aktionen beobachten kann, legt R sich auf ein Akzeptanzschema φ fest. ...