Provable Guarantees for General Two-sided 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 trade-off between recommending suitable suppliers consumers avoiding collisions among consumers' preferences. In this work, we study a general version two-sided sequential model introduced by Ashlagi et al. (2019). The setting is following: (the platform) offer menu each consumer. Then, every consumer selects, simultaneously independently, match with supplier or remain unmatched. Suppliers observe subset that selected them, choose either leave system. Finally, takes place if both sequentially select other. Each agent's behavior probabilistic determined regular discrete choice model. Our objective an assortment family maximizes expected cardinality matching. Given computational complexity problem, show provable guarantees for model, which particular, significantly improve approximation factors previously obtained.