Robust and Approximately Stable Marriages Under Partial Information

Abstract

We study the stable marriage problem in the partial information setting where the agents, although they have an underlying true strict linear order, are allowed to specify partial orders either because their true orders are unknown to them or they are unwilling to completely disclose the same. Specifically, we focus on the case where the agents are allowed to submit strict weak orders and we try to address the following questions from the perspective of a market-designer: (i) How can a designer generate matchings that are robust—in the sense that they are “good” with respect to the underlying unknown true orders? (ii) What is the trade-off between the amount of missing information and the “quality” of solution one can get? With the goal of resolving these questions through a simple and prior-free approach, we suggest looking at matchings that minimize the maximum number of blocking pairs with respect to all the possible underlying true orders as a measure of “goodness” or “quality”, and subsequently provide results on finding such matchings. In particular, we first restrict our attention to matchings that have to be stable with respect to at least one of the completions (i.e., weakly-stable matchings) and show that in this case arbitrarily filling-in the missing information and computing the resulting stable matching can give a non-trivial approximation factor for our problem in certain cases. We complement this result by showing that, even under severe restrictions on the preferences of the agents, the factor obtained is asymptotically tight in many cases. We then investigate a special case, where only agents on one side provide strict weak orders and all the missing information is at the bottom of their preference orders, and show that in this special case the negative result mentioned above can be circumvented in order to get a much better approximation factor; this result, too, is tight in many cases. Finally, we move away from the restriction on weakly-stable matchings and show a general hardness of approximation result and also discuss one possible approach that can lead us to a near-tight approximation bound.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Two-sided matching markets have numerous applications, e.g., in matching students to dormitories (i.e., Stable Roommates problem (SR) [11]), residents to hospitals (i.e., Hospital-Resident problem (HR) [18]) etc., and hence are ubiquitous in practice. Perhaps unsurprisingly, then, this line of research has received much attention, with plenty of work done on investigating numerous problems like SR and HR, and their many variations (we refer the reader to the excellent books by Gusfield and Irving [9] and Manlove [17] for a survey on two-sided matching problems). The focus of this paper, too, is on one such problem—one that is perhaps the most widely-studied, but yet the simplest—called the Stable Marriage problem (SM), first introduced by Gale and Shapley [8]. In SM we are given two disjoint sets (colloquially referred to as the set of men and women) and each agent in one set specifies a strict linear order over the agents in the other set, and the aim is to find a stable matching, i.e., a matching where there is no man-woman pair such that each of them prefers the other over their partner in the matching. (Such a pair, if it exists, is called a blocking pair).

While the assumption that the agents will be able to specify strict linear orders is not unreasonable in small markets, in general, as the markets get larger, it may not be feasible for an agent to determine a complete ordering over all the alternatives. Furthermore, there may arise situations where agents are simply unwilling to provide strict total orders due to, say, privacy concerns. Thus, it is natural for a designer to allow agents the flexibility to specify partial orders, and so in this paper we assume that the agents submit strict weak orders¹ (i.e., strict partial orders where incomparability is transitive) that are consistent with their underlying true strict linear orders. Although the issue of partially specified preferences has received attention previously, we argue that certain aspects have not been addressed sufficiently. In particular, the common approach to the question of what constitutes a “good” matching in such a setting has been to either work with stable matchings that arise as a result of an arbitrary linear extension of the submitted partial orders (these are known as weakly-stable matchings) or to look at something known as super-stable matchings, which are matchings that are stable with respect to all the possible linear extensions of the submitted partial orders [12, 19]. In the case of the former, one key issue is that we often do not really know how “good” a particular weakly-stable matching is with the respect to the underlying true orders of the agents, and in the case of the latter they often do not exist. Furthermore, we believe that it is in the interest of the market-designer to understand how robust or “good” a matching is with respect to the underlying true orders of the agents, for, if otherwise, issues relating to instability and market unravelling can arise since the matching that is output by a mechanism can be arbitrarily bad with respect to these true orders. Hence, in this paper we propose to move away from the extremes of working with either arbitrary weakly-stable matchings or super-stable matchings, and to find a middle-ground when it comes to working with partial preference information. To this end, we aim to answer two questions from the perspective of a market-designer: (i) How should one handle partial information so as to be able to provide some guarantees with respect to the underlying true preference orders? (ii) What is the trade-off between the amount of missing information and the quality of a matching that one can achieve? We discuss our proposal in more detail in the following sections.

1.1 How Does One Work with Partial Information?

When agents do not submit full preference orderings, there are several possible ways to cope with the missing information. For instance, one approach that immediately comes to mind is to assume that there exists some underlying distribution from which the agents’ true preferences are drawn, and then use this information to find a “good” matching—which is, say, the one with the least number of blocking pairs in expectation. However, the success of such an approach crucially depends on having access to information about the underlying preference distributions which may not always be available. Therefore, in this paper we make no assumptions on the underlying preference distributions and instead adopt a prior-free and absolute-worst-case approach where we assume that any of the linear extensions of the given strict partial orders can be the underlying true order, and we aim to provide solutions that perform well with respect to all of them. We note that similar worst-case approaches have been looked at previously, for instance, by Chiesa et al. [5] in the context of auctions.

The objective we concern ourselves with here is that of minimizing the number of blocking pairs, which is well-defined and has been considered previously in the context of matching problems (for instance, see [1, 4]). In particular, for a given instance $\mathcal {I}$ our aim is to return a matching $\mathcal {M}_{opt}$ that has the best worst case—i.e., a matching that has the minimum maximum ‘regret’ after one realises the true underlying preference orders. (We refer to $\mathcal {M}_{opt}$ as the minimax optimal solution.) More precisely, let $\mathcal {I} = (p_U, p_W)$ denote an instance, where $p_U = \{p_{u_1}, \cdots , p_{u_n}\}$, $p_W = \{p_{w_1}, \cdots , p_{w_n}\}$, $U = \{u_i\}_{i\in \{1,2,\cdots ,n\}}$ and $W=\{w_i\}_{i\in \{1,2,\cdots ,n\}}$ are the set of men and women respectively, and $p_i$ is the strict partial order submitted by agent i. Additionally, let $C(p_i)$ denote the set of linear extensions of $p_i$, C be the Cartesian product of the $C(p_i)$s, i.e., , $bp(\mathcal {M}, c)$ denote the set of blocking pairs that are associated with the matching $\mathcal {M}$ according to some linear extension $c \in C$, and S denote the set of all possible matchings. Then the matching $\mathcal {M}_{opt}$ that we are interested in is defined as $\mathcal {M}_{opt} = {{\mathrm{arg\,min}}}_{\mathcal {M} \in S} \max _{c \in C} \left| bp(\mathcal {M}, c)\right|$.

While we are aware of just one work by Drummond and Boutilier [6] who consider the minimax regret approach in the context of stable matchings (they consider it mainly in the context of preference elicitation; see Sect. 1.4 for more details), the approach, in general, is perhaps reminiscent, for instance, of the works of Hyafil and Boutilier [10] and Lu and Boutilier [15] who looked at the minimax regret solution criterion in the context of mechanism design for games with type uncertainty and preference elicitation in voting protocols, respectively.

Remark: In the usual definition of a minimax regret solution, there is a second term which measures the ‘regret’ as a result of choosing a particular solution. That is, in the definition above, it would usually be $\mathcal {M}_{opt} = {{\mathrm{arg\,min}}}_{\mathcal {M} \in S} \max _{c \in C} \left| bp(\mathcal {M}, c)\right| - \left| bp(\mathcal {M}_{c}, c)\right|$, where $\mathcal {M}_{c}$ is the optimal matching (with respect to the objective function $\left| bp()\right|$) for the linear extension c. We do not include this in the definition above because $\left| bp(\mathcal {M}_{c}, c)\right| = 0$ as every instance of the marriage problem with linear orders has a stable solution (which by definition has zero blocking pairs). Additionally, the literature on stable matchings uses the term “regret” to denote the maximum cost associated with a stable matching, where the cost of a matching for an agent is the rank of its partner in the matching and the maximum is taken over all the agents (for instance, see [16]). However, here the term regret is used in the context of the minimax regret solution criterion.

1.2 How Does One Measure the Amount of Missing Information?

For the purposes of understanding the trade-off between the amount of missing information and the “quality” of solution one can achieve, we need a way to measure the amount of missing information in a given instance. There are many possible ways to do this, however in this paper we adopt the following. For a given instance $\mathcal {I}$, the amount of missing information, $\delta$, is the fraction of pairwise comparisons one cannot infer from the given strict partial orders. That is, we know that if every agent submits a strict linear order over n alternatives, then we can infer $\left( {\begin{array}{c}n\\ 2\end{array}}\right)$ comparisons from it. Now, instead, if an agent i submits a strict partial order $p_i$, then we denote by $\delta _i$ the fraction of these $\left( {\begin{array}{c}n\\ 2\end{array}}\right)$ comparisons one cannot infer from $p_i$ (this is the “missing information” in $p_i$). Our $\delta$ here is equal to $\frac{1}{2n}\sum _{i\in U \cup W} \delta _i$. Although, given a strict partial order $p_i$, it is straightforward to calculate $\delta _i$, we will nevertheless assume throughout that $\delta$ is part of the input. Hence, our definition of an instance will be modified the following way to include the parameter for missing information: $\mathcal {I} = (\delta , p_U, p_W)$.

Remark: $\delta = 0$ denotes the case when all the preferences are strict linear orders. Also, for an instance with n agents on each side, the least value of $\delta$ when the amount of missing information is non-zero is $\frac{1}{2n}\frac{1}{\left( {\begin{array}{c}n\\ 2\end{array}}\right) }$ (this happens in the case where there is only one agent with just one pairwise comparison missing). However, despite this, in the interest of readability, we sometimes just write statements of the form “for all $\delta > 0$”. Such statements need to be understood as being true for only realizable or valid values of $\delta$ that are greater than zero.

1.3 Our Contributions

The focus of our work is on computing the minimax optimal matching, i.e., a matching that, when given an instance $\mathcal {I}$, minimizes the maximum number of blocking pairs with respect to all the possible linear extensions (see Sect. 2.1 for a formal definition of the problem). Towards this end, we make the following contributions:

• We formally define the problem and show that, interestingly, the problem under consideration is equivalent to the problem of finding a matching that has the minimum number of super-blocking pairs (i.e., man-woman pairs where each of them weakly-prefers the other over their current partners).

• While an optimal answer to our question might involve matchings that have man-woman pairs such that each of them strictly prefers the other over their partners, we start by focusing our investigation on matchings that do not have such pairs. Given the fact that any matching with no such pairs are weakly-stable, through this setting we address the question “given an instance, can we find a weakly-stable matching that performs well, in terms of minimizing the number of blocking pairs, with respect to all the linear extensions of the given strict partial orders?” We show that by arbitrarily filling-in the missing information and computing the resulting stable matching, one can obtain a non-trivial approximation factor (i.e., one that is ${o}(n^2)$) for our problem for many values of $\delta$. We complement this result by showing that, even under severe restrictions on the preferences of the agents, the factor obtained is asymptotically tight in many cases.

• By assuming a special structure on the agents’ preferences—one where strict weak orders are specified by just agents on one side and all the missing information is at the bottom of their preference orders—we show that one can obtain a $\mathcal {O}(n)$-approximation algorithm for our problem. The proof of the same is via finding a 2-approximation for another problem (see Problem 3) that might be of independent interest.

• In Sect. 4 we remove the restriction to weakly-stable matchings and show a general hardness of approximation result for our problem. Following this, we discuss one possible approach that can lead to a near-tight approximation guarantee for the same.

1.4 Related Work

There has recently been a number of papers that have looked at problems relating to missing preference information or uncertainty in preferences in the context of matching.

Drummond and Boutilier [6] used the minimax regret solution criterion in order to drive preference elicitation strategies for matching problems. While they discussed computing robust matchings subject to a minimax regret solution criteria, their focus was on providing an NP-completeness result and heuristic preference elicitation strategies for refining the missing information. In contrast, in addition to focusing on understanding the exact trade-offs between the amount of missing information and the solution “quality”, we concern ourselves with arriving at approximation algorithms for computing such robust matchings.

Rastegari et al. [19] studied a partial information setting in labour markets. However, again, the focus of this paper was different than ours. They looked at pervasive-employer-optimal matchings, which are matchings that are employer-optimal (see [19] for the definitions) with respect to all the underlying linear extensions. In addition, they also discussed how to identify, in polynomial time, if a matching is employer-optimal with respect to some linear extension.

Recent work by Aziz et al. [2] looked at the stable matching problem in settings where there is uncertainty about the preferences of the agents. They considered three different models of uncertainty and primarily studied the complexity of computing the stability probability of a given matching and the question of finding a matching that will have the highest probability of being stable. In contrast to their work, in this paper we do not make any underlying distributional assumptions about the preferences of the agents and instead take an absolute worst-case approach, which in turn implies that our results hold irrespective of the underlying distribution on the completions.

Finally, we also briefly mention another line of research which deals with partial information settings and goes by the name of interview minimization (see, for instance, [7, 20]). One of the main goals in this line of work is to come with a matching that is stable (and possibly satisfying some other desirable property) by conducting as few ‘interviews’ (which in turn helps the agents in refining their preferences) as possible. We view this work as an interesting, orthogonal, direction from the one we pursue in this paper.

2 Preliminaries

Let U and W be two disjoint sets. The sets U and W are colloquially referred to as the set of men and women, respectively, and $|U| = |W| = n$. We assume that each agent in U and W has a true strict linear order (i.e., a ranking without ties) over the agents in the other set, but this strict linear order may be unknown to the agents or they may be unwilling to completely disclose the same. Hence, each agent in U and W specifies a strict partial order over the agents in the other set (which we refer to as their preference order) that is consistent with their underlying true orders, and $p_U$ and $p_W$, respectively, denote the collective preference orders of all the men and women. For a strict partial order $p_i$ associated with agent i, we denote the set of linear extensions associated with $p_i$ by $C(p_i)$ and denote by C the Cartesian product of the $C(p_i)$s, i.e., . We refer to the set C as “the set of all completions” where the term completion refers to an element in C. Also, throughout, we denote strict preferences by $\succ$ and use $\succeq$ to denote the relation ‘weakly-prefers’. So, for instance, we say that an agent c strictly prefers a to b and denote this by $a \succ _{c} b$ and use $a \succeq _{c} b$ to denote that either c strictly prefers a to b or finds them incomparable. As mentioned previously, we restrict our attention to the case when the strict partial orders submitted by the agents are strict weak orders over the set of agents in the other set.

Remark: Strict weak orders are defined to be strict partial orders where incomparability is transitive. Hence, although the term tie is used to mean indifference, it is convenient to think of strict weak orders as rankings with ties. Therefore, throughout this paper, whenever we say that agent c finds a and b to be tied, we mean that c finds a and b to be incomparable. Additionally, we will use the terms ties and incomparabilities interchangeably.

An instance $\mathcal {I}$ of the stable marriage problem (SM) is defined as $\mathcal {I} = (\delta , p_U, p_w)$, where $\delta$ denotes the amount of missing information in that instance and this in turn, as defined in Sect. 1.2, is the average number of pairwise comparisons that are missing from the instance, and $p_U$ and $p_W$ are as defined above. Given an instance $\mathcal {I}$, the aim is usually to come up with a matching $\mathcal {M}$—which in turn is a set of disjoint pairs (m, w), where $m \in U$ and $w \in W$—that is stable. There are different notions of stability that have been proposed and below we define two of them that are relevant to our paper: (i) weak-stability and (ii) super-stability. However, before we look at their definitions we introduce the following terminology that will be used throughout this paper. (Note that in the definitions below we implicitly assume that in any matching $\mathcal {M}$ all the agents are matched. This is so because of the standard assumption that is made in the literature on SM (i.e., the stable marriage problem where every agent has a strict linear order over all the agents in the other set) that an agent always prefers to be matched to some agent than to remain unmatched).

Definition 1

(blocking pair/obvious blocking pair). Given an instance $\mathcal {I}$ and a matching $\mathcal {M}$ associated with $\mathcal {I}$, (m, w) is said to be a blocking pair associated with $\mathcal {M}$ if $w \succ _{m} \mathcal {M}(m)$ and $m \succ _{w} \mathcal {M}(w)$. The term blocking pair is usually used in situations where the preferences of the agents are strict linear orders, so in cases where the preferences of the agents have missing information, we refer to such a pair as an obvious blocking pair.

Definition 2

(super-blocking pair). Given an instance $\mathcal {I}$ where the agents submit partial preference orders and a matching $\mathcal {M}$ associated with $\mathcal {I}$, we say that (m, w) is a super-blocking pair associated with $\mathcal {M}$ if $w \succeq _{m} \mathcal {M}(m)$ and $m \succeq _{w} \mathcal {M}(w)$.

Given the definitions above we can now define weak-stability and super-stability.

Definition 3

(weakly-stable matching). Given an instance $\mathcal {I}$ and matching $\mathcal {M}$ associated with $\mathcal {I}$, $\mathcal {M}$ is so said to be weakly-stable with respect to $\mathcal {I}$ if it does not have any obvious blocking pairs. When the preferences of the agents are strict linear orders, such a matching is just referred to as a stable matching.

Definition 4

(super-stable matching). Given an instance $\mathcal {I}$ and matching $\mathcal {M}$ associated with $\mathcal {I}$, $\mathcal {M}$ is so said to be super-stable with respect to $\mathcal {I}$ if it does not have any super-blocking pairs.

2.1 What Problems Do We Consider?

As mentioned in the introduction, we are interested in finding the minimax optimal matching where the objective is to minimize the number of blocking pairs, i.e., to find, from the set S of all possible matchings, a matching that has the minimum maximum number of blocking pairs with respect to all the completions. This is formally defined below.

Problem 1

($\delta$-minimax-matching). Given a $\delta \in [0, 1]$ and an instance $\mathcal {I} = (\delta ', p_U, p_W)$, where $\delta ' \le \delta$ is the amount of missing information and $p_U, p_W$ are the preferences submitted by men and women respectively, compute $\mathcal {M}_{opt}$ where $\mathcal {M}_{opt} = {{\mathrm{arg\,min}}}_{\mathcal {M} \in S} \max _{c \in C} \left| bp(\mathcal {M}, c)\right|$.

Although the problem defined above is our main focus, for the rest of this paper we will be talking in terms of the following problem which concerns itself with finding an approximately super-stable matching (i.e., a super-stable matching with the minimum number of super-blocking pairs). As we will see below, the reason we do the same is because both the problems are equivalent.

Problem 2

($\delta$-min-bp-super-stable-matching). Given a $\delta \in [0, 1]$ and an instance $\mathcal {I} = (\delta ', p_U, p_W)$, where $\delta ' \le \delta$ is the amount of missing information and $p_U, p_W$ are the preferences submitted by men and women respectively, compute $\mathcal {M}^{SS}_{opt}$ where $\mathcal {M}^{SS}_{opt} = {{\mathrm{arg\,min}}}_{\mathcal {M} \in S} \left| \text {super-bp}(\mathcal {M})\right|$ and $\text {super-bp}(\mathcal {M})$ is the set of super-blocking pairs associated with $\mathcal {M}$ for the instance $\mathcal {I}$.

Below we show that both the problems described above are equivalent. However, before that we prove the following lemma. Unfortunately, due to space constraints, all the proofs are omitted. We refer the reader to the full version of the paper² for all the proofs and for more detailed explanations.

Lemma 1

Let $\mathcal {M}$ be a matching associated with some instance $\mathcal {I} = (\delta , p_U, p_W)$, $\alpha$ denote the maximum number of blocking pairs associated with $\mathcal {M}$ for any completion of $\mathcal {I}$, and $\beta$ denote the number of super-blocking pairs associated with $\mathcal {M}$ for the instance $\mathcal {I}$. Then, $\alpha = \beta$.

Given the lemma above, we can now show the following theorem.

Theorem 1

For any $\delta \in [0, 1]$, the $\delta$-minimax-matching and $\delta$-min-bp-super-stable-matching problems are equivalent.

For the rest of this paper, we assume that we are always dealing with instances which do not have a super-stable matching as this can be checked in polynomial-time [12, Theorem 3.4]. So, now, in the context of the $\delta$-min-bp-super-stable-matching problem, it is easy to show that if the number of super-blocking pairs k in the optimal solution is a constant, then we can solve it in polynomial-time. We state this in the theorem below. Later, in Sect. 4, we will see that the problem is NP-hard, even to approximate.

Theorem 2

An exact solution to the $\delta$-min-bp-super-stable-matching problem can be computed in $\mathcal {O}(n^{2(k+1)})$ time, where k is the number of super-blocking pairs in the optimal solution.

3 Investigating Weakly-Stable Matchings

In this section we focus on situations where obvious blocking pairs are not permitted in the final matching. In particular, we explore the space of weakly-stable matchings and ask whether it is possible to find weakly-stable matchings that also provide good approximations to the $\delta$-min-bp-super-stable-matching problem (and thus the $\delta$-minimax-matching problem).

3.1 Approximating $\delta$-min-bp-super-stable-matching with Weakly-Stable Matchings

It has previously been established that a matching is weakly-stable if and only if it is stable with respect to at least one completion [16, Sect. 1.2]. Therefore, given this result, one immediate question that arises in the context of approximating the $\delta$-min-bp-super-stable-matching problem is “what if we just fill in the missing information arbitrarily and then compute a stable matching associated with such a completion?” This is the question we consider here, and we show that weakly-stable matchings do give a non-trivial (i.e., one that is $o(n^2)$, as any matching has only $\mathcal {O}(n^2)$ super-blocking pairs) approximation bound for our problem for certain values of $\delta$. The proof of the following theorem is through a simple application of the Cauchy-Schwarz inequality and due to space constraints is omitted.

Theorem 3

For any $\delta > 0$ and an instance $\mathcal {I} = (\delta ', p_U, p_W)$ where $\delta ' \le \delta$, any weakly-stable matching with respect to $\mathcal {I}$ gives an $\mathcal {O}\left( \min \left\{ n^3\delta , n^2\sqrt{\delta }\right\} \right)$-approximation for the $\delta$-min-bp-super-stable-matching problem.

3.2 Can We Do Better When Restricted to Weakly-Stable Matchings?

While Theorem 3 established an approximation factor for the $\delta$-min-bp-super-stable-matching problem when considering only weakly-stable matchings, it was simply based on arbitrarily filling-in the missing information. Therefore, there remains the question as to whether one can be clever about handling the missing information and as a result obtain improved approximation bounds. In this section we consider this question and show that for many values of $\delta$ the approximation factor obtained in Theorem 3 is asymptotically the best one can achieve when restricted to weakly-stable matchings.

Theorem 4

For any $\delta \in [\frac{16}{n^2}, \frac{1}{4}]$, if there exists an $\alpha$-approximation algorithm for $\delta$-min-bp-super-stable-matching that always returns a matching that is weakly-stable, then $\alpha \in \varOmega \left( n^2\sqrt{\delta }\right)$. Moreover, this result is true even if we allow only one side to specify ties and also insist that all the ties need to be at the top of the preference order.

3.3 The Case of One-Sided Top-Truncated Preferences: An $\mathcal {O}(n)$ Approximation Algorithm for $\delta$-min-bp-super-stable-matching

Although Theorem 4 is an inherently negative result, in this section we consider an interesting restriction on the preferences of the agents and show how this negative result can be circumvented. In particular, we consider the case where only agents on one side are allowed to specify ties and all the ties need to be at the bottom. Such a restriction has been looked at previously in the context of matching problems and as noted by Irving and Manlove [13] is one that appears in practise in the Scottish Foundation Allocation Scheme (SFAS). Additionally, restricting ties to only at the bottom models a very well-studied class of preferences known as top-truncated preferences, which has received considerable attention in the context of voting (see, for instance, [3]).

Top-truncated preferences model scenarios where an agent is certain about their most preferred choices, but is indifferent among the remaining ones or is unsure about them. More precisely, in our setting, the preference order submitted by, say, a woman w is said to be a top-truncated order if it is a linear order over a subset of U and the remaining men are all considered to be incomparable by w. In this section we consider one-sided top-truncated preferences, i.e., where only men or women are allowed to specify top-truncated orders, and show an $\mathcal {O}(n)$-approximation algorithm for $\delta$-min-bp-super-stable-matching under this setting. (Without loss of generality we assume throughout that only the women submit strict weak orders.) Although arbitrarily filling-in the missing information and computing the resulting weakly-stable matching can lead to an $\mathcal {O}(n^2\sqrt{\delta })$-approximate matching even for this restricted case (see the full version of the paper for an example), we will see that not all weakly-stable matchings are “bad” and that in fact the $\mathcal {O}(n)$-approximate matching we obtain is weakly-stable.

However, in order to arrive at this result, we first introduce the following problem which might be of independent interest. (To the best of our knowledge, this has not been previously considered in the literature.) Informally, in this problem we are given an instance $\mathcal {I}$ and are asked if we can delete some of the agents to ensure that the instance, when restricted to the remaining agents, will have a perfect super-stable matching.

Problem 3

(min-delete-super-stable-matching). Given an instance $\mathcal {I} = (\delta , p_U, p_W)$, where $\delta$ is the amount of missing information and $p_U, p_W$ are the preferences submitted by men and women respectively, compute the set D of minimum cardinality such that the instance $\mathcal {I}_{-D} = (\delta _{-D}, p_{U\setminus D}, p_{W\setminus D})$, where $\delta _{-D} = \frac{1}{|(U \cup W) \setminus D|}\sum _{i \in (U \cup W) \setminus D} \delta _i$, has a perfect super-stable matching (i.e., every agent in $(U \cup W) \setminus D$ is matched in a super-stable matching).

Below we first show that Algorithm 1 gives a 2-approximation for the min-delete-super-stable-matching problem when restricted to the case of one-sided top-truncated preferences. Subsequently, we then use this result in order to get an $\mathcal {O}(n)$-approximation for our problem. Intuitively, the main idea in Algorithm 1, which is inspired by the work of Tan [21], is that some of the entries in each agent’s preference list can be deleted by running the proposal-rejection sequence like in Gale-Shapley algorithm and through rotation eliminations, while at the same time maintaining at least one solution of the maximum size. Unfortunately, due to space constraints, we are unable to provide a complete analysis and so we refer the reader to the full version of the paper for detailed explanations and proofs.

Proposition 1

Algorithm 1 is a polynomial-time 2-approximation algorithm for the min-delete-super-stable-matching problem when restricted to the case of one-sided top-truncated preferences.

Given Proposition 1, we can now prove the following theorem.

Theorem 5

For any $\delta > 0$, Algorithm 1 is a polynomial-time $\mathcal {O}(n)$-approximation algorithm for the $\delta$-min-bp-super-stable-matching problem when restricted to the case of one-sided top-truncated preferences. Moreover, the matching it returns is also weakly-stable.

Before we end this section, we address one final question as to whether, for the class of one-sided top-truncated preferences, one can obtain a better approximation result if one continues to consider only weakly-stable matchings. In the theorem below we show that for $\delta \in \varOmega (\frac{1}{n})$ Algorithm 1 is asymptotically the best one can do under this restriction.

Theorem 6

For $\delta \le \frac{1}{2}$, if there exists an $\alpha$-approximation algorithm for $\delta$-min-bp-super-stable-matching that always returns a matching that is weakly-stable for the case of one-sided top-truncated preferences, then $\alpha \in \varOmega \left( \min \left\{ n^{\frac{3}{2}}\sqrt{\delta }, n\right\} \right)$.

4 Beyond Weak-Stability

In the previous section we investigated weakly-stable matchings and we showed several results concerning this situation. Here we move away from this restriction and explore what happens when we do not place any restriction on the matchings. In particular, we begin this section by showing a general hardness of approximation result, and then follow it with a discussion on one possible approach that can lead to a near-tight approximation result.

4.1 Inapproximability Result for $\delta$-min-bp-super-stable-matching

We show a hardness of approximation result for the $\delta$-min-bp-super-stable-matching problem through a gap-producing reduction from the Vertex Cover (VC) problem, which is a well-known NP-complete problem [14]. In the VC problem, we are given a graph $G=(V,E)$, where $V = \{v_1, \cdots , v_k\}$, and a $k_0 \le k$ and are asked if there exists a subset of the vertices with size less than or equal to $k_0$ such that it contains at least one endpoint of every edge.

Theorem 7

For any constant $\epsilon \in (0,1]$ and $\delta \in (0, 1)$, one cannot obtain a polynomial-time $(n\sqrt{\delta })^{1-\epsilon }$ approx. algorithm for the $\delta$-min-bp-super-stable-matching problem unless $P = NP$.

4.2 A Possible General Approach for Obtaining a Near-Tight Approximation Factor for $\delta$-min-bp-super-stable-matching

While obtaining a general near-optimal approximation result for the $\delta$-min-bp-super-stable-matching problem is still open, in this section we propose a potentially promising direction for this problem. In particular, we demonstrate how solving even a very relaxed version of the min-delete-stable-matching problem will be enough to get an $\mathcal {O}(n)$-approximation for $\delta$-min-bp-super-stable-matching in general. Below, we first define the relaxation in question, which we refer to as an $(\alpha , \beta )$-approximation to the min-delete-super-stable-matching problem.

Definition 5

($(\alpha , \beta )$-min-delete-super-stable-matching). Given an instance $\mathcal {I} = (\delta , p_U, p_W)$, compute a set $D'$ such that $|D'| \le \alpha \cdot |D_{opt}|$, where $|D_{opt}|$ is the size of the optimal solution to the min-delete-super-stable-matching for the same instance, and the instance $\mathcal {I}_{-D'} = (\delta _{-D'}, p_{U\setminus D'}, p_{W\setminus D'})$, where $\delta _{-D'} = \frac{1}{|(U \cup W) \setminus D'|}\sum _{i \in (U \cup W) \setminus D'} \delta _i$, has a matching with at most $\beta$ super-blocking pairs.

Next, we show that an $(\alpha , \beta )$-approximation to the min-delete-super-stable-matching problem gives us an $(\alpha n + \beta )$-approximation for $\delta$-min-bp-super-stable-matching. So, in particular, if we have an $(\alpha , \beta )$-approximation where $\alpha$ is a constant and $\beta \in \mathcal {O}(n)$, then this in turn gives us an $\mathcal {O}(n)$-approximation for $\delta$-min-bp-super-stable-matching in general.

Proposition 2

If there exists an $(\alpha , \beta )$-approximation algorithm for the min-delete-super-stable-matching problem, then there exists an $(\alpha n + \beta )$-approximation algorithm for the $\delta$-min-bp-super-stable-matching problem.

5 Conclusion

In this paper we initiated a study on matching with partial information in order to investigate what makes a matching “good” in this context, and to better understand the trade-off between the amount of missing information and the quality of different matchings. Towards this end, we introduced a measure for accounting for missing preference information in an instance, and argued that a natural definition of a “good” matching in this context is one that minimizes the maximum number of blocking pairs with respect to all the possible completions. Subsequently, using an equivalent problem ($\delta$-min-bp-super-stable-matching) we first explored the space of matchings that contained no obvious blocking pairs (i.e., weakly-stable matchings) in order to better understand how missing preference information effected/affected the quality, in terms of approximation with respect to the objective of minimizing the number of super-blocking pairs. Later on, by expanding the space of matchings we considered (i.e., removing the restriction that matches must be weakly-stable), we asked whether it was possible to improve on the approximation factors that were achieved under the restriction to weakly-stable matchings.

There are a number of interesting directions for future work. First, while in Sect. 4.2 we proposed one possible approach that can lead to near-tight approximations, there may be other approaches that can prove fruitful. Second, we believe that the min-delete-super-stable-matching problem, and its relaxation we introduced, are both of independent interest, and so an open question is to see if one can obtain general results on them. In Proposition 1 we saw that a 2-approximation was achievable for the case of one-sided top-truncated preferences and hence it would also be interesting to determine if there are other interesting classes of preferences for which constant-factor approximations are possible. Finally, there are possible extensions, like, for instance, allowing incompleteness—meaning the agents can specify that they are willing to be matched to only a subset of the agents on the other set—that one could consider and ask similar questions like the ones we considered.