# A General Statistical Physics Framework for Assignment Problems
###### Abstract
If there are \(N_{2}\) tasks and \(N_{1}\) agents, with \(N_{2}>N_{1}\), for example, it is possible to add \(N_{2}-N_{1}\) \"dummy\" agents, solve the balanced assignment problem of size \(N_{2}\), and then only retain the assignments to the actual \(N_{1}\) agents. If each agent can perform up to \(M\) tasks, the textbook solution is then to create \(M\) copies of each agent prior to using the Hungarian algorithm. This approach, however, may not lead to the expected solution. Consider a problem with fiv tasks and three agents, with each agent allowed to perform up to three tasks. The option of creating three copies of each agent and then solving the corresponding unbalanced assignment problem may lead to one agent performing two tasks, a second agent performing three tasks, and the last agent not performing any task, possibly violating a constraint that each agent needs to perform at least one task. Several methods have been proposed to circumvent this problem, either by dividing the problem into multiple subproblems [10; 11] or by using random algorithms such as the ant colony algorithms [12; 13]. It is unclear whether these algorithms can identify the optimal solution (they have been shown to fail in some cases, see for example [14]) or how they scale for large problems. In this paper, we propose a radically different approach to solving a general class of assignment problems using continuous systems. Our approach is motivated by statistical physics. It is a full generalization of the method developed in a previous paper to solve balanced assignment problems [15]. In the following, we will use the generic term \"multi-assignment\" to represent an assignment problem with agents possibly performing multiple tasks, or with tasks assigned to multiple agents. In this paper, we aim to  
* Introduce and substantiate a continuous framework for addressing potentially multi-faceted assignment problems involving multiple tasks and/or multiple agents, leveraging principles from statistical physics;
* Demonstrate that, under generic circumstances where the multi-assignment problem possesses a unique solution, the aforementioned framework ensures convergence to that solution with arbitrarily high accuracy, in terms of both cost (referred to as energy) and assignment matrix,
* Present a modified approach capable of identifying at least one solution for degenerate multi-assignment problems that feature multiple solutions;
* Demonstrate that the implementation of this framework can be efficiently parallelized. We emphasize that this formalism is not a mere adaptation but a full generalization of the framework we develop for solving assignment problems [16]. In particular, new features of this paper are as follows:  
* A method to account for the fact that each task can be assigned to a variable number of agents and, on the other hand, that each agent can be assigned a variable number of tasks. To that end, we introduce indicator functions over the sets of tasks and agents that are optimized along with the transportation plan. * The establishment of proofs of validity and convergence of our algorithm for those general multi-assignment problems. The main results are provided in the text, while the proofs themselves are relegated to the Appendices for more clarity. For the balanced assignment problem, these proofs rely heavily on the fact that the corresponding transportation matrices are permutation matrices that are the extreme points of the well-characterized convex set of doubly stochastic matrices (according to the Birkhoff-von Neumann theorem [17; 18]). For more general multi-assignment problems, the transportation matrices also belong to a convex set, with properties akin to the Birkhoff-von Neumann theorem (these properties are discussed in Appendix A). The use of these properties to derive the convergence of our algorithm for solving multi-assignment problems is new. The paper is organized as follows. In sections 2 to 4, we describe in detail the general framework we propose for solving multi-assignment problems.