# A General Statistical Physics Framework for Assignment Problems
## 2 A General Formulation of the Assignment Problem
### Optimizing the Effective Free Energy  
Let \(\overline{G}(i,j)\), \(\overline{n}_{1}(i)\), and \(\overline{n}_{2}(j)\) represent the expected values of \(G(i,j)\), \(n_{1}(i)\), and \(n_{2}(j)\), respectively, in accordance with the Gibbs distribution specified in Equation (4). Computing these expected values directly is unfortunately not feasible as the partition function defined in Equation (8) lacks an analytical expression. Instead, we derive a saddle point approximation (SPA) by seeking extrema of the effective free energy with respect to the variables \(\lambda\), \(\mu\), and \(x\):  
\[\frac{\partial F_{\beta}(\lambda,\mathbf{\mu},x)}{\partial\lambda_{i}}=\frac{ \partial F_{\beta}(\lambda,\mathbf{\mu},x)}{\partial\mu_{j}}=\frac{\partial F_{ \beta}(\lambda,\mathbf{\mu},x)}{\partial x}=0. \tag{9}\]  
After some rearrangements, these two equations can be written as  
\[\forall i,\ \sum_{j}X(i,j)=d_{1}(i), \tag{10a}\] \[\forall j,\ \sum_{i}X(i,j)=d_{2}(j),\] (10b) \[\sum_{i,j}X(i,j)=k, \tag{10c}\]  
where  
\[X(i,j) = h[\beta(\mathcal{C}(k,l)+\delta\lambda(i)+\delta\mu(j)+\delta x ),]\] \[d_{1}(i) = g(\beta\beta\lambda(i),p_{min}(i),p_{max}(i)),\] \[d_{2}(j) = g(\beta\beta\mu(j),q_{min}(j),q_{max}(j)), \tag{11}\]  
and  
\[h(x)= \frac{1}{e^{x}+1},\] \[g(x,a,b)= \frac{(b-a+1)}{e^{(b-a+1)x}-1}+\frac{1}{1-e^{x}}+b.\]  
Note that  
1. \(g(x,a,a)=a\). If \(a=1\) and \(N_{1}=N_{2}=1\), we recover Equation (11) from [16] corresponding to the balanced assignment problem. 2. \(g(x,0,1)=h(-x)\). In this case, Equation (11) refers to the \(k\)-cardinality problem. As frequently encountered, the saddle point may be purely imaginary. In this instance, it is evident from Equations (10) and (11) that the variables \(\delta\lambda(i)\), \(\delta\mu(j)\), and \(\delta x\) must be real. Consequently, we will replace \(\{\delta\lambda(i),\delta\mu(j),\delta x\}\) by \(\{\lambda(i),\mu(j),x\}\) below. In order to analyze the saddle point approximation, SPA, it is necessary to verify the existence and evaluate the uniqueness of the extrema of the effective free energy. The following theorem proves that \(F_{\beta}(\lambda,\mathbf{\mu},x)\) is strictly concave. Theorem 1: _The Hessian of the effective free energy \(F_{\beta}(\lambda,\mathbf{\mu},x)\) is negative definite if \(p_{min}(i)<p_{max}(i)\) for all \(i\) and \(q_{min}(j)<q_{max}(j)\), for all \(j\), and negative semidefinite otherwise. The free energy function \(F_{\beta}(\lambda,\mathbf{\mu},x)\) is then strictly concave in the first case and concave in the second case._  
Proof: See Appendix B. The following property establishes a relationship between the solutions of the SPA system of equations and the expected values for the assignment matrix and for the indicator functions:  
**Proposition 1**. : _Let \(\overline{S}_{\beta}\) be the expected state of the system at the temperature \(\beta\) with respect to the Gibbs distribution given in Equation (4). \(\overline{S}_{\beta}\) is associated with an expected transportation plan \(\overline{G}_{\beta}\) and expected indicator functions \(\overline{n}_{1\beta}\) and \(\overline{n}_{2\beta}\). Let \(\lambda^{\text{MF}}(i)\), \(\mu^{\text{MF}}(j)\), and \(x^{\text{MF}}\) be the solutions of the system of Equation (10). Then the following identities hold:_  
\[ \begin{array}{rcl}\overline{G}_{\beta}(i,j)&=&h(\beta(C(i,j)+\lambda^{MF}(i) +\mu^{\text{MF}}(j)+x^{\text{MF}}))\\ &=&X^{\text{MF}}(k,l)\\ \overline{n}_{1\beta}(i)&=&g(\beta\lambda^{\text{MF}}(i),p_{min}(i),p_{max}(i) )=d_{1}^{\text{MF}}(i)\\ \overline{n}_{2\beta}(j)&=&g(\beta\mu^{\text{MF}}(j),q_{min}(j),q_{max}(j))=d_ {2}^{\text{MF}}(j).\end{array}  \tag{12}\]  
_To indicate that the solutions are mean field solutions, we use the superscript \(\text{MF}\)._  
Proof. : The proof of this proposition is virtually identical to the proof of the same results for the assignment problem, found in Appendix B of [15].