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.