I'm thinking about the assignment problem for assigning $I$ workers to $I$ tasks (let $I=J$ so there are the same number). Suppose that each possible assignment yields a payoff of $u_{ij}$. I want to find the assignments that maximize the total payoffs (the sum of the $u_{ij}$s).
\begin{array}{cccc} & \text{Task 1} & \text{...} & \text{Task J} \\ \text{Worker 1} & u_{1,1} & ...& u_{1,J}\\ \text{...} & ... & ... & ... \\ \text{Worker I} & u_{I,1} &... & u_{I,J} \end{array}
Here is my question. Suppose we focus on one particular $u_{ij}$, leaving all of the others equal. I can find cases where increasing $u_{ij}$ to $u'_{ij}$ ($u'_{ij}>u_{ij}$) makes $i,j$ pair go *from excluded (original) to included (increased) * in the final Hungarian match.
I can also find cases where increasing it would not change the final Hungarian match. However, I can't think of any cases where increasing $u_{ij}$ would make $i,j$ go from included (original) to excluded (increased) in the final match.
Am I missing anything? I'm basically seeking a monotonicity property. I think that whether the Hungarian includes $i,j$ is weakly increasing in the value of $u_{ij}$.
Note: The Hungarian algorithm is sometimes framed in terms of cost-minimization, rather than value-maximization. The same question can be asked in reverse: Does decreasing the cost of $i,j$ weakly increase whether $i$ is assigned to $j$?
I think it is, but I wish there were a proof I could point to. Maybe someone knows in the literature.
Let $x_{i,j}\in \lbrace 0, 1\rbrace$ be the variable deciding whether the $i\rightarrow j$ assignment is made (1) or not (0), and let $X\subseteq \lbrace 0, 1\rbrace ^{n \times n}$ be the set of feasible solutions. Solve the model with the original payoff coefficients, obtaining an optimal solution $x^*.$ Optimality means that $$\sum_{i,j} u_{i,j} x^*_{i,j} \ge \sum_{i,j} u_{i,j} x_{i,j} \quad \forall x\in X \quad (1).$$
Now suppose that $x^*_{i_0,j_0}=1$ and you add $\delta > 0$ to $u_{i_0,j_0}.$ The left side of (1) increases by $\delta,$ the right side increases by $\delta x_{i_0,j_0} \le \delta,$ and so the inequality is preserved, meaning $x^*$ still has a payoff at least as large as that of any other feasible solution.