On the Problem of Assigning PhD Grants

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 PhD grants is decentralized 1 , and each university organizes its own procedure to hire PhD 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 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".

1 As 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].

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 difficult 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 identified 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 PhD candidates as it is perceived as a loss of autonomy.

In this paper, we study the design of efficient 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

[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 first 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 PhD grant allocation in LAMSADE. A bounded number of PhD grants, namely k, are offered by the university to the laboratory in order to hire PhD 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.

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

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 PhD 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 define 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.

received (or not) a funding recently, the supervisor representing a topic has successfully supervised multiple PhD 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 find 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) := ∑(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 find 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: fixed and flexible 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 fixed offer then he will be ultimately assigned to topic tj. On the other hand, if student si accepts a flexible 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 fixed offer contains a single topic whereas a flexible offer may contain several topics. A flexible 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 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 fixed offers looks constraining for the jury, and one can ask whether only flexible offers can be considered. However, fixed 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 fixed 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 fixed 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 flexible 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 fixed 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 fixed offers.

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

Proof: Consider the instance described by Figure 2. Assume that two grants are available. Any sequential protocol restricted to fixed offers starts by proposing a fixed offer to one of the students. Assume that it first 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 ratio 2 .

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 ′ =

2 Proposition 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.

Algorithm 1 Optimal sequential protocol

Input: Candidacy set C, initial matching M 0 .

• 2: Compute a M-optimal augmenting path P in GC.
• 1: M ←M 0 .
• 3: while vM(P) ≥ 0 and |M| < k do
• 4: Let si be the unassigned student inM 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: returnM.

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 vM(P) = ∑(si,tj)∈P\M v(si, tj) - ∑(si,tj)∈M∩P v(si, tj), and it corresponds to the marginal value incurred by switching fromM to M∆P. More formally, v(M∆P) = v(M) + vM(P). It is worth noting that M ′ = M∆P implies that P is an alternating path for both M and M ′ , and vM(P) = -vM′(P). Augmenting path P for M is M-optimal if there is no augmenting path P ′ for M such that vM(P ′ ) > vM(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 fromC2. 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 vM(P). Hence, finding an optimal augmenting path for M amounts to finding 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 fill the k grants. This could be problematic if not enough offers are accepted before the market closure (for PhD 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 first 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 first 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 satisfies 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 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 first 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 fixed 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 fixed offers achieves a constant approximation ratio.

Proposition. 4 For any constant c ≤ 1, no mixed protocol restricted to fixed 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 fixed 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 flexible 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 definition, 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.

Base case (ℓ = 0): By construction, M 0 is (0)-optimal.

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 modified (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 | + ℓ.

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 ℓ )+vMℓ (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 toM ℓ 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 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 toM′A. If vMℓ(Pi) ≤ 0 then v(M ′ ) = v(M) - vM′(Pi) = v(M) + vMℓ(Pi) ≤ v(M) implies that M is also (ℓ + 1)-optimal, a contradiction since M is closer toM ℓ thanM ′ . On the other hand, if vMℓ(Pi) > 0 then matching M ℓ∆Pi of size |M ℓ | has value v(M ℓ ) + vMℓ(Pi) > v(M ℓ ), a contradiction with the fact that M ℓ is (ℓ)-optimal since M ℓ∆Pi belongs toM′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 ℓ )+vMℓ(P1) holds and it implies vMℓ (P1) > vMℓ (P ) since both v(M ℓ+1 ) = v(M ℓ )+ vMℓ (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 vMℓ(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 ℓ ) + ∑|M′ |-|Mℓ | i=1 vMℓ(Pi) and v(M ′ ) > v(M ℓ ) hold, there must be at least one augmenting path Pi for M ℓ such that vMℓ(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 first phase, but their impact is limited.

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

5 RelatedWork

The problem of assigning PhD 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 define 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 finding 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 finding 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 first 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 efficient mixed protocol.

6 Conclusion and FutureWorks

In this paper, we have proposed a decentralized matching model for the problem of assigning grants to PhD 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 first 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 CoCoRICo-CoDec.