Unpopularity Factor in the Marriage and Roommates
Problems
Suthee Ruangwises1 and Toshiya Itoh2

arXiv:1803.09435v1 [] 26 Mar 2018

1

Department of Mathematical and Computing Science, Tokyo Institute of
Technology, Tokyo, Japan; ruangwises.s.aa@m.titech.ac.jp
2
Department of Mathematical and Computing Science, Tokyo Institute of
Technology, Tokyo, Japan; titoh@c.titech.ac.jp

Abstract
We develop an algorithm to compute an unpopularity factor of a given matching
in the
Problem (mp). The algorithm runs in
√ Roommate Problem (rp) and Marriage
√
O(m n log2 n) time for rp and in O(m n log n) time for mp.

1

Introduction

The concept of an unpopularity factor was first introduced by McCutchen [5] in the setting
of one-sided preference lists, where each person has a list that ranks items but each item
does not have list that ranks people. In the setting of two-sided preference lists, Huang
and Kavitha [4] proved that an rp instance always has a matching with unpopularity factor
O(log n), and it is NP-hard to find a matching with unpopularity factor less than 4/3 times
of the lowest one.
Biró et al. p
[1] developed an algorithm to determine whether a given matching M is
√
popular in O(m nα(n, m) log3/2 n) time for rp (O(m n log n) time when running with the
√
most recent algorithm to find a maximum weight perfect matching [2]) and in O(m n) time
for mp. However, there is currently no algorithm to efficiently compute an unpopularity
factor u(M ) of a given matching M .
Our Contribution: Using a similar idea to [1], in this paper we develop an algorithm
√
√
to compute u(M ) in O(m n log2 n) time for rp and in O(m n log n) time for mp.

2

Preliminaries

Let I be an instance of the Roommate Problem (rp) or Marriage Problem (mp) where there
is a set A = {a1 , ..., an } of n people, with each person having a list that ranks some people
in A as his/her preferred partner in order of preference, and let m be the total length of
people’s preference lists. In rp there is no further restriction, while in mp only people with
different genders can be matched.

1

Let

For matchings X and Y of I, let φ(X, Y ) be the number of people who prefer X to Y .
(
φ(Y, X)/φ(X, Y ), if φ(X, Y ) > 0;
∆(X, Y ) =
∞,
otherwise.

Finally, define an unpopularity factor u(M ) = maxM ′ ∈M−{M } ∆(M, M ′ ), where M is the
set of all matchings of I. A matching M is popular if u(M ) ≤ 1.

3

Main Results

We first consider rp in the case that people’s preference lists contain no ties (two or more
items with equal preference). Let I be an rp instance, M be a matching of I, and k be an
arbitrary positive real number. Similarly to [1], we construct an undirected graph H(M,k)
with vertices A ∪ A′ , where A′ = {a′1 , ..., a′n }. An edge {ai , aj } exists if and only if ai is in
aj ’s preference list and aj is in ai ’s preference list. An edge {a′i , a′j } exists if and only if
{ai , aj } exists. Finally, we add an edge {ai , a′i } for every ai ∈ A.
However, we will assign weights to edges of H(M,k) differently from [1]. For each pair
of i, j with an edge {ai , aj }, define δi,j as follows.


if ai is unmatched in M or ai prefers aj to M (ai );
1,
δi,j = −k, if ai prefers M (ai ) to aj ;


0,
if {ai , aj } ∈ M.

We then set the weights of {ai , aj } and {a′i , a′j } to be δi,j + δj,i . Also, for each edge {ai , a′i },
we set its weight to be −2k if ai is matched in M , and 0 otherwise.
Lemma 1. u(M ) > k if and only if H(M,k) has a positive weight perfect matching.

Proof. Suppose that u(M ) > k. There must be a matching M ′ such that φ(M ′ , M ) > k ·
φ(M, M ′ ).
′
Let A1 (M ′ ) = {ai ∈ A|ai is matched in M ′ } and A2 (M ′ ) = A−A1 (M ′ ). Also, let A+
1 (M ) =
′
{ai ∈ A1 (M ′ )|ai is unmatched in M or ai prefers M ′ (ai ) to M (ai )}, A−
1 (M ) = {ai ∈
−
′
′
′
′
A1 (M )| ai prefers M (ai ) to M (ai )}, and A2 (M ) = {ai ∈ A2 (M )|ai is matched in M }.
−
−
′
′
′
′
We have φ(M ′ , M ) = |A+
1 (M )| and φ(M, M ) = |A1 (M )|+ |A2 (M )|. Now consider a perfect matching S = M ′ ∪ {(a′i , a′j )|(ai , aj ) ∈ M ′ } ∪ {(ai , a′i )|ai is unmatched in M ′ } of H(M,k) .

−
−
′
′
′
′
′
The weight of S is 2 |A+
1 (M )| − k|A1 (M )| −2k|A2 (M )| = 2φ(M , M )−2k·φ(M, M ) > 0
by the assumption.
On the other hand, suppose there is a positive weight perfect matching S of H(M,k) .
Let M1 = {(ai , aj ) ∈ S} and M2 = {(ai , aj )|(a′i , a′j ) ∈ S}. We have A2 (M1 ) = A2 (M2 ) and
the weight of S is


−
+
−
|A+
1 (M1 )| − k|A1 (M1 )| + |A1 (M2 )| − k|A1 (M2 )| − 2k|A2 (M1 )|


−
+
−
−
−
≤ |A+
1 (M1 )| − k|A1 (M1 )| + |A1 (M2 )| − k|A1 (M2 )| − k|A2 (M1 )| − k|A2 (M2 )|
= (φ(M1 , M ) − k · φ(M, M1 )) + (φ(M2 , M ) − k · φ(M, M2 )).

Therefore, (φ(M1 , M ) − k · φ(M, M1 )) + (φ(M2 , M ) − k · φ(M, M2 )) must be positive, so we
have φ(M1 , M ) > k · φ(M, M1 ) or φ(M2 , M ) > k · φ(M, M2 ), which means u(M ) > k.
2

Lemma 2. Given an rp instance I, a matching M of I, and a number k = xy , where x ∈
√
[0, n − 1] and y ∈ [1, n] are integers, we can determine whether u(M ) > k in O(m n log n)
time.
Proof. Observe that H(M,k) has O(n) vertices and O(m) edges, and we can multiply the
weights of all edges by y so that they are all integers with magnitude at most O(n2 ). The
current fastest algorithm to find a maximum weight perfect matching in a graph with integer
√
weight edges takes O(m n log n) running time [2].
Theorem 3. Given an rp instance I and a matching M of I, we can compute u(M ) in
√
O(m n log2 n) time.
Proof. Observe that if u(M ) is not ∞, it must be in the form of x/y, where x ∈ [0, n − 1]
and y ∈ [1, n] are integers, meaning that there are at most O(n2 ) possible values of u(M ).
By performing a binary search on k (if u(M ) > n − 1, then u(M ) = ∞), we have to run
the algorithm in Lemma 2 for O(log n2 ) = O(log n) times, so the total running time is
√
O(m n log2 n).
Remarks: It is easy to generalize the result to the case that preference lists contain
ties by setting δi,j = 0 if ai prefers M (ai ) and aj equally. Also, in mp the graph H(M,k) is
bipartite, so we can orient the edges of S in one way and the rest in other way. The problem
√
is reduced to finding a positive weight directed cycle, which can be done in O(m n) time
√
[3], thus the total running time is O(m n log n).

References
[1] P. Biró, R.W. Irving, and D. Manlove. Popular Matchings in the Marriage and Roommates Problems. In Proceedings of the 7th International Conference on Algorithms and
Complexity (CIAC), pages 97-108 (2010).
[2] R. Duan, S. Pettie, and H.-H. Su. Scaling Algorithms for Weighted Matching in General
Graphs. ACM Trans. Algorithms, 14(1):8:1-8:35 (2018).
[3] A.V. Goldberg. Scaling algorithms for the shortest paths problem. SIAM Journal on
Computing, 24(3):494-504 (1995).
[4] C.-C. Haung, T. Kavitha, D. Michail, and M. Nasre. Bounded unpopularity matchings. In Proceedings of the 11th Scandinavian Workshop on Algorithm Theory (SWAT),
pages 127-137 (2008).
[5] R.M. McCutchen. The least-unpopularity-factor and least-unpopularity-margin criteria
for matching problems with one-sided preferences. In Proceedings of the 15th Latin
American Symposium on Theoretical Informatics (LATIN), pages 593-604 (2008).

3

