Multi-agent Assortment Optimization in Sequential Matching Markets

Par

Alfredo Torrico

Polytechnique Montreal

Résumé:

Consumer-supplier matching platforms pose several technical challenges, especially due to the tradeoff between recommending suitable suppliers to consumers and avoiding collisions among consumers’ preferences. In this work, we study the following setting: we (the platform) offer a menu of suppliers to each consumer. Then, every consumer selects 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. This is joint work with Margarida Carvalho and Andrea Lodi.

Biographie :

Alfredo Torrico is a postdoctoral researcher at the CERC in Data Science, Polytechnique Montreal. He obtained his Ph.D. in Operations Research in the School of Industrial and Systems Engineering at Georgia Tech in 2019. His main interest is the design of theoretical tools at the interface between discrete and continuous optimization for resource allocation and subset selection problems. Other topics of interest include fairness and diversity, spread of misinformation, and in general, topics on Operations Research/Machine Learning for social good.