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.
