2025/10/29 by De, Koustav
#Computer Science and Game Theory (cs.GT) #F.2.2 #FOS: Computer and information sciences #Multiagent Systems (cs.MA)
paper · doi:10.48550/arxiv.2510.25209
We are given a bipartite graph G = ( A ∪ B, E ). In the one-sided model, every a ∈ A (often called agents) ranks its neighbours z ∈ Na strictly, and no b ∈ B has any preference order over its neighbours y ∈ Nb, and vertices in B abstain from casting their votes to matchings. In the two-sided model with one-sided ties, every a ∈ A ranks its neighbours z ∈ Na strictly, and every b ∈ B puts all of its neighbours into a single large tie, i.e., b ∈ B prefers every y ∈ Nb equally. In this two-sided model with one-sided ties, when two matchings compete in a majority election, b ∈ B abstains from casting its vote for a matching when both the matchings saturate b or both leave b unsaturated; else b prefers the matching where it is saturated. A popular matching M is robust if it remains popular among multiple instances. We have analysed the cases when a robust popular matching exists in the one-sided model where only one agent alters her preference order among the instances, and we have proposed a polynomial-time algorithm to decide if there exists a robust popular matching when instances differ only with respect to the preference orders of a single agent. We give a simple characterisation of popular matchings in the two-sided model with one-sided ties. We show that in the two-sided model with one-sided ties, if the input instances differ only with respect to the preference orders of a single agent, there is a polynomial-time algorithm to decide whether there exists a robust popular matching. We have been able to decide the stable matching problem in bipartite graphs G = (A ∪ B, E) where both sides have weak preferences (ties allowed), with the restriction that every tie has length at most k.