Fairness and Efficiency in Two-Sided Matching Markets

We give a polynomial-time reduction from the (3-3)-com smti problem. In (3-3)-com smti, we have sets $M,W$ of men and women. For $x\in M\uplus W$, let ${\mathrm{𝗉𝗋𝖾𝖿}}_x$ denote the preference list of $x$. We assume that $x\in M$ without loss of generality (i.e., the following constraints hold for the preference lists of each woman in (3-3)-com smti as well). The list ${\mathrm{𝗉𝗋𝖾𝖿}}_x$ is an ordered sequence of disjoint subsets of women which represents a partial order over the women, where women in earlier subsets are preferred over women in later subsets, and women in the same subsets are tied. We define $|{\mathrm{𝗉𝗋𝖾𝖿}}_x|$ as the total number of women appearing in ${\mathrm{𝗉𝗋𝖾𝖿}}_x$, and (3-3)-com smti requires that $|{\mathrm{𝗉𝗋𝖾𝖿}}_x|\le 3$. Women which do not appear in ${\mathrm{𝗉𝗋𝖾𝖿}}_x$ are considered unacceptable by $x$. In (3-3)-com smti, the goal is to find a weakly stable matching of men and women, given the above constraints.

Let $𝒥$ be an instance of (3-3)-com smti such that the ties are only on the women’s side. We construct an instance $ℐ$ of MEFE-Matching as follows. Let $X=M$ and $T=W$, i.e., for each man $m\in M$, we have a course $m$, and for each woman $w$, we have a TA $w$. For every course $m\in X$, $v_m(w)=4-i$, if man $m$ ranks woman $w$ at position $i$; otherwise $0$. We next define a set of valuation functions of TAs. It is according to the preference list of women. If woman $w$ ranks man $m$ at position $i$, then the utility of TA $w$ for the course $m$ is $u_w(m)=4-i$, if $m$ is not in the preference list of woman $w$, then $u_w(m)=0$. Next, we define a grade function for every course based the preference list of men, which is strict. If man $m$ ranks woman $w$ at position $i$, then the grade of TA $w$ for the course $m$ is $g_w(m)=4-i$, if $m$ is not in the preference list of woman $w$, then $g_w(m)=0$. The capacity of each course is one and $k=1$. Next, we prove the correctness. In particular, we prove the following.

In the forward direction, let $\eta$ be a solution to $𝒥$. We claim that $\mu =\eta$ is also a solution to $ℐ$. Clearly, $\mu$ is a feasible matching as every course is matched to one TA. Furthermore, for every course $m\in X$, $\mathrm{𝖠𝗏𝗀𝖴𝗍𝗂𝗅}(m)\ge 1$ as $v_m(w)\ge 1$ for all $w$ who are in preference list of $m$ and if a woman $w$ is matched to a man $m$ then $w$ must be in the preference list of $m$. Next, we argue that $\mu$ is merit-based envy-free. Note that $\mu$ is a perfect matching. Thus, every TA is matched to a course. Furthermore, every TA is matched to a course with non-zero utility due to the construction and the fact that $\eta$ is a solution to (3-3)-com smti. Suppose that TA $t$ envies TA $t^{\prime }$, then we have $g_t(\mu (t^{\prime }))\ge g_{t^{\prime }}(\mu (t^{\prime }))$. Due to construction and the fact that ties belong to only women side, equality is not possible. Hence, $g_t(\mu (t^{\prime }))>g_{t^{\prime }}(\mu (t^{\prime }))$. Also, $u_t(\mu (t^{\prime }))>u_t(\mu (t))$ which means $t{\succ }_{\eta (t^{\prime })}{t}^{\prime }$ and $\eta (t^{\prime }){\succ }_t\eta (t)$, which contradicts the fact that $\eta$ is a stable matching.

In the reverse direction, let $\mu$ be a solution to $ℐ$. We claim that $\eta =\mu$ is a solution to $𝒥$. Recall that the capacity of every course is one in $𝒥$. Thus, $\eta$ saturates all men. Since, the number of courses and TAs is same and every course is matched to only one TA, every TA is matched to a course in $\mu$. Thus, $\eta$ is a perfect matching. Moreover, for every course $w\in X$, $\mathrm{𝖠𝗏𝗀𝖴𝗍𝗂𝗅}(w)\ge 1$ as we have $v_m(w)\ge 1$ for matched pair ($m,w$). Each man is matched with a woman who is in his preference list and hence, each woman also is matched with a man in her preference list due to construction. Next, we claim that $\mu$ is weakly stable. Towards the contradiction, suppose that there is a pair $(m,w)$ such that $w{\succ }_m\eta (m)$ and

$m{\succ }_w\eta (w)$. Thus, due to the construction of the instance $ℐ$, $g_w(m)>g_{\eta (m)}(m)$, and $u_w(m)>u_w(\mu (w))$. Thus, TA $w$ envies TA $w^{\prime }$, which contradicts that $\mu$ is a solution to $ℐ$. $◀$

The transformation can be carried out in polynomial time since, for each pair $(m,w)\in M\times W$, the values $v_m(w)$, $u_w(m)$, and $g_w(m)$ can be computed by scanning the preference lists of $m$ and $w$, each of which has length at most $𝒪(n)$. Thus, the total time required to construct the instance is $𝒪(n^2)$. This completes the NP-hardness proof when course utilities are derived from grades. The binary case is similar. Here, the course valuation would be defined as follows: for every course $m\in X$, $v_m(w)=1$ if woman $w$ is in the preference list of man $m$, otherwise $0$. The proof remains same for binary valuation function. $◀$

Our next intractability result is when TAs have binary valuations and grades in the range $\{0,1,2\}$, other than the constraints on degrees and capacities. The result is due to a polynomial-time reduction from the $3$-dimensional Perfect Matching problem.

We visualize an instance $ℐ$ of MEFE-Matching as a bipartite graph $G=(X,T)$ and note that $G$ can be a disconnected graph. However, it is sufficient to solve each component separately, as we do not assign $0$-valued TAs to a course. Let $G_{conn}$ be a maximal connected subgraph of $G$. For the ease of notation, we reuse $X,T$ as the bipartiton of $G_{conn}$ as well, where $X,T$ is the set of courses and TAs, respectively, in $G_{conn}$. Let $X=\{x_1,\mathrm{\dots },x_n\}$ and $T=\{t_1,\mathrm{\dots },t_m\}$. We find an MEFE matching, if it exists, for $G_{conn}$. We design the algorithm based on the structure of the graph. We first consider the case the graph has a course with degree equalling capacity. If not, then we further consider other cases: whether it is acyclic, or contains one cycle, or contains at least two cycles. In the case of two cycles, we argue that it is no-instance. In the other cases, for a yes-instance, the intuitive idea is that there exists a TA/course whose assignment or decision that it is unassigned dictates the whole matching. Note that such a TA/course should be chosen carefully as every choice does not fix the matching.

Let $X^{\prime }=\{x_1,\mathrm{\dots },x_{\mathrm{\ell }}\}$ be the set of courses in $X$ such that $d(x_i)=c_i$, where $i\in [\mathrm{\ell }]$. We construct a matching $\mu$ as follows: for each $i\in [\mathrm{\ell }]$, ${\mu }^{-1}(x_i)=N(x_i)$. If ${\mu }^{-1}(x_i)$ and ${\mu }^{-1}(x_j)$ are not disjoint, for any $i,j\in [\mathrm{\ell }]$, then we return NO. Otherwise, we call $\text{Extended Matching}(G_{conn},\mu ,T_{\mu }=N(X^{\prime }),X_{\mu }=X^{\prime })$(Algorithm 1) and find a matching $\mu$. The intuition is that we consider a course $x\in X$ whom we did not assign TAs yet, such that one of the positively valued TAs it has an edge with has already been assigned to a course. Thus, all the remaining TAs positively valued by this course must be assigned to it (we will argue in the correctness proof that for a yes-instance, only one of its TA is assigned to another course). If $\mu$ is a solution to $ℐ$, we return it; otherwise, we return NO.

In this case, $|E(G_{conn})|=|X|+|T|-1$. Furthermore, since $G_{conn}$ is a bipartite graph, $E(G_{conn})={\sum }_{i\in [n]}d(x_i)$. Thus,

This implies that ${\sum }_{i\in [n]}(d(x_i)-1)=|T|-1$ Since $c_i=d(x_i)-1$, we have that

Hence, there is only one TA that is unassigned in any feasible solution to $ℐ$. We guess this TA, say $t$. Now, we need to assign all TAs in $T^{\prime }=T\setminus \{t\}$ to the courses in $X$. The intuitive idea is that since $t$ is unassigned, for all the courses that have positive valuations to $t$, we only have capacity many choices. Thus, the allocation of all these courses is fixed. Since the graph is connected, this eventually fixes the allocation of all the courses. Algorithm 2 describes the algorithm formally.

Let $C=(x_1,t_1,\mathrm{\dots },x_{\mathrm{\ell }},t_{\mathrm{\ell }})$ be the cycle in $G_{conn}$. Clearly, there exists an edge in $C$ whose deletion makes the graph $G_{conn}$ acyclic. Thus, in this case, $|E(G_{conn})|=|X|+|T|$. Furthermore, $|E(G_{conn})|={\sum }_{i\in [n]}d(x_i)$. Thus, by equating the above two expressions just as we did in Case 2.1, we get $|T|={\sum }_{i\in [n]}{c}_i$. Therefore, all TAs need to be assigned in a feasible matching for this case. Let $X_C,T_C$ denote the set of courses and TAs, respectively, in $C$. We guess whether $t_1$ or $t_{\mathrm{\ell }}$ is assigned to $x_1$ (one of them has to be assigned as $d(x_1)-c_1=1$). After this guess, an allocation for all the courses gets “fixed”, i.e., there is a unique choice of allocation. Algorithm 3 describes the algorithm formally.

The algorithm returns NO in this case.

The detailed proof of correctness and running time analysis can be found in the full version [24]. $◀$

Due to Theorem 5, we have the following result, which is in contrast to Theorem 2 when considering the degree of courses.

Our next tractability result is in contrast to Theorem 2, as it reduces the problem to Weighted Strongly Stable Matching with Ties and Incomplete Lists (WSSMTI) in polynomial time, which can be solved in polynomial time [30].

Our next result is in contrast to Theorem 1. The result is due to the observation that a TA with high grade needs to be prioritised over low grade TAs in a solution. Thus, we sort the TAs based on their grades and match the top capacity many TAs to the course. We also observe that an instance can be partitioned into distinct sub-instances, where each sub-instance has only one course.

The degree of every TA is 1 when the number of courses is one. Hence Theorem 8 is applicable. $◀$

Another restricted instance we analyze is one in which the capacities of all courses are constant, and the number of courses is also constant. In this case, the total number of possible solutions are polynomial which can be enumerated in polynomial time. Hence, we have the following result.

Next, we consider the case when every course has only two positive distinct values for TAs, and obtain the tractability, with some restrictions on valuations and grades of TAs.

Let $ℐ=(X,T,{\{v_i\}}_{i\in X},{\{u_i\}}_{i\in T},{\{g_i\}}_{i\in T},$ ${\{c_i\}}_{i\in X},k\}$ be an instance of MEFE-Matching such that $v_i:T\to \{0,q_i,q_i^{\prime }\}$, where $q_i,q_i^{\prime }$ are positive integers, and for any pair of TAs $t_i,t_j\in T$, $g_i(x)\ne g_j(x)$, for any course $x$. Without loss of generality, let $q_i\ge q_i^{\prime }$. Next, we find the number of $q_i$ and $q_i^{\prime }$ valued items assigned to $x_i$ in a solution. Let $a_i,a_i^{\prime }$ be the number of $q_i$ and $q_i^{\prime }$ valued items assigned to $x_i$, respectively. If $q_i=q_i^{\prime }$, then $a_i=c_i,a_i^{\prime }=0$. Otherwise, we find the following equations for each course independently. Due to our feasibility and satisfaction constraints for courses, we know that for each $i\in [n]$,

If the set of the above two equations does not have a solution, then clearly, $ℐ$ is a no-instance of MEFE-Matching. Suppose that there is a solution of the set of Equation 1 and 2 for every course. If we solve these two equations, we obtain that $a_i^{\prime }\le \frac{c_i(q_i-k)}{q_i-q_i^{\prime }}$ and $a_i\ge \frac{c_i(k-q_i^{\prime })}{q_i-q_i^{\prime }}$. Note that if $a_i^{\prime }$ is negative, then $a_i>c_i$, which violates the feasibility of a matching. Thus, if , it is a no-instance. So next we assume that $q_i\ge k$. We choose $a_i=\max \{0,\lceil \frac{c_i(k-q_i^{\prime })}{q_i-q_i^{\prime }}\rceil \}$ and $a_i^{\prime }=c_i-a_i$. We next give a polynomial time reduction from MEFE-Matching to the Stable Matching problem for bipartite graphs, in which given a set of men, say $M$, and women, say $W$, a preference list of women over men, a preference list of men over woman, (preference lists might be incomplete); the goal is to decide whether there exists a matching such there is no pair of man and woman $(m,w)$ such that (i) $m$ is unmatched or prefers $w$ over his matched partner, and (ii) $w$ is unmatched or prefers $m$ over her matched partner. Such a pair of $(m,w)$ is called a blocking pair, and a matching without blocking pairs is called a stable matching.

We create an instance of the Stable Matching problem $𝒥$ as follows. The set of men is $M=T$, i.e., corresponding to every TA in $T$, we have a man in $M$. Corresponding to every course $x_i\in X$, we have $c_i$ women, say $w_i^1,\mathrm{\dots },w_i^{c_i}$. If $a_i>0$, let $W_i=\{w_i^1,\mathrm{\dots },w_i^{a_i}\}$, and if $a_i^{\prime }>0$, let $W_i^{\prime }=\{w_i^{a_i+1},\mathrm{\dots },w_i^{c_i}\}$. Next, we define the preference list of every woman $w$, say $P_w$, as follows. For every $w\in W_i$, man $t$ is in $P_w$ if and only if the valuation of course $x_i$ for the TA $t$ is $q_i$. For every woman $w\in W_i^{\prime }$, man $t$ is in the preference list of $w$ if and only if the valuation of course $x_i$ for TA $t$ is positive. Recall that in an instance of the Stable Matching problem a man $m$ is on the preference list of a woman $w$ if and only if $w$ is in the preference list of $m$. Next, we define the ordering of men in the preference list of every woman, which is based on the grades. Since no two TAs have the same grade for a course, for men $t,t^{\prime }$ in $P_w$, woman $w$ prefers $t$ more than $t^{\prime }$ if and only if $g_t(w)>g_{t^{\prime }}(w)$. Next, we define the ordering of women in the preference list of every man. Let $P_t$ be the set of women in the preference list of the man $t$. Consider a man $t$. If $u_t(x_i)>u_t(x_j)$, where $x_i,x_j\in X$, then man $t$ prefers women in $w\in W_i\cup W_i^{\prime }$ more than woman $\widehat{w}\in W_j\cup W_j^{\prime }$, where $w,\widehat{w}\in P_m$. Furthermore, if $w\in P_m\cap W_i$ and $\widehat{w}\in P_m\cap W_i^{\prime }$, then $m$ prefers $w$ more than $\widehat{w}$. If $w,\widehat{w}\in P_m\cap W_i$, then $m$ order them arbitrarily; similarly women in $P_m\cap W_i^{\prime }$ are ordered arbitrarily. This completes the construction of $𝒥$.

Proof of correctness and running time analysis can be found in the full version [24]. $◀$

Let $ℐ$ be an instance of MEFE-Matching that satisfies the constraints in the theorem statement. Let $v_i:T\to \{q_{1i},\mathrm{\dots },q_{r_{i}i}\}$, where $r_i$ is a constant. Let $a_{ji}$ be the number of TAs of value $q_{ji}$ assigned to the course $x_i$ in a solution, where $i\in [n],j\in [r_i]$. We guess the values of $a_{ji}$, for all $i\in [n],j\in [r_i]$, that satisfies the following two constraints.

Note that we have ${(c_i+1)}^{r_i}$ choices for vector $(a_{1i},\mathrm{\dots },a_{r_{i}i})$ for every course $x_i$. A vector is called valid, if it satisfies Equation 3 and 4. Since the capacity of each course and $r_i$ is constant, we have constant choices for every course. Hence, we have $c^n$ total choices, where $c$ is a constant.

For each combination of $n$ valid vectors (one for each course) $(a_{11},\mathrm{\dots }{a}_{r_{1}1},\mathrm{\dots },a_{1n},\mathrm{\dots }{a}_{r_{n}n})$, we create an instance of the Stable Matching problem $𝒥$ as follows. The set of men is $M=T$, i.e., corresponding to every TA in $T$, we have a man in $M$. Corresponding to every course $x_i\in X$, we have a set of women $W_{ji}$ that contains $a_{ji}$ many women. If any of these sets are empty we ignore those sets. Let $W_i$ be set of all women corresponding to course $x_i$. Due to the validity of the vector, corresponding to every course $x_i$, we have $c_i$ women. Next, we define the preference list of every woman $w$, say $P_w$, as follows. For every $w\in W_{ji}$, man $t$ is in $P_w$ if the valuation of course $x_i$ for the TA $t$ is $q_{ji}$. Recall that in an instance the Stable Matching problem a man $m$ is in the preference list of a woman $w$ if and only if $w$ is in the preference list of $m$. Thus, woman $w$ is in $P_m$, the preference list of $m$, if and only if $m$ is in $P_w$. Next, we define the ordering of men in the preference list of every woman, which is based on the grades. Let $w$ be a women corresponding to the course $x_i$. Since no two TAs have the same grade for a course, for men $t,t^{\prime }$ in $P_w$, $w$ prefers $t$ more than $t^{\prime }$ if and only if $g_t(x_i)>g_{t^{\prime }}(x_i)$. Next, we define the ordering of women in the preference list of every man. Consider a man $t$. If $u_t(x_i)>u_t(x_j)$, where $x_i,x_j\in X$, then man $t$ prefers women in $w\in W_i$ more than woman in $\widehat{w}\in W_j$, where $w,\widehat{w}\in P_t$. If $w,w^{\prime }\in P_t\cap W_i$, then we first note that there exists unique $j\in [r_i]$ such that $w,w^{\prime }\in W_{ji}$, due to the construction. In this case, man $t$ orders them arbitrarily. This completes the construction of $𝒥$. If any of the constructed instance of Stable Matching returns a women-saturating stable matching, then we return “yes”, otherwise “no”.

The proof of correctness can be found in the full version [24]. $◀$

Next, we design a parameterized approximation scheme with respect to the parameter $n,ϵ$, and $\log v$, where $v$ is maximum value assigned to a TA by a course. Our basic idea is that for appropriately chosen ${ϵ}^{\prime }$, we guess the number of TAs assigned to course $x_i$ that have valuations in the range $[{(1+{ϵ}^{\prime })}^{j-1},{(1+{ϵ}^{\prime })}^j)$, for every course $x_i\in X$. Then, we create the number of copies of a course accordingly and reduce to the Stable Matching problem as in Theorem 13.