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.
翻译:我们的重点是资源分配问题,即代理可能存在使其与某些资源不相容的限制。我们假设,原则会随机选择最大匹配,以便每个代理都与某种可能性的资源相匹配。代理人希望增加其匹配的机会,在一定限度内修改其限制。原则的目标是建议不满意的代理放松其限制,以便放松总费用在预算范围内(由代理所选择),分配资源的可能性增加最大化。我们为这一预算紧缩的最大化问题的某些变体确定硬性结果,并为其他变体提出算法结果。我们实验性地评估我们合成数据集的方法以及两个新的真实世界数据集:度假活动数据集和教室数据集。