论文标题
资源分配给有限制的代理：最大程度地提高可能性的可能性
Resource Allocation to Agents with Restrictions: Maximizing Likelihood with Minimum Compromise
论文作者
论文摘要
在两部分图上，有限制代理争夺资源的代理商竞争资源的许多情况都可以作为最大匹配问题。我们的重点是资源分配问题，在这些问题上，代理可能会有限制，使其与某些资源不相容。我们假设一个原理可以随机选择最大匹配，以便每个代理都具有一定概率的资源。代理商希望通过在一定范围内修改限制来提高他们的匹配机会。原则的目标是建议一个不满意的代理商放松其限制，以便放松的总成本在预算之内（由代理商选择），并最大化了分配资源的可能性的增加。我们为这种预算受限的最大化问题的某些变体建立硬度结果，并为其他变体提供算法结果。我们通过实验性地评估了关于合成数据集以及两个新颖的现实数据集的方法：一个度假活动数据集和一个教室数据集。
Many scenarios where agents with restrictions compete for resources can be cast as maximum matching problems on bipartite graphs. Our focus is on resource allocation problems where agents may have restrictions that make them incompatible with some resources. We assume that a Principle chooses a maximum matching randomly so that each agent is matched to a resource with some probability. Agents would like to improve their chances of being matched by modifying their restrictions within certain limits. The Principle's goal is to advise an unsatisfied agent to relax its restrictions so that the total cost of relaxation is within a budget (chosen by the agent) and the increase in the probability of being assigned a resource is maximized. We establish hardness results for some variants of this budget-constrained maximization problem and present algorithmic results for other variants. We experimentally evaluate our methods on synthetic datasets as well as on two novel real-world datasets: a vacation activities dataset and a classrooms dataset.
