Characterization and equilibrium of bichromatic max-sum matchings

What the math gives to ML

The paper gives a local-to-global optimality certificate for maximum-weight red-blue matchings: a proposed matching is globally optimal exactly when every directed cycle of partner shifts has nonpositive gain. This turns a permutation-level assignment objective into explicit improving moves that preserve feasibility, and it also provides a falsifiable certificate for approximate matchers. The most transferable neural-network use is to replace or augment greedy or truncated Sinkhorn matching in retrieval, token routing, or bipartite representation alignment with positive-cycle augmentation and a sampled cycle-gain regularizer. The resulting module can improve an approximate assignment at inference time or train score networks to produce permutation matrices with fewer assignment inconsistencies.