# necessarily_optimal_onesided_matchings__1dfef3a0.pdf

Necessarily Optimal One-Sided Matchings

Hadi Hosseini,1 Vijay Menon,2 Nisarg Shah,3 Sujoy Sikdar 4

1 College of Information Sciences and Technology, Penn State University 2 David R. Cheriton School of Computer Science, University of Waterloo 3 Department of Computer Science, University of Toronto 4 Department of Computer Science, Binghamton University hadi@psu.edu, vijay.menon@uwaterloo.ca, nisarg@cs.toronto.edu, ssikdar@binghamton.edu

We study the classical problem of matching n agents to n objects, where the agents have ranked preferences over the objects. We focus on two popular desiderata from the matching literature: Pareto optimality and rank-maximality. Instead of asking the agents to report their complete preferences, our goal is to learn a desirable matching from partial preferences, speciﬁcally a matching that is necessarily Pareto optimal (NPO) or necessarily rank-maximal (NRM) under any completion of the partial preferences. We focus on the topk model in which agents reveal a preﬁx of their preference rankings. We design efﬁcient algorithms to check if a given matching is NPO or NRM, and to check whether such a matching exists given top-k partial preferences. We also study online algorithms for eliciting partial preferences adaptively, and prove bounds on their competitive ratio.

1 Introduction

Resource allocation is a fundamental problem in artiﬁcial intelligence and multi-agent systems. One particular type of resource allocation deals with assigning a number of indivisible objects to agents according to their preferences. These problems have given rise to a wide array of research in economics (Moulin 2004) and theoretical computer science (Manlove 2013). The focus of our work is the special case of allocating n objects to n agents (so each agent is matched to a single object), which models many real-world applications (see, e.g., (Hylland and Zeckhauser 1979; Abdulkadiro glu and S onmez 1999)). For instance, imagine allocating ofﬁce spaces to faculty members in a building. Instead of asking each faculty member to report a full preference ranking over the available ofﬁces, the department head may ask them to reveal their top choices, and then, if need be, she may ask individual faculty members to reveal their next best choices, and so on. The goal is to come up with a matching that necessarily satisﬁes some form of economic efﬁciency while asking as few queries as possible. That is, it must satisfy the economic efﬁciency property regardless of the parts of the preferences that were not elicited, because otherwise some faculty may ﬁnd the ﬁnal matching undesirable.

Copyright c 2021, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

What form of economic efﬁciency might one want for a matching? Luckily, decades of research in matching theory offers two prominent desiderata: Pareto optimality (Shapley and Scarf 1974; Cirillo 2012) and rank-maximality (Irving 2003; Irving et al. 2006). Informally, Pareto optimality requires that no other matching be able to make some agents better off without making any agent worse off. Despite its wide use, Pareto optimality may be a weak guarantee in many practical settings. Hence, a stronger guarantee called rank-maximality is often used in practical applications such as assigning papers to referees (Garg et al. 2010), assigning rented resources to customers (Abraham et al. 2006), and assigning students to schools (Abraham 2009). Informally, rank-maximality requires matching as many agents to their top choice as possible, subject to that matching as many agents to their second choice as possible, and so on. The study of these axioms, along with axioms of fairness and incentive-compatibility, has led to the design of elegant rules such as random priority and probabilistic serial (Bogomolnaia and Moulin 2001; Che and Kojima 2010), which have been made easily accessible by not-for-proﬁt endeavors such as Match U.ai (www.matchu.ai). However, in many real-life situations, one rarely has access to complete preferences which can simply be fed to these rules. More often than not, the problem at hand is to come up with a desirable matching of agents to objects with only partial information about agents preferences. While the role of partial preferences has been well-explored in the sister problem known as two-sided matching (Rastegari et al. 2013; Liu et al. 2014), in which agents are matched to other agents (for example matching roommates, kidney donors to patients, or men to women), it has been signiﬁcantly understudied for one-sided matching. This is the primary focus of our work. In particular, we consider the following three research questions. Given partial preferences, can we efﬁciently check if a given matching is NPO or NRM? Can we efﬁciently check if an NPO or NRM matching exists (and if so, ﬁnd one)? How much online elicitation of preferences is needed to ﬁnd an NPO or NRM matching?

Our Results We study the next-best query model which allows, in each query, asking one agent to reveal her next best choice. Partial preferences elicited under this model are referred to as

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

top-k preferences as each agent reveals a preﬁx of her preference ranking consisting of the top k items (where k can be different for each agent). As mentioned above, our goal is to design online algorithms that ask few queries and learn a matching that is necessarily Pareto optimal or necessarily rank-maximal w.r.t. the elicited partial preferences. We study their performance in terms of their competitive ratio (Borodin and El-Yaniv 2005). Note that these algorithms need to check if there already exists a matching that is NPO or NRM w.r.t. the elicited preferences in order to decide if further elicitation is required. Along the way, it is also useful to know if a given matching is NPO or NRM w.r.t. the given partial preferences. Thus, we also study these two questions for NPO and NRM. For necessary Pareto optimality, we show that checking whether a given matching is NPO reduces to computing the maximum weight matching in a bipartite graph, which can be solved efﬁciently. We also show that there exists an NPO matching if and only if there exists a matching that matches at least n 1 agents to objects they have revealed, where n is the number of agents; this can be checked in polynomialtime, and if this is the case, our algorithm efﬁciently ﬁnds an NPO matching. Our main result is an online algorithm for ﬁnding an NPO matching that has a competitive ratio of O( n). By proving a matching lower bound, we show that our algorithm is asymptotically optimal. For necessary rank-maximality, we design efﬁcient algorithms for checking whether a given matching is NRM. For checking whether an NRM matching exists; unlike in the case of NPO, these questions do not seem to reduce to checking a simple analytical condition. In the supplementary material, we show that a simple characterization can be obtained in the special case where each agent has revealed exactly the same number of objects. For online elicitation, we show a constant lower bound on the competitive ratio, and conjecture that the optimal competitive ratio is in fact constant, unlike in the case of NPO.

Related Work The problem of matching n agents to n objects models a number of scenarios and is well-studied, sometimes as the house allocation or one-to-one object allocation problem (e.g., (Hylland and Zeckhauser 1979; Abdulkadiro glu and S onmez 1998; Abraham et al. 2004; Irving 2003)). There are two approaches to learning a desirable matching given only partial information about agents preferences. One approach is to consider the worst case scenario over missing preferences; imposing a property X in the worst case leads to the necessarily X concept. This concept has been considered in other contexts such as in voting (Xia and Conitzer 2011) and in one-sided matching problems where an agent may be assigned to more than one good (Bouveret, Endriss, and Lang 2010; Aziz et al. 2015, 2019b). However, in the latter case, even having access to agents full preference rankings over individual goods is not sufﬁcient for checking Pareto optimality, which leads Aziz et al. (2019b) to consider NPO given full rankings. In contrast, in our one-to-one matching setting, full preference rankings over individual goods are sufﬁcient to check whether a given matching is PO, which

leads us to consider partial (top-k) rankings. Another approach is to assume that the underlying preferences are drawn from a known distribution (Rastegari et al. 2013), and consider the probability of satisfying X (Aziz et al. 2019a). We note that asking whether a matching satisﬁes X with probability 1 often coincides with the necessarily X concept. We focus on the top-k model of partial preferences, which is commonly used in the literature (Aziz, Walsh, and Xia 2015; Drummond and Boutilier 2013). However, there are also other interesting models; one such model is where the information available regarding each agent s preferences is in the form of a set of pairwise comparisons among objects (Aziz et al. 2019a). In general, the goal of this line of work is to make matching algorithms more practically relevant, to which our work contributes. Other than economic efﬁciency, researchers have also focused on notions of fairness and incentive-compatibility in matching agents to objects, which has led to the design of rules such as random priority and probabilistic serial (Bogomolnaia and Moulin 2001; Abdulkadiro glu and S onmez 1998; Hosseini, Larson, and Cohen 2018). A related line of research considers two-sided matching markets, where agents are matched to other agents. Working with partial preferences is well-explored in such markets (Rastegari et al. 2013; Liu et al. 2014).

2 Preliminaries

Let N = {a1, , an} denote the set of agents and O = {o1, , on} be the set of objects. We use [k] to denote the set {1, . . . , k}. Thus, for i [n], ai and oi represent agent and object i respectively. A matching of agents to objects is a bijection M : N O. We sometimes refer to a matching as a collection of pairs {(ai, M(ai) | i [n])} and use M to denote the set of all possible matchings. Each agent ai N has an underlying linear order Ri over O, where a linear order over O is a transitive, antisymmetric, and total relation on O. We use L(O) to denote the set of all linear orders over O, and refer to R = (R1, , Rn) L(O)n as a (complete) preference proﬁle. Additionally, for i, j, k [n], if ai prefers oj to ok according to Ri, then we denote this by oj Ri ok or ok Ri oj. We formally describe two notions of economic efﬁciency, namely Pareto optimality and rank-maximality.

Deﬁnition 1 (Pareto optimality). Given a preference proﬁle R = (R1, . . . , Rn), a matching M is said to be Pareto optimal w.r.t. R if no other matching can make an agent happier without making some other agent less happy, i.e., if M M : ( ai N, M (ai) Ri M(ai)) aj N, M (aj) Rj M(aj) .

Deﬁnition 2 (rank-maximality). Given a preference proﬁle R and a matching M, let the signature of M w.r.t. R, denoted sig R(M), be the tuple (x1, . . . , xn), where xℓis the number of (ai, oj) M such that oj is the ℓth most preferred choice of ai. We say that (x1, . . . , xn) sig (x 1, . . . , x n) if k [n] such that xk > x k and xi = x i for all i < k; this is the lexicographic comparison of signatures. A matching

M is rank-maximal w.r.t. R if sig R(M) is maximum under sig. In words, a matching is rank-maximal if it matches max. number of agents to their top choice, subject to that the max. number of agents to their second choice, and so on.

Partial Preferences In this paper, we study a partial preference model called topk preferences, in which each agent i may reveal a preﬁx of her preference ranking, that is, a ranking of her ki most favorite objects for some ki [n]. Speciﬁcally, agent i may reveal Pi which is a linear order over some L O such that any object in L are preferred to any object in L \ O by the agent; we say that agent i has revealed object o in Pi if o L. Also, we sometimes use |Pi| = |L| = ki to denote the size of Pi, i.e., the number of objects revealed in Pi. We refer to P = (P1, . . . , Pn) as a top-k preference proﬁle and say that a linear order Ri is consistent with Pi if, for all j, k [n], oj Pi ok oj Ri ok. We use C(Pi) to denote the set of linear orders over O that are consistent with Pi, and C(P) to denote C(P1) . . . C(Pn). Given a top-k preference proﬁle P = (P1, , Pn), we use rev(P) to denote the set of all pairs (ai, oj) such that ai has revealed object oj in Pi, and unrev(P) to denote (N O) \ rev(P). Throughout, whenever we refer to the size of a matching M w.r.t. to P, we mean |M rev(P)|. We are interested in the notion of necessarily efﬁcient matchings, which are guaranteed to satisfy an efﬁciency notion such as Pareto optimality or rank-maximality given only a top-k preference proﬁle (Gaspers et al. 2014; Xia and Conitzer 2011; Aziz, Walsh, and Xia 2015). Deﬁnition 3 (necessary Pareto optimality (NPO) and necessary rank-maximality (NRM)). Given a top-k preference proﬁle P, a matching M is said to be necessarily Pareto optimal (resp. necessarily rank-maximal) w.r.t. P if it is Pareto optimal (resp. rank-maximal) w.r.t. any proﬁle of linear orders that is consistent with P, i.e., for any R C(P).

Query Model and Elicitation We consider algorithms that can elicit preferences by asking agents to reveal their next-best objects meaning if the agent has already revealed their k 1 most preferred objects, then it asks the agent to reveal their k-th most preferred object. We formally deﬁne this query model below. Deﬁnition 4 (next-best query model). For ai N and k [n], query Q(ai, k), which asks agent ai to reveal the object in the k-th position in her preference list, is a valid query in the next-best query model if query Q(ai, j) has already been made for all j [k 1]. We are interested in online elicitation algorithms that ﬁnd NPO or NRM matchings in the next-best query model and measure their performance against an all-powerful optimal algorithm. An all-powerful optimal algorithm is a hypothetical ofﬂine algorithm that can identify the minimum number of queries of the form Q(ai, j) that are sufﬁcient to guarantee an NPO or NRM matching. That is, for i [n] and ki [n], the optimal algorithm can minimize P i [n] ki, and can claim that asking every agent i for their top-ki order, Pi, is sufﬁcient to compute a matching that is NPO or

NRM w.r.t. all consistent completions of P = (P1, . . . , Pn). We say that an online elicitation algorithm is α-competitive (or, equivalently, it achieves a competitive ratio of α) if the number of queries it requires to ask in the worst-case across all possible instances is at most α OPT, where OPT is the number of queries asked by the optimal algorithm.

3 Necessarily Pareto Optimal Matchings We begin, in Section 3, by presenting an algorithm that determines if a given matching is NPO w.r.t. to a proﬁle of top-k preferences. Following this, we provide a useful characterization for when NPO matchings exist. This in turn is used in Section 3 in designing an elicitation algorithm that is 2( n + 1)-competitive. We also show that no elicitation algorithm can achieve a competitive ratio of o( n), establishing our algorithm as asymptotically optimal.

Determining Whether a Matching is NPO We present a polynomial time algorithm to determine whether a given matching M is NPO w.r.t. a proﬁle of top-k preferences P. The algorithm proceeds in two steps: In Step 1, we build a directed graph G = (N, E), where E consists of directed edges (ai, aj) such that M(aj) Ri M(ai) under some Ri C(Pi). That is, there exists an edge when agent i prefers the object allocated to agent j over her own under some completion of her partial preferences. In Step 2, we efﬁciently check if this directed graph admits a cycle. If it does, matching M is not NPO; otherwise, it is NPO.

Theorem 1. Given a top-k preference proﬁle P and a matching M, there is a polynomial time algorithm to check if M is NPO w.r.t. P.

Proof. We claim that the algorithm described above formally presented as Algorithm 1 in the full version (Hosseini et al. 2020) is such an algorithm. First, let us prove its correctness. The key observation, which the reader can easily verify, is that the graph G constructed in Step 1 contains an edge (ai, aj) if and only if there exists a completion Ri C(Pi) under which M(aj) Ri M(ai). This includes edges (ai, aj) for which M(aj) Pi M(ai) is already true under the top-k preference order Pi. Suppose the algorithm returns NO. Then, G has a cycle. Let C be one such cycle. Construct a matching, M , from M as follows: if agent i has an outgoing edge (ai, aj) C in the cycle, set M (ai) = M(aj), and if agent i is not part of cycle C, then set M (ai) = M(ai). It is easy to verify that M is a matching. Let R = (R1, . . . , Rn) C(P) be a completion such that if agent i has an outgoing edge (ai, aj) C in the cycle, then Ri C(Pi) satisﬁes M (ai) = M(aj) Ri M(ai), and otherwise Ri C(Pi) is chosen arbitrarily. Then, it is easy to see that for each agent i who is a part of cycle C, we have M (ai) Ri M(ai), and for every remaining agent i, we have M (ai) = M(ai). Thus, M Pareto-dominates M under the completion R C(P), which implies that M is not NPO w.r.t. P, as desired. Conversely, suppose M is not NPO w.r.t. P. Hence, there exists a matching M and a completion R C(P) such

that M Pareto-dominates M under R. We claim that G must have a cycle, and the algorithm therefore must return NO. To see this, consider the graph G = (N, E ) where, for ai = aj, (ai, aj) E , if M assigns to agent i the object that was assigned to agent j under M, i.e., if M (ai) = M(aj) = M(ai). Note that in G , each agent i either has exactly one incoming and one outgoing edge, or no incident edges. Hence, G is a union of disjoint cycles. In particular, G has at least one cycle. However, since M Pareto-dominates M under R, for every edge (ai, aj) E , we have that M (ai) = M(aj) Ri M(ai). Hence, by the observation above, edge (ai, aj) must also exist in G. Thus, G is a subgraph of G. Since G has at least one cycle, so does G, as desired. Finally, Algorithm 5 runs in polynomial time because constructing G and checking whether G has a cycle can be done in O(n2) time (the latter using depth-ﬁrst search).

At a high level, correctness of the algorithm follows from the observation that if there is a cycle in the directed graph constructed above, then one can construct a complete preference proﬁle R C(P) such that each agent in the cycle strictly prefers the object allocated to the next agent in the cycle under M. Then, trading objects along this cycle would result in a matching M that, under this completion R, Pareto-dominates M, establishing that M is not NPO.

Computing an NPO Matching, When It Exists

Next, we ﬁnd a necessary and sufﬁcient condition for a given top-k preference proﬁle P to admit an NPO matching. In the case that an NPO matching exists, we also provide an algorithm to compute one in polynomial time.

Theorem 2. A top-k preference proﬁle P admits an NPO matching if and only if there is a matching of size at least n 1 w.r.t. P. Moreover, there is a polynomial time algorithm to determine whether a top-k preference proﬁle admits an NPO matching, and to compute an NPO matching if it exists.

Proof. ( ) Consider a top-k preference proﬁle P that admits an NPO matching M. Suppose for the sake of contradiction that there is no matching w.r.t. P that is of size larger than n 2. Then, |M rev(P)| n 2, which implies that there are at least two agents, w.l.o.g. agents a1 and a2, who are matched to objects they have not revealed under P. It is easy to see that one can now construct a completion R C(P) such that M(a2) R1 M(a1) and M(a1) R2 M(a2). Under this completion, exchanging the objects assigned to a1 and a2 would Pareto-dominate M, contradicting the fact that M is NPO w.r.t. P. ( ) Let P be a top-k preference proﬁle such that there exists a matching of size at least n 1 w.r.t. P. Construct a weighted bipartite graph G = (N O, rev(P)), where each edge (ai, oj) rev(P) has weight equal to the rank of oj in Pi. Let M be a matching of min. weight among all matchings of max. cardinality in G. Note that |M| n 1. Let us ﬁrst consider the case when |M| = n. If so, then it is easy to see that M is an NPO matching w.r.t. P. This is because any matching that Pareto-dominates M in any

completion R C(P) must have size n w.r.t. P as well and a strictly lower weight than M, which is a contradiction. Now, consider the case when |M| = n 1. So exactly one agent and one object are not matched. Without loss of generality, suppose these are an and on. Construct a matching c M of our problem by adding (an, on) to M. Thus, |c M rev(P)| = |M| = n 1. We wish to show that c M is NPO. Suppose for the sake of contradiction that there exists a matching M which Pareto dominates c M w.r.t. some completion R C(P). Hence, M must assign each agent an object she prefers (under R) at least much as what she receives under c M, and at least one agent a strictly better (under R) object than what she receives under c M. Thus, M , when viewed as a matching in G, must have cardinality n 1 and weight at most the weight of M. Further, weight of M is equal to the weight of M only if M assigns each agent ai = an the same object that c M assigns. However, any two matchings that differ must differ in the assignment to at least two agents. Hence, we have that M is a matching in G with cardinality n 1 and weight strictly less than the weight of M, which is a contradiction. Now, we provide a polynomial-time algorithm to compute an NPO matching, when it exists. From the argument above, it is sufﬁcient to be able to compute a min-weight maxcardinality matching M of the graph G. This can be done in polynomial time using the Hungarian algorithm (Munkres 1957). Then, if |M| = n, the algorithm returns M, and if |M| = n 1, the algorithm returns c M by adding the unmatched agent-object pair.

Elicitation to Compute an NPO Matching In this section we turn to the question of elicitation. As mentioned in Section 2, we use the next-best query model, and informally our main goal is to understand how to elicit as little information as possible in order to compute an NPO matching. Towards this end, we ﬁrst prove, in Theorem 3, a lower bound that shows that any elicitation algorithm has a competitive ratio of Ω( n). Due to space constraints, the proof appears in the full version (Hosseini et al. 2020). Theorem 3. In the next-best query model, if there exists an α-competitive elicitation algorithm for ﬁnding a necessarily Pareto optimal matching, then α Ω( n). A natural strategy to elicit preferences is to simultaneously ask all the n agents to reveal their next best object until the point at which the designer has enough information to compute an NPO matching. Recall that we can check the latter condition at every step by leveraging our Theorem 2 from Section 3. Although this approach is natural, it is not difﬁcult to see that it results in a competitive ratio of Ω(n). Let us describe the high-level idea of our algorithm (Algorithm 1), although the exact details vary slightly in the algorithm in order to optimize the competitive ratio. We follow the aforementioned na ıve approach of asking all agents to report their next best object only up to a point where we can match at least n n agents to objects they have revealed. At that point, we compute one such matching, focus on the unmatched agents (at most n of them), and then

Input: A proﬁle of top-k preferences P = (P1, . . . , Pn), a set of agents N, and a set of objects O. Output: An NPO matching 1: for each i [n], initialize Pi = 2: M ; k 1; s |M| 3: while s < (n 1) do 4: if s (n 1) min({k 1, n}) then 5: for each i [n] do 6: o Q(ai, |Pi| + 1) 7: update Pi by adding object o at position |Pi|+1 8: end for 9: else if s > (n 1) min({k 1, n}) then 10: U the set of unmatched agents in M 11: for each i U do 12: o Q(ai, |Pi| + 1) 13: update Pi by adding object o at position |Pi|+1 14: end for 15: end if 16: k k + 1 17: M max. matching in G (N O, rev(P)) 18: s |M| 19: end while 20: use algorithm described in Theorem 2 to return a matching that is NPO w.r.t. P = (P1, , Pn)

Algorithm 1: A 2( n+1)-competitive elicitation algorithm

just ask these agents for their next best object until there is a matching of size at least n 1, which, by Theorem 2, is a sufﬁcient condition for the existence of an NPO matching. Once we know an NPO matching exists, we use the polynomial time algorithm from Theorem 2 to ﬁnd one. This strategy, with the details optimized, results in an improved competitive ratio of 2( n + 1), which, given Theorem 3, is asymptotically optimal.

Theorem 4. Algorithm 1 is a 2( n + 1)-competitive elicitation algorithm in the next-best query model for computing a necessarily Pareto optimal matching.

In order to prove this result, we ﬁrst introduce the following notation. We maintain a graph G = (N O, rev(P)), where P denotes the top-k preference proﬁle elicited so far. Let sj denote the size of the maximum matching in this graph during the j-th iteration of line 3. Next, let m denote the number of times lines 4 8 are run in Algorithm 1. Note that m 1 (since s1 = 0 and hence lines 4 8 are executed at least during the ﬁrst iteration), and that the total number of iterations of the algorithm is m + 1 (since the else if , i.e., lines 9 15 is executed just once). Also, note that for all j [m], sj is also the size of the maximum matching when all agents have revealed their top (j 1) objects in Algorithm 1. Finally, for j [m], let Xj denote the number of agents who are asked at least j queries by the optimal algorithm. Now, we have the following claim, whose proof appears in the full version (Hosseini et al. 2020).

Claim 1. For every j [m], Xj (n sj 1).

Equipped with the notations and the claim above, we can now prove our theorem.

Proof of Theorem 4. Let ALG denote the number of queries

asked in Algorithm 1 and m be as deﬁned above. Since the algorithm asks n queries during each time lines 4 8 is run and it asks at most (n sm+1) (n m) queries during the execution of lines 9 15 (the ﬁrst term is maximum number of agents in set U in line 10 and the second arises from the fact that all these agents have revealed their top m preferences), we have that

ALG n m + (n sm+1) (n m)

< n m + (min({m, n}) + 1) (n m), (1)

where the second step follows from the fact that (n sm+1) < (1 + min({m, n})) (see line 9 in Algorithm 1). Next, let OPT denote the number of queries asked by the optimal algorithm. From Claim 1 we know that Xj, which is the number of agents who are asked at least j queries by the optimal algorithm, is at least (n sj 1). Therefore,

j=1 (m j) (Xm j Xm j+1)

= Xm + Xm 1 + + X1

j=2 (n sj 1)

(using Claim 1 and the fact that s1 = 0) n 1 + (m 1) (n sm 1) (since j [m], sj sj+1)

n 1 + (m 1) min({m 1, n}), (2)

where the ﬁnal inequality follows from the fact that (n 1 sm) min({m 1, n}) (see line 4 in Algorithm 1). Therefore, using (1) and (2), we have

OPT n m + (min({m, n}) + 1) (n m)

n 1 + (m 1) min({m 1, n}) 2(min({m, n}) + 1),

where the last inequality follows by using n 2, m 1, and by considering the cases m n and m > n.

4 Necessarily Rank-Maximal Matchings In the previous section, we devised algorithms for computing an NPO matching when one exists and when given a top-k preference proﬁle, and for eliciting a small amount of information to determine such matchings. Here, we focus on rank-maximality, which is a stronger notion of economic efﬁciency than Pareto optimality and widely used in real-world applications (see, e.g., (Garg et al. 2010; Abraham et al. 2006; Abraham 2009)). To illustrate this notion, consider the top-k preference proﬁle P with three agents, where P1 = o1 o2 o3, P2 = o1 o2 and P3 = o1. The matching M = {(a1, o3), (a2, o2), (a3, o1)} is NPO, but not NRM. To see this, consider the completion R of P, where R1 = o1 o2 o3, R2 = o1 o2 o3, and R3 = o1 o3 o2. While M has signature (1, 1, 1) under R, matching M = {(a1, o1), (a2, o2), (a3, o3)} has a better signature (1, 2, 0) under R. In fact, it is easy to verify that M is NRM w.r.t. P.

We begin, in Section 4, by presenting an algorithm that determines whether a given matching is necessarily rankmaximal (NRM) w.r.t. a given top-k preference proﬁle. In Section 4, we build upon this algorithm to design another algorithm that decides if a given top-k preference proﬁle admits an NRM matching, and computes one if it does. Finally, we turn to the elicitation question, where we provide a lower bound on the competitive ratio of any elicitation algorithm that returns an NRM matching. We ﬁrst introduce necessary additional deﬁnitions and notations.

Deﬁnition 5 (rank-maximality w.r.t. top-k preferences). Given a top-k preference proﬁle P and a matching M, let the signature of M w.r.t. P, denoted sig P (M), be the tuple (x1, . . . , xn), where xℓis the number of (ai, oj) M rev(P) such that oj is the ℓth most preferred choice of ai. We say that (x1, . . . , xn) sig (x 1, . . . , x n) if there exists a h [n] such that xh > x h and xi = x i for all i < h; this is the lexicographic comparison of signatures. A matching M is rank-maximal w.r.t. P if sig P (M) is maximum under sig. In plain words, a matching is rank-maximal w.r.t. partial preference proﬁle P if it maximizes the number of agents matched to their top choice, subject to that the number of agents matched to their second choice, and so on.

Deﬁnition 6 (Extended signature). Following Deﬁnition 2, we deﬁne the extended signature of a matching M w.r.t. P, denoted extsig P (M), to be the tuple (x1, . . . , xn), where, for all i [n 1], xi is deﬁned as in sig P (M), while xn counts not only the number of agents matched to their nth choice revealed in P, but also the number of agents matched to an object they did not reveal in P.

Deﬁnition 7 (Optimal signature). Given a top-k preference proﬁle P over a subset of agents S N and a subset of objects T O, as well as a set of forbidden pairs F S T, let M(S, T, F) denote the set of all matchings M that match agents in S to objects in T and satisfy M F = . We deﬁne sigopt P (S, T, F) = sup M M(S,T,F ),R C(P ) sig R(M). Informally, this is the best possible signature that any matching can achieve under any completion of P while avoiding pairings from F. We use arg sigopt P (S, T, F) to denote the matching M M(S, T, F) that obtains this best signature under some completion R C(P). Note that sometimes we use sigopt P to denote sigopt P (N, O, ).

Determining Whether a Matching is NRM At a high level, our algorithm to determine if a given matching M is NRM under a given top-k preference proﬁle P works as follows. It leverages the fact that given any S N, T O, and F S T, we can efﬁciently compute sigopt P (S, T, F). Algorithm 2 formally describes how to do this; the proof of its correctness is in the full version. Given this, our algorithm ﬁrst checks if M has size at least n 1 w.r.t. P; this is necessary for M to even be NPO w.r.t. P, as the proof of Theorem 2 shows. If M has size n w.r.t. P, then we argue that its signature w.r.t. P (which is the same as its signature w.r.t. any completion R of P) must be sigopt P . On the other hand, suppose M has size n 1 w.r.t. P, with (ai, oj) M unrev(P) being the pair where an agent

Input: A top-k preference proﬁle P over a set of agents S N and a set of objects T O, and F S T. Output: sigopt P (S, T, F) and arg sigopt P (S, T, F) 1: For all ai S, let ki |Pi| 2: P weak order proﬁle which matches P on the preferences revealed under P, and for every (ai, oj) unrev(P), has object oj at position ki + 1 in P i 3: Create a bipartite graph G = (S T, E), where E = S T \ F, and each edge (ai, oj) E is labelled with ℓ if oj appears in position ℓin P i. 4: M compute a rank-maximal matching of G using the algorithm by Irving et al. (2006) 5: return sig P (M) and M

Algorithm 2: Algorithm to compute sigopt P (S, T, F) and arg sigopt P (S, T, F).

Input: A top-k preference proﬁle P, a set of agents N, a set of objects O, and a matching M. Output: Is M NRM w.r.t. P? 1: c |M rev(P)|. 2: if c = n and sig P (M) = sigopt P then 3: return YES 4: else if c = n 1 then 5: Pick (ai, oj) M unrev(P) this is unique since M has cardinality n 1 w.r.t. P. 6: if sig P (M) sig sigopt P (N \ {ai}, O \ {oj}, ) and extsig P (M) sig sigopt P (N, O, {(ai, oj)}) then 7: return YES 8: end if 9: end if 10: return NO

Algorithm 3: Algorithm to check if a given matching is NRM given a top-k preference proﬁle.

is matched to an object she did not reveal under P. Then, we argue that two conditions need to be met: (a) to ensure that another matching M with (ai, oj) M cannot have a better signature under any completion R, we require that the signature of M w.r.t. P be at least as good as sigopt P (N \ {ai} , O \ {oj} , ), and (b) to ensure that another matching M with (ai, oj) / M cannot have a better signature under any completion R, we require that the extended signature of M w.r.t. P be at least as good as sigopt P (N, O, {(ai, oj)}). Algorithm 3 formalizes this and the proof of its correctness (claimed below) appears in the full version.

Theorem 5. Given a top-k preference proﬁle P and a matching M, there exists a polynomial-time algorithm that determines if M is NRM w.r.t. P.

Computing an NRM matching, When It Exists

The results from Section 4 are key to devising an algorithm that determines if a given top-k preference proﬁle admits an NRM matching and computes one if it does. Speciﬁcally, note again that a matching that is NRM w.r.t. a top-k preference proﬁle P must have size at least n 1 w.r.t. P. If there is an NRM matching of size n w.r.t. P, then we argue that it

Input: A top-k preference proﬁle P, agents N, and objects O. Output: Returns an NRM matching if P admits one, and returns NO otherwise. 1: M rank-maximal matching w.r.t. P 2: if |M rev(P)| = n and sig P (M) = sigopt P then 3: return M

4: else 5: for (ai, oj) unrev(P) do 6: X rank-maximal matching of N \ {ai} to O \ {oj} w.r.t. P 7: M X {(ai, oj)} 8: if M is NRM w.r.t. P, then return M

9: end for 10: end if 11: return NO

Algorithm 4: Algorithm to check if an NRM matching exists given a top-k preference proﬁle.

must be rank-maximal w.r.t. P and have signature sigopt P . We can check this efﬁcienty using the results from Section 4. If there is an NRM matching of size n 1 w.r.t. P with (ai, oj) M unrev(P), then we argue that M \ {(ai, oj)} must be a rank-maximal matching of N \ {ai} to O \ {oj} w.r.t. P. By iterating over all agent-object pairs (ai, oj), we can again check this efﬁciently. Algorithm 4 formalizes this and the next result proves its correctness. Theorem 6. Given a top-k preference proﬁle P, there exists a polynomial-time algorithm that returns a necessarily rankmaximal matching if one exists, and returns NO otherwise.

Proof. We want to show that P admits an NRM matching if and only if Algorithm 4 returns a matching (i.e. does not return NO). Moreover, in case that the algorithm returns a matching, we want to show that it is in fact NRM w.r.t. P. ( ) Let M be an NRM matching w.r.t. P. Then, it must be NPO w.r.t. P. Hence, as we show in the proof of Theorem 2, M must have size at least n 1 w.r.t. P. So, we again have the following two cases. Either M is a perfect matching w.r.t. P, which we refer to as Case (a) below, or M is of size n 1 w.r.t. P, which we refer to as Case (b) below. Case (a). Observe that sig P (M) = sig R(M) for all R C(P) since M is a perfect matching w.r.t. P. Second, note that sig P (M) = sigopt P , since otherwise it follows from the deﬁnition of sigopt P that there is a matching M and a completion R C(P) such that sig R(M ) sig sig R(M) = sig P (M), which in turn contradicts the fact that M is NRM w.r.t. P. Finally, it is easy to see that since M has size n w.r.t. P and it is NRM w.r.t. P, it has to be rank-maximal w.r.t. to P. Combining these observations, we have that any matching M that is a rank-maximal matching w.r.t. P must have size n and the same signature (under P) as sigopt P . Hence, the check in line 2 will succeed, and the algorithm will return matching M , which is NRM w.r.t. P. Case (b). Let (ai, oj) M unrev(P). As in Case (a), we can argue that M \ {(ai, oj)} is NRM w.r.t. P among all matchings that match N \ {ai} to O \ {oj}. Let X be any matching of N \{ai} to O \{oj} that is rank-maximal w.r.t. P. Then, this implies that X {(ai, oj)} is also an NRM

matching. Observe that this is precisely the condition that is checked in line 8 of Algorithm 4. Hence, the algorithm returns an NRM matching w.r.t. P in this case too. ( ) Suppose P does not have an NRM matching. Note that Algorithm 4 returns a matching only under two cases. First is when there is a matching M such that M is of size n w.r.t. P and has the same signature as sigopt P . Note that if such a matching exists, then it is easy to see from the deﬁnition of sigopt P and the fact that M is a perfect matching w.r.t. P that it has to be NRM w.r.t. P, which in turn contradicts our assumption that P does not have an NRM. The other case is when Algorithm 4 returns a matching in line 8, and here, the proof trivially follows from Theorem 5, which proves the correctness of Algorithm 3. Finally, one can see that Algorithm 4 runs in polynomial time since Algorithms 2 and 3 run in polynomial time.

Elicitation to Compute an NRM Matching We are now ready to consider the question of eliciting information to compute an NRM matching. Below we provide a lower bound on the competitive ratio of any elicitation algorithm (the proof is in the full version (Hosseini et al. 2020)).

Theorem 7. In the next-best query model, for n 2, if there exists an α-competitive elicitation algorithm for ﬁnding a necessarily rank-maximal matching, then α 4

n, if n is even, and α 4

3 20 9n 3, if n is odd.

Note that our lower bound converges to 4

3 as n goes to inﬁnity. So, a natural question is whether one can design an online algorithm to compute an NRM matching that has constant competitive ratio. We conjecture that this should be possible, but leave it as an open problem for future work.

5 Discussion As discussed in Section 4, the most immediate open question that stems from our work is to design an online elicitation algorithm to compute an NRM matching, and analyze its competitive ratio. In particular, we believe that there exists an algorithm with a constant competitive ratio. Note that our online algorithm to compute an NPO matching from Section 3 is a constructive procedure, and uses our result that the existence of an NPO matching can be reduced to a simple analytical condition. Given that such a simple condition seems out of reach for the case of NRM, it may be interesting to explore a different approach to designing an online algorithm to compute an NRM matching. For example, one can train a machine learning model to select which agent to query next as a function of the preferences elicited so far. At each step, we can ﬁrst use this algorithm to make one more query, and then call our efﬁcient algorithm to check if the elicited preference reveal an NRM matching. It would be interesting to study if this approach can lead to a low competitive ratio, at least in practice. More broadly, the literature on learning a desirable matching of agents to objects from partial preferences or historical data is still in its infancy, and many interesting directions, such as studying other models of partial preferences or other models of querying agents, remain unexplored.

Acknowledgments Hadi Hosseini acknowledges support from NSF grant #1850076. Nisarg Shah was partially supported by an NSERC Discovery grant. We thank Lirong Xia and the anonymous reviewers for their very helpful comments and suggestions.

References Abdulkadiro glu, A.; and S onmez, T. 1998. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66(3): 689 701.

Abdulkadiro glu, A.; and S onmez, T. 1999. House allocation with existing tenants. Journal of Economic Theory 88(2): 233 260.

Abraham, D.; Chen, N.; Kumar, V.; and Mirrokni, V. S. 2006. Assignment problems in rental markets. In Proceedings of the Second International Workshop on Internet and Network Economics (WINE), 198 213. Springer.

Abraham, D. J. 2009. Matching markets: Design and analysis. Ph.D. thesis, University of Glasgow.

Abraham, D. J.; Cechl arov a, K.; Manlove, D. F.; and Mehlhorn, K. 2004. Pareto optimality in house allocation problems. In Proceedings of the Fifteenth International Symposium on Algorithms and Computation (ISAAC), 3 15.

Aziz, H.; Biro, P.; de Haan, R.; and Rastegari, B. 2019a. Pareto optimal allocation under compact uncertain preferences. In Proceedings of the Thirty-Third AAAI Conference on Artiﬁcial Intelligence (AAAI), volume 33, 1740 1747.

Aziz, H.; Bir o, P.; Lang, J.; Lesca, J.; and Monnot, J. 2019b. Efﬁcient reallocation under additive and responsive preferences. Theoretical Computer Science 790: 1 15.

Aziz, H.; Gaspers, S.; Mackenzie, S.; and Walsh, T. 2015. Fair assignment of indivisible objects under ordinal preferences. Artiﬁcial Intelligence 227: 71 92.

Aziz, H.; Walsh, T.; and Xia, L. 2015. Possible and necessary allocations via sequential mechanisms. In Proceedings of the Twenty-Fourth International Joint Conference on Artiﬁcial Intelligence (IJCAI), 468 474.

Bogomolnaia, A.; and Moulin, H. 2001. A new solution to the random assignment problem. Journal of Economic theory 100(2): 295 328.

Borodin, A.; and El-Yaniv, R. 2005. Online computation and competitive analysis. Cambridge University Press.

Bouveret, S.; Endriss, U.; and Lang, J. 2010. Fair Division under Ordinal Preferences: Computing Envy-Free Allocations of Indivisible Goods. In Proceedings of Nineteenth European Conference on Artiﬁcial Intelligence (ECAI), volume 215, 387 392.

Che, Y.-K.; and Kojima, F. 2010. Asymptotic equivalence of probabilistic serial and random priority mechanisms. Econometrica 78(5): 1625 1672.

Cirillo, R. 2012. The Economics of Vilfredo Pareto. Routledge.

Drummond, J.; and Boutilier, C. 2013. Elicitation and approximately stable matching with partial preferences. In Proceedings of the Twenty-Third international Joint conference on Artiﬁcial Intelligence (IJCAI), 97 105. AAAI Press. Garg, N.; Kavitha, T.; Kumar, A.; Mehlhorn, K.; and Mestre, J. 2010. Assigning papers to referees. Algorithmica 58(1): 119 136. Gaspers, S.; Naroditskiy, V.; Narodytska, N.; and Walsh, T. 2014. Possible and necessary winner problem in social polls. In Proceedings of the Thirteenth International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 613 620. Hosseini, H.; Larson, K.; and Cohen, R. 2018. Investigating the characteristics of one-sided matching mechanisms under various preferences and risk attitudes. Autonomous Agents and Multi-Agent Systems 32(4): 534 567. Hosseini, H.; Menon, V.; Shah, N.; and Sikdar, S. 2020. Necessarily Optimal One-Sided Matching. ar Xiv preprint ar Xiv:2007.09079 . Hylland, A.; and Zeckhauser, R. 1979. The efﬁcient allocation of individuals to positions. Journal of Political Economy 87(2): 293 314. Irving, R. W. 2003. Greedy matchings. Technical Report TR-2003-136, University of Glasgow . Irving, R. W.; Kavitha, T.; Mehlhorn, K.; Michail, D.; and Paluch, K. E. 2006. Rank-maximal matchings. ACM Transactions on Algorithms (TALG) 2(4): 602 610. Liu, Q.; Mailath, G. J.; Postlewaite, A.; and Samuelson, L. 2014. Stable matching with incomplete information. Econometrica 82(2): 541 587. Manlove, D. 2013. Algorithmics of matching under preferences, volume 2. World Scientiﬁc. Moulin, H. 2004. Fair division and collective welfare. MIT press. Munkres, J. 1957. Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics 5(1): 32 38. Rastegari, B.; Condon, A.; Immorlica, N.; and Leyton Brown, K. 2013. Two-sided matching with partial information. In Proceedings of the Fourteenth ACM Conference on Electronic Commerce (EC), 733 750. Shapley, L.; and Scarf, H. 1974. On cores and indivisibility. Journal of Mathematical Economics 1(1): 23 37. Xia, L.; and Conitzer, V. 2011. Determining Possible and Necessary Winners Given Partial Orders. Journal of Artiﬁcial Intelligence Research (JAIR) 41: 25 67.