# on_the_problem_of_assigning_phd_grants__6ddd1b94.pdf

On the Problem of Assigning Ph D Grants

Katar ına Cechl arov a1 , Laurent Gourv es2 and Julien Lesca2

1P.J. ˇSaf arik University, Koˇsice, Slovakia 2Universit e Paris-Dauphine, PSL, CNRS, LAMSADE, Paris, France katarina.cechlarova@upjs.sk, {laurent.gourves, julien.lesca}@dauphine.fr

In this paper, we study the problem of assigning Ph D grants. Master students apply for Ph D grants on different topics and the number of available grants is limited. In this problem, students have preferences over topics they applied to and the university has preferences over possible matchings of student/topic that satisfy the limited number of grants. The particularity of this framework is the uncertainty on a student s decision to accept or reject a topic offered to him. Without using probability to model uncertainty, we study the possibility of designing protocols of exchanges between the students and the university in order to construct a matching which is as close as possible to the optimal one i.e., the best achievable matching without uncertainty.

1 Introduction

Matching is a fundamental problem at the intersection of computer science, mathematics and economics [Manlove, 2013]. The restriction of this problem to bipartite graphs has attracted lot of attention in the research community. It has been used to match students with colleges [Goto et al., 2016; Hamada et al., 2017] or schools [Pathak, 2017], doctors with hospitals [Roth, 1984; Deng et al., 2017], etc. In our countries, the market for Ph D grants is decentralized1, and each university organizes its own procedure to hire Ph D candidates. The procedure can even vary between the different disciplines of the same institution. Each university competes to obtain the most successful candidates in the market. A student may apply for different grants in various universities in order to increase his chances to obtain a grant. This phenomenon is well documented in economics where various papers study the strategical aspects of constructing a portfolio of applications maximizing the chances of obtaining a good position [Chade and Smith, 2006; Chade et al., 2014]. One obvious conclusion of these works is that it is always safer for a candidate to apply for various positions. If a

1As it is the case for the postdoctoral job market for economists in North America [Roth, 2008], and for college admission in US, Korea and Japan [Che and Koh, 2016].

candidate receives multiple proposals, he can choose among them his most preferred one and reject the others. As a consequence, when a university makes a grant offer to a candidate in this decentralized market, it faces the uncertainty that this offer may be rejected in favor of an outside option . This uncertainty on the answer of a candidate to an offer is a special feature of a decentralized market. If the procedure for assigning students to grants was centralized among universities, and a stable matching algorithm such as deferred acceptance [Gale and Shapley, 1962] was in use, then no offer (or very few) would be rejected by students. Unfortunately imposing a centralized procedure to the various actors of this market is a difﬁcult task. There are various examples of markets which have failed to impose centralized procedures, including gastroenterology fellowships [Niederle et al., 2006], and psychology postdoctoral training [Bodin et al., 2017]. Economists have identiﬁed various theoretical reasons to explain this phenomenon. One of them is that it is not always a dominating strategy for a university to participate in a centralized procedure [Ekmekci and Yenmez, 2014] and it may be better off by opting out. Another one is that even if (student optimal) deferred acceptance is strategy-proof for students, it can be manipulated in various ways by universities [S onmez, 1999; Kesten, 2012]. In fact, there is no stable procedure which is non-manipulable by both students and universities [Roth, 1984]. Apart from these theoretical reasons, and unless it is enforced by law, an institute refrains to charge a central authority to choose their Ph D candidates as it is perceived as a loss of autonomy. In this paper, we study the design of efﬁcient protocols between some candidates and a university in this decentralized market. In these protocols, the university offers grants to students who may accept or reject the proposals, depending on their unknown outside options. We assume that the university has cardinal preferences over possible matchings but we do not resort to probabilistic models to represent the uncertainty faced by the university over students acceptance. Instead, we opt for a robust approach [Kouvelis and Yu, 1997] and we perform a worst case analysis by considering the greatest regret incurred by the protocol. In other words, our objective is to design protocols returning a matching which is as close as possible to the best achievable matching without uncertainty. This framework relies on approximation algorithms

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

[Vazirani, 2001] but the barrier is the lack of information instead of the computational complexity.

Plan. The different aspects of the model are introduced in Section 2. Afterwards, two types of protocols are considered: sequential protocols where offers are issued one by one (Section 3), and mixed protocols where a ﬁrst set of offers is made in parallel, followed by a sequence of offers (Section 4). Some proofs are omitted due to space limitation.

2 Preliminaries

The model proposed in this paper intends to represent the Ph D grant allocation in LAMSADE. A bounded number of Ph D grants, namely k, are offered by the university to the laboratory in order to hire Ph D students. The members of the department are encouraged to propose topics, and master students apply to the grants under different topics. Then, a jury decides to whom will be given the grants and with which topics. In the current system, a grant is given to a student/topic pair. Let S = {s1, . . . , sn} denote the set of students and T = {t1, . . . , tm} the set of topics. Student si applies for a subset of topics Ci which is his candidacy set; Ci T . The preference of student si over the topics of Ci is represented by total preorder i such that tj i tℓif and only if student si weakly prefers tj to tℓ. The fact that both tj i tℓand tℓ i tj (both tj i tℓand tℓ i tj, respectively) hold is denoted by tj i tℓ(tj i tℓ, respectively). We assume that students reveal their preferences over topics truthfully and do not try to manipulate. For any topic tj Ci, we denote by Ri(tj) the set of topics that are at least as good as tj according to i, and we denote by Ei(tj) the i-equivalence class of Ci which contains tj. More formally, Ri(tj) = {tℓ Ci : tℓ i tj} and Ei(tj) = {tℓ Ci : tℓ i tj} hold. Actually, each student si applies to a set of job opportunities Ji which is a superset of Ci. The job opportunities of Ji \ Ci are either Ph D grants proposed by other universities or other types of positions. The preference i of student si may be extended to Ji. Ultimately, student si will receive a subset of propositions Pi from Ji \ Ci. Let ji denote the most preferred job opportunity of student si inside this set of propositions Pi. Job opportunity ji will deﬁne the set of acceptable topics Ai for student si, which is the subset of Ci containing topics as least as preferred as ji according to i. More formally, Ai = Ri(ji). The jury knows the candidacy set Ci of each student si but it does not know his set of job opportunities Ji as well as his set of acceptable topics Ai. Let C and A denote sets {(si, tj) S T : tj Ci} and {(si, tj) C : tj Ai}, respectively. A matching is a subset of C containing at most k pairs and such that no student nor topic appears twice. Note that some topics may not be assigned if k < m. Matching M is acceptable, or is an A-matching, if M A. The jury provides its preference over matchings through preorder such that M M iff matching M is at least as good as matching M according to the jury s preference. The preference of the jury may model multiple aspects of this problem, including the preference over topics that may be selected in the matching. The jury has preferences over topics for different reasons: a topic seems more promising than another, the supervising team has

received (or not) a funding recently, the supervisor representing a topic has successfully supervised multiple Ph D students, etc. These preferences may also model the synergy over student/topic pairs: a student may not be a good match for one topic but would be a perfect match for another one, according to his capabilities and skills. Matching M is optimal if there is no matching M such that M M. M is A-optimal if it is an A-matching and there is no A-matching M such that M M. Our objective is to ﬁnd an A-optimal matching. Thereafter, we denote by M an A-optimal matching. In matching theory literature, it is common to assume that the preferences over subsets are responsive [Roth, 1985]. In this paper, we further assume that the jury s preferences are additive. This means that there exists a value function v : C R 0 such that for any matchings M and M , M M if and only if v(M) v(M ), where v(M) := P (si,tj) M v(si, tj). The use of a value function leaves the possibility to quantify the relative importance of a student/topic pair. For example, if v(si, tj) > v(sℓ, tp) + v(sr, tq) holds then it means that the jury prefers to assign a single grant to student si with topic tj rather than assigning two grants to student sℓand sr with topics tp and tq, respectively. Furthermore, this value function is a good measure of the worth of a matching according to the jury [Biro and Gudmondsson, 2019], and comparisons between matchings can be easily done. For any subset E C, let GE denote the edge-weighted bipartite graph with vertex set S T , edge set E and where weights are provided by v. Our objective is therefore to ﬁnd an optimal matching M in GA. This objective would be easy to achieve if A was known by the jury i.e., the jury knows which topics are acceptable to the students. However only C is known by the jury, and this can force them to make offers that will be rejected by the students. As we will see later, this can lead the jury to select a matching which is not an Aoptimal matching. Sometimes, no protocol can produce an A-optimal matching. In that case, we will search for an Amatching that is as close as possible to the A-optimal matching M . An algorithm achieves an approximation ratio of α 1 if for any instance of the problem, it computes an Amatching M such that v(M)/v(M ) α. A matching is constructed through an interaction between the candidates and the jury, called protocol, where the jury makes offers to students. In this paper, we consider two types of offers: ﬁxed and ﬂexible offers. In both cases, some topic, say tj, is offered to some student, say si, i.e. si receives a grant for working on tj. If student si accepts a ﬁxed offer then he will be ultimately assigned to topic tj. On the other hand, if student si accepts a ﬂexible offer he may be assigned to another topic tℓunder the condition that tℓ i tj holds. More formally, offer Oi Ci is a subset of topics proposed to student si. A ﬁxed offer contains a single topic whereas a ﬂexible offer may contain several topics. A ﬂexible offer Oi will be of the form Ri(tj) for some tj Ci. If student si accepts offer Oi then he is guaranteed to receive one of the topics of Oi at the end of the protocol. By accepting offer Oi, student si also commits to accept any topic in Oi. We assume that student si accepts offer Oi if and only if it is a subset of Ai. Once a student has accepted an offer, it is no

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

Figure 1: Example with 3 students, 2 topics and 2 grants

longer possible for the jury to make another offer to him. On the other hand, if a student rejects an offer then the jury can make other offers to him. The use of ﬁxed offers looks constraining for the jury, and one can ask whether only ﬂexible offers can be considered. However, ﬁxed offers somehow take into account the preference of the supervisor of a topic over students. Once an offer for a given topic tj is accepted by student si, the supervisor of this topic may disagree to obtain another student sℓin order to enlarge the global matching, and especially if student si seems to be more suited than student sℓfor topic tj. With ﬁxed offers, this situation cannot occur.

Example. 1 Consider the instance described in Figure 1, and where two grants are available (k = 2). The set of applications C contains (si, tj) for each si S and tj T . In other words, each student applies to each topic. However, student s2 will only accept t2 and student s3 will not accept any topic. More formally, A1 = {t1, t2}, A2 = {t2} and A3 = hold. If the protocol starts by a ﬁxed offer O1 = {t2} to student s1 then he accepts and t2 must be assigned to him. In that case, only topic t1 is still available. Topic t1 is unacceptable for any other student than s1, therefore any further offer will be rejected. The resulting matching M = {(s1, t2)} has value 5 whereas the A-optimal matching M = {(s1, t1), (s2, t2)} has value 7. On the other hand, if the protocol starts with ﬂexible offer O1 = {t1, t2} then student s1 accepts. Whatever offers are made by the jury thereafter, only offer O2 = {t2} will be accepted, leading to the A-optimal matching M which is consistent with the offers.

3 Sequential Protocols

In this section, the protocols under consideration consist of a single phase of exchanges between the jury and the students. During this phase, the jury makes offers one by one and waits for the answer of a student before making a new offer, even if the new offer is not addressed to the same student. We call this type of protocols sequential. In Subsection 3.1, we provide a sequential protocol restricted to ﬁxed offers which achieves the best possible approximation ratio of 1/2. In Subsection 3.2, we propose a sequential protocol which provides an A-optimal matching.

3.1 Sequential Protocols with Fixed Offers

The following proposition shows that an approximation ratio better than 1/2 cannot be achieved with ﬁxed offers.

Proposition. 1 No sequential protocol restricted to ﬁxed offers achieves a higher approximation ratio than 1/2.

Figure 2: Value function v equals 1 for each pair of C

Proof: Consider the instance described by Figure 2. Assume that two grants are available. Any sequential protocol restricted to ﬁxed offers starts by proposing a ﬁxed offer to one of the students. Assume that it ﬁrst proposes Oi = {tj} to student si and he accepts. Let sℓbe another student who prefers tj to the other topic. If Ai = {t1, t2}, Aℓ= {tj} and the set of acceptable topics is empty for the other students then M = {(si, t3 j), (sℓ, tj)} has value 2 whereas the protocol outputs M = {(si, tj)} with value 1 since no student will accept any further offer. Therefore, the protocol achieves an approximation ratio of at most 1/2. Consider now the following sequential protocol, called Max: by considering each pair (si, tj) of C by non-increasing value of v, the jury proposes Oi = {tj} to student si if si did not accept a former offer until either k offers have been accepted or all pairs of C have been considered. It obviously returns an A-matching. The following proposition shows that this protocol achieves the best possible approximation ratio2.

Proposition. 2 Max achieves an approximation ratio of 1/2.

3.2 Sequential Protocols with Flexible Offers In this subsection, we present a sequential protocol which returns an A-optimal matching. The underlying algorithm relies on the notion of alternating path. A path is assumed to be a sequence of edges belonging to GC. For a given matching M, an alternating path P with respect to M is a path in GC whose edges belong alternatively to M and C\M. We assume that an alternating path is either a cycle or does not contain a cycle. In the former case, we refer to it as an alternating cycle. When it is clear from context, we do not refer to the assignment associated with an alternating path. An alternating path is augmenting for M (decreasing for M, resp.) if it starts from an unassigned student (assigned student, resp.) in M and ends with an unassigned topic (assigned topic, resp.) in M. Finally, an alternating path is an even path if it is neither augmenting, decreasing nor cycle. For any two sets A, B C, let A B = (A \ B) (B \ A) denote the symmetric difference of A and B. Operator can be used to construct a new matching from an alternating path as follows. If M is a matching and P an alternating path then M P is a matching constructed from M by replacing the edges of M P with the edges of P \ M. Note that M =

2Proposition 2 is closely related to the greedy approach for obtaining a 1/2-approximation for the maximum matching problem [Karp et al., 1990]. Its proof is similar and is therefore omitted.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

Algorithm 1 Optimal sequential protocol Input: Candidacy set C, initial matching M 0. 1: M M 0. 2: Compute a M-optimal augmenting path P in GC. 3: while v M(P) 0 and |M| < k do 4: Let si be the unassigned student in M visited by P. 5: Propose Oi = Ci to student si. 6: if si accepts Oi then 7: M M P. 8: else 9: Let E Ci be the i-equivalence class containing the least preferred topics according to i. Remove E from Ci and (si, tj) from C for any tj E. 10: Compute M-optimal augmenting path P in GC. 11: return M.

M P implies M M = P. More generally, if M and M are two matchings then M M contains the set of alternating paths P1 . . . , Ps such that M = M P1 . . . Ps. The value of alternating path P with respect to M is v M(P) = P (si,tj) P \M v(si, tj) P (si,tj) M P v(si, tj), and it corresponds to the marginal value incurred by switching from M to M P. More formally, v(M P) = v(M) + v M(P). It is worth noting that M = M P implies that P is an alternating path for both M and M , and v M(P) = v M (P). Augmenting path P for M is M-optimal if there is no augmenting path P for M such that v M(P ) > v M(P). The sequential protocol proposed to obtain an A-optimal matching is presented in Algorithm 1. The initial matching M 0 used in this protocol is . If no augmenting path exists in GC then P = with value 0. In order to simplify notation, we assume that the candidacy set C can be updated, and set Ci for any si S, derives from C. In essence, Algorithm 1 starts with an empty matching and at every step augments it by proposing its candidacy set to the unmatched student visited by an optimal augmenting path. If he accepts the offer then he is included in the matching, and otherwise his candidacy set is revised by removing his least preferred topics.

Example. 2 We apply Algorithm 1 to the instance of Example 1. Parameter M 0 is set to , and initially M = . The set of augmenting paths for M is therefore C and their values correspond to the ones returned by v. The M-optimal augmenting path is P = {(s1, t2)} with value 5. Offer O1 = C1 = {t1, t2} is made to student s1 who accepts since A1 = C1. Then, matching M becomes M P = {(s1, t2)}. The augmenting paths for M of size 1 are the edges {s2, t1} and {s3, t1}. The augmenting paths for M of size 3 are {(s1, t1), (s1, t2), (s2, t2)} and {(s1, t1), (s1, t2), (s3, t2)} with values 2 and 0, respectively. The M-optimal augmenting path is {(s2, t1)} with value 4. Offer O2 = {t1, t2} is made to student s2 who rejects it. Since t2 2 t1, t1 is removed from C2. During the next iteration, the M-optimal augmenting path is {(s1, t1), (s1, t2), (s2, t2)}. Offer O2 = {t1} is made to student s2 who accepts since O2 = A2. Then, M becomes M P = {(s1, t1), (s2, t2)}.

The next result states that the corresponding sequential protocol returns an A-optimal matching. It is a corollary to

Proposition 6 which is given and proved in Subsection 4.2.

Corollary. 1 Algorithm 1 describes a sequential protocol which returns an A-optimal matching when M 0 = .

An M-optimal augmenting path can be computed through the incremental digraph which is an oriented version of GC where each edge (si, tj) of M is oriented from topic to student with weight v(si, tj), and each edge (si, tj) of C \ M is oriented from student to topic with weight v(si, tj). An oriented path from an unmatched student to an unmatched topic corresponds to an augmenting path for M. If P is an alternating path then the sum of its weights in the incremental digraph is equal to v M(P). Hence, ﬁnding an optimal augmenting path for M amounts to ﬁnding an oriented path in the incremental digraph of maximum weight. This problem is in general NP-hard. However, it is easy to show that the incremental digraph does not contain a cycle with positive weight. Therefore, a generalized version of Bellman-Ford algorithm [Gondran and Minoux, 2008] can be used to compute the oriented path of maximum weight.

4 Mixed Protocols In practice, a sequential protocol may require a lot of time in order to ﬁll the k grants. This could be problematic if not enough offers are accepted before the market closure (for Ph D grants allocation, it would be before the start of the academic year). This problem, called congestion, is well documented in the matching literature [Roth, 2008]. In order to reduce the duration of the process, it is natural to try to make multiple offers in parallel. However, since the jury commits to give a grant to every accepted offer, parallel offers should be issued carefully. Moreover, we will see that parallelization has an impact on the performance guarantee. The mixed protocols under consideration in this section comprise two different phases of exchanges between the jury and the students. As opposed to sequential protocols, multiple offers are made in parallel, but only during the ﬁrst phase. Phase one ends when the students who received an offer have answered. A second phase is initiated if at least one student declined. In the second phase, offers are made to the students who did not receive any offer or declined. As for the sequential protocol, the jury makes offers sequentially: one waits for a student s answer before making a new offer. Mixed protocols are similar to the procedures used in the American entrylevel market for clinical psychologists [Roth and Xing, 1997]. During the ﬁrst phase, a set of offers O = {Oi1, . . . , Oiℓ} will be made in parallel to students i1, . . . , iℓ. We will say that a matching M complies with a set of offers O if for every Oi O, student si is matched in M with a topic of Oi. A matching M compliant with a set of offers O is optimal if no other matching M compliant with O has greater value. Thus, the optimal compliant matching is what we can best do if all offers are accepted. A set of offers O is said to be feasible if it satisﬁes 3 requirements: (i) each student receives at most one offer, (ii) at least one matching is compliant with O, and (iii) for any superset O of O, no matching compliant with O has a greater value than the optimal matching compliant with O. In other words, requirement (iii) implies that there is no additional offer, made to a student who did not receive

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

Figure 3: Two available grants, d < c is an arbitrary positive value

any, which can be added to a feasible set in order to improve the value of the optimal matching compliant with it. To illustrate this property, consider an instance with two students, two topics and two grants such that C1 = {t1, t2}, C2 = {t2}, t2 1 t1, v(s1, t1) = v(s2, t2) = 1 and v(s1, t2) = 3. The set of offers O = {O1}, where O1 = {(s1, t2)}, is feasible since an additional offer to student s2 would lead to a compliant matching {(s1, t1), (s2, t2)} which has a strictly lower value than {(s1, t2)}. In this work, we will only consider feasible sets of offers O for the ﬁrst phase. Each time a student accepts an offer, the jury commits to assign him a topic of the offer. If all answers to O are positive, then the protocol returns an optimal matching compliant with O, and the second phase can be skipped. The goal of the second phase is to complete and improve the optimal matching compliant with the accepted offers. In Section 4.1, we show that no constant approximation ratio can be achieved by a mixed protocol if either a student applies to less than k topics or the protocol is restricted to ﬁxed offers. In Section 4.2, we provide an upper bound of 1/

2 for the approximation ratio achievable by a mixed protocol when each student applies to at least k topics, and we provide a mixed protocol with approximation ratio 1/2.

4.1 Cases of Unbounded Approximation Ratio The following proposition shows that no mixed protocol achieves a constant approximation ratio.

Proposition. 3 For any constant c 1, no mixed protocol achieves an approximation ratio of c.

Under the light of this impossibility result, we consider an additional constraint on the instances leading to constant approximation ratios. We assume in the remaining of the section that the number of candidacies for each student is at least k. This assumption is realistic since the jury can invalidate a student s application if it comprises less than k topics. The following proposition shows that even with this restriction, no mixed protocol restricted to ﬁxed offers achieves a constant approximation ratio.

Proposition. 4 For any constant c 1, no mixed protocol restricted to ﬁxed offers achieves an approximation ratio of c, even if |Ci| k holds for all si S.

Proof: Consider the instance described by Figure 3. During phase one, either (O1 = {t1} and O2 = {t2}) or (O1 = {t2} and O2 = {t1}) are proposed. In the former case, if A1 = and A2 = {t1, t2} then s1 declines and s2 accepts. In the latter case, if A1 = {t1, t2} and A2 = then s1 accepts but s2 declines. In both cases, topic t1 remains unassigned whereas it could be assigned to the student who accepted the offer. Therefore, the resulting matching has value 1/d whereas M

has value 1/d2. This implies that no mixed protocol restricted to ﬁxed offers achieves a better approximation ratio than d and d < c.

4.2 Mixed Protocol with Flexible Offers The following proposition provides an upper bound on the approximation ratio for a mixed protocol with ﬂexible offers.

Proposition. 5 No mixed protocol achieves an approximation ratio larger than 1/

2, even if |Ci| k for any si S.

Finally, we present a mixed protocol, called Max-sum, which achieves an approximation ratio of 1/2. During phase one, the protocol starts by computing an optimal matching MC in GC. Let S denote the set of students matched in MC. The set of offers O contains offer Oi := Ci for each student si S. Let A S denote the set of students who accept their offer, and let OA be the set of offers that they have received. For each student si S \ A, candidacy set Ci is updated by removing the topics contained in his least preferred iequivalence class. Let MA be an optimal matching compliant with OA. During phase two, Algorithm 1 is used with input C and MA. Let MA be the set of all A-matchings such that each student si A is assigned a topic of Ci. We are going to see that using Algorithm 1 with input MA leads to an A-matching of maximum value within MA. This is more general than Proposition 1 (input M 0 = MA instead of M 0 = ) which is a corollary to the following result.

Proposition. 6 Algorithm 1 with input C and MA returns an A-matching of maximum value within MA.

Proof: By deﬁnition, A is a subset of C. During its execution, Algorithm 1 prunes some elements of C\A. Eventually, the set of candidacies is equal to C , and C C A holds. Let M A be the set of matchings in GC such that each student si A is assigned a topic of Ci. Note that an Amatching which is optimal within M A is also optimal within MA. Therefore, our proving strategy is to show that Algorithm 1 with input C and MA provides a matching which is optimal within M A. Let M ℓdenote the current solution during the execution of Algorithm 1. More precisely, M 0 is the initial solution. Each time the solution is modiﬁed (in line 7), its index is incremented. Thus, M ℓcontains |M 0| + ℓedges. We show by induction on ℓthat M ℓis (ℓ)-optimal i.e., optimal within M A restricted to the matchings of size at most |M 0| + ℓ. Base case (ℓ= 0): By construction, M 0 is (0)-optimal. Induction step: By induction hypothesis, M ℓis (ℓ)- optimal. We show that M ℓ+1 is (ℓ+ 1)-optimal. Let P denote the M ℓ-optimal augmenting path computed at the end of iteration ℓand such that M ℓ+1 = M ℓ P. Note that v(M ℓ+1) = v(M ℓ)+v M ℓ(P) v(M ℓ) holds, and therefore M ℓ+1 is (ℓ)-optimal. By contradiction, assume that there exists a matching M M A of size |M 0| + ℓ+ 1 such that v(M ) > v(M ℓ+1). Without loss of generality, we assume that M is (ℓ+ 1)-optimal and as close as possible to M ℓi.e., there is no matching M in M A of size |M 0| + ℓ+ 1 such that v(M) = v(M ) and M ℓ M M ℓ M hold. Let P1, . . . , Ps be the alternating paths of M ℓ M . Note that

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

each of these paths belongs to GC since both M ℓand M belong to GC . We claim that no alternating path Pi is a cycle or an even path. By contradiction, assume that Pi is either a cycle or an even path. Let M be the matching in GC of size |M 0| + ℓ+ 1 such that M = M Pi. Note that M belongs to M A since both M ℓand M belong to M A. If v M ℓ(Pi) 0 then v(M ) = v(M) v M (Pi) = v(M) + v M ℓ(Pi) v(M) implies that M is also (ℓ+ 1)-optimal, a contradiction since M is closer to M ℓthan M . On the other hand, if v M ℓ(Pi) > 0 then matching M ℓ Pi of size |M ℓ| has value v(M ℓ) + v M ℓ(Pi) > v(M ℓ), a contradiction with the fact that M ℓis (ℓ)-optimal since M ℓ Pi belongs to M A. Since |M ℓ| < |M |, there must be at least one augmenting path Pj for M ℓin M M ℓ. We claim that M M ℓdoes not contain any decreasing path for M ℓ. The existence of a decreasing path Pr for M ℓleads to a contradiction. This can be shown by using the same argument as above (replace Pi by Pr Pj). Since M ℓ M only contains augmenting paths for M ℓand |M | = |M ℓ| + 1, M M ℓcontains a single path P1. Therefore, v(M ) = v(M ℓ) + v M ℓ(P1) holds and it implies v M ℓ(P1) > v M ℓ(P) since both v(M ℓ+1) = v(M ℓ)+ v M ℓ(P) and v(M ) > v(M ℓ+1) hold, a contradiction with P is M ℓ-optimal since P1 belongs to GC . Now we know that M ℓis (ℓ)-optimal. If the while loop of Algorithm 1 stops because |M ℓ| = k, then M ℓis outputted and must be optimal within M A because k is the maximum cardinality of a matching. If the while loop of Algorithm 1 stops because v M ℓ(P) < 0 for every augmenting path P for M ℓthen we shall see that M ℓis optimal within MA. Assume by contradiction that there exists a matching M within M A of size greater than |M ℓ| such that v(M ) > v(M ℓ). With arguments similar to the ones used in the above induction, we can check that M ℓ M contains only augmenting paths P1, P2, . . . , P|M | |M ℓ| for M ℓ. Since v(M ) =

v(M ℓ) + P|M | |M ℓ| i=1 v M ℓ(Pi) and v(M ) > v(M ℓ) hold, there must be at least one augmenting path Pi for M ℓsuch that v M ℓ(Pi) > 0, a contradiction since Pi belongs to GC . Proposition 6 shows that the second phase of Max-sum suffers from no loss of value. Bad decisions can be made during the ﬁrst phase, but their impact is limited.

Proposition. 7 The approximation ratio of Max-sum is 1/2.

5 Related Work

The problem of assigning Ph D grants to students is closely related to the student-project allocation problem [Abraham et al., 2007; Abu El-Atta and Moussa, 2009] where projects are proposed by lecturers who have preferences over student/topic pairs. The main novelty of our model lies in the fact that it is decentralized and the preferences of the students (i.e., the set of topics that they may accept) are unknown when the jury builds the matching. The model proposed by Che and Koh [2016] shares also some similarity with our problem. They study a decentralized college admission problem where the students preferences are unknown and they deﬁne the equilibria in the related games.

Matching problems where parameters are unknown or partially observable have already been investigated in the literature. One of the closest model to our problem is the stable matching with partially observable preferences [Drummond and Boutilier, 2013] (see also Rastegari et al. [2013; 2014]). The notion of maximum regret used to quantify the quality of a solution is close to our notion of approximation. Probabilistic models have also been used to represent uncertainty over the preferences of agents for stable matchings [Aziz et al., 2017a] and assignment problems [Aziz et al., 2017b]. Another related matching problem has been proposed by Anshelevich and Sekar [2016] where we know how the edges compare but the exact edges weights are unknown. Another problem close to ours is the stochastic matching problem [Blum et al., 2015] which aims at ﬁnding a maximum matching in a graph where the existence of the edges is only probabilistically known. Similarly to our problem, the matching is constructed through a protocol which checks at each step the existence of a given edge. However, the fact that the protocol checks the existence of a given edge does not imply that one of its extremities should be selected if the edge exists. Finally, the mixed protocols presented in this paper bear resemblance with the robust matching problem [Hassin and Rubinstein, 2002]. This problem consists in ﬁnding a matching whose restriction to its k-best edges provides a good approximation of the optimal matching of size k, for any integer k. The authors show that no algorithm achieves a better approximation than 1/

2, and they provide an algorithm achieving this ratio. A robust matching is not necessarily a good candidate for the ﬁrst phase of a mixed protocol because it may contain edges of large value which are unacceptable, and edges of low value which are acceptable. However, the algorithm to produce a robust matching is a good candidate to design an efﬁcient mixed protocol.

6 Conclusion and Future Works

In this paper, we have proposed a decentralized matching model for the problem of assigning grants to Ph D candidates where the answers of students are not known in advance by the university. This setting can cover other applications (e.g. allocation of internships in a company). We have provided a theoretical analysis of the best approximation ratio achievable by a protocol of exchanges between the jury and the students. An open question is whether the 1/2-approximation can be improved for mixed protocols (in polynomial time or not). It would also be interesting to relax the notion of feasible set of offers imposed during the ﬁrst phase of a mixed protocol. For example, a feasible set could be instead the largest set of offers that can be made to students without losing the possibility to obtain an A-optimal matching.

Acknowledgements

This work is supported by the bilateral Slovak-French grant of Campus France PHC STEFANIK 2018, 40562NF and Slovak Research and Development Agency APVV SK-FR2017-0022. Cechl arov a is also supported by VEGA grants 1/0311/18 and 1/0056/18. Gourv es and Lesca are supported by the project ANR-14-CE24-0007-01 Co Co RICo-Co Dec.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

[Abraham et al., 2007] D. Abraham, R. Irving, and D. Manlove. Two algorithms for the student-project allocation problem. J. of Discrete Algo., 5:73 90, 2007.

[Abu El-Atta and Moussa, 2009] A. Abu El-Atta and M. Moussa. Student project allocation with preference lists over (student, project) pairs. In Proc. of ICCEE, pages 375 379, 2009.

[Anshelevich and Sekar, 2016] E. Anshelevich and S. Sekar. Blind, greedy, and random: Algorithms for matching and clustering using only ordinal information. In Proc. of AAAI, pages 390 396, 2016.

[Aziz et al., 2017a] H. Aziz, P. Bir o, T. Fleiner, S. Gaspers, R. de Haan, N. Mattei, and B. Rastegari. Stable matching with uncertain pairwise preferences. In Proc. of AAMAS, pages 344 352, 2017.

[Aziz et al., 2017b] H. Aziz, R. de Haan, and B. Rastegari. Pareto optimal allocation under uncertain preferences. In Proc. of IJCAI, pages 77 83, 2017.

[Biro and Gudmondsson, 2019] P. Biro and J. Gudmondsson. Complexity of ﬁnding Pareto-efﬁcient allocations of highest welfare. Working papers, 2019.

[Blum et al., 2015] A. Blum, J. Dickerson, N. Haghtalab, A. Procaccia, T. Sandholm, and A. Sharma. Ignorance is almost bliss: Near-optimal stochastic matching with few queries. In Proc. of ACM EC, pages 325 342, 2015.

[Bodin et al., 2017] D. Bodin, J. Schmidt, R. Lemle, B. Roper, R. Goldberg, K. Hill, C. Parrish, S. Williams, A. Kuemmel, and W. Siegel. Recruitment and selection in health service psychology postdoctoral training: A review of the history and current issues. Training and Education in Professional Psychology, 12, 11 2017.

[Chade and Smith, 2006] H. Chade and L. Smith. Simultaneous search. Econometrica, 74(5):1293 1307, 2006.

[Chade et al., 2014] H. Chade, G. Lewis, and L. Smith. Student Portfolios and the College Admissions Problem. The Review of Economic Studies, 81(3):971 1002, 02 2014.

[Che and Koh, 2016] Y. Che and Y. Koh. Decentralized college admissions. J. of Poly. Eco., 124(5):1295 1338, 2016.

[Deng et al., 2017] Y. Deng, D. Panigrahi, and B. Waggoner. The complexity of stable matchings under substitutable preferences. In Proc. of AAAI, pages 480 486, 2017.

[Drummond and Boutilier, 2013] J. Drummond and C. Boutilier. Elicitation and approximately stable matching with partial preferences. In Proc. of IJCAI, pages 97 105, 2013.

[Ekmekci and Yenmez, 2014] M. Ekmekci and M. Yenmez. Integrating Schools for Centralized Admissions. Working paper, 2014.

[Gale and Shapley, 1962] D. Gale and L. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9 15, 1962.

[Gondran and Minoux, 2008] M. Gondran and M. Minoux. Graphs, dioids and semirings: new models and algorithms. Springer Science & Business Media, 2008. [Goto et al., 2016] M. Goto, A. Iwasaki, Y. Kawasaki, R. Kurata, Y. Yasuda, and M. Yokoo. Strategyproof matching with regional minimum and maximum quotas. Artiﬁcial Intelligence, 235:40 57, 2016. [Hamada et al., 2017] N. Hamada, C. Hsu, R. Kurata, T. Suzuki, S. Ueda, and M. Yokoo. Strategy-proof school choice mechanisms with minimum quotas and initial endowments. Artiﬁcial Intelligence, 249:47 71, 2017. [Hassin and Rubinstein, 2002] R. Hassin and S. Rubinstein. Robust matchings. SIAM J. on Discrete Mathematics, 15:530 537, 2002. [Karp et al., 1990] R. Karp, U. Vazirani, and V. Vazirani. An optimal algorithm for on-line bipartite matching. In Proc. of STOC, pages 352 358, 1990. [Kesten, 2012] O. Kesten. On two kinds of manipulation for school choice problems. Eco. Theory, 51:677 693, 2012. [Kouvelis and Yu, 1997] P. Kouvelis and G. Yu. Robust discrete optimization and its applications. Kluwer Academic Publishers Group, 1997. [Manlove, 2013] D. Manlove. Algorithmics of matching under preferences. World Scientiﬁc, 2013. [Niederle et al., 2006] M. Niederle, D. Proctor, and A. Roth. What will be needed for the new GI fellowship match to succeed? Gastroenterology, 130:218 24, 02 2006. [Pathak, 2017] P. Pathak. What Really Matters in Designing School Choice Mechanisms, page 176 214. Econometric Society Monographs. Cambridge University Press, 2017. [Rastegari et al., 2013] B. Rastegari, A. Condon, N. Immorlica, and K. Leyton-Brown. Two-sided matching with partial information. In ACM EC, pages 733 750, 2013. [Rastegari et al., 2014] B. Rastegari, A. Condon, N. Immorlica, R. Irving, and K. Leyton-Brown. Reasoning about optimal stable matchings under partial information. In Proc. of ACM EC, pages 431 448, 2014. [Roth and Xing, 1997] A. Roth and X. Xing. Turnaround time and bottlenecks in market clearing: Decentralized matching in the market for clinical psychologists. J. of Political Economy, 105(2):284 329, 1997. [Roth, 1984] A. Roth. The evolution of the labor market for medical interns and residents: A case study in game theory. J. of Political Economy, 92(6):991 1016, 1984. [Roth, 1985] A. Roth. The college admissions problem is not equivalent to the marriage problem. J. of Economic Theory, 36(2):277 288, 1985. [Roth, 2008] A. Roth. What have we learned from market design? The Economic Journal, 118(527):285 310, 2008. [S onmez, 1999] T. S onmez. Can pre-arranged matches be avoided in two-sided matching markets? J. of Economic Theory, 86(1):148 156, 1999. [Vazirani, 2001] Vijay V. Vazirani. Approximation algorithms. Springer, 2001.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)