11institutetext: Tata Institute of Fundamental Research, Mumbai, India
11email<EMAIL_ADDRESS>
# Popular Matchings with One-Sided Bias††thanks: A preliminary version of this
paper appeared in ICALP 2020 [18].

Telikepalli Kavitha Work done while visiting Max-Planck-Institut für
Informatik, Saarbrücken, Germany.

###### Abstract

Let $G=(A\cup B,E)$ be a bipartite graph where the set $A$ consists of agents
or main players and the set $B$ consists of jobs or secondary players. Every
vertex has a strict ranking of its neighbors. A matching $M$ is popular if for
any matching $N$, the number of vertices that prefer $M$ to $N$ is at least
the number that prefer $N$ to $M$. Popular matchings always exist in $G$ since
every stable matching is popular.

A matching $M$ is $A$-popular if for any matching $N$, the number of agents
(i.e., vertices in $A$) that prefer $M$ to $N$ is at least the number of
agents that prefer $N$ to $M$. Unlike popular matchings, $A$-popular matchings
need not exist in a given instance $G$ and there is a simple linear time
algorithm to decide if $G$ admits an $A$-popular matching and compute one, if
so.

We consider the problem of deciding if $G$ admits a matching that is both
popular and $A$-popular and finding one, if so. We call such matchings fully
popular. A fully popular matching is useful when $A$ is the more important
side—so along with overall popularity, we would like to maintain “popularity
within the set $A$”. A fully popular matching is not necessarily a min-
size/max-size popular matching and all known polynomial-time algorithms for
popular matching problems compute either min-size or max-size popular
matchings. Here we show a linear time algorithm for the fully popular matching
problem, thus our result shows a new tractable subclass of popular matchings.

##  1 Introduction

Let $G=(A\cup B,E)$ be a bipartite graph where vertices in $A$ are called
agents and those in $B$ are called jobs. Every vertex has a strict ranking of
its neighbors. Such a graph, also called a marriage instance, is a very well-
studied model in two-sided matching markets. A matching $M$ in $G$ is stable
if there is no blocking edge with respect to $M$, i.e., no edge $(a,b)$ such
that $a$ and $b$ prefer each other to their respective assignments in $M$.
Gale and Shapley [10] in 1962 showed that stable matchings always exist in $G$
and can be efficiently computed.

Stable matching algorithms have applications in several real-world problems.
For instance, stable matchings have been extensively used to match students to
schools and colleges [1, 3] and one of the oldest applications here is to
match medical residents to hospitals [4, 22]. It is known that all stable
matchings in $G$ have the same size [11] and this may only be half the size of
a maximum matching in $G$. Consider the following instance on four vertices
$a_{0},a_{1},b_{0},b_{1}$. The preferences of these four vertices are as
follows:

$a_{0}:b_{1}\ \ \ \ \ \ \ \ \ \ \ \ a_{1}:b_{1}\succ b_{0}\ \ \ \ \ \ \ \ \ \
\ \ b_{0}:a_{1}\ \ \ \ \ \ \ \ \ \ \ \ b_{1}:a_{1}\succ a_{0}.$

Here $a_{1}$ and $b_{1}$ are each other’s top choices. There is no edge
between $a_{0}$ and $b_{0}$. Note that
$M_{\max}=\\{(a_{0},b_{1}),(a_{1},b_{0})\\}$ has size 2 while the only stable
matching $S=\\{(a_{1},b_{1})\\}$ has size 1.

Hence forbidding blocking edges constrains the size of the resulting matching.
Rather than empower every edge with a “veto power” to block matchings (this is
the notion of stability), we would like to relax stability so that the power
to block matchings gets diffused among all the vertices. That is, rather than
a single pair of vertices declaring that a given matching is infeasible, we
now want all the vertices to participate in deciding if a given matching is
feasible or not. The motivation is to obtain a larger pool of feasible
matchings in order to obtain improved matchings with respect to size or any
other desired objective.

#### Popularity.

The notion of popularity is a natural relaxation of stability that captures
collective welfare. Consider an election between two matchings $M$ and $N$
where vertices are voters. Preferences of a vertex over its neighbors extend
naturally to preferences over matchings—in the $M$ versus $N$ election, each
vertex votes for the matching in $\\{M,N\\}$ that it prefers, i.e., where it
gets a better assignment. Note that a vertex abstains from voting if it has
the same assignment in both $M$ and $N$; also, being left unmatched is the
worst choice for any vertex. Let $\phi(M,N)$ (resp., $\phi(N,M)$) be the
number of votes for $M$ (resp., $N$) in this election.

###### Definition 1

A matching $M$ is popular if $\phi(M,N)\geq\phi(N,M)$ for all matchings $N$ in
$G$.

So a popular matching never loses a head-to-head election against any
matching, in other words, it is a weak Condorcet winner [5, 6] in the voting
instance where matchings are candidates and vertices are voters. The notion of
popularity was introduced by Gärdenfors [12] who showed that every stable
matching is popular. So popular matchings always exist in any marriage
instance. In fact, every stable matching is a min-size popular matching [14].
Going to back to our earlier example on the four vertices
$a_{0},a_{1},b_{0},b_{1}$, the matching
$M_{\max}=\\{(a_{0},b_{1}),(a_{1},b_{0})\\}$, though unstable, is popular.
There are efficient algorithms to compute a max-size popular matching [14,
16].

Popular matchings are suitable in applications such as matching students to
projects where students and project advisers have strict preferences. By
relaxing stability to popularity, we can obtain better matchings in terms of
size (as in the above example) or some other desired objective. We consider a
natural and relevant objective here: observe that the two sides of $G=(A\cup
B,E)$ are asymmetric in this application—students are the doers of the
projects, i.e., they are the main or more active players, while project
advisers are the secondary or more passive players. So along with overall
popularity, we would like to maintain “popularity within the set $A$”.

That is, we would like the popular matching that we compute to be popular even
when we only count the votes of vertices in the set $A$, so there should be no
matching that is preferred by more vertices in $A$. Popularity within the set
$A$ is the notion of popularity with one-sided preferences and we will refer
to this as $A$-popularity here. In the $M$ versus $N$ election, let
$\phi_{A}(M,N)$ (resp., $\phi_{A}(N,M)$) be the number of vertices in $A$ that
vote for $M$ (resp., $N$).

###### Definition 2

A matching $M$ is $A$-popular if $\phi_{A}(M,N)\geq\phi_{A}(N,M)$ for all
matchings $N$ in $G$.

Matchings that are $A$-popular have been well-studied [2, 19, 20, 21] and
$A$-popular matchings are relevant in applications such as assigning training
posts to applicants [2] and housing allocation schemes [20] where vertices on
only one side of the graph have preferences over their neighbors. An
$A$-popular matching need not necessarily exist in a given instance. Consider
the following instance on three agents $a_{1},a_{2},a_{3}$ where all the
agents have identical preferences as shown below.

$a_{1}:b_{1}\succ b_{2}\succ b_{3}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \
a_{2}:b_{1}\succ b_{2}\succ b_{3}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \
a_{3}:b_{1}\succ b_{2}\succ b_{3}.$

It is easy to check that none of the matchings in the above instance is
$A$-popular. Let $M_{0}=\\{(a_{1},b_{1}),(a_{2},b_{2}),(a_{3},b_{3})\\}$ and
$M_{1}=\\{(a_{1},b_{3}),(a_{2},b_{1}),(a_{3},b_{2})\\}$. We have
$\phi_{A}(M_{1},M_{0})=2>1=\phi_{A}(M_{0},M_{1})$ since $a_{2}$ and $a_{3}$
prefer $M_{1}$ to $M_{0}$ while $a_{1}$ prefers $M_{0}$ to $M_{1}$. Similarly,
for any matching $M$ in this instance, there exists some other matching that
is more “$A$-popular” than $M$. Thus the above instance has no $A$-popular
matching.

We now seek matchings that are both popular and $A$-popular. So let us define
the following subclass of popular matchings.

###### Definition 3

A popular matching $M$ in $G=(A\cup B,E)$ is fully popular if $M$ is also
$A$-popular. So for any matching $N$ in $G$, we have: $\phi(M,N)\geq\phi(N,M)$
and $\phi_{A}(M,N)\geq\phi_{A}(N,M)$.

There may be exponentially many popular matchings in $G=(A\cup B,E)$. So when
$A$ is the more important/active side, say it consists of those doing their
projects/internships/jobs, it is natural to seek a popular matching that is
$A$-popular as well, i.e., a fully popular matching. We show the following
result here.

######  Theorem 1.1 ()

There is a linear time algorithm to decide if a marriage instance $G=(A\cup
B,E)$ with strict preferences admits a fully popular matching or not. If so,
our algorithm returns a max-size fully popular matching.

###  1.1 Background and Related results

The notion of popularity was proposed by Gärdenfors [12] in 1975. Algorithms
in the domain of popular matchings were first studied in 2005 for one-sided
preferences or the $A$-popular matching problem. Efficient algorithms were
given in [2] to decide if a given instance (with ties permitted in
preferences) admits an $A$-popular matching or not; in particular, a linear
time algorithm was given for the case with strict preferences.

Algorithms for popular matchings in a marriage instance $G=(A\cup B,E)$ or
two-sided preferences have been well-studied in the last decade. The max-size
popular matching algorithms in [14, 16] compute special popular matchings
called dominant matchings. A linear time algorithm for finding a popular
matching with a given edge $e$ was given in [7] (such an edge is called a
popular edge). It was shown in [7] that if $e$ is a popular edge then there is
either a stable matching or a dominant matching with the edge $e$.

Popular half-integral matchings in $G=(A\cup B,E)$ were characterized in [17]
as stable matchings in a larger graph related to $G$. The popular fractional
matching polytope was analyzed in [15] where the half-integrality of this
polytope was shown. Other than algorithms for min-size/max-size popular
matchings and for the popular edge problem, no other polynomial-time
algorithms were known for finding popular matchings with special properties.

To complete the picture, it was shown in [8] that it is NP-hard to decide if
$G$ admits a popular matching that is neither a min-size nor a max-size
popular matching. A host of hardness results in [8] painted a bleak picture
for efficient algorithms for popular matching problems (other than what is
already known). For instance, it is NP-hard to find a popular matching in $G$
with a given pair of edges. Thus finding a max-weight (resp., min-cost)
popular matching is NP-hard when there are weights (resp., costs) on edges.

###  1.2 Our Result and Techniques

It may be the case that no min-size or max-size popular matching in $G$ is
$A$-popular, however $G$ admits a fully popular matching; Section 2 has such
an example. As there are instances where it is NP-hard to decide if there
exists a popular matching that is neither a min-size nor a max-size popular
matching [8], a first guess may be that the fully popular matching problem is
NP-hard.

Though an $A$-popular matching is constrained to use only some special edges
in $G$ (see Theorem 2.1), this does not seem very helpful since it is NP-hard
to solve the popular matching problem with forced edges [8]. Note that a rival
matching is free to use any edge in $G$. It was not known if there was any
tractable subclass of popular matchings other than the classes of stable
matchings [10] and dominant matchings [7, 14, 16].

We show the set of fully popular matchings is a new tractable subclass of
popular matchings. Unlike the classes of stable matchings and dominant
matchings which are always non-empty, there need not exist a fully popular
matching in $G$. Our algorithm for finding a fully popular matching is based
on the classical Gale-Shapley algorithm and works in a new graph $H$. This
graph $H$ is essentially two copies of $G$ and is a variant of the graph seen
in [17] to study popular half-integral matchings. There is a natural map from
the set of stable matchings in $H$ to the set of popular half-integral
matchings in $G$. Our goal is to compute a stable matching with sufficient
symmetry in $H$ so that we can obtain a popular integral matching in $G$.

We achieve this symmetry by using properties of both popular and $A$-popular
matchings. These properties allow us to identify certain edges that have to be
excluded from our matching. If there is no stable matching in $H$ without
these edges then we use the lattice structure on stable matchings [13] to show
that $G$ has no fully popular matching. Else we obtain a matching $M$ in $G$
from this “partially symmetric” stable matching in $H$. The most technical
part of our analysis is to prove $M$’s popularity in $G$.

#### Organization of the paper.

Section 2 discusses preliminaries on popular matchings and $A$-popular
matchings. Our algorithm is presented in Section 3 and its correctness is
proved in Section 4.

##  2 Preliminaries

Our input is a bipartite graph $G=(A\cup B,E)$ where every vertex has a strict
preference order on its neighbors. Let us augment $G$ with self-loops, so each
vertex is assumed to be at the bottom of its own preference list. Hence for
any vertex, being matched along a self-loop will be equivalent to what was
originally the state of being left unmatched. Thus popularity (resp.,
$A$-popularity) in the augmented instance is equivalent to popularity (resp.,
$A$-popularity) in the original instance.

We will first present the characterization of $A$-popular matchings—note that
preferences of vertices in $B$ play no role here. For each $a\in A$, define
the vertex $f(a)$ to be $a$’s top choice neighbor and let $s(a)$ be $a$’s most
preferred neighbor that is nobody’s top choice neighbor. We assume every $a\in
A$ has at least one neighbor other than itself, so $f(a)\in B$, however it may
be the case that $s(a)=a$. The following characterization of $A$-popular
matchings was given in [2]. Let $E^{\prime}=E\cup\\{(u,u):u\in A\cup B\\}$.

######  Theorem 2.1 ([2])

A matching $M$ in $G=(A\cup B,E^{\prime})$ is $A$-popular if and only if:

  1. 1.

$M\subseteq\\{(a,f(a)),(a,s(a)):a\in A\\}$.

  2. 2.

$M$ matches all in $A$ and all in $\\{f(a):a\in A\\}$.

Thus any $A$-popular matching $M$ has to match every $a\in A$ to either $f(a)$
or $s(a)$. Furthermore, any job $b\in B$ that is some agent’s top choice
neighbor has to be matched in $M$ to an agent $a\in A$ such that $b=f(a)$,
i.e., $a$ regards $b$ as its top choice neighbor.

#### Popular matchings.

We will use an LP-based characterization of popular matchings [17, 19] in a
marriage instance $G$. Recall that we augmented the edge set $E$ with self-
loops. It will be convenient to view any matching in the original instance as
a perfect matching in the augmented instance $G=(A\cup B,E^{\prime})$ by using
self-loops to match all the vertices originally left unmatched.

Let $M$ be any perfect matching in $G=(A\cup B,E^{\prime})$. For any vertex
$u$, let $M(u)$ be $u$’s partner in $M$. For any pair of adjacent vertices $u$
and $v$, let $u$’s vote for $v$ versus $M(u)$ be $1$ if $u$ prefers $v$ to
$M(u)$, it is $-1$ if $u$ prefers $M(u)$ to $v$, else it is 0 (in this case
$M(u)=v$). In order to check if $M$ is popular or not in $G$, the following
edge weight function $\mathsf{wt}_{M}$ will be useful. Note that
$\mathsf{wt}_{M}(a,b)$ is the sum of votes of $a$ and $b$ for each other
versus their respective assignments in $M$.

For any $(a,b)\in E$:

$\mathsf{wt}_{M}(a,b)=\begin{cases}2&\text{if\ $(a,b)$\ is\ a\ blocking\ edge\
to\ $M$;}\\\ -2&\text{if\ both\ $a$\ and\ $b$\ prefer\ their\ partners\ in\
$M$\ to\ each\ other;}\\\ 0&\text{otherwise.}\end{cases}$

Thus $\mathsf{wt}_{M}(a,b)=0$ for every $(a,b)\in M$. We need to define
$\mathsf{wt}_{M}$ for self-loops as well. For any $u\in A\cup B$:

$\mathsf{wt}_{M}(u,u)=\begin{cases}0&\text{if\ $(u,u)\in M$;}\\\
-1&\text{otherwise.}\end{cases}$

For any perfect matching $N$ in $G$, observe that
$\mathsf{wt}_{M}(N)=\sum_{e\in N}\mathsf{wt}_{M}(e)=\phi(N,M)-\phi(M,N)$. Thus
$M$ is popular if and only if $\mathsf{wt}_{M}(N)\leq 0$ for every perfect
matching $N$ in $G$.

Consider the max-weight perfect matching LP in $G$ with the edge weight
function $\mathsf{wt}_{M}$. This linear program is (LP1) given below and (LP2)
is the dual of (LP1). The variables $x_{e}$ for $e\in E^{\prime}$ are primal
variables and the variables $y_{u}$ for $u\in A\cup B$ are dual variables.
Here $\delta^{\prime}(u)=\delta(u)\cup\\{(u,u)\\}$.

$\displaystyle\max\sum_{e\in E^{\prime}}\mathsf{wt}_{M}(e)\cdot x_{e}$ (LP1)
$\displaystyle\text{s.t.}\qquad\sum_{e\in\delta^{\prime}(u)}x_{e}=1$
$\displaystyle\mbox{\hskip 7.22743pt}\forall\,u\in A\cup B$ $\displaystyle
x_{e}\geq 0$ $\displaystyle\mbox{}\forall\,e\in E^{\prime}.$

$\displaystyle\min\sum_{u\in A\cup B}y_{u}$ (LP2)
$\displaystyle\text{s.t.}\qquad y_{a}+y_{b}\geq\mathsf{wt}_{M}(a,b)$
$\displaystyle\mbox{\hskip 7.22743pt}\forall\,(a,b)\in E$ $\displaystyle
y_{u}\geq\mathsf{wt}_{M}(u,u)$ $\displaystyle\mbox{\hskip
13.73148pt}\forall\,u\in A\cup B.$

$M$ is popular if and only if the optimal value of (LP1) is at most 0. In
fact, the optimal value is exactly 0 since $M$ is a perfect matching in $G$
and $\mathsf{wt}_{M}(M)=0$. Thus $M$ is popular if and only if the optimal
value of (LP2) is 0 (by LP-duality).

######  Theorem 2.2 ([17, 19])

A matching $M$ in $G=(A\cup B,E^{\prime})$ is popular if and only if there
exists $\vec{\alpha}\in\\{0,\pm 1\\}^{n}$ (where $|A\cup B|=n$) such that
$\sum_{u\in A\cup B}\alpha_{u}=0$ along with

$\alpha_{a}+\alpha_{b}\geq\mathsf{wt}_{M}(a,b)\ \ \ \forall(a,b)\in E\ \ \ \ \
\ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \alpha_{u}\geq\mathsf{wt}_{M}(u,u)\ \ \
\forall u\in A\cup B.$

###### Proof

The constraint matrix of (LP2) is totally unimodular. This is because $E$ is
the edge set of a bipartite graph and adding self-loops preserves the total
unimodularity of the constraint matrix. So (LP2) admits an optimal solution
that is integral. Let $\vec{\alpha}$ be an integral optimal solution of (LP2).
Hence $\vec{\alpha}\in\mathbb{Z}^{n}$. We need to show that
$\vec{\alpha}\in\\{0,\pm 1\\}^{n}$.

We have $\alpha_{u}\geq\mathsf{wt}_{M}(u,u)\geq-1$ for all $u\in A\cup B$.
Since $M$ is an optimal solution to (LP1), complementary slackness implies
that $\alpha_{u}+\alpha_{v}=\mathsf{wt}_{M}(u,v)=0$ for each edge $(u,v)\in
M$. Thus $\alpha_{u}=-\alpha_{v}\leq 1$ for every vertex $u$ matched to a non-
trivial neighbor $v$ in $M$.

Regarding any vertex $u$ such that $(u,u)\in M$, we again have by
complementary slackness $\alpha_{u}=\mathsf{wt}_{M}(u,u)=0$. Hence
$\vec{\alpha}\in\\{0,\pm 1\\}^{n}$. ∎

For any popular matching $M$, a vector $\vec{\alpha}$ as given in Theorem 2.2
will be called a witness of $M$’s popularity. A popular matching may have
several witnesses. A stable matching $S$ in $G$ has $\vec{\alpha}=0^{n}$ as a
witness since $\mathsf{wt}_{S}(e)\leq 0$ for all $e\in E^{\prime}$.

#### An interesting example.

Recall that our problem is to compute a fully popular matching, i.e., a
popular matching that is also $A$-popular. It is easy to construct instances
that admit $A$-popular matchings but admit no fully popular matching. It could
also be the case that no min-size or max-size popular matching in $G=(A\cup
B,E)$ is $A$-popular, however $G$ has a fully popular matching. Consider the
instance $G$ given in Fig. 1. Vertex preferences are indicated on edges: 1
denotes top choice, 2 denotes second choice, and so on.

$1$$2$$1$$1$$1$$1$$1$$2$$2$$1$$1$$2$$2$$2$$2$$1$$3$$1$$1$$1$$b$$b^{\prime}$$p^{\prime}$$q$$x^{\prime}$$y^{\prime}$$y$$p$$a^{\prime}$$a$$x$$q^{\prime}$$2$$3$$4$$2$

Figure 1: An instance on $A=\\{a,a^{\prime},p,p^{\prime},x,x^{\prime}\\}$ and
$B=\\{b,b^{\prime},q,q^{\prime},y,y^{\prime}\\}$ where no min-size/max-size
popular matching is $A$-popular. There is a fully popular matching (on blue
edges) here.

We list the vertices $f(u)$ and $s(u)$ for each $u\in A$ in this instance.
Observe that the vertex $b^{\prime}$ is not $s(a)$ since $a$ prefers
$q^{\prime}$ to $b^{\prime}$ and $q^{\prime}\neq f(u)$ for any $u\in A$.

  * •

We have $f(a)=f(a^{\prime})=b$, $f(p)=f(p^{\prime})=q$, and
$f(x)=f(x^{\prime})=y$.

  * •

We have $s(a)=s(p)=s(p^{\prime})=s(x^{\prime})=q^{\prime}$, $s(x)=y^{\prime}$,
and $s(a^{\prime})=a^{\prime}$.

Since $s(u)\neq u$ for $u\in\\{a,p,p^{\prime},x,x^{\prime}\\}$, any
$A$-popular matching $M$ has to match these 5 vertices to neighbors in $B$ (by
Theorem 2.1). So $q^{\prime}$, which is $s(a)$, has to be matched to one of
$p,p^{\prime}$. Thus $M(a)=f(a)=b$ which implies that
$M(a^{\prime})=s(a^{\prime})=a^{\prime}$. That is, after pruning self-loops
from $M$, the vertex $a^{\prime}$ has to be left unmatched in $M$. So $M$ has
size 5.

The matching $S=\\{(a,b),(p,q),(p^{\prime},q^{\prime}),(x,y)\\}$ is stable.
Thus any min-size popular matching in $G$ has size 4. The perfect matching
$M_{\max}=\\{(a,b^{\prime}),(a^{\prime},b),(p,q),(p^{\prime},q^{\prime}),(x,y^{\prime}),(x^{\prime},y)\\}$
is popular, so any max-size popular matching in $G$ has size 6. Thus no min-
size or max-size popular matching in $G$ can be $A$-popular. Interestingly,
this instance admits a fully popular matching; it is easy to check that the
matching
$M=\\{(a,b),(p,q),(p^{\prime},q^{\prime}),(x,y^{\prime}),(x^{\prime},y)\\}$ is
both popular and $A$-popular.

##  3 Fully Popular Matchings

We are given a marriage instance $G=(A\cup B,E)$. Recall that we augmented $G$
with self-loops. So henceforth $G=(A\cup B,E^{\prime})$ where
$E^{\prime}=E\cup\\{(u,u):u\in A\cup B\\}$. Our algorithm will work in a
bipartite graph $H$ which is essentially two copies of the graph $G$ as shown
in Fig. 2. The vertex set of $H$ is $A_{L}\cup B_{L}$ on the left and
$B_{R}\cup A_{R}$ on the right. Here $A_{L}=\\{a_{\ell}:a\in A\\}$ and
$A_{R}=\\{a_{r}:a\in A\\}$. Similarly, $B_{L}=\\{b_{\ell}:b\in B\\}$ and
$B_{R}=\\{b_{r}:b\in B\\}$.

$\mathrm{half}$$\mathrm{Lower}$$\mathrm{half}$$\mathrm{Upper}$$B_{R}$$A_{R}$$A_{L}$$B_{L}$

Figure 2: The bipartite graph $H$ consists of two copies of the graph
$G=(A\cup B,E)$.

The upper half of $H$ consists of the set $A_{L}$ of agents on the left and
the set $B_{R}$ of jobs on the right while the lower half of $H$ consists of
the set $B_{L}$ of jobs on the left and the set $A_{R}$ of agents on the
right. Thus every vertex $u\in A\cup B$ has two copies in $H$: one as
$u_{\ell}$ on the left of $H$ and another as $u_{r}$ on the right of $H$.

For every edge in $E$, there will be four edges in $H$: a pair of parallel
edges in the upper half and a pair of parallel edges in the lower half. In
order to distinguish two parallel edges with the same endpoints, we use
superscripts $+$ and $-$ on the endpoints. For any $(a,b)\in E$:

  * •

in the upper half, there are two parallel edges $(a_{\ell}^{+},b_{r}^{-})$ and
$(a_{\ell}^{-},b_{r}^{+})$ between $a_{\ell}$ and $b_{r}$;

  * •

in the lower half, there are two parallel edges $(b_{\ell}^{+},a_{r}^{-})$ and
$(b_{\ell}^{-},a_{r}^{+})$ between $b_{\ell}$ and $a_{r}$.

Remark. A pair of parallel edges $(u^{+},v^{-})$ and $(u^{-},v^{+})$ can be
visualized as a bidirected pair $u\rightarrow v$ and $u\leftarrow v$. We
prefer to use superscripts instead of directions since these $+/-$
superscripts will be related to witnesses of popular matchings (see Lemma 1).

Corresponding to every self-loop $(u,u)$, there is a single edge
$(u_{\ell}^{-},u_{r}^{+})$ in $H$. For convenience, we have used $+/-$
superscripts on the endpoints of this edge also. These edges
$(u_{\ell}^{-},u_{r}^{+})$ for all $u\in A\cup B$ are the only edges in $H$
that go across the two halves of $H$.

Vertices in $H$ have preferences on their incident edges rather than on their
neighbors. However it would be more convenient to say $u$ prefers $v^{-}$ to
$w^{+}$ rather than say $u$ prefers $(u^{+},v^{-})$ to $(u^{-},w^{+})$. In
fact, $H$ is equivalent to a conventional graph $H^{*}$ (with preferences on
neighbors) that was used to study popular half-integral matchings in [17]:
there were 4 vertices in $H^{*}$ for each $u\in A\cup B$. The graph $H$ is a
sparser version of $H^{*}$ with only 2 vertices $u_{\ell}$ and $u_{r}$ for
each $u\in A\cup B$ and a pair of parallel edges between every pair of
adjacent vertices. We now describe the preferences of vertices in $H$.

Preferences in $H$. Every vertex prefers superscript $-$ neighbors to
superscript $+$ neighbors; among superscript $-$ neighbors (similarly,
superscript $+$ neighbors), it will be its original preference order. Consider
any vertex $u\in A\cup B$. Suppose $u$’s preference order in the original
instance $G=(A\cup B,E)$ is $v\succ v^{\prime}\succ\cdots\succ
v^{\prime\prime}$, i.e., $u$’s top choice is $v$, second choice is
$v^{\prime}$, and so on. In $H$, the preference order of $u_{\ell}$ is as
follows:

$\underbrace{v^{-}_{r}\succ v^{\prime-}_{r}\succ\cdots\succ
v^{\prime\prime-}_{r}}_{\text{superscript\ $-$\
neighbors}}\succ\underbrace{v^{+}_{r}\succ v^{\prime+}_{r}\succ\cdots\succ
v^{\prime\prime+}_{r}\succ u^{+}_{r}}_{\text{superscript\ $+$\ neighbors}},$

where $v_{r},v^{\prime}_{r},\ldots$ correspond to the copies of
$v,v^{\prime},\ldots$ on the right side of $H$.

Observe that the vertex $u^{+}_{r}$ is the last choice of $u_{\ell}$. In $H$,
the preference order of $u_{r}$ is as follows:

$\underbrace{v^{-}_{\ell}\succ v^{\prime-}_{\ell}\succ\cdots\succ
v^{\prime\prime-}_{\ell}\succ u^{-}_{\ell}}_{\text{superscript\ $-$\
neighbors}}\succ\underbrace{v^{+}_{\ell}\succ
v^{\prime+}_{\ell}\succ\cdots\succ
v^{\prime\prime+}_{\ell}}_{\text{superscript\ $+$\ neighbors}},$

where $v_{\ell},v^{\prime}_{\ell},\ldots$ correspond to the copies of
$v,v^{\prime},\ldots$ on the left side of $H$. This is analogous to
$u_{\ell}$’s preference order—the main difference is in the position of its
twin—note that the vertex $u_{r}$ prefers $u^{-}_{\ell}$ to all its
superscript $+$ neighbors.

#### Blocking edges.

For any matching $M$ in $H$, we say an edge $(u_{\ell}^{+},v_{r}^{-})$, where
$u_{\ell}\in A_{\ell}\cup B_{\ell}$ and $v_{r}\in A_{r}\cup B_{r}$, blocks $M$
if the following two conditions hold:

  1. 1.

$u_{\ell}$ prefers $v_{r}^{-}$ to its assignment in $M$ and

  2. 2.

$v_{r}$ prefers $u_{\ell}^{+}$ to its assignment in $M$.

Similarly, we say $(u_{\ell}^{-},v_{r}^{+})$ blocks $M$ if $u_{\ell}$ prefers
$v_{r}^{+}$ to its assignment in $M$ and $v_{r}$ prefers $u_{\ell}^{-}$ to its
assignment in $M$.

###### Definition 4

A matching $M$ in $H$ is stable if no edge in $H$ blocks $M$.

For any perfect matching $S$ in $G=(A\cup B,E^{\prime})$, there is a
corresponding matching $S^{\prime}$ in $H$ where
$S^{\prime}=\\{(a^{-}_{\ell},b^{+}_{r}),(b^{-}_{\ell},a^{+}_{r}):(a,b)\in
S\cap E\\}\cup\\{(u^{-}_{\ell},u^{+}_{r}):(u,u)\in S\\}$. So $S^{\prime}$ is a
perfect matching in $H$. The following claim will be useful to us.

###### Claim 1

If $S$ is stable in $G$ then $S^{\prime}$ is stable in $H$.

###### Proof

We need to show that no edge in $H$ blocks $S^{\prime}$. Consider any edge
$(a^{+}_{\ell},b^{-}_{r})$ in $H$ where $a\in A$ and $b\in B$. By the
definition of the matching $S^{\prime}$, some edge $(\ast,b^{+}_{r})\in
S^{\prime}$. Since every vertex prefers superscript $-$ neighbors to
superscript $+$ neighbors, the vertex $b_{r}$ prefers its partner in
$S^{\prime}$ to $a^{+}_{\ell}$. Thus the edge $(a^{+}_{\ell},b^{-}_{r})$ does
not block $S^{\prime}$.

So consider any edge $(a^{-}_{\ell},b^{+}_{r})$ in $H$. If $(a,b)\in S$ then
$(a^{-}_{\ell},b^{+}_{r})\in S^{\prime}$ and so it does not block
$S^{\prime}$. If $(a,b)\notin S$ then it follows from the stability of $S$ in
$G$ that:

  1. 1.

either $a$ is matched to a neighbor $d$ preferred to $b$

  2. 2.

or $b$ is matched to a neighbor $c$ preferred to $a$.

In the first case, $a_{\ell}$ is matched in $S^{\prime}$ to a neighbor
$d^{+}_{r}$ preferred to $b^{+}_{r}$; in the second case, $b_{r}$ is matched
in $S^{\prime}$ to a neighbor $c^{-}_{\ell}$ preferred to $a^{-}_{\ell}$. Thus
$(a^{-}_{\ell},b^{+}_{r})$ does not block $S^{\prime}$.

It can analogously be shown that neither $(b^{-}_{\ell},a^{+}_{r})$ nor
$(b^{+}_{\ell},a^{-}_{r})$ blocks $S^{\prime}$. Also
$(u^{-}_{\ell},u^{+}_{r})$ for any $u\in A\cup B$ does not block $S^{\prime}$
since $u^{+}_{r}$ is $u_{\ell}$’s least preferred neighbor in $H$. Hence
$S^{\prime}$ is a stable matching in $H$. ∎

Thus the graph $H$ admits a perfect stable matching. Since all stable
matchings in $H$ have the same size [11], every stable matching in $H$ has to
be perfect. We seek to compute a “special” stable matching in $H$: one that
has no edge that is forbidden. The edges that will be marked forbidden are
those that no fully popular matching can use. The definition of valid edges
given below is as given in Theorem 2.1: any $A$-popular matching in $G$ has to
contain only these edges/self-loops.

###### Definition 5

Edges/self-loops in $\\{(a,f(a)),(a,s(a)):a\in A\\}$ are valid. So are self-
loops in $\\{(b,b):b\neq f(a)\ \mathrm{for\ any}\ a\in A\\}$. All other edges
and self-loops are invalid.

Thus every $a\in A$ has exactly two valid edges incident to it: one of these
may be the self-loop $(a,a)$. Note that a job $b\in B$ may have several valid
edges incident to it.

An edge $e$ in $G$ is called popular if there exists a popular matching $M$ in
$G$ that contains $e$. Similarly, a vertex is called stable if it is matched
in some (equivalently, every [11]) stable matching. It is known that every
popular matching in $G$ has to match all stable vertices to genuine neighbors
[14]. So the self-loop $(u,u)$ is popular if and only if $u$ is unstable.

###### Definition 6

Call an edge $e$ in $E^{\prime}=E\cup\\{(u,u):u\in A\cup B\\}$ legal if $e$ is
valid and popular.

#### Forbidden edges.

A fully popular matching, by definition, has to contain only legal edges. So
if $(a,b)\in E$ is not legal then $(a_{\ell}^{+},b_{r}^{-})$,
$(a_{\ell}^{-},b_{r}^{+})$, $(b_{\ell}^{+},a_{r}^{-})$, and
$(b_{\ell}^{-},a_{r}^{+})$ are forbidden edges in the stable matching that we
seek to compute in $H$. Similarly, for any $u\in A\cup B$, if $(u,u)$ is not
legal then $(u_{\ell}^{-},u_{r}^{+})$ is a forbidden edge in our matching.

###### Definition 7

A matching $M$ in $H$ is legal if $M$ has no forbidden edge.

#### Symmetric matchings.

Call a matching $M$ in $H$ symmetric if for each edge $(a,b)$ in $E$, either
both $(a_{\ell},b_{r})$ and $(b_{\ell},a_{r})$ are in $M$ or neither is in
$M$. For convenience, we are not mentioning the $+/-$ superscripts on
$a_{\ell},a_{r},b_{\ell},b_{r}$. Loosely speaking, a symmetric matching $M$
has the same edges in the upper and lower halves of $H$. A symmetric matching
$M$ in $H$ will be called a realization of
$\tilde{M}=\\{(a,b):(a_{\ell},b_{r})\ \text{and}\ (b_{\ell},a_{r})\ \text{are\
in}\ M\\}$. Note that $\tilde{M}$ is a matching in $G$.

###### Lemma 1

Let $N$ be any fully popular matching in $G$. Then there exists a legal stable
matching in $H$ that is a realization of $N$.

###### Proof

Let $N$ be a fully popular matching in $G$ and let $\vec{\alpha}\in\\{0,\pm
1\\}^{n}$ be a witness of $N$’s popularity (see Theorem 2.2). For
$i\in\\{0,\pm 1\\}$, let $A_{i}$ be the set of vertices $a\in A$ with
$\alpha_{a}=i$ and let $B_{i}$ be the set of vertices $b\in B$ with
$\alpha_{b}=i$. Thus we have $A=A_{0}\cup A_{1}\cup A_{-1}$ and $B=B_{0}\cup
B_{1}\cup B_{-1}$.

We have $\alpha_{a}+\alpha_{b}=\mathsf{wt}_{N}(a,b)=0$ for each edge $(a,b)\in
N$: this is by complementary slackness on the linear program that is analogous
to (LP2) (so $\mathsf{wt}_{N}$ replaces $\mathsf{wt}_{M}$ in this LP). Since
$\alpha_{a}=-\alpha_{b}$ for every $(a,b)\in N$, we have $N\cap
E\subseteq(A_{0}\times B_{0})\cup(A_{-1}\times B_{1})\cup(A_{1}\times B_{-1})$
(see Fig. 3).

$A_{1}$$A_{-1}$$B_{1}$$B_{-1}$$B_{0}$$A_{0}$

Figure 3: The partition $A_{0}\cup A_{1}\cup A_{-1}$ of $A$ and $B_{0}\cup
B_{-1}\cup B_{1}$ of $B$.

We need to show a realization of $N$ in $H$ that is stable. We will use $N$’s
witness $\vec{\alpha}$ in $G$ to define the following symmetric matching
$N^{*}_{\alpha}$ in $H$. Note that this is similar to how popular half-
integral matchings were realized as stable matchings in a larger graph as
shown in [17].

  * •

For all $(a,b)\in N\cap(A_{-1}\times B_{1})$ do: add edges
$(a_{\ell}^{-},b_{r}^{+})$ and $(b_{\ell}^{+},a_{r}^{-})$ to $N^{*}_{\alpha}$.

  * •

For all $(a,b)\in N\cap(A_{1}\times B_{-1})$ do: add edges
$(a_{\ell}^{+},b_{r}^{-})$ and $(b_{\ell}^{-},a_{r}^{+})$ to $N^{*}_{\alpha}$.

  * •

For all $(a,b)\in N\cap(A_{0}\times B_{0})$ do: add edges
$(a_{\ell}^{-},b_{r}^{+})$ and $(b_{\ell}^{-},a_{r}^{+})$ to $N^{*}_{\alpha}$.

For each vertex $u$ such that $(u,u)\in N$, add $(u_{\ell}^{-},u_{r}^{+})$ to
$N^{*}_{\alpha}$. Thus $N^{*}_{\alpha}$ is a perfect matching in $H$. Observe
that for any vertex $u$, the sum of superscripts (where $\pm$ are interpreted
as $\pm 1$) of the vertices $u_{\ell}$ and $u_{r}$ on the edges in
$N^{*}_{\alpha}$ incident to them is exactly $2\alpha_{u}$.

###### Claim 2

The matching $N^{*}_{\alpha}$ is stable in $H$.

The proof of Claim 2 is based on the constraints that $\vec{\alpha}$ has to
satisfy and is given below. Moreover, the fact that $N$ is a fully popular
matching in $G$ implies that $N^{*}_{\alpha}$ is a legal matching in $H$. This
is because every edge used in $N$ is valid (resp., popular) as $N$ is
$A$-popular (resp., popular) in $G$. So $N^{*}_{\alpha}$ has no forbidden
edge. Thus $N^{*}_{\alpha}$ is a legal stable matching in $H$. ∎

#### Proof of Claim 2.

We need to show that $N^{*}_{\alpha}$ is a stable matching in $H$. Let us
consider any edge $(a^{-}_{\ell},b^{+}_{r})$ in $H$ and show that this edge
does not block $N^{*}_{\alpha}$. We can assume $a\neq b$ since the edge
$(a^{-}_{\ell},a^{+}_{r})$ cannot block $N^{*}_{\alpha}$ as $a^{+}_{r}$ is
$a_{\ell}$’s least preferred neighbor in $H$. Thus we can assume $(a,b)\in E$.

Recall that $N$ is a perfect matching (due to augmenting $G$ with self-loops).
Let $c=N(a)$ and $d=N(b)$. The matching $N^{*}_{\alpha}$ in $H$ was
constructed using a witness $\vec{\alpha}$ of $N$’s popularity in $G$. We have
the following cases depending on the values of $\alpha_{a}$ and $\alpha_{b}$.

  1. 1.

Suppose $\alpha_{a}=1$. This means $(a_{\ell}^{+},c^{-}_{r})\in
N^{*}_{\alpha}$ for some neighbor $c$ of $a$. Since every vertex prefers
superscript $-$ neighbors to superscript $+$ neighbors, the vertex $a_{\ell}$
prefers $c^{-}_{r}$ to $b^{+}_{r}$. Thus the edge $(a^{-}_{\ell},b^{+}_{r})$
does not block $N^{*}_{\alpha}$. Note that this argument is independent of the
value of $\alpha_{b}$, so it holds for all $\alpha_{b}\in\\{\pm 1,0\\}$.

  2. 2.

Suppose $\alpha_{a}=0$ and $\alpha_{b}=1$. Then $(a_{\ell}^{-},c^{+}_{r})$ and
$(d^{-}_{\ell},b^{+}_{r})$ are in $N^{*}_{\alpha}$ for some neighbors $c$ and
$d$ of $a$ and $b$, respectively. The edge covering constraint for the edge
$(a,b)$ tells us that $\alpha_{a}+\alpha_{b}=1\geq\mathsf{wt}_{N}(a,b)$. Since
$\mathsf{wt}_{N}(a,b)\in\\{0,\pm 2\\}$, this means $\mathsf{wt}_{N}(a,b)\leq
0$. So either (i) $a$ prefers $c$ to $b$ or (ii) $b$ prefers $d$ to $a$. In
the former case, $a_{\ell}$ prefers $c^{+}_{r}$ to $b^{+}_{r}$ and in the
latter case, $b_{r}$ prefers $d_{\ell}^{-}$ to $a_{\ell}^{-}$. Thus the edge
$(a^{-}_{\ell},b^{+}_{r})$ does not block $N^{*}_{\alpha}$.

  3. 3.

Suppose $\alpha_{a}=\alpha_{b}=0$. Either $(a,b)\in N$ which implies
$(a^{-}_{\ell},b^{+}_{r})\in N^{*}$ and so it does not block $N^{*}_{\alpha}$
or as analyzed in case 2 above, $(a_{\ell}^{-},c^{+}_{r})$ and
$(d^{-}_{\ell},b^{+}_{r})$ are in $N^{*}_{\alpha}$. Since
$\mathsf{wt}_{N}(a,b)\leq 0$, either (i) $a$ prefers $c$ to $b$ or (ii) $b$
prefers $d$ to $a$. So either $a_{\ell}$ prefers $c^{+}_{r}$ to $b^{+}_{r}$ or
$b_{r}$ prefers $d_{\ell}^{-}$ to $a_{\ell}^{-}$. Thus the edge
$(a^{-}_{\ell},b^{+}_{r})$ does not block $N^{*}_{\alpha}$.

  4. 4.

Suppose $\alpha_{a}\in\\{0,-1\\}$ and $\alpha_{b}=-1$. Then
$(a_{\ell}^{-},c^{+}_{r})$ and $(d^{+}_{\ell},b^{-}_{r})$ are in
$N^{*}_{\alpha}$ for some neighbors $c$ and $d$ of $a$ and $b$, respectively.
The edge covering constraint for $(a,b)$ tells us that
$\alpha_{a}+\alpha_{b}=-1\geq\mathsf{wt}_{N}(a,b)$. Since
$\mathsf{wt}_{N}(a,b)\in\\{0,\pm 2\\}$, this means
$\mathsf{wt}_{N}(a,b)\leq-2$. So both $a$ and $b$ prefer their partners in $N$
to each other. Hence $a_{\ell}$ prefers $c^{+}_{r}$ to $b^{+}_{r}$ and so
$(a^{-}_{\ell},b^{+}_{r})$ does not block $N^{*}_{\alpha}$.

  5. 5.

Suppose $\alpha_{a}=-1$ and $\alpha_{b}\in\\{0,1\\}$. Then
$(a_{\ell}^{-},c^{+}_{r})$ and $(d^{-}_{\ell},b^{+}_{r})$ are in
$N^{*}_{\alpha}$ for some neighbors $c$ and $d$ of $a$ and $b$, respectively.
The edge covering constraint for the edge $(a,b)$ is
$\alpha_{a}+\alpha_{b}=0\geq\mathsf{wt}_{N}(a,b)$. If $(a,b)\in N$ then
$(a^{-}_{\ell},b^{+}_{r})\in N^{*}$ and it does not block $N^{*}_{\alpha}$.
Otherwise either (i) $a$ prefers $c$ to $b$ or (ii) $b$ prefers $d$ to $a$. In
the former case, $a_{\ell}$ prefers $c^{+}_{r}$ to $b^{+}_{r}$ and in the
latter case, $b_{r}$ prefers $d_{\ell}^{-}$ to $a_{\ell}^{-}$. So
$(a^{-}_{\ell},b^{+}_{r})$ does not block $N^{*}_{\alpha}$.

Thus the edge $(a^{-}_{\ell},b^{+}_{r})$ does not block $N^{*}_{\alpha}$.
Analogous arguments show that no edge in $H$ blocks the matching
$N^{*}_{\alpha}$. Hence we can conclude that $N^{*}_{\alpha}$ is a stable
matching in $H$. ∎

#### Stable matchings with forbidden edges.

A stable matching that avoids all forbidden edges (if such a matching exists
in $H$) can be computed in linear time by running a variant of the Gale-
Shapley algorithm in $H$ where any proposal made along a forbidden edge is
rejected by the vertex receiving this proposal. Once a proposal received along
a forbidden edge is rejected by a vertex, all further proposals received along
worse edges also have to rejected by this vertex. If some vertex is left
unmatched at the end of this algorithm, then there is no stable matching in
$H$ that avoids all forbidden edges; else we have a desired stable matching in
$H$. We refer to [13] for details on this variant of the Gale-Shapley
algorithm.

Thus it can be efficiently checked if $H$ admits a legal stable matching or
not. If such a matching does not exist in $H$ then there is no fully popular
matching in $G$ (by Lemma 1). So we will assume henceforth that there exists a
legal stable matching in $H$. However the fact that such a stable matching
exists in $H$ does not imply that $G$ admits a fully popular matching. This is
because $H$ is made up of two copies of $G$, thus any matching $M^{*}$ in $H$
can only be mapped to a half-integral matching in $G$.

In order to claim the resulting matching in $G$ is integral, we need $M^{*}$
to be symmetric, i.e., we need $M^{*}$ to have the same edges in both halves
of $H$. We will not construct such a symmetric stable matching in $H$. The
matching we compute will have a certain amount of symmetry and this will be
enough to obtain a fully popular matching in $G$. If $H$ does not admit such a
partially symmetric stable matching, then we show that $G$ has no fully
popular matching.

###  3.1 Two partitions of the vertex set

We run the Gale-Shapley algorithm that avoids all forbidden edges [13] in $H$.
In this algorithm, vertices on the left of $H$ propose in decreasing order of
preference and vertices on the right of $H$ dispose. When $u_{\ell}\in
A_{L}\cup B_{L}$ proposes to $v_{r}^{-}$, this proposal is made along
$(u_{\ell}^{+},v_{r}^{-})$: so $v_{r}$ sees this as $u_{\ell}^{+}$’s proposal;
when $u_{\ell}$ proposes to $v_{r}^{+}$, this proposal is made along
$(u_{\ell}^{-},v_{r}^{+})$: so $v_{r}$ sees this as $u_{\ell}^{-}$’s proposal.

If $u_{\ell}$ proposes to a neighbor $v_{r}$ along $(u_{\ell}^{+},v^{-}_{r})$
or $(u_{\ell}^{-},v^{+}_{r})$, then $v_{r}$ (tentatively) accepts $u_{\ell}$’s
proposal only if the edge $(u,v)$ is legal; otherwise $v_{r}$ rejects
$u_{\ell}$’s proposal since this is a forbidden edge. Edges ranked worse than
$(u_{\ell}^{+},v^{-}_{r})$/$(u_{\ell}^{-},v^{+}_{r})$ (as the case may be)
will be deleted from the current instance—this ensures that once $v_{r}$
receives a proposal along a certain edge, whether this proposal is
(tentatively) accepted or not, $v_{r}$ cannot accept proposals made along
worse edges.

Let $S_{0}$ be the legal stable matching in $H$ that is obtained. The sets
$U_{A}$ and $U_{B}$ will be useful.

  * •

Let $U_{A}\subseteq A$ be the set of agents $a$ such that
$(a^{-}_{\ell},a^{+}_{r})\in S_{0}$.

  * •

Let $U_{B}\subseteq B$ be the set of jobs $b$ such that
$(b^{-}_{\ell},b^{+}_{r})\in S_{0}$.

We know that $H$ is made up of two halves: the upper half and the lower half.
Since $S_{0}$ is stable and thus perfect (recall that any stable matching in
$H$ is perfect), the set of agents matched to genuine neighbors—not to their
twins—in each half of $H$ is $A\setminus U_{A}$ and similarly, the set of jobs
matched to genuine neighbors in each half of $H$ is $B\setminus U_{B}$.

We now define the sets
$A_{+},A_{-},B_{+},B_{-},A^{\prime}_{+},A^{\prime}_{-},B^{\prime}_{+},B^{\prime}_{-}$.
Initially these sets are empty. Then we add vertices to them as described
below.

  * •

For every $(a^{+}_{\ell},b^{-}_{r})\in S_{0}$ where $a\in A$ and $b\in B$: add
$a$ to $A_{+}$ and $b$ to $B_{-}$.

  * •

For every $(a^{-}_{\ell},b^{+}_{r})\in S_{0}$ where $a\in A$ and $b\in B$: add
$a$ to $A_{-}$ and $b$ to $B_{+}$.

  * •

For every $(b^{+}_{\ell},a^{-}_{r})\in S_{0}$ where $a\in A$ and $b\in B$: add
$b$ to $B^{\prime}_{+}$ and $a$ to $A^{\prime}_{-}$.

  * •

For every $(b^{-}_{\ell},a^{+}_{r})\in S_{0}$ where $a\in A$ and $b\in B$: add
$b$ to $B^{\prime}_{-}$ and $a$ to $A^{\prime}_{+}$.

$\mathrm{Partition\ of}\ A\cup B\setminus U_{B}$$\mathrm{induced\ by}\ S_{0}\
\mathrm{in\ the\ upper\ half\ of}\ H$$\mathrm{Partition\ of}\ B\cup A\setminus
U_{A}$$\mathrm{induced\ by}\ S_{0}\ \mathrm{in\ the\ lower\ half\ of}\
H$$U_{B}$$U_{A}$$A_{-}$$B_{+}$$B^{\prime}_{-}$$A^{\prime}_{+}$$A_{+}$$B_{-}$$A^{\prime}_{-}$$B^{\prime}_{+}$

Figure 4: The two partitions of the set $(A\cup B)\setminus(U_{A}\cup U_{B})$
induced by the matching $S_{0}$.

We have $A\setminus U_{A}=A_{+}\cup A_{-}=A^{\prime}_{+}\cup A^{\prime}_{-}$
and $B\setminus U_{B}=B_{+}\cup B_{-}=B^{\prime}_{+}\cup B^{\prime}_{-}$. Fig.
4 denotes these partitions of $A\setminus U_{A}$ and $B\setminus U_{B}$
induced by the matching $S_{0}$ in the upper and lower halves of $H$. In this
figure, the set $U_{A}$ has been included in the upper half and the set
$U_{B}$ in the lower half.

We will use $(a^{-}_{\ell},\ast)$ to denote any edge in the set
$\\{(a^{-}_{\ell},b^{+}_{r}):b\in B\\}\cup\\{(a^{-}_{\ell},a^{+}_{r})\\}$.
Similarly $(\ast,a^{+}_{r})$ denotes any edge in the set
$\\{(b^{-}_{\ell},a^{+}_{r}):b\in B\\}\cup\\{(a^{-}_{\ell},a^{+}_{r})\\}$.
Similarly for $(b^{-}_{\ell},\ast)$ and $(\ast,b^{+}_{r})$. Recall that every
popular matching in $G$ has a witness $\vec{\alpha}\in\\{0,\pm 1\\}^{n}$ (see
Theorem 2.2).

The following lemma will be crucial to us.

###### Lemma 2

Let $N$ be a fully popular matching in $G$ and let $\vec{\alpha}$ be any
witness of $N$. If $a\in A_{-}\cap A^{\prime}_{+}$ then $\alpha_{a}=0$.

###### Proof

The vertex $a\in A_{-}\cap A^{\prime}_{+}$, where the sets $A_{-}$ and
$A^{\prime}_{+}$ are defined above. Let ${\cal D}_{0}$ be the set of legal
stable matchings in $H$. The set ${\cal D}_{0}$ forms a sublattice of the
lattice111The meet of 2 stable matchings $M$ and $M^{\prime}$ is the stable
matching where every $u$ in $A_{L}\cup B_{L}$ (resp., $A_{R}\cup B_{R}$) is
matched to its more (resp., less) preferred partner in
$\\{M(u),M^{\prime}(u)\\}$. The join of $M$ and $M^{\prime}$ is the stable
matching where every $u$ in $A_{L}\cup B_{L}$ (resp., $A_{R}\cup B_{R}$) is
matched to its less (resp., more) preferred partner in
$\\{M(u),M^{\prime}(u)\\}$. of stable matchings in $H$ and the matching
$S_{0}$ is the $(A_{L}\cup B_{L})$-optimal matching in ${\cal D}_{0}$ [13].
Since $a\in A_{-}$, we have $(a^{-}_{\ell},c^{+}_{r})\in S_{0}$ for some
neighbor $c^{+}_{r}$ of $a_{\ell}$. Thus $c^{+}_{r}$ is the most preferred
partner for $a_{\ell}\in A_{L}$ in all matchings in ${\cal D}_{0}$. Recall
that every vertex prefers superscript $-$ neighbors to superscript $+$
neighbors. Hence no matching in ${\cal D}_{0}$ matches $a_{\ell}$ to a
superscript $-$ neighbor, i.e., every legal stable matching in $H$ has to
contain $(a^{-}_{\ell},\ast)$.

$S_{0}$ is also the $(A_{R}\cup B_{R})$-pessimal matching in ${\cal D}_{0}$
[13]. Since $a\in A^{\prime}_{+}$, we have $(d_{\ell}^{-},a_{r}^{+})\in S_{0}$
for some neighbor $d^{-}_{\ell}$ of $a_{r}$. So every matching in ${\cal
D}_{0}$ has to match $a_{r}\in A_{R}$ to a neighbor at least as good as
$d_{\ell}^{-}$, i.e., every legal stable matching in $H$ has to contain
$(\ast,a_{r}^{+})$.

Suppose $N$ is a legal stable matching with a witness $\vec{\alpha}$ such that
$\alpha_{a}\in\\{\pm 1\\}$. If $\alpha_{a}=1$, i.e., if $a\in A_{1}$ (see Fig.
3), then there is a legal stable matching $N^{*}_{\alpha}$ in $H$ such that
$(a_{\ell}^{+},\ast)\in N^{*}_{\alpha}$ (see the proof of Lemma 1). This
contradicts our claim above that every legal stable matching in $H$ has to
contain $(a_{\ell}^{-},\ast)$. So $\alpha_{a}=-1$, i.e., $a\in A_{-1}$. Then
there is a legal stable matching $N^{*}_{\alpha}$ in $H$ such that
$(\ast,a_{r}^{-})\in N^{*}_{\alpha}$ (as shown in the proof of Lemma 1). This
again contradicts our claim above that every legal stable matching in $H$ has
to contain $(\ast,a_{r}^{+})$. Thus $\alpha_{a}\notin\\{\pm 1\\}$, hence
$\alpha_{a}=0$. ∎

###### Lemma 3

Let $N$ be a fully popular matching in $G$ and let $\vec{\alpha}$ be any
witness of $N$. If $b\in B_{+}\cap B^{\prime}_{-}$ then $\alpha_{b}=0$.

The proof of Lemma 3 is analogous to the proof of Lemma 2. We will use
$G_{0}=(A\cup B,E_{0})$ to denote the popular subgraph of $G=(A\cup
B,E^{\prime})$. The edge set $E_{0}$ of $G_{0}$ is the set of popular
edges/self-loops. The subgraph $G_{0}$ need not be connected and Lemma 4 will
be useful to us.

######  Lemma 4 ([9])

Let $C$ be any connected component in the popular subgraph $G_{0}$. For any
popular matching $N$ in $G$ and any witness $\vec{\alpha}$ of $N$: if
$\alpha_{v}=0$ for some $v\in C$ then $\alpha_{u}=0$ for all $u\in C$.

###### Proof

Consider any popular edge $(a,b)$. So there is some popular matching $M$ with
the edge $(a,b)$. The matching $M$ is an optimal solution to the max-weight
perfect matching LP with edge weight function $\mathsf{wt}_{N}$ since
$\mathsf{wt}_{N}(M)=\phi(M,N)-\phi(N,M)=0$: recall that $M$ and $N$ are
popular matchings in $G$. We know that $\vec{\alpha}$ is an optimal solution
to the dual LP. So it follows from complementary slackness that
$\alpha_{a}+\alpha_{b}=\mathsf{wt}_{N}(a,b)$. Since
$\mathsf{wt}_{N}(a,b)\in\\{\pm 2,0\\}$ (an even number), the integers
$\alpha_{a}$ and $\alpha_{b}$ have the same parity.

Let $u$ and $v$ be any two vertices in the same connected component in the
popular subgraph $G_{0}$. So there is a $u$-$v$ path $\rho$ in $G$ such that
every edge in $\rho$ is a popular edge. We have just seen that the endpoints
of each popular edge have the same parity in $\vec{\alpha}$. Hence
$\alpha_{u}$ and $\alpha_{v}$ have the same parity. Thus $\alpha_{v}=0$
implies $\alpha_{u}=0$. ∎

###  3.2 Our algorithm

Lemmas 2-4 motivate our algorithm which is described as Algorithm 1. The main
step of the algorithm is the while loop that takes any unmarked vertex $v$ in
$(A_{-}\cap A^{\prime}_{+})\cup(B_{+}\cap B^{\prime}_{-})$. Initially all
vertices are unmarked. Consider the first iteration of the algorithm: let
$v\in A$.

Lemma 2 tells us that for any fully popular matching $N$ and any witness
$\vec{\alpha}$ of $N$, we have $\alpha_{v}=0$. Lemma 4 tells us that
$\alpha_{u}=0$ for every vertex $u$ in the component $C$, where $C$ is $v$’s
connected component in $G_{0}$. The proof of Lemma 1 shows $N$ has a
realization $N^{*}_{\alpha}$ in $H$ such that $N^{*}_{\alpha}$ contains
$(a_{\ell}^{-},\ast)$ and $(\ast,a_{r}^{+})$ for every agent $a\in C$.

Thus we are interested in those legal stable matchings in $H$ that contain
$(a_{\ell}^{-},\ast)$ and $(\ast,a_{r}^{+})$ for every agent $a\in C$. Hence
our algorithm forbids all edges $(a_{\ell}^{+},\ast)$ and $(\ast,a_{r}^{-})$
for every agent $a\in C$ in the stable matching that we compute here. This
step is implemented by making every neighbor reject offers from $a_{\ell}^{+}$
(this may induce other rejections) and symmetrically, $a_{r}$ rejects all
offers from superscript $+$ neighbors. Note that the resulting matching may
contain $(a_{\ell}^{-},a_{r}^{+})$ for some of the agents $a$ in $C$. All the
vertices in $C$ get marked in this iteration.

Algorithm 1 Our algorithm to find a fully popular matching in $G=(A\cup
B,E^{\prime})$

1:Compute a legal stable matching $S_{0}$ in $H$ by running the Gale-Shapley
algorithm with forbidden edges. $\triangleright$ (Vertices in $A_{L}\cup
B_{L}$ propose and those in $B_{R}\cup A_{R}$ dispose. Any edge in $H$ whose
corresponding edge in $G$ is not legal is forbidden.)

2:Let $A_{-},A^{\prime}_{+}$ and $B_{+},B^{\prime}_{-}$ be as defined earlier
(see the start of Section 3.1).

3:Initially all vertices are unmarked and $i=0$.

4:while there exists an unmarked vertex $v\in(A_{-}\cap
A^{\prime}_{+})\cup(B_{+}\cap B^{\prime}_{-})$ do

5: $i=i+1$.

6: Modify $S_{i-1}$ to $S_{i}$ so as to forbid all edges $(a_{\ell}^{+},\ast)$
and $(\ast,a_{r}^{-})$ for every agent $a$ in $v$’s component in the popular
subgraph $G_{0}$. $\triangleright$ ($S_{i}$ is the $(A_{L}\cup B_{L})$-optimal
legal stable matching in $H$ that avoids all forbidden edges identified in the
first $i$ iterations of the while-loop.)

7: if there is no such legal stable matching $S_{i}$ in $H$ then

8: Return “No fully popular matching in $G$”.

9: Update the sets $A_{-},A^{\prime}_{+}$ and $B_{+},B^{\prime}_{-}$: these
correspond to $S_{i}$ now.

10: Mark all vertices in $v$’s component in the popular subgraph $G_{0}$.

11:Return $M=\\{(a,b)\in E:(a^{+}_{\ell},b^{-}_{r})\ \mathrm{or}\
(a^{-}_{\ell},b^{+}_{r})\ \mathrm{is\ in}\ S_{i}\\}$.

Recall that ${\cal D}_{0}$ is the set of legal stable matchings in $H$. Let
${\cal D}_{1}\subseteq{\cal D}_{0}$ be the set of all legal stable matchings
in $H$ that contain $(a_{\ell}^{-},\ast)$ and $(\ast,a_{r}^{+})$ for every
agent $a\in C$. Thus ${\cal D}_{1}$ is a sublattice of ${\cal D}_{0}$. We know
from the proof of Lemma 1 that $N^{*}_{\alpha}\in{\cal D}_{1}$ where $N$ is a
fully popular matching in $G$ and $\vec{\alpha}$ is any witness of $N$. So if
${\cal D}_{1}$ is empty then we can conclude that $G$ has no fully popular
matching. Otherwise, we have a matching $S_{1}\in{\cal D}_{1}$ with us and we
update the sets $A_{-},A^{\prime}_{+}$ and $B_{+},B^{\prime}_{-}$: these sets
are defined at the start of Section 3.1 and now $S_{1}$ replaces $S_{0}$ in
their definitions.

Let us assume we are now in the $i$-th iteration and let ${\cal D}_{i}$ be the
set of legal stable matchings in $H$ that avoid all edges forbidden by our
algorithm in the first $i$ iterations. In other words, ${\cal D}_{i}$ is the
set of those matchings in ${\cal D}_{i-1}$ where no edge identified as
forbidden in the $i$-th iteration is present. We have ${\cal
D}_{0}\supseteq{\cal D}_{1}\supseteq\cdots\supseteq{\cal
D}_{i-1}\supseteq{\cal D}_{i}$. For all $0\leq j\leq i$, the set ${\cal
D}_{j}$ forms a sublattice of the lattice of all stable matchings in $H$ [13].

###### Lemma 5

For every fully popular matching $N$ in $G$ and every witness $\vec{\alpha}$
of $N$, the realization $N^{*}_{\alpha}$ is an element of ${\cal D}_{i}$.

###### Proof

We need to show that $N^{*}_{\alpha}$ is an element of ${\cal D}_{i}$. We will
prove this by induction. We know from Lemma 1 that the base case is true,
i.e., $N^{*}_{\alpha}\in{\cal D}_{0}$. By induction hypothesis, let us assume
that for every fully popular matching $N$ and any witness $\vec{\alpha}$ of
$N$, the realization $N^{*}_{\alpha}$ is an element of ${\cal D}_{i-1}$. Since
the algorithm entered the $i$-th iteration of the while loop, there was an
unmarked vertex $x$ in $(A_{-}\cap A^{\prime}_{+})\cup(B_{+}\cap
B^{\prime}_{-})$ at the start of this iteration.

###### Claim 3

For any fully popular matching $N$ and any witness $\vec{\alpha}$ of $N$, we
have $\alpha_{x}=0$.

The proof of Claim 3 (this is similar to the proof of Lemma 2) is given below.
Claim 3 along with Lemma 4 tells us that for all vertices $u$ in $x$’s
component $C^{\prime}$ in $G_{0}$, we have $\alpha_{u}=0$. The proof of Lemma
1 shows us that $N^{*}_{\alpha}$ contains $(a_{\ell}^{-},\ast)$ and
$(\ast,a_{r}^{+})$ for every agent $a\in C^{\prime}$. Since
$N^{*}_{\alpha}\in{\cal D}_{i-1}$, it follows that $N^{*}_{\alpha}$ is an
element in ${\cal D}_{i}$. Thus for every fully popular matching $N$ in $G$
and every witness $\vec{\alpha}$ of $N$, the realization $N^{*}_{\alpha}$ is
an element of ${\cal D}_{i}$. ∎

#### Proof of Claim 3.

The matching $S_{i-1}$ that is computed in line 6 of the $(i-1)$-th iteration
is the $(A_{L}\cup B_{L})$-optimal matching in the lattice ${\cal D}_{i-1}$
[13]. Hence if $(x_{\ell}^{-},\ast)\in S_{i-1}$ for some $x_{\ell}\in
A_{L}\cup B_{L}$ then $(x_{\ell}^{-},\ast)$ belongs to every matching in
${\cal D}_{i-1}$. The matching $S_{i-1}$ is also the $(A_{R}\cup
B_{R})$-pessimal matching in the set ${\cal D}_{i-1}$ [13]. Hence if
$(\ast,x_{r}^{+})\in S_{i-1}$ for some $x_{r}\in A_{R}\cup B_{R}$ then
$(\ast,x_{r}^{+})$ belongs to every matching in ${\cal D}_{i-1}$.

If the above claim is false then there is a fully popular matching $N$ and a
witness $\vec{\alpha}$ of $N$ with $\alpha_{x}\in\\{\pm 1\\}$. If
$\alpha_{x}=1$ then there is a legal stable matching $N^{*}_{\alpha}$ in $H$
such that $(x_{\ell}^{+},\ast)\in N^{*}_{\alpha}$. If $\alpha_{x}=-1$ then
there is a legal stable matching $N^{*}_{\alpha}$ in $H$ such that
$(\ast,x^{-}_{r})\in N^{*}_{\alpha}$. Since $N^{*}_{\alpha}\in{\cal D}_{i-1}$,
both cases contradict our earlier observation that every matching in ${\cal
D}_{i-1}$ has to contain $(x_{\ell}^{-},\ast)$ and $(\ast,x^{+}_{r})$. Thus
for any fully popular matching $N$ and any witness $\vec{\alpha}$ of $N$, we
have $\alpha_{x}=0$. ∎

We now need to prove the correctness of our algorithm. Suppose the algorithm
returns “No fully popular matching in $G$”. Then this means that ${\cal
D}_{i}=\emptyset$ for some $i\geq 1$. Lemma 5 tells us that if ${\cal
D}_{i}=\emptyset$, then there is indeed no fully popular matching in $G$. This
finishes one part of our proof of correctness.

Suppose the algorithm does not return “No fully popular matching in $G$”.
Since at least one unmarked vertex gets marked in every iteration of the while
loop, the algorithm always terminates. So a matching $M$ is returned. We need
to show that $M$ is a fully popular matching in $G$. This is the tougher side
in the proof of correctness and this is proved in Section 4.

##  4 Popularity of the Matching $M$

In this section we complete the proof of correctness of Algorithm 1. We need
to show that the matching $M$ returned by Algorithm 1 is fully popular in $G$.
Let $S_{i}$ be the matching in $H$ computed in the final iteration of
Algorithm 1. Then $M$ is the matching (in $G$) induced by $S_{i}$ in the upper
half of $H$. The matching $M$ is as defined below:

$M=\\{(a,b)\in E:(a^{+}_{\ell},b^{-}_{r})\ \mathrm{or}\
(a^{-}_{\ell},b^{+}_{r})\ \mathrm{is\ in}\ S_{i}\\}.$

Note that $M\subseteq(A_{+}\times B_{-})\cup(A_{-}\times B_{+})$, where the
sets $A_{+},B_{-},A_{-},B_{+}$ are defined at the beginning of Section 3.1:
the matching $S_{i}$ replaces $S_{0}$ in the definitions of
$A_{+},B_{-},A_{-},B_{+},A^{\prime}_{+},B^{\prime}_{-},A^{\prime}_{-},B^{\prime}_{+}$
now. Similarly, let $L$ be the matching (in $G$) induced by $S_{i}$ in the
lower half of $H$. So we have:

$L=\\{(a,b)\in E:(b^{+}_{\ell},a^{-}_{r})\ \mathrm{or}\
(b^{-}_{\ell},a^{+}_{r})\ \mathrm{is\ in}\ S_{i}\\}.$

Thus $L\subseteq(A^{\prime}_{+}\times B^{\prime}_{-})\cup(A^{\prime}_{-}\times
B^{\prime}_{+})$. Let $U_{A}$ (resp., $U_{B}$) be the set of vertices $u$ in
$A$ (resp., $B$) such that $(u^{-}_{\ell},u^{+}_{r})\in S_{i}$. The vertices
in $U_{A}\cup U_{B}$ are unmatched in both $M$ and $L$.

Since $S_{i}$ is a legal stable matching in $H$, it matches all vertices in
$H$ using valid edges. Thus by Theorem 2.1, $M$ is $A$-popular.222In order to
apply Theorem 2.1, we ought to say $M\cup\\{(u,u):u\in U_{A}\cup U_{B}\\}$ is
$A$-popular. We need to show that $M$ is popular in $G$.

Theorem 4.1 is our starting point. The subgraph $G\setminus U_{B}$ is the
subgraph of $G$ induced on $A\cup(B\setminus U_{B})$ and similarly, the
subgraph $G\setminus U_{A}$ is the subgraph of $G$ induced on $(A\setminus
U_{A})\cup B$.

###### Theorem 4.1

The matching $M$ is popular in the subgraph $G\setminus U_{B}$. Also, the
matching $L$ is popular in the subgraph $G\setminus U_{A}$.

###### Proof

We will use Theorem 2.2 to prove the popularity of $L$ and $M$ in $G\setminus
U_{A}$ and $G\setminus U_{B}$, respectively. The popularity of $L$ in
$G\setminus U_{A}$ will be shown using the witness $\vec{\beta}$ defined below
and the popularity of $M$ in $G\setminus U_{B}$ will be shown using the
witness $\vec{\gamma}$ defined below.

  1. 1.

$\beta_{u}=1$ for $u\in A^{\prime}_{+}\cup B^{\prime}_{+}$, $\beta_{u}=-1$ for
$u\in A^{\prime}_{-}\cup B^{\prime}_{-}$, and $\beta_{u}=0$ for $u\in U_{B}$.

  2. 2.

$\gamma_{u}=1$ for $u\in A_{+}\cup B_{+}$, $\gamma_{u}=-1$ for $u\in A_{-}\cup
B_{-}$, and $\gamma_{u}=0$ for $u\in U_{A}$.

Observe that $\sum_{u\in(A\setminus U_{A})\cup B}\beta_{u}=0$. This is because
$L\subseteq(A^{\prime}_{+}\times B^{\prime}_{-})\cup(A^{\prime}_{-}\times
B^{\prime}_{+})$. Note that $\mathsf{wt}_{L}(u,u)=0$ for $u\in U_{B}$ and
$\mathsf{wt}_{L}(u,u)=-1$ for all $u\notin U_{A}\cup U_{B}$. Thus we have
$\beta_{u}\geq\mathsf{wt}_{L}(u,u)$ for all $u\in(A\setminus U_{A})\cup B$.

Similarly, $\sum_{u\in A\cup(B\setminus U_{B})}\gamma_{u}=0$. Also,
$\gamma_{u}\geq\mathsf{wt}_{M}(u,u)$ for all $u\in A\cup(B\setminus U_{B})$.

###### Claim 4

$\beta_{a}+\beta_{b}\geq\mathsf{wt}_{L}(a,b)$ for all edges $(a,b)$ where
$a\in A\setminus U_{A}$ and $b\in B$.

###### Claim 5

$\gamma_{a}+\gamma_{b}\geq\mathsf{wt}_{M}(a,b)$ for all edges $(a,b)$ where
$a\in A$ and $b\in B\setminus U_{B}$.

We will prove Claim 5 below. The proof of Claim 4 is analogous.

  * •

Case 1: let $a\in U_{A}$. We set $\gamma_{a}=0$ and we know that
$(a_{\ell}^{-},a_{r}^{+})\in S_{i}$. Recall that $a_{r}^{+}$ is $a_{\ell}$’s
least preferred neighbor, thus $a_{\ell}$ must have been rejected by all its
more preferred neighbors. That is, every neighbor $b^{+}_{r}$ of $a_{\ell}$
must have received a proposal from $a_{\ell}^{-}$. Since $b_{r}$ prefers
superscript $-$ neighbors to superscript $+$ neighbors, this means
$(d^{-}_{\ell},b^{+}_{r})\in S_{i}$ for some neighbor $d^{-}_{\ell}$ that
$b_{r}$ prefers to $a^{-}_{\ell}$, i.e., $b$ prefers $d$ to $a$. Thus $b\in
B_{1}$ (so $\gamma_{b}=1$) and moreover, $\mathsf{wt}_{M}(a,b)=0$. Hence
$\gamma_{a}+\gamma_{b}=1>\mathsf{wt}_{M}(a,b)$.

  * •

Case 2: let $a\in A_{-}$. There are two possibilities: (1) $b\in B_{-}$ and
(2) $b\in B_{+}$. Suppose $b\in B_{-}$. Then we have
$(a^{-}_{\ell},c^{+}_{r})$ and $(d^{+}_{\ell},b^{-}_{r})$ in $S_{i}$ for some
neighbors $c$ and $d$ of $a$ and $b$, respectively. Since every vertex prefers
superscript $-$ neighbors to superscript $+$ neighbors, it means $a_{\ell}$
proposed to $b^{-}_{r}$ and got rejected, i.e., $b_{r}$ prefers its partner
$d^{+}_{\ell}$ to $a^{+}_{\ell}$. We also claim $a_{\ell}$ prefers its partner
$c^{+}_{r}$ to $b^{+}_{r}$. This is because $b_{r}$ prefers $a^{-}_{\ell}$ to
$d^{+}_{\ell}$ (superscript $-$ neighbors over superscript $+$ neighbors): so
if $a^{-}_{\ell}$ had proposed to $b_{r}$, then $b_{r}$ would have rejected
its partner $d^{+}_{\ell}$. This means that both $a$ and $b$ prefer their
partners in $M$ to each other. Thus
$\mathsf{wt}_{M}(a,b)=-2=\gamma_{a}+\gamma_{b}$.

Suppose $b\in B_{+}$. Then either (i) $(a^{-}_{\ell},b^{+}_{r})\in S_{i}$ or
(ii) $(a^{-}_{\ell},c^{+}_{r})$ and $(d^{-}_{\ell},b^{+}_{r})$ are in $S_{i}$
for some neighbors $c$ and $d$ of $a$ and $b$, respectively. In subcase (i),
we have $\mathsf{wt}_{M}(a,b)=0=\gamma_{a}+\gamma_{b}$ and in subcase (ii),
the stability of $S_{i}$ in $H$ implies that either $a_{\ell}$ prefers
$c^{+}_{r}$ to $b^{+}_{r}$ or $b_{r}$ prefers $d^{-}_{\ell}$ to
$a^{-}_{\ell}$, thus $\mathsf{wt}_{M}(a,b)\leq 0=\gamma_{a}+\gamma_{b}$.

  * •

Case 3: let $a\in A_{+}$. As before, there are two possibilities: $b\in B_{+}$
and $b\in B_{-}$. When $b\in B_{+}$, we have $\gamma_{a}+\gamma_{b}=2$ and
since $\mathsf{wt}_{M}(a,b)\leq 2$, the constraint
$\mathsf{wt}_{M}(a,b)\leq\gamma_{a}+\gamma_{b}$ obviously holds.

When $b\in B_{-}$, either (i) $(a^{+}_{\ell},b^{-}_{r})\in S_{i}$ or (ii)
$(a^{+}_{\ell},c^{-}_{r})$ and $(d^{+}_{\ell},b^{-}_{r})$ are in $S_{i}$. In
subcase (i), we have $\mathsf{wt}_{M}(a,b)=0=\gamma_{a}+\gamma_{b}$ and in
subcase (ii), it follows from the stability of $S_{i}$ in $H$ that either
$a_{\ell}$ prefers $c^{-}_{r}$ to $b^{-}_{r}$ or $b_{r}$ prefers
$d^{+}_{\ell}$ to $a^{+}_{\ell}$. Thus $\mathsf{wt}_{M}(a,b)\leq
0=\gamma_{a}+\gamma_{b}$.

This finishes the proof of $M$’s popularity in $G\setminus U_{B}$ (by Theorem
2.2). Similarly, $L$ is popular in $G\setminus U_{A}$ by using the witness
$\vec{\beta}$ defined above. ∎

Theorem 4.1 tells us that the matching $M$ is popular in the subgraph
$G\setminus U_{B}$. However we need to prove the popularity of $M$ in the
entire graph $G$, i.e., we need to include vertices in $U_{B}$ as well.
Setting $\gamma_{b}=0$ for $b\in U_{B}$ will not cover edges in $A_{-}\times
U_{B}$. To prove the popularity of $M$ in $G$, we will use the fact that $L$
is popular in $G\setminus U_{A}$ and show that $M$ and $L$ have several edges
in common.

Let $Z$ be the set of all vertices outside $U_{A}\cup U_{B}$ that got marked
in our algorithm. So these are the marked vertices that are matched in $S_{i}$
to genuine neighbors (not to their twins). Since we marked entire connected
components in the popular subgraph $G_{0}$ in Algorithm 1, both $M$ and $L$
match vertices in $Z$ to each other.

Lemma 7 shows that the matching $S_{i}$ has “partial symmetry” across the
upper and lower halves of the graph $H$; more precisely, $M$ and $L$ are
identical on the set $Z$. This will be key to showing $M$’s popularity in $G$.
The following lemma will be useful in proving Lemma 7.

###### Lemma 6

$M$ and $L$ are stable matchings when restricted to vertices in $Z\cup
U_{A}\cup U_{B}$.

###### Proof

Let $Z_{A}=Z\cap A$ and let $Z_{B}=Z\cap B$. It follows from our algorithm
that $Z_{A}\subseteq A_{-}\cap A^{\prime}_{+}$ and $Z_{B}\subseteq B_{+}\cap
B^{\prime}_{-}$ (see Fig. 5).

$U_{A}$$Z_{A}$$Z_{B}$$\mathrm{The\ upper\ half\ of}\ H$$\mathrm{The\ lower\
half\ of}\ H$$A_{-}\setminus Z_{A}$$B_{+}\setminus
Z_{B}$$A_{+}$$B^{\prime}_{-}\setminus
Z_{B}$$B^{\prime}_{+}$$A^{\prime}_{+}\setminus
Z_{A}$$A^{\prime}_{-}$$B_{-}$$U_{B}$$Z_{B}$$Z_{A}$

Figure 5: The final picture of the partitions created by $M$ and $L$ in the
upper and lower halves of $H$, respectively. The while loop termination
condition implies $(A_{-}\setminus Z_{A})\subseteq A^{\prime}_{-}$ and
$(A^{\prime}_{+}\setminus Z_{A})\subseteq A_{+}$ and so on.

We need to show that $M$ (similarly, $L$) has no blocking edge in $(Z_{A}\cup
U_{A})\times(Z_{B}\cup U_{B})$. Consider any edge $(a,b)\in Z_{A}\times
Z_{B}$. We have $\gamma_{a}=-1$ and $\gamma_{b}=1$ while $\beta_{a}=1$ and
$\beta_{b}=-1$. We know from Claim 5 (given in the proof of Theorem 4.1) that
$\mathsf{wt}_{M}(a,b)\leq\gamma_{a}+\gamma_{b}=-1+1=0$. Similarly,
$\mathsf{wt}_{L}(a,b)\leq\beta_{a}+\beta_{b}=1-1=0$. Thus $(a,b)$ is not a
blocking edge to either $M$ or $L$. Hence neither $M$ nor $L$ has a blocking
edge in $Z_{A}\times Z_{B}$.

Moreover, $G$ has no edge in $U_{A}\times U_{B}$. This is because each vertex
$u\in U_{A}\cup U_{B}$ has to be an unstable vertex—otherwise $u$ is stable
and so $(u^{-}_{\ell},u^{+}_{r})$ is an unpopular edge and thus forbidden.

Consider any edge $(a,b)\in U_{A}\times Z_{B}$. We have $\gamma_{a}=0$ and
$\gamma_{b}=1$. So $\mathsf{wt}_{M}(a,b)\leq\gamma_{a}+\gamma_{b}=0+1=1$.
Since $\mathsf{wt}_{M}(a,b)$ is an even number, this means
$\mathsf{wt}_{M}(a,b)\leq 0$. Thus $(a,b)$ is not a blocking edge to $M$. We
will next show that $(a,b)$ is not a blocking edge to $L$.

Since $a\in U_{A}$ and $b\in Z_{B}\subseteq B^{\prime}_{-}$, the edges
$(a^{-}_{\ell},a^{+}_{r})$ and $(b^{-}_{\ell},c^{+}_{r})$ are in $S_{i}$ for
some neighbor $c$ of $b$. Note that $a^{-}_{\ell}$ is $a^{+}_{r}$’s least
preferred superscript $-$ neighbor in $H$. Thus $a^{+}_{r}$ did not receive
any offer from $b^{-}_{\ell}$ in Algorithm 1. Because $S_{i}$ is stable in
$H$, it has to be the case that $b_{\ell}$ prefers $c^{+}_{r}$ to $a^{+}_{r}$.
Since $(c,b)\in L$, we have $\mathsf{wt}_{L}(a,b)=0$. Thus $(a,b)$ is not a
blocking edge to $L$.

An analogous argument shows that no edge in $Z_{A}\times U_{B}$ blocks either
$M$ or $L$. Thus $M$ and $L$ are stable matchings when restricted to vertices
in $Z\cup U_{A}\cup U_{B}$. ∎

###### Lemma 7

The matching $M$ restricted to vertices in $Z$ is the same as the matching $L$
restricted to vertices in $Z$.

###### Proof

Consider any connected component $C$ in the popular subgraph $G_{0}$. The
component $C$ splits into sub-components
$C^{\prime}_{1},\ldots,C^{\prime}_{t}$ when we restrict edges to only those
marked “valid”. We claim there is exactly one stable matching
$T_{C^{\prime}_{j}}$ in each such sub-component $C^{\prime}_{j}$. Assume
$C^{\prime}_{j}$ contains a job $b$ that is a top choice neighbor for some
agent.333Otherwise $C^{\prime}_{j}$ consists of a single edge $(a,s(a))$ for
some $a\in A$; if there was another agent $a^{\prime}$ in $C^{\prime}_{j}$
then $s(a^{\prime})=s(a)$ and so one of $a,a^{\prime}$ would be left unmatched
in $S_{i}$, a contradiction to $S_{i}$’s stability in $H$. Then $b$ has to be
matched in $T_{C^{\prime}_{j}}$ to its most preferred neighbor $a$ in
$C^{\prime}_{j}$, otherwise $(a,b)$ would be a blocking edge to
$T_{C^{\prime}_{j}}$. Recall that every agent has exactly two valid edges
incident to it. So fixing one edge $(a,b)$ in the matching fixes
$T_{C^{\prime}_{j}}$.

In more detail, every agent $a^{\prime}\neq a$ in $C^{\prime}_{j}$ such that
$f(a^{\prime})=b$ has to be matched in $T_{C^{\prime}_{j}}$ to $s(a^{\prime})$
(call it $b^{\prime}$). Given that $a^{\prime}$ is matched to $b^{\prime}$,
every agent $a^{\prime\prime}\neq a^{\prime}$ in $C^{\prime}_{j}$ such that
$s(a^{\prime\prime})=b^{\prime}$ has to be matched in $T_{C^{\prime}_{j}}$ to
$f(a^{\prime\prime})$ and so on. Thus the matching $T_{C^{\prime}_{j}}$ gets
fixed. The same happens with every sub-component in $C$ and so the only stable
matching in $C$ is $T_{C}=\cup_{j=1}^{t}T_{C^{\prime}_{j}}$.

Let $C_{1},\ldots,C_{r}$ be the connected components of $G_{0}$ that contain
vertices in $Z$. So all vertices in $\cup_{i=1}^{r}C_{i}$ are marked, thus
$\cup_{i=1}^{r}C_{i}\subseteq Z\cup U_{A}\cup U_{B}$. We know from Lemma 6
that both $M$ and $L$ are stable matchings in each $C_{i}$, where $1\leq i\leq
r$. So $M$ (similarly, $L$) restricted to $\cup_{i=1}^{r}C_{i}$ is
$\cup_{i=1}^{r}T_{C_{i}}$. Thus $M$ and $L$ have the same edges on $Z$. ∎

Lemma 7 helps us in defining an appropriate witness $\vec{\alpha}$ to show
$M$’s popularity in $G$. Recall the vector $\vec{\gamma}$ defined in Theorem
4.1: we will set $\alpha_{u}=0$ for all $u\in Z\cup U_{B}$ and
$\alpha_{u}=\gamma_{u}$ otherwise. Before we use this vector $\vec{\alpha}$ to
prove the popularity of $M$ in Theorem 4.2, we need the following two lemmas.

###### Lemma 8

For every $a\in A_{-}\setminus Z_{A}$, $a$ likes $M(a)$ at least as much as
$L(a)$.

###### Proof

Suppose not. Then $M(a)=s(a)$ while $L(a)=f(a)$. We claim $f(a)\in B_{+}$.
Otherwise $f(a)\in B_{-}$, however for every edge $(x,y)\in A_{-}\times
B_{-}$, we have $\mathsf{wt}_{M}(x,y)\leq\gamma_{x}+\gamma_{y}=-2$ (by Claim
5). But $a$ prefers $f(a)$ to its partner in $M$, thus
$\mathsf{wt}_{M}(a,f(a))\geq 0$. Hence $f(a)\in B_{+}$. Since
$\mathsf{wt}_{M}(x,y)\leq 0$ for every edge $(x,y)\in A_{-}\times B_{+}$, we
can conclude that $\mathsf{wt}_{M}(a,f(a))=0$, i.e., $f(a)$ is matched in $M$
to a neighbor $a^{\prime}\in A_{-}$ that it prefers to $a$. Since $S_{i}$ uses
only valid edges, this means $f(a)=f(a^{\prime})$, i.e., $f(a)$ is the top
choice neighbor of $a^{\prime}$.

We now move to the lower half of $H$: observe that both $a$ and $a^{\prime}$
are in $A^{\prime}_{-}$. This is because there is no unmarked vertex in
$A_{-}\cap A^{\prime}_{+}$ by the termination condition of our while-loop.
Note that $a$ is unmarked since $a\notin Z_{A}$. Thus $a^{\prime}$ is also
unmarked since $(a,f(a))$ and $(a^{\prime},f(a))$ are popular edges, hence $a$
and $a^{\prime}$ are in the same connected component in $G_{0}$. Since $a\in
A^{\prime}_{-}$, $L(a)=f(a)$ is in $B^{\prime}_{+}$. Consider the edge
$(a^{\prime},f(a))\in A^{\prime}_{-}\times B^{\prime}_{+}$: both $a^{\prime}$
and $f(a)$ prefer each other to their respective partners in $L$. This means
$\mathsf{wt}_{L}(a^{\prime},f(a))=2$. However for each edge $(x,y)\in
A^{\prime}_{-}\times B^{\prime}_{+}$, we have
$\mathsf{wt}_{L}(x,y)\leq\beta_{x}+\beta_{y}=0$ (by Claim 4), a contradiction.
So for every $a\in A_{-}\setminus Z_{A}$, it has to be the case that $a$ likes
$M(a)$ at least as much as $L(a)$. ∎

###### Lemma 9

For every $a\in A_{+}\cap A^{\prime}_{+}$, $a$ likes $M(a)$ at least as much
as $L(a)$.

###### Proof

Suppose not. Then $M(a)=s(a)$ while $L(a)=f(a)$. Since $a\in A^{\prime}_{+}$,
$L(a)=f(a)\in B^{\prime}_{-}$. This implies $f(a)\in B_{-}$ since there is no
unmarked vertex in $B_{+}\cap B^{\prime}_{-}$ by the termination condition of
our while-loop. We know $f(a)$ is unmarked since $a$ (its partner in $L$) is
unmarked and this is because $a\in A_{+}$. Since $a\in A_{+}$ and $f(a)\in
B_{-}$, we have $\mathsf{wt}_{M}(a,f(a))\leq\gamma_{a}+\gamma_{b}=0$ (by Claim
5). So $f(a)$ has to be matched in $M$ to a more preferred neighbor
$a^{\prime}\in A_{+}$. As argued in the proof of Lemma 8, it follows from the
legality of $S_{i}$ that $f(a)$ is the top choice neighbor of $a^{\prime}$.

Consider the matching $L$ in the lower half of $H$. Since $L(a)=f(a)$,
$\mathsf{wt}_{L}(a^{\prime},f(a))~{}=~{}2$. That is, $(a^{\prime},f(a))$ is a
blocking edge to $L$. We need $\beta_{a^{\prime}}=\beta_{f(a)}=1$ to ensure
$\beta_{a^{\prime}}+\beta_{f(a)}\geq\mathsf{wt}_{L}(a^{\prime},f(a))=2$ (by
Claim 4). However $f(a)\in B^{\prime}_{-}$ since $a\in A^{\prime}_{+}$. This
means $\beta_{f(a)}=-1$, a contradiction. Thus for any $a\in A_{+}\cap
A^{\prime}_{+}$, it follows that $a$ likes $M(a)$ at least as much as $L(a)$.
∎

We are now ready to prove the popularity of $M$ in $G$.

###### Theorem 4.2

The matching $M$ is popular in $G$.

###### Proof

The popularity of $M$ in $G$ will be shown using $\vec{\alpha}$ defined below:

  * •

$\alpha_{u}=0$ for $u\in Z\cup U_{A}\cup U_{B}$.

  * •

$\alpha_{u}=1$ for $u\in A_{+}\cup(B_{+}\setminus Z_{B})$.

  * •

$\alpha_{u}=-1$ for $u\in B_{-}\cup(A_{-}\setminus Z_{A})$.

We have $M\subseteq(A_{+}\times B_{-})\cup(Z_{A}\times
Z_{B})\cup((A_{-}\setminus Z_{A})\times(B_{+}\setminus Z_{B}))$ (see Fig. 5).
Thus $\sum_{u\in A\cup B}\alpha_{u}=0$. Also,
$\alpha_{u}\geq\mathsf{wt}_{M}(u,u)$ for all vertices $u\in A\cup B$ since
$\alpha_{u}=0=\mathsf{wt}_{M}(u,u)$ for $u\in U_{A}\cup U_{B}$ and
$\alpha_{u}\geq-1=\mathsf{wt}_{M}(u,u)$ for all other $u$. To show $M$’s
popularity using Theorem 2.2, we need to prove that
$\alpha_{a}+\alpha_{b}\geq\mathsf{wt}_{M}(a,b)$ for all edges $(a,b)$.

We will first show this constraint holds for edges incident to vertices in
$U_{B}$. For this, we will use the matching $L$. It is easy to see that the
neighborhood of $U_{B}$ is in $A^{\prime}_{+}$ and also that each $a\in
A^{\prime}_{+}$ prefers its partner in $L$ to $b\in U_{B}$. This is because
$(b_{\ell}^{-},b_{r}^{+})\in S_{i}$ and $b_{r}^{+}$ is $b_{\ell}$’s least
preferred neighbor, thus $b_{\ell}$ must have been rejected by all its more
preferred neighbors in our algorithm, i.e., every neighbor $a^{+}_{r}$ of
$b_{\ell}$ received a proposal from $b_{\ell}^{-}$. Since $a_{r}$ prefers
superscript $-$ neighbors to superscript $+$ neighbors, this means
$(c^{-}_{\ell},a^{+}_{r})\in S_{i}$ for some neighbor $c^{-}_{\ell}$ that
$a_{r}$ prefers to $b^{-}_{\ell}$, i.e., $a$ prefers $c$ to $b$. Thus $a\in
A^{\prime}_{+}$.

We have $A^{\prime}_{+}=Z_{A}\cup(A^{\prime}_{+}\setminus Z_{A})$ and
$A^{\prime}_{+}\setminus Z_{A}\subseteq A_{+}$ (by the while loop termination
condition). Lemma 7 and Lemma 9 showed that for $a\in Z_{A}\cup(A_{+}\cap
A^{\prime}_{+})$, $a$ likes $M(a)$ at least as much as $L(a)$ and we showed in
the above paragraph that each $a\in A^{\prime}_{+}$ prefers $L(a)$ to $b$.
Thus $\mathsf{wt}_{M}(a,b)=0$. Since we set $\alpha_{a}=0$ for $a\in Z_{A}$
and $\alpha_{a}=1$ for $a\in A_{+}$, we have $\alpha_{a}+\alpha_{b}\geq
0=\mathsf{wt}_{M}(a,b)$.

We now need to show $\alpha_{a}+\alpha_{b}\geq\mathsf{wt}_{M}(a,b)$ holds for
all edges $(a,b)$ in $G\setminus U_{B}$. Recall the witness $\vec{\gamma}$
defined in the proof of Theorem 4.1 to show the popularity of $M$ in the
subgraph $G\setminus U_{B}$. Observe that it is only for vertices $u$ in $Z$
that we have $\alpha_{u}\neq\gamma_{u}$. Moreover, $\alpha_{a}>\gamma_{a}$ for
$a\in Z_{A}$.

For $b\in Z_{B}$, we have $\alpha_{b}=0$ while $\gamma_{b}=1$. Thus we have to
worry about edges $(a,b)$ in $G\setminus U_{B}$ where $b\in Z_{B}$ and check
that $\mathsf{wt}_{M}(a,b)\leq\alpha_{a}+\alpha_{b}$. Edges in $G\setminus
U_{B}$ that are not incident to $Z_{B}$ are covered by $\vec{\alpha}$ since
$\vec{\gamma}$ covers these edges and $\alpha_{u}\geq\gamma_{u}$ for all
$u\notin Z_{B}$.

Let $b\in Z_{B}\subseteq B_{+}\cap B^{\prime}_{-}$. We consider the following
three possibilities for the vertex $a$.

  1. 1.

Suppose $a\in U_{A}\cup Z_{A}$. For any $(a,b)\in(U_{A}\cup Z_{A})\times
B_{+}$, we have $\mathsf{wt}_{M}(a,b)\leq\gamma_{a}+\gamma_{b}\leq 0+1$.
Because $\mathsf{wt}_{M}(a,b)$ is an even number, this means
$\mathsf{wt}_{M}(a,b)\leq 0$. Since $\alpha_{a}=0$ for $a\in U_{A}\cup Z_{A}$
and $\alpha_{b}=0$ for $b\in Z_{B}$, we have $\mathsf{wt}_{M}(a,b)\leq
0=\alpha_{a}+\alpha_{b}$.

  2. 2.

Suppose $a\in A_{-}\setminus Z_{A}$. Then $a\in A^{\prime}_{-}$ by the
termination condition of the while-loop in our algorithm. Since
$\mathsf{wt}_{L}(x,y)\leq\beta_{x}+\beta_{y}=-2$ for every edge $(x,y)\in
A^{\prime}_{-}\times B^{\prime}_{-}$, it follows that $b\in Z_{B}\subseteq
B^{\prime}_{-}$ prefers $L(b)$ to $a$ and similarly, $a\in A^{\prime}_{-}$
prefers $L(a)$ to $b$.

We know from Lemma 7 that $M(b)=L(b)$, so $b$ prefers $M(b)$ to $a$. We know
from Lemma 8 that $a$ likes $M(a)$ at least as much as $L(a)$, so $a$ prefers
$M(a)$ to $b$. Thus $\mathsf{wt}_{M}(a,b)=-2<\alpha_{a}+\alpha_{b}$ since
$\alpha_{a}=-1$ and $\alpha_{b}=0$.

  3. 3.

Suppose $a\in A_{+}$. There are two subcases here: (i) $a\in A^{\prime}_{-}$
and (ii) $a\in A^{\prime}_{+}$. In subcase (i),
$\mathsf{wt}_{L}(a,b)\leq\beta_{a}+\beta_{b}=-2$. Since $M(b)=L(b)$ (by Lemma
7), it means that $b$ prefers $M(b)$ to $a$. Hence $\mathsf{wt}_{M}(a,b)\leq
0<\alpha_{a}+\alpha_{b}$ since $\alpha_{a}=1$ and $\alpha_{b}=0$ here.

Consider subcase (ii). We have
$\mathsf{wt}_{L}(a,b)\leq\beta_{a}+\beta_{b}=0$. So either (1) $b$ prefers
$L(b)$ to $a$ or (2) $a$ prefers $L(a)$ to $b$. In case (1), we have
$\mathsf{wt}_{M}(a,b)\leq 0$ since $M(b)=L(b)$ (by Lemma 7). In case (2) also,
we have $\mathsf{wt}_{M}(a,b)\leq 0$ since $a$ likes $M(a)$ at least as much
as $L(a)$ (by Lemma 9). So in both cases we have $\mathsf{wt}_{M}(a,b)\leq
0<\alpha_{a}+\alpha_{b}$ since $\alpha_{a}=1$ and $\alpha_{b}=0$ here.

Thus $\vec{\alpha}$ is a witness of $M$’s popularity (by Theorem 2.2). Hence
$M$ is popular in $G$. ∎

Since $M$ is $A$-popular (recall that it uses only valid edges), Theorem 4.2
immediately implies that $M$ is fully popular in $G$. Moreover, $M$ is a max-
size fully popular matching in $G$, as shown below.

###### Lemma 10

The matching $M$ is a max-size fully popular matching in $G=(A\cup B,E)$.

###### Proof

Observe that $U_{A}$ is the set of agents left unmatched in the matching $M$.
We claim that all the agents in $U_{A}$ are left unmatched in any fully
popular matching $N$ in $G$. We will use the fact that the matching $S_{i}$ is
the $(A_{L}\cup B_{L})$-optimal matching in the lattice ${\cal D}_{i}$ to
prove this claim.

Let $a\in A$ be such that $(a_{\ell}^{-},a_{r}^{+})\in S_{i}$. Since $S_{i}$
is the $(A_{L}\cup B_{L})$-optimal matching in the lattice ${\cal D}_{i}$, if
$a_{\ell}$ is matched to its least preferred neighbor $a^{+}_{r}$ in $S_{i}$,
then $a_{\ell}$ cannot be matched to a better neighbor in the realization
$N^{*}_{\alpha}$ of $N$, for any witness $\vec{\alpha}$ of $N$. In other
words, $(a_{\ell}^{-},a_{r}^{+})\in N^{*}_{\alpha}$. Thus $a$ is left
unmatched in $N$ as well. Hence $|M|=|A\setminus U_{A}|\geq|N|$. ∎

#### Running time of the algorithm.

The set of popular edges can be computed in linear time [7] and similarly, the
set of valid edges can be computed in linear time [2]. The Gale-Shapley
algorithm with forbidden edges in $H$ can be implemented to run in time linear
in the size of $H$ [13], which is $O(m+n)$, where $|E|=m$ and $|A\cup B|=n$.

Let us consider the time taken by Algorithm 1 in line 6 added up over all
iterations. This is the same as running the Gale-Shapley algorithm with
forbidden edges. More explicitly, when $S_{i-1}$ is modified to $S_{i}$ in the
$i$-th iteration, all the intermediate edges considered while modifying
$S_{i-1}$ to $S_{i}$ (these edges are now forbidden) are henceforth deleted
from the graph. Thus the total time taken by Algorithm 1 in line 6 added up
over all the iterations is linear in the size of $H$.

It is easy to see that updating the sets
$A_{-},A^{\prime}_{+},B^{\prime}_{-},B_{+}$ takes $O(1)$ time per vertex since
any vertex can move at most once from $A_{+}$ to $A_{-}$ (similarly, from
$A^{\prime}_{-}$ to $A^{\prime}_{+}$ and from $B^{\prime}_{+}$ to
$B^{\prime}_{-}$ and from $B_{-}$ to $B_{+}$). We need to check at the start
of each iteration if there is an unmarked vertex in $(A_{-}\cap
A^{\prime}_{+})\cup(B_{+}\cap B^{\prime}_{-})$. This can be implemented
efficiently by maintaining a list of vertices $u$ such that both
$(u^{-}_{\ell},\ast)$ and $(\ast,u^{+}_{r})$ are in our matching.

So for each vertex $u$, whenever (i) $u_{\ell}$ starts proposing to
superscript $+$ neighbors or (ii) $u_{r}$ receives a proposal from a
superscript $-$ neighbor, we check if $u_{\ell}$ and $u_{r}$ are in opposite
states. If so, then $u$ is added to the end of this list. We use a pointer
that traverses this list once from left to right during the entire course of
the algorithm. At the start of each iteration, we start from the current
position of this pointer and traverse rightwards in the list searching for a
vertex that is still unmarked. Thus we can efficiently check if $(A_{-}\cap
A^{\prime}_{+})\cup(B_{+}\cap B^{\prime}_{-})$ has an unmarked vertex or not.
Hence our algorithm can be implemented to run in linear time. Thus Theorem 1.1
follows.

See 1.1

#### Acknowledgements.

Supported by the DAE, Government of India, under project no. RTI4001. Thanks
to Yuri Faenza for discussions that led to this problem and his helpful
comments on the manuscript. Thanks to the reviewers of the conference version
of this paper for their suggestions on improving the presentation.

## References

  * [1] A. Abdulkadiroğlu and T. Sönmez.  School choice: A mechanism design approach.  American Economic Review, 93(3): 729–747, 2003.
  * [2] D. J. Abraham, R. W. Irving, T. Kavitha, and K. Mehlhorn.  Popular matchings.  SIAM Journal on Computing, 37(4): 1030–1045, 2007.
  * [3] S. Baswana, P. P. Chakrabarti, S. Chandran, Y. Kanoria, and U. Patange.  Centralized admissions for engineering colleges in India.  INFORMS Journal on Applied Analytics, 49(5): 338–35, 2019.
  * [4] Canadian Resident Matching Service.  How the matching algorithm works. Web document available at http://carms.ca/algorithm.htm.
  * [5] M.-J.-A.-N. de C. (Marquis de) Condorcet.  Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix. L’Imprimerie Royale, 1785.
  * [6] Condorcet method.  https://en.wikipedia.org/wiki/Condorcet_method
  * [7] Á. Cseh and T. Kavitha.  Popular edges and dominant matchings.  Mathematical Programming, 172(1): 209–229, 2018.
  * [8] Y. Faenza, T. Kavitha, V. Powers, and X. Zhang.  Popular matchings and limits to tractability.  In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2790-2809, 2019.
  * [9] Y. Faenza and T. Kavitha.  Quasi-popular matchings, optimality, and extended formulations.  In Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), 325-344, 2020.
  * [10] D. Gale and L.S. Shapley.  College admissions and the stability of marriage.  American Mathematical Monthly, 69(1): 9–15, 1962.
  * [11] D. Gale and M. Sotomayor.  Some remarks on the stable matching problem.  Discrete Applied Mathematics, 11(3): 223–232, 1985.
  * [12] P. Gärdenfors.  Match making: assignments based on bilateral preferences.  Behavioural Sciences, 20(3): 166–173, 1975.
  * [13] D. Gusfield and R. W. Irving.  The Stable Marriage Problem: Structure and Algorithms.  MIT Press, 1989.
  * [14] C.-C. Huang and T. Kavitha.  Popular matchings in the stable marriage problem.  Information and Computation, 222: 180–194, 2013.
  * [15] C.-C. Huang and T. Kavitha.  Popularity, mixed matchings, and self-duality.  Mathematics of Operations Research, 46(2): 405–427, 2021.
  * [16] T. Kavitha.  A size-popularity tradeoff in the stable marriage problem.  SIAM Journal on Computing, 43(1): 52–71, 2014.
  * [17] T. Kavitha.  Popular half-integral matchings.  In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), 22:1–22:13, 2016.
  * [18] T. Kavitha.  Popular matchings with one-sided bias.  In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP), 70:1–70:18, 2020.
  * [19] T. Kavitha, J. Mestre, and M. Nasre.  Popular mixed matchings.  Theoretical Computer Science, 412(24): 2679–2690, 2011.
  * [20] D. Manlove and C. Sng.  Popular matchings in the capacitated house allocation problem.  Journal of Discrete Algorithms, 8(2): 102–116, 2010.
  * [21] J. Mestre.  Weighted Popular Matchings.  ACM Transactions on Algorithms 10(1): 2:1–2:16, 2014.
  * [22] National Resident Matching Program.  Why the Match? Web document available at http://www.nrmp.org/whythematch.pdf.


* [38] R. Boughezal, A. Isgró and F. Petriello, _Next-to-leading power corrections to $V+1$ jet production in $N$-jettiness subtraction_, _Phys. Rev._ D101 (2020) 016005, [1907.12213].
  * [39] M. A. Ebert, I. Moult, I. W. Stewart, F. J. Tackmann, G. Vita and H. X. Zhu, _Subleading power rapidity divergences and power corrections for q T_, _JHEP_ 04 (2019) 123, [1812.08189].
  * [40] L. Cieri, C. Oleari and M. Rocco, _Higher-order power corrections in a transverse-momentum cut for colour-singlet production at NLO_ , _Eur. Phys. J._ C79 (2019) 852, [1906.09044].
  * [41] C. Oleari and M. Rocco, _Power corrections in a transverse-momentum cut for vector-boson production at NNLO: the $qg$-initiated real-virtual contribution_, _Eur. Phys. J. C_ 81 (2021) 183, [2012.10538].
  * [42] Z. L. Liu and M. Neubert, _Factorization at subleading power and endpoint-divergent convolutions in $h\to\gamma\gamma$ decay_, _JHEP_ 04 (2020) 033, [1912.08818].
  * [43] Z. L. Liu, B. Mecaj, M. Neubert and X. Wang, _Factorization at subleading power, Sudakov resummation, and endpoint divergences in soft-collinear effective theory_ , _Phys. Rev. D_ 104 (2021) 014004, [2009.04456].
  * [44] Z. L. Liu, B. Mecaj, M. Neubert and X. Wang, _Factorization at subleading power and endpoint divergences in $h\to\gamma\gamma$ decay. Part II. Renormalization and scale evolution_, _JHEP_ 01 (2021) 077, [2009.06779].
  * [45] Z. L. Liu, M. Neubert, M. Schnubel and X. Wang, _Factorization at next-to-leading power and endpoint divergences in gg → h production_ , _JHEP_ 06 (2023) 183, [2212.10447].
  * [46] G. Bell, P. Böer and T. Feldmann, _Muon-electron backward scattering: a prime example for endpoint singularities in SCET_ , _JHEP_ 09 (2022) 183, [2205.06021].
  * [47] T. Feldmann, N. Gubernari, T. Huber and N. Seitz, _Contribution of the electromagnetic dipole operator ${\cal O}_{7}$ to the $\bar{B}_{s}\to\mu^{+}\mu^{-}$ decay amplitude_, _Phys. Rev. D_ 107 (2023) 013007, [2211.04209].
  * [48] C. Cornella, M. König and M. Neubert, _Structure-dependent QED effects in exclusive B decays at subleading power_ , _Phys. Rev. D_ 108 (2023) L031502, [2212.14430].
  * [49] T. Hurth and R. Szafron, _Refactorisation in subleading $\bar{B}\to X_{s}\gamma$_, _Nucl. Phys. B_ 991 (2023) 116200, [2301.01739].
  * [50] M. Beneke, M. Garny, S. Jaskiewicz, R. Szafron, L. Vernazza and J. Wang, _Unpublished, 2020_ , .
  * [51] A. Broggio, S. Jaskiewicz and L. Vernazza, _Next-to-leading power two-loop soft functions for the Drell-Yan process at threshold_ , _JHEP_ 10 (2021) 061, [2107.07353].
  * [52] Z. L. Liu, M. Neubert, M. Schnubel and X. Wang, _Radiative quark jet function with an external gluon_ , _JHEP_ 02 (2022) 075, [2112.00018].
  * [53] Z. L. Liu, B. Mecaj, M. Neubert, X. Wang and S. Fleming, _Renormalization and Scale Evolution of the Soft-Quark Soft Function_ , _JHEP_ 07 (2020) 104, [2005.03013].
  * [54] G. T. Bodwin, J.-H. Ee, J. Lee and X.-P. Wang, _Analyticity, renormalization, and evolution of the soft-quark function_ , _Phys. Rev. D_ 104 (2021) 016010, [2101.04872].
  * [55] M. Beneke, A. P. Chapovsky, M. Diehl and T. Feldmann, _Soft collinear effective theory and heavy to light currents beyond leading power_ , _Nucl. Phys._ B643 (2002) 431–476, [hep-ph/0206152].
  * [56] M. Beneke and T. Feldmann, _Multipole expanded soft collinear effective theory with non-abelian gauge symmetry_ , _Phys. Lett._ B553 (2003) 267–276, [hep-ph/0211358].
  * [57] S. E. Jaskiewicz, _Factorization and Resummation at Subleading Powers_ , Ph.D. thesis, Technical University of Munich, May, 2021.
  * [58] M. Beneke, M. Garny, R. Szafron and J. Wang, _Anomalous dimension of subleading-power N-jet operators_ , _JHEP_ 03 (2018) 001, [1712.04416].
  * [59] M. Beneke, M. Garny, R. Szafron and J. Wang, _Anomalous dimension of subleading-power $N$-jet operators. Part II_, _JHEP_ 11 (2018) 112, [1808.04742].
  * [60] M. Beneke, M. Garny, R. Szafron and J. Wang, _Violation of the Kluberg-Stern-Zuber theorem in SCET_ , _JHEP_ 09 (2019) 101, [1907.05463].
  * [61] C. Marcantonini and I. W. Stewart, _Reparameterization Invariant Collinear Operators_ , _Phys. Rev._ D79 (2009) 065028, [0809.1093].
  * [62] D. W. Kolodrubetz, I. Moult and I. W. Stewart, _Building Blocks for Subleading Helicity Operators_ , _JHEP_ 05 (2016) 139, [1601.02607].
  * [63] I. Feige, D. W. Kolodrubetz, I. Moult and I. W. Stewart, _A Complete Basis of Helicity Operators for Subleading Factorization_ , _JHEP_ 11 (2017) 142, [1703.03411].
  * [64] I. Moult, I. W. Stewart and G. Vita, _A subleading operator basis and matching for gg $\to$ H_, _JHEP_ 07 (2017) 067, [1703.03408].
  * [65] M. Beneke, P. Falgari and C. Schwinn, _Threshold resummation for pair production of coloured heavy (s)particles at hadron colliders_ , _Nucl. Phys._ B842 (2011) 414–474, [1007.5414].
  * [66] A. Vogt, _Leading logarithmic large-x resummation of off-diagonal splitting functions and coefficient functions_ , _Phys. Lett. B_ 691 (2010) 77–81, [1005.1606].
  * [67] T. Liu and A. A. Penin, _High-Energy Limit of QCD beyond the Sudakov Approximation_ , _Phys. Rev. Lett._ 119 (2017) 262001, [1709.01092].
  * [68] T. Liu and A. Penin, _High-Energy Limit of Mass-Suppressed Amplitudes in Gauge Theories_ , _JHEP_ 11 (2018) 158, [1809.04950].
  * [69] M. Beneke and V. A. Smirnov, _Asymptotic expansion of Feynman integrals near threshold_ , _Nucl. Phys._ B522 (1998) 321–344, [hep-ph/9711391].
  * [70] R. Hamberg, W. L. van Neerven and T. Matsuura, _A complete calculation of the order $\alpha_{s}^{2}$ correction to the Drell-Yan $K$ factor_, _Nucl. Phys._ B359 (1991) 343–405.
  * [71] T. Gehrmann, E. W. N. Glover, T. Huber, N. Ikizlerli and C. Studerus, _Calculation of the quark and gluon form factors to three loops in QCD_ , _JHEP_ 06 (2010) 094, [1004.3653].
  * [72] D. Binosi, J. Collins, C. Kaufhold and L. Theussl, _JaxoDraw: A Graphical user interface for drawing Feynman diagrams. Version 2.0 release notes_ , _Comput. Phys. Commun._ 180 (2009) 1709–1715, [0811.4113].
  * [73] J. A. M. Vermaseren, _New features of FORM_ , math-ph/0010025.
  * [74] T. Huber and D. Maitre, _HypExp: A Mathematica package for expanding hypergeometric functions around integer-valued parameters_ , _Comput. Phys. Commun._ 175 (2006) 122–144, [hep-ph/0507094].