# A General Statistical Physics Framework for Assignment Problems
## Appendix D Monotonicity of \(\mathbf{U_{\beta}^{MF}}\)  
Let  
\[U_{\beta}(\lambda,\mathbf{\mu},x)=\sum_{i,j}C(i,j)\tilde{G}(i,j),\]  
and let the corresponding mean field approximation of the internal energy at the saddle point,  
\[U_{\beta}^{MF}=U_{\beta}\Big{(}\lambda^{MF},\mathbf{\mu}^{MF},x^{MF}\Big{)}.\]  
Before computing \(\frac{dU_{\beta}^{MF}}{d\beta}\), we prove the following property  
**Proposition A1**.: \[U_{\beta}^{MF} = F_{\beta}^{MF}+\beta\frac{dF_{\beta}^{MF}}{d\beta},\] (105)  
_i.e., it extends the well-known relationship between the free energy and the average energy to their mean field counterparts._  
Proof.: The proof of this proposition is virtually identical to the proof of the same results for the assignment problem, found in Appendix C of [15].  
Based on the chain rule,  
\[\frac{dU_{\beta}^{MF}}{d\beta}= \frac{\partial U_{\beta}^{MF}}{\partial\beta}+\sum_{i}\frac{ \partial U_{\beta}^{MF}}{\partial\lambda(i)}\frac{\partial\lambda(i)}{ \partial\beta}+\sum_{j}\frac{\partial U_{\beta}^{MF}}{\partial\mu(j)}\frac{ \partial\mu(j)}{\partial\beta}+\] \[\frac{\partial U_{\beta}^{MF}}{\partial x}\frac{\partial x}{ \partial\beta}.\]  
Using Proposition A1, we find that the partial derivatives of \(U_{\beta}^{MF}\) with respect to \(\lambda\), \(\mu\), and \(x\) are all zeros, and therefore,  
\[\frac{dU_{\beta}^{MF}}{d\beta}= \frac{\partial U_{\beta}^{MF}}{\partial\beta}.\]Using again Proposition A1, we obtain  
\[\frac{dU_{\beta}^{MF}}{d\beta} = \frac{dF_{\beta}^{MF}}{d\beta}+\frac{d}{d\beta}\left(\beta\frac{dF_{ \beta}^{MF}}{d\beta}\right)\] \[= 2\frac{\partial F_{\beta}^{MF}}{\partial\beta}+\beta\frac{ \partial}{\partial\beta}\left(\frac{\partial F_{\beta}^{MF}}{\partial\beta} \right).\]  
Using Equation (A5),  
\[\beta^{2}\frac{dU_{\beta}^{MF}}{d\beta} =\sum_{i}\beta\lambda(i)l^{\prime}(\beta\lambda^{MF}(i),p_{min}(i),p_{max}(i))\] \[+\sum_{j}\beta\mu^{MF}(j)l^{\prime}(\beta\mu^{MF}(j),q_{min}(j),q_ {max}(j))\] \[-\sum_{i,j}\beta y^{MF}(i,j)t^{\prime}(\beta y^{MF}(i,j)),\]  
where \(t(x)\) and \(l(x,a,b)\) are the functions defined above, and \(t^{\prime}(x)\) and \(l^{\prime}(x,a,b)\) are their derivatives with respect to \(x\). Let us define \(r(x)=xt^{\prime}(x)\) and \(s(x,a,b)=xl^{\prime}(x,a,b)\). Then,  
\[\beta^{2}\frac{\partial U_{\beta}^{MF}}{\partial\beta}= \sum_{i}s(\beta\lambda^{MF}(i),p_{min}(i),p_{max}(i))+\] \[\sum_{j}s(\beta\mu^{MF}(j),q_{min}(j),q_{max}(j))-\] \[\sum_{i,j}r(\beta y^{MF}(i,j)).\]  
Note that \(r(x)=\frac{x^{2}e^{x}}{(1+e^{x})^{2}}\). Therefore, \(r(x)\) is positive, bounded below by 0. In Appendix H, we show that \(s(x,a,b)\) is negative, bounded above 0. Therefore,  
\[\frac{dU_{\beta}^{MF}}{d\beta}=\frac{\partial U_{\beta}^{MF}}{\partial\beta} \leq 0,\]  
and the function \(U_{\beta}^{MF}\) is a monotonically decreasing function of \(\beta\).  
Appendix E Proof of Theorem 2: Convergence of the Mean Field Free Energy and the Internal Energy to the Optimal Assignment Cost  
For simplicity in notation, we define \(F^{MF}(\infty)=\lim_{\beta\rightarrow+\infty}F_{\beta}^{MF}\) and \(U^{MF}(\infty)=\lim_{\beta\rightarrow+\infty}U_{\beta}^{MF}\).