Two-Sided Assortment Optimization: Adaptivity Gaps and Approximation Algorithms

On the Power of Adaptivity in Choice-Based Matching Platforms Online labor, lodging, and carpooling platforms decide not only whom users can choose but also when those options are shown. Simultaneity can crowd attention around a few popular users and leave many good matches unrealized. In the forthcoming Operations Research paper, “Two-Sided Assortment Optimization: Adaptivity Gaps and Approximation Algorithms,” the authors study how much platforms gain by updating assortments after observing earlier choices. They compare four policy classes, ranging from showing all assortments at once to fully adaptive policies that process users one by one. They prove that adaptivity within one side improves performance by at most a factor of [Formula: see text], whereas fully adaptive policies improve on one-sided adaptive policies by at most a factor of two; both bounds are tight. They also develop efficient approximation algorithms, extend their results to constrained settings, and empirically show that their methods perform far better than their worst-case guarantees.