On Robust Popular Matchings with Tie-Bounded Preferences and Stable Matchings with Two-Sided Ties

We are given a bipartite graph $G=(A\cup B,E)$. 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 $\mathit{\text{both}}$ sides have weak preferences (ties allowed), with the restriction that every tie has length at most $k$.