Popular Matchings with Two-Sided Preferences and One-Sided Ties

We are given a bipartite graph

$$G = (A \cup B, E)$$

G

=

(

A

∪

B

,

E

)

where each vertex has a preference list ranking its neighbors: in particular, every

$$a \in A$$

a

∈

A

ranks its neighbors in a strict order of preference, whereas the preference lists of

$$b \in B$$

b

∈

B

may contain ties. A matching

M

is

popular

if there is no matching

$$M'$$

M

′

such that the number of vertices that prefer

$$M'$$

M

′

to

M

exceeds the number that prefer

M

to

$$M'$$

M

′

. We show that the problem of deciding whether

G

admits a popular matching or not is

$$\mathsf {NP}$$

NP

-hard. This is the case even when every

$$b \in B$$

b

∈

B

either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each

$$b \in B$$

b

∈

B

puts all its neighbors into a single tie. That is, all neighbors of

b

are tied in

b

’s list and and

b

desires to be matched to any of them. Our main result is an

$$O(n^2)$$

O

(

n

2

)

algorithm (where

$$n = |A \cup B|$$

n

=

|

A

∪

B

|

) for the popular matching problem in this model. Note that this model is quite different from the model where vertices in

B

have no preferences and do

not

care whether they are matched or not.