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

分配人员的工作是许多组织面临的一个大规模的问题，包括军事和跨国组织，如联合国机构。尽管已经开发出了能够确保稳定匹配（没有偏离激励的匹配）的成功算法，但这些算法并没有解决所有实际问题。这项研究是由与世界上最大的人道主义机构世界粮食计划署（粮食计划署）进行的讨论发起的。仅人道主义方面的影响就很重要，因为稳定的匹配可以提高劳动力的稳定性，降低人员派遣的成本，最终可以为受益人提供更多的资金。这项研究的发现也有可能改善美国军队的工作人员轮换、医疗住院分配、学校选择和器官分配。本研究利用了实际稳定匹配问题中出现的一些方面：(1)中心化组织经常可以与特定的代理协商改变他们的偏好列表；（ii）对于大型系统而言，并非所有员工或职位都完全了解其他人的偏好清单，因此可以在不引入激励问题的情况下放宽一些稳定性考虑。该研究的目标是开发数学模型，即使在偏好列表被截断时也能确保一套完整的匹配，其中模型可用于大型组织，并且算法提供了随时间动态分配的方法。提出的研究将产生创新的模型、算法和方法来解决考虑用户行为的大规模分配问题。解决这些问题的方法包括平衡约束的整数规划、松弛技术、动态规划和局部搜索。该研究通过在开发大规模和实际稳定匹配问题的算法方法的背景下研究分散决策者的优化，从而促进了计算机科学，经济学和优化的交叉。

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.