11institutetext: Tata Institute of Fundamental Research, Mumbai, India;
11email<EMAIL_ADDRESS>22institutetext: Eötvös Loránd University,
Budapest, Hungary; 22email<EMAIL_ADDRESS>33institutetext: Research
Center for Operations Management, KU Leuven, Leuven, Belgium; 33email:
<EMAIL_ADDRESS>44institutetext: Centre for Economic and Regional
Studies, Budapest, Hungary; 44email<EMAIL_ADDRESS>55institutetext: Budapest University of Technology and Economics, Budapest,
Hungary; 66institutetext: Simons Laufer Mathematical Sciences Institute
(SLMath), Berkeley, California, United States; 66email<EMAIL_ADDRESS>
# The popular assignment problem:
when cardinality is more important than popularity

Telikepalli Kavitha 11 Tamás Király 22 Jannik Matuschke 33
Ildikó Schlotter 4455 Ulrike Schmidt-Kraepelin 66

###### Abstract

We consider a matching problem in a bipartite graph $G=(A\cup B,E)$ where
nodes in $A$ are agents having preferences in partial order over their
neighbors, while nodes in $B$ are objects without preferences. We propose a
polynomial-time combinatorial algorithm based on LP duality that finds a
maximum matching or _assignment_ in $G$ that is popular among all maximum
matchings, if there exists one. Our algorithm can also be used to achieve a
trade-off between popularity and cardinality by imposing a penalty on
unmatched nodes in $A$.

We also provide an $O^{*}(|E|^{k})$ algorithm that finds an assignment whose
unpopularity margin is at most $k$; this algorithm is essentially optimal,
since the problem is $\mathsf{NP}$-complete and $\mathsf{W}_{l}[1]$-hard with
parameter $k$. We also prove that finding a popular assignment of minimum cost
when each edge has an associated binary cost is $\mathsf{NP}$-hard, even if
agents have strict preferences. By contrast, we propose a polynomial-time
algorithm for the variant of the popular assignment problem with
forced/forbidden edges. Finally, we present an application in the context of
housing markets.

##  1 Introduction

We consider a matching problem in a bipartite graph $G=(A\cup B,E)$ with one-
sided preferences. Nodes in $A$, also called agents, have preferences in
partial order over their neighbors, while nodes in $B$, also called objects,
have no preferences. The preference order $\succ_{a}$ of an agent $a\in A$
over its neighboring objects in $G$ is a _partial order_ if $\succ_{a}$ is
irreflexive and transitive. The model of one-sided preferences is often called
the house allocation problem as it arises in campus housing allocation in
universities [1]. The fact that preferences are one-sided here makes this
model very different from the marriage problem introduced by Gale and Shapley
[14] in 1962, where all nodes have preferences over their neighbors.

Usually one seeks a matching in $G$ that is optimal in some sense. Popularity
is a well-studied notion of optimality in the model of one-sided preferences.
Any pair of matchings, say $M$ and $N$, can be compared by holding an election
between them where agents are voters. Every agent prefers the matching where
she gets assigned a more preferred partner, and being unmatched is her worst
choice. Let $\phi(M,N)$ be the number of agents who prefer $M$ to $N$. Then we
say that $M$ is _more popular than_ $N$ if $\phi(M,N)>\phi(N,M)$. Let us write
$\Delta(M,N)=\phi(M,N)-\phi(N,M)$.

###### Definition 1

A matching $M$ is popular if there is no matching more popular than $M$, i.e.,
$\Delta(M,N)\geq 0$ for all matchings $N$ in $G$.

The popular matching problem involves deciding if $G$ admits a popular
matching, and finding one if so. This is a well-studied problem from 2005, and
there is an efficient algorithm to solve it in the case when each agent’s
preference order is a _weak ranking_ [2], i.e., when the indifference111We say
that agent $a\in A$ is _indifferent_ between objects $b$ and $b^{\prime}$ if
$b\not\succ_{a}b^{\prime}$ and $b^{\prime}\not\succ_{a}b$. relation is
transitive. Our goal in this paper is to solve the following natural
generalization of the popular matching problem when agents have partial order
preferences (these generalize weak rankings).

##### The popular assignment problem.

Consider applications where the size of the matching is of primary importance.
It is natural that as many students as possible be assigned campus housing.
Another application is in assigning final year medical and nursing students to
hospitals during emergencies (such as a pandemic) to overcome staff shortage
[11]. Preferences of these students are important but the size of the matching
is more important, since we want to augment human resources as much as
possible. Thus what we seek is not a popular matching but a popular maximum
matching, i.e., among maximum matchings, a best one. Our approach to
prioritize the cardinality of the matching is in stark contrast with most
existing results in the area of popular matchings, where the foremost
requirement is usually popularity.

By augmenting $G$ with dummy agents and artificial objects (see Section 3), we
can assume that $G$ admits a perfect matching, i.e., an _assignment_. So our
problem becomes the popular perfect matching problem—we will call this the
popular assignment problem in $G$. In other words, we seek an assignment of
objects to agents such that every agent is assigned an object and, roughly
speaking, there is no assignment that makes more agents happier than it makes
unhappier.

###### Definition 2

A perfect matching $M$ is a popular assignment if there is no perfect matching
in $G$ that is more popular than $M$, i.e., $\Delta(M,N)\geq 0$ for all
perfect matchings $N$ in $G$.

Thus, a popular assignment is a weak Condorcet winner [7, 25] where all
perfect matchings are candidates and agents are voters. Weak Condorcet winners
need not exist in a general voting instance; in our setting as well, a popular
assignment need not exist in $G$. Consider the following simple example where
$A=\\{a_{1},a_{2},a_{3}\\}$ and $B=\\{b_{1},b_{2},b_{3}\\}$, and $G$ is the
complete bipartite graph $K_{3,3}$, i.e., every agent and object are adjacent.
Suppose that every agent has the same (strict) preference ordering:
$b_{1}\succ b_{2}\succ b_{3}$, i.e., $b_{i}$ is the $i$-th choice for
$i=1,2,3$. For any assignment here, there exists a more popular assignment,
e.g., $\\{(a_{1},b_{3}),(a_{2},b_{1}),(a_{3},b_{2})\\}$ is more popular than
$\\{(a_{1},b_{1}),(a_{2},b_{2}),(a_{3},b_{3})\\}$. Therefore, this instance
has no popular assignment.

#####  The popular assignment problem.

Given a bipartite graph $G=(A\cup B,E)$ where every $a\in A$ has preferences
in partial order over her neighbors, does $G$ admit a popular assignment? If
so, find one.

It is easy to show instances that admit popular assignments but do not have
any popular matching (see Section 2.2). Interestingly, an algorithm for the
popular assignment problem also solves the popular matching problem. By
augmenting the given instance with artificial worst-choice objects and some
dummy agents, we can construct an instance $G^{\prime}$ on at most twice as
many nodes as in $G$ such that $G$ admits a popular matching if and only if
$G^{\prime}$ admits a popular assignment (this simple reduction is given in
Section 2.3). Thus, the popular assignment problem generalizes the popular
matching problem. Furthermore, we introduce a family of problems that
interpolates between these two problems by introducing a penalty
(parameterized by $t$) for unmatched agents. In particular, the popular
matching problem with penalty $t=1$ equals the popular matching problem, while
the same problem with $t=n$ corresponds to the popular assignment problem. In
fact, we can reduce all of these problems to the popular assignment problem
(see Section 4.2).

By adjusting the usage of worst-choice objects appropriately, an algorithm for
popular assignment can solve the following more general variant of both the
popular matching problem and the popular assignment problem, and thus opens
possibilities to a wide spectrum of applications.

##### Popularity with diversity.

Consider instances $G=(A\cup B,E)$ where every agent has one of $k$ colors
associated with it, and we are interested in only those (not necessarily
perfect) matchings that match for every $i\in\\{1,\ldots,k\\}$, $c_{i}$ agents
of color $i$, where $s_{i}\leq c_{i}\leq t_{i}$ for some given bounds $s_{i}$
and $t_{i}$, i.e., only those matchings that satisfy these lower and upper
bounds for every color are admissible. We seek a matching that is popular
within the set of admissible matchings (see Section 2.3 for a reduction to
popular assignment).

Public housing programs constitute an application where such problems arise.
For example, in Singapore, $70\%$ of the residential real estate is managed by
a public housing program which promotes ethnic diversity by imposing quotas on
each housing block and ethnic group. Motivated by this market, Benabbou et al.
[3] study a similar model with cardinal utilities.

###  1.1 Our contribution

Our first result is that the popular assignment problem (with general partial
order preferences) can be solved in polynomial time. Let $|A|=|B|=n$ and
$|E|=m$.

###### Theorem 1.1

The popular assignment problem in $G=(A\cup B,E)$ can be solved in $O(m\cdot
n^{5/2})$ time.

Note that Theorem 1.1 implies that the popular matching problem with general
partial order preferences can be solved in polynomial time, using the
reduction described in Section 2.3. Curiously, the popular matching algorithm
in [2] does not generalize to partial order preferences; we include an example
that illustrates this in Section 2.1. To the best of our knowledge, no
polynomial-time algorithm for solving the popular matching problem with
partial order preferences has been known prior to Theorem 1.1.

Partial order preferences arise naturally, e.g., when agents have cardinal
utilities for the objects that then induce _semiorder_ preferences. This means
that for any agent, a pair of objects with widely differing utilities get
compared by their utilities, while a pair of objects with utilities that are
within a small threshold are deemed equivalent, thus the agent is indifferent
between two such objects.222Yu Yokoi posed the popular matching problem with
semiorder preferences as an open problem in a talk on “Approximation
Algorithms for Matroidal and Cardinal Generalizations of Stable Matching” at
RIMS, Kyoto in May 2023 (she was not aware that the conference version of our
paper [20] solves the popular matching problem with partial order
preferences). Observe that the indifference relation here need not be
transitive.

When a popular assignment does not exist in $G$, a natural extension is to ask
for an almost popular assignment, i.e., an assignment with low unpopularity.
How do we measure the unpopularity of an assignment? A well-known measure is
the unpopularity margin [23] defined for any assignment $M$ as
$\mu(M)=\max_{N}(\phi(N,M)-\phi(M,N))=\max_{N}\Delta(N,M)$, where the maximum
is taken over all assignments, that is, all perfect matchings $N$ in $G$. Thus
$\mu(M)$ is the maximum margin by which another assignment defeats $M$.

An assignment $M$ is popular if and only if $\mu(M)=0$. Let the
$k$-unpopularity margin problem be the problem of deciding if $G$ admits an
assignment with unpopularity margin at most $k$. We generalize Theorem 1.1 to
show the following result.

###### Theorem 1.2

For any $k\in\mathbb{Z}_{\geq 0}$, the $k$-unpopularity margin problem in
$G=(A\cup B,E)$ can be solved in $O(m^{k+1}\cdot n^{5/2})$ time.

So when $k=\Theta(1)$, this is a polynomial-time algorithm to find a
$k$-unpopularity margin assignment if $G$ admits one. Via the reduction
described in Section 2.3, which preserves the unpopularity margin of any
matching, Theorem 1.2 extends to the $k$-unpopularity margin version of the
popular matching problem, i.e., to decide if $G$ admits a matching with
unpopularity margin at most $k$. Though the measure of unpopularity margin was
introduced in 2008, no polynomial-time algorithm was known so far to solve the
$k$-unpopularity margin matching problem for any $k\geq 1$.

Rather than the exponential dependency on the parameter $k$ in Theorem 1.2,
can we solve the $k$-unpopularity margin problem in polynomial time? Or at
least can we achieve a running time of the form $f(k)\mathsf{poly}(m,n)$ for
some function $f$ so that the degree of the polynomial is independent of $k$?
That is, can we get a _fixed-parameter tractable_ algorithm with parameter
$k$? The following hardness result shows that the algorithm of Theorem 1.2 is
essentially optimal for the $k$-unpopularity margin problem. See Section 6.2
for the definition of $\mathsf{W}_{l}[1]$-hardness.

###### Theorem 1.3

The $k$-unpopularity margin problem is $\mathsf{W}_{l}[1]$-hard with parameter
$k$ when agents’ preferences are weak rankings, and it is
$\mathsf{NP}$-complete even if preferences are strict rankings.

##### Popularity with penalty for unmatched agents.

We also consider a model that allows for a trade-off between popularity and
cardinality by imposing a _penalty_ for unmatched agents. A matching $M$ in
$G=(A\cup B,E)$ is _popular with penalty $t$_ if it does not lose a pairwise
election against any matching $N$ in $G$, where votes of agents that are
matched in $M$ but unmatched in $N$ (or vice versa) are counted with weight
$t$; see Section 4.2 for a formal definition. If $M$ is a matching that is
popular with penalty $t$, then $|M|\geq\frac{t}{t+1}|M_{\max}|$ where
$M_{\max}$ is a maximum matching in $G$.

We prove that a matching that is popular with penalty $t$, if it exists, can
be found via an appropriately constructed instance of the popular assignment
problem (without penalty). Moreover, we show that a truncated variant of our
algorithm for the popular assignment problem can find an assignment that is
popular with penalty $t$ (when compared against any matching), if such an
assignment exists.

##### Minimum-cost popular assignment.

We next consider the minimum-cost popular assignment problem: suppose that, in
addition to our instance $G=(A\cup B,E)$ of the popular assignment problem
where every agent has preferences in partial order over her adjacent objects,
there is a cost function $c:E\rightarrow\mathbb{R}$ on the edges and a budget
$\beta\in\mathbb{R}$, and we want to decide whether $G$ admits a popular
assignment whose sum of edge costs is at most $\beta$. Computing a minimum-
cost popular assignment efficiently would also imply an efficient algorithm
for finding a popular assignment with _forced/forbidden_ edges. We show the
following hardness result.

###### Theorem 1.4

The minimum-cost popular assignment problem is $\mathsf{NP}$-complete, even if
each edge cost is in $\\{0,1\\}$ and agents have strict preferences.

This result reveals a surprising difference between the popular assignment
problem and the popular matching problem; for the latter problem, arbitrary
linear cost functions can be minimized efficiently when preferences are weak
rankings [2]. The $\mathsf{NP}$-hardness for the minimum-cost popular
assignment problem implies that given a set of desired edges, it is
$\mathsf{NP}$-hard (even for strict preferences) to find a popular assignment
that contains the maximum number of desired edges. Interestingly, in spite of
the above hardness result, we show the following positive result that the
popular assignment problem with partial order preferences and forced/forbidden
edges is tractable. Note that the assignment $M$ must be popular among _all_
assignments, not only those adhering to the forced and forbidden edge
constraints. Thus, although the desired edges variant is hard, the forced
edges variant is easy.

###### Theorem 1.5

Given a set $F^{+}\subseteq E$ of forced edges and another set $F^{-}\subseteq
E$ of forbidden edges, we can determine in polynomial time if there exists a
popular assignment $M$ in $G=(A\cup B,E)$ such that $F^{+}\subseteq M$ and
$F^{-}\cap M=\emptyset$.

Thus the popular assignment problem is reminiscent of the well-known stable
roommates problem333This problem asks for a stable matching in a general graph
(which need not be bipartite) with strict preferences.; in a roommates
instance, finding a stable matching can be solved in polynomial time [16] even
with forced/forbidden edges [13], however finding a minimum-cost stable
matching is $\mathsf{NP}$-hard [12].

##### Application to housing markets.

Finally, in Corollary 2 we present an application of the algorithm of Theorem
1.1 that allows us to find popular allocations in so-called _housing markets_
, a model defined by Shapley and Scarf [28]; see Section 7 for all definitions
concerning housing markets. We contrast this with Theorem 7.1, a strengthening
of Theorem 1.4, showing that it is $\mathsf{NP}$-hard to find a popular
allocation that maximizes the number of trading agents in the housing market.

##### Conference version.

A preliminary version of this paper appeared in the proceedings of SODA 2022
[20]. This version of the paper goes beyond the conference version in the
following two points: (i) Section 4.1, Section 4.2, and Section 7 are new and
(ii) Theorem 1.4 is proved in its full generality; in fact, we prove a
stronger version of Theorem 1.4, namely Theorem 7.1. The conference version
[20] contained the proof of a weaker result which stated that the minimum-cost
popular assignment problem is $\mathsf{NP}$-complete when edge costs are in
$\\{0,1,+\infty\\}$.

###  1.2 Background

The notion of popularity in a marriage instance (where preferences are two-
sided and strict) was introduced by Gärdenfors [15] in 1975. Popular matchings
always exist in such an instance, since any stable matching is popular [15].
When preferences are one-sided, popular matchings need not exist. For the case
when preferences are weak rankings, a simple and clean combinatorial
characterization of popular matchings (see Section 2.1) was given in [2],
leading to an $O(m\sqrt{n})$ time algorithm [2] for the popular matching
problem. By contrast, a combinatorial characterization of popular assignments
(even for strict rankings) remains elusive. Finding a minimum unpopularity
margin matching was proved to be $\mathsf{NP}$-hard [23].

In the last fifteen years, popularity has been a widely studied concept.
Researchers have considered extensions of the popular matching problem where
one aims for a popular matching satisfying some additional optimality criteria
such as rank-maximality or fairness [22, 24], or where the notion of
popularity is adjusted to incorporate capacitated objects or weighted agents
[26, 29]. Another variant of the popular matching problem was considered in
[9] where nodes in $A$ have strict preferences and nodes in $B$, i.e.,
objects, have no preferences, however each object cares to be matched to any
of its neighbors. We refer to [8] for a survey on results in this area.

Among the literature on popular matchings, only a few studies have considered
a setting that focuses on popularity within a restricted set of admissible
solutions. The paper that comes closest to our work is [17] which considered
the popular maximum matching problem in a marriage instance (where preferences
are two-sided and strict). It was shown there that a popular maximum matching
always exists in a marriage instance and one such matching can be computed in
$O(mn)$ time; the following size-popularity trade-off in a marriage instance
was also shown in [17]: for any integer $t\geq 2$, there exists a matching
$M_{t}$ with $|M_{t}|\geq\frac{t}{t+1}|M_{\max}|$ and unpopularity factor at
most $t-1$.444The unpopularity factor of a matching $M$ is
$\max_{N}\phi(N,M)/\phi(M,N)$, where the maximum is taken over all matchings
$N\neq M$ in $G$ [23]. Very recently, it was shown in [19] that a minimum-cost
popular maximum matching in a marriage instance can be computed in polynomial
time. These results use the rich machinery of stable matchings in a marriage
instance [14, 27]. In contrast to these positive results for popular maximum
matchings, computing an almost-stable maximum matching (one with the least
number of blocking edges) in a marriage instance is $\mathsf{NP}$-hard [4].

###  1.3 Techniques

Our popular assignment algorithm is based on LP duality. We show that a
matching $M$ is a popular assignment if and only if it has a _dual
certificate_ $\vec{\alpha}\in\\{0,\pm 1,\ldots,\pm(n-1)\\}^{2n}$ fulfilling
certain constraints induced by the matching $M$. Our algorithm (see Section 4)
can be viewed as a search for such a dual certificate. It associates a level
$\ell(b)$ with every $b\in B$. This level function $\ell$ guides us in
constructing a subgraph $G_{\ell}$ of $G$. If $G_{\ell}$ contains a perfect
matching, then this matching is a popular assignment in $G$ and the levels
determine a corresponding dual certificate. If $G_{\ell}$ has no perfect
matching, then we increase some $\ell$-values and update $G_{\ell}$
accordingly, until eventually $G_{\ell}$ contains a perfect matching or the
level of an object increases beyond the permitted range, in which case we
prove that no popular assignment exists.

The LP method for popular matchings was introduced in [21] and dual
certificates for popular (maximum) matchings in marriage instances were shown
in [18, 19]. However, dual certificates for popular matchings in instances
with one-sided preferences have not been investigated so far. The existence of
simple dual certificates for popular assignments is easy to show (see Section
3), but this does not automatically imply polynomial-time solvability. The
main novelty of our paper lies in showing a combinatorial algorithm to search
for dual certificates in an instance $G$ and in using this approach to solve
the popular assignment problem, as well as several related problems, in
polynomial time.

##### Our other results.

Our algorithm for the variant of the popular assignment problem with forced/
forbidden edges (see Section 5) is a natural extension of the above algorithm
where certain edges are excluded. The $k$-unpopularity margin algorithm (see
Section 6) associates a load with every edge such that the total load is at
most $k$ and the overloaded edges are treated as forced edges. Our
$W_{l}[1]$-hardness result shows that this $O^{*}(m^{k})$ algorithm for the
$k$-unpopularity margin problem is essentially optimal, i.e., it is highly
unlikely that this problem admits an $f(k)m^{o(k)}$ algorithm for any
computable function $f$.

##  2 Preliminaries

For any $v\in A\cup B$, let $\mathsf{Nbr}_{G}(v)$ denote the set of neighbors
of $v$ in $G$, and $\delta(v)$ the set of edges incident to $v$. For any
$X\subseteq A\cup B$, we let $\mathsf{Nbr}_{G}(X)=\cup_{v\in
X}\mathsf{Nbr}_{G}(v)$; we may omit the subscript $G$ if it is clear from the
context. For any set $X$ of vertices (or edges) in $G$, let $G-X$ be the
subgraph of $G$ obtained by deleting the vertices (or edges, respectively) of
$X$ from $G$. For an edge set $F\subseteq E$, we denote by $G[F]$ the subgraph
of $G$ restricted to edges of $F$, that is, $G[F]=(A\cup B,F)$. For a matching
$M$ in $G$ and a node $v$ matched in $M$, we denote the partner of $v$ by
$M(v)$.

The preferences of node $a\in A$ over its neighbors are given by a strict
partial order $\succ_{a}$, so $b\succ_{a}b^{\prime}$ means that $a$ prefers
$b$ to $b^{\prime}$. We use $b\sim_{a}b^{\prime}$ to denote that $a$ is
indifferent between $b$ and $b^{\prime}$, i.e., neither $b\succ_{a}b^{\prime}$
nor $b^{\prime}\succ_{a}b$ holds. As mentioned earlier, the relation
$\succ_{a}$ is a _weak ranking_ if $\sim_{a}$ is transitive. In this case,
$\sim_{a}$ is an equivalence relation and there is a strict order on the
equivalence classes. When each equivalence class has size 1, we call it a
_strict ranking_ or a _strict preference_.

We will also use the notation $[k]=\\{1,2,\dots,k\\}$ for any positive integer
$k$.

###  2.1 A characterization of popular matchings from [2] for weak rankings

In order to characterize popular matchings in the case when agents’
preferences are weak rankings, as done in [2], it will be convenient to add
artificial worst-choice or last resort objects to the given instance $G=(A\cup
B,E)$. So $B=B\cup\\{l(a):a\in A\\}$, i.e., corresponding to each $a\in A$, a
node $l(a)$ gets added to $B$ and we set this node $l(a)$ as the worst-choice
object for $a$. Thus we have $E=E\cup\\{(a,l(a)):a\in A\\}$.

We say that an edge $(a,b)$ _dominates_ an edge $(a,b^{\prime})$, if
$b\succ_{a}b^{\prime}$. We let $E_{1}$ denote the set of edges that are not
dominated by any edge in $E$, we will call these _first-choice edges_. We call
an edge $e\in E$ critical if the maximum matching in $G[E_{1}\cup\\{e\\}]$ is
larger than a maximum matching in $G[E_{1}]$. We define the set $E_{2}$ of
_second-choice edges_ as those edges that are critical, and are not dominated
by any critical edge.

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

A matching $M$ in $G=(A\cup B,E)$ is popular if and only if

  * (1)

$M$ is a matching in $G[E_{1}\cup E_{2}]$ that matches all agents in $A$, and

  * (2)

$M\cap E_{1}$ is a maximum matching in $G[E_{1}]$.

The above characterization was given in [2] for instances where agents’
preferences are weak rankings, and the following example shows that it does
not hold for general partial orders. Let $G=(A\cup B,E)$ where $A=\\{a,b,c\\}$
and $B=\\{x,y,z\\}$, each agent is adjacent to each object, and the preference
orders of the agents are defined by

$\begin{array}[]{lll}a:&x\succ_{a}z,&y\succ_{a}z;\\\ b:&x\succ_{b}z;\\\
c:&y\succ_{c}x,&y\succ_{c}z.\\\ \end{array}$

Thus $x\sim_{a}y$, similarly, $x\sim_{b}y$ and $y\sim_{b}z$, and also
$x\sim_{c}z$. The set of first-choice edges is then
$E_{1}=\\{(a,x),(a,y),(b,x),(b,y),(c,y)\\}$, the set of second-choice edges is
$E_{2}=\\{(a,z),(b,z),(c,z)\\}$. Consider now the matching
$M=\\{(a,x),(b,y),(c,z)\\}$. It is straightforward to verify that $M$
satisfies properties (1) and (2) required in Theorem 2.1. However, $M$ is not
popular, since the matching $N=\\{(a,x),(b,z),(c,y)\\}$ is more popular than
$M$, because $c$ prefers $N$ to $M$, while $a$ and $b$ are indifferent between
$M$ and $N$.

###  2.2 An instance without popular matchings that admits a popular
assignment

We describe a simple example that does not admit any popular matching, but
admits a popular assignment. Let $G=(A\cup B,E)$ where
$A=\\{a_{1},a_{2},a_{3}\\}$ and $B=\\{b_{1},b_{2},b_{3}\\}$ and the preference
order of both $a_{1}$ and $a_{2}$ is $b_{1}\succ b_{2}$ while the preference
order of $a_{3}$ is $b_{1}\succ b_{2}\succ b_{3}$.

It follows from the characterization of popular matchings from [2] that a
popular matching $M$ has to match each of $a_{1},a_{2},a_{3}$ to either
$b_{1}$ or $b_{2}$. Since this is not possible, this instance has no popular
matching. It is easy to check that
$M^{*}=\\{(a_{1},b_{1}),(a_{2},b_{2}),(a_{3},b_{3})\\}$ is a popular
assignment in $G$.

###  2.3 Some simple reductions to the popular assignment problem

We will first show a reduction from the popular matching problem to the
popular assignment problem. Let $G=(A\cup B,E)$ be an instance of the popular
matching problem. Let $B^{\prime}=B\cup\\{l(a):a\in A\\}$. That is,
corresponding to each $a\in A$, an object $l(a)$ (the last resort of $a$) is
in $B^{\prime}$ and we set this object $l(a)$ as the worst-choice of $a$. Let
$A^{\prime}=A\cup\\{d_{1},\ldots,d_{|B|}\\}$, i.e., there are $|B|$ many dummy
agents in $A^{\prime}$. Each dummy agent $d_{i}$ is adjacent to all objects in
$B^{\prime}$ and is indifferent between any two of them.

It is easy to see that every matching $M$ in $G$ can be extended to a perfect
matching $M^{\prime}$ in this new graph $G^{\prime}=(A^{\prime}\cup
B^{\prime},E^{\prime})$ and conversely, every perfect matching $M^{\prime}$ in
$G^{\prime}$ projects to a matching $M$ in $G$. For any pair of matchings $M$
and $N$ in $G$, observe that $\Delta(M,N)=\Delta(M^{\prime},N^{\prime})$. Thus
$M$ and $M^{\prime}$ have the same unpopularity margin and, in particular, an
algorithm that finds a popular assignment in $G^{\prime}$ solves the popular
matching problem in $G$.

##### Popularity with diversity.

Recall this problem defined in Section 1 where every agent in an instance
$G=(A\cup B,E)$ has one of $k$ colors associated with it, and admissible
matchings are those that for every $i\in\\{1,\ldots,k\\}$ match $c_{i}$ agents
of color $i$ so that $s_{i}\leq c_{i}\leq t_{i}$ for some given bounds $s_{i}$
and $t_{i}$. We seek a matching that is popular within the set of admissible
matchings.

We augment $B$ by adding $n_{i}-s_{i}$ artificial objects for each $i$, where
$n_{i}$ is the number of agents colored $i$. For each $i$, these $n_{i}-s_{i}$
objects are tied as the worst-choices of all agents colored $i$. Let
$A^{\prime}=A\cup\\{d_{1},\ldots,d_{n^{\prime}}\\}$, where
$n^{\prime}=|B|-\sum_{i}s_{i}$. Every dummy agent
$d\in\\{d_{1},\dots,d_{n^{\prime}}\\}$ is adjacent to all objects in $B$ and
for each color $i$ some fixed $t_{i}-s_{i}$ artificial objects meant for color
class $i$ introduced above—as before, $d$ is indifferent between any two of
its neighbors. So for each $i$, there are $n_{i}-t_{i}$ artificial objects not
adjacent to any dummy agent. Let $G^{\prime}$ be the new instance. It is easy
to see that an algorithm that finds a popular assignment in $G^{\prime}$
solves our problem in $G$.

##  3 Dual certificates for popular assignments

Let $G=(A\cup B,E)$ be an input instance and let $\nu$ be the size of a
maximum matching in $G$. Let us augment $G$ with $|B|-\nu$ dummy agents that
are adjacent to all objects in $B$ (and indifferent among them), along with
$|A|-\nu$ artificial objects that are tied as the worst-choice neighbors of
all non-dummy agents. Any maximum matching $M$ in the original graph extends
to a perfect matching (i.e., assignment) $M^{\prime}$ in the augmented graph;
moreover, $\Delta(M,N)=\Delta(M^{\prime},N^{\prime})$ for any pair of maximum
matchings $M$ and $N$ in $G$. Thus, we can assume without loss of generality
that the input instance $G$ admits a perfect matching.

Let $|A|=|B|=n$ and $|E|=m$. Let $M$ be any perfect matching in $G$. The
following edge weight function $\mathsf{wt}_{M}$ in $G$ will be useful. For
any $(a,b)\in E$

$\mathrm{let}\ \mathsf{wt}_{M}(a,b)=\begin{cases}\phantom{-}1&\text{if\ $a$\
prefers\ $b$\ to\ $M(a)$;}\\\ -1&\text{if\ $a$\ prefers\ $M(a)$\ to\ $b$;}\\\
\phantom{-}0&\text{otherwise,\ i.e., if\ $b\sim_{a}M(a)$.}\end{cases}$

Let $\mathsf{wt}_{M}(N)=\sum_{e\in N}\mathsf{wt}_{M}(e)$ for any edge set
$N\subseteq E$. Consider the following linear program LP1 and its dual LP2.

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

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

LP1 is well known to be integral, and hence its optimal value is
$\max_{N}\mathsf{wt}_{M}(N)$ where $N$ is a perfect matching in $G$. The
definition of $\mathsf{wt}_{M}$ implies that $\mathsf{wt}_{M}(N)=\Delta(N,M)$;
recall the definition $\Delta(N,M)=\phi(N,M)-\phi(M,N)$. So $M$ is a popular
assignment if and only if the optimal value of LP1 is at most 0. In fact, the
optimal value of LP1 is then exactly 0, by $\Delta(M,M)=0$. Hence for a
popular assignment $M$, the edge incidence vector of $M$ is an optimal
solution to LP1.

Theorem 3.1 gives a useful characterization of popular assignments. The proof
of Theorem 3.1 is given in Section 6 along with the proof of a related result
(Theorem 6.1).

###### Theorem 3.1

$M$ is a popular assignment if and only if there exists an optimal solution
$\vec{\alpha}$ to LP2 such that $\alpha_{a}\in\\{0,1,2,\ldots,(n-1)\\}$ for
all $a\in A$, $\alpha_{b}\in\\{0,-1,-2,\ldots,-(n-1)\\}$ for all $b\in B$, and
$\sum_{u\in A\cup B}\alpha_{u}=0$.

A dual certificate for a popular assignment $M$ is an optimal solution
$\vec{\alpha}$ to LP2 satisfying the conditions given in Theorem 3.1.

##  4 The popular assignment algorithm

The goal of our algorithm is to construct a perfect matching $M$ in $G$ along
with a dual certificate $\vec{\alpha}$. Every $b\in B$ will have an associated
level $\ell(b)$ in this algorithm and the $\alpha$-value of $b$ will be
$-\ell(b)$, i.e., we set $\alpha_{b}=-\ell(b)$.

Given a function $\ell:B\rightarrow\mathbb{N}$ called a level function, for
any $a\in A$ let $\ell^{*}(a)=\max_{b\in\mathsf{Nbr}(a)}\ell(b)$ be the
highest level at which agent $a$ has neighbors. Now we define the subgraph
$G_{\ell}=(A\cup B,E_{\ell})$ _induced by levels $\ell(\cdot)$_ by putting an
edge $(a,b)\in E$ into $E_{\ell}$ if and only if

  * (i)

$b$ has level $\ell^{*}(a)$, and $a$ has no neighbor in level $\ell^{*}(a)$
that she prefers to $b$, or

  * (ii)

$b$ has level $\ell^{*}(a)-1$, and $a$ prefers $b$ to each of her neighbors in
level $\ell^{*}(a)$, and moreover, $a$ prefers none of her neighbors in level
$\ell^{*}(a)-1$ to $b$.

Thus in the subgraph $G_{\ell}$, every agent has edges to her favorite
highest-level neighbors and to her favorite neighbors one level below,
provided these neighbors are preferred to all of her highest-level neighbors
(see Fig. 2 for an illustration). The following lemma will be very useful.

###### Lemma 1

A matching $M$ in $G$ is a popular assignment if and only if there exists a
level function $\ell$ such that $M$ is a perfect matching in $G_{\ell}$.
Furthermore, this happens if and only if there is a level function $\ell$ and
a dual certificate $\vec{\alpha}$ for $M$ where $\ell(b)=|\alpha_{b}|$ for all
$b\in B$ and $M$ is a perfect matching in $G_{\ell}$.

###### Proof

Let us first show that if there exists a level function $\ell$ such that $M$
is a perfect matching in $G_{\ell}$, then $M$ is a popular assignment in $G$.
We construct a dual certificate for $M$ as follows. Let $\alpha_{b}=-\ell(b)$
for all $b\in B$ and $\alpha_{a}=\ell(M(a))$ for all $a\in A$. Note that the
value of $\vec{\alpha}$ as a solution for LP2 is $\sum_{v\in A\cup
B}\alpha_{v}=\sum_{a\in A}(\alpha_{a}+\alpha_{M(a)})=0=\sum_{e\in
M}\mathsf{wt}_{M}(e)$. Thus $\vec{\alpha}$ is optimal for LP2 if it is
feasible. It remains to show that
$\alpha_{a}+\alpha_{b}\geq\mathsf{wt}_{M}(a,b)$ for every $(a,b)\in E$.

So let $(a,b)\in E$ and let $b^{\prime}:=M(a)$. Note that
$\alpha_{a}+\alpha_{b}=\ell(b^{\prime})-\ell(b)$. We show that
$\ell(b^{\prime})-\ell(b)\geq\mathsf{wt}_{M}(a,b)$. Because $(a,b^{\prime})\in
E_{\ell}$, one of the following cases holds:

  * •

Case (i): $\ell(b^{\prime})=\ell^{*}(a)$, so $a$ prefers no neighbor of hers
in level $\ell^{*}(a)$ to $b^{\prime}$. We have two subcases:

    * –

If $\ell(b)=\ell^{*}(a)$, then $a$ does not prefer $b$ to $b^{\prime}$ and
hence $\mathsf{wt}_{M}(a,b)\leq 0=\ell(b^{\prime})-\ell(b)$.

    * –

If $\ell(b)<\ell^{*}(a)$, then $\ell(b^{\prime})-\ell(b)\geq
1\geq\mathsf{wt}_{M}(a,b)$.

  * •

Case (ii): $\ell(b^{\prime})=\ell^{*}(a)-1$, so $a$ prefers $b^{\prime}$ to
each of her neighbors in level $\ell^{*}(a)$, and $a$ prefers none of her
neighbors in level $\ell^{*}(a)-1$ to $b^{\prime}$. We have three subcases:

    * –

If $\ell(b)=\ell^{*}(a)$, then $a$ prefers $b^{\prime}$ to $b$ and hence
$\mathsf{wt}_{M}(a,b)=-1=\ell(b^{\prime})-\ell(b)$.

    * –

If $\ell(b)=\ell^{*}(a)-1$, then $a$ does not prefer $b$ to $b^{\prime}$ and
hence $\mathsf{wt}_{M}(a,b)\leq 0=\ell(b^{\prime})-\ell(b)$.

    * –

If $\ell(b)<\ell^{*}(a)-1$, then $\ell(b^{\prime})-\ell(b)\geq
1\geq\mathsf{wt}_{M}(a,b)$.

Thus in each of these cases
$\mathsf{wt}_{M}(a,b)\leq\ell(b^{\prime})-\ell(b)=\alpha_{a}+\alpha_{b}$.
Hence $\vec{\alpha}$ is a dual certificate for $M$, and thus $M$ is a popular
assignment by Theorem 3.1.

$a_{1}$$a_{2}$$2$$1$$0$$0$$2$$3$$1$$2$$1$$1$ Figure 1: Illustration of the
subgraph $G_{\ell}$ of $G$ for an instance with weak rankings and a level
function $\ell$. Circles indicate agents and squares objects; the $\ell$-level
of each object is written inside the square depicting it. Numbers on the edges
indicate the agents’ weak rankings. Bold edges are included in $G_{\ell}$ and
dashed edges are not. All but two agents were omitted.

$a_{0}$$a_{t-1}$$a_{t}$$b_{0}$$b_{t-1}$$b_{t}$$\dots$$\not\in E_{\ell}$$\dots$
Figure 2: An illustration of the $M$-augmenting path $P$ within the proof of
Lemma 2. Solid edges are in $M$ and dashed edges are in $M^{\star}$. The edge
$(a_{t},b_{t})$ is not contained in $E_{\ell}$.

We will now show the converse. Let $M$ be a popular assignment in $G$ and let
$\vec{\alpha}$ be a dual certificate for $M$. We claim that $M$ is a matching
in the graph $G_{\ell_{\vec{\alpha}}}$ induced by levels $\ell_{\vec{\alpha}}$
with $\ell_{\vec{\alpha}}(b)=|\alpha_{b}|$ for all $b\in B$. To prove this, we
use that $\alpha_{a}+\alpha_{b}\geq\mathsf{wt}_{M}(a,b)$ for every $(a,b)\in
E$. First, because the incidence vector of $M$ and $\vec{\alpha}$ are optimal
solutions to LP1 and LP2, respectively, we get $\alpha_{a}+\alpha_{M(a)}=0$
for each $a\in A$ by complementary slackness. This implies
$\alpha_{a}=-\alpha_{M(a)}=\ell_{\vec{\alpha}}(M(a))$. Therefore,
$\ell_{\vec{\alpha}}(M(a))\geq\ell_{\vec{\alpha}}(b)+\mathsf{wt}_{M}(a,b)$ for
all $(a,b)\in E$.

Since $\mathsf{wt}_{M}(e)\geq-1$ for all edges $e$, any agent $a$ has to be
matched in $M$ to either (i) an undominated neighbor in level
$\ell^{*}_{\vec{\alpha}}(a)$ (i.e., $a$ prefers none of her neighbors in this
level to $M(a)$) or (ii) an undominated neighbor in level
$\ell^{*}_{\vec{\alpha}}(a)-1$ which, moreover, has to dominate (i.e., be
preferred by $a$ to) all of $a$’s neighbors in level
$\ell^{*}_{\vec{\alpha}}(a)$. So $M$ is a perfect matching in
$G_{\ell_{\vec{\alpha}}}$. ∎

##### The algorithm.

Consider Algorithm 1 on input $G=(A\cup B,E)$. In search for a dual
certificate, this algorithm will maintain a _level_ $\ell(b)$ for every $b\in
B$. Initially, $\ell(b)=0$ for every $b\in B$.

The algorithm checks whether there exists a popular assignment by computing a
perfect matching in the graph $G_{\ell}$. If no such matching exists, the
levels of unmatched objects are increased, the graph $G_{\ell}$ is updated
accordingly, and the search continues.

Eventually, either a perfect matching in $G_{\ell}$ is found, or the level of
an object exceeds $n-1$. In the latter case we can conclude that no popular
assignment exists, as we will show below.

Algorithm 1 Finding a popular assignment in $G=(A\cup B,E)$

1:for all $b\in B$ do $\ell(b)=0$.

2:while $\ell(b)<n$ for all $b\in B$ do

3: Construct the graph $G_{\ell}$ and compute a maximum matching $M$ in
$G_{\ell}$.

4: if $M$ is a perfect matching then return $M$.

5: for all $b\in B$ unmatched in $M$ do $\ell(b)=\ell(b)+1$.

6:return “$G$ has no popular assignment”.

##### Running time.

Computing a maximum matching in $G_{\ell}$ takes $O(m\sqrt{n})$ time. In every
iteration of the algorithm, the value $\sum_{b\in B}\ell(b)$ increases. So the
number of iterations is at most $n^{2}$. Hence the running time of our
algorithm is $O(m\cdot n^{5/2})$.

###### Theorem 4.1

If our algorithm returns a matching $M$, then $M$ is a popular assignment in
$G$.

Theorem 4.1 follows immediately from Lemma 1. The more difficult part in our
proof of correctness is to show that whenever our algorithm says that $G$ has
no popular assignment, the instance $G$ indeed has no popular assignment. This
is implied by Theorem 4.2.

###### Theorem 4.2

Let $M^{\star}$ be a popular assignment in $G$ and let $\vec{\alpha}$ be a
dual certificate of $M^{\star}$. Then for every $b\in B$, we have
$|\alpha_{b}|\geq\ell(b)$, where $\ell(b)$ is the level of $b$ when our
algorithm terminates.

If our algorithm terminates because $\ell(b)=n$ for some $b\in B$, then
$|\alpha_{b}|\geq n$ for any dual certificate $\vec{\alpha}$ by Theorem 4.2.
However $|\alpha_{b}|\leq n-1$ by definition, a contradiction. So $G$ has no
popular assignment.

The following lemma is crucial for proving Theorem 4.2. It guarantees that
when the algorithm increases $\ell(b)$ for some unmatched object $b\in B$,
then the new level function does not exceed $|\alpha_{b}|$.

###### Lemma 2

Let $M^{\star}$ be a popular assignment, let $\vec{\alpha}$ be a dual
certificate of $M^{\star}$, and let $\ell:B\rightarrow\mathbb{N}$ be such that
$\ell(b)\leq|\alpha_{b}|$ for all $b\in B$. Let $M$ be a maximum matching in
$G_{\ell}$ and let $b_{0}\in B$ be an object that is left unmatched in $M$.
Then $\ell(b_{0})<|\alpha_{b_{0}}|$.

Before we turn to the proof of Lemma 2, we point out that Theorem 4.2 follows
from this lemma by a simple induction.

######  Proof (of Theorem 4.2)

Let $\ell_{i}$ be the level function on the set $B$ at the start of the $i$-th
iteration of our algorithm. We are going to show by induction that for every
$i$ we have $|\alpha_{b}|\geq\ell_{i}(b)$ for all $b\in B$. This is true for
$i=1$, since $\ell_{1}(b)=0$ for all $b\in B$. Now suppose that
$|\alpha_{b}|\geq\ell_{i}(b)$ for all $b\in B$. Let $b_{0}\in B$. If $b_{0}$
is matched in the maximum matching $M$ in $G_{\ell_{i}}$, then we know
$\ell_{i+1}(b_{0})=\ell_{i}(b_{0})\leq|\alpha_{b_{0}}|$. If $b_{0}$ is left
unmatched in $M$, then $\ell_{i+1}(b_{0})=\ell_{i}(b_{0})+1$ and
$\ell_{i}(b_{0})<|\alpha_{b_{0}}|$ by Lemma 2. Thus
$\ell_{i+1}(b_{0})\leq|\alpha_{b_{0}}|$ in either case, completing the
induction. ∎

######  Proof (of Lemma 2)

By Lemma 1, $M^{\star}$ is a perfect matching in $G_{\ell_{\vec{\alpha}}}$
where $\ell_{\vec{\alpha}}(b)=|\alpha_{b}|$ for $b\in B$. Thus, the symmetric
difference $M\oplus M^{\star}$ in $G$ contains an $M$-augmenting path $P$
starting at $b_{0}$. However, as $M$ is of maximum size in $G_{\ell}$, the
path $P$ must contain an edge that is not in $E_{\ell}$.

Let $(b_{0},a_{0},b_{1},a_{1},\dots,b_{t},a_{t})$ be any prefix of $P$ such
that $(a_{t},b_{t})\notin E_{\ell}$ (see Fig. 2). Note that $(a_{0},b_{0})$
and $(a_{t},b_{t})$ are in $M^{\star}$, since $M$ leaves $b_{0}$ unmatched and
$M\subseteq E_{\ell}$. Thus $(a_{h},b_{h})\in M^{\star}\subseteq
E_{\ell_{\vec{\alpha}}}$ for all $h\in\\{0,\dots,t\\}$ and $(a_{h},b_{h+1})\in
M\subseteq E_{\ell}$ for all $h\in\\{0,\dots,t-1\\}$. We will show that
$\ell(b_{h})<\ell_{\vec{\alpha}}(b_{h})$ for all $h\in\\{0,\dots,t\\}$, and
thus in particular, $\ell(b_{0})<\ell_{\vec{\alpha}}(b_{0})=|\alpha_{b_{0}}|$.

We first show that $\ell(b_{t})<\ell_{\vec{\alpha}}(b_{t})$. Assume for
contradiction that $\ell(b_{t})=\ell_{\vec{\alpha}}(b_{t})$. Using the fact
that $(a_{t},b_{t})\notin E_{\ell}$, one of the following cases must hold:

  * $\bullet$

$a_{t}$ has a neighbor in level at least $\ell(b_{t})+2$, or

  * $\bullet$

$a_{t}$ has a neighbor in level $\ell(b_{t})+1$ that is not dominated by
$b_{t}$, or

  * $\bullet$

$a_{t}$ has a neighbor in level $\ell(b_{t})$ that is preferred to $b_{t}$.

As $\ell_{\vec{\alpha}}(b_{t})=\ell(b_{t})$ and
$\ell_{\vec{\alpha}}(b)\geq\ell(b)$ for all $b\in B$, in each case we get
$(a_{t},b_{t})\notin E_{\ell_{\vec{\alpha}}}$, a contradiction.

Now suppose there exists some $h\in\\{0,\dots,t-1\\}$ with
$\ell(b_{h+1})<\ell_{\vec{\alpha}}(b_{h+1})$ but
$\ell(b_{h})=\ell_{\vec{\alpha}}({b_{h}})$. Recall that $(a_{h},b_{h+1})\in
M\subseteq E_{\ell}$, which leaves us with the following possibilities:

  * $\bullet$

$\ell(b_{h+1})\geq\ell(b_{h})+1$: then
$\ell_{\vec{\alpha}}(b_{h+1})\geq\ell_{\vec{\alpha}}(b_{h})+2$;

  * $\bullet$

$\ell(b_{h+1})=\ell(b_{h})$: then $a_{h}$ does not prefer $b_{h}$ to
$b_{h+1}$, but $\ell_{\vec{\alpha}}(b_{h+1})\geq\ell_{\vec{\alpha}}(b_{h})+1$;

  * $\bullet$

$\ell(b_{h+1})=\ell(b_{h})-1$: then $a_{h}$ prefers $b_{h+1}$ to $b_{h}$, but
$\ell_{\vec{\alpha}}(b_{h+1})\geq\ell_{\vec{\alpha}}(b_{h})$.

In each of these cases, we get $(a_{h},b_{h})\notin E_{\ell_{\vec{\alpha}}}$
by the definition of $G_{\ell_{\vec{\alpha}}}$, again a contradiction. ∎

We remark that if a popular assignment exists, then the algorithm returns a
popular assignment $M$ and a corresponding dual certificate $\vec{\alpha}$
such that $\ell_{\vec{\alpha}}\leq\ell_{\vec{\alpha}^{\prime}}$ for any dual
certificate $\vec{\alpha}^{\prime}$ of any popular assignment $M^{\prime}$.
This shows that there is a unique minimal dual certificate in this sense.

We will show that a two-level truncation of Algorithm 1 (i.e., where the
while-loop terminates if $\ell(b)=2$ for some $b\in B$) solves the popular
matching problem with partial order preferences. Before we do this, we point
out a generalization of Lemma 2 that encapsulates the main argument of the
preceding proof. This insight will be useful for generalizing our algorithmic
result in Sections 5-6.

###### Lemma 3

Let $\ell,\ell^{\prime}:B\rightarrow\mathbb{N}$ be such that
$\ell(b)\leq\ell^{\prime}(b)$ for all $b\in B$. Let $M$ and $M^{\prime}$ be
matchings in $G_{\ell}$ and $G_{\ell^{\prime}}$, respectively. Let $b_{0}\in
B$ be an object that is matched in $M^{\prime}$ but not in $M$. Let $P$ be the
path in $M\oplus M^{\prime}$ containing $b_{0}$. If $P$ contains an edge not
in $E_{\ell}$, then $\ell(b_{0})<\ell^{\prime}(b_{0})$.

###  4.1 Implications for the popular matching problem

Recall the reduction from the popular matching problem to the popular
assignment problem, as described in Section 2.3. It can be shown that for
graphs obtained through this reduction (i.e., those with last resort objects
and dummy agents) we can terminate our algorithm as soon as some object
reaches level $2$. This is because in any such instance, there exists a dual
certificate $\vec{\alpha}$ for a popular assignment that satisfies
$|\alpha_{b}|\leq 1$ for all $b\in B$, as shown in Proposition 1 below.

###### Proposition 1

Let $G=(A\cup B,E)$ be an instance of the popular matching problem, and let
$G^{\prime}=(A^{\prime}\cup B^{\prime},E^{\prime})$ be the corresponding
instance of popular assignment as constructed in Section 2.3. If a popular
matching exists in $G$, then there exists a dual certificate $\vec{\alpha}$
for a popular assignment $M^{\prime}$ in $G^{\prime}$ that satisfies
$|\alpha_{b}|\leq 1$ for all $b\in B^{\prime}$.

###### Proof

It is straightforward to check that the reduction in Section 2.3 is correct,
so $G$ admits a popular matching if and only if $G^{\prime}$ admits a popular
assignment. If $M^{\prime}$ is a popular assignment in $G^{\prime}$, then by
Theorem 3.1 there exists a dual certificate $\vec{\alpha}$ for $M^{\prime}$.

We may assume that there exists some object $b_{0}\in B^{\prime}$ for which
$\alpha_{b_{0}}=0$. Otherwise we have $\alpha_{b}\leq-1$ for each $b\in
B^{\prime}$, and since $\alpha_{b}+\alpha_{M^{\prime}(b)}=0$ for each $b\in
B^{\prime}$ by complementary slackness, we also have $\alpha_{a}\geq 1$ for
each $a\in A^{\prime}$. Therefore, decreasing the $\alpha$-value of each agent
by $\min_{a\in A^{\prime}}\alpha_{a}$ while increasing the $\alpha$-value of
each object by the same amount results in a dual certificate where some object
$b_{0}$ has $\alpha$-value $0$.

Assume now for the sake of contradiction that $\alpha_{b}\leq-2$ for some
$b\in B^{\prime}$, and consider the agent $M^{\prime}(b_{0})$. Recall that
$\alpha_{M^{\prime}(b_{0})}=0$ follows from $\alpha_{b_{0}}=0$.

On the one hand, if $M^{\prime}(b_{0})$ is a dummy agent $d$, then by
construction it is adjacent to $b$, and moreover,
$\mathsf{wt}_{M^{\prime}}(d,b)=0$, because $d$ is indifferent between all
objects in $B^{\prime}$. However, then
$\alpha_{d}+\alpha_{b}\leq-2<\mathsf{wt}_{M^{\prime}}(d,b)=0$ contradicts the
feasibility of $\vec{\alpha}$.

On the other hand, if $M^{\prime}(b_{0})$ is a non-dummy agent $a\in A$, then
$\alpha_{l(a)}\geq-1$ follows for the last resort object $l(a)$ of $a$, due to
$\mathsf{wt}_{M^{\prime}}(a,l(a))\geq-1$. Since $a$ is the unique non-dummy
neighbor of $l(a)$ in $G^{\prime}$ and $M^{\prime}(a)=b_{0}$, we know that
$l(a)$ must be assigned to some dummy agent $d^{\prime}$ in $M^{\prime}$. By
$\alpha_{l(a)}\geq-1$ we know $\alpha_{d^{\prime}}\leq 1$; however, then the
edge $(d^{\prime},b)$ contradicts the feasibility of $\vec{\alpha}$ by
$\alpha_{d^{\prime}}+\alpha_{b}\leq-1<\mathsf{wt}_{M^{\prime}}(d^{\prime},b)=0$.
∎

Thanks to Proposition 1, we can solve the popular matching problem by using
Algorithm 1 and terminating it with rejection as soon as some object reaches
level $2$. This implies that the number of iterations the algorithm performs
is at most the number of objects. Thus we have the following corollary.

###### Corollary 1

The popular matching problem where agents’ preferences are partial orders can
be solved in $O(m\cdot n^{3/2})$ time on a graph with $n$ vertices and $m$
edges.

Note that for weak rankings, a two-level truncation of Algorithm 1 essentially
leads to the popular matching algorithm by Abraham et al. [2]. However these
two algorithms are quite different for partial order preferences, e.g.,
consider the example in Section 2.1. Running Algorithm 1 on this instance, we
obtain $\ell(x)=\ell(y)=0$ and $\ell(z)=1$ at the last iteration. This implies
$(b,y)\notin E_{\ell}$, hence the unpopular matching $\\{(a,x),(b,y),(c,z)\\}$
is not contained in $E_{\ell}$.

###  4.2 Popularity with penalties

In the following, we describe a family of problems that interpolates between
the popular matching and popular assignment problem: given an instance
$G=(A\cup B,E)$ of popular matching, we say that a matching $M$ in $G$ is
_popular with penalty $t$_ for some positive integer $t$, if there is no
matching $N$ in $G$ such that $N$ beats $M$ in an election where agents vote
between $M$ and $N$ according to their preferences, but votes of unmatched
agents are counted with weight $t$. Formally, given two matchings $N$ and $M$,
define for any agent $a$

$\mathsf{vote}^{t}_{a}(N,M)=\begin{cases}\phantom{-}1&\text{if\ $a$\ is
matched in~{}$N$ and~{}$M$, and prefers\ $N(a)$\ to\ $M(a)$;}\\\ -1&\text{if\
$a$\ is matched in~{}$N$ and~{}$M$, and prefers\ $M(a)$\ to\ $N(a)$;}\\\
\phantom{-}t&\text{if\ $a$\ is matched in~{}$N$ but not in~{}$M$;}\\\
-t&\text{if\ $a$\ is matched in~{}$M$ but not in~{}$N$;}\\\
\phantom{-}0&\text{otherwise.}\end{cases}$

Then, the matching $M$ is _popular with penalty $t$_, if $\sum_{a\in
A}\mathsf{vote}^{t}_{a}(N,M)\leq 0$ for each matching $N$. Clearly, for $t=1$,
this property corresponds to the notion of popularity for matchings. Moreover,
as long as $G$ contains an assignment (perfect matching), a matching $M$ is
popular with penalty $t=n$ if and only if $M$ is a popular assignment. More
generally, any augmenting path $P$ with respect to a matching $M$ that is
popular with penalty $t$ contains at least $t+1$ agents, otherwise $\sum_{a\in
A}\mathsf{vote}^{t}_{a}(M\oplus P,M)>0$. Hence
$|M|\geq\frac{t}{t+1}|M_{\max}|$ where $M_{\max}$ is a maximum matching in
$G$.

In the following we show that a matching that is popular with penalty $t$ can
be found via a reduction to an instance of the popular assignment problem.
Moreover, we also show that we can determine whether there is an assignment
that is popular with penalty $t$ (when compared with matchings from $G$) by
running a truncated version of Algorithm 1.

####  4.2.1 Reduction for finding a matching that is popular with penalty $t$.

Given an instance $G=(A\cup B,E)$ of popular matching and an integer $t$, let
us construct an instance of popular assignment $G^{\prime}=(A^{\prime}\cup
B^{\prime},E^{\prime})$ as follows:

  * •

The set $A^{\prime}$ of agents contains all agents in $A$, a set
$D=\\{d_{1},\dots,d_{|B|}\\}$ of $|B|$ dummy agents, and a set
$\\{p_{1}(a),\dots,p_{t-1}(a)\\}$ of new agents for each $a\in A$.

  * •

The set $B^{\prime}$ of objects contains all objects in $B$ and a set
$\\{l_{1}(a),\dots,l_{t}(a)\\}$ of new objects for each $a\in A$.

The edge set $E^{\prime}$ of $G^{\prime}$ contains the following edges in
addition to the ones in the original set of edges $E$:

  * •

For each $a\in A$, a path
$P(a)=(a,l_{1}(a),p_{1}(a),l_{2}(a),\dots,p_{t-1}(a),l_{t}(a))$ is added;
moreover, the dummy agents are adjacent to every object in $B\cup L_{t}$ where
$L_{t}=\\{l_{t}(a):a\in A\\}$.

The preferences of the original instance are extended as follows: Each
original agent $a\in A$ keeps her original preference order and in addition,
prefers any object $b\in B$ with $(a,b)\in E$ to object $l_{1}(a)$, i.e.,
$l_{1}(a)$ is $a$’s unique worst-choice object. For $a\in A$ and $i\in[t-1]$,
agent $p_{i}(a)$ prefers object $l_{i}(a)$ to object $l_{i+1}(a)$. Finally,
each dummy agent $d\in D$ is indifferent among her adjacent objects.

For a matching $M$ in $G$, we define a _corresponding assignment_ $M^{\prime}$
in $G^{\prime}$ as follows. For each agent $a\in A$ that is matched in $M$,
define $M^{\prime}(a)=M(a)$ and $M^{\prime}(p_{i}(a))=l_{i}(a)$ for
$i\in[t-1]$. For each agent $a\in A$ that is left unmatched in $M$, define
$M^{\prime}(a)=l_{1}(a)$ and $M^{\prime}(p_{i}(a))=l_{i+1}(a)$ for
$i\in[t-1]$. Finally, we add an arbitrary perfect matching between the dummy
agents in $D$ and the $|B|$ objects in $\\{b\in B:b\text{ is left unmatched in
}M\\}\cup\\{l_{t}(a):a\text{ is matched in }M\\}$.

Note that, by construction of $G^{\prime}$, for every assignment $N^{\prime}$
in $G^{\prime}$ and every $a\in A$, either $N^{\prime}$ contains the edges
$(a,l_{1}(a))$, $(p_{1}(a),l_{2}(a))$, …, $(p_{t-1}(a),l_{t}(a))$ or we have
$N^{\prime}(a)\in B$, $N^{\prime}(l_{t}(a))\in D$, and $N^{\prime}$ contains
the edges $(p_{1}(a),l_{1}(a))$, …, $(p_{t-1}(a),l_{t-1}(a))$. Hence, up to
permutation of the dummy agents (which, due their indifference, do not
influence pairwise comparisons) there is a one-to-one correspondence between
matchings in $G$ and assignments in $G^{\prime}$.

###### Proposition 2

Let $M$ and $N$ be two matchings in $G$ and let $M^{\prime}$ and $N^{\prime}$
be the corresponding assignments in $G^{\prime}$. Then
$\Delta(N^{\prime},M^{\prime})=\sum_{a\in A}\mathsf{vote}^{t}_{a}(N,M)$.

###### Proof

When comparing assignments $N^{\prime}$ and $M^{\prime}$, we write
$\mathsf{vote}_{a}(N^{\prime},M^{\prime})$ instead of
$\mathsf{vote}^{t}_{a}(N^{\prime},M^{\prime})$, since no agent is unmatched in
an assignment. We claim that

$\mathsf{vote}_{a}(N^{\prime},M^{\prime})+\sum_{i=1}^{t-1}\mathsf{vote}_{p_{i}(a)}(N^{\prime},M^{\prime})=\mathsf{vote}^{t}_{a}(N,M)$
(1)

for each agent $a\in A$. Note that for every agent $a\in A$ that is either
matched in both $M$ and $N$ or unmatched in both $M$ and $N$, every agent
$p_{i}(a)$ for $i\in[t-1]$ is matched to the same object in both $M^{\prime}$
and $N^{\prime}$. Hence (1) holds for such agent $a$. Now consider an agent
$a\in A$ that is matched in $N$ but not in $M$. Note that in this case
$\mathsf{vote}_{a}(N^{\prime},M^{\prime})+\sum_{i=1}^{t-1}\mathsf{vote}_{p_{i}(a)}(N^{\prime},M^{\prime})=t$,
because $\mathsf{vote}_{a}(N^{\prime},M^{\prime})=1$ and because $p_{i}(a)$
prefers $N(p_{i}(a))=l_{i}(a)$ to $M(p_{i})=l_{i+1}(a)$ for each $i\in[t-1]$,
so (1) holds again. By a symmetric argument,
$\mathsf{vote}_{a}(N^{\prime},M^{\prime})+\sum_{i=1}^{t-1}\mathsf{vote}_{p_{i}(a)}(N^{\prime},M^{\prime})=-t$
for all agents $a\in A$ that are unmatched in $N^{\prime}$ but matched in
$M^{\prime}$. This proves our claim. Because
$\mathsf{vote}_{d}(N^{\prime},M^{\prime})=0$ for all $d\in D$, we conclude
that

$\displaystyle\Delta(N^{\prime},M^{\prime})$ $\displaystyle=\sum_{a\in
A^{\prime}}\mathsf{vote}_{a}(N^{\prime},M^{\prime})=\sum_{a\in
A}\left(\mathsf{vote}_{a}(N^{\prime},M^{\prime})+\sum_{i=1}^{t-1}\mathsf{vote}_{p_{i}(a)}(N^{\prime},M^{\prime})\right)$
$\displaystyle=\sum_{a\in A}\mathsf{vote}^{t}_{a}(N,M).$

This completes the proof. ∎

By Proposition 2, a matching $M$ in $G$ is popular with penalty $t$ in $G$ if
and only if the corresponding assignment $M^{\prime}$ in $G^{\prime}$ is
popular in $G^{\prime}$. In particular, we can find a matching in $G$ that is
popular with penalty $t$, if it exists, in polynomial time by applying
Algorithm 1. Furthermore, the structure of $G^{\prime}$ allows us to show that
the _$(t+1)$ -level truncation_ of Algorithm 1 suffices to solve the popular
assignment problem in $G^{\prime}$, i.e., we terminate the algorithm with
rejection as soon as some object reaches level $t+1$. The proof of the
following proposition is given in the appendix.

######  Proposition 3 ()

If $M^{\prime}$ is a popular assignment in $G^{\prime}$, then there exists a
dual certificate $\vec{\alpha}$ for $M^{\prime}$ such that $|\alpha_{b}|\leq
t$ for each object $b\in B^{\prime}$.

Recall that there are $O(nt)$ nodes and $O(n^{2})$ edges in $G^{\prime}$ where
$n=|A\cup B|$ and $m=|E|$. Thus, the following result follows immediately from
Proposition 2 and Proposition 3.

###### Theorem 4.3

Given an instance $G=(A\cup B,E)$ of the popular matching problem where
$|A\cup B|=n$ along with $t\in[n-1]$, a matching that is popular with penalty
$t$ can be computed in $O(n^{7/2}\cdot t^{5/2})$ time, if $G$ admits such a
matching.

####  4.2.2 Finding a popular assignment with penalty $t$.

In the following, we show that it is possible to determine whether an instance
of popular matching with penalty $t$ has a solution $M$ that is an assignment.
For any assignment $N$, we have $\sum_{a\in
A}\mathsf{vote}^{t}_{a}(N,M)=\Delta(N,M)$, hence any such solution $M$ is also
a popular assignment. Moreover, for popularity with penalty $t$, an assignment
is also compared with matchings in $G$. This means that for an assignment,
popularity with a given penalty is a stronger requirement than popularity
within the set of assignments.

Below, we show that the $(t+1)$-level truncation of Algorithm 1 finds an
assignment that is popular with penalty $t$ (if it exists). In contrast to the
previous result, we can directly execute the truncated algorithm on $G$
without applying the reduction.

###### Theorem 4.4

For any positive integer $t$, the $(t+1)$-level truncation of Algorithm 1
finds an assignment that is popular with penalty $t$, if such an assignment
exists. The running time on a graph with $n$ vertices and $m$ edges is
$O(t\cdot m\cdot n^{3/2})$.

###### Proof

Suppose first that Algorithm 1 outputs an assignment $M$ while all objects
have level at most $t$; by the correctness of Algorithm 1 we know that $M$ is
a popular assignment. We claim that $M$ is also popular with penalty $t$.

For the sake of contradiction, assume that $N$ is a matching that beats $M$,
i.e., for which $\sum_{a\in A}\mathsf{vote}^{t}_{a}(N,M)>0$, and consider the
symmetric difference $N\oplus M$ of $N$ and $M$. For each connected component
$K$ in $N\oplus M$, let $A_{K}$ and $B_{K}$ denote the set of agents and
objects in $K$, respectively. Observe that there must exist a connected
component $K$ of $N\oplus M$ for which we have $\sum_{a\in
A_{K}}\mathsf{vote}^{t}_{a}(N,M)>0$.

First, if $K$ is a cycle, then the matching $M^{\prime}=M\oplus K$ is an
assignment, and we get that $\sum_{a\in
A}\mathsf{vote}^{t}_{a}(M^{\prime},M)=\sum_{a\in
A_{K}}\mathsf{vote}^{t}_{a}(M^{\prime},M)=\sum_{a\in
A_{K}}\mathsf{vote}^{t}_{a}(N,M)>0$, which contradicts the fact that $M$ is a
popular assignment.

Second, if $K$ is a path, then since $M$ is a perfect matching, the two
endpoints of $K$ must be an agent $a$ and an object $b$, both matched in $M$
but unmatched in $N$. Let the vertices of the path $K$ be
$a=a_{0},b_{0},a_{1},b_{1},\dots,a_{t},b_{t}=b$ for some $t\in\mathbb{N}$, so
that $M(a_{i})=b_{i}$ for $i=0,1,\dots,t$ and $N(a_{i})=b_{i-1}$ for
$i=1,\dots,t$. Let $\vec{\alpha}$ be the dual certificate for $M$ for which
$\ell_{\vec{\alpha}}$ is the level-function obtained by Algorithm 1.

On the one hand, by complementary slackness we know
$\sum_{i=0}^{t}(\alpha_{a_{i}}+\alpha_{b_{i}})=0$. On the other hand, for each
$i\in[t]$ we know
$\mathsf{wt}_{M}(a_{i},b_{i-1})=\mathsf{vote}^{t}_{a_{i}}(N,M)$ by definition,
which implies

$\displaystyle\sum_{i=1}^{t}(\alpha_{a_{i}}+\alpha_{b_{i-1}})\geq$
$\displaystyle\sum_{i=1}^{t}\mathsf{wt}_{M}(a_{i},b_{i-1})=\sum_{i=1}^{t}\mathsf{vote}^{t}_{a_{i}}(N,M)$
$\displaystyle=$
$\displaystyle\left(\sum_{i=0}^{t}\mathsf{vote}^{t}_{a_{i}}(N,M)\right)-\mathsf{vote}^{t}_{a_{0}}(N,M)=\left(\sum_{i=0}^{t}\mathsf{vote}^{t}_{a_{i}}(N,M)\right)+t>t$

because $\mathsf{vote}^{t}_{a_{0}}(N,M)=-t$. This leads to

$0=\sum_{i=0}^{t}(\alpha_{a_{i}}+\alpha_{b_{i}})=\alpha_{a_{0}}+\alpha_{b_{t}}+\sum_{i=1}^{t}\left(\alpha_{a_{i}}+\alpha_{b_{i-1}}\right)>\alpha_{b_{t}}+t$

by $\alpha_{a_{0}}\geq 0$. However, this means
$\ell_{\vec{\alpha}}(b_{t})=|\alpha_{b_{t}}|>t$ which contradicts our
assumption that Algorithm 1 returned $M$ while all objects had level at most
$t$. This proves that $M$ is indeed popular with penalty $t$.

For the other direction, we show that if $M$ is an assignment that is popular
with penalty $t$, then it admits a dual certificate $\vec{\alpha}$ such that
$\alpha_{b}\geq-t$ for each object $b\in B$. Since Algorithm 1 returns a level
function $\ell$ satisfying $\ell(b)\leq\ell_{\vec{\alpha}}(b)=|\alpha_{b}|$
for each $b\in B$, this means that the $(t+1)$-level truncation of Algorithm 1
will return an assignment as desired.

Recall first that $M$ is a popular assignment, so let $\vec{\alpha}$ be a dual
certificate for $M$ minimizing $\sum_{a\in A}\alpha_{a}$. Assume for the sake
of contradiction that $\alpha_{b^{\star}}<-t$ for some $b^{\star}\in B$. Let
us call an edge $(a,b)$ in $G$ _tight_ , if
$\alpha_{a}+\alpha_{b}=\mathsf{wt}_{M}(a,b)$; clearly, all edges of $M$ are
tight by complementary slackness. Let us consider the set $A^{\star}$ of
agents and the set $B^{\star}$ of objects in $G$ that are reachable from
$b^{\star}$ via an $M$-alternating path in $G$ consisting only of tight edges
and starting with the edge $(M(b^{\star}),b^{\star})$; for convenience, let us
add $b^{\star}$ to $B^{\star}$.

We show that there exists some $a^{\star}\in A^{\star}$ with
$\alpha_{a^{\star}}=0$. If not, then consider the modification $\vec{\beta}$
of $\vec{\alpha}$ obtained through increasing the $\alpha$-value of each
object in $B^{\star}$ by $1$ and decreasing the $\alpha$-value of each agent
in $A^{\star}$ by $1$. We claim that $\vec{\beta}$ is a dual certificate.
First note that an agent $a$ is contained in $A^{\star}$ if and only if $M(a)$
is contained in $B^{\star}$, by construction. Hence, as no agent in
$A^{\star}$ has level $0$, the $\beta$-value of each agent remains non-
negative, and the $\beta$-value of each object remains non-positive. Observe
also that $\vec{\beta}$ is a feasible solution for LP2: assuming that LP2 is
violated on some edge $(a,b)$, it must be the case that $a\in A^{\star}$ but
$b\notin B^{\star}$ and $(a,b)$ is tight, otherwise
$\beta_{a}+\beta_{b}\geq\mathsf{wt}_{M}(a,b)$ still holds, since
$\vec{\alpha}$ is a feasible solution for LP2. However, then the edge $(a,b)$
is not in $M$ but is tight, which implies that appending $(a,b)$ to an
$M$-alternating path from $b^{\star}$ to $a$ witnessing $a\in A^{\star}$
yields a path that shows $b\in B^{\star}$, a contradiction. Hence,
$\vec{\beta}$ is also a dual certificate, contradicting the minimality of
$\vec{\alpha}$. This proves that there exists some $a^{\star}\in A^{\star}$
with $\alpha_{a^{\star}}=0$.

Now, let $P$ be an $M$-alternating path of tight edges between $b^{\star}$ and
$a^{\star}$ that witnesses $a^{\star}\in A^{\star}$, and let $A_{P}$ and
$B_{P}$ denote the agents and objects appearing on $P$, respectively. Consider
the matching $N=M\oplus P$ in which $a^{\star}$ and $b^{\star}$ are unmatched,
and observe that

$\displaystyle\sum_{a\in A}\mathsf{vote}^{t}_{a}(N,M)$
$\displaystyle=\sum_{a\in
A_{P}}\mathsf{vote}^{t}_{a}(N,M)=\mathsf{vote}^{t}_{a^{\star}}(N,M)+\sum_{a\in
A_{P}\setminus\\{a^{\star}\\}}\mathsf{vote}^{t}_{a}(N,M)$
$\displaystyle=-t+\sum_{a\in
A_{P}\setminus\\{a^{\star}\\}}\mathsf{wt}_{M}(a,N(a))=-t+\sum_{a\in
A_{P}\setminus\\{a^{\star}\\}}\alpha_{a}+\sum_{b\in
B_{P}\setminus\\{b^{\star}\\}}\alpha_{b}$ $\displaystyle=-t+\left(\sum_{a\in
A_{P}}\alpha_{a}+\sum_{B\in
B_{P}}\alpha_{b}\right)-\alpha_{a^{\star}}-\alpha_{b^{\star}}=-t+0-0-\alpha_{b^{\star}}>0$

which contradicts our assumption that $M$ is an assignment that is popular
with penalty $t$.

Finally, the running time of the $(t+1)$-truncation of Algorithm 1 is indeed
as claimed, since there can be at most $t\cdot n$ iterations, each one taking
$O(m\sqrt{n})$ time. ∎

##  5 Finding a popular assignment with forced/forbidden edges

In this section we consider a variant of the popular assignment problem where,
in addition to our instance, we are given a set $F^{+}$ of _forced_ edges and
a set $F^{-}$ of _forbidden_ edges, and what we seek is a popular assignment
that contains $F^{+}$ and is disjoint from $F^{-}$. Observe that it is
sufficient to deal with forbidden edges, since putting an edge $(a,b)$ into
$F^{+}$ is the same as putting all the edges in the set
$\\{(a,b^{\prime}):b^{\prime}\in\mathsf{Nbr}(a)\textrm{ and }b^{\prime}\neq
b\\}$ into $F^{-}$.

##### The popular assignment with forbidden edges problem.

Given a bipartite graph $G=(A\cup B,E)$ where every $a\in A$ has preferences
in partial order over her neighbors, together with a set $F\subseteq E$ of
forbidden edges, does $G$ admit a popular assignment $M$ avoiding $F$, i.e.,
one where $M\cap F=\emptyset$?

We will show that in order to deal with forbidden edges, it suffices to modify
our algorithm in Section 4 as follows; see Algorithm 2. The only difference
from the earlier algorithm is that we find a maximum matching in the subgraph
$G_{\ell}-F$, i.e., on the edge set $E_{\ell}\setminus F$.

Algorithm 2 Finding a popular assignment with forbidden set $F\subset E$

1:for all $b\in B$ do $\ell(b)=0$.

2:while $\ell(b)<n$ for all $b\in B$ do

3: Construct $G_{\ell}=(A\cup B,E_{\ell})$ and find a maximum matching $M$ in
$G_{\ell}-F$.

4: if $M$ is a perfect matching then return $M$.

5: for all $b\in B$ unmatched in $M$ do $\ell(b)=\ell(b)+1$.

6:return “$G$ has no popular assignment with forbidden set $F$”.

###### Theorem 5.1

The above algorithm outputs a popular assignment avoiding $F$, if such an
assignment exists in $G$.

###### Proof

Recall that any perfect matching in $G_{\ell}$ is a popular assignment in $G$
by Lemma 1. It is therefore immediate that if the above algorithm outputs a
matching $M$, then $M$ is a popular assignment in $G$ that avoids $F$.

Let us now prove that if there exists a popular assignment $M^{\star}$
avoiding $F$, then our algorithm outputs such an assignment. Let
$\vec{\alpha}$ be a dual certificate for $M^{\star}$. Let $\ell_{i}$ denote
the level function at the beginning of iteration $i$ of the algorithm. As in
the proof of Theorem 4.2, we show by induction that
$\ell_{i}(b)\leq|\alpha_{b}|$ for all $b\in B$ for any iteration $i$.

This is clearly true initially with $\ell_{1}(b)=0$ for all $b\in B$. To
complete the induction, it suffices to show that
$\ell_{i}(b_{0})<|\alpha_{b_{0}}|$ for all $b_{0}\in B$ that are unmatched by
any maximum matching $M$ in $G_{\ell_{i}}-F$. Since $M^{\star}$ is a perfect
matching, the symmetric difference $M\oplus M^{\star}$ contains an
$M$-augmenting path $P$ starting at $b_{0}$. However, because $M$ has maximum
size in $G_{\ell_{i}}-F$, the path $P$ must contain an edge $e\notin
E_{\ell_{i}}\setminus F$. We have $(M\cup M^{\star})\cap F=\emptyset$, thus we
obtain $e\notin F$ and therefore $e\notin E_{\ell_{i}}$. Note that Lemma 1
implies $M^{\star}\subseteq E_{\ell_{\vec{\alpha}}}$ (recall that
$\ell_{\vec{\alpha}}(b)=|\alpha_{b}|$ for all $b\in B$). Furthermore,
$\ell_{i}(b)\leq\ell_{\vec{\alpha}}(b)$ for all $b\in B$ by our induction
hypothesis. We can thus apply Lemma 3 with $M^{\prime}=M^{\star}$ and
$\ell^{\prime}=\ell_{\vec{\alpha}}$ to obtain
$\ell_{i}(b_{0})<\ell_{\vec{\alpha}}(b_{0})=|\alpha_{b_{0}}|$, which completes
the induction step. ∎

##### Minimum-cost popular assignment vs. popular assignment with forbidden
edges.

The popular assignment with forbidden edges problem can be seen as the special
case of the minimum-cost popular assignment problem in which the popular
assignment may only contain edges of cost $0$, excluding all edges of non-zero
cost. In the general version of minimum-cost popular assignment, however,
there is a degree of freedom as to which non-zero cost edges are included in
the assignment. Theorem 1.4 shows that this degree of freedom introduces an
additional complexity to the problem. Indeed, in our reduction from Vertex
Cover in Theorem 7.1 (which implies Theorem 1.4), a set of vertices chosen as
a vertex cover is encoded via the set of cost $1$ edges chosen to be included
in the assignment, and explicitly forbidding all cost $1$ edges would turn the
constructed popular assignment with forbidden edges instance into a trivial
‘no’-instance.

##  6 Finding an assignment with minimum unpopularity margin

In this section we consider the $k$-unpopularity-margin problem in $G$;
Section 6.1 has our algorithmic result and Section 6.2 contains our hardness
results.

###  6.1 Our algorithm

For any assignment $M$, recall that the optimal value of LP1 is
$\max_{N}\Delta(N,M)=\mu(M)$, where the maximum is taken over all assignments
$N$ in $G$. Consequently, $\mu(M)$ equals the optimal value of the dual linear
program LP2 as well. Therefore, $\mu(M)=k$ if and only if there exists an
optimal solution $\vec{\alpha}$ to LP2 for which $\sum_{u\in A\cup
B}\alpha_{u}=k$. This leads us to a characterization of assignments with a
bounded unpopularity margin that is a direct analog of Theorem 3.1.

###### Theorem 6.1

$M$ is an assignment with $\mu(M)\leq k$ if and only if there exists a
solution $\vec{\alpha}$ to LP2 such that $\alpha_{a}\in\\{0,1,\dots,n\\}$ for
all $a\in A$, $\alpha_{b}\in\\{0,-1,\dots,-(n-1)\\}$ for all $b\in B$, and
$\sum_{u\in A\cup B}\alpha_{u}\leq k$.

######  Proof (of Theorem 3.1 and Theorem 6.1)

If there exists a feasible solution $\vec{\alpha}$ to LP2 such that
$\sum_{u\in A\cup B}\alpha_{u}=0$, then the optimal value of LP2 is 0 and
hence by LP-duality, the optimal value of LP1 is also 0. Thus $\Delta(N,M)\leq
0$ for any perfect matching $N$; in other words, $M$ is a popular assignment.
Similarly, if there is a feasible solution $\vec{\alpha}$ to LP2 such that
$\sum_{u\in A\cup B}\alpha_{u}\leq k$, then $\Delta(N,M)\leq k$ for any
perfect matching $N$, so $\mu(M)\leq k$.

We will now show the converse. Let $M$ be a perfect matching with $\mu(M)=k$;
there exists a dual optimal solution $\vec{\alpha}$ such that $\sum_{u\in
A\cup B}\alpha_{u}=k$. Moreover, we can assume
$\vec{\alpha}\in\mathbb{Z}^{2n}$ due to the total unimodularity of the
constraint matrix. We can also assume $\alpha_{b}\leq 0$ for all $b\in B$,
because feasibility and optimality are preserved if we decrease $\alpha_{b}$
for all $b\in B$ and increase $\alpha_{a}$ for all $a\in A$ by the same
amount.

Let us choose $\vec{\alpha}$ such that $\sum_{b\in B}\alpha_{b}$ is maximum
subject to the above assumptions. We claim that if there is no $b\in B$ with
$\alpha_{b}=-r$ for some $r\in\mathbb{N}$, then there is no $b\in B$ with
$\alpha_{b}\leq-(r+1)$. Suppose the contrary, and let $B^{\prime}=\\{b\in
B:\alpha_{b}<-r\\}$ and $A^{\prime}=\\{M(b):b\in B^{\prime}\\}$. Since
$\alpha_{a}+\alpha_{b}\geq 0$ for every $(a,b)\in M$, we have $\alpha_{a}\geq
r+1$ for every $a\in A^{\prime}$. Let $\vec{\alpha}^{\prime}$ be obtained by
decreasing $\alpha_{a}$ by 1 for all $a\in A^{\prime}$ and increasing
$\alpha_{b}$ by 1 for all $b\in B^{\prime}$. The dual feasibility constraints
$\alpha^{\prime}_{a}+\alpha^{\prime}_{b}\geq\mathsf{wt}_{M}(a,b)$ can only be
violated if $a\in A^{\prime}$, $b\notin B^{\prime}$, and
$\alpha_{a}+\alpha_{b}=\mathsf{wt}_{M}(a,b)$. But this would imply
$\alpha_{a}\geq r+1$, $\alpha_{b}\geq-r+1$ (since $b\notin B^{\prime}$ and
$\alpha_{b}$ cannot be $-r$), and
$\alpha_{a}+\alpha_{b}=\mathsf{wt}_{M}(a,b)\leq 1$, a contradiction. Thus,
$\vec{\alpha}^{\prime}$ is also an optimal dual solution, and $\sum_{b\in
B}\alpha^{\prime}_{b}>\sum_{b\in B}\alpha_{b}$, contradicting the choice of
$\vec{\alpha}$.

We have shown that the values that $\vec{\alpha}$ takes on $B$ are consecutive
integers, so we obtain that $\alpha_{b}\in\\{0,-1,-2,$ $\ldots,-(n-1)\\}$ for
all $b\in B$. Since $\alpha_{a}+\alpha_{b}\geq 0$ for every $(a,b)\in M$, we
have $\alpha_{a}\geq 0$ for every $a\in A^{\prime}$.

To conclude the proof of Theorem 3.1, observe that $M$ is an optimal primal
solution when $k=0$, so $\alpha_{a}+\alpha_{b}=0$ for every $(a,b)\in M$. This
implies that $\alpha_{a}\in\\{0,1,2,\ldots,n-1\\}$ for all $a\in A$. As for
Theorem 6.1, let $N$ be a perfect matching that is optimal for LP1; then
$\alpha_{a}+\alpha_{b}=\mathsf{wt}_{M}(a,b)\leq 1$ for every $(a,b)\in N$ by
complementary slackness, and therefore $\alpha_{a}\leq n$ for all $a\in A$. ∎

Generalizing the notion that we already used for popular assignments, we
define a _dual certificate_ for an assignment $M$ with unpopularity margin $k$
as a solution $\vec{\alpha}$ to LP2 with properties as described in Theorem
6.1. So let us suppose that $M$ is an assignment with $\mu(M)=k$ and
$\vec{\alpha}$ is a dual certificate for $M$. We define the _load_ of
$(a,b)\in M$ as $\alpha_{a}+\alpha_{b}$, and we will say that an edge
$(a,b)\in M$ is _overloaded_ (with respect to $\vec{\alpha}$), if it has a
positive load, that is, $\alpha_{a}+\alpha_{b}>0$. Clearly, the total load of
all edges in $M$ is at most $k$, moreover
$\alpha_{a}+\alpha_{b}\geq\mathsf{wt}_{M}(a,b)=0$ for every $(a,b)\in M$, so
there are at most $k$ overloaded edges in $M$.

Given a level function $\ell:B\rightarrow\mathbb{N}$ and an integer
$\lambda\in\mathbb{N}$, we say that edge $(a,b)$ is _$\lambda$ -feasible_, if

  * (i)

$b$ has level at least $\ell^{*}(a)-\lambda+1$ where
$\ell^{*}(a)=\max_{b\in\mathsf{Nbr}(a)}\ell(b)$, or

  * (ii)

$b$ has level $\ell^{*}(a)-\lambda$ and $a$ has no neighbor in level
$\ell^{*}(a)$ that she prefers to $b$, or

  * (iii)

$b$ has level $\ell^{*}(a)-\lambda-1$, $a$ prefers $b$ to each of her
neighbors in level $\ell^{*}(a)$, and moreover, $a$ prefers none of her
neighbors in level $\ell^{*}(a)-1$ to $b$.

Note that $0$-feasible edges are exactly those contained in the graph
$G_{\ell}$ induced by levels $\ell(\cdot)$, as defined in Section 4. The
following observation follows directly from the constraints of LP2.

###### Proposition 4

Let $M$ be an assignment with $\mu(M)\leq k$ and let $\vec{\alpha}$ be a dual
certificate for $M$. Consider the level function $\ell_{\vec{\alpha}}$ where
the level of any $b\in B$ is $\ell_{\vec{\alpha}}(b)=-\alpha_{b}$. Then any
edge $e\in M$ with load $\lambda$ is $\lambda$-feasible.

Given a level function $\ell:B\rightarrow\mathbb{N}$ and a load capacity
function $\lambda:E\rightarrow\mathbb{N}$, we define the graph _induced by
levels $\ell(\cdot)$ and load capacities $\lambda(\cdot)$_ as
$G_{\ell,\lambda}=(A\cup B,E_{\ell,\lambda})$ where an edge $e$ is contained
in $E_{\ell,\lambda}$ if and only if $e$ is $\lambda(e)$-feasible.

We are now ready to describe an algorithm for finding an assignment $M$ with
$\mu(M)\leq k$ if such an assignment exists. Algorithm 3 starts by guessing
the load $\lambda(e)$ for each edge $e$ of $E$. Then we use a variant of the
algorithm for Theorem 5.1 that enables each edge $e$ with $\lambda(e)>0$ to
have positive load (so $G_{\ell,\lambda}$ will be used instead of $G_{\ell}$),
and treats the overloaded edges as forced edges.

Algorithm 3 Finding a popular assignment with unpopularity margin at most $k$

1:for all functions $\lambda:E\rightarrow\mathbb{N}$ with $\sum_{e\in
E}\lambda(e)\leq k$ do

2: Set $K=\\{e\in E:\lambda(e)>0\\}$ as the edges that we will overload.

3: Set $F=\\{(a,b^{\prime})\in E:(a,b)\in K,b^{\prime}\neq b\\}$ as the set of
forbidden edges.

4: for all $b\in B$ do $\ell(b)=0$.

5: while $\ell(b)<n$ for all $b\in B$ do

6: Construct the graph $G_{\ell,\lambda}$ and find a maximum matching $M$ in
$G_{\ell,\lambda}-F$.

7: if $M$ is a perfect matching then return $M$.

8: for all $b\in B$ unmatched in $M$ do $\ell(b)=\ell(b)+1$.

9:return “$G$ has no assignment $M$ with $\mu(M)\leq k$”.

Observe that there are at most $m^{k}$ ways to choose the load capacity
function $\lambda$, where $m=|E|$, by the bound $\sum_{e\in E}\lambda(e)\leq
k$. Each iteration of the while-loop takes $O(m\sqrt{n})$ time and there are
at most $m^{k}\cdot n^{2}$ such iterations. Thus the running time of the above
algorithm is $O(m^{k+1}\cdot n^{5/2})$.

######  Proof (of Theorem 1.2)

Suppose Algorithm 3 returns an assignment $M$. Consider the values of
$\lambda(\cdot)$ and $\ell(\cdot)$ at the moment the algorithm outputs $M$.
Set $\alpha_{b}=-\ell(b)$ for each object, and set
$\alpha_{a}=-\alpha_{b}+\lambda(a,b)$ for each edge $(a,b)\in M$. From the
definition of $G_{\ell,\lambda}$ and $\lambda$-feasibility, such a vector
$\vec{\alpha}$ fulfills all constraints in LP2. Hence, by $\sum_{u\in A\cup
B}\alpha_{u}=\sum_{(a,b)\in M}\lambda(a,b)\leq k$, we get that $\mu(M)\leq k$.

Now let us assume that $G$ admits an assignment $M^{\star}$ with
$\mu(M^{\star})\leq k$, and let $\vec{\alpha}$ be a dual certificate for
$M^{\star}$. We need to show that our algorithm will produce an output.
Consider those iterations where $\lambda(e)$ equals the load of each edge
$e\in M^{\star}$; we call this the _significant branch_ of the algorithm. We
claim that $|\alpha_{b}|\geq\ell(b)$ holds throughout the run of the
significant branch.

To prove our claim, we use the same approach as in the proof of Theorem 5.1,
based on induction. Clearly, the claim holds at the beginning of the branch;
we need to show that $\ell(b)$ is increased only if $|\alpha_{b}|>\ell(b)$. So
let $|\alpha_{b}|\geq\ell(b)$ for each $b\in B$ at the beginning of an
iteration (steps (6)–(8)), and consider an object $b$ whose value is increased
at the end of the iteration.

First, assume that $b$ is incident to some overloaded edge $(a,b)$ of
$M^{\star}$ with load $\lambda(a,b)$. Observe that $(a,b)\in K$, and all edges
incident to $a$ other than $(a,b)$ belong to the set $F$ of forbidden edges.
Therefore, if $a$ is not matched to $b$ in a maximum matching in
$G_{\ell,\lambda}-F$, then this must be because $(a,b)$ is not an edge in
$G_{\ell,\lambda}$. That is, the edge $(a,b)\in K$ is not $\lambda$-feasible
with respect to $\ell(\cdot)$. Recall that by Proposition 4, $(a,b)$ is
$\lambda(a,b)$-feasible with respect to the level function
$\ell_{\vec{\alpha}}$ defined by
$\ell_{\vec{\alpha}}(b^{\prime})=|\alpha_{b^{\prime}}|$ for each object
$b^{\prime}$. Moreover, by our induction hypothesis,
$\ell(b^{\prime})\leq|\alpha_{b^{\prime}}|$ holds at the beginning of the
iterations for each object $b^{\prime}$, that is, the
$\ell_{\vec{\alpha}}$-level of any object is at least its $\ell$-level.
Consider the following hypothetical procedure: starting from the level
function $\ell(\cdot)$ (in which $(a,b)$ is _not_ $\lambda(a,b)$-feasible) we
obtain the level function $\ell_{\vec{\alpha}}(\cdot)$ (in which $(a,b)$ _is_
$\lambda(a,b)$-feasible) via raising the levels of some objects and never
decreasing the level of any object. However, by the definition of
$\lambda$-feasibility, if we only raise the levels of objects other than $b$,
then the edge $(a,b)$ cannot become $\lambda(a,b)$-feasible. Hence, in this
hypothetical procedure of obtaining $\ell_{\vec{\alpha}}(\cdot)$ from
$\ell(\cdot)$, it is necessary to raise the level of $b$. It follows that
$\ell_{\vec{\alpha}}(b)=|\alpha_{b}|>\ell(b)$ must hold.

Second, assume that $b$ is not incident to any overloaded edge. Consider the
path $P$ in $M\oplus M^{\star}$ on which $b$ lies. Notice that, since the
edges of $F$ are treated as forbidden edges, $M$ assigns each agent incident
to some edge in $K$ either the object assigned to it by $M^{\star}$, or does
not assign any object to it. Therefore, no such agent lies on the path $P$.
Consequently, we can apply Lemma 3 to the matchings $M\cap P\subseteq
E_{\ell}$ and $M^{\star}\cap P\subseteq E_{\ell_{\vec{\alpha}}}$. This yields
$|\alpha_{b}|=\ell_{\vec{\alpha}}(b)>\ell(b)$, proving our claim.

Finally, note that in the significant branch, no object may have $\ell$-level
higher than $n-1$, as implied by the properties of $\vec{\alpha}$ stated in
Theorem 6.1. ∎

###  6.2 Hardness results

We now contrast Theorem 1.2 with Theorem 1.3 which states that finding an
assignment with minimum unpopularity margin is $\mathsf{NP}$-hard and
$\mathsf{W}_{l}[1]$-hard with respect to the parameter $k$, our bound on the
unpopularity margin. A parameterized problem $Q$ is $\mathsf{W}_{l}[1]$-hard
if there exists a linear FPT-reduction from the weighted antimonotone cnf
2-sat (or wcnf 2sat-) problem555 The input to this problem is a propositional
formula $\varphi$ in conjunctive normal form with only negative literals and
clauses of size two, together with an integer parameter $k$; the question is
whether the formula can be satisfied by a variable assignment that sets
exactly $k$ variables to true. to $Q$ [5]. Since wcnf 2sat- is a
$\mathsf{W}[1]$-complete problem [10], $\mathsf{W}_{l}[1]$-hardness implies
$\mathsf{W}[1]$-hardness. While the $\mathsf{W}[1]$-hardness of
$k$-unpopularity margin shows that it cannot be solved in $f(k)|I|^{O(1)}$
time for any computable function $f$ unless $W[1]=FPT$ (where $|I|$ denotes
the input length), the results of Chen et al. [5] enable us to obtain a
tighter lower bound: the $\mathsf{W}_{l}[1]$-hardness of $k$-unpopularity
margin implies that it cannot even be solved in $f(k)|I|^{o(k)}$ time for any
computable function $f$, unless all problems in $\mathsf{SNP}$ are solvable in
subexponential time – a possibility widely considered unlikely. Therefore,
Theorem 1.3 shows that our algorithm for Theorem 1.2 is essentially optimal.

Note that the unpopularity margin of any assignment $M$ can be computed
efficiently by determining the optimal value of LP1, so the $k$-unpopularity
margin problem is in $\mathsf{NP}$. In the remainder of this section, we
present a linear FPT-reduction from the Clique problem to the $k$-unpopularity
margin problem where agents’ preferences are weak rankings. By the work of
Chen et al. [5], the $\mathsf{W}_{l}[1]$-hardness of $k$-unpopularity margin
follows. Our reduction is a polynomial-time reduction as well, implying
$\mathsf{NP}$-hardness for the case of weak rankings; note that this also
follows easily from the $\mathsf{NP}$-hardness of finding a matching (not
necessarily an assignment) with minimum unpopularity margin [23], using our
reduction from the popular matching problem to the popular assignment problem.
Both the reduction presented in this section and the reduction from popular
matching in Section 2.3 use weak rankings. However, we prove the
$\mathsf{NP}$-hardness of $k$-unpopularity margin for strict rankings by
reducing the problem with weak rankings to the case with strict rankings in
Lemma 10.666The reduction from weak to strict rankings increases the parameter
$k$ by a non-constant term. Thus $\mathsf{W}_{l}[1]$-hardness does not carry
over and the parameterized complexity of $k$-unpopularity margin with strict
rankings is still open; see the related open question in Section 8.

Instead of giving a direct reduction from Clique, we will use an intermediate
problem that we call CliqueHog. Given a graph $H$, we define a _cliquehog_ of
size $k$ as a pair $(C,F)$ such that $C\subseteq V(H)$ is a clique of size
$k$, and $F\subseteq E(H)$ is a set of edges that contains exactly two edges
connecting $c$ to $V(H)\setminus C$, for each $c\in C$. The input of the
CliqueHog problem is a graph $H$ and an integer $k$, and it asks whether $H$
contains a _cliquehog_ of size $k$.

###### Lemma 4

The CliqueHog problem is $\mathsf{NP}$-hard and $\mathsf{W}_{l}[1]$-hard with
parameter $k$.

###### Proof

We reduce from the Clique problem. Given a graph $H=(V,E)$ and an integer $k$,
we construct a graph $H^{\prime}$ by adding $2|V|$ edges and $2|V|$ vertices
to $H$ as follows: for each vertex $v$ of $H$ we introduce two new vertices
$v^{\prime}$ and $v^{\prime\prime}$, together with the edges $(v,v^{\prime})$
and $(v,v^{\prime\prime})$. It is then easy to see that $H$ contains a clique
of size $k$ if and only if $H^{\prime}$ contains a cliquehog of size $k$. The
reduction is a linear FPT-reduction with parameter $k$, as well as a
polynomial-time reduction. ∎

Let us now prove the first part of Theorem 1.3 by presenting a reduction from
the CliqueHog problem.

##### Construction.

Let $H=(V,E)$ and $k$ be our input for CliqueHog. We construct an instance $G$
of the $k$-unpopularity margin problem, with a set $A$ of agents and a set $B$
of objects as follows. For each vertex $v\in V$, we define a vertex gadget
$G_{v}$ containing agents $a_{v}^{0}$ and $a_{v}^{1}$ and objects $b_{v}^{0}$
and $b_{v}^{1}$. For each $e\in E$, we define an agent $a_{e}$ and an object
$b_{e}$. Furthermore, we will use a set $A_{D}$ of $|E|-\binom{k}{2}-2k$ dummy
agents, and a set $B_{D}$ of $|E|-\binom{k}{2}-2k$ artificial objects. We
define $A_{V}=\\{a_{v}^{i}:v\in V,i\in\\{0,1\\}\\}$, $B_{V}=\\{b_{v}^{i}:v\in
V,i\in\\{0,1\\}\\}$, $A_{E}=\\{A_{e}:e\in E\\}$, and $B_{E}=\\{b_{e}:e\in
E\\}$. We set $A=A_{V}\cup A_{E}\cup A_{D}$ and $B=B_{V}\cup B_{E}\cup B_{D}$.
The preferences of the agents in $G$ are as follows (ties are simply indicated
by including them as a set in the preference list):

$a_{v}^{i}:$ | $\\{b_{e}:e\textrm{ is incident to $v$ in $H$}\\}\succ b_{v}^{0}\succ b_{v}^{1}\qquad$ | for each $v\in V$ and $i\in\\{0,1\\}$;
---|---|---
$a_{e}:$ | $b_{e}\succ B_{D}\cup\\{b_{x}^{0},b_{y}^{0}\\}\succ\\{b_{x}^{1},b_{y}^{1}\\}$ | for each $e=(x,y)\in E$;
$a_{d}:$ | $B_{E}$ | for each $a_{d}\in A_{D}$.

We finish the construction by setting the bound for the unpopularity margin of
the desired assignment as $k$. Clearly, this is a polynomial-time reduction,
and also a linear FPT-reduction with parameter $k$, so it remains to prove
that $H$ contains a cliquehog of size $k$ if and only if $G$ admits an
assignment $M$ with unpopularity margin at most $k$.

###### Lemma 5

If $(C,F)$ is a cliquehog in $H$ of size $k$, then $G$ admits an assignment
$M$ with unpopularity margin at most $k$.

###### Proof

Let $f_{c}^{0}$ and $f_{c}^{1}$ denote the two edges of $F$ connecting $c$ to
$V\setminus C$ in $H$ (in any fixed order), and we set
$F^{i}=\\{f_{c}^{i}:c\in C\\}$ for $i\in\\{0,1\\}$.

Figure 3: Illustration for the construction in the proof of Theorem 1.3. The
assignment $M$ defined in Lemma 5 is indicated by bold lines. Red, black, and
blue edges have weight $+1$, $0$, and $-1$, respectively, according to
$\mathsf{wt}_{M}(\cdot)$. The values of the dual certificate $\vec{\alpha}$
for $M$ are indicated by numbers within the circle (square) corresponding to
the given agent (object, respectively). For some edges $(a_{e},b_{e})$ in $G$
we indicate only the corresponding edge $e$ of $H$ (see $(u,v)$, $(v,x)$ and
$(v,y)$). The figure assumes $v\in C$ but $x,y\notin C$; note that the edge
$(a_{(v,y)},b_{v}^{1})$ is overloaded in $M$.

We define an assignment $M$ as follows; see Fig. 3 as an illustration. First,
let us assign the $|E|-\binom{k}{2}-2k$ objects in $\\{b_{e}:e\notin E[C]\cup
F\\}$ to the dummy agents (where $E[C]$ denotes the set of those edges of $E$
whose both endpoints are in $C$). Second, we assign the artificial objects to
the $|E|-\binom{k}{2}-2k$ agents in $\\{a_{e}:e\notin E[C]\cup F\\}$. To
define $M$ on the remaining objects and agents, let

$M(a_{v}^{i})=b_{v}^{i}$ | for each $v\in V\setminus C$ and $i\in\\{0,1\\}$;
---|---
$M(a_{v}^{i})=b_{f_{v}^{i}}$ | for each $v\in C$ and $i\in\\{0,1\\}$;
$M(a_{e})=b_{e}$ | for each $e\in E[C]$;
$M(a_{f})=b_{v}^{i}$ | for each $f\in F$ where $f=f_{v}^{i}$.

Observe that $M$ indeed assigns exactly one object to each agent. To show that
$\mu(M)\leq k$, we define a dual certificate $\vec{\alpha}$ for $M$:

$\alpha_{a_{d}}=0$ | for each $a_{d}\in A_{D}$;
---|---
$\alpha_{b_{d}}=-1$ | for each $b_{d}\in B_{D}$;
$\alpha_{a_{v}^{0}}=1$ | for each $v\in V\setminus C$;
$\alpha_{b_{v}^{0}}=-1$ | for each $v\in V\setminus C$;
$\alpha_{a_{v}^{1}}=2$ | for each $v\in V\setminus C$;
$\alpha_{b_{v}^{1}}=-2$ | for each $v\in V\setminus C$;
$\alpha_{a_{v}^{i}}=0$ | for each $v\in C$ and $i\in\\{0,1\\}$;
$\alpha_{b_{v}^{i}}=-1$ | for each $v\in C$ and $i\in\\{0,1\\}$;
$\alpha_{a_{e}}=1$ | for each $e\in E\setminus(F^{1}\cup E[C])$;
$\alpha_{b_{e}}=0$ | for each $e\in E$;
$\alpha_{a_{e}}=2$ | for each $e\in F^{1}$;
$\alpha_{a_{e}}=0$ | for each $e\in E[C]$.

It is straightforward to check that $\vec{\alpha}$ is indeed a dual
certificate, that is, it satisfies the constraints of LP2. Since $\sum_{u\in
A\cup B}\alpha_{u}=k$, assignment $M$ indeed has unpopularity margin at most
$k$. ∎

We now show that any assignment in $G$ with unpopularity margin at most $k$
implies the existence of a cliquehog of size $k$ in $H$. We first establish a
useful assumption that we will show is without loss of generality. We say that
an assignment $M$ has a _nice structure_ , if for each $e\in E$ one of the
following cases holds true:

  * $\bullet$

$M(a_{e})=b_{e}$, or

  * $\bullet$

$M(a_{e})=b^{i}_{x}$ and $M(a^{i}_{x})=b_{e}$ for some endpoint $x$ of edge
$e$ in $H$ and $i\in\\{0,1\\}$, or

  * $\bullet$

$M(a_{e})\in B_{D}$ and $M(b_{e})\in A_{D}$.

###### Lemma 6

If there exists an assignment in $G$ with unpopularity margin at most $k$,
then there exists an assignment in $G$ with unpopularity margin at most $k$
that has a nice structure.

###### Proof

Let $M^{\prime}$ be any assignment in $G$. By switching the names of the
identical agents $a^{0}_{x}$ and $a^{1}_{x}$ wherever necessary, we can assume
that $M^{\prime}(a^{i}_{x})\in\\{b^{i}_{x}\\}\cup B_{E}$ for all $x\in V$ and
$i\in\\{0,1\\}$. We construct a new assignment $M$ as follows: For each $e\in
E$, let $M(a_{e})=M^{\prime}(a_{e})$. For each $x\in V$ and each
$i\in\\{0,1\\}$, if $M^{\prime}(b^{i}_{x})=a_{e}$ for some $e\in E$, then let
$M(a^{i}_{x})=b_{e}$; otherwise let $M(a^{i}_{x})=b^{i}_{x}$. Assign the
unmatched objects in $B_{E}$ arbitrarily to the dummy agents in $A_{D}$. Note
that for every agent $a\in A$, we have $M(a)=M^{\prime}(a)$ or $M(a)$ and
$M^{\prime}(a)$ are both in $B_{E}$. Since every agent is indifferent between
all her neighbors in $B_{E}$, the assignment $M$ has the same unpopularity
margin as $M^{\prime}$. ∎

In what follows, let $M$ be an assignment in $G$ with unpopularity margin at
most $k$ and a nice structure, and let $\vec{\alpha}$ be a dual certificate
for $M$. We will construct a cliquehog of size $k$ in $H$.

We define a partition $(E_{0},E_{1},E_{2})$ of those edges $e$ in $E$ for
which $M(a_{e})\notin B_{D}$. For any edge $e\in E$, we decide which set of
the partition $e$ belongs to using the following procedure.

  1. 1.

If $M(a_{e})=b_{e}$ and $\alpha_{a_{e}}+\alpha_{b_{e}}>0$, then we put $e$
into $E_{0}$.

  2. 2.

If $M(a_{e})=b_{e}$ and $\alpha_{a_{e}}+\alpha_{b_{e}}=0$, then we put $e$
into $E_{1}$.

  3. 3.

If $M(a_{e})$ is an object in $G_{x}$ or $G_{y}$ where $e=(x,y)$, then we put
$e$ into $E_{2}$.

We also define $S$ as the set of those vertices $v\in V$ for which the vertex
gadget $G_{v}$ contains an agent or object that is incident to an overloaded
edge of $M$. Note that since no agent in a vertex gadget is connected to an
object in another vertex gadget, and moreover, the overloaded edges of $M$
corresponding to edges in $E_{0}$ are not incident to any vertex gadget, we
know that

$|S|+|E_{0}|\leq\mu(M)\leq k.$ (2)

We will show that $(S,E_{2})$ is a cliquehog of size $k$. To do so, we first
establish two helpful lemmas. The first shows that $S$ contains all nodes
$x\in V$ for which at least one of the objects $b^{0}_{x}$ and $b^{1}_{x}$ is
matched to an edge agent. This implies that every edge in $E_{2}$ is incident
to a node in $S$. The second lemma shows that all endpoints of edges in
$E_{1}$ are contained in $S$.

###### Lemma 7

Let $x\in V$. If $M(b^{0}_{x})\in A_{E}$ or $M(b^{1}_{x})\in A_{E}$, then
$x\in S$.

###### Proof

We distinguish two cases. First, suppose that $M(b_{x}^{0})=a_{e}$ for some
$e\in E$. Recall that this implies $M(a^{0}_{x})=b_{e}$, because $M$ has a
nice structure. From the preferences of agents and the feasibility of
$\vec{\alpha}$, we get the three inequalities
$\alpha_{a^{0}_{x}}+\alpha_{b^{1}_{x}}\geq-1$ and
$\alpha_{M(b^{1}_{x})}+\alpha_{b^{0}_{x}}\geq 1$ and
$\alpha_{a_{e}}+\alpha_{b_{e}}\geq 1$. Adding these inequalities, we observe
that at least one of the sums $\alpha_{a^{0}_{x}}+\alpha_{b_{e}}$ or
$\alpha_{b^{1}_{x}}+\alpha_{M(b^{1}_{x})}$ or
$\alpha_{a_{e}}+\alpha_{b^{0}_{x}}$ must be positive, and thus the
corresponding edge in $M$ must be overloaded.

Second, suppose that $M(b^{0}_{x})\notin A_{E}$ but $M(b^{1}_{x})=a_{e}$ for
some $e\in E$. Recall that this implies $M(a^{0}_{x})=b^{0}_{x}$ and
$M(a^{1}_{x})=b_{e}$, because $M$ has a nice structure. Again from the
preferences of agents and the feasibility of $\vec{\alpha}$, we obtain the
three inequalities $\alpha_{a_{e}}+\alpha_{b_{x}^{0}}\geq 1$ and
$\alpha_{a_{x}^{0}}+\alpha_{b_{e}}\geq 1$ and
$\alpha_{a_{x}^{1}}+\alpha_{b_{x}^{1}}\geq-1$. Adding these inequalities, we
see that at least one of the sums $\alpha_{a_{e}}+\alpha_{b_{x}^{1}}$ or
$\alpha_{a_{x}^{0}}+\alpha_{b_{x}^{0}}$ or $\alpha_{a_{x}^{1}}+\alpha_{b_{e}}$
must be positive, and so the corresponding edge in $M$ must be overloaded. ∎

###### Lemma 8

If $e=(x,y)\in E_{1}$, then $\\{x,y\\}\subseteq S$.

###### Proof

We only show that $x\in S$. The proof for $y\in S$ follows by symmetry. If
$M(b^{0}_{x})\in A_{E}$ or $M(b^{1}_{x})\in A_{E}$, Lemma 7 implies that $x\in
S$. So we can assume that $M(b^{0}_{x})=a^{0}_{x}$ and
$M(b^{1}_{x})=a^{1}_{x}$ by the nice structure of $M$. By the preferences of
agents and feasibility of $\vec{\alpha}$, we obtain the three inequalities
$\alpha_{a^{0}_{x}}+\alpha_{b_{e}}\geq 1$ and
$\alpha_{a^{1}_{x}}+\alpha_{b^{0}_{x}}\geq 1$ and
$\alpha_{a_{e}}+\alpha_{b^{1}_{x}}\geq-1$. Adding up these inequalities, we
observe that at least one of the sums $\alpha_{a^{0}_{x}}+\alpha_{b^{0}_{x}}$
or $\alpha_{a^{1}_{x}}+\alpha_{b^{1}_{x}}$ or $\alpha_{a_{e}}+\alpha_{b_{e}}$
must be positive. By $e\in E_{1}$, the third expression is equal to $0$, and
so one of the former two has to be positive. This implies that at least one of
the two corresponding edges of $M$ in $G_{x}$ is overloaded. ∎

We are now ready to prove Lemma 9, which together with Lemma 5 proves Theorem
1.3.

###### Lemma 9

If the constructed instance $G$ admits an assignment $M$ with unpopularity
margin at most $k$, then $H$ contains a cliquehog of size $k$.

###### Proof

By Lemma 8 we know that any edge $e\in E_{1}$ must have both of its endpoints
in $S$, yielding

$|E_{1}|\leq\binom{|S|}{2}.$ (3)

By Lemma 7, each edge $e\in E_{2}$ must have its agent $a_{e}$ assigned to an
object in a vertex gadget $G_{v}$ for some $v\in S$. By Inequality (2) there
are at most $2|S|$ such objects, so we obtain

$|E_{2}|\leq 2|S|.$ (4)

Recall that by construction of $G$ and the definition of the partition
$(E_{0},E_{1},E_{2})$, we know

$\displaystyle\binom{k}{2}+2k=|E|-|B_{D}|=|E_{1}|+|E_{2}|+|E_{0}|\leq\binom{|S|}{2}+|S|+k$

where the inequality follows from combining Inequalities (2), (3), and (4).
Hence, by $|S|\leq k$ we obtain $|S|=k$. Moreover, every inequality we used
must hold with equality. In particular, this implies $|E_{1}|=\binom{k}{2}$,
which can only happen if there are $\binom{k}{2}$ edges in $H$ (namely, those
in $E_{1}$) with both of their endpoints in $S$. In other words, $S$ forms a
clique in $H$. Additionally, (4) must also hold with equality, so
$|E_{2}|=2|S|=2k$. Since every edge in $E_{2}$ is incident to a vertex of $S$
by Lemma 7, but is not contained in $E[S]$ (because $E[S]=E_{1}\subseteq
E\setminus E_{2}$), and any $x\in S$ is incident to at most two edges of
$E_{2}$ (by the definition of $E_{2}$), we can conclude that $(S,E_{2})$ is a
cliquehog of size $k$. ∎

In order to prove the second part of Theorem 1.3, we show in Lemma 10 a
reduction from weak rankings to strict for the $k$-unpopularity margin
problem. The proof of Lemma 10 is given in the appendix.

######  Lemma 10 ()

Let $G$ be an instance with weak rankings and $n$ agents. Then we can compute
in polynomial time an instance $G^{\prime}$ with strict rankings and an
integer $q\in\mathcal{O}(n)$ such that $G$ admits an assignment with
unpopularity margin $k$ if and only if $G^{\prime}$ admits an assignment with
unpopularity margin $k+q$ for any $k\in[n]$.

This completes the proof of Theorem 1.3.

##  7 Popular allocations in housing markets

A housing market, as introduced by Shapley and Scarf in their seminal paper
[28], models a situation where agents are initially endowed with one unit of
an indivisible good, called a house, and agents may trade their houses
according to their preferences without using monetary transfers. In such
markets, trading results in a reallocation of houses in a way that each agent
ends up with exactly one house.

Let $A$ denote the set of agents, and let $\omega(a)$ denote the house of
agent $a\in A$; note that agents do not share houses, so
$\omega(a)\neq\omega(a^{\prime})$ whenever $a\neq a^{\prime}$. The classic
representation of a _housing market_ over $A$ is a directed graph $D=(A,F)$
where each agent $a\in A$ has preferences over the arcs leaving $a$ in $D$. In
this model, an arc $(a,a^{\prime})\in F$ means that $a$ prefers
$\omega(a^{\prime})$ to her own house (i.e., $\omega(a)$), and is therefore
willing to participate in a trade where she obtains $\omega(a^{\prime})$.
Thus, preferences over the arcs leaving $a$ describe her preferences of the
houses she finds acceptable (i.e., prefers to her own). An _allocation_ in a
housing market $D=(A,F)$ is a set $S\subseteq F$ of edges that form disjoint
cycles in $D$ called _trading cycles_. An agent _trades_ in $S$ if it is
covered by a trading cycle of $S$.

The solution concept used by Shapley and Scarf is the so-called _core_ [28],
but there have been several other stability notions studied in the literature
on housing markets. We may consider popularity as an alternative concept, with
a straightforward interpretation as follows. Given allocations $S$ and
$S^{\prime}$ in $D$, some agent $a\in A$ _prefers_ $S$ to $S^{\prime}$, if
either $S$ covers $a$ but $S^{\prime}$ does not, or $(a,a_{1})\in S$,
$(a,a_{2})\in S^{\prime}$ and $a$ prefers $\omega(a_{1})$ to $\omega(a_{2})$.
We say that $S$ is _more popular than $S^{\prime}$_, if the number of agents
preferring $S$ to $S^{\prime}$ is more than the number of agents preferring
$S^{\prime}$ to $S$. An allocation $S$ is _popular_ in $D$, if there is no
allocation in $D$ that is more popular than $S$. A natural question is the
following: can we find a popular allocation in a given housing market
efficiently?

###  7.1 Popular allocations in a housing market: reduction to popular
assignment

We propose a reduction from the problem of finding a popular allocation in a
housing market to the problem of finding a popular assignment in a bipartite
graph. The main idea of the reduction is to associate a bipartite graph
$G_{D}$ with a given housing market $D=(A,F)$ as follows. We define the graph
$G_{D}=(A\cup B,E)$ where objects are houses, i.e., $B=\\{\omega(a):a\in
A\\}$, and the edge set is $E=\\{(a,\omega(a^{\prime})):(a,a^{\prime})\in
F)\\}\cup\\{(a,\omega(a)):a\in A\\}$. Thus, each arc $(a,a^{\prime})\in F$
corresponds to an edge $(a,\omega(a^{\prime}))$ in $E$, and we also add an
edge $(a,\omega(a))$ for each agent $a\in A$, corresponding to the possibility
of $a$ staying in her own house. Preferences of an agent $a$ over her outgoing
arcs in $D$ naturally yield her preferences in $G_{D}$ over objects in
$\mathsf{Nbr}_{G_{D}}(a)\setminus\\{\omega(a)\\}$, while $\omega(a)$ is the
unique worst-choice object of $a$.

Observe that there is a one-to-one correspondence between allocations in $D$
and assignments in $G_{D}$ that preserves the preferences of any agent: an
allocation $S$ in $D$ corresponds to an assignment
$M_{S}=\\{(a,\omega(a^{\prime})):(a,a^{\prime})\in S\\}\cup\\{(a,\omega(a)):a$
does not trade in $S\\}$; note that this indeed yields a bijection. It is easy
to see that an allocation $S$ is popular in $D$ if and only if $M_{S}$ is a
popular assignment in $G_{D}$. Hence, we can find a popular allocation in a
housing market $D$ by using Algorithm 1 to find a popular assignment in
$G_{D}$; thus the following is a corollary to Theorem 1.1.

###### Corollary 2

For any housing market $D=(A,F)$ on $n$ nodes and $m$ arcs where each agent
has preferences over her outgoing arcs, we can decide in time $O((m+n)\cdot
n^{5/2})$ whether $D$ admits a popular allocation or not, and if so, find one.

###  7.2 Maximum-size popular allocation in a housing market

Given the above positive result (Corollary 2), an interesting question is
whether it is possible to find a maximum-size popular allocation in a housing
market $D=(A,F)$, where the _size_ of an allocation $S$ in $D$ is $|S|$, that
is, the number of agents trading in $S$. A natural approach for finding a
maximum-size popular allocation in $D$ would be to assign cost $1$ to the edge
$(a,\omega(a))$ for each $a\in A$ in $G_{D}$, assign cost $0$ to all remaining
edges of $G_{D}$, and ask for a minimum-cost popular assignment in $G_{D}$.
However, as we prove in Theorem 7.1, finding a popular allocation of maximum
size in a housing market is $\mathsf{NP}$-hard; by the above reasoning, this
implies that finding a minimum-cost popular assignment in the classic setting
of the popular assignment problem is also $\mathsf{NP}$-hard, even for binary
costs. Thus, Theorem 1.4 is a corollary of Theorem 7.1.

###### Theorem 7.1

The minimum-cost popular assignment problem is $\mathsf{NP}$-hard, even if
agents’ preferences are strict, the input graph $G_{D}$ corresponds to a
housing market $D=(A,F)$ where edges in $\\{(a,\omega(a)):a\in A\\}$,
corresponding to initial endowments in $D$, have cost 1, while all remaining
edges have cost 0.

###### Proof

We present a reduction from the Vertex Cover problem, whose input is a graph
$H=(V,E)$ and an integer $k$, and asks whether there exists a set $S$ of at
most $k$ vertices in $H$ such that each edge of $E$ has one of its endpoints
in $S$. We will construct an equivalent instance of the minimum-cost popular
assignment problem. We assume an arbitrary, fixed ordering on the vertices of
$H$, which allows us to represent each edge in $E$ as an ordered pair
$(x,y)\in E$; this implicit ordering will be relevant in our construction.

##### Gadgets.

We begin by defining two types of gadgets. A _gadget_ $G_{\gamma}$ of size
$s\in\mathbb{N}$ contains agents $a_{\gamma}^{i}$ and objects $b_{\gamma}^{i}$
for each $i\in\\{0,1,\dots,6s-1\\}$. Superscripts of these agents and objects
are always taken modulo $6s$, in particular, we set
$a_{\gamma}^{6s}=a_{\gamma}^{0}$ and $b_{\gamma}^{6s}=b_{\gamma}^{0}$. We let
$A_{\gamma}=\\{a_{\gamma}^{i}:i\in[6s]\\}$ and
$B_{\gamma}=\\{b_{\gamma}^{i}:i\in[6s]\\}$.

Preferences of agents in $A_{\gamma}$ depend on the type of the gadget; see
Fig. 4. If $G_{\gamma}$ is a _type-0 gadget_ , then agents in $A_{\gamma}$
have preferences as follows.

$a_{\gamma}^{i}:$ | $b_{\gamma}^{i}\succ b_{\gamma}^{i+1}$ | for each $i\in\\{0,1,\dots,3s-1\\}$;
---|---|---
$a_{\gamma}^{i}:$ | $b_{\gamma}^{i+1}\succ b_{\gamma}^{i}$ | for each $i\in[6s-1]\setminus[3s-1]$ where $i\not\equiv 0\mod 3$;
$a_{\gamma}^{i}:$ | $b_{\gamma}^{i+1}\succ b_{\gamma}^{i}\succ b_{\gamma}^{i+3}$ | for each $i\in[6s-1]\setminus[3s-1]$ where $i\equiv 0\mod 3$.

Figure 4: An illustration of type-0 and type-1 gadgets constructed in the
proof of Theorem 7.1. Edges leading from an agent to its worst-choice object
are shown in red.

By contrast, if $G_{\gamma}$ is a _type-1 gadget_ , then its agents have the
following preferences.

$a_{\gamma}^{i}:$ | $b_{\gamma}^{i}\succ b_{\gamma}^{i+1}$ | for each $i\in\\{0,1,\dots,3s-1\\}$ where $i\not\equiv 2\mod 3$;
---|---|---
$a_{\gamma}^{i}:$ | $b_{\gamma}^{i}\succ b_{\gamma}^{i+1}\succ b_{\gamma}^{i-2}$ | for each $i\in\\{0,1,\dots,3s-1\\}$ where $i\equiv 2\mod 3$;
$a_{\gamma}^{i}:$ | $b_{\gamma}^{i+1}\succ b_{\gamma}^{i}$ | for each $i\in[6s-1]\setminus[3s-1]$.

Furthermore, we define two disjoint matchings in gadget $G_{\gamma}$, namely
$M_{\gamma}^{0}=\\{(a_{\gamma}^{i},b_{\gamma}^{i}):i\in[6s]\\}$ and
$M_{\gamma}^{1}=\\{(a_{\gamma}^{i},b_{\gamma}^{i+1}):i\in[6s]\\}$.

Notice that the edge set $\\{(a,\omega(a)):a\in A_{\gamma}\\}$ leading from
the agents to their worst-choice objects forms a perfect matching within the
gadget. In our construction, we will assign a cost of 1 for such edges,
setting all remaining edge costs as 0. This gives rise to the following
important difference between type-0 and type-1 gadgets: for a type-0 gadget
$G_{\gamma}$ of size $s$, the cost of $M_{\gamma}^{0}$ is $2s$, while the cost
of $M_{\gamma}^{1}$ is $3s$. By contrast, for a type-1 gadget $G_{\gamma}$ of
size $s$, the matching $M_{\gamma}^{0}$ has cost $3s$, while $M_{\gamma}^{1}$
has cost $2s$. In fact, the sole purpose of the differences between the two
types of gadgets is to make $M_{\gamma}^{0}$ “cheap” and $M_{\gamma}^{1}$
“expensive” in a type-0 gadget, and the other way around in a type-1 gadget.

##### Construction.

Let us set $n_{v}=3|E|+1$ and $n_{\ell}=(3|V|+1)n_{v}$; it will be sufficient
for the reader to keep $n_{\ell}\gg n_{v}\gg|E|$ in mind. We are now ready to
define the set $A$ of agents and the set $B$ of objects by creating the
following:

  * •

a type-0 gadget $G_{\ell}$ of size $n_{\ell}$ called the _level-setting
gadget_ ,

  * •

for each $e\in E$ a type-0 gadget $G_{e}$ of size $1$ called an _edge gadget_
, and

  * •

for each $x\in V$ a type-1 gadget $G_{x}$ of size $n_{v}$ called a _vertex
gadget_.

Additionally, we introduce a set $F$ of _inter-gadget edges_ ; see Fig. 5 for
an illustration. First, in order to enforce certain lower bounds on the dual
certificate, we connect some agents and objects in the level-setting gadget
with those in the vertex and edge gadgets, by adding the edges of

$F_{\textup{bnd}}=\\{(a_{x}^{-3},b_{\ell}^{-2}):x\in
V\\}\cup\\{(a_{e}^{2},b_{\ell}^{-3}),(a_{e}^{4},b_{\ell}^{-2}),(a_{\ell}^{-3},b_{e}^{4}):e\in
E\\}.$ (5)

Second, we encode the incidence relation in $H$ into our instance by adding
the edges of

$F_{\textup{inc}}=\\{(a_{e}^{2},b_{x}^{-3}),(a_{e}^{3},b_{y}^{-3}):e=(x,y)\in
E\\}$ (6)

between edge and vertex gadgets. We define the set of all inter-gadget edges
as $F=F_{\textup{bnd}}\cup F_{\textup{inc}}$. Note that the edges of $F$
indeed run between different gadgets.

Preferences of agents incident to inter-gadget edges are given below; all
remaining agents have preferences as given in the definition of a type-0 or
type-1 gadget. Again, for a set $X$ of objects, we write $[X]$ in an agent’s
preference list to denote an arbitrarily ordered list containing objects in
$X$.

$a_{\ell}^{-3}:$ |  $b_{\ell}^{-2}\succ b_{\ell}^{-3}\succ[\\{b_{e}^{4}:e\in E\\}]\succ b_{\ell}^{0}$; |
---|---|---
$a_{e}^{2}:$ | $b_{\ell}^{-3}\succ b_{x}^{-3}\succ b_{e}^{2}\succ b_{e}^{3}$ | for each $e=(x,y)\in E$;
$a_{e}^{3}:$ | $b_{y}^{-3}\succ b_{e}^{4}\succ b_{e}^{3}\succ b_{e}^{0}$ | for each $e=(x,y)\in E$;
$a_{e}^{4}:$ | $b_{\ell}^{-2}\succ b_{e}^{5}\succ b_{e}^{4}$ | for each $e=(x,y)\in E$;
$a_{x}^{-3}:$ | $b_{\ell}^{-2}\succ b_{x}^{-2}\succ b_{x}^{-3}$ | for each $x\in V$.

Note that the introduction of inter-gadget edges did not change the worst-
choice object of any agent. As a consequence, the edge set
$\\{(a,\omega(a)):a\in A\\}$ forms a perfect matching in the resulting graph
$G$, and therefore $G$ indeed corresponds to a housing market as promised.

Figure 5: An illustration of the construction in the proof of Theorem 7.1. The
figure assumes $e=(x,y)\in E$. Again, worst-choice edges are shown in red,
while inter-gadget edges are depicted in blue.

We set the cost of all edges in $\\{(a,\omega(a)):a\in A\\}$ as $1$. All
remaining edges have cost $0$, and we set
$\beta=2n_{\ell}+3kn_{v}+(|V|-k)2n_{v}+3|E|$ as our budget. This finishes the
definition of our instance.

##### Direction “$\Rightarrow$”.

To prove the correctness of our reduction, first we will show that the
existence of a popular assignment $M$ of cost at most $\beta$ in $G$ implies a
vertex cover of size at most $k$ in $H$. Let us make some basic observations
about the structure of $M$.

##### Excluding inter-gadget edges.

We claim that $M$ does not contain any inter-gadget edges. To prove this, we
first show that $(a_{\ell}^{-2},b_{\ell}^{-2})\in M$. For any index
$i\in\\{-2,-1,0,\dots,3n_{\ell}-1\\}$, agent $a_{\ell}^{i}$ can be assigned
either $b_{\ell}^{i}$ or $b_{\ell}^{i+1}$. Using that $M$ assigns an object to
every agent, we immediately get that if $(a_{\ell}^{-2},b_{\ell}^{-2})\notin
M$, then $M$ must contain all edges $(a_{\ell}^{i},b_{\ell}^{i+1})$ for
$i\in\\{-2,-1,0,1,\dots,3n_{\ell}-1\\}$. However, these edges have total cost
$3n_{\ell}$ which by our choice of $n_{\ell}$ exceeds the budget $\beta$.
Hence, $M$ contains $(a_{\ell}^{-2},b_{\ell}^{-2})$. In particular, this shows
that agents in a vertex gadget $G_{x}$ can only be assigned by $M$ an object
within the same gadget. Thus, all objects within vertex gadgets must be
assigned to agents within vertex gadgets, implying that no edge of $F$
incident to a vertex gadget may be contained in $M$.

To prove our claim, it remains to show that $M$ does not contain any edge
connecting the level-setting gadget with an edge gadget. Assume otherwise for
the sake of contradiction. Recall that only $a_{\ell}^{-3}$ and
$b_{\ell}^{-3}$ may be incident to an edge of $M\cap F$ among all agents and
objects in $G_{\ell}$. Thus, it follows that $M$ must contain both
$(a_{\ell}^{-3},b_{e}^{4})$ and $(a_{e}^{2},b_{\ell}^{-3})$ for some $e\in E$.
(Observe that here we used the fact that no edge leaving a vertex gadget may
be in $M$.) From this we also get $(a_{e}^{3},b_{e}^{3})\in M$. We can then
define a matching $M^{\prime}$ by replacing these three edges with the edges
$(a_{\ell}^{-3},b_{\ell}^{-3})$, $(a_{e}^{2},b_{e}^{3})$ and
$(a_{e}^{3},b_{e}^{4})$. Observe that $M^{\prime}$ is more popular than $M$,
since both $a_{e}^{3}$ and $a_{\ell}^{-3}$ prefer $M^{\prime}$ to $M$; a
contradiction to the popularity of $M$. Hence, we have established that $M\cap
F=\emptyset$.

##### Assignment $M$ on the level-setting gadget.

We show that
$M_{\ell}^{0}=\\{(a_{\ell}^{i},b_{\ell}^{i}):i\in[6n_{\ell}]\\}\subseteq M$.
To this end, we first prove that $M$ does not contain any of the edges
$(a_{\ell}^{i},b_{\ell}^{i+3})$ where $i\in[6n_{\ell}]$ and $i\equiv 0\mod 3$.
Suppose $(a_{\ell}^{i},b_{\ell}^{i+3})\in M$ for the sake of contradiction.
Then $(a_{\ell}^{i+2},b_{\ell}^{i+2})\in M$ and
$(a_{\ell}^{i+1},b_{\ell}^{i+1})\in M$ follows. However, we can now define an
assignment $M^{\prime}$ by deleting these three edges from $M$ and adding the
edges $(a_{\ell}^{i},b_{\ell}^{i+1})$, $(a_{\ell}^{i+1},b_{\ell}^{i+2})$, and
$(a_{\ell}^{i+2},b_{\ell}^{i+3})$ instead. Notice that all three agents
$a_{\ell}^{i}$, $a_{\ell}^{i+1}$, and $a_{\ell}^{i+2}$ prefer $M^{\prime}$
over $M$, contradicting our assumption that $M$ is popular.

Together with $M\cap F=\emptyset$, this implies that
$M(a_{\ell}^{i})\in\\{b_{\ell}^{i},b_{\ell}^{i+1}\\}$ for each
$i\in[6n_{\ell}]$. Recall that we already know
$(a_{\ell}^{-2},b_{\ell}^{-2})\in M$, which yields $M_{\ell}^{0}\subseteq M$.

##### Edge and vertex gadget: a binary choice for $M$.

Consider some edge gadget $G_{e}$. Since $M$ does not contain any inter-gadget
edges, we can argue that $M$ does not contain the edge
$(a_{e}^{3},b_{e}^{0})$: indeed, supposing $(a_{e}^{3},b_{e}^{0})\in M$ would
imply $\\{(a_{e}^{4},b_{e}^{4}),(a_{e}^{5},b_{e}^{5})\\}\subseteq M$; however,
replacing these edges by $\\{(a_{e}^{i},b_{e}^{i+1}):i=3,4,5\\}$ yields a
matching more popular than $M$, a contradiction. Hence, $M$ contains either
$M_{e}^{0}$ or $M_{e}^{1}$.

Analogously, we can show that $M$ contains no edge of the form
$(a_{x}^{i},a_{x}^{i-2})$ in a vertex gadget $G_{x}$: indeed,
$(a_{x}^{i},b_{x}^{i-2})\in M$ would imply
$\\{(a_{x}^{i-2},b_{x}^{i-1}),(a_{x}^{i-1},b_{x}^{i})\\}\subseteq M$; however,
replacing these edges by $\\{(a_{e}^{j},b_{e}^{j}):j=i-2,i-1,i\\}$ yields a
matching more popular than $M$, a contradiction. Hence, $M$ contains either
$M_{x}^{0}$ or $M_{x}^{1}$.

##### Properties of a dual certificate.

Let $M$ admit a dual certificate $\vec{\alpha}$, and consider some gadget
$G_{\gamma}$ in $G$ of size $s$. Recall that for each $(a,b)\in M$
complementary slackness for LP2 implies that
$\alpha_{a}+\alpha_{b}=\mathsf{wt}_{M}(a,b)=0$. Thus, either
$\alpha_{a_{\gamma}^{i}}=-\alpha_{b_{\gamma}^{i}}$ for each $i\in[s]$, or
$\alpha_{a_{\gamma}^{i}}=-\alpha_{b_{\gamma}^{i+1}}$ for each $i\in[s]$.
Furthermore, let $\overline{M}_{\gamma}$ denote the matching
$(M_{\gamma}^{0}\cup M_{\gamma}^{1})\setminus M$ (that is,
$\overline{M}_{\gamma}=M_{\gamma}^{1}$ if $M_{\gamma}^{0}\subseteq M$ and
$\overline{M}_{\gamma}=M_{\gamma}^{0}$ otherwise). Observe that half of the
edges in $\overline{M}_{\gamma}$ have weight $+1$ and half of them have weight
$-1$ according to $\mathsf{wt}_{M}(\cdot)$, since exactly half of the agents
in $G_{\gamma}$ prefer $M_{\gamma}^{0}$ to $M_{\gamma}^{1}$, while the other
half prefer $M_{\gamma}^{1}$ to $M_{\gamma}^{0}$. Hence, using the feasibility
of the dual certificate $\vec{\alpha}$, we get

$\displaystyle 0=$ $\displaystyle\sum_{a\in
A_{\gamma}}\alpha_{a}+\alpha_{M(a)}=\sum_{a\in
A_{\gamma}}\alpha_{a}+\sum_{b\in B_{\gamma}}\alpha_{b}$ $\displaystyle=$
$\displaystyle\sum_{a\in
A_{\gamma}}\alpha_{a}+\alpha_{\overline{M}_{\gamma}(a)}\geq|A_{\gamma}|/2\cdot
1+|A_{\gamma}|/2\cdot(-1)=0$

where the first equality holds because $\alpha_{a}+\alpha_{b}=0$ for each edge
$(a,b)\in M$. Thus, it follows that
$\alpha_{a}+\alpha_{b}=\mathsf{wt}_{M}(a,b)$ must hold for each edge
$(a,b)\in\overline{M}_{\gamma}$ as well. From this we get

$\displaystyle\alpha_{b_{\gamma}^{i+1}}$ $\displaystyle=$
$\displaystyle\alpha_{b_{\gamma}^{i+1}}+\alpha_{a_{\gamma}^{i}}-\alpha_{a_{\gamma}^{i}}-\alpha_{b_{\gamma}^{i}}+\alpha_{b_{\gamma}^{i}}=\mathsf{wt}_{M}(a_{\gamma}^{i},b_{\gamma}^{i+1})-\mathsf{wt}_{M}(a_{\gamma}^{i},b_{\gamma}^{i})+\alpha_{b_{\gamma}^{i}}$
(9) $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}\alpha_{b_{\gamma}^{i}}-1,&\textrm{\hskip
20.0ptif $i\in\\{0,1,\dots,3s-1\\}$,}\\\
\alpha_{b_{\gamma}^{i}}+1,&\textrm{\hskip 20.0ptif
$i\in[6s-1]\setminus[3s-1]$,}\\\ \end{array}\right.$

irrespectively of the type of gadget $G_{\gamma}$. In particular, this implies

$\alpha_{b_{\gamma}^{i}}=\alpha_{b_{\gamma}^{-i}}$ (10)

for each $i\in[3s]$.

Note that w.l.o.g. we can assume that $\alpha_{b_{\ell}^{0}}=0$, as otherwise
we can decrease the value of $\alpha_{b}$ for all objects $b$ by
$\alpha_{b_{\ell}^{0}}$ and increase $\alpha_{a}$ by the same amount for each
agent $a$. Therefore, (9) yields

$\alpha_{b_{\ell}^{-3}}=-3,\quad\alpha_{b_{\ell}^{-2}}=-2,\quad\alpha_{a_{\ell}^{-3}}=3$
(11)

where the last equality follows from $(a_{\ell}^{-3},b_{\ell}^{-3})\in M$.

##### Defining a vertex cover.

We are going to define a set $S\subseteq V$, and show that $S$ is a vertex
cover in $H$ of size at most $k$. Namely, let $S$ contain exactly those
vertices $x\in V$ for which $M_{x}^{0}\subseteq M$. Note that since $G_{x}$ is
a type-1 gadget of size $n_{v}$ for each $x\in V$, the cost of all edges of
$M$ within $G_{x}$ is either $3n_{v}$ (if $x\in S$) or $2n_{v}$ (if $x\notin
S$). Since the cost of $M_{\ell}^{0}\subseteq M$ is $2n_{\ell}$, and by our
choice of $n_{v}$ we have
$\beta+n_{v}-3|E|=2n_{\ell}+(k+1)3n_{v}+(|V|-k-1)2n_{v}<\beta$, our budget
implies $|S|\leq k$. It remains to show that $S$ is indeed a vertex cover.

To this end, consider now the edges in $F_{\textup{bnd}}$. Observe that
$\mathsf{wt}_{M}(a_{e}^{2},b_{\ell}^{-3})=1$,
$\mathsf{wt}_{M}(a_{e}^{4},b_{\ell}^{-2})=1$ and
$\mathsf{wt}_{M}(a_{\ell}^{-3},b_{e}^{4})=-1$ for any $e\in E$. Using (11)
this implies

$\alpha_{a_{e}^{2}}\geq 4,\quad\alpha_{a_{e}^{4}}\geq
3,\quad\alpha_{b_{e}^{4}}\geq-4.$ (12)

By (10) we also have $\alpha_{b_{e}^{2}}=\alpha_{b_{e}^{4}}$. Let us
distinguish between two cases: (i) first, if $M_{e}^{0}\subseteq M$, then
$\alpha_{a_{e}^{2}}+\alpha_{b_{e}^{2}}=\mathsf{wt}_{M}(a_{e}^{2},b_{e}^{2})=0$,
which by (12) implies $\alpha_{b_{e}^{2}}\leq-4$; (ii) second, if
$M_{e}^{1}\subseteq M$, then
$\alpha_{a_{e}^{4}}+\alpha_{b_{e}^{4}}=\mathsf{wt}_{M}(a_{e}^{4},b_{e}^{4})=-1$,
which by (12) implies $\alpha_{b_{e}^{4}}\leq-4$. Hence, in either case we
obtain $\alpha_{b_{e}^{2}}=\alpha_{b_{e}^{4}}=-4$ by (12). This leads us to
the following important facts:

if $M_{e}^{0}\subseteq M$, then $\displaystyle\\!\\!\ \alpha_{a_{e}^{2}}=4;$
(13) if $M_{e}^{1}\subseteq M$, then $\displaystyle\\!\\!\
\alpha_{a_{e}^{3}}=4.$ (14)

Now, consider the edges incident to some vertex gadget $G_{x}$. First,
$\mathsf{wt}_{M}(a_{x}^{-3},b_{\ell}^{-2})=1$ implies $\alpha_{a_{x}^{-3}}\geq
3$ by the equations in (11). From (9) it follows that

$\textrm{if $M_{x}^{1}\subseteq M$, then
}\alpha_{b_{x}^{-3}}=\alpha_{b_{x}^{-2}}-1=\alpha_{M(a_{x}^{-3})}-1=-\alpha_{a_{x}^{-3}}-1\leq-4.$
(15)

We are now ready to show that $S$ is indeed a vertex cover in $H$. Let
$e=(x,y)\in E$ be an edge in $H$. First, if $M_{e}^{0}\subseteq M$, then
$\mathsf{wt}_{M}(a_{e}^{2},b_{x}^{-3})=1$ together with (13) implies
$\alpha_{b_{x}^{-3}}\geq-3$. Hence, by (15) we must have
$M_{x}^{1}\not\subseteq M$, yielding $x\in S$. Second, if $M_{e}^{1}\subseteq
M$, then $\mathsf{wt}_{M}(a_{e}^{3},b_{y}^{-3})=1$ together with (14) implies
$\alpha_{b_{y}^{-3}}\geq-3$. By (15) applied to gadget $G_{y}$ we obtain
$M_{y}^{1}\not\subseteq M$, yielding $y\in S$. Thus, we can conclude that
either $x\in S$ or $y\in S$, proving our claim.

##### Direction “$\Leftarrow$”.

For the other direction, given a vertex cover $S\subseteq V$ of size at most
$k$ in $H$, we will show that a popular assignment $M$ of total cost at most
$\beta$ exists in $G$. For each edge $e\in E$, let us fix one of its endpoints
in $S$, and denote it by $\tau(e)$. We may define $M$ as follows:

$M=M_{\ell}^{0}\cup\left(\bigcup_{x\in
S}M_{x}^{0}\right)\cup\left(\bigcup_{x\in V\setminus
S}M_{x}^{1}\right)\cup\left(\bigcup_{\begin{subarray}{c}e=(x,y)\in E,\\\
\tau(e)=x\end{subarray}}M_{e}^{0}\right)\cup\left(\bigcup_{\begin{subarray}{c}e=(x,y)\in
E,\\\ \tau(e)=y\end{subarray}}M_{e}^{1}\right).$

Figure 6: An illustration of a popular assignment for the instance $G$
constructed in the proof of Theorem 7.1, given a vertex cover $S$. The figure
assumes $e=(x,y)\in E$ with $x\notin S$ and $y\in S$. Edges contained in $M$
are depicted in bold. The values of a dual certificate $\vec{\alpha}$ for $M$
are indicated within the corresponding agent or object.

It is clear that $M$ indeed has total cost at most $\beta$: the cost of
$M_{\ell}^{0}$ is $2n_{\ell}$, the cost of $\bigcup_{x\in S}M_{x}^{0}$ is
$3kn_{v}$, the cost of $\bigcup_{x\in V\setminus S}M_{x}^{1}$ is
$2(|V|-k)n_{v}$, while the cost of all edges of $M$ within edge gadgets is at
most $3|E|$. To show that $M$ is popular, we define a dual certificate
$\vec{\alpha}$ for $M$ by defining $\alpha_{b}$ for each object $b\in B$ as
follows; we set $\alpha_{a}=-\alpha_{M(a)}$ for each agent $a\in A$. See Fig.
6 for an illustration.

$\alpha_{b_{\ell}^{i}}=-|i|$ | for each $i\in\\{-3n_{\ell}+1,\dots,-1,0,1,\dots,3n_{\ell}\\}$;
---|---
$\alpha_{b_{x}^{i}}=-|i|$ | for each $x\in S$ and $i\in\\{-3n_{v}+1,\dots,-1,0,1,\dots,3n_{v}\\}$;
$\alpha_{b_{x}^{i}}=-|i|-1$ | for each $x\in V\setminus S$ and $i\in\\{-3n_{v}+1,\dots,-1,0,1,\dots,3n_{v}\\}$;
$\alpha_{b_{e}^{i}}=-|i|-2$ | for each $e\in E$ and $i\in\\{-2,-1,0,1,2,3\\}$;

This finishes the proof of the theorem. ∎

##  8 Open problems

We proposed a polynomial-time algorithm for computing a popular assignment in
an instance $G=(A\cup B,E)$ with one-sided preferences, if one exists. Our
algorithm solves $O(n^{2})$ instances of the maximum matching problem in
certain subgraphs of $G$ (where $|A|=|B|=n$) and it is easy to show instances
where our algorithm indeed solves $\Theta(n^{2})$ instances of the maximum
matching problem. The running time of our algorithm is $O(m\cdot n^{5/2})$
(where $|E|=m$) and by using the almost-linear time algorithm for maximum flow
[6] to solve the bipartite maximum matching problem, we can get a faster
randomized algorithm for the popular assignment problem. Can we show faster
deterministic or randomized algorithms for the popular assignment problem by
solving $o(n^{2})$ instances of the maximum matching problem or via some other
approach?

Another open problem is the computational complexity of the minimum-cost
popular matching problem when agents’ preferences are partial orders. For weak
rankings, a polynomial-time algorithm for this problem follows from the
combinatorial characterization of popular matchings given in [2]. However as
illustrated in an example in Section 2.1, this characterization does not hold
for partial order preferences. So the computational complexity of the minimum-
cost popular matching problem for partial order preferences is open.

One more open problem is to show a short witness that a given instance $G$
does not admit a popular assignment. Rather than run our algorithm and
discover that $G$ has no popular assignment, is there a forbidden structure
that causes $G$ not to admit a popular assignment? Can we characterize
instances that admit popular assignments? Interestingly, such a result is
known for the stable roommates problem [30]; recall our discussion in Section
1 on the similarity between results for the popular assignment problem and the
stable roommates problem.

Our $\mathsf{W}_{l}[1]$-hardness proof for the $k$-unpopularity margin problem
with parameter $k$ needs weak rankings. We are able to show that this problem
remains $\mathsf{NP}$-hard for strict rankings (Lemma 10). However, the
parameterized complexity of this case is still open: is the $k$-unpopularity
margin problem in FPT with parameter $k$, if agents’ preferences are strict
rankings?

## Acknowledgments

Telikepalli Kavitha is supported by the DAE, Government of India, under
project no. RTI4001. Tamás Király is supported by the Ministry of Innovation
and Technology of Hungary from the National Research, Development and
Innovation Fund, financed under the ELTE TKP 2021-NKTA-62 funding scheme.
Jannik Matuschke is supported by internal funds of KU Leuven. Ildikó Schlotter
is supported by the Hungarian Academy of Sciences under its Momentum Programme
(LP2021-2) and its János Bolyai Research Scholarship, and by the Hungarian
Scientific Research Fund (OTKA grant K124171). Ulrike Schmidt-Kraepelin was
supported by the Deutsche Forschungsgemeinschaft (DFG) under grant BR 4744/2-1
while affiliated with TU Berlin, and the _National Science Foundation (NSF)_
under Grant No. DMS-1928930 and by the Alfred P. Sloan Foundation under grant
G-2021-16778, while she was in residence at the Simons Laufer Mathematical
Sciences Institute (formerly MSRI) in Berkeley, California, during the Fall
2023 semester.

## References

  * [1] A. Abdulkadiroglu and T. Sönmez.  Random serial dictatorship and the core from random endowments in house allocation problems.  Econometrica, 66:689–701, 1998.
  * [2] D. J. Abraham, R. W. Irving, T. Kavitha, and K. Mehlhorn.  Popular matchings.  SIAM Journal on Computing, 37(4):1030–1045, 2007.
  * [3] N. Benabbou, M. Chakraborty, X.-V. Ho, J. Sliwinski, and Y. Zick.  Diversity constraints in public housing allocation.  In AAMAS 2018: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 973–981, 2018.
  * [4] P. Biró, D. F. Manlove, and S. Mittal.  Size versus stability in the marriage problem.  Theoretical Computer Science, 411:1828–1841, 2010.
  * [5] J. Chen, X. Huang, I. A. Kanj, and G. Xia.  Strong computational lower bounds via parameterized complexity.  Journal of Computer and System Sciences, 72(8):1346–1367, 2006\.
  * [6] L. Chen, R. Kyng, Y. P. Liu, R. Peng, M. Probst Gutenberg, and S. Sachdeva.  Maximum flow and minimum-cost flow in almost-linear time.  In FOCS 2022: Proceedings of the 63rd Annual Symposium on Foundations of Computer Science, pages 612–623. IEEE, 2022.
  * [7] M. Condorcet.  Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix.  L’Imprimerie Royale, 1785.
  * [8] Á. Cseh.  Popular matchings.  In U. Endriss, editor, Trends in computational social choice, chapter 6, pages 105–122. AI Access, 2017.
  * [9] Á. 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.
  * [10] R. G. Downey and M. R. Fellows.  Parameterized Complexity.  Monographs in Computer Science. Springer-Verlag, New York, 1999.
  * [11] ET Bureau.  Final year medics, nurses to be roped in to fight covid.  Economic Times, 2021.  India, May 03.
  * [12] T. Feder.  A new fixed point approach for stable networks and stable marriages.  Journal of Computer and System Sciences, 45:233–284, 1992.
  * [13] T. Fleiner, R. W. Irving, and D. F. Manlove.  Efficient algorithms for generalised stable marriage and roommates problems.  Theoretical Computer Science, 381(1-3):162–176, 2007.
  * [14] D. Gale and L. S. Shapley.  College admissions and the stability of marriage.  The American Mathematical Monthly, 69(1):9–15, 1962.
  * [15] P. Gärdenfors.  Match making: assignments based on bilateral preferences.  Behavioural Science, 20:166–173, 1975.
  * [16] R. W. Irving.  An efficient algorithm for the “stable roommates” problem.  Journal of Algorithms, 6:577–595, 1985.
  * [17] T. Kavitha.  A size-popularity tradeoff in the stable marriage problem.  SIAM Journal on Computing, 43(1):52–71, 2014.
  * [18] T. Kavitha.  Popular half-integral matchings.  In ICALP 2016: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1–22:13, 2016.
  * [19] T. Kavitha.  Maximum matchings and popularity.  In ICALP 2021: Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 85:1–85:21, 2021.
  * [20] T. Kavitha, T. Király, J. Matuschke, I. Schlotter, and U. Schmidt-Kraepelin.  The popular assignment problem: when cardinality is more important than popularity.  In SODA 2022: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 103–123. SIAM, 2022.
  * [21] T. Kavitha, J. Mestre, and M. Nasre.  Popular mixed matchings.  Theoretical Computer Science, 412(24):2679–2690, 2011.
  * [22] T. Kavitha and M. Nasre.  Optimal popular matchings.  Discrete Applied Mathematics, 157:3181–3186, 2009.