In this paper, we consider a variant of the classical \textit{Assignment Problem} (AP) where we seek to find a trade-off between fairness and efficiency in the optimal solution. The classical AP can be stated as follows : given a set $n$ workers and a set of $n$ jobs with a $n \times n$ cost matrix representing the assignment of any worker to any job, the classical AP aims as finding an one-to-one worker-job assignment (i.e a bipartite perfect matching) of minimum total cost. In 1984, Martello et al \cite{Martello} introduced the \textit{Balanced Assignment Problem} (BAP) where instead of minimizing the total cost, one minimizes the max-min distance which is the difference between the maximum cost assignment and the minimum one in the optimal solution. Hence, the classical AP focus on efficiency of the solution while the BAP focus on the fairness between the assignments in the solution. Consequently, an optimal solution for AP may be a bad solution with respect to BAP and vice versa. Let us illustrate this by the following $6 \times 6$ cost matrix

\begin{gather*}
C = \begin{bmatrix} 26 & 47 & 46 & 47 & 35 & 13 \\ 25 & 39 & 26 & 48 & 36 & 30 \\ 25 & 28 & 42 & 25 & 10 & 38 \\ 25 & 47 & 41 & 36 & 13 & 48 \\ 19 & 23 & 13 & 43 & 18 & 34 \\ 18 & 28 & 19 & 22 & 19 & 25 \end{bmatrix}
\end{gather*}

Let $i-j$ represent the assignment of worker $i$ to job $j$. In this example, the optimal assignment solutions for AP and BAP are respectively $(1-6, 2-1, 3-2, 4-5, 5-3, 6-4)$ and $(1-5, 2-3, 3-4, 4-1, 5-6, 6-2)$ corresponding to (114,15) and (173,10) as the value of total cost and max-min distance. We can remark that the optimal solution for AP is "50\% less fair" than the optimal solution for BAP. On the other hand, the optimal solution for BAP is "50\% less efficient" than the optimal solution for AP.

Hence, in this paper we propose a fair way based on Nash equilibrium \cite{Kelly}, \cite{Ogryczak}, \cite{Bert} to inject the total cost into the objective function of BAP in order to obtain a better trade-off between efficiency (total cost) and fairness (max-min distance). In particular, we seek to find a solution achieving a Nash equilibrium between two players: the first aims at minimizing the total cost and
the second aims at minimizing the max-min distance. For this purpose, we introduce the \textit{Nash Fairness} (NF) solutions based on the definition of proportional-fair scheduling adapted in the context of AP : a transfer of utilities between the two players is considered to be fair if the percentage increase in the utility of one player is smaller than the percentage decrease in utility of the other player.

Let $P,Q$ represent the total cost and max-min distance in each feasible assignment for AP. Using this definition of proportional-fair scheduling, a feasible solution $(P^{*},Q^{*}) \in S$ be a NF solution if and only if

\begin{equation}
P^{*}Q+Q^{*}P \geq 2P^{*}Q^{*}, \; \forall (P,Q) \in S,
\end{equation}

where $S$ is the set of pairs $(P,Q)$ corresponding to all feasible assignments for AP.

For the above example, we can show that there is an assignment solution as $(1-6, 2-1, 3-4, 4-5, 5-2, 6-3)$ achieving $(P,Q) = (118,12)$ which is a NF solution. The latter offers a better alternative than the optimal solution for BAP $((P,Q) = (173,10))$ with a significant drop (46\%) on the value of total cost and a slight growth (20\%) on the value of max-min distance. Similarly, it is also a better alternative than the optimal solution for AP $((P,Q) = (114,15))$ with 20\% drop on the value of max-min distance and 3.5\% growth on the value of total cost.

We first prove that there always exists a NF solution for AP which is exactly the optimal solution minimizing the product of $P$ and $Q$. However, finding such a solution may be difficult as it requires to minimize a concave function. The main contribution of our paper is to show that finding NF solutions can be done in polynomial time. For that, we focus on extreme NF solutions having either the smallest value of $P$ or the smallest value of $Q$. The algorithm that we propose is a Newton-like iterative algorithm converging to extreme NF solutions in polynomial time. It consists in optimizing a sequence of linear combinations of the two players objective based on Weighted Sum Method \cite{Weighted}. Moreover, this algorithm can be modified for finding all NF solutions including the one minimizing the product of $P$ and $Q$. Computational results on various instances of AP will be presented and commented.