On the Problem of Assigning PhD Grants

Katarína Cechlárová, Laurent Gourvès, Julien LescaIJCAI 2019 · DOI

TL;DR

This paper tackles the challenge of assigning PhD grants in a decentralized market where students' acceptance of offers is uncertain. The authors propose novel protocols that aim to find a matching as close as possible to the optimal one, even without knowing students' true preferences or outside options, by employing a robust, worst-case analysis approach.

What Problem Does This Paper Address?

The process of assigning PhD grants, especially in decentralized academic markets, presents a unique challenge. Universities (the "jury") want to hire the best PhD candidates, and students apply to multiple grants to maximize their chances. However, when a university offers a grant, it faces uncertainty: the student might reject the offer in favor of another opportunity (an "outside option"). This uncertainty makes it difficult for universities to achieve an optimal matching, where the best possible set of student-grant assignments is made. Traditional stable matching algorithms like deferred acceptance assume full information and can be manipulated. This paper addresses the problem of designing protocols for this decentralized, uncertain environment, aiming to find a matching that is "as close as possible" to the ideal scenario without this uncertainty.

Methods

The paper introduces two main types of protocols:

  • Sequential Protocols: Offers are made one by one, with the university waiting for a student's response before proceeding.
  • Fixed Offers: If a student accepts, they are definitively assigned to that specific topic.
  • Flexible Offers: If a student accepts, they are guaranteed a topic from a set of acceptable options, allowing for some flexibility.
  • Mixed Protocols: These involve an initial phase of parallel offers, followed by a sequential phase if needed. This aims to speed up the process while still managing uncertainty.

A key methodological contribution is the use of a robust approach and worst-case analysis to quantify the "regret" incurred by uncertainty. Instead of probabilistic models, the paper focuses on designing protocols that perform well even in the least favorable scenarios regarding student acceptance. The authors also leverage the concept of augmenting paths in bipartite graphs to improve matchings, similar to algorithms for maximum matching problems.

Datasets

Not discussed in the paper. The paper focuses on theoretical modeling and protocol design rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Uncertainty is the core challenge: The paper highlights that the decentralized nature of PhD grant allocation, with unknown student outside options, is the primary obstacle to achieving optimal matchings.
  • Robustness over optimality: Since perfect optimality is unattainable under uncertainty, the focus shifts to designing protocols that guarantee a certain level of performance (approximation ratio) even in the worst case.
  • Flexible offers offer more power: While fixed offers are simpler, flexible offers allow for better outcomes and can lead to optimal matchings under certain conditions.
  • Parallelization has trade-offs: Mixed protocols can speed up the process but may impact the achievable approximation ratio, especially if students have limited applications.
  • The "regret" of uncertainty: The paper frames the problem as minimizing the "regret" of not achieving the best possible matching due to unknown student choices.

Key Results

  • Sequential Protocols:
    • A sequential protocol restricted to fixed offers can achieve an approximation ratio of at most 1/2.
  • A sequential protocol using flexible offers can achieve an A-optimal matching (the best possible under the acceptance constraints).
  • Mixed Protocols:
    • For mixed protocols with flexible offers, an upper bound on the approximation ratio is 1/√2.
  • A specific mixed protocol, Max-sum, achieves an approximation ratio of 1/2.
  • The paper demonstrates that for mixed protocols, especially those restricted to fixed offers, a constant approximation ratio cannot be guaranteed if students have few applications.

Limitations and Future Work

  • Approximation Ratios: While 1/2 and 1/√2 are established, an open question is whether these ratios can be improved for mixed protocols.
  • Feasible Set of Offers: The definition of a "feasible set of offers" for the first phase of mixed protocols could be relaxed. For instance, it could be the largest set of offers that doesn't preclude obtaining an A-optimal matching.
  • Computational Complexity: While the paper focuses on theoretical guarantees, the computational complexity of finding optimal augmenting paths (which can be NP-hard in general) is mentioned, with a note that specific graph structures in this problem allow for polynomial-time solutions.
  • Real-world applicability: The model assumes students reveal preferences truthfully. Future work could explore scenarios with strategic students.

Summary updated

BibTeX
@inproceedings{cechlarova2019problem,
  author = {Katarína Cechlárová and Laurent Gourvès and Julien Lesca},
  title = {{On the Problem of Assigning PhD Grants}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/19},
}
Figure