We consider the problem of assigning agents to programs in the presence of two-sided preferences. Each agent has to be assigned to at most one program and each program can accommodate multiple agents. However unlike the standard setting of school choice, we do not have fixed upper quotas with programs as an input -- instead we abstract it as a cost associated with every program. This setting enables the programs to control the number of agents assigned to them and is also applicable in the two-round setting (Gajulapalli et al., FSTTCS 2020) where largest stable extension is computed. In this setting, our goal is to compute a min-cost stable matching that matches all the agents. We show that the problem is NP-hard even under very severe restrictions on the instance. We complement our negative results by presenting approximation algorithms for general case and a fast exponential algorithm for a special case.
翻译:我们考虑在有双面偏好的情况下向方案指派代理的问题。 每个代理必须被分配到最多一个程序, 每个程序可以容纳多个代理。 但是,与学校选择的标准设置不同, 我们没有固定程序的最高配额作为投入, 我们把它抽象起来作为每个程序的相关成本。 这个设置使程序能够控制分配给它们代理的数量, 并且也适用于计算最大稳定扩展的双轮环境( Gajulapalli 等人, FSTTCS 2020 ) 。 在此设置中, 我们的目标是计算一个与所有代理匹配的低成本稳定匹配。 我们显示, 问题很硬, 即使在非常严格的限制下, 我们通过为普通案例提供近似算法和为特殊案例提供快速指数算法来补充我们的负面结果 。