Stable Assignment Problems for Staffing: Complete Matchings, Local Stability, and Dynamic Reassignments

工作人员失业是许多组织面临的一个大规模问题，包括军事和多国组织，如联合国机构。虽然成功的算法已经开发，可以确保稳定的匹配（匹配没有激励偏离），并不是所有的实际问题已经解决了这些算法。这项研究是在与世界上最大的人道主义机构-世界粮食计划署（粮食计划署）不断讨论后发起的。单是人道主义影响就很重要，因为稳定的匹配会提高工作人员的稳定性，减少人员分配的成本，并最终使更多的美元可用于受益者。这项研究的结果也有可能改善美国军队的人员轮换，医疗住院医师分配，学校选择和器官分配。本研究利用出现在实际的稳定匹配问题的方面：（一）集中式组织往往可以与特定的代理商进行谈判，以改变他们的偏好列表;（二）对于大型系统，并不是所有的工作人员或工作将有完整的知识，其他人的偏好列表，因此潜在的一些稳定性的考虑可以放松，而不引入激励问题。 所提出的研究的目标是开发数学模型，可以确保一套完整的匹配，即使当偏好列表被截断，其中的模型是可扩展的大型组织，算法提供的方法，使动态分配随着时间的推移。所提出的研究将导致创新的模型，算法和方法来解决大规模的分配问题，考虑用户行为。求解该问题的方法包括带平衡约束的整数规划、松弛技术、动态规划和局部搜索。拟议的研究有助于计算机科学，经济学和优化的交叉点，通过研究优化与分散的决策者的背景下，开发算法的方法来大规模和实际的稳定匹配问题。

Assigning personnel to jobs is a large-scale problem faced by many organizations including the military and multinational organizations, such as United Nations agencies. Although successful algorithms have been developed that can ensure stable matchings (matchings without incentive to deviate), not all practical concerns have been addressed by these algorithms. This research was initiated by ongoing discussions with the World Food Programme (WFP), the largest humanitarian agency in the world. The humanitarian impact alone is significant, since stable matches lead to improved workforce stability, reduced costs of personnel assignments, and ultimately more dollars that can be used for beneficiaries. Findings of this research also have the potential to improve staff rotations in the US military, medical resident assignments, school choice, and organ allocations. This research exploits aspects appearing in practical stable matching problems: (i) centralized organizations often can negotiate with specific agents to change their preference lists; (ii) for large systems not all staff or jobs will have complete knowledge of others' preference lists, hence potentially some stability considerations can be relaxed without introducing incentive issues. The objective of the proposed research is to develop mathematical models that can ensure a complete set of matchings even when preference lists are truncated, where the models are scalable for large organizations, and the algorithms provide approaches to make dynamic assignments over time. The proposed research will result in innovative models, algorithms, and approaches to solve large-scale assignment problems with considerations of user behavior. The methodologies to solve the problems include integer programming with equilibrium constraints, relaxation techniques, dynamic programming, and local search. The proposed research contributes to the intersection of computer science, economics and optimization, by studying optimization with decentralized decision makers in the context of developing algorithmic approaches to large-scale and practical stable matching problems.