# A General Statistical Physics Framework for Assignment Problems
## Appendix A A Generalized Birkhoff-von Neumann Theorem  
An \(N\times N\) matrix \(A=(a(i,j))\) is said to be doubly stochastic if and only if it satisfies the following conditions,  
\[a(i,j) \geq 0,\] \[\sum\limits_{i=1}^{N}a(i,j) = 1,\quad\sum\limits_{j=1}^{N}a(i,j)=1,\]  
for all \((i,j)\in[1,N]^{2}\). The set \(\Omega_{N}\) of doubly stochastic matrices is a convex polytope whose vertices are the permutation matrices with the same size. This is expressed by the following theorem, established by [17; 18]:  
An \(N\times N\) matrix \(A\) is doubly stochastic if and only if it can be written as a weighted sum of permutation matrices, i.e.,  
\[A=\sum\limits_{\pi\in\Pi_{N}}a_{\pi}\pi,\]  
where \(\Pi_{N}\) is the set of permutation matrices of size \(N\), \(a_{\pi}\) is a positive real number and \(\sum\limits_{\pi\in\Pi_{N}}a_{\pi}=1\). Doubly stochastic matrices and their properties associated with the Birkhoff-von Neumann theorem above proved useful to establish convergence properties of statistical physics frameworks for solving the balanced assignment problem [15; 35]. For the more general assignment problem considered here, however, we need to consider a different but related set of matrices, defined as follows. Let \(N\) and \(M\) be two natural numbers. Let \(R_{min}=(r(1),\ldots,r(N))\), \(R_{max}=(R(1),\ldots,R(N))\), \(C_{min}=(c(1),\ldots,c(M))\), and \(C_{max}=(C(1),\ldots,C(M))\) be four non-negative integral vectors satisfying  
\[\forall i,\quad\ 0\leq r(i)\leq R(i),\] \[\forall j,\quad\ \ 0\leq c(j)\leq C(j).\]Let \(A\) be a non-negative matrix of size \(N\times M\), and let us denote the row sum vector of \(A\) as \(RA\) and the column sum vector of \(A\) as \(CA\). Let us also define \(\sigma(A)\) as the sum of all elements of \(A\), i.e., \(\sigma(A)=\sum_{i=1}^{N}\sum_{j=1}^{M}A(i,j)\). The transportation polytope \(\mathcal{U}(R_{min}^{max},C_{min}^{max})\) is the set of \(N\times M\) matrices \(A\) that satisfy  
\[\forall(i,j),0 \leq A(i,j)\leq 1,\] \[\forall i, r(i) \leq RA(i)\leq R(i),\] \[\forall j, c(j) \leq CA(j)\leq C(j).\]  
The transportation polytope \(\mathcal{U}^{k}(R_{min}^{max},C_{min}^{max})\) is the set of \(N\times M\) matrices \(A\) that satisfy  
\[\mathcal{U}^{k}(R_{min}^{max},C_{min}^{max})=\{A\in\mathcal{U}(R_{min}^{max},C_ {min}^{max})|\quad\sigma(A)=k\}\]  
Denote \(\mathcal{P}(R_{min}^{max},C_{min}^{max})\) as the set of all matrices in \(\mathcal{U}(R_{min}^{max},C_{min}^{max})\) whose entries are either \(0\) or \(1\) with a similar definition for \(\mathcal{P}^{k}(R_{min}^{max},C_{min}^{max})\) with respect to \(\mathcal{U}^{k}(R_{min}^{max},C_{min}^{max})\). Relaved solutions to the general assignment problem considered in this paper belong to \(\mathcal{U}^{k}(P_{min}^{max},Q_{min}^{max})\), while integer solutions belong to \(\mathcal{P}^{k}(P_{min}^{max},Q_{min}^{max})\), where \(P_{min}\), represents the vectors containing the constraints on the number of tasks that can be assigned to an agent or the number of agents that can be assigned to a task. In [PERSON] [36], we show the following theorem:  
**Theorem A2**. : \(\mathcal{U}^{k}(R_{min}^{max},C_{min}^{max})\) _is the convex hull of all matrices in \(\mathcal{P}^{k}(R_{min}^{max},C_{min}^{max})\)._  
Theorem A2 can be stated as any matrix in \(\mathcal{U}^{k}(R_{min}^{max},C_{min}^{max})\) that can be written as a linear combination of matrices in \(\mathcal{P}^{k}(R_{min}^{max},C_{min}^{max})\). This result will be useful for some of the proofs below. **Remark A1**. :
1. _If_ \(R_{min}=R_{max}=1_{N}\)_,_ \(C_{min}=C_{max}=1_{M}\) _(where_ \(1_{N}\) _and_ \(1_{N}\) _are vectors of one of size_ \(N\) _and_ \(M\)_, respectively,_ \(N=M=k\)_,_ \(\mathcal{U}(R_{min}^{max},C_{min}^{max})\) _is the set of doubly stochastic matrices,_ \(\mathcal{P}^{k}(R_{min}^{max},C_{min}^{max})\) _is the set of permutation matrices, and Theorem_ A2 _is then equivalent to the Birkhoff-von Neumann theorem for doubly stochastic matrices_ _[_17; 18_]__._
2.