PARCOURSUP 👩🏽🎓🏫 et les algorithmes de mariage stable ❤️
TLDRThe video discusses the French higher education allocation process, Parcoursup, and the mathematical algorithms behind its matching procedure. It explains the evolution from the decentralized pre-2009 system to the current centralized one, highlighting the famous Gale-Shapley algorithm that aims to create stable and fair student-university pairings. The video also addresses the controversy surrounding algorithms, emphasizing the need for understanding and transparency in the allocation process. It compares the APB system with Parcoursup, pointing out the latter's improvements and challenges, such as the elimination of ranking preferences and the introduction of a more transparent selection process based on pedagogical criteria.
Takeaways
- 📚 ParcourSup is a centralized procedure for assigning high school graduates to higher education programs, including universities, BTS, and preparatory classes.
- 🧮 The video aims to clarify the mathematics behind ParcourSup, focusing on the allocation algorithms that have been criticized due to a lack of understanding.
- 🔄 Before 2009, the process in France was decentralized, leading to inefficiency and long waiting times for students.
- 🇺🇸 The United States medical internship allocation system from the 1950s inspired the centralized and grouped procedure used in ParcourSup.
- 🔢 The initial allocation procedure is simple: students rank their choices, and institutions decide on acceptance based on these preferences.
- 🤔 Despite its apparent fairness, the simple allocation method has flaws, such as students potentially ending up in their least preferred choice due to the order of selection.
- 🎓 Gale and Shapley's algorithm, introduced in 1962, provides a fair and non-manipulable solution by creating stable marriages between students and institutions.
- 💑 The Gale-Shapley algorithm uses a proposal and acceptance process, where students propose to their preferred institutions, and institutions accept based on their preferences.
- 🔄 The algorithm iterates through rounds of proposals until a stable matching is found, where no student or institution has an incentive to change partners.
- 🇫🇷 The APB procedure in France, which used Gale-Shapley's algorithm, faced issues with its implementation, including the use of a lottery system for oversubscribed programs.
- 🚀 Parcoursup, introduced in 2018, replaced APB and addressed some of its issues, including the elimination of lotteries and allowing institutions to use educational criteria for selection.
Q & A
What is the main purpose of the video?
-The main purpose of the video is to explain the mathematics behind Parcoursup, a procedure for assigning high school students to higher education programs, and to shed light on the algorithms used in the process.
What was the issue with the decentralized process in France before 2009?
-The decentralized process was inefficient, time-consuming, and stressful for both students and institutions as it involved individual contacts and exchanges of documents, leading to long waiting times for responses and potential mismatches in the allocation of students to programs.
How does the centralized procedure for assigning students to higher education programs work?
-The centralized procedure involves students ranking their preferred programs and the programs ranking the students based on their applications. Initially, each student's first choice is considered, and if there is a match, they are accepted. If not, the process moves to the student's second choice, and so on until a match is found or all choices have been considered.
What is the main criticism of the centralized procedure?
-The main criticism is that the centralized procedure is not fair and is manipulable. Students may end up in their last choice instead of their first, and there is an incentive for students to play tactically by misrepresenting their true preferences to improve their chances of getting a better match.
Who discovered a better procedure for assigning students to higher education programs?
-Mathematicians David Gale and Lloyd Shapley discovered a better procedure for such assignments in 1962.
What is the Gale-Shapley algorithm and how does it ensure fairness?
-The Gale-Shapley algorithm is a method for creating stable marriages between two groups, such as students and programs. It involves iterative proposals and acceptances based on preferences until a stable matching is reached where no individual has an incentive to switch partners. This algorithm ensures fairness by preventing manipulation of preferences and providing the best possible stable outcome for the proposing group.
How is the Gale-Shapley algorithm applied to student placement in higher education?
-In the context of student placement, the Gale-Shapley algorithm is applied by considering students as one group and higher education programs as the other. Each student ranks their preferred programs, and each program ranks the students. The algorithm then proceeds through rounds of proposals and acceptances to find a stable matching where no student or program has a reason to prefer another match over their current one.
What are the key advantages of the Gale-Shapley algorithm?
-The key advantages of the Gale-Shapley algorithm include its ability to provide a stable and fair solution, its resistance to manipulation, its favorability for the proposing group (students in this case), and its efficiency in terms of computation once preference lists are established.
What was the APB procedure and what were its main issues?
-The APB (Admission Post-Bac) procedure was a system used in France to assign students to higher education programs. Its main issues included the use of a lottery system for highly demanded programs and the fact that it was manipulable, leading to stress for students who had to play tactics in ranking their choices to improve their chances.
What is the Parcoursup platform and how does it differ from APB?
-Parcoursup is a newer platform for assigning students to higher education programs in France. It differs from APB by allowing programs to rank candidates based on educational criteria, eliminating the lottery system, and requiring students to respond to program offers over multiple rounds instead of having a single ranked list of choices. Parcoursup also includes mechanisms for affirmative action and automatic consideration of quotas for students.
What is the main criticism of Parcoursup compared to APB?
-The main criticism of Parcoursup compared to APB is that it takes much longer to reach a stable matching, causing stress and uncertainty for students who must wait for months to receive their final assignment.
What is the 'oui si' mechanism in Parcoursup and how does it work?
-The 'oui si' mechanism in Parcoursup allows programs to accept a student on the condition that they follow an additional complementary training. This provides more flexibility for both students and programs and allows for more tailored educational paths.
Outlines
📚 Introduction to Parcoursup and Its Algorithmic Behind
This paragraph introduces Parcoursup, a French higher education allocation procedure for high school graduates to various higher education programs. The focus is on the mathematics and algorithms behind Parcoursup, specifically the allocation algorithms that have been criticized and misunderstood. The aim is to clarify the process and address common fears and misconceptions about these algorithms.
🤔 The Problem of Centralized Allocation and the Gale-Shapley Solution
The paragraph discusses the historical inefficiency of the decentralized allocation process in France before 2009 and introduces the centralized allocation procedure used in the United States since the 1950s. It explains the simple allocation process where students rank all programs by preference, and the programs accept or reject based on these rankings. The paragraph then introduces the Gale-Shapley algorithm, developed in 1962, which provides a fair and non-manipulable solution to the allocation problem.
💡 The Gale-Shapley Algorithm and Its Intuitive Explanation
This section provides an intuitive explanation of the Gale-Shapley algorithm using the analogy of arranging marriages between men and women. It explains how the algorithm works in multiple rounds where men propose and women decide, leading to stable marriages where no man or woman has an incentive to 'cheat' on their partner. The paragraph emphasizes the stability and fairness of the Gale-Shapley procedure and how it always leads to a stable solution.
🔄 The Asymmetric Nature of the Gale-Shapley Procedure
The paragraph delves into the asymmetric nature of the Gale-Shapley algorithm, where the proposers (men in the analogy) and the deciders (women in the analogy) have different roles. It explains that the group who proposes gets the best possible outcome among all stable solutions, while the group who decides gets the worst. The paragraph also discusses the implications of this asymmetry and how it discourages strategic manipulation of the procedure.
🎓 Application of the Gale-Shapley Procedure to Student Allocation
This section applies the Gale-Shapley procedure to the context of student allocation to higher education programs. It explains how the procedure ensures a stable match without justified envy, meaning no student is rejected in favor of a less qualified candidate. The paragraph also highlights the adaptability of the procedure to situations where the number of students and available places may vary.
📉 Limitations and Alternatives to the Gale-Shapley Procedure
The paragraph acknowledges that while the Gale-Shapley procedure is optimal among stable solutions, it may not be the absolute best solution. It introduces the concept of optimal exchange cycles, which prioritize finding the best possible solution over stability. The paragraph also discusses the trade-off between stability and optimality in allocation procedures.
🇫🇷 The Evolution from APB to Parcoursup: Changes and Challenges
This paragraph discusses the transition from the APB (Admission Post-Bac) system to Parcoursup in France. It outlines the changes in the allocation procedure, including the elimination of the lottery system and the introduction of academic criteria for classifying candidates. The paragraph also addresses the challenges of the Parcoursup system, such as the lengthy allocation process and the stress it causes for students.
🤷♂️ Criticisms and Misconceptions About Algorithms in Allocation
The final paragraph addresses criticisms of the APB system and the misconceptions about algorithms in allocation procedures. It argues that the Gale-Shapley algorithm is transparent and understandable, and that the issues with APB were not inherently due to the algorithm itself. The paragraph calls for better communication about how allocation algorithms work and their benefits, and suggests potential improvements for the Parcoursup system.
Mindmap
Keywords
💡Parcoursup
💡Gale-Shapley algorithm
💡Stable allocation
💡APB (Admission Post-Bac)
💡Non-manipulable
💡Preferences
💡Lottery system
💡Centralized allocation
💡Educational merit
💡Stability in matching
💡Justified envy
Highlights
Introduction to Parcoursup, the French higher education allocation system.
Explanation of the historical context and evolution from a decentralized process to Parcoursup.
Discussion of the inefficiency and drawbacks of the pre-2009 decentralized application process.
Overview of the match-making algorithms and their role in Parcoursup.
Critique of the fear and misunderstanding surrounding algorithms in allocation processes.
Introduction to the concept of stable marriages and the work of mathematicians David Gale and Lloyd Shapley.
Explanation of the Gale-Shapley algorithm and its application to the marriage problem.
Discussion of the advantages of the Gale-Shapley algorithm, including fairness and resistance to manipulation.
Comparison of the centralized and decentralized allocation processes and their outcomes.
Illustration of the allocation process with a concrete example involving three students and three faculties.
Explanation of the APB (Admission Post-Bac) system used in France from 2009 to 2017.
Critique of the APB system, highlighting its flaws and the introduction of the Parcoursup platform.
Overview of the differences between APB and Parcoursup, focusing on the latter's emphasis on transparency and student choice.
Discussion of the non-ranking of choices in Parcoursup and its implications for students and institutions.
Explanation of the 'oui si' mechanism in Parcoursup, allowing conditional acceptance of students.
Inclusion of quotas for scholarship students and out-of-academy students in Parcoursup's algorithm.
Critique of the lengthy process in Parcoursup and its impact on students' stress levels.
Comparison of the efficiency and speed of APB and Parcoursup, highlighting the latter's manual-like approach.
Discussion on the public perception of algorithms and the importance of transparency in their application.
Reflection on the CNIL's role in the transition from APB to Parcoursup and the implications for algorithmic decision-making.
Suggestion of potential improvements for Parcoursup, including a time limit on non-ranked choice and accelerated processing.