论文标题
连续匹配市场中的多代理分类优化
Multi-agent Assortment Optimization in Sequential Matching Markets
论文作者
论文摘要
在这项工作中，我们研究了Ashlagi等人引入的双面顺序匹配模型中的多代理分类优化问题。 （2022）。设置如下：我们（平台）为每个客户提供供应商菜单。然后，每个客户同时且独立地选择与供应商匹配或保持无与伦比。每个供应商都观察选择它们的客户的子集，并选择与客户匹配或离开系统。因此，如果客户和供应商都依次选择彼此，则进行匹配。每个代理的行为都是概率的，由离散选择模型决定。我们的目标是选择一个最大化匹配收入的各种家族。鉴于问题的硬度，我们在异质环境中显示了$ 1-1/e $ - approximation因子，在该设置中，客户遵循一般选择模型和供应商遵循的一般选择模型，其需求功能是单调和supsodular。我们的方法足够灵活，可以允许不同的分类限制和收入目标功能。此外，我们设计了一种超过$ 1-1/e $障碍的算法，实际上，当供应商遵循经典的多项式选择模型并且足够选择性时，它在渐近上是最佳的。我们最终提供了其他结果和进一步的见解。值得注意的是，在不受约束的环境中，客户和供应商遵循多项式模型，我们设计了一种简单有效的近似算法，该算法适当地随机随机随机而在嵌套分类家族中进行了适当的随机。此外，我们分析了匹配市场模型的各个方面，这些方面导致了几种运营见解，例如，匹配平台可以从允许更具选择性的代理人启动对接过程中受益。
In this work, we study the multi-agent assortment optimization problem in the two-sided sequential matching model introduced by Ashlagi et al. (2022). The setting is the following: we (the platform) offer a menu of suppliers to each customer. Then, every customer selects, simultaneously and independently, to match with a supplier or to remain unmatched. Each supplier observes the subset of customers that selected them, and choose either to match a customer or to leave the system. Therefore, a match takes place if both a customer and a supplier sequentially select each other. Each agent's behavior is probabilistic and determined by a discrete choice model. Our goal is to choose an assortment family that maximizes the expected revenue of the matching. Given the hardness of the problem, we show a $1-1/e$-approximation factor for the heterogeneous setting where customers follow general choice models and suppliers follow a general choice model whose demand function is monotone and submodular. Our approach is flexible enough to allow for different assortment constraints and for a revenue objective function. Furthermore, we design an algorithm that beats the $1-1/e$ barrier and, in fact, is asymptotically optimal when suppliers follow the classic multinomial-logit choice model and are sufficiently selective. We finally provide other results and further insights. Notably, in the unconstrained setting where customers and suppliers follow multinomial-logit models, we design a simple and efficient approximation algorithm that appropriately randomizes over a family of nested-assortments. Also, we analyze various aspects of the matching market model that lead to several operational insights, such as the fact that matching platforms can benefit from allowing the more selective agents to initiate the matchmaking process.
