Balancing Matching of Two-Sided Agents with Adaptive and Fair Instability

The concept of stable matching is substantially used in bipartite graphs with individual preferences of the vertices. The existence of stability restricts the weight and size of the matching to be satisfactory. We study the trade-offs in stability, weight and cardinality in a one-to-many capacitated weighted bipartite matching with an edge-weight-oriented preference setting. We establish a stability relaxation framework which is adaptive to the pairing suitability and capacity of the vertices. The purpose of the relaxation is to update the stable matching towards the balance of stability, weight and cardinality in the result. The relaxation preserves fairness by keeping the satisfaction degradation of the vertices with the potential new partner in a desired range. We propose an algorithm to produce a new matching using the stability relaxation framework. Furthermore, we define a novel popularity measurement model of matching based on the edge weight with the multi-voting ability of one-sided vertices. We show the resulting matching is also popular as stable matching. The experimentation performed based on the use case of the homeless placement system complements the claim of improving the weight and cardinality in the matching with marginal and fair relaxation of stability.