Manipulation Strategies for the Rank Maximal Matching Problem
Pratik Ghosal and Katarzyna Paluch

arXiv:1710.11462v1 [cs.DS] 31 Oct 2017

University of Wroclaw

Abstract. We consider manipulation strategies for the rank-maximal matching problem. In the rank-maximal
matching problem we are given a bipartite graph G = (A ∪ P, E) such that A denotes a set of applicants and
P a set of posts. Each applicant a ∈ A has a preference list over the set of his neighbors in G, possibly involving
ties. Preference lists are represented by ranks on the edges - an edge (a, p) has rank i, denoted as rank(a, p) = i, if
post p belongs to one of a’s i-th choices. Posts most preferred by an applicant a have rank one in his preference list.
A matching M is any subset of edges E such that no two edges of M share an endpoint. A rank-maximal matching
is one in which the maximum number of applicants is matched to their rank one posts and subject to this condition,
the maximum number of √
applicants is matched to their rank two posts, and so on. A rank-maximal matching can
be computed in O(min(c n, n)m) time, where n denotes the number of applicants, m the number of edges and c
the maximum rank of an edge in an optimal solution [1].
A central authority matches applicants to posts. It does so using one of the rank-maximal matchings. Since there
may be more than one rank- maximal matching of G, we assume that the central authority may choose any one of
them or that the rank-maximal matching is chosen randomly. Let a1 be a manipulative applicant, who knows the
preference lists of all the other applicants and wants to falsify his preference list so that he has a chance of getting
better posts than if he were truthful, i.e., than if he gave a true preference list. We can always assume that a1 does
not get his most preferred post in every rank maximal matching when he is truthful, otherwise a1 does not have any
incentive to cheat. In the first problem addressed in this paper the manipulative applicant a1 wants to ensure that
he is never matched to any post worse than the most preferred among those of rank greater than one and obtainable
when he is truthful. In the second problem the manipulator wants to construct such a preference list that the worst
post he can become matched to by the central authority is best possible or in other words, a1 wants to minimize the
maximal rank of a post he can become matched to.

1 Introduction
We consider manipulation strategies for the rank-maximal matching problem. In the rank-maximal matching problem
we are given a bipartite graph G = (A ∪ P, E) such that A denotes a set of applicants and P a set of posts. Each
applicant a ∈ A has a preference list over the set of his neighbors in G, possibly involving ties. Preference lists are
represented by ranks on the edges - an edge (a, p) has rank i, denoted as rank(a, p) = i, if post p belongs to one of
a’s i-th choices. An applicant a prefers a post p to a post p′ if rank(a, p) < rank(a, p′ ). In this case we say that (a, p)
has smaller or higher rank than (a, p′ ). If a is indifferent between p and p′ , then rank(a, p) = rank(a, p′ ). Posts most
preferred by an applicant a have rank one in his preference list. A matching M is any subset of edges E such that no
two edges of M share an endpoint. A rank-maximal matching is one in which the maximum number of applicants is
matched to their rank one posts and subject to this condition, the maximum number√of applicants is matched to their
rank two posts, and so on. A rank-maximal matching can be computed in O(min(c n, n)m) time, where n denotes
the number of applicants, m the number of edges and c the maximum rank of an edge in an optimal solution [1].
A central authority matches applicants to posts. It does so using one of the rank-maximal matchings. Since there
may be more than one rank- maximal matching of G, we assume that the central authority may choose any one of them
or that the rank-maximal matching is chosen randomly. Let a1 be a manipulative applicant, who knows the preference
lists of all the other applicants and wants to falsify his preference list so that he has a chance of getting better posts
than if he were truthful, i.e., than if he gave a true preference list. We can always assume that a1 does not get his most
preferred post in every rank maximal matching when he is truthful, otherwise a1 does not have any incentive to cheat.
In the first problem addressed in this paper the manipulative applicant a1 wants to ensure that he is never matched to
any post worse than the most preferred among those of rank greater than one and obtainable when he is truthful. In the
second problem the manipulator wants to construct such a preference list that the worst post he can become matched
to by the central authority is best possible or in other words, a1 wants to minimize the maximal rank of a post he can
become matched to.
More formally, the manipulation strategies of the applicant a1 are described as follows. Let Z(G) = {p1 , p2 , . . . , pk }
denote the sets of posts a1 may become matched to in the instance G, i.e., a post pi belongs to Z(G) if and only

2

Pratik Ghosal and Katarzyna Paluch

if there exists a rank-maximal matching M of G such that a1 is matched to pi in M . By max(Z(G)) we denote
max{rank(pi ) : pi ∈ Z(G)}. In a similar way, we define min(Z(G)) = min{rank(pi ) : pi ∈ Z(G) ∩ rank(pi ) >
i}. The set H of graphs consists of graphs each of which differs from G only in that a1 may have a different set of
neighbors contained in P and a different preference list over this set. Thus H denotes the set of all instances, in which
the applicant a may have a different preference list than in the instance G.
First, we can notice that it is usually advantageous for a1 to truncate his preference list. Let Hp denote the graph,
in which a’s preference list consists of only one post p. Then as long as no rank-maximal matching of Hp leaves a1
unmatched, he is guaranteed to always get the post p. This provides a1 with a method to ensure that he always gets
his most preferred post. To prevent such procedures we require that a1 and generally each applicant is required to give
a full preference list that includes every post from P . Therefore, we assume that every H ∈ H represents a graph, in
which a1 has a full preference list. Also, a1 could make the posts he does not want to be matched to appear very far in
his preference list. Thus we assume that a1 does not have any gaps in his preference list in every H ∈ H, i.e., it cannot
happen that in a1 ’s preference list there are a rank i and rank (i + 2) posts but none of rank (i + 1).
By a strategy termed ‘best nonfirst’(section 3) we denote any graph H ∈ H such that every rank-maximal matching
of H matches a1 to a post most preferred among those of rank greater than one and obtainable when he is truthful.
Such posts are the most preferred non-f -posts of a1 in G. (An f -post is defined in Section 3). And by a strategy termed
‘min max’ we denote any graph H ∈ H such that every rank-maximal matching of H matches a1 to a post having
rank equal to min{max(Z(H)) : H ∈ H}. Our algorithm of ‘min max’ strategy matches a1 to a particular post p in
rank maximal matching of H. We also show that the output of any optimal ‘min max’ strategy also matches a1 to that
same post p in every rank maximal matching.
Previous and related work. The rank-maximal matching problem belongs to the class of matching problems
under preferences. In the problems with one-sided preferences the considered graph is bipartite and each vertex of
only one set of the bipartition expresses preferences over the set of its neighbors. Apart from rank-maximal matchings
other types of matchings from this class include matchings that are pareto-optimal [2][3] [4], popular [5] or fair[6]
among others. In the problems with two-sided preferences the underlying graph does not have to be bipartite and each
vertex from the graph ranks all of its neighbors. Thus every edge is assigned two ranks by each of its endpoints. The
most famous example of a matching problem under two-sided preferences is that of a stable matching known also as
the stable marriage problem. Since the seminal paper by Gale and Shapley [7] it has been studied very intensively,
among others in [8], [9], [10], [11],[12].
The rank-maximal matching problem was introduced by Irving in [13]. A rank-maximal matching can be found via
a relatively
straightforward reduction to a maximum weight matching. The running time of the resulting algorithm is
√
O(r2 nm log n), where r denotes the maximal value of a rank, if we use the Gabow-Tarjan algorithm, or O(rn(m +
n log n)) for√the Fredman-Tarjan algorithm. The already mentioned [1] gives a combinatorial algorithm that runs in
O(min(n, c n)m) time. The capacitated and weighted versions were considered, respectively, in [14] and [15]. A
switching graph characterization of the set of all rank-maximal matchings is described in [16]. The dynamic version
of the rank-maximal matching problem was considered in [17] and [18]. Nimbhorkar et al. gave an O(r(n + m))
algorithm for updating a rank-maximal matching after the addition or deletion of a vertex or edge and Ghosal et al.
presented an O(min(rn, n2 ) + m) time algorithm for updating a rank maximal matching algorithm after the addition
of a vertex.
In the context of matching under preferences the cheating strategies were mainly studied for the stable matching
problem. Gale and Sotomayor [19] showed that women can shorten their preference lists to force an algorithm that
computes a men-optimal stable matching to produce a women-optimal stable matching. Teo et al. [20] considered a
cheating strategy, where women are required to give a full preference list and one of the women is a manipulator. It
was shown in [21] and [22] that if the applied algorithm is men-optimal, then it is not possible for men to gain any
advantage by contracting their preference lists and that the best strategy for them is to give their true preference lists.
Huang [23] explored versions in which men can make coalitions. Cheating strategy in the non-bipartite version of the
stable matching problem (called the stable roommate problem) was considered in [24].
Nasre[25] studied manipulation strategies for the popular matching problem. She presented the following cheating
strategy for the manipulator when he falsifies his preference list: (a) In every popular matching he is matched to a post
that is at least as good as the most-preferred post that he is matched to when he gives his true preference list. (b) In
some popular matching, he is matched to a post that is strictly better than the most-preferred post that he is matched
to when he submits his true preference list. The running time
√ of the algorithms for the cheating strategy matches the
running time needed to compute a popular matching - O( nm).

Manipulation Strategies for the Rank Maximal Matching Problem

3

2 Background
A matching M is said to be maximum (in a graph G) if among all matchings of G, it has the maximum number of
edges. A path P is said to be alternating with respect to matching M or M -alternating if its edges belong alternately
to M and E \ M . A vertex v is unmatched or free in M if it is incident to no edge of M . An M -alternating path P
such that both its endpoints are unmatched in M is said to be M -augmenting (or augmenting with respect to M ). It
was proved by Berge that a matching M is maximum if and only if there exists no M -augmenting path.
We state the following well-known properties of maximum matchings in bipartite graphs. Let G = (A ∪ P, E) be
a bipartite graph and let M be a maximum matching in G. The matching M defines a partition of the vertex set A ∪ P
into three disjoint sets. A vertex v ∈ A ∪ P is even (resp. odd) if there is an even (resp. odd) length alternating path
with respect to M from an unmatched vertex to v. A vertex v is unreachable if there is no alternating path from an
unmatched vertex to v. The even, odd and unreachable vertices are denoted by E, O and U respectively. The following
lemma is well known in matching theory. The proofs can be found in [1].
Lemma 1. Let E, O and U be the sets of vertices defined as above by a maximum matching M in G. Then,
1. E, O and U are pairwise disjoint, and independent of the maximum matching M in G.
2. In any maximum matching of G, every vertex in O is matched with a vertex in E, and every vertex in U is matched
with another vertex in U . The size of a maximum matching is |O| + |U |/2.
3. No maximum matching of G contains an edge between a vertex in O and a vertex in O ∪ U . Also, G contains no
edge between a vertex in E and a vertex in E ∪ U .
2.1 Rank-Maximal Matchings
Next we review an algorithm by Irving et al. [1] for computing a rank-maximal matching. Let G = (A ∪ P, E) be
an instance of the rank-maximal matching problem. Every edge e = (a, p) has a rank reflecting its position in the
preference list of applicant a. E is the union of disjoint sets Ei , i.e., E = E1 ∪ E2 ∪ E3 ... ∪ Er , where Ei denotes the set
of edges of rank i.
Definition 1. The signature of a matching M is defined as an r-tuple ρ(M ) = (x1 , ..., xr ) where, for each 1 ≤ i ≤ r,
xi is the number of applicants who are matched to their i-th rank post in M .
Let M and M ′ be two matchings of G, with the signatures sig(M ) = (x1 , ..., xr ) and sig(M ′ ) = (y1 , ..., yr ). We
say M ≻ M ′ if xi = yi for 1 ≤ i < k ≤ r and xk > yk .
Definition 2. A matching M of a graph G is called rank-maximal if and only if M has the best signature under the
ordering ≻ defined above.
We now give a brief description of an algorithm for computing a rank-maximal matching, whose pseudocode
denoted as Algorithm 1 is given below. Let us denote Gi = (A ∪ P, E1 ∪ E2 ∪ ... ∪ Ei ) as a subgraph of G that only
contains edges of rank smaller or equal to i. The algorithm runs in phases. The algorithm starts with G′1 = G1 and
a maximum matching M1 of G1 . In the first phase, the set of vertices is partitioned into E1 , O1 and U1 . The edges
between O1 and O1 ∪ U1 are deleted. Since the vertices incident to O1 ∪ U1 have to be matched in G1 in every rankmaximal matching, the edges of rank greater than 1 incident to such vertices are deleted from the graph G. Next we add
the edges of rank 2 and call the resulting graph G′2 . We determine the maximum matching M2 in G′2 by augmenting
M1 .
In the i-th phase, the vertices are partitioned into three disjoint sets E(G′i ), O(G′i ) and U (G′i ). We delete every
edge between Oi and Oi ∪ Ui . Also, we delete every edge of rank greater than i incident to vertices in Oi ∪ Ui . Next
we add the edges of rank (i + 1) and call the resulting graph G′i+1 . We determine the maximum matching Mi+1 in
G′i+1 by augmenting Mi .
The following invariants are proved in [1].
1.
2.
3.
4.

For every 1 ≤ i ≤ r, every rank-maximal matching in Gi is contained in G′i .
The matching Mi is rank-maximal in Gi , and is a maximum matching in G′i .
If a rank-maximal matching in G has signature (s1 , ..., si , ...sr ), then Mi has signature (s1 , ..., si ).
The graphs G′i , (1 ≤ i ≤ r) are independent of the rank-maximal matching computed by the algorithm.

Fact 1 Let G = (A ∪ P, E) and G′ = (A ∪ P, E ′ ) be two bipartite graphs with ranks on the edges. Suppose that
E ⊆ E ′ . Also, every edge e ∈ E has the same rank in G and G′ . Then any rank-maximal matching M of G′ such that
M ⊆ E is also a rank-maximal matching of G′ .

4

Pratik Ghosal and Katarzyna Paluch

Algorithm 1 for computing a rank-maximal matching
1: procedure R ANK M AXIMAL M ATCHING(G)
2:
G′1 ← G1
3:
Let M1 be any maximum matching of G′1
4:
for i = 1, 2, . . . , r do
5:
Partition the vertices of G′i into the sets E(G′i ), O(G′i ) and U (G′i )
6:
Delete all edges in Ej (for j > i) which are incident on vertices in O(G′i ) ∪ U (G′i )
7:
Delete all O(G′i )O(G′i ) and O(G′i )U (G′i ) edges from G′i .
8:
Add the edges in Ei+1 and denote the graph as G′i+1 .
9:
Determine a maximum matching Mi+1 in G′i+1 by augmenting Mi .
10:
return Mr

3 Properties of a preference list and strategy ‘best nonfirst’
We note down some properties of the preference list of a1 . First we check which posts a1 can be matched to when he
gives a fixed preference list. Let us assume that the preference list of a1 in G has the form (P1 , P2 , P3 , . . . , Pi , . . . , Pn ),
where Pi denotes the set of posts of rank i in the preference list of a1 . We define an f -post in a similar way as in the
popular matching problem.
Definition 3. A post is called an f -post of G if and only if it belongs to O(G1 \ {a1 }) or U (G1 \ {a1 }), where
G1 = (A ∪ P, E1 ).
Lemma 2. If P1 contains a post that is not an f -post, then a1 is always matched to one of such posts in a rank-maximal
matching of G and thus to one of his first choices.
Proof. Let M ′ be a maximum matching of G1 \ {a1 }. M ′ is of course a matching of G1 but not necessarily of
maximum size. a1 is unmatched in M ′ . P1 contains a post p that is not an f post. Hence, p belongs to E(G1 \ {a1 })
and there exists an M ′ -alternating path S of even length starting at p and ending at some vertex p′ unmatched in
M ′ . Therefore, S together with the edge (a1 , p) forms an augmenting path in the graph G1 . If we apply any such
augmenting path we obtain a maximum matching of G1 . Let us also notice that no edge (a1 , p1 ) such that p1 is an
f -post from P1 belongs to an M ′ -augmenting path. This shows that a1 is matched in every maximum matching of G1
and to a non-f -post from P1 . This completes our proof.
The next lemma shows that if a1 is not matched to a rank one post in every rank maximal matching of G, then an f post may be defined in an alternative way that takes into account the whole graph G1 . This property is needed during
the construction of strategy ‘min max’.
Lemma 3. Let us assume that a1 is not matched to his rank 1 post in every rank maximal matching of G. Then a post
is an f -post if and only if the post belongs to O(G1 ) or U (G1 ).
Proof. We say that a vertex v has the same type in graphs G and H if v ∈ (E(G) ∩ E(H) ∪ (O(G) ∩ O(H)) ∪
(U (G) ∩ U (H)).
We have assumed that a1 is not matched to his rank one post in every rank maximal matching. By the properties
of the rank maximal matchings, a1 ∈ E(G1 ). Hence, we can find a maximum matching M of G1 in which a1 as
an unmatched vertex. Notice that M is a maximum matching of both G1 and G1 \ {a1 }. Hence, a vertex that is
reachable from a free vertex other than a1 in G1 , has the same type in both G1 and G1 \ {a1 }. The vertices from P
that are reachable only from a1 by an alternating path in G1 , belong to O(G1 ). These vertices become unreachable
in G1 \ {a1 }. Finally an unreachable vertex in G1 is also an unreachable vertex in G1 \ {a1 }. Therefore, a post that
belongs to O(G1 ) or U (G1 ), is an f -post.
Conversely, let us consider an f -post p. p is either an odd or an unreachable vertex in G1 \ {a1 }. Suppose p
becomes an even vertex in G1 . We have proved in the previous part that p must be reachable from vertices other than
a1 . Also we know that a vertex that is reachable from a free vertex other than a1 in G1 , has the same type in both G1
and G1 \ {a1 }. Hence, p is an even vertex in G1 \ {a1 }, which is a contradiction. Therefore, p is either an odd or an
unreachable vertex in G1 .
The next lemma shows the potential posts a1 can be matched to when he gives his true preference list.

Manipulation Strategies for the Rank Maximal Matching Problem

5

Lemma 4. Let G be an instance of the rank-maximal matching problem such that a1 is not matched to a rank one post
in every rank-maximal matching of G. Suppose that i is the rank of the highest ranked non-f -post in the preference
list of a1 . If a1 is not matched to his rank one post then a1 can only be matched to a post of rank i or greater than i in
any rank-maximal matching of G.
Proof. Let M be a rank-maximal matching of G. While computing a rank-maximal matching of G we start by finding
a maximum matching of G1 . Since a1 is not matched to his rank one post in every rank maximal matching of G, by
Lemma 3, the set of f -posts contains every vertex from O(G1 ) and U (G1 ). Hence, we delete every edge, that has
rank bigger than 1, incident to an f -post. Thus, every edge e = (a1 , p) such that p is an f -post gets deleted after the
first iteration of the algorithm. Therefore, no such edge can belong to a rank-maximal matching and a1 can only be
matched to a post of rank i or worse.
The above lemmas provide us with an easy method of manipulation that guarantee that a1 can always be matched
to the best non-f -post in his true preference list. Lemma 4 shows us that the most preferred non-f -post of a1 is ranked
not worse than the second most preferred post he can be matcheed to when he is truthful. We assume that a1 is not
matched to a rank one post in every rank-maximal matching of G. Otherwise, the manipulator has no incentive to
cheat. Let pi ∈ Pi be the highest ranked non-f post in the true preference list of a1 . We put pi as a rank 1 post in the
falsified preference list of a1 . Next we fill the falsified preference list of a1 arbitrarily. This completes the description
of strategy ‘best nonfirst’.

Algorithm 2 Strategy ‘best nonfirst’
1:
2:
3:
4:
5:
6:
7:

pi ← a highest ranked non-f -post in the true preference list of a1 .
pi ← the rank 1 post in the falsified preference list of a1 in H
P ′ ← P \ {pi }
for i = 2, . . . , n do
add any post p from P ′ as a rank i post to the falsified preference list of a1 in H
P ′ ← P ′ \ {p}
Output H

Theorem 1. The graph H computed by Algorithm 3 is a strategy ‘best nonfirst’.
The correctness of Algorithm 3 follows from Lemma 2.

4 Optimal manipulation
We have given a strategy ‘best nonfirst’ in the previous section. But that strategy may not be optimal in the sense
that the manipulator may arrange to get a post of even better rank. Let us consider an example from Figure 1. Let us
assume that a1 is a manipulator. The first preference table consists of the true preference list of a1 . a1 is matched to
p5 in every rank-maximal matching of the first example. p3 is the best non-f -post in the preference list of a1 . In the
second example, he applies the strategy described in the previous section. In this example, a1 gives p3 as a rank 1 post
and he is matched to p3 in every rank-maximal matching. Now let us consider the falsified preference list of a1 from
the third example. a1 is matched to p2 in every rank-maximal matching in this example, which is his true rank 1 post.
Hence getting matched to p3 is not an optimal strategy for a1 . In the next section, we are going to give an algorithm
for computing an optimal improvement,i.e., a strategy ‘min max’. Now we introduce the notion of a critical rank and
prove some of its properties.
4.1 Critical Rank
The notion that is going to be very useful while constructing a preference list is that of a critical rank.

6

Pratik Ghosal and Katarzyna Paluch

a1

p2 p1 p3 p5 p4

a1

p3

a2

p1 p2 p3 p4 p5

a2

p1 p2 p3 p4 p5

a3

p1 p2 p3 p4 p5

a3

p1 p2 p3 p4 p5

a4

p1 p2 p3 p4 p5

a4

p1 p2 p3 p4 p5

a5

p2 p1 p3 p6 p4 p5

a5

p2 p1 p3 p6 p4 p5

a6

p6

a6

p6

a1

p2 p1 p6 p3 p4 p5

a2

p1 p2 p3 p4 p5

a3

p1 p2 p3 p4 p5

a4

p1 p2 p3 p4 p5

a5

p2 p1 p3 p6 p4 p5

a6

p6

Fig. 1. Example that shows that strategy ‘best nonfirst’ may not be optimal. The underlined posts are those matched to the corresponding applicant. We can fill the rest of the positions arbitrarily because those posts will not affect any rank-maximal matching

Definition 4. Let G = (A ∪ P, E) be a bipartite graph with ranks belonging to {1, 2, . . . , r} on the edges. Suppose
that a ∈ A, p ∈ P and (a, p) does not belong E. Let H = (A ∪ P, E ∪ {(a, p)}). We define a critical rank of (a, p) as
follows.
If there exists a natural number 1 ≤ i ≤ r such that a ∈ O(G′i ) ∪ U (G′i ) or p ∈ O(G′i ) ∪ U (G′i ), then the critical
rank of (a, p) is equal to min{i : (O(G′i ) ∪ U (G′i )) ∩ {a, p} 6= ∅}. Otherwise, the critical rank of (a, p) is defined as
r + 1.
Lemma 5. Let G, H and (a, p) be as in Definition 4. Then the critical rank of (a, p) is c if and only if
1. for every 1 ≤ i < c the edge (a, p) belongs to every rank-maximal matching of Hi , in which (a, p) has rank i, and
2. for every c < i ≤ r the edge (a, p) belongs to no rank-maximal matching of Hi , in which (a, p) has rank i, and
3. there exists a rank-maximal matching M of Hc , in which (a, p) has rank c such that (a, p) is not contained in M .
Proof. We start by proving the following claim.
Claim. Suppose that e = (a, p) has rank i in the graph H. Then (a, p) belongs to every rank-maximal matching of Hi
if and only if for every j ≤ i both a ∈ E(G′j ) and p ∈ E(G′j ).
Since (a, p) has rank j in H and G differs from H only by the existence of the edge (a, p), we know that the
reduced graphs G′j and Hj′ are the same for each j < i. Also, the reduced graphs Hi′ and G′i may be the same or differ
by the existence of the edge e.
If for some j < i it holds that a ∈ O(G′j ) ∪ U (G′j ) or p ∈ O(G′j ) ∪ U (G′j ), then the edge (a, p) does not belong
to Hi′ , because it is removed at the beginning of phase j + 1 during the computation of a rank-maximal matching
of H. Thus in this case e does not belong to any rank-maximal matching of Hi . If for every j < i, a ∈ E(G′j ) and
p ∈ E(G′j ) and both a ∈ O(G′i )∪U (G′i ) or p ∈ O(G′i )∪U (G′i ), then e belongs to Hi′ , but there exists a rank-maximal
matching of Hi that does not contain e. This is so because the addition of e to G′i does not create any augmenting path
in Hi′ , therefore a maximum matching of G′i is also a maximum matching of Hi′ and thus a rank-maximal matching of
Hi . This shows that in this case every rank-maximal matching of Gi is also rank-maximal in Hi . Hence, there exists a
rank-maximal matching of Hi that does not contain (a, p).
Assume now that for every j ≤ i both a ∈ E(G′j ) and p ∈ E(G′j ). This means that the reduced graph Hi′ does
contain (a, p). Any rank-maximal matching of Hi is a maximum matching of Hi′ . Let Mi denote a maximum matching
of G′i . Since a ∈ E(G′i ) and p ∈ E(G′i ), (a, p) belongs to every an Mi -augmenting path - because a is the endpoint
of some even length Mi -alternating path ending at a free vertex a′ ∈ A and similarly, p is the endpoint of some even
length Mi -alternating path ending at a free vertex p′ ∈ P . Together with (a, p) these paths form an Mi -augmenting

Manipulation Strategies for the Rank Maximal Matching Problem

7

path in Hi′ . Additionally, we notice that (a, p) belongs to every Mi -augmenting path and thus to every maximum
matching of Hi′ and hence to every rank-maximal matching of Hi .
Let us now prove the other direction of the claim and suppose that (a, p) belongs to every rank-maximal matching
of Hi . This means that (a, p) belongs to every maximum matching of Hi′ . Then (a, p) must be contained in Hi′ and by
the above arguments, we know that for every j < i both a ∈ E(G′j ) and p ∈ E(G′j ). No maximum matching of G′i
contains (a, p) - therefore a maximum matching of Hi′ must be bigger by one than a maximum matching of G′i . This
means that (a, p) must belong to a path augmenting with respect to a maximum matching of G′i , which means that the
endpoints of (a, p) belong to E(G′i ). This way we have proved the claim.
The claim, which we have just proved, shows that if (i) for every 1 ≤ i < c the edge (a, p) belongs to every
rank-maximal matching of Hi , in which (a, p) has rank i and (ii) there exists a rank-maximal matching M of Hc , in
which (a, p) has rank c such that (a, p) is not contained in M , then c = min{i : (O(G′i ) ∪ U (G′i )) ∩ {a, p} =
6 ∅} and
hence, c is the critical rank of (a, p).
The claim also shows that if c is the critical rank of (a, p), then for every i < c the edge (a, p) belongs to every
rank-maximal matching of Hi , in which (a, p) has rank i and there exists a rank-maximal matching of Hc , in which
(a, p) has rank c that does not contain (a, p). It remains to prove that if c is the critical rank of (a, p), then for every
c < i ≤ r the edge (a, p) belongs to no rank-maximal matching of Hi , in which (a, p) has rank i. This follows from
the fact that any edge of rank i > c incident to a vertex belonging to O(Hc′ )∪U (Hc′ ) is removed from Hi′ and therefore
cannot belong to a maximum matching of Hi′ and thus cannot be present in any rank-maximal matching of Hi . This
ends the proof of the lemma.
Corollary 1. The critical rank of an edge incident to an f -post of G is 1 in G.
Lemma 6. Let G be a bipartite graph and a be an applicant. Let p be the only post in the preference list of a. Suppose
that the critical rank of (a, p) in G is c. Let Ĝ = G ∪ {(a, p′ )}. We assume that p′ is a rank 1, f -post in the preference
list of a. Then the critical rank of (a, p) is at most c in Ĝ.
Proof. It suffices to show that for every c < i ≤ r no rank-maximal matching of Ĝ, in which (a, p) has rank i
contains (a, p). Suppose to the contrary that there exists rank-maximal matching M of Ĝ, in which (a, p) has rank i
that contains (a, p). Then M is also a matching of G and by Fact 1 it is also a rank-maximal matching of G. However,
by Lemma 5 no rank-maximal matching of G, in which (a, p) has rank i > c can contain (a, p) - a contradiction.
Lemma 7. Let G = (A ∪ P, E) be a bipartite graph, in which a has two neighbors p and p′ such that apart from
(a, p) each edge has a rank belonging to {1, 2, . . . , r}. Additionally, p′ is a rank one f -post in the preference list of
a1 . Let G′ = (A ∪ P, E \ {a, p}) and G′′ = (A ∪ P, E \ {a, p′ }). Suppose that a becomes unreachable in G′i and the
critical rank of (a, p) is c in G′′ . Then the critical rank of (a, p) in the graph G is equal to, correspondingly:
1. c if c ≤ i,
2. i if c > i.
Proof. We can prove that for every j < i there exists a rank-maximal matching of G′′j that contains (a, p′ ) and there
exists a rank-maximal matching of G′′j that does not contain (a, p′ ).
Claim. Let us suppose that (a, p) has rank c′ < i in G. Then, the existence of a rank-maximal matching M of G that
does not contain (a, p) implies that the critical rank of (a, p) in G′′ is at most c′ .
Proof. By Fact 1 M is a rank-maximal matching of G′ and hence, every rank-maximal matching of G′ is also rankmaximal in G. We know that there exists a rank-maximal matching M ′ of G′ that does not contain (a, p′ ). Thus a is
unmatched in M ′ . By Fact 1 M ′ is also a rank-maximal matching of G′′ . M ′ does not contain (a, p), which shows
that the critical rank of (a, p) is at most c′ in G′′ .
First we assume that c ≤ i. Since G′′ is a subgraph of G, by Lemma 6 the critical rank of (a, p) ≤ c in G. Suppose
the critical rank of (a, p) = c′ < c in G. Let us consider a graph G, in which (a, p) has rank c′ . Since the critical rank
of (a, p) is equal to c′ , there exists a rank-maximal matching M of G that does not contain (a, p). By Claim C1 this
means that that the critical rank of (a, p) in G′′ is at most c′ < c - a contradiction. We conclude that the critical rank
of (a, p) remains c in G if c ≤ i.
Let us consider now the case when c > i. First we show that the critical rank of (a, p) ≤ i in G. Let us consider
the graph G′ . The vertex a becomes unreachable in G′ after iteration i. We know that G = G′ ∪ {(a, p)}. Hence, the
edge (a, p) is deleted in the graph G if the rank of (a, p) > i in G. Therefore, the critical rank of (a, p) ≤ i in G.

8

Pratik Ghosal and Katarzyna Paluch

Next we show that the critical rank of (a, p) = i in G. Suppose the critical rank of (a, p) = i′ < i in G. Since
the critical rank of (a, p) is equal to i′ < i, there exists a rank-maximal matching M of G, in which (a, p) has rank
i′ that does not contain (a, p). By Claim C1 this means that that the critical rank of (a, p) in G′′ is at most i′ < c - a
contradiction. Therefore we have proved that the critical rank of (a, p) is equal to i in G.
Corollary 2. Let G be a bipartite graph such that p′ is a rank one, f -post in the preference list of a. Suppose that a
becomes unreachable during iteration i. Let G̃ = G ∪ {(a, p)} with the rank of the edge (a, p) being c. Then (a, p) is
never matched in a rank- maximal matching of G̃, if c > i.
Lemma 8. Let us consider two bipartite graphs G1 and G2 such that p is a rank one, f -post of in the preference list
of a in both graphs. Also a has only two neighbors in each of the graphs. In the graph G1 , a has p1 as a rank i post. In
the graph G2 , a has p2 as a rank j post. We assume that G3 is the union of graphs G1 and G2 . Then a1 is matched to
p in every rank-maximal matching of both G1 and G2 if and only if a is matched to p in every rank-maximal matching
of G3 .
Proof. Assume that a is matched to p1 in a rank-maximal matching M of G3 . M is also a matching in the graph G1 .
Since G1 is a subgraph of G3 , from the fact 1 a rank maximal matching of G3 is a rank maximal matching of G1 . This
means that a is matched to p1 in some rank maximal matching of G1 , which is a contradiction.
Conversely, let a be matched to p in every rank maximal matching of G3 . Let M3 be a rank maximal matching of
G3 . Suppose that a is matched to p1 in some rank-maximal matching of G1 . Since G1 is a subgraph of G3 , from fact 1
M3 is a rank maximal matching of G1 . Thus, M1 and M3 have the same signature. Therefore, M1 is a rank maximal
matching of G3 , which is a contradiction.

5 Strategy ‘min max’
In this section we give an algorithm that computes a graph H by using the strategy ‘min max’ for the applicant a1 . We
recall that strategy ‘min max’ consists of finding a full preference list for a1 such that the maximal rank of a post he
can obtain is minimized. Since we have assumed that a1 is not always matched to his first choice when he is truthful
and since strategy ‘best nonfirst’ ensures that a1 always gets a highest ranked non-f -post, it remains to check if it is
possible for a1 to get one of f -posts. For a given f -post p we want to verify if a1 can construct a full preference list
that gives him a guarantee that he is matched to p in every rank maximal matching of the resulting graph. From all
such f -posts we want to choose that of highest rank in the true preference list of a1 . Below we show that this way we
indeed compute strategy ‘min max’.
Let p be an f -post a1 wants to be matched to in every rank maximal matching of Hp . How do we construct such
Hp ? Let Ĥp denote the graph, in which a1 is incident only to p and (a1 , p) has rank one. The graph Ĥp is meant to
be a subgraph of Hp . By Lemma 8 we know that in order to obtain Hp it suffices to find a certain number of graphs
Hp,pj such that p and pj are the only posts in the preference list of a1 , p has rank 1, pj has rank j > 1 and every
rank-maximal matching of Hp,pj matches a1 to p. Because then we can combine those graphs into one graph Hp . In
fact, it suffices to fill the preference list of a1 only till rank k, where k is the number of phase during which a1 becomes
unreachable in Ĥp , or equivalently, where k is the rank when a1 becomes an unreachable vertex in Ĥp . This follows
from Corollary 2, which says that no rank-maximal matching of Hp,p′ such that (a1 , p′ ) has rank i > k contains
(a1 , p′ ). Therefore, the ranks greater than k in the preference list of a1 may be filled with arbitrary posts not occurring
previously.
Suppose that we want to find a "good" post for rank i < k in the preference list of a1 . First, we check if there is
any available post p′ such that the critical rank of (a, p′ ) is smaller than i in Ĥp . If we find such a post, then by Lemma
5 the edge (a, p′ ) never occurs in a rank-maximal matching of Hp,p′ in which (a, p′ ) has rank i or greater and we may
add p′ to the preference list of a1 as its post of rank i. Otherwise, we consider the posts with critical rank i in the graph
Ĥp . Let p′ be such a post. Next we use a dynamic rank-maximal matching algorithm to verify if p is matched to a1 in
every rank maximal matching, when we add (a1 , p′ ) as a rank i edge to the graph Ĥp . If yes, then we put p′ as an ith
choice in the falsified preference list of a1 . If not, we check another post with critical rank i in Ĥp . If we are unable to
find any post for rank i, Algorithm 5 outputs that there does not exist any preference list that matches a1 to p in every
rank maximal matching of Hp .
The algorithm that computes a graph Hp , if it exists is given below as Algorithm 5. The thing that still requires
explanation is how we check if (a, p) belongs to every rank-maximal matching of Hp,p′ . For this we need the reduced

Manipulation Strategies for the Rank Maximal Matching Problem

9

graph of Hp,p′ from phase r, which we can obtain by either applying the standard rank-maximal matching algorithm
or we can use one of the algorithms for the dynamic version if we want to have a faster algorithm. Once we have
access to this reduced graph of Hp,p′ we can use the following lemma.
Lemma 9. Let G be an instance of the rank-maximal matching problem, in which the maximal rank of an edge is
r. Also, we assume that M is a fixed rank-maximal matching of G that matches an edge (a, p). Let us consider the
switching graph of the matching M in G. Then the edge (a, p) belongs to every rank-maximal matching of G if there
does not exist any switching path or switching cycle in the switching graph of M that contains the vertex p.
Proof. Let us fix a rank maximal matching M of G that matches the edge (a, p). Theorem 1 from [16] states that every
rank-maximal matching G can be obtained from M by applying some vertex-disjoint switching paths and switching
cycles in the switching graph of M . If there does not exist any switching path or switching cycle containing the vertex
p, p has the same partner in every rank maximal matching of G. Therefore, (a, p) is matched in every rank maximal
matching of G.
Definition 5. We say that an f -post p is feasible if there exists a graph Hp such that every rank-maximal matching of
Hp matches a1 to p.

Algorithm 3 Construction of Hp
1: Ci ← {p′ ∈ P : the critical rank of (a1 , p′ ) in Hp,p′ equals i}
2: L ← an empty list - L is the falsified preference list of a1 that is going to have the form (p1 , p2 , ..., pn ), where pi denotes the
rank i post in L.
3: add p to L – this is the rank 1 post in the preference list L of a1
4: k ← the number of phase when a1 becomes unreachable in Ĥp , i.e., a1 ∈ U (Ĥ ′ p,k ) and a1 ∈ E(Ĥ ′ p,i ) for every i < k,
where Ĥ ′ p,i denotes the i-th reduced graph of Ĥp .
5: C ← C1
6: for i = 2, . . . , k do
7:
if C 6= ∅ then (there exists a post p′ in C)
8:
add p′ as a rank i post to the falsified preference list L of a1
9:
C ← C \ {p′ }
10:
else (C = ∅)
11:
SEARCH ← T RU E
12:
while ∃p′ with critical rank of (a, p′ ) equal to i in Ĥp and SEARCH do
13:
if (a, p) belongs to every rank-maximal matching of Hp,p′ (Lemma 9) then
14:
add p′ as a rank i post to the falsified preference list L of a1
15:
SEARCH ← F ALSE
16:
if SEARCH then Break
17:
C ← C ∪ Ci
18: if L is a full preference list then
19: return Hp
20: else
21: return p is not a feasible f -post

In the lemma below we prove the correctness of Algorithm 5.
Lemma 10. If Algorithm 5 outputs a graph Hp , then every rank-maximal matching of Hp matches a1 to p. Otherwise,
there does not exist a graph Hp , in which a1 gives a full preference list and such that every rank-maximal matching of
Hp matches a1 to p.
Proof. If Algorithm 5 outputs a graph Hp , then by Corollary 2 and Lemma 8 every rank-maximal matching of Hp
matches a1 to p. If the algorithm does not output any graph, then it means that there was a problem for some i with
finding a rank i post for the preference list of a1 . However, the algorithm considers every available post p′ of critical
rank at most i in Hp,p′ for that position. Therefore, if none of them has the required property that every rank-maximal
matching of Hp,p′ matches a1 to p, then no post of critical rank greater than i in Hp,p′ satisfies it either. This finishes
the proof of correctness of Algorithm 5.

10

Pratik Ghosal and Katarzyna Paluch

Theorem 2. Let p be a highest rank feasible f -post in the true preference list of a1 . Then Hp output by Algorithm 5 is
a strategy ‘min max’. Moreover, each graph H that is a strategy ‘min max’ has the property that each rank-maximal
matching of H matches a1 to the same post.
Proof. Let Hopt denote a graph that is a strategy ‘min max’. Suppose that Hp is not a strategy ‘min max’. There exists
then a post p′ such that rank(a1 , p′ ) < rank(a1 , p) in the true preference list of a1 and (a1 , p′ ) belongs to some rank
maximal matching of Hopt . Since rank(a1 , p′ ) < rank(a1 , p) in the true preference list of a1 , p′ is an f -post. Also,
a1 can only be matched to a post of rank not worse than rank(a1 , p) in the true preference list of a1 in a rank-maximal
matching of Hopt , otherwise Hopt would not be a strategy ‘min max’ because it would fare worse that the strategy
Hp in terms of the worst post a1 can become matched to. This means that a1 can only be matched to f -posts under
strategy Hopt , because every non-f -post has a worse rank than the rank of post p in the preference list of a1 . Corollary
1 shows that the critical rank of an f -post is 1. Hence, a1 can only be matched to a post of that has rank 1 in Hopt .
Therefore, we can only put p′ as a rank 1 post in the preference list of a1 in Hopt .
Now we will show how to build a preference list of a1 without any ties that matches a1 to p′ in every rank-maximal
matching. Let us denote this graph as Hmod . We put p′ as a rank 1 post. We create the preference list of a1 in Hmod
using the preference list of a1 in Hopt . Suppose we want to add a rank i post to the preference list of a1 in Hmod . If
there is only one rank i post in the preference list of a1 in Hopt , then that post will have the same rank in the preference
list of a1 in Hmod . If there are more than one rank i posts in the preference list of a1 in Hopt , we choose only one of
them. Finally, we add the remaining posts to a1 ’s preference list in Hmod in an arbitrary order as his least preferred
posts. This way we get a preference list without any ties.
First, we show that Hmod and Hopt have the same signature. A rank-maximal matching in Hopt that matches a to
p′ is a matching in Hmod and has the same signature. Thus a rank-maximal matching of Hopt does not have a better
signature than a rank- maximal matching of Hmod . Also, any post in the preference list of a1 has rank in Hopt that is
not worse than in Hmod . If we consider a rank-maximal matching of Hmod , then the signature of that matching is not
worse in Hopt . Therefore rank-maximal matchings of Hopt and Hmod have the same signature.
Next we want to prove that a1 is matched to p′ in every rank-maximal matching of Hmod . Suppose that a1 is
matched to some p′′ in a rank-maximal matching M of Hmod . We can see that M is a matching in Hopt . The rank
of p′′ in the preference list of a1 in Hopt is not worse than the rank of p′′ in the preference list of a1 in Hmod . This
shows that the signature of the matching M in Hopt is not worse than the signature of M in Hmod . But we know that
the signatures of rank-maximal matching of Hopt and Hmod are the same. Hence, M is a rank-maximal matching of
Hopt . This implies that a1 is matched to p′′ in a rank-maximal matching of Hopt too.
The preference list of a1 in Hmod does not contain any ties, which means that p′′ is not a rank 1 post in the
preference list of a1 in Hmod . We know that the critical rank of an f -post is 1. Therefore p′′ is not an f -post. But
a1 cannot be matched to a non-f -post in Hopt - a contradiction. This proves that a1 is matched to p′ in every rankmaximal matching of Hmod . Lemma 8 shows that Algorithm 5 could also create the same preference list because it
would consider each graph Hp,pi such that pi has rank i in Hmod . Since the rank of (a1 , p′ ) is strictly better than the
rank of (a1 , p) in the true preference list of a1 , it means that p is not a highest rank feasible f -post - a contradiction.
Therefore Hp is indeed a strategy ‘min max’. Also, by the construction of Hmod we have shown that each graph H
that is a strategy ’min max’ has the property that each rank-maximal matching of H matches a1 to the same post.

References
1. R. W. Irving, T. Kavitha, K. Mehlhorn, D. Michail, and K. E. Paluch, “Rank-maximal matchings,” ACM Trans. Algorithms,
vol. 2, no. 4, pp. 602–610, 2006.
2. A. Abdulkadiroğlu and T. Sönmez, “Random serial dictatorship and the core from random endowments in house allocation
problems,” Econometrica, vol. 66, no. 3, pp. 689–701, 1998.
3. D. J. Abraham, K. Cechlárová, D. Manlove, and K. Mehlhorn, “Pareto optimality in house allocation problems,” in Algorithms and Computation, 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004, Proceedings
(R. Fleischer and G. Trippen, eds.), vol. 3341 of Lecture Notes in Computer Science, pp. 3–15, Springer, 2004.
4. A. E. Roth and A. Postlewaite, “Weak versus strong domination in a market with indivisible goods,” Journal of Mathematical
Economics, vol. 4, no. 2, pp. 131–137, 1977.
5. D. J. Abraham, R. W. Irving, T. Kavitha, and K. Mehlhorn, “Popular matchings,” SIAM J. Comput., vol. 37, no. 4, pp. 1030–
1045, 2007.
6. C.-C. Huang, T. Kavitha, K. Mehlhorn, and D. Michail, “Fair matchings and related problems,” Algorithmica, vol. 74, no. 3,
pp. 1184–1203, 2016.

Manipulation Strategies for the Rank Maximal Matching Problem

11

7. D. Gale and L. S. Shapley, “College admissions and the stability of marriage,” American Mathematical Monthly, vol. 69, no. 1,
pp. 9–15, 1962.
8. D. Gusfield and R. W. Irving, The stable marriage problem: structure and algorithms. Foundations of computing, MIT Press,
1989.
9. M. M. Halldórsson, K. Iwama, S. Miyazaki, and H. Yanagisawa, “Improved approximation of the stable marriage problem,” in
Algorithms - ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings (G. D.
Battista and U. Zwick, eds.), vol. 2832 of Lecture Notes in Computer Science, pp. 266–277, Springer, 2003.
10. R. W. Irving, “Matching medical students to pairs of hospitals: A new variation on a well-known theme,” in Proceedings of the
6th Annual European Symposium on Algorithms, ESA’98, (London, UK, UK), pp. 381–392, Springer-Verlag, 1998.
11. R. W. Irving, D. F. Manlove, and S. Scott, “Strong stability in the hospitals/residents problem,” in Proceedings of the 20th
Annual Symposium on Theoretical Aspects of Computer Science, STACS’03, (London, UK, UK), pp. 439–450, Springer-Verlag,
2003.
12. A. E. Roth, “The evolution of the labor market for medical interns and residents: A case study in game theory,” Journal of
Political Economy, vol. 92, no. 6, p. 991, 1984.
13. R. W. Irving, “Greedy matchings,” Technical R eport Tr-2003-136, University of G lasgow, 2003.
14. K. Paluch, “Capacitated rank-maximal matchings,” in International Conference on Algorithms and Complexity, pp. 324–335,
Springer, 2013.
15. T. Kavitha and C. D. Shah, “Efficient algorithms for weighted rank-maximal matchings and related problems,” in ISAAC, vol. 6,
pp. 153–162, Springer, 2006.
16. P. Ghosal, M. Nasre, and P. Nimbhorkar, “Rank-maximal matchings–structure and algorithms,” in International Symposium on
Algorithms and Computation, pp. 593–605, Springer, 2014.
17. P. Nimbhorkar and A. R. V, “Dynamic rank-maximal matchings,” in Computing and Combinatorics - 23rd International Conference, COCOON 2017, Hong Kong, China, August 3-5, 2017, Proceedings (Y. Cao and J. Chen, eds.), vol. 10392 of Lecture
Notes in Computer Science, pp. 433–444, Springer, 2017.
18. P. Ghosal, A. Kunysz, and K. E. Paluch, “The dynamics of rank-maximal and popular matchings,” CoRR, vol. abs/1703.10594,
2017.
19. D. Gale and M. Sotomayor, “Ms. machiavelli and the stable matching problem,” The American Mathematical Monthly, vol. 92,
no. 4, pp. 261–268, 1985.
20. C.-P. Teo, J. Sethuraman, and W.-P. Tan, “Gale-shapley stable marriage problem revisited: Strategic issues and applications,”
Management Science, vol. 47, no. 9, pp. 1252–1267, 2001.
21. L. E. Dubins and D. A. Freedman, “Machiavelli and the gale-shapley algorithm,” The American Mathematical Monthly, vol. 88,
no. 7, pp. 485–494, 1981.
22. A. E. Roth, “The economics of matching: Stability and incentives,” Mathematics of operations research, vol. 7, no. 4, pp. 617–
628, 1982.
23. C.-C. Huang, “Cheating by men in the gale-shapley stable matching algorithm,” in ESA, vol. 6, pp. 418–431, Springer, 2006.
24. C.-C. Huang, “Cheating to get better roommates in a random stable matching,” in Annual Symposium on Theoretical Aspects
of Computer Science, pp. 453–464, Springer, 2007.
25. M. Nasre, “Popular matchings–structure and cheating strategies,” arXiv preprint arXiv:1301.0902, 2013.

