Zweiseitige Sortimentoptimierung: Adaptivitätslücken und Approximationsalgorithmen

Um die Herausforderung der Wahlbelastung in Matching-Märkten anzugehen, stellen wir in dieser Arbeit einen Rahmen für die zweiseitige Sortimentoptimierung unter allgemeinen Wahlpräferenzen vor. Das Ziel dieses Problems besteht darin, die erwartete Anzahl an Übereinstimmungen zu maximieren, indem entschieden wird, welche Sortimente den Agenten angezeigt werden und in welcher Reihenfolge sie gezeigt werden. In diesem Zusammenhang identifizieren wir mehrere Klassen von Richtlinien, die Plattformen in ihrem Design nutzen können. Unsere Ziele sind: (1) den Wert zu messen, den eine Klasse von Richtlinien gegenüber einer anderen hat, und (2) das Optimierungsproblem selbst für eine gegebene Klasse annähernd zu lösen. Für (1) definieren wir die Adaptivitätslücke als das Worst-Case-Verhältnis zwischen den optimalen Werten von zwei unterschiedlichen Klassen von Richtlinien. Zunächst zeigen wir, dass die Lücke zwischen der Klasse von Richtlinien, die Sortimente statisch zuerst einer Seite anzeigen, und der Klasse von Richtlinien, die Sortimente adaptiv zuerst einer Seite anzeigen, genau 1 - 1/e beträgt. Zweitens zeigen wir, dass die Lücke zwischen letzterer Klasse von Richtlinien und der vollständig adaptiven Klasse von Richtlinien, die Sortimente den Agenten einzeln zeigen, genau 1/2 beträgt. Wir stellen auch fest, dass die schlechtesten Richtlinien diejenigen sind, die gleichzeitig Sortimente allen Agenten anzeigen; tatsächlich zeigen wir, dass ihre Adaptivitätslücke sogar im Hinblick auf einseitige statische Richtlinien willkürlich klein sein kann. Für (2) zeigen wir zunächst, dass es eine polynomielle Zeitrichtlinie gibt, die einen Approximationsfaktor von 1/4 innerhalb der Klasse von Richtlinien erreicht, die Sortimente adaptiv den Agenten einzeln zeigen. Schließlich zeigen wir, dass ein Approximationsfaktor von 0,066 innerhalb der Klasse von Richtlinien erreicht werden kann, die Sortimente einmal allen Agenten anzeigen, wenn die Präferenzen der Agenten durch multinomiale Logit-Modelle bestimmt werden.