Multi-agent Assortment Optimization in Sequential Matching Markets

Two-sided markets have become increasingly more important during the last years, mostly because of their numerous applications in housing, labor and dating. Consumer-supplier matching platforms pose several technical challenges, specially due to the tradeoff between recommending suitable suppliers to consumers and avoiding collisions among consumers' preferences. In this work, we study a general version of the two-sided sequential matching model introduced by Ashlagi et al. (2019). The setting is the following: we (the platform) offer a menu of suppliers to each consumer. Then, every consumer selects, simultaneously and independently, to match with a supplier or to remain unmatched. Suppliers observe the subset of consumers that selected them, and choose either to match a consumer or leave the system. Finally, a match takes place if both the consumer and the supplier sequentially select each other. Each agent's behavior is probabilistic and determined by a regular discrete choice model. Our objective is to choose an assortment family that maximizes the expected revenue of the matching. Given the computational complexity of the problem, we show several constant factor guarantees for the general model that, in particular, significantly improve the approximation factors previously obtained. Furthermore, we obtain the first constant approximation guarantees when the problem is subject to cardinality constraints. Our approach relies on submodular optimization techniques and appropriate linear programming relaxations. Finally, we provide a computational study on different settings that supports our technical results.