Popular matchings: structure and cheating ⋆ strategies Meghana Nasre University of Texas at Austin,USA 3 1 0 Abstract. We consider the cheating strategies for the popular match- 2 ingsproblem.LetG=( ,E)beabipartitegraphwhere denotes A∪P A a set of agents, denotes a set of posts and the edges in E are ranked. n P Each agent ranks a subset of posts in an order of preference, possibly a J 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 num- 5 berofagentsthatpreferM toM′.Consideracentralized marketwhere ] agents submit their preferences and a central authority matches agents S topostsaccordingtothenotionofpopularity.Sinceapopularmatching D need not be unique, we assume that the central authority chooses an . arbitrary popular matching. Let a1 be the sole manipulative agent who s c is aware of thetruepreference lists of all other agents. The goal of a1 is [ to falsify her preference list to get better always, that is, in the falsified instance(i)everypopularmatchingmatchesa1 toapostthatisatleast 1 as good as the most-preferred post that she gets when she was truth- v ful,and(ii)somepopularmatchingmatchesa1 toapostbetterthanthe 2 most-preferredpostpthatshegetswhenshewastruthful,assumingthat 0 9 pisnotoneofa1’s(true)most-preferredposts.Weshowthattheoptimal 0 cheatingstrategyforasingleagenttogetbetter alwayscanbecomputed . inO(m+n)timewhenpreferencelistsareallstrictandinO(√nm)time 1 whenpreferencelistsareallowed tocontainties.Heren= + and 0 |A| |P| m = E . Next, we consider the set of agents, their preference lists and 3 | | the popular matchings algorithm as a non-cooperative game. We show 1 : a necessary and sufficient condition for the true preference lists of the v agents to be an equilibrium of this game when each agent wishes to get i X better always. Tocomputethecheatingstrategies,wedevelopaswitchinggraphcharac- r a terizationofthepopularmatchingsprobleminvolvingties.Theswitching graph characterization was studied for thecase of strict lists byMcDer- mid and Irving (J. Comb. Optim. 2011) and was open for the case of ties.WeshowanO(√nm)algorithmtocomputethesetofpopular pairs usingtheswitchinggraph.Theseresultsareofindependentinterestand answer a part of theopen questionsposed by McDermid and Irving. 1 Introduction We consider the cheating strategies for the popular matchings problem. Let G=( ,E) be a bipartite graphwhere denotes a setofagents, denotes A∪P A P ⋆ This work was supported in part by NSFgrant CCF-0830737. asetofposts,andthe edgesinE areranked.Eachagentranksasubsetofposts in an order of preference, possibly involving ties. This ranking of posts by an agentiscalledthe preferencelistoftheagent.Anagentapreferspostp topost i p if the rankofpost p is smallerthan the rank ofpostp in a’s preference list. j i j An agent a is indifferent between posts p and p if they have the same rank on i j a’spreferencelist.When agentscanbe indifferentbetweenposts,the preference listsaresaidtocontainties,otherwisethepreferencelistsarestrict.Amatching M of G is a subset of edges,no two of which share an end point. For a matched vertex u, let M(u) denote its partner in the matching M. An agent a prefers a matching M to another matching M′ if (i) a is matched in M but unmatched in M′, or (ii) a prefers M(a) to M′(a). Definition 1. A matching M is morepopularthan M′ if the number of agents that prefer M is greater than the number of agents that prefer M′. A matching M is popular if there is no matching M′ that is more popular than M. Thereexistsimpleinstancesthatdonotadmitanypopularmatching–how- ever,whenaninstance admitsa popularmatching,theremaybe morethanone popular matching. Abraham et al. [1] characterized the instances that admit popularmatchingsandgaveefficientalgorithmstocomputeapopularmatching if one exists. Our problem.Consideracentralizedmatchingmarketwhereeachagenta ∈A submits a preference over a subset of posts and a central authority matches agents to posts using the criteria of popularity. Let a1 be the sole manipulative agent who is aware of the true preference lists of all other agents and the pref- erence lists of a a1 remain fixed throughout. The goal of a1 is clear: ∈ A\{ } she wishes to falsify her preference list so as to improve the post that she gets matched to as compared to the post she got when she was truthful. Since there may be more than one popular matching in an instance, we assume that the central authority chooses an arbitrary popular matching. Let G = ( ,E) A∪P denote the instance where ranks on the edges represent true preferences of all the agents. Let H denote the instance obtained by falsifying the preference list of a1 alone. We assume that G admits a popular matching and a1 falsifies in order to create an instance H which also admits a popular matching. Note that itmaybepossiblefora1 tofalsifyherpreferencelistsuchthatH doesnotadmit any popular matching. But we do not consider such a falsification. Agenta1 wishes to falsify her preference listto ensure that (i) everypopular matching in H matches her to a post that is at least as good as the most- preferred post that she gets matched to in G, and (ii) some popular matching in H matches a1 to a post better than the most-preferred post p that she gets matchedto inG,assumingthatp isnota1’s truefirstchoicepost.We termthis strategy of a1 as ‘better always’ strategy. 1.1 Our contributions – Let a1 be the sole manipulative agent who wishes to get better always. The optimal strategy for a1 can be computed in O(m+n) time when preference 2 lists are all strict and in O(√nm) time when preference lists are allowed to contain ties. – Next,considerthesetofagents,theirpreferencelistsandthepopularmatch- ings algorithm as a non-cooperative game. We show a necessary and suffi- cientconditionfor the true preferencelists to be anequilibriumofthe game assuming that every agent wishes to get better always. – Tocomputethecheatingstrategies,wedevelopaswitching graphcharacteri- zationofthepopularmatchingsprobleminvolvingties.Theswitchinggraph characterizationwasstudiedforthecaseofstrictlistsbyMcDermidandIrv- ing[13]andsuchacharacterizationwasnotknownforthecaseofties.Using theswitchinggraph,weshowanO(√nm)timealgorithmtocomputetheset of popular pairs. An edge (a,p) E is a popular pair if there exists a popu- ∈ lar matching M in G such that (a,p) M. We also show that counting the ∈ totalnumberofpopularmatchingsinaninstancewithtiesis#P-Complete. The switchinggraphcharacterizationisofindependentinterestandanswers a part of the open questions in [13]. 1.2 Related work The work in this paper is motivated by the work of Teo et al. [16] where they studythestrategicissuesofthestablemarriageproblem[3].Thestablemarriage problemisageneralizationofourproblemwhereboththesidesofthebipartition (usually referred to as men and women) rank members of the opposite side in order of their preference. Teo et al. [16] study the strategic issues of the stable marriageproblemwherewomenarerequiredtogivecompletepreferencelistsand there is a sole manipulative woman.Further, she is awareof the true preference listsofalltheotherwomen.Teoetal.[16]computeanoptimalcheatingstrategy for a single woman under this model. Huang [5] studies the strategic issues of the stableroom-matesproblem[3]under a similar model.Inthe samespirit,we study the strategic issues of the popular matchings problem. The notion of popular matchings was introduced by G¨ardenfors [4] in the context of the stable marriage [3]. Abraham et al. [1] studied the problem for one-sided preference lists and gave a characterization of instances which admit a popular matching. Subsequent to this result, the popular matchings problem has received a lot of attention [11] [12] [9] [6] [8]. However, to the best of our knowledge none of them is motivated by the strategic issues of the popular matchings problem. 2 Background We first review the following well known properties of maximum matchings in bipartite graphs. Let G = ( ,E) be a bipartite graph and let M be a A ∪ P maximum matching in G. The matching M defines a partition of the vertex set into three disjoint sets: a vertex v is even (resp. odd) if A∪P ∈ A∪P there is an even (resp. odd) length alternating path in G w.r.t. M from an 3 unmatched vertex to v. A vertex v is unreachable if there is no alternating path from an unmatched vertex to v. Denote by , and the sets of even, odd, E O U and unreachablevertices,respectively,in G. The following lemma is well known in matching theory; its proof can be found in [15] or [7]. Lemma 1 ([15] Dulmage Mendelsohn). Let , and be the sets of ver- E O U tices defined by a maximum matching M in G. Then, (a) , and arepairwisedisjoint, andindependentofthemaximummatching E O U M in G. (b) In any maximum matching of G, every vertex in is matched with a vertex O in , and every vertex in is matched with another vertex in . The size E U U of a maximum matching is + /2. |O| |U| (c) No maximum matching of G contains an edge between a vertex in and a O vertex in . Also, G contains no edge between a vertex in and a vertex O∪U E in . E ∪U We now review the characterizationof the popular matchings problem from [1]. As was done in [1], we createa unique last-resortpost ℓ(a) for eachagenta. In this way, we can assume that every agent is matched, since any unmatched agent a can be paired with ℓ(a). For an agent a, let f(a) be the set of rank-1 postsfora.Todefine s(a),letusconsiderthegraphG1 =( ,E1)onrank-1 A∪P edges in G and let M1 be any maximum matching in G1. Let 1, 1, 1 define O E U the partition of vertices with respect to M1 in G1. For any agent a, let A∪P s(a) denote the set of most preferred posts which belong to 1 by the above E partition. Abraham et al. [1] proved the following theorem. Theorem 1 ([1]). A matching M is popular in G iff (1) M E1 is a maximum matching of G1 =( ,E1), and ∩ A∪P (2) for each agent a, M(a) f(a) s(a) . ∈{ ∪ } Thealgorithmforsolvingthepopularmatchingproblemisasfollows:eacha ∈A determines the sets f(a) and s(a). An -complete matching (a matching that A matchesallagents)thatismaximuminG1 andthatmatcheseachatoapostin f(a) s(a) needstobedetermined.Ifnosuchmatchingexists,thenGdoesnot { ∪ } admit a popular matching. Abraham et al. [1] gave an O(√nm) time algorithm to compute a popularmatching in Gwhich is presentedasAlgorithm2.1. Steps 7–11are added by us and will be used to define the switching graphin the next section.Abrahametal.[1]alsoshowedasimplercharacterizationforthepopular matchings in case of strict lists which results in an O(m+n) time algorithm to return a popular matching if one exists. Let G′ = ( ,E′) denote the graph in which every agent a has edges incident to f(Aa)∪Ps(a) . Step 4 of Algorithm 2.1 deletes edges from G′ which { ∪ } cannotbe presentinany maximummatching ofG1. We extend this further and inStep9deleteedgesfromG′ whichcannotbepresentinanypopularmatching inG.Forthis,letuspartitionthevertexset as 2, 2 and 2 withrespect to a popular matching M in G′. Since any pAop∪uPlar mOatchEing MUis a maximum matching in G′, it is easy to see that M cannot containedges of the form 2 2 O O 4 and 2 2 (by Lemma 1(c)). However, note that since M matches every agent, O U it implies that 2 = and 2 = . Thus, there are no 2 2 edges in the graph G′. TAhe∩reEfore, a∅ny edgPe∩(aO,p) de∅leted in Step 9 is of thOe fOorm a 2 ∈O and p 2. We can now make the following claim. ∈U Claim. Let a be an agent such that a 2. Then, in Step 9 of Algorithm 2.1, ∈ U no edge incident ona gets deleted. Let a be an agentsuch that a 1. Then, in ∈E Step 4 of Algorithm 2.1, no edge incident on a gets deleted. Algorithm 2.1O(√nm)-time algorithmforthe popular matchingproblem [1] (Steps 1–6). Input: G=( ,E). 1: ConstructAth∪ePgraph G′ = ( ,E′), where E′ = (a,p) : a and p A∪P { ∈ A ∈ f(a) s(a) . ∪ } 2: Construct the graph G1 =( ,E1) and let M1 be any maximum matching in A∪P G1. 3: Partition as 1, 1, 1 with respect toM1 in G1. 4: RemoveaAny∪edPge inOG′EbetUween a node in 1 and a nodein 1 1. 5: Determinea maximum matching M in G′ bOy augmenting M1O. ∪U 6: ReturnM if it is -complete, otherwise return “no popular matching”. A 7: if G admits a popular matching then 8: Partition as 2, 2, 2 with respect toM in G′. 9: RemoveaAny∪edPge inOG′EbetUween a node in 2 and a nodein 2. 10: Denotetheresulting graph as G′′ =( O,E′′). U A∪P 11: endif Definition 2. Foranagenta,letchoices(a)bethesetofpostspsuchthat(a,p) is an edge in G′′. It is easy to see that for any a , choices(a) f(a) s(a) . Further, if ∈ A ⊆ { ∪ } M is a popular matching in G, then M(a) choices(a). ∈ 3 The switching graph characterization Inthissectionwedeveloptheswitchinggraphforthepopularmatchingsproblem with ties. In case of strict lists, McDermid and Irving [13] defined a switching graph G = ( ,E ) as a directed graph on the posts of G and the edge set M M P E was determined by a popular matching M in G. In fact, a similar graph M was defined even before that by Mahdian [11] (again for strict lists) to study existence of popular matchings in random instances. We use the notation and terminology from [13]. Let G be an instance of the popular matchings problem with ties and let M be a popular matching in G. The switching graph G = ( ,E ) is a directed M M P 5 weighted graph on the posts of G and is defined with respect to a popular matching M in G. The edge Pset E is defined using the pruned graph G′′ = M ( ,E′′) constructed in Step 10 of Algorithm 2.1. There exists an edge from pAt∪oPp (with p = p ) iff for some a , p = M(a) and (a,p ) E′′. The i j i j i j 6 ∈ A ∈ weight of an edge w(M(a),p ) is defined as: j w(M(a),p ) =0 if a is indifferent between M(a) and p j j = 1 if a prefers M(a) to p j − =+1 if a prefers p to M(a). j It is easy to see that the graph G =( ,E ) can be constructed in O(√nm) M M P time using Algorithm 2.1. Consider a vertex p in G . Call p a sink vertex in G if out-degree of p is M M zero in G . The following lemma characterizes sinks in G . M M Lemma 2. A post p is a sink vertex in G if and only if p is unmatched in M. M Let be a maximal weakly connected component of G . Call a sink com- M X X ponent if contains one or more sink vertices otherwise call a non-sink X X component. ForapathT (resp.cycleC)inG ,theweightofthepathw(T)(resp.w(C)) M isthesumoftheweightsontheedgesinT (resp.C).(Wheneverwerefertopaths and cycles in G we imply directed paths and directed cycles respectively.) A M path T = p1,...,pk in GM is calleda switching path if T ends ina sink vertex h i andw(T)=0.Similarly,acycle C = p1,...,pk,p1 inGM is calleda switching h i cycle if w(C) = 0. Let = a : M(p ) = a , for i=1...k and denote by T i i i M′ =M T thematchinAgobta{inedbyapplyingtheswitchingpa}thtoM,thatis, for ai ·T, M′(ai)=pi+1 whereas for a / T, M′(a)=M(a). Similarly, for a ∈A ∈A switching cycle C, define = a :M(p )=a ,for i=1...k and denote by C i i i M′ =M C the matchingAobtai{ned by applying the switching c}ycle to M, that is, for ai · C, M′(ai)=pi+1 mod k whereas for a / C, M′(a)=M(a). ∈A ∈A Example 1. Consider an instance G where = a1,...,a7 and = p1,...,p9 . The A { } P { } preference lists of the agents are shown in Figure 1(a). The preference lists can bereadasfollows:agenta1 rankspostsp1,p2,p3 asherrank-1,rank-2andrank- 3 posts respectively and the two posts p6 and p7 are tied as her rank-4 posts. For every agent a, the posts which are bold denote the set f(a), whereas the postswhichareunderlineddenotethesets(a).TheinstanceGadmitsapopular matching; M and M′ shown below are both popular in G. M = (a1,p6),(a2,p1),(a3,p8),(a4,p2),(a5,p3),(a6,p9),(a7,p4) (1) { } ′ M = (a1,p6),(a2,p1),(a3,p8),(a4,p2),(a5,p4),(a6,p3),(a7,p5) (2) { } Figure1(b)showstheswitchinggraphG withrespecttothepopularmatching M M.We note thatthe edges(a4,p3)and(a1,p1)getdeletedinStep 4andStep9 6 of Algorithm 2.1, respectively. Hence the switching graph G does not have M the edges (M(a4) = p2,p3) and (M(a1) = p6,p1) respectively. Consider the switchingpathT = p9,p3,p4,p5 inGM.ByapplyingT toM wegetM′ =M T h i · (see Equation (2)) which is also popular in G. a1 : p1 p2 p3 (p6,p7) p1 a2 : p1 p2 p8 +1 1 p3 −1 p4 − a3 : p1 p8 +1 0 a4 : (p2,p3) p1 p8 p8 1 a5 : p3 (p2,p4) − p9 p5 a6 : p3 p9 p1 p2 a7 : (p4,p5) p1 0 p6 p7 (a) (b) Fig.1. (a) Preference lists of agents a1,...,a7 . The posts which are bold denote { } f(a) and the posts which are underlined denote s(a). (b) Switching graph G with M respect to thepopular matching M in G. 3.1 Some useful properties In this section we prove some useful properties of the switching graph G . M Recall that the vertices are partitioned as 1, 1, 1 w.r.t. a maximum A∪P O E U matching M1 in G1 (see Step 3 of Algorithm 2.1). Further, the vertices are partitioned as 2, 2, 2 w.r.t. a popular matching M in G′ (see SteAp ∪8 oPf O E U Algorithm 2.1). Property 1. All sink vertices of GM belong to the set 1. E Proof. Assume for the sake of contradiction that p is a sink vertex in G and M p 1 1. Recall that the sink vertices of GM are unmatched posts in the ∈ O ∪U popular matching M in G. Since M is a popular matching, it implies that M is amaximummatchingonrank-1edgesinG.However,everymaximummatching on rank-1 edges of G matches every vertex in 1 1. Thus, if p is unmatched O ∪U in M andp 1 1, it implies that M is not a maximum matching on rank-1 ∈O ∪U edges of G, a contradiction. Property 2. Every post p belonging to a sink component has a path to a sink and hence belongs to the set 2. Everypost belonging to a non-sink component E belongs to the set 2. U Proof. We prove that a post p belongs to a sink component of GM iff p 2. ∈ E Let p be a post such that p 2. Then p is either unmatched in M or p has ∈ E 7 anevenlengthalternatingpathstartingatanunmatchedvertexp′ withrespect to M in G′. If p is unmatched, then p is a sink vertex in G and hence we M are done. Else let p= p1,a1,...,pk,ak,pk+1 =p′ denote the alternating path h i and for every 1 i k, we have M(p ) = a . Note that every unmatched i i ≤ ≤ edge (ai,pi+1) is of the form 2 2 and hence none of these unmatched edges O E get deleted in Step 9 of Algorithm 2.1. Therefore, it is easy to see that the path p = p1,p2,...,pk+1 = p′ is present in GM and hence p belongs to the sink chomponent that contains pi′. To prove the other direction let be a sink component in G and let p be M X somevertexin .Ifp 2,itiseasytoseethatphasapathtosomesinkvertex X ∈E in andwearedone,elsep 2.Recallthat 2 = .Sincepbelongsto , theXre exists somevertexp′ in∈Usuchthatp′ O2∩anPdp′∅has apath to p inGMX. Let p′ =p1,p2,...,pk =p deXnoteapathof∈mEinimallength.Notethatforeach h i 1 i k, p is matched in M and let M(p ) = a . By the minimality of the i i i ≤ ≤ path, we know that for 2 i k, pi 2. However, p1 2 implies a1 2. ≤ ≤ ∈ U ∈ E ∈ O Thus the presence of edge (p1,p2) in GM implies that there is a 2 2 edge in the graphG′′ whichshouldhavebeendeleted bystep9 ofAlgorithOmU2.1.Hence such an edge cannot be present in GM contradicting the fact that p 2. This ∈U implies that every vertex contained in a sink component of G has a path to M some sink in the component. The above proof immediately implies that a post p belongs to a non-sink component iff p 2. This finishes the proof of Property 2. ∈U Property 3. For an edge (p ,p ) in G , the weight w(p ,p ) is determined by i j M i j which partition pi and pj belong to when vertices are partitioned as 1, 1, 1. O E U w(p ,p ) can be determined using Table 1. i j ❅p j pi❅❅ O1 E1 U1 1 0 1 O − × 1 +1 0 E × 1 1 0 U × − Table1.Tableshowsw(p ,p )foranedge(p ,p )inG .Theweightisdeterminedby i j i j M the partition of vertices as 1, 1, 1. The denotes that such an edge is not present O E U × in G . M Proof. To prove Property 3 we justify the entries in Table 1. Let (p ,p ) be an i j edge in G and let M(p ) = a. The weight on the edge (p ,p ) is determined M i i j by the relative ranks of p and p in a’s preference list. We note that a post i j p 1 1 has only rank-1 edges incident on it in the graph G′. Hence if ∈ O ∪ U pi 1 1, then a treats pi as her rank-1 post. ∈O ∪U – pi 1:atreatspi asherrank-1postandsincepostsin 1 remainmatched ∈O O along agents in 1, it implies that a 1. E ∈E 8 pj 1: a treats pj as her rank-1 post, thus, w(pi,pj)=0. • ∈O pj 1: We show that a treats pj as her non-rank-1 post and hence • ∈ E w(p ,p )= 1. Assume for the sake of contradiction that a treats p as i j j − a rank-1 post. It implies that there is a 1 1 edge in the graph G1, a E E contradiction (by part (c) Lemma 1). pj 1: We show that such an edge cannot exist in GM. Recall that • ∈ U posts in 1 have only rank-1 edges incident on them, hence a treats U pj as her rank-1 post. This implies that there is a 1 1 edge in G1 a E U contradiction (by part (c) of Lemma 1). – pi 1: Here we consider two cases: ∈E (i) a treats p as her rank-1 post: In this case, we note that s(a) f(a) and i hence a has only rank-1 edges incident on it in the graph G′ an⊆d all these edges are incident on posts which belong to 1. Thus the only case possible E is, pj 1 and w(pi,pj)=0. ∈E (ii) a treats pi as her non-rank-1 post: We first note that a 1 because ∈ E agentsin 1 1remainmatchedalongrank-1edgesineverypopularmatch- O ∪U ing. Consider the three different cases for p . j pj 1: a treats pj as her rank-1 post and hence w(pi,pj)=+1. • ∈O pj 1: We show that a treats pj as her non-rank-1 post and hence • ∈ E w(p ,p ) = 0. Assume for the sake of contradiction that a treats p as i j j her rank-1 post. Then there exists an 1 1 edge in G1 a contradiction E E (by part (c) of Lemma 1). pj 1: We show that such an edge cannot exist in GM. If such an • ∈ U edge exists there is an 1 1 edge in G1 a contradiction (by part (c) of E U Lemma 1). – pi 1: a treatspi asherrank-1postandsince postsin 1 remainmatched ∈U U along agents in 1, it implies that a 1. U ∈U pj 1:atreatspj asherrank-1posthoweversuchanedgegetsdeleted • ∈O as an 1 1 edge in Step 4 of Algorithm 2.1. Thus such an edge cannot O U be present in G . M pj 1: We show that a treats pj as her non-rank-1 edge and hence • ∈ E w(p ,p )= 1. Assume for the sake of contradiction that a treats p as i j j − a rank-1post then, it implies that there is a 1 1 edge in the graphG1, U E a contradiction (by part (c) of Lemma 1). pj 1: a treats pj as her rank-1 post and therefore w(pi,pj)=0. • ∈U Property 4. Every path T in G has w(T) 1,0,+1 . Every cycle C in M ∈ {− } G has w(C) = 0. There exists no path T in G ending in a sink vertex with M M w(T)=+1. Proof. It is easy to observe that if the edges have weights according to Table 1, then everypathinG hasweightbelongingto 1,0,+1 .Further everycycle M {− } has to have weight 0. It remains to argue that in G there exists no path T M of weight +1 which ends in a sink. For contradiction, assume that such a path exists in G and consider applying the path T to M to obtain the matching M M′ = M T. The number of agents that prefer M′ to M is exactly one more than the n·umber of agents that prefer M to M′. Thus M′ is more popular than M, contradicting the fact that M was a popular matching. 9 Property 5. Foranyswitching pathT (orswitchingcycle C)inG ,the match- M ing M′ =M T (M′ =M C resp.) is a popular matching in G. Every popular matching M′· in G can be· obtained from M by applying to M one or more vertex disjoint switching paths and switching cycles in each of a subset of sink componentsofG togetherwithoneormorevertexdisjointswitchingcyclesin M each of a subset of the non-sink components of G . M Proof. Let T = p1,p2,...,pk be a switching path in GM with pk unmatched in M and M′ =h M T denoite the matching obtained by applying the path T to M. Let = ·k−1 M(p ) = a . We observe that for every a , M′(a ) f(aAT) s(∪ai=)1{becauise edgie}s of G are derived from a suib∈seAt Tof i i i M graph G∈′ ={ ( ∪ ,E′)}(refer to Algorithm 2.1). Further for any a / , T M′(a) = M(aA).∪FiPnally note that since w(T) = 0, for every agent th∈atAgot demoted from her rank-1 post there exists a unique agent who got promoted to her rank-1post in M′. Thus, M′ is a maximum matching on rank-1edges of G. It is therefore clear that M′ satisfies both the properties defined by Theorem 1 and hence M′ is a popular matching in G. An exactly similar argument proves that for any switching cycle C, M C is also a popular matching in G. LetM′ beanypopularmatchin·ginG.ConsiderM M′,thisissetofvertex ⊕ disjointevenlengthpathsandevenlengthcyclesinG.LetTG = p1,a1,...,pk,ak,pk+1 beanyevenlengthpathinM M′withpk+1unmatchedinM anhdp1unmatched i in M′. For every 1 i k,⊕let M(p ) = a . Note that every unmatched edge i i ≤ ≤ (ai,pi+1) is of the form 2 2 and hence none of these unmatched edges get O E deleted in Step 9 of Algorithm 2.1. Therefore, it is easy to see that the path p = p1,p2,...,pk+1 = p′ is present in GM and it ends in a sink. Note that h i w(T) cannotbe strictly positivesince M is a popularmatching.Similarly, w(T) cannot be strictly negative. This is because since both M and M′ are popular, w(T) 1impliesthatthereexistsanotherpathT′ (oracycleC′ )inM M′, whose≤co−rresponding path T′ (resp. cycle C′) in thGe graph G hGas a po⊕sitive M weight. However, this again contradicts the fact that M is a popular matching. Thus, the path T has weight 0 and ends in a sink and hence is a switching path.AsimilarargumentshowsthateverycycleinM M′ hasacorresponding ⊕ switchingcycleinG .ApplyingtheseswitchingpathsandcyclestoM givesus M the desired matching M′, thus completing the proof. Recall the definition of choices(a) for an agent as given by Definition 2. We now define the notion of a tight-pair , that is, a set of agents 1 and a set of A posts 1 with 1 = 1 . Further, for every a 1 we have choices(a) 1. P |A | |P | ∈ A ⊆ P We show that a tight-pair exists whenever there is a non-sink component in the switching graph G . M Lemma 3. Let be a non-sink component in G and q . Let, M Y ∈Y =q p: q has a path to p in G q M P ∪{ } Then there exists a set of agents such that (i) = , and (ii) for every q q q A |A | |P | a , choices(a) . q q ∈A ⊆P 10