{"ID":2848414,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.25209","arxiv_id":"2510.25209","title":"On Robust Popular Matchings with Tie-Bounded Preferences and Stable Matchings with Two-Sided Ties","abstract":"We are given a bipartite graph $G = \\left( A \\cup B, E \\right)$. In the one-sided model, every $a \\in A$ (often called agents) ranks its neighbours $z \\in N_{a}$ strictly, and no $b \\in B$ has any preference order over its neighbours $y \\in N_{b}$, and vertices in $B$ abstain from casting their votes to matchings. In the two-sided model with one-sided ties, every $a \\in A$ ranks its neighbours $z \\in N_{a}$ strictly, and every $b \\in B$ puts all of its neighbours into a single large tie, i.e., $b \\in B$ prefers every $y \\in N_{b}$ equally. In this two-sided model with one-sided ties, when two matchings compete in a majority election, $b \\in 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 \\emph{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 \\cup B, E)$ where \\textit{both} sides have weak preferences (ties allowed), with the restriction that every tie has length at most $k$.","short_abstract":"We are given a bipartite graph $G = \\left( A \\cup B, E \\right)$. In the one-sided model, every $a \\in A$ (often called agents) ranks its neighbours $z \\in N_{a}$ strictly, and no $b \\in B$ has any preference order over its neighbours $y \\in N_{b}$, and vertices in $B$ abstain from casting their votes to matchings. In t...","url_abs":"https://arxiv.org/abs/2510.25209","url_pdf":"https://arxiv.org/pdf/2510.25209v1","authors":"[\"Koustav De\"]","published":"2025-10-29T06:20:21Z","proceeding":"cs.GT","tasks":"[\"cs.GT\",\"cs.MA\"]","methods":"[]","has_code":false}