On Robust Popular Matchings with Tie-Bounded Preferences and Stable Matchings with Two-Sided Ties
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908618900635648 |
|---|---|
| author | De, Koustav |
| author_facet | De, Koustav |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_25209 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Robust Popular Matchings with Tie-Bounded Preferences and Stable Matchings with Two-Sided Ties De, Koustav Computer Science and Game Theory Multiagent Systems F.2.2 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$. |
| title | On Robust Popular Matchings with Tie-Bounded Preferences and Stable Matchings with Two-Sided Ties |
| topic | Computer Science and Game Theory Multiagent Systems F.2.2 |
| url | https://arxiv.org/abs/2510.25209 |