# A General Statistical Physics Framework for Assignment Problems
## 3 Solving Generic Assignment Problems  
In the previous section, we proposed an effective free energy, \(F_{\beta}(\lambda,\mathbf{\mu},x)\), that depends on \(N_{1}+N_{2}+1\) unconstrained variables and on the inverse of the temperature, \(\beta\), whose extremum identifies the solution of a possibly multi-job, multi-agent assignment problem. We have shown that the trajectory of this extremum is monotonic, increasing with respect to \(\beta\). We now relate these values to the optimal assignment energy \(U^{*}\):  
**Theorem 2**.: _Let \(F_{\beta}^{MF}\) and \(U_{\beta}^{MF}\) be the mean field approximations of the exact free energy and internal energy of the system at the inverse temperature \(\beta\). The optimal assignment energy \(U^{*}\) is then given by,_  
\[U^{*} = \lim_{\beta\rightarrow+\infty}F_{\beta}^{MF},\] \[U^{*} = \lim_{\beta\rightarrow+\infty}U_{\beta}^{MF}, \tag{13}\]  
_namely, the optimal assignment energy, \(U^{*}\), is equal to the infinite limit with respect to the inverse temperature of both the mean field free energy and the internal energy._  
Proof.: See Appendix E.  
This theorem illustrates that as the inverse temperature approaches infinity (or equivalently, as the temperature tends towards zero), the internal energy and free energy of the system converge to the optimal assignment energy. This confirms the validity of our statistical physics approach, particularly emphasizing the effectiveness of the saddle-point approximation. Note, however, that it does not define the behavior of the coupling matrix \(\overline{G}_{\beta}=X^{MF}\). As \(\overline{G}_{\beta}(i,j)=h(\beta(C(i,j)+\lambda^{MF}(i)+\mu^{MF}(j)+x^{MF}))\) and \(0<h(x)<1\), the coupling matrix at any finite temperature is fractional. We need to show that as \(\beta\rightarrow+\infty\), the corresponding matrix \(\overline{G}_{\infty}\) does converge to the solution matrix \(G^{*}\) and not to a fractional matrix that would lead to the same low energy \(U^{*}\).  
We first establish bounds on the internal energy and free energy at the SPA. Let us define  
\[A(N_{1},N_{2})= N_{1}N_{2}\ln(2)+\sum_{i=1}^{N_{1}}\ln(p_{max}(i)-p_{min}(i)+1)\] \[+\sum_{j=1}^{N_{2}}\ln(q_{max}(j)-q_{min}(j)+1). \tag{14}\]  
**Theorem 3**.: \(F_{\beta}^{MF}\) _and \(U_{\beta}^{MF}\), the mean field approximations of the exact free energy and internal energy of the system at the inverse temperature \(\beta\), satisfy the following inequalities:_  
\[U^{*}-\frac{A(N_{1},N_{2})}{\beta} \leq F_{\beta}^{MF}\leq U^{*}, \tag{15}\] \[U^{*} \leq U_{\beta}^{MF}\leq U^{*}+\frac{A(N_{1},N_{2})}{\beta}, \tag{16}\]  
_where \(U^{*}\) is the optimal assignment energy and \(A(N_{1},N_{2})\) is defined in Equation (14)._  
Proof.: See Appendix F.  
Now, let us assume that the multi-assignment problem linked with the \(N_{1}\times N_{2}\) cost matrix \(C\) possesses a unique optimal assignment matrix, denoted as \(G^{*}\). We have the following theorem:  
**Theorem 4**.: _Let \(\overline{G}_{\beta}\) be the coupling matrix solution of the SPA equations at the inverse temperature \(\beta\). We assume that the multi-assignment problem has a unique solution, with \(G^{*}\) being the associated coupling matrix. If \(\Delta\) is the difference in total cost between the optimal solution and the second-best solution, then_  
\[\max_{i,j}\left|\overline{G}_{\beta}(i,j)-G^{*}(i,j)\right|\leq \frac{A(N_{1},N_{2})}{\beta\Delta}. \tag{17}\]Proof.: See Appendix G.  
This theorem validates that, in the generic case in which the solution to the assignment problem is unique, the converged solution matrix \(\overline{G}_{\infty}\) is this unique solution.