Popular Matchings: Structure and Strategic Issues

Source abstract

We consider the strategic issues of the popular matchings problem. Let $G = (\mathcal{A} \cup \mathcal{P}, E)$ be a bipartite graph, where $\mathcal{A}$ denotes a set of agents, $\mathcal{P}$ denotes a set of posts, and the edges in $E$ are ranked. Each agent ranks a subset of posts in an order of preference, possibly involving ties. A matching $M$ is popular if there exists no matching $M'$ such that the number of agents that prefer $M'$ to $M$ exceeds the number of agents that prefer $M$ to $M'$. Consider a centralized market where agents submit their preferences and a central authority matches agents to posts according to the notion of popularity. Since a popular matching need not be unique, we assume that the central authority chooses an arbitrary popular matching. Let $a_1$ be the sole manipulative agent who is aware of the true preference lists of all other agents. The goal of $a_1$ is to falsify her preference list to get better always, that is, in the falsified instance (i) every popular matching matches $a_1$ to a post that is at least as good as the most preferred post that she gets when she was truthful, and (ii) some popular matching matches $a_1$ to a post better than the most preferred post $p$ that she gets when she was truthful, assuming that $p$ is not one of $a_1$'s (true) most preferred posts. We show that the optimal cheating strategy for a manipulative agent to get better always can be computed in $O(m+n)$ time when preference lists are all strict and in $O(\sqrt{n}m)$ time when preference lists are allowed to contain ties. Here $n = |\mathcal{A}| + |\mathcal{P}|$ and $m = |E|$. To compute the cheating strategies, we develop a switching graph characterization of the popular matchings problem involving ties. The switching graph characterization was studied for the case of strict lists by McDermid and Irving [J. Comb. Optim., 22 (2011), pp. 339--358] and was open for the case of ties. We show an $O(\sqrt{n}m)$ time algorithm to compute the set of popular pairs using the switching graph. These results are of independent interest and answer a part of the open questions posed by McDermid and Irving.