11institutetext:  1 KRTK KTI, Budapest, Hungary

# Weakly-Popular and Super-Popular Matchings with Ties and Their Connection to
Stable Matchings

Gergely Csáji 11

###### Abstract

In this paper, we study a slightly different definition of popularity in
bipartite graphs $G=(U,W,E)$ with two-sided preferences, when ties are present
in the preference lists. This is motivated by the observation that if an agent
$u$ is indifferent between his original partner $w$ in matching $M$ and his
new partner $w^{\prime}\neq w$ in matching $N$, then he may probably still
prefer to stay with his original partner, as change requires effort, so he
votes for $M$ in this case, instead of being indifferent.

We show that this alternative definition of popularity, which we call weak-
popularity allows us to guarantee the existence of such a matching and also to
find a weakly-popular matching in polynomial-time that has size at least
$\frac{3}{4}$ the size of the maximum weakly popular matching. We also show
that this matching is at least $\frac{4}{5}$ times the size of the maximum
(weakly) stable matching, so may provide a more desirable solution than the
current best (and tight under certain assumptions) $\frac{2}{3}$-approximation
for such a stable matching. We also show that unfortunately, finding a maximum
size weakly popular matching is NP-hard, even with one-sided ties and that
assuming some complexity theoretic assumptions, the
$\frac{3}{4}$-approximation bound is tight.

Then, we study a more general model than weak-popularity, where for each edge,
we can specify independently for both endpoints the size of improvement the
endpoint needs to vote in favor of a new matching $N$. We show that even in
this more general model, a so-called $\gamma$-popular matching always exists
and that the same positive results still hold.

Finally, we define an other, stronger variant of popularity, called super-
popularity, where even a weak improvement is enough to vote in favor of a new
matching. We show that for this case, even the existence problem is NP-hard.

##  1 Introduction

In preference based markets, each market participant expresses their
preferences as a strict ordering of some possible scenarios and the aim is to
find solutions that are fair or optimal according to some fairness or
optimality notion. The area is extensively used and studied in Economics,
Mathematics and Computer Science, originating from the seminal paper of Gale
and Shapley (1962) about stable matchings. Stability means that we aim for
solutions, where there is no pair of agents that could mutually improve by
getting matched together and leaving their partners behind. Their model for
the stable matching problem has been applied to countless real word scenarios,
from Resident-allocation to School-choice and even Kidney Exchange Programs.
For an overview of the area of preference based markets, see for example
Manlove (2013). A relaxation of stability, called popularity, which gained
significant theoretical interest in the literature recently, was introduced by
Gärdenfors (1975). Popular matchings translate the simple majority voting rule
into the world of matchings under preferences, i.e a matching is popular if it
does not lose a head to head comparison to any other matching. A very
attractive property of popular matchings is that they still always exists in
bipartite markets with two-sided preferences (in fact, every stable matching
is popular), and their size may even be two times the size of stable
matchings. For an overview of popular matchings, see Cseh (2017).

A large drawback of popular matchings however, is that they do not necessarily
exist when ties are allowed in the preferences of the agents and even worse,
deciding if an instance with ties admits a popular matching or not is NP-
complete, even if ties occur on one side of the market only, as shown in Cseh
et al. (2017). In contrast, stable matchings still always exist in this model,
however a maximum size stable matching becomes NP-hard to find ( Iwama et al.
(1999)) and the current best approximation ratio is $\frac{2}{3}$ (McDermid
(2009),Király (2012)) that holds even in significantly more general settings
(Csáji (2023)). In this paper, we show that with a natural alternative
definition of popularity in the presence of ties, we can guarantee the
existence of a popular matching and also find a $\frac{3}{4}$-approximation of
a maximum size such matching in polynomial time, that is also a
$\frac{4}{5}$-approximation for the maximum size stable matching.

We also study a strengthened variant called super-popularity, where we show
that even deciding if such a matching exists is NP-hard.

###  1.1 Related work

Popularity was introduced by Gärdenfors (1975) for the two-sided preference
model, where he showed that every stable matching is popular. Abraham et al.
(2007) introduced popularity for the one-sided House Allocation model. Both
these papers provided polynomial-time algorithms for finding a popular
matching in the given model.

Later, study has been started to focus on finding maximum size popular
matchings. Huang and Kavitha (2013) have shown that maximum size popular
matchings can also be found in polynomial-time. Kavitha (2014) gave an
algorithm for this problem that used a multi-level Gale-Shapley approach,
which is similar to the edge duplicating method we use, but the latter allows
much easier analysis and is easier to generalize.

For the non-bipartite roommates model, finding a popular matching becomes NP-
hard (Faenza et al. (2019), Gupta et al. (2021)).

If ties are allowed in the preferences of the agents, then even in the two-
sided model, a popular matching may fail to exists, and finding one becomes
NP-hard (Cseh et al. (2017)). To get over this obstacle, we introduce an
alternative definition of popularity in this case.

The Stable Marriage problem was introduced by Gale and Shapley (1962). The
_stable marriage problem with ties and incomplete lists_ (smti) was first
studied by Iwama et al. (1999), who showed the NP-hardness of Max-SMTI, which
is the problem of finding a maximum size stable matching in an SMTI instance.
Super stability, which is a stronger version of stability was introduced by
Irving (1994), where he proved that a super stable matching can be found in
polynomial time, if one exists. Also, super stable matchings have the same
size, even with weak preferences.

Later, it has been shown that Max-SMTI can be $\frac{2}{3}$ approximated in
polynomial-time algorithm by McDermid (2009). Király (2012) gave a much
simpler and linear time novel algorithm with the same approximation ratio,
using a multilevel Gale-Shapley algorithm.

On the negative side, Halldórsson et al. (2002) showed that it is NP-hard to
approximate Max-SMTI within some constant factor. Yanagisawa (2007) and
Halldórsson et al. (2003) showed that assuming the Unique Games Conjecture,
there is no $\frac{3}{4}+\varepsilon$-approximation for any $\varepsilon>0$.
Recently, Dudycz et al. (2022) proved that assuming the Small Set Expansion
Hypothesis or the strong-UGC, there cannot even be a
$\frac{2}{3}+\varepsilon$-approximation algorithm for Max-SMTI.

Notions related to our $\gamma$-popularity has been studied in Chen et al.
(2021), Csáji et al. (2023) and Csáji (2023). Chen et al. (2021) defined
_local $d$-near-stability_ based on swaps in the preference orders, such that
a matching is locally $d$-near stable, if there is no blocking edge $(u,w)$
that still remains blocking even after moving $w$ and $u$ $d$ places down
their original preference lists. In Csáji et al. (2023) a similar notion for
cardinal preferences called $\Delta$-max stability was introduced, which meant
that for any edge to block, both endpoints should improve by at least
$\Delta$. Csáji (2023) generalized this to a concept called $\gamma$-max
stability, where for each edge $e=(u,w)$, distinct $\gamma_{e}^{u}>0$ and
$\gamma_{e}^{w}>0$ values are given, and for an edge $(u,w)$ to block, $u$
should improve by at least $\gamma_{e}^{u}$ and $w$ by $\gamma_{e}^{w}$. He
extended the $\frac{2}{3}$-approximation algorithm for Max-SMTI even for this
more general setting.

###  1.2 Our contributions

In this paper, we define new notions of popularity, called weak-popularity,
super-popularity and $\gamma$-popularity, where the first is inspired by weak-
stability, the second by super-stability and the last is inspired by
$\gamma$-max stability. We prove that weakly-popular and $\gamma$-popular
matchings always exists, and we can find a near maximum size such a matching
in linear time. In particular, we show that in both the weak-popularity model,
and the more general $\gamma$-popularity model, there exists a
$\frac{3}{4}$-approximation algorithm. We also show that the size of the
output of this algorithm is at least $\frac{4}{5}$ times the size of the
maximum size stable matching and $\gamma$-max stable matching respectively.

We use the edge duplication technique that has proven to be a very efficient
technique in problems related to stable matchings. While this technique is
very similar to the idea of promoting agents, it allows us the handle, analyze
and solve problems much more easily. Our algorithm combines the one in Csáji
(2023) for the maximum size $c\gamma$-stable matching and the one in Kamiyama
(2020) for the maximum size popular matching with strict preferences and
matroid constraints.

On the hardness side, we show that finding a maximum size weakly popular
matching in an instance with ties is NP-hard, even if ties occur on one side
of the market only, so an exact polynomial algorithm for the problem is not
very likely. We also show that the $\frac{3}{4}$ approximation ratio is tight
under the strong-Unique Games Conjecture or the Small Set Expansion
Hypothesis.

##  2 Preliminaries

We investigate matching markets, where the set of agents with the possible set
of contracts is given by a (not necessarily simple) bipartite graph
$G=(U,W;E)$. For each agent $v\in U\cup W$, we denote by $E(v)$ the edges that
are incident to $v$. We assume that for each agent $v$, there is a preference
valuation $p_{v}:E(v)\to\mathbb{R}_{\geq 0}$, which defines a weak ranking
over the adjacent edges of $v$, this is a strictly more general setting than
ordinary weak preference lists, where only a weak order $\succeq_{v}$ is given
for each agent $v\in U\cup W$ over $E(v)$. We note that we assume that the
vertices rank their adjacent edges instead of the adjacent agents on the other
side, because we allow parallel edges in our model. We also assume that
$p_{v}(\emptyset)\leq 0$, which denotes that an agent always weakly prefers to
be matched to any acceptable partners rather than being unmatched.

We say that an edge set $M\subset E$ is a matching, if $|M\cap E(v)|\leq 1$
for each $v\in U\cup W$. For a vertex $v$, let $M(v)$ denote the edge incident
to $v$ in $M$, if there is any, otherwise $M(v)$ is $\emptyset$. A matching
$M$ is maximal, if no edge can be added to it. A matching is maximum, if it is
largest among all matchings.

Stability.

We start by defining weakly stable matchings. We say that a matching $M$ is
weakly stable, or simply stable, if there is no edge $e=(u,w)\notin M$, such
that $p_{u}(e)>p_{u}(M(u))$ and $p_{w}(e)>p_{w}(M(w))$. Otherwise, such an
edge is called a blocking edge.

In the context of ordinary weak preference orders $\succeq_{v}$ for $v\in
U\cup W$ this is just equivalent to saying that there should be no edge
$(u,w)$, where $u$ and $w$ strictly prefer each other to their partners in
$M$.

Super Stability.

A stronger version of stability, called super-stability is the following. Let
$M$ be a matching. We say that $M$ is super-stable, if there is no edge
$e=(u,w)$ to $M$ such that $p_{u}(e)\geq p_{u}(M(u))$ and $p_{w}(e)\geq
p_{w}(M(w))$, so here even a weak improvement is enough to block $M$.

$\gamma$-max stability.

Now we define $\gamma$-max stability from Csáji (2023). Suppose we are given
$\gamma_{e}^{u}>0,\gamma_{e}^{w}>0$ values for each edge $e=(u,w)\in E$. They
specify the size of improvement an agent $u$ needs in order to prefer the edge
$e$ over his partner $M(u)$. Let $M$ be a matching. We say that an edge
$e=(u,w)\notin M$ $\gamma$-max blocks $M$, if $p_{u}(e)\geq
p_{u}(M(u))+\gamma_{e}^{u}$ and $p_{w}(e)\geq p_{w}(M(w))+\gamma_{e}^{w}$. We
say that $M$ is $\gamma$-max stable, if there is no $\gamma$-max blocking edge
to $M$. The case of simple stability corresponds to the special case when
every $\gamma_{e}^{v}$ value is sufficiently small.

Popularity.

Now we define popular matchings with their original definition. Let $M$ be a
matching, and $N$ be another matching. Each agent $v\in U\cup W$ compares
these two matchings and casts a vote as follows. If $p_{v}(M(v))=p_{v}(N(v))$,
then we define $\textit{vote}_{v}(M,N)=0$. If $p_{v}(M(v))>p_{v}(N(v))$, then
$\textit{vote}_{v}(M,N)=+1$, and finally if $p_{v}(M(v))<p_{v}(N(v))$, then
$\textit{vote}_{v}(M,N)=-1$. Then, we aggregate the votes of each agent and
obtain $\Delta(M,N)=\sum_{v\in U\cup W}\textit{vote}_{v}(M,N)$. Clearly, with
this definition it holds that $vote_{v}(M,N)+vote_{v}(N,M)=0$. We say that a
matching $M$ is popular, if for any matching $N$, it holds that
$\Delta(M,N)\geq 0$.

Weak popularity.

We provide an alternative definition of popularity as follows. Let $M,N$ be
two matchings. We define $\textit{vote}^{weak}_{v}(M,N)$ in a slightly
different manner. If $p_{v}(M(v))>p_{v}(N(v))$ or $p_{v}(M(v))>p_{v}(N(v))$,
then $\textit{vote}^{weak}_{v}(M,N)$ is $+1$ and $-1$ respectively, same as
before. Also, if $M(v)=N(v)$, then again, $\textit{vote}^{weak}_{v}(M,N)=0$.
However, when $M(v)\neq N(v)$, but $p_{v}(M(v))=p_{v}(N(v))$, we define
$\textit{vote}^{weak}_{v}(M,N)=+1$.

This is motivated by the fact that if an agent $v$ does not improve in the
matching $N$ from $M$, but has to change partners, then he would probably
prefer keeping his original partner and not go through the additional effort
to obtain a similarly liked new partner.

Then, we define a matching $M$ to be weakly-popular, if for any matching $N$,
it holds that $\Delta^{weak}(M,N)=\sum_{v\in U\cup
W}\textit{vote}^{weak}_{v}(M,N)\geq 0$.

This is also related to the definition of weakly stable matchings, where in
order for a pair $(u,w)$ to block, both must strictly improve.

$\gamma$-popularity.

We give a generalization of weak popularity, inspired by $\gamma$-max
stability Csáji (2023). Suppose again we are given
$\gamma_{e}^{u}>0,\gamma_{e}^{w}>0$ values for each edge $e=(u,w)\in E$.

Let $M,N$ be two matchings. We define $\textit{vote}^{\gamma}_{v}(M,N)$ as
follows. First, if $M(v)=N(v)$, then $\textit{vote}^{\gamma}_{v}(M,N)=0$. If
$p_{v}(N(v))\geq p_{v}(M(v))+\gamma_{N(v)}^{v}$, then
$\textit{vote}^{\gamma}_{v}(M,N)=-1$. Finally, if
$p_{v}(N(v))<p_{v}(M(v))+\gamma_{e}^{v}$ and $M(v)\neq N(v)$, then
$\textit{vote}^{\gamma}_{v}(M,N)=+1$.

Then, we define a matching $M$ to be $\gamma$-popular, if for any matching
$N$, it holds that $\Delta^{\gamma}(M,N)=\sum_{v\in U\cup
W}\textit{vote}^{\gamma}(M,N)\geq 0$.

Super popularity.

Motivated by super stable matchings, we can introduce a stronger variant of
popularity, called super-popularity. In the super stable matching model, even
a partner that is equally good is considered as good enough to block. Hence,
now we define the votes as follows. Let $M,N$ be two matchings. If
$p_{v}(M(v))>p_{v}(N(v))$, then $\textit{vote}^{super}_{v}(M,N)=+1$. If
$N(v)=M(v)$, then $\textit{vote}^{super}_{v}(M,N)=0$. Finally, if
$p_{v}(N(v))\geq p_{v}(M(v))$ and $M(v)\neq N(v)$, then
$\textit{vote}^{super}_{v}(M,N)=-1$.

Then, we say that $M$ is super-popular if for any other matching $N$, it holds
that $\Delta^{super}(M,N)=\sum_{v\in U\cup
W}\textit{vote}^{super}_{v}(M,N)\geq 0$.

The studied problems.

Now we define the optimization problem we investigate, called Maximum
$\gamma$-popular matching with ties and incomplete preferences abbriviated as
max-$\gamma$-PM for short.

max-$\gamma$-PM
Input: A bipartite graph $G=(U,W;E)$, $p_{v}()$ preference valuations for each
$v\in U\cup W$, numbers $0<\gamma_{e}^{v}$ for each pair $(e,v)\in
E\times(U\cup W)$ such that $v\in e$. Output: A maximum size $\gamma$-popular
matching $M$.

For the restricted case of weak-popularity, which corresponds to the case,
when each $\gamma_{e}^{v}$ is sufficiently small, we call the optimization
problem max-weak-pm.

We define the following existence problem too.

$\gamma$-super-pm
Input: A bipartite graph $G=(U,W;E)$, $p_{v}()$ preference valuations for each
$v\in U\cup W$, numbers $0<\gamma_{e}^{v}$ for each pair $(e,v)\in
E\times(U\cup W)$ such that $v\in e$. Output: Is there a super-popular
matching $M$?

The restriction of the problem to ordinary weak preferences is denoted by
super-pm.

Before we move on to our main results, let us show a simply theorem that
connects $\gamma$-popular and $c\gamma$-stable matchings.

######  Theorem 2.1.

Any $\gamma$-max stable matching $M$ is also $\gamma$-popular.

###### Proof.

Let $M$ be a $\gamma$-max stable matching. Then, for any matching $N$, it
holds that the sum of votes on each edge $e=(u,w)$ of $N$ is at least 0.
Indeed, by the definition of the votes, either both are 0 or neither are.
Hence, if the two votes of the endpoints are negative, then both votes with
$-1$, but by the definition of the votes, such an edge is a blocking edge to
$M$, contradiction. ∎

##  3 Hardness of finding maximum weakly popular matchings

In this section we give a simple proof of the NP-hardness of max-weak-pm, even
in very restricted settings.

######  Theorem 3.1.

max-weak-pm is NP-hard, even with one-sided ties.

###### Proof.

We reduce from max-smti, where we are given in instance $I$ of the stable
matching problem with ties and a number $k$, and the question is whether there
exists a stable matching with size at least $k$. In particular, we reduce from
an NP-hard restricted variant, where ties occur on one side only, say on side
$W$ (Manlove et al. (2002)).

Let $I=(G,\succ)$ be such an instance of max-smti, with
$U=(u_{1},\dots,u_{n})$ and $W=\\{w_{1},\dots,w_{n}\\}$. We create an instance
$I^{\prime}$ from $I$ as follows. We add an agent $z_{i}$ to $W$ for each
$i\in[n]$ to get $W^{\prime}$ and an agent $z_{i}^{\prime}$ to $U$ for each
$i\in[n]$ to get $U^{\prime}$. The preference list of $z_{i}$ is $u_{i}\succ
z_{i}^{\prime}$. Agent $z_{i}^{\prime}$ only considers $z_{i}$ acceptable.
Finally, for each agent $u_{i}\in U$, we add $z_{i}$ to the top of their
preference list. So if $u_{i}$ had a preference list $w_{1}\succ w_{2}$ in
$I$, now he has $z_{i}\succ w_{1}\succ w_{2}$. Note that in our construction,
ties still occur on side $W^{\prime}$ only.

We show that there is a stable matching of size $n-l$ in $I$ if and only if
there is a weakly-popular matching of size $2n-l$ in $I^{\prime}$, for any
$0\leq l\leq n$.

######  Claim.

Let $M^{\prime}$ be a weakly-popular matching in $I^{\prime}$ of size $2n-l$.
Then, there is a stable matching $M$ in $I$ of size $n-l$.

Proof: Clearly, $M^{\prime}$ can contain at most $n$ edges from
$\\{(z_{i},z_{i}^{\prime}),(u_{i},z_{i})\mid i\in[n]\\}$, therefore
$M^{\prime}$ induces a matching $M$ of size at least $n-l$ in $G$. If this
matching is not maximal in $G$, then let $H$ be the subgraph of the unmatched
vertices of $M$ in $G$, and let $N$ be a stable matching in $H$. Then, we
extend $M$ by the edges of $N$. Clearly, $M$ has at least $n-l$ edges still
and now it is maximal in $G$.

We claim that $M$ is stable. Suppose that $e=(u_{i},w_{j})$ blocks $M$, with
$u\in U,w\in W$.

Assume that $w_{j}$ is unmatced in $M^{\prime}$. Then $u_{i}$ is matched in
$M^{\prime}$, which follows from $M^{\prime}$ being weakly-popular. If
$M^{\prime}(u_{i})\in W$, then $M^{\prime}(u_{i})=M(u_{i})$ and
$M^{\prime}\setminus\\{M^{\prime}(u_{i})\\}\cup\\{(u_{i},w_{j})\\}$ dominates
$M^{\prime}$, as there is two $-1$ votes and one $+1$ vote, contradiction. If
$M^{\prime}(u_{i})=z_{i}$, then in the restriction of $M^{\prime}$ to $G$ both
$u_{i}$ and $w_{j}$ were unmatched, so they were both in $H$. As we extended
$M$ with a stable matching in $H$, we get that the edge $(u_{i},w_{j})$ cannot
block, contradiction.

Hence, from now we may assume that $w_{j}$ is matched in $M^{\prime}$, hence
has the same partner as in $M$. Let $u_{i^{\prime}}$ be the partner of $w_{j}$
in $M$. If $u_{i}$ in unmatched in $M^{\prime}$, then
$M^{\prime}\setminus\\{M^{\prime}(w_{j})\\}\cup\\{(u_{i},w_{j})\\}$ dominates
$M^{\prime}$, contradiction.

Suppose that $M^{\prime}(u_{i})\in W$, so $M^{\prime}(u_{i})=M(u_{i})$. Then,
we create a matching $N^{\prime}$ as follows. Delete the edge
$M^{\prime}(u_{i}),M^{\prime}(w_{j})$ and
$(z_{i^{\prime}},z_{i^{\prime}}^{\prime})$ from $M^{\prime}$, and add
$(u_{i},w_{j})$ and $(u_{i^{\prime}},z_{i^{\prime}})$. Now, if we compare
$N^{\prime}$ to $M^{\prime}$, $z_{i^{\prime}},u_{i^{\prime}}$ vote with $-1$,
$u_{i},w_{j}$ also vote with $-1$, as $e=(u_{i},w_{j})$ is a blocking edge to
$M$ and hence $M^{\prime}$ and only $z_{i^{\prime}}^{\prime}$ and $u_{i}$’s
original partner vote with $+1$, everyone else votes with $0$. Hence,
$\Delta^{weak}(M^{\prime},N^{\prime})<0$, contradiction.

Suppose finally that $M^{\prime}(u_{i})=z_{i}$. Create $N^{\prime}$ from
$M^{\prime}$ by deleting $(u_{i},z_{i}),M^{\prime}(w_{j})$ and
$(z_{i^{\prime}},z_{i^{\prime}}^{\prime})$ and adding
$(z_{i},z_{i}^{\prime}),(u_{i},w_{j})$ and $(u_{i^{\prime}},z_{i^{\prime}})$.
Then, $z_{i}^{\prime},w_{j},u_{i^{\prime}},z_{i^{\prime}}$ all vote with $-1$
against $N^{\prime}$ and only $z_{i},u_{i},z_{i^{\prime}}^{\prime}$ vote with
$+1$, so $\Delta^{weak}(M^{\prime},N^{\prime})<0$, contradiction.
$\blacksquare$

######  Claim.

Let $M$ be a stable matching of size at least $n-l$ in $I$. Then there is a
weakly-popular matching of size $2n-l$ in $I^{\prime}$.

Proof: Let $M^{\prime}$ be the matching we get from $M$ as follows. For each
unmatched $u_{i}$ in $M$, we add the edge $(u_{i},z_{i})$ and for matched
$u_{j}$ in $M$, we add the edge $(z_{j},z_{j}^{\prime})$.

Suppose that there is a matching $N^{\prime}$ such that
$\Delta^{weak}(M^{\prime},N^{\prime})<0$. We may suppose that $N^{\prime}$ is
(inclusionwise) maximal.

Observe, that since $M$ is stable, if we add the two votes on an edge
$e=(u,w)\in N^{\prime}$, with $u,w\in U\cup W$, then we get at least $0$.
Indeed, by the definition of the votes, if one of them votes with $0$, then so
does the other one, and therefore if
$\textit{vote}^{weak}_{u}(M^{\prime},N^{\prime})+\textit{vote}^{weak}_{w}(M^{\prime},N^{\prime})<0$,
then both votes are $-1$, but this means that $(u,w)$ blocks $M$,
contradiction.

Let $x$ be the number of agents in $W$ who are matched in $M^{\prime}$ but are
not matched in $N^{\prime}$ and denote them by $X$. Let $y$ be the number of
agents in $U$ who are matched to a $z_{i}$ agent in $M^{\prime}$, but are not
matched to one in $N^{\prime}$ and denote them by $Y$. Then, there are $x$
agents who vote with $+1$, but we do not count them on the edges of $N$. Also,
there are $y$ agents from $U$, who vote with $+1$. Also, if such an $u_{i}$
agent has a partner $w_{j}\in W$ in $N^{\prime}$, then $w_{j}$ also votes with
$+1$, as otherwise the edge $(u_{i},w_{j})$ would have blocked $M$, as $u_{i}$
was unmatched in $M$, contradiction.

Any edge of $N^{\prime}$, where both endpoints vote with $-1$ must be of the
form $(u_{i},z_{i})$. Let the number of these be $z$ and denote them with $Z$.
Then, these edges together give us $-2z$ aggregate votes, but the original
partners of the $z_{i}$ agents vote with $+1$ in this case. Our goal is to
show that $z\leq x+y$. In this case, the $x$ votes of $+1$ of the agents in
$X$ and the $y$ votes of $+1$ of the ones in $Y$ cancel the $z$ votes of $-1$
of the agents in $Z$, and therefore we get that
$\Delta^{weak}(M^{\prime},N^{\prime})\geq 0$, contradiction.

Each agent from the set $Z$ had a partner in $W$ originally that he is not
matched to in $N^{\prime}$. As the agents in $W$ can only be matched to agents
from $U$, we get that because of each $u\in Z$, either there is one less agent
in $W$ matched in $N^{\prime}$ or one less agent in $U$ that is matched to
some $z_{i}$. Hence, we indeed have $z\leq x+y$.  $\blacksquare$

Hence, it is NP-hard to decide if there is a weakly-popular matching of size
at least $n+k$. ∎

##  4 Approximating max-$\gamma$-PM

In this section we describe our $\frac{3}{4}$-approximation algorithm for
max-$\gamma$-PM.

We start by giving a high level idea of the algorithm, which is the same as in
privious approaches (Yokoi (2021),Kamiyama (2020),Csáji et al. (2023), Csáji
(2023)).

Let $I$ be an instance of max-$\gamma$-PM.

1\. Create an instance $I^{\prime}$ of the stable marriage problem with strict
preferences by making parallel copies of each edge and create strict
preferences over the created edges.

2\. Run the Gale-Shapley algorithm to obtain a stable matching $M^{\prime}$ in
the new instance $I^{\prime}$

3\. Take the projection $M$ of $M^{\prime}$ in $I$ by taking an edge $e$
inside $M$, whenever one of the parallel copies of $e$ was inside
$M^{\prime}$.

We describe the algorithm in more detail as follows. Let $I$ be an instance of
max-$\gamma$-PM. For each edge $e$, we create parallel copies
$a(e),b(e),c(e),x(e),y(e),z(e)$.

Then, we create strict preferences as follows. For a vertex $u\in U$, we rank
the copies according to the rule

$a\succeq^{\gamma}b\succ c\succ x\succeq^{\gamma}y\succ z$.
For a vertex $w\in W$, we rank the copies according to the rule

$z\succeq^{\gamma}y\succ x\succ c\succeq^{\gamma}b\succ a$.
For any non-$b,y$ copy, we rank the edges of the same copy according to the
preference functions $p_{v}()$ by breaking the ties arbitrarily. Here,
$\alpha\succ\beta$ denotes that for any two edges $e,f$, the copy $\alpha(e)$
is always ranked higher than the copy $\beta(f)$. The notion
$\alpha\succeq^{\gamma}\beta$ means that $\alpha(e)\succ_{v}\beta(e)$ for any
edge $e$, and $\beta(f)\succ_{v}\alpha(e)$, if and only if $p_{v}(f)\geq
p_{v}(e)+\gamma_{f}^{v}$.

This ranking can be obtained in the following way. For each vertex $u\in U$
rank the $a,c,x,y$ copies strictly after each other according to $p_{v}()$ by
breaking the ties arbitrarily. Then, we can insert the $b$ and $y$ copy of
each edge $f$, such that $b(f)\succ_{u}a(e)$, if and only if $p_{u}(f)\geq
p_{u}(e)+\gamma_{f}^{u}$ and $b(f)\succ_{u}c(g)$ for any edge $g$. Similarly
we can insert the $y$ copies such that $y(f)\succ_{u}x(e)$ if and only if
$p_{u}(f)\geq p_{u}(e)+\delta_{f}^{u}$ and that
$c(g)\succ_{u}y(f)\succ_{u}z(g)$ for any edge $g$.

For the $W$ side, we do it similarly, according to their ranking.

If there are still some ties remaining, we break them arbitrarily.

We remark that this definition allows the $b$ and $y$ copies to be ranked in a
different order than $p_{v}()$, similarly as in Csáji (2023).

######  Theorem 4.1.

Let $M$ be the output of the algorithm. Then, it holds that

  * $\bullet$

$M$ is $\gamma$-popular,

  * $\bullet$

for any matching $N$, $|M|\geq\frac{2}{3}|N|$,

  * $\bullet$

for any $\gamma$-popular matching $N$, $|M|\geq\frac{3}{4}|N|$ and

  * $\bullet$

for any $\gamma$-max stable matching $N$, $|M|\geq\frac{4}{5}|N|$.

###### Proof.

We start by showing that $M$ is indeed $\gamma$-popular. For an edge $e\in M$,
we use the notation $M^{\prime}(e)$ to denote the copy of $e$ that is included
in $M^{\prime}$. First, let $N$ be any matching.

######  Claim.

Let $e=(u,w)\in N$ be an edge. Then, the following holds:

  1. 1.

At least one of $\\{u,w\\}$ are matched.

  2. 2.

If $u$ or $w$ is unmatched in $M^{\prime}$, then
$\textit{vote}^{\gamma}_{u}(M,N)+\textit{vote}^{\gamma}_{w}(M,N)=0$.
Furthermore, in the first case, $M^{\prime}(w)$ is of type $y$ or $z$ and in
the second case, $M^{\prime}(u)$ is of type $a$ or $b$.

  3. 3.

If $M^{\prime}(u)$ is of type $a,b$ or $c$ and $M^{\prime}(w)$ is of type
$a,b$ or $c$ too, then
$\textit{vote}^{\gamma}_{u}(M,N)+\textit{vote}^{\gamma}_{w}(M,N)\geq 0$.

  4. 4.

If $M^{\prime}(u)$ is of type $a,b$ or $c$ and $M^{\prime}(w)$ is of type
$x,y$ or $z$ too, then
$\textit{vote}^{\gamma}_{u}(M,N)+\textit{vote}^{\gamma}_{w}(M,N)\geq-2$.

  5. 5.

If $M^{\prime}(u)$ is of type $x,y$ or $z$ and $M^{\prime}(w)$ is of type
$a,b$ or $c$ too, then
$\textit{vote}^{\gamma}_{u}(M,N)+\textit{vote}^{\gamma}_{w}(M,N)=+2$.

  6. 6.

If $M^{\prime}(u)$ is of type $x,y$ or $z$ and $M^{\prime}(w)$ is of type
$x,y$ or $z$ too, then
$\textit{vote}^{\gamma}_{u}(M,N)+\textit{vote}^{\gamma}_{w}(M,N)=0$.

Proof: 1\. If $u,w$ are both unmatched, then this means that $M^{\prime}$ is
not maximal, contradicting that it is stable.

2\. Suppose that $u$ is unmatched in $M^{\prime}$. Then, as the edge $z(e)$
does not block, we get that $M^{\prime}(w)$ is either an edge of type $y$ or
of type $z$. Let $M(w)=g$. Suppose that
$\textit{vote}^{\gamma}_{w}(M,N)\neq+1$. Then, $p_{w}(e)\geq
p_{w}(g)+\gamma_{e}^{w}$. This implies that
$z(e)\succ_{w}z(g)\succeq_{w}M^{\prime}(w)$, so $z(e)$ blocks $M^{\prime}$,
contradiction. Hence, $\textit{vote}^{\gamma}_{w}(M,N)=+1$, so
$\textit{vote}^{\gamma}_{u}(M,N)+\textit{vote}^{\gamma}_{w}(M,N)=0$. The case
when $w$ is unmatched in similar.

From now on, let $f=M(u)$ and $g=M(w)$.

3\. As $\textit{vote}^{\gamma}_{u}(M,N)\neq 0$ and
$\textit{vote}^{\gamma}_{w}(M,N)\neq 0$, it is enough to show that
$\textit{vote}^{\gamma}_{u}(M,N)=\textit{vote}^{\gamma}_{w}(M,N)=-1$ is
impossible. Suppose for the contrary that this holds. Then, we know that
$p_{u}(e)\geq p_{u}(f)+\gamma_{e}^{u}$ and $p_{w}(e)\geq
p_{w}(g)+\gamma_{e}^{w}$. From this, we get that
$b(e)\succ_{u}a(f)\succeq_{u}M^{\prime}(u)$ and
$b(e)\succ_{w}c(g)\succeq_{w}M^{\prime}(w)$, therefore $b(e)$ blocks
$M^{\prime}$, contradiction.

4\. This is trivial, as both votes are at least $-1$.

5\. Suppose that $\textit{vote}^{\gamma}_{u}(M,N)=-1$. Then, $p_{u}(e)\geq
p_{u}(f)+\gamma_{e}^{u}$. Hence, $y(e)\succ_{u}x(f)\succeq_{u}M^{\prime}(u)$
and $y(e)\succ_{w}c(g)\succeq M^{\prime}(w)$, therefore $y(e)$ blocks
$M^{\prime}$, contradiction. If $\textit{vote}^{\gamma}_{w}(M,N)=-1$, then
$p_{w}(e)\geq p_{w}(g)+\gamma_{e}^{w}$ and so $b(e)$ blocks $M^{\prime}$
contradiction.

6\. The proof of the last statement is analogous of the proof of point 3.

$\blacksquare$

######  Claim.

$M$ is $\gamma$-popular.

Proof: Suppose for the contrary that there is a matching $N$, such that
$\Delta^{\gamma}(M,N)<0$. Consider the symmetric difference of the two
matchings, $M\triangle N$. Then, there must be a component $P$ of $M\triangle
N$, such that $\Delta^{\gamma}(M\cap P,N\cap P)<0$.

For each edge $f\in M\cap P$, let $t(f)=0$, if
$M^{\prime}(f)\in\\{a(f),b(f),c(f)\\}$ and $t(f)=1$ if
$M^{\prime}(f)\in\\{x(f),y(f),z(f)\\}$. Then, for any edge $e=(u,w)\in N$, if
it is between $M$-edges $f=M(u)$ and $g=M(w)$ with $t(f)=t(g)$, by Claim 4 we
obtain that
$\textit{vote}^{\gamma}_{u}(M,N)+\textit{vote}^{\gamma}_{w}(M,N)\geq 0$. If
$t(f)=1-t(g)=0$, then
$\textit{vote}^{\gamma}_{u}(M,N)+\textit{vote}^{\gamma}_{w}(M,N)\geq-2$ and if
$t(f)=1-t(g)=1$, then
$\textit{vote}^{\gamma}_{u}(M,N)+\textit{vote}^{\gamma}_{w}(M,N)=+2$.

Therefore, from $\Delta^{\gamma}(M\cap P,N\cap P)<0$ and Claim 4 point 2, we
get that there must be strictly more edges $e=(u,w)\in N\cap P$ with
$t(M(u))=1-t(M(w))=0$ then with $t(M(u))=1-t(M(w))=1$. In particular, $P$ must
be a path.

From the two possible ordering of the vertices (and hence also the edges) of
$P$, consider the one, where the first vertex that is matched in $M$ is from
$U$, and hence the last vertex matched by $M$ is from $W$. From now on, by the
$k$-th edge of $M\cap P$, we mean the $k$-th $M$-edge in this ordering.

Now, by the above, the first edge of $M$ has a type $x,y$ or $z$ copy in
$M^{\prime}$ and last edge has a type $a,b$ or $c$. However, this implies that
both the first and last edges of $P$ must be $M$-edges. Indeed, if the first
edge would be an $N$-edge, then the first vertex is an agent $w_{1}$, and by
Claim 4 point 2, we obtain that the first $M$-edge must be of type $a,b$ or
$c$, contradiction. Similarly, if the last edge is an $N$-edge, than the last
$M$-edge has to by of type $x,y$ or $z$ contradiction again. Hence, there are
two vertices in $P$ that are only covered in $M$ and zero vertices that are
only covered in $N$, so even though $\sum_{v\in V(N\cap
P)}\textit{vote}^{\gamma}_{v}(M,N)\geq-2$, by considering the votes of the two
vertices in $V(M\cap P)\setminus V(N\cap P)$, we obtain that
$\Delta^{\gamma}(M\cap P,N\cap P)\geq 0$, contradiction.

Therefore, we conclude that $M$ is $\gamma$-popular.

$\blacksquare$

Now we proceed to the approximation statements.

######  Claim.

Let $N$ be any matching. Then, $|M|\geq\frac{2}{3}|N|$.

Proof: Clearly, $M$ is maximal, as otherwise $M^{\prime}$ would not be stable.

Suppose for the contrary that there is a path $P$ in $M\triangle N$ which
contains 2 $N$-edges $f,g$ and a middle $M$-edge $e=(u,w)$, where
$f=M(u),g=M(w)$. As $M^{\prime}$ was stable, we obtain that $a(f)$ does not
block $M^{\prime}$, and therefore $M^{\prime}(e)\in\\{a(e),b(e)\\}$.
Similarly, as $z(g)$ does not block $M^{\prime}$, we get that
$M^{\prime}(e)\in\\{z(e),y(e)\\}$, contradiction.  $\blacksquare$

######  Claim.

Let $N$ be any $\gamma$-popular matching. Then, $|M|\geq\frac{3}{4}|N|$.

Proof: Let $N$ be a $\gamma$-popular matching. We have already seen that there
can be no component in $N\triangle M$, with $i$ $M$-edge and $i+1$ $N$-edge
for $i=0,1$.

Suppose for the contrary that there is a component $P$ in $M\triangle N$ with
$2$ $M$-edges and $3$ $N$-edges. Let
$P=\\{w_{1},u_{1},w_{2},u_{2},w_{3},u_{3}\\}$, where $e_{i}=(w_{i},u_{i})\in
N$, $i=1,2,3$ and $f_{i}=(u_{i},w_{i+1})\in M$, $i=1,2$.

As the edge $a(e_{1})$ does not block $M^{\prime}$ and the edge $z(e_{3})$
does not block $M^{\prime}$, we get that
$M^{\prime}(f_{1})\in\\{a(f_{1}),b(f_{1})\\}$ and
$M^{\prime}(f_{2})\in\\{z(f_{2}),y(f_{2})\\}$.

Suppose that $M^{\prime}(f_{1})=a(f_{1})$. Then, $b(e_{2})$ blocks
$M^{\prime}$ contradiction. Similarly, if $M^{\prime}(f_{2})=z(f_{2})$, then
$y(e_{2})$ blocks $M^{\prime}$, contradiction again. This also means that
$p_{u_{1}}(f_{1})\geq p_{u_{1}}(e_{1})+\gamma_{f_{1}}^{u_{1}}$ and
$p_{w_{3}}(f_{2})\geq p_{w_{3}}(e_{3})+\gamma_{f_{2}}^{w_{3}}$ (using again
that $a(e_{1})$ and $z(e_{3})$ do not block $M^{\prime}$).

We conclude that $M^{\prime}(f_{1})=b(f_{1}),M^{\prime}(f_{2})=y(f_{2})$. Now,
using that $x(e_{2})$ does not block $M^{\prime}$, we get that
$p_{u_{2}}(f_{2})\geq p_{u_{2}}(e_{2})+\gamma_{f_{2}}^{u_{2}}.$ The same
argument for $c(e_{2})$ gives $p_{w_{2}}(f_{1})\geq
p_{w_{2}}(e_{2})+\gamma_{f_{1}}^{w_{2}}$.

Putting this together, we get that if we compare the matching
$\hat{N}=N\setminus\\{(w_{i},u_{i})\mid i=1,2,3\\}\cup\\{(u_{i},w_{i+1})\mid
i=1,2\\}$, then agents $u_{1},w_{2},u_{2}$ and $w_{3}$ vote with $-1$, as
their improvement in $\hat{N}$ is large enough from $N$ and only $w_{1}$ and
$u_{3}$ vote with $+1$, every other agents vote with $0$. Hence,
$\Delta^{\gamma}(N,\hat{N})<0$, contradicting that $N$ is $\gamma$-popular.
$\blacksquare$

######  Claim.

For any $\gamma$-max stable matching $N$, we have that
$|M|\geq\frac{4}{5}|N|$.

Proof: Let $N$ be a $\gamma$-max stable matching. As any $\gamma$-max stable
matching is also $\gamma$-popular, by the previous proofs there can be no
component in $N\triangle M$, with $i$ $M$-edge and $i+1$ $N$-edge for
$i=0,1,2$.

Suppose for the contrary that there is a component $P$ in $M\triangle N$ with
$3$ $M$-edges and $4$ $N$-edges. Let
$P=\\{w_{1},u_{1},w_{2},u_{2},w_{3},u_{3},w_{4},u_{4}\\}$, where
$e_{i}=(w_{i},u_{i})\in N$ $i=1,2,3,4$ and $f_{i}=(u_{i},w_{i+1})\in M$,
$i=1,2,3$.

Similar arguments as before give that
$M^{\prime}(f_{1})\in\\{a(f_{1}),b(f_{1})\\}$ and
$M^{\prime}(f_{3})\in\\{z(f_{3}),y(f_{3})\\}$. Now, it is clear that
$M^{\prime}(f_{2})$ is either an $a/b/c$ copy or a $x/y/z$ copy. Suppose that
$M^{\prime}(f_{2})\in\\{a(f_{2}),b(f_{2}),c(f_{2})\\}$. Then, $w_{3}$ prefers
$x(e_{3})$ to $M^{\prime}(f_{2})$. As $x(e_{3})$ does not block $M^{\prime}$,
we get that it must be dominated at $u_{3}$, so $M^{\prime}(f_{3})=y(f_{3})$
and $p_{u_{3}}(f_{3})\geq p_{u_{3}}(e_{3})+\gamma_{f_{3}}^{u_{3}}$. Now
knowing that $M^{\prime}(f_{3})=y(f_{3})$, then we get that
$p_{w_{4}}(f_{3})\geq p_{w_{4}}(e_{4})+\gamma_{f_{3}}^{w_{4}}$. Combining
this, we get that $f_{3}$ $c\gamma$-blocks $N$, which is a contradiction.

The case for $M^{\prime}(f_{2})\in\\{x(f_{2}),y(f_{2}),z(f_{2})\\}$ is
symmetric and leads to $f_{1}$ being a $c\gamma$-blocking edge to $N$.

$\blacksquare$

The theorem follows from the above claims.

∎

##  5 Approximation analysis and inapproximability

First, we give some examples to illustrate that our approximation analysis is
tight in all three cases, even in the case of ordinary weak preferences and
one-sided ties.

######  Example 1.

Consider an instance with agents $\\{w_{1},u_{1},w_{2},u_{2},w_{3},u_{3}\\}$.
Let the edges be $E\cup F$, where $E=\\{e_{i}=(u_{i},w_{i})\mid i=1,2,3\\}$,
$F=\\{f_{i}=(u_{i},w_{i+1})\mid i=1,2\\}$.

All agents with degree $2$ strictly prefer the edge $e_{i}$ to $f_{i}$. In
this instance, each preference is strict, so weak-popularity and popularity
coincide. It is easy to see that the only popular matching is $M=F$, so this
must be the output of the algorithm, but for $N=E$, $\frac{2}{3}|N|=|M|$.

######  Example 2.

Consider an instance with agents
$\\{w_{1},u_{1},w_{2},u_{2},w_{3},u_{3},w_{4},u_{4}\\}$. Let the edges be
$E\cup F$, where $E=\\{e_{i}=(u_{i},w_{i})\mid i=1,2,3,4\\}$,
$F=\\{f_{i}=(u_{i},w_{i+1})\mid i=1,2,3\\}$.

Let the preference lists be: $u_{1}:f_{1}\succ e_{1}$, $u_{2}:f_{2}\succ
e_{2}$, $u_{3}:f_{3}\succ e_{3}$, $u_{4}:e_{4}$ and $w_{1}:e_{1}$,
$w_{2}:f_{1}\sim e_{2}$, $w_{3}:f_{2}\sim e_{3}$, $w_{4}:f_{3}\succ e_{4}$.

First we show that $N=E$ is weakly-popular. It is easy to see that only agents
$u_{1},u_{2},u_{3}$ and $w_{4}$ may vote with $-1$ when comparing $N$ to any
matching $M$. However, whenever $u_{1}$ improves, $w_{1}$ is worse off an
votes with $+1$. Similarly, whenever $u_{2}$ or $u_{3}$ improves, $w_{2}$ and
$w_{3}$ is weakly worse off respectively, so they vote with $+1$. Finally, if
$w_{4}$ improves, than $u_{4}$ is worse off and votes with $+1$. Hence, the
number of $+1$ votes is always at least the number of $-1$ votes, showing that
$N$ is weakly-popular.

Next, we show that the algorithm may terminate in $M=F$. Suppose
$M^{\prime}(f_{1})=b(f_{1}),M^{\prime}(f_{2})=c(f_{2})$ and
$M^{\prime}(f_{3})=y(f_{3})$. Furthermore, suppose that the ties are broken up
in the following way: $w_{2}:f_{1}\succ e_{2}$, $w_{3}:f_{2}\succ e_{3}$,
which implies that $b(f_{1})\succ_{w_{2}}b(e_{2})$ and
$c(f_{2})\succ_{w_{3}}c(e_{3})$. It is straighforward to verify that
$M^{\prime}$ is stable, and $M^{\prime}$ gives $M$ when we project it back.

As $|M|=\frac{3}{4}|N|$, we get that this approximation ratio is tight for the
algorithm.

######  Example 3.

Consider an instance with agents
$\\{w_{1},u_{1},w_{2},u_{2},w_{3},u_{3},w_{4},u_{4},w_{5},u_{5}\\}$. Let the
edges be $E\cup F$, where $E=\\{e_{i}=(u_{i},w_{i})\mid i=1,2,3,4,5\\}$,
$F=\\{f_{i}=(u_{i},w_{i+1})\mid i=1,2,3,4\\}$.

Let the preference lists be: $u_{1}:f_{1}\succ e_{1}$, $u_{2}:f_{2}\succ
e_{2}$, $u_{3}:f_{3}\succ e_{3}$, $u_{4}:e_{4}\succ f_{4}$, $u_{5}:e_{5}$ and
$w_{1}:e_{1}$, $w_{2}:f_{1}\sim e_{2}$, $w_{3}:f_{2}\sim e_{3}$,
$w_{4}:f_{3}\sim e_{4}$, $w_{5}:f_{4}\succ e_{5}$.

We claim that $N=E$ is stable. Indeed, no edge in $F$ blocks $N$.

Let $M=F$. We claim that the algorithm may output $F$. Let
$M^{\prime}(f_{1})=b(f_{1}),M^{\prime}(e_{2})=c(f_{2}),M^{\prime}(f_{3})=x(f_{3})$
and $M^{\prime}(e_{4})=y(f_{4})$. Suppose we break the ties in the following
manner: $w_{2}:f_{1}\succ e_{2}$, $w_{3}:f_{2}\succ e_{3}$, $w_{4}:f_{3}\succ
e_{4}$. Then, it is straightforward to verify that $M^{\prime}$ is stable and
that $M^{\prime}$ gives $M$. Also, as $|M|=\frac{4}{5}|N|$, our approximation
analysis is tight in this case too.

Now we show that assuming either the strong-Unique Games Conjecture (strong-
UGC) or the Small Set Expansion Hypothesis (SSEH) it is NP-hard to approximate
max-weak-pm within a factor of $\frac{3}{4}+\varepsilon$, for any
$\varepsilon>0$.

Dudycz et al. (2022) have shown the following result.

######  Theorem 5.1.

If the strong-UGC or the SSEH holds, then for any $\varepsilon>0$, it is NP-
hard to distinguish for a bipartite graph $G=(U,W,E)$ with $|U|=|W|=n$ the
below two cases:

  * $\bullet$

There is a maximal matching in $G$ of size at most
$(\frac{1}{2}+\varepsilon)n$ or

  * $\bullet$

every maximal matching in $G$ has at least $(1-\varepsilon)n$ edges.

######  Theorem 5.2.

Assuming either the strong-UGC or the SSEH, it is NP-hard to approximate max-
weak-pm within a factor of $(\frac{3}{4}+\varepsilon)$, for any
$\varepsilon>0$.

###### Proof.

We show that for any $\varepsilon>0$, such an approximation algorithm for max-
weak-pm implies that we can distinguish between the two cases of Theorem 5.1,
which is a contradiction.

Let $\varepsilon>0$ and let $G=(U,W,E)$ be a bipartite graph with $|U|=|W|=n$,
where $U=\\{u_{1},\dots,u_{n}\\}$ and $W=\\{w_{1},\dots,w_{n}\\}$, call this
instance $I$. We may assume that $n$ is even, otherwise we duplicate $G$ and
get an equivalent problem. We create an instance $I^{\prime}$ of max-weak-pm.
We create sets of agents
$W^{\prime}=\\{w_{1}^{\prime},\dots,w_{n}^{\prime}\\}$,
$U^{\prime}=\\{u_{1}^{\prime},\dots,u_{\frac{n}{2}}^{\prime}\\}$,
$Z=\\{z_{1},\dots,z_{\frac{n}{2}}\\}$ and
$Z^{\prime}=\\{z_{1}^{\prime},\dots,z_{\frac{n}{2}}^{\prime}\\}$. We create
the edges of the instance in $I^{\prime}$, by keeping the edges induced by
$G$, and adding $\\{(w_{i},w_{i}^{\prime})\mid
i\in[n]\\}\cup\\{(u_{j}^{\prime},z_{j}),(z_{j},z_{j}^{\prime})\mid
j\in[\frac{n}{2}]\\}\cup\\{(u_{i},u_{j}^{\prime})\mid
i\in[n],j\in[\frac{n}{2}]\\}$.

The preferences are illustrated in Figure 1. Because the created graph is
simple, we write the weak preferences over the set of neigbhors $V(u)$ for an
agent $u$ intead of over $E(u)$. $V_{G}(v)$ denotes the set of neighbors of
$v$ in $G$, and $[X]$ for a set $X$ means that the elements of $X$ form a
single tie in the preference list.

$u_{i}:$ | $[V_{G}(u_{i})]\succ[U^{\prime}]$ | $w_{i}:$ | $[V_{G}(w_{i})]\succ w_{i}^{\prime}$
---|---|---|---
$w_{i}^{\prime}:$ | $w_{i}$ | $u_{j}^{\prime}:$ | $z_{j}\succ[U]$
$z_{j}:$ | $u_{j}^{\prime}\succ z_{j}^{\prime}$ | $z_{j}^{\prime}:$ | $z_{j}$
Figure 1: The created preferences in Theorem 5.2. Here,
$i\in[n],j\in[\frac{n}{2}]$

Let $k\geq\frac{n}{2}$.

######  Claim.

Suppose that there is a weakly-popular matching $M^{\prime}$ in $I^{\prime}$
of size at least $\frac{5}{2}n-k$. Then, there is a maximal matching in $G$ of
size at most $k$.

Proof: Let $M$ be the restriction of $M^{\prime}$ to $G$. Suppose that
$|M|=k^{\prime}>k$. Then, we get that the size of $M^{\prime}$ is at most
$(n-k^{\prime})+k^{\prime}+(n-k^{\prime})+\frac{n}{2}=\frac{5}{2}n-k^{\prime}<\frac{5}{2}n-k$,
contradiction.

Therefore, it is enough to show that $M$ is maximal. Suppose that
$(u_{i},w_{j})$ is an edge of $G$ that can be added to $M$. If $u_{i}$ or
$w_{j}$ is unmatched in $M^{\prime}$, then at most one of them leaves a
partner behind if they get matched together and strictly improve, so we obtain
a matching that dominates $M^{\prime}$, contradiction.

Hence, $(w_{j},w_{j}^{\prime})\in M^{\prime}$ and $(u_{i},u_{l}^{\prime})\in
M^{\prime}$ for some $l\in[\frac{n}{2}]$. Hence also
$(z_{l},z_{l}^{\prime})\in M^{\prime}$ as a weakly-popular matching must be
maximal. Let $N^{\prime}$ be the matching
$M^{\prime}\setminus\\{(w_{j},w_{j}^{\prime}),(u_{i},u_{l}^{\prime}),(z_{l},z_{l}^{\prime})\cup\\{(u_{i},w_{j}),(u_{l}^{\prime},z_{l})\\}$.
Then, $u_{i},w_{j},u_{l}^{\prime},z_{l}$ all improve and vote with $-1$ and
only $w_{j}^{\prime}$ and $z_{l}^{\prime}$ vote with $+1$. Hence, $N^{\prime}$
dominates $M^{\prime}$, contradiction.  $\blacksquare$

######  Claim.

If there is a maximal matching of size $k$ in $G$, then there is a weakly-
popular matching of size at least $\frac{5}{2}n-k$ in $I^{\prime}$.

Proof: Let $M$ be such a matching of $G$. Extend it to a matching $M^{\prime}$
of $I^{\prime}$ as follows. For each $i\in[n]$, such that $w_{i}$ is unmatched
in $M$, add $(w_{i},w_{i}^{\prime})$. Let $\\{u_{i_{1}},\dots,u_{i_{n-k}}\\}$
be the unmatched agents in $U$ by $M$. Then, we add the edges
$(u_{i_{j}},u_{j}^{\prime}),(z_{j},z_{j}^{\prime})$ for $j\in[n-k]$. As
$n-k\leq\frac{n}{2}$, we can do this. Finally, if $n-k<\frac{n}{2}$, then for
each $n-k<j\leq\frac{n}{2}$ we add $(u_{j}^{\prime},z_{j})$. Clearly
$|M^{\prime}|=(n-k)+k+2(n-k)+(\frac{n}{2}-(n-k))=\frac{5}{2}n-k$.

We show that $M^{\prime}$ is weakly-popular. From the fact that $M$ is
inclusionwise maximal, we get that the only blocking edges to $M^{\prime}$ are
the edges $(u_{j}^{\prime},z_{j})$, $j\in[n-k]$. Therefore, these are the only
possible $(-1,-1)$ voting edges in an other matching.

Suppose that a matching $N^{\prime}$ dominates $M^{\prime}$. Take the
components of the symmetric difference $N^{\prime}\triangle M^{\prime}$. Then,
there is a component, such that within this component, $N^{\prime}$ also
dominates $M^{\prime}$. In such a component, there must be an edge $e$ of
$N^{\prime}$, such that both of its endpoints vote with $-1$. As we have seen,
such an edge must be $(u_{j}^{\prime},z_{j})$, for some $j\in[n-k]$. As for a
vertex $z_{j}$, his only other neighbor is $z_{j}^{\prime}$, which is a leaf
vertex, we get that at most two such edges can be in any component and the
component cannot be a cycle. Also, if $(u_{j}^{\prime},z_{j})\in N^{\prime}$,
then $z_{j}^{\prime}$ is unmatched in $N^{\prime}$, but is matched in
$M^{\prime}$, so such edges can only be in components in $M^{\prime}\triangle
N^{\prime}$, where they are adjacent to an $M^{\prime}$-edge, whose other
endpoint is only covered by $M^{\prime}$.

Let $(u_{j}^{\prime},z_{j})\in N^{\prime}$. If $u_{i_{j}}$ is unmatched in
$N^{\prime}$, then he and $z_{j}^{\prime}$ vote with $+1$ in the component and
only $u_{j}^{\prime}$ and $z_{j}$ vote with $-1$, contradiction.

If $(u_{i_{j}},u_{l}^{\prime})\in N^{\prime}$, then both of them vote with
$+1$, so there is a $(+1,+1)$ edge. Hence, even if there are two $(-1,-1)$
edges of $N^{\prime}$ in the component, the $(+1,+1)$ edge and the two $+1$
votes by the endpoints only covered by $M^{\prime}$ cancel those,
contradiction.

So $(u_{i_{j}},w_{i})\in N^{\prime}$ for some $i\in[n]$. As $M$ was maximal
and $(u_{i_{j}},u_{j}^{\prime})\in M^{\prime}$, we get that $w_{i}$ was
matched in $M$, so $(u_{l},w_{i})\in M^{\prime}$ for some $l\in[n]$. This
implies $u_{l}$ and $w_{i}$ both vote with $+1$ in any case. Now, if $u_{l}$
is unmatched in $N^{\prime}$, then there is only one $(-1,-1)$ edge in the
component, but both endpoints of the component vote with $+1$, contradiction.
If $u_{l}$ and his partner in $N^{\prime}$ both vote with $+1$, then we have a
$(+1,+1)$ edge and we get a contradiction by similar reasoning as before.
Otherwise, the partner of $u_{l}$ in $N^{\prime}$ must strictly improve from
$M^{\prime}$, hence $(u_{l},w_{m})\in N^{\prime}$ for an agent $w_{m}$ who was
unmatched in $M$, so $(w_{m},w_{m}^{\prime})\in M^{\prime}$. As
$w_{m}^{\prime}$ is a leaf, we get that in this case, this is the whole
component. However, as both endpoints are only covered by $M^{\prime}$, we get
that those two $+1$ votes cancel the $(-1,-1)$ edge, a contradiction.

Hence we conclude that $M^{\prime}$ is weakly-popular.  $\blacksquare$

Now suppose for the contrary that there is a
$(\frac{3}{4}+\varepsilon)$-approximation algorithm for max-weak-pm. We may
assume that $n$ is larger than $\frac{1}{\varepsilon}$. Now, if every maximal
matching of $G$ has size at least $(1-\varepsilon)n$ edges, then any weakly-
popular matching in $I^{\prime}$ has size at most
$\frac{5}{2}n-(1-\varepsilon)n$ by Claim 5. Also, if there is a maximal
matching of size at most $(\frac{1}{2}+\varepsilon)n>\frac{n}{2}+1$ edges,
then there is one with $\frac{n}{2}\leq k<(\frac{1}{2}+\varepsilon)n$ edges
(if $k<\frac{n}{2}$, then we increase it by one via an alternating path and
get a larger maximal matching, as we may assume that $G$ has a matching of
size at least $\frac{n}{2}$, otherwise distinguishing the cases is easy) and
by Claim 5 we have that there is a weakly popular matching of size at least
$\frac{5}{2}n-k\geq(2-\varepsilon)n$.

Now, because
$(2-\varepsilon)n\cdot(\frac{3}{4}+\varepsilon)=\frac{3}{2}n-\frac{3}{4}\varepsilon
n+2\varepsilon
n-\varepsilon^{2}n>(\frac{3}{2}+\varepsilon)n=\frac{5}{2}n-(1-\varepsilon)n$
for $\varepsilon<\frac{1}{2}$, we get that by Claim 5, that if the first case
of Theorem 5.1 holds, then we can find a maximal matching of size strictly
less than $(1-\varepsilon)n$, which is a contradiction. ∎

##  6 Super-popular matchings

In this final section we show that even deciding if a super-popular matching
exists is NP-hard.

######  Theorem 6.1.

Deciding if an instance $I$ of super-pm admits a super popular matching is NP-
hard even with ordinary weak preferences, where only two agents have ties, and
both have just a single tie of length two.

###### Proof.

We reduce from the NP-hard problem (0,1,1,0)-pm, which is the problem of
deciding whether an instance $I$ of the popular matching problem with strict
preferences contains a popular matching $M$, that does not contain a given
forbidden edge $(x,y)$ and cover a given forced vertex $t\neq x,y$. By the
reduction of Faenza et al. (2018), we may assume that it holds that $x$ is a
leaf, and $y$ has only one other neighbor $z$ (other than $x$), such that $y$
and $z$ are each others’ first ranked agents.

Let $I$ be an instance of (0,1,1,0)-pm. We create an instance $I^{\prime}$ of
super-pm as follows. We keep each vertex and edge from $I$. Furthermore, we
add vertices $d_{x},x^{\prime},d_{t},t^{\prime}$ along with edges
$(x,d_{x}),(x^{\prime},d_{x}),(t,d_{t}),(t^{\prime},d_{t})$. Then, the graph
is still clearly bipartite.

We let the preference of $d_{x}$ be $x\succ x^{\prime}$ and the preference of
$d_{t}$ be $t\sim t^{\prime}$, where $\sim$ denotes a tie. Furthermore, we
extend $t$’s preference list by adding $d_{t}$ to the end and also $x$’s
preference list from $y$ to $d_{x}\sim y$.

######  Claim.

If there is a super-popular matching in $I^{\prime}$, then there is a popular
matching in $I$, which excludes $(x,y)$ and covers $t$.

Proof: Let $M^{\prime}$ be a super-popular matching in $I^{\prime}$. Let $M$
be the restriction of $M^{\prime}$ to $I$.

We first show that $t$ is covered in $M$. Suppose otherwise. Then, if
$(t,d_{t})\in M^{\prime}$, we get that
$M^{\prime}\setminus\\{(t,d_{t})\\}\cup\\{(t^{\prime},d_{t})\\}$ dominates
$M^{\prime}$, as $d_{t}$ and $t^{\prime}$ vote with $-1$ and only $t$ votes
with $+1$. Similarly, if $(t,d_{t})\notin M^{\prime}$, then
$M^{\prime}\setminus\\{(t^{\prime},d_{t})\\}\cup\\{(t,d_{t})\\}$ domintes
$M^{\prime}$, contradiction.

Next we show that $(x,y)\notin M$. Suppose that $(x,y)\in M^{\prime}$. Then
$(x^{\prime},d_{x})\in M^{\prime}$. Also, $M(z)\neq\emptyset$, because
otherwise $M^{\prime}\setminus\\{(x,y)\\}\cup\\{(y,z)\\}$ dominates
$M^{\prime}$. However, the matching
$M^{\prime}\setminus\\{(x^{\prime},d_{x}),(x,y),M(z)\\}\cup\\{(x,d_{x}),(y,z)\\}$
dominates $M^{\prime}$, because $x,y,z$ and $d_{x}$ all vote with $-1$ and
only $x^{\prime}$ and $z$’s partner in $M^{\prime}$ vote with $+1$.

These observations also imply that $(t^{\prime},d_{t})\in M^{\prime}$ and
$(x,d_{x})\in M^{\prime}$.

Finally, we show that $M$ is popular. Suppose that a matching $N$ dominates
$M$. Create $N^{\prime}$ from $N$ by adding $(t^{\prime},d_{t})$ and
$(x,d_{x})$, if $N(x)=\emptyset$ and $(x^{\prime},d_{x})$ otherwise. In both
cases, the sum of the votes of $t^{\prime},d_{t},x^{\prime},d_{x}$ is $0$.
Also, no original agent may have a smaller vote, because apart from $x$, each
of them has the same situation in $M^{\prime}$ and $M$; and also $N^{\prime}$
and $N$. For agent $x$, if $(x,d_{x})\in N^{\prime}$, then he votes with 0 in
both $M$ versus $N$ in $I$ and $M^{\prime}$ versus $N^{\prime}$ in
$I^{\prime}$. Otherwise, his vote is $-1$ in the former and also $-1$ in the
latter case. Hence, we get that the sum of votes in the comparison of
$M^{\prime}$ and $N^{\prime}$ is negative, contradictiong that $M^{\prime}$ is
super-popular.  $\blacksquare$

######  Claim.

If there is a popular matching $M$ in $I$ that excludes $(x,y)$ and covers
$t$, then there is a super-popular matching in $I^{\prime}$.

Proof: Let $M$ be such a popular matching in $I$. Then, we can extend $M$ to
$M^{\prime}$ in $I^{\prime}$ by adding the edges $(x,d_{x})$ and
$(t^{\prime},d_{t})$. Suppose that some matching $N^{\prime}$ dominates
$M^{\prime}$.

Let $N$ be the restriction of $N^{\prime}$ to $I$. Each original agent other
than $x$ and $t$ must have the same partners in both $M$ and $M^{\prime}$ and
also in $N$ and $N^{\prime}$, hence their vote is the same.

Consider agent $t$. He has the same partner in $M$ and $M^{\prime}$. Suppose
he has a different partner in $N$ than in $N^{\prime}$. Then, $(t,d_{t})\in
N^{\prime}$ and $t$ is unmatched in $N$. As $d_{t}$ is the strictly worst
neighbor of $t$ in $I^{\prime}$, we get that $t$ votes with $+1$ in both
instances.

Consider agent $x$. Suppose that $x$ is matched in $N$, so $(x,y)\in N$ and
$(x,y)\in N^{\prime}$. As $x$ was unmatched in $M$ and $(x,d_{x})\in
M^{\prime}$, we get that $x$ votes with $-1$ in both instances. If $x$ is not
matched in $N$, but is matched in $N^{\prime}$, then $(x,d_{x})\in N^{\prime}$
and $x$ votes with $0$ in both cases. Finally, if $x$ is unmatched in both $N$
and $N^{\prime}$, then in $I$ he votes with $0$ in $M$ versus $N$, but he
votes with $+1$ in $M^{\prime}$ versus $N^{\prime}$, which is larger.

It is easy to check that the sum of the votes of
$x^{\prime},d_{x},t^{\prime},d_{t}$ are always 0. Hence, we obtain that $N$
must dominate $M$, contradiction.  $\blacksquare$ ∎

##  7 Conclusion and future work

In this paper we introduced a new natural notion of popularity in two-sided
matching markets with ties. We have shown that with our definition, a weakly-
popular matching always exists. We also provided an algorithm that finds a
$\frac{3}{4}$-approximation to the maximum size $\gamma$-popular matching
problem, which is also a $\frac{4}{5}$-approximation for the maximum size
$\gamma$-max stable matching problem. We also proved that the ratio of
$\frac{3}{4}$ is tight assuming that either the strong-UGC or the Small Set
Expansion Hypothesis holds.

For super popularity, we have show that even the existence problem is NP-hard.
However, our proof only works for two-sided ties, so with one-sided ties, the
problem may become solvable, which we leave as an open question.

##  8 Acknowledgements

The work was supported by the Lendület Programme of the Hungarian Academy of
Sciences – grant number LP2021-1/2021, by the Hungarian National Research,
Development and Innovation Office – NKFIH, grant number K143858.

## References

  * Abraham et al. (2007) D. J. Abraham, R. W. Irving, T. Kavitha, and K. Mehlhorn.  Popular matchings.  _SIAM Journal on Computing_ , 37(4):1030–1045, 2007.
  * Chen et al. (2021) J. Chen, P. Skowron, and M. Sorge.  Matchings under preferences: Strength of stability and tradeoffs.  _ACM Transactions on Economics and Computation_ , 9(4):1–55, 2021.
  * Csáji (2023) G. Csáji.  A simple 1.5-approximation algorithm for a wide range of max-smti problems.  _arXiv e-prints_ , pages arXiv–2304, 2023.
  * Csáji et al. (2023) G. Csáji, T. Király, and Y. Yokoi.  Approximation algorithms for matroidal and cardinal generalizations of stable matching.  In _Symposium on Simplicity in Algorithms (SOSA)_ , pages 103–113. SIAM, 2023.
  * Cseh (2017) Á. Cseh.  Popular matchings.  _Trends in computational social choice_ , 105(3), 2017.
  * Cseh et al. (2017) Á. Cseh, C.-C. Huang, and T. Kavitha.  Popular matchings with two-sided preferences and one-sided ties.  _SIAM Journal on Discrete Mathematics_ , 31(4):2348–2377, 2017.
  * Dudycz et al. (2022) S. Dudycz, P. Manurangsi, and J. Marcinkowski.  Tight inapproximability of minimum maximal matching on bipartite graphs and related problems.  In _Approximation and Online Algorithms: 19th International Workshop, WAOA 2021, Lisbon, Portugal, September 6–10, 2021, Revised Selected Papers_ , pages 48–64. Springer, 2022.
  * Faenza et al. (2018) Y. Faenza, V. Powers, and X. Zhang.  Two-sided popular matchings in bipartite graphs with forbidden/forced elements and weights.  _arXiv preprint arXiv:1803.01478_ , 2018.
  * Faenza et al. (2019) Y. Faenza, T. Kavitha, V. Powers, and X. Zhang.  Popular matchings and limits to tractability.  In _Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 2790–2809. SIAM, 2019.
  * Gale and Shapley (1962) D. Gale and L. S. Shapley.  College admissions and the stability of marriage.  _The American Mathematical Monthly_ , 69(1):9–15, 1962.
  * Gärdenfors (1975) P. Gärdenfors.  Match making: assignments based on bilateral preferences.  _Behavioral Science_ , 20(3):166–173, 1975.
  * Gupta et al. (2021) S. Gupta, P. Misra, S. Saurabh, and M. Zehavi.  Popular matching in roommates setting is np-hard.  _ACM Transactions on Computation Theory (TOCT)_ , 13(2):1–20, 2021.
  * Halldórsson et al. (2002) M. Halldórsson, K. Iwama, S. Miyazaki, and Y. Morita.  Inapproximability results on stable marriage problems.  In _LATIN 2002: Theoretical Informatics: 5th Latin American Symposium Cancun, Mexico, April 3–6, 2002 Proceedings 5_ , pages 554–568. Springer, 2002.
  * Halldórsson et al. (2003) M. M. Halldórsson, K. Iwama, S. Miyazaki, and H. Yanagisawa.  Improved approximation of the stable marriage problem.  In _Algorithms-ESA 2003: 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings 11_ , pages 266–277. Springer, 2003.
  * Huang and Kavitha (2013) C.-C. Huang and T. Kavitha.  Popular matchings in the stable marriage problem.  _Information and Computation_ , 222:180–194, 2013.
  * Irving (1994) R. W. Irving.  Stable marriage and indifference.  _Discrete Applied Mathematics_ , 48(3):261–272, 1994.
  * Iwama et al. (1999) K. Iwama, D. Manlove, S. Miyazaki, and Y. Morita.  Stable marriage with incomplete lists and ties.  In _Proc. 26th International Colloquium on Automata, Languages, and Programming (ICALP 1999)_ , pages 443–452. Springer, 1999.
  * Kamiyama (2020) N. Kamiyama.  Popular matchings with two-sided preference lists and matroid constraints.  _Theoretical Computer Science_ , 809:265–276, 2020.
  * Kavitha (2014) T. Kavitha.  A size-popularity tradeoff in the stable marriage problem.  _SIAM Journal on Computing_ , 43(1):52–71, 2014.
  * Király (2012) Z. Király.  Linear time local approximation algorithm for maximum stable marriage.  In _Proc. Second International Workshop on Matching Under Preferences (MATCH-UP 2012)_ , page 99, 2012.
  * Manlove (2013) D. Manlove.  _Algorithmics of matching under preferences_ , volume 2.  World Scientific, 2013.
  * Manlove et al. (2002) D. F. Manlove, R. W. Irving, K. Iwama, S. Miyazaki, and Y. Morita.  Hard variants of stable marriage.  _Theoretical Computer Science_ , 276(1-2):261–279, 2002.
  * McDermid (2009) E. McDermid.  A 3/2-approximation algorithm for general stable marriage.  In _Proc. 36th International Colloquium on Automata, Languages, and Programming (ICALP 2009)_ , pages 689–700. Springer, 2009.
  * Yanagisawa (2007) H. Yanagisawa.  Approximation algorithms for stable marriage problems.  _PhD thesis, Kyoto University, Graduate School of Informatics_ , 2007.
  * Yokoi (2021) Y. Yokoi.  An approximation algorithm for maximum stable matching with ties and constraints.  _arXiv preprint arXiv:2107.03076_ , 2021.