We study the problem of assigning jobs to applicants. Each applicant has a weight and provides a preference list ranking a subset of the jobs. A matching M is popular if there is no other matching M' such that the weight of the applicants who prefer M' over M exceeds the weight of those who prefer M over M'. This paper gives efficient algorithms to find a popular matching if one exists.
Following the publication of the work of Abraham al @cite_11 , the topic of unweighted popular matchings has been further explored in many interesting directions. Suppose we want to go from an arbitrary matching to some popular matching by a sequence of matchings each more popular than the previous; Abraham and Kavitha @cite_0 showed that there is always a sequence of length at most two and gave a linear time algorithm to find it. One of the main drawbacks of popular matchings is that they may not always exist; Mahdian @cite_10 nicely addressed this issue by showing that the probability that a random instance admits a popular matching depends on the ratio @math , and exhibits a phase transition around @math . Motivated by a house allocation application, Manlove and Sng @cite_1 gave fast algorithms for popular assignments with capacities on the jobs.
@cite_0 @cite_1 @cite_10 @cite_11
2471400471 1564148014 2040117841
We consider a matching market, in which the aim is to maintain a popular matching between a set of applicants and a set of posts, where each applicant has a preference list that ranks some subset of acceptable posts. The setting is dynamic: applicants and posts can enter and leave the market, and applicants can also change their preferences arbitrarily. After any change, the current matching may no longer be popular, in which case, we are required to update it. However, our model demands that we can switch from one matching to another only if there is consensus among the applicants to agree to the switch. Hence, we need to update via a voting path, which is a sequence of matchings, each more popular than its predecessor, that ends in a popular matching. In this paper, we show that, as long as some popular matching exists, there is a 2-step voting path from any given matching to some popular matching. Furthermore, given any popular matching, we show how to find a shortest-length such voting path in linear time. We consider the problem of finding a popular matching in the Capacitated House Allocation problem (CHA). An instance of CHA involves a set of agents and a set of houses. Each agent has a preference list in which a subset of houses are ranked in strict order, and each house may be matched to a number of agents that must not exceed its capacity. A matching M is popular if there is no other matching M' such that the number of agents who prefer their allocation in M' to that in M exceeds the number of agents who prefer their allocation in M to that in M'. Here, we give an O(√Cn1+m)algorithm to determine if an instance of CHA admits a popular matching, and if so, to find a largest such matching, where C is the total capacity of the houses, n1 is the number of agents and m is the total length of the agents' preference lists. For the case where preference lists may contain ties, we give an O(√Cn1)+m) algorithm for the analogous problem. We consider matching markets where a centralized authority must find a matching between the agents on one side of the market, and the items on the other side. Such settings occur, for example, in mail-based DVD rental services such as NetFlix or in some job markets. The objective is to find a popular matching, or a matching that is preferred by a majority of the agents to any other matching. This concept was first defined and studied by The main drawback of this concept is that popular matchings sometimes do not exist. We partially address this issue in this paper, by proving that in a probabilistic setting where preference lists are drawn at random and the number of items is more than the number of agents by a small multiplicative factor, popular matchings almost surely exist. More precisely, we prove that there is a threshold α ≈ 1.42 such that if the number of items divided by the number of agents exceeds this threshold, then a solution almost always exists. Our proof uses a characterization result by , and a number of tools from the theory of random graphs and phase transitions.