通过放宽限制提升匹配平台整体效率，同时保障用户不受损。
Facilitating Matches on Allocation Platforms
- 设计约束下优化放松哪些限制以最大化社会福利。
- 提出多项式时间算法，适用于一对一和一对多匹配场景。
- 实验证明可显著提升匹配率，适合平台方决策参考。
我们研究分配平台（如匹配平台）中，由分配促进者通过鼓励部分参与者放宽其限制来提高整体效用/社会福利的场景。该建议必须确保原本更优的参与者不受损害，且促进者可能受数量或类型限制（即‘预算’）。本文提出了该促进者的优化问题：在满足参与保障的前提下，选择最优的限制放松集合。贡献包括：(i) 形式化定义问题，提出参与保障层级及多种社会福利函数；(ii) 提供多种版本优化问题的多项式时间算法，涵盖一对一与一对多分配场景；(iii) 基于三个真实世界数据集的大量实验，展示促进策略的实际效益及不同参与保障的影响。
原文摘要 · Abstract (English)
We consider a setting where goods are allocated to agents by way of an allocation platform (e.g., a matching platform). An ``allocation facilitator'' aims to increase the overall utility/social-good of the allocation by encouraging (some of the) agents to relax (some of) their restrictions. At the same time, the advice must not hurt agents who would otherwise be better off. Additionally, the facilitator may be constrained by a ``bound'' (a.k.a. `budget'), limiting the number and/or type of restrictions it may seek to relax. We consider the facilitator's optimization problem of choosing an optimal set of restrictions to request to relax under the aforementioned constraints. Our contributions are three-fold: (i) We provide a formal definition of the problem, including the participation guarantees to which the facilitator should adhere. We define a hierarchy of participation guarantees and also consider several social-good functions. (ii) We provide polynomial algorithms for solving various versions of the associated optimization problems, including one-to-one and many-to-one allocation settings. (iii) We demonstrate the benefits of such facilitation and relaxation, and the implications of the different participation guarantees, using extensive experimentation on three real-world datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。