# A General Statistical Physics Framework for Assignment Problems
## 6 Examples  
The framework we propose is general: it allows us to solve balanced and unbalanced assignment problems, including those that allow for multi-agent or multi-task assignments. We illustrate our method on the latter types of problems, as, to our knowledge, there are currently no solutions to those that are guaranteed to reach the optimal assignment. As a first illustration of our framework, we ran Matching on the cost matrix \(C_{1}\) given in Table 1. This matrix has been used in previous studies of multi-agent assignment problems [10; 11; 13; 14; 26; 27]. Matching was run with the following parameters: \(p_{min}=0\) for all agents (i.e., some agents may stay idle), \(p_{max}=4\) for all agents (i.e., an agent can perform up to 4 tasks), \(q_{min}=q_{max}=1\) (i.e., a task is only performed by one agent), and \(k=8\) (all tasks are performed). In Figure 1, we show the corresponding trajectories of the internal energy \(U_{\beta}^{iMF}\) and free energy \(F_{\beta}^{MF}\). As expected, the internal energy is monotonically decreasing while the free energy is monotonically increasing, and both converge to the same value, 1440. Theorem 3 provides bounds on those energy values. Note that it can be rewritten as  
\[U_{\beta}^{MF}-\frac{A(N_{1},N_{2})}{\beta}\leq U^{*}\leq U_{\beta}^{ MF},\] \[F_{\beta}^{MF}\leq U^{*}\leq U_{\beta}^{MF}+\frac{A(N_{1},N_{2}) }{\beta},\]  
i.e., at each value of \(\beta\), we have bounds based on internal energy and free energy for the actual optimal cost of the assignment problem. These bounds are shown as shaded areas in Figure 1. Note that the widths of the intervals defined by the bounds are inversely proportional to \(\beta\) and therefore decrease monotonically as \(\beta\) increases. In Table 2, we compare the assignment found by Matching on \(C_{1}\) with \(p_{max}\) set to 4 (i.e., up to four tasks per agent), and \(p_{min}=0\) (agents can be idle) or \(p_{min}=1\) (each agent must execute at least one task). The removal of the latter constraint leads to a better optimal assignment in which agent 3 remains idle. When we maintain this constraint, our results are the same as those found by [PERSON] et al. (2019). As a second more general test of our method, we compared the results of the framework we propose with the results of our own version of the Hungarian algorithm, as well as with those found in previous studies. We used both the matrix C1 and the matrix C2 given in Table 3 in those computing experiments. \begin{table}
\begin{tabular}{l c c c c c c c c} \hline  & & & & & & & & \\ \hline
**Agents** & \(\mathbf{T_{1}}\) & \(\mathbf{T_{2}}\) & \(\mathbf{T_{3}}\) & \(\mathbf{T_{4}}\) & \(\mathbf{T_{5}}\) & \(\mathbf{T_{6}}\) & \(\mathbf{T_{7}}\) & \(\mathbf{T_{8}}\) \\ \hline \(A_{1}\) & 300 & 250 & 180 & 320 & 270 & 190 & 220 & 260 \\ \(A_{2}\) & 290 & 310 & 190 & 180 & 210 & 200 & 300 & 190 \\ \(A_{3}\) & 280 & 290 & 300 & 190 & 190 & 220 & 230 & 260 \\ \(A_{4}\) & 290 & 300 & 190 & 240 & 250 & 190 & 180 & 210 \\ \(A_{5}\) & 210 & 200 & 180 & 170 & 160 & 140 & 160 & 180 \\ \hline \end{tabular}
\end{table} 
Table 1: The cost matrix \(C_{1}\). Figure 1: Convergence of the internal energy \(U_{\beta}^{MF}\) (**A**) and free energy \(F_{\beta}^{MF}\) (**B**) as a function of \(\beta\) when solving the multi-task assignment problem with the cost matrix \(C_{1}\), such that each agent can perform up to 4 tasks, may be idle, and all 8 tasks are performed. On both panels, we show the bounds on the expected value for the optimal cost \(U^{*}\) as shaded areas (see text for details). We ran Matching as follows. For all tasks \(j\), we set \(q_{min}(j)=q_{max}(j)=1\), i.e., a task is only performed by one agent, and all tasks are expected to be executed. The latter is further enforced by setting \(k\) to be the total number of tasks (8 for \(C_{1}\) and 10 for \(C_{2}\)). For an agent \(i\), we either set all \(p_{min}(i)\) to be 1 (in which case all agents must perform at least one task) or 0 (in which case some agents may not be assigned).