52
Quelle place pour les algorithmes dans la r´ egulation des inscriptions scolaires? Julien Grenet CNRS ´ Ecole d’´ economie de Paris Journ´ ee d’´ etude “APB, cas d’´ ecole des algorithmes publics”, 28 juin 2017

Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

  • Upload
    etalab

  • View
    4.762

  • Download
    1

Embed Size (px)

Citation preview

Page 1: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

Quelle place pour les algorithmes dans

la regulation des inscriptions scolaires?

Julien Grenet

CNRSEcole d’economie de Paris

Journee d’etude “APB, cas d’ecole des algorithmes publics”, 28 juin 2017

Page 2: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

Contexte

Profonde transformation des modalites d’affectation des eleves auxetablissements d’enseignement depuis le milieu des annees 2000

Adoption de procedure centralisees et automatisees

– au lycee : PAM puis AFFELNET

– dans l’enseignement superieur : RAVEL puis APB

Caracteristiques communes :

– vœux d’inscription

– criteres de priorite

– algorithme d’appariement

Evolutions similaires dans de nombreux pays

Australie, Belgique, Chili, Espagne, Etats-Unis, Hongrie, Norvege,Pays-Bas, Royaume-Uni, Suede...

1 / 15

Page 3: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

Objectifs

Objectif initial : simplifier la gestion des procedures d’inscriptionsscolaires (ex : probleme des candidatures multiples a l’universite)

Prise de conscience progressive des potentialites et limites desalgorithmes pour la mise en œuvre d’objectifs de politique educative

– transparence de l’affectation (ex : Chili)

– adequation entre aptitudes et formations (ex : Norvege)

– mixite sociale (ex : Belgique, France)

Recherches tres actives a la frontiere entre plusieurs disciplines(mathematiques, economie, operations research, psychologie...)

Role moteur de la recherche dans la reforme des proceduresd’affectation des eleves aux Etats-Unis (A. Roth et L. Shapley, PrixNobel d’economie 2012)

2 / 15

Page 4: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

Enjeux

En France, les algorithmes d’affectation des eleves/etudiants (et lesalgorithmes plus generalement !) ont mauvaise presse

“casse-tete”, “usine a gaz”, “jeu de dupes”, “loterie”, “anxiogene”

La critique des algorithmes est en partie justifiee : ils ont parfois demauvaises proprietes

Cependant, les difficultes crees par les procedures d’affectation nesont pas pas principalement imputables aux algorithmes mais plutot

– a la complexite et a l’opacite des procedures

– aux criteres de priorite utilises (et aux choix politiques qui lessous-tendent)

Illustration : polemique sur le tirage au sort dans APB

3 / 15

Page 5: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

Enjeux

En France, les algorithmes d’affectation des eleves/etudiants (et lesalgorithmes plus generalement !) ont mauvaise presse

“casse-tete”, “usine a gaz”, “jeu de dupes”, “loterie”, “anxiogene”

La critique des algorithmes est en partie justifiee : ils ont parfois demauvaises proprietes

Cependant, les difficultes crees par les procedures d’affectation nesont pas pas principalement imputables aux algorithmes mais plutot

– a la complexite et a l’opacite des procedures

– aux criteres de priorite utilises (et aux choix politiques qui lessous-tendent)

Illustration : polemique sur le tirage au sort dans APB

3 / 15

Page 6: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

Les algorithmes d’affectation :quel est leur role ?

4 / 15

Page 7: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

Procedures d’inscription : le role des algorithmes

Toute procedure de regulation des inscriptions scolaires comportequatre omposantes distinctes :

(1) capacite d’accueil des etablissements/formations

(2) vœux d’affectation des eleves

(3) regles de priorite

(4) algorithme d’affectation

Les regles de priorite traduisent des objectifs politiques

Quand il ne reste qu’une seule place pour deux candidats,comment choisir ? Decision politique puisqu’elle cree des“gagnants” et des “perdants”

Ex : resultats scolaires, distance, fratries, criteres sociaux...

L’algorithme d’affectation vise a satisfaire au mieux lespreferences des eleves tout en respectant les regles de priorite

4 / 15

Page 8: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

Quels criteres normatifs ?Il existe de nombreux algorithmes pour reguler les inscriptionsscolaires : comment choisir ?

Les economistes evaluent leurs performances a l’aune de troiscriteres normatifs :

– Efficacite (respect des preferences) : il ne doit pas etrepossible de proposer un meilleur choix a un eleve sans que celaaffecte negativement un autre eleve (critere de Pareto)

– Equite (respect des priorities) : aucun eleve ne doit avoird’“envie justifiee” (justified envy), i.e. s’etre vu refuserl’admission dans une ecole alors qu’il a une priorite plus elevequ’un autre eleve admis dans cette ecole

– Non-manipulabilite (strategy-proofness) : on veut qu’il soitdans l’interet des eleves d’etre sinceres, i.e. de soumettre leursvraies preferences

Ces trois criteres sont-ils compatibles ?5 / 15

Page 9: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme ideal existe-t-il ?

Mauvaise nouvelle : l’efficacite (respect des preferences), l’equite(respect des priorites) et la non-manipulabilite sont incompatibles

Aucun algorithme ne peut satisfaire ces trois criteres dans toutesles situations !

Mais des compromis optimaux sont possibles :

– equite + non-manipulabilte → algorithme d’acceptationdifferee (Deferred acceptance) - mais pas toujours efficace

– efficacite + non-manipulabilite → algorithme des cyclesd’echanges (Top trading cycles) - mais pas toujours equitable

Malheureusement, beaucoup d’algorithmes utilises a travers lemonde ne respectent aucun des trois criteres...

6 / 15

Page 10: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

Un algorithme manipulable : le Boston Mechanism

Le Boston mechanism (BM) est l’algorithme d’affectation le pluscouramment utilise pour reguler les inscriptions scolaires

Boston (jusqu’en 2005), Chicago (jusqu’en 2009), Denver(jusqu’en 2009), Minneapolis, Amsterdam, Barcelone, Madrid,plusieurs villes au Royaume-Uni, Pekin...

Algorithme relativement intuitif qui vise a satisfaire au maximumles premiers vœux exprimes :

– on considere d’abord le 1er vœu des eleves ; les places sontdefinitivement attribuees en fonction des criteres de priorite

– on considere ensuite le 2e vœu des eleves refuses sur leur 1er

vœu ; les places restantes apres l’etape 1 sont definitivementattribuees en fonction des criteres de priorite

– etc. exemple

7 / 15

Page 11: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme de Boston : defauts

Le mecanisme de Boston presente trois defauts majeurs :

1. il est manipulable

2. il est inequitable (ne respecte pas les priorites)

3. il est inefficace (ne respecte pas les preferences)

Intuition : cet algorithme dissuade les eleves de classer en 1er vœuune ecole ou ils ont peu de chance d’etre admis

– si une ecole est tres demandee, un eleve qui la classe enpremier vœu risque fortement de ne pas l’obtenir et, in fine, deperdre sa priorite sur les autres ecoles

– incitation a mentir en sous-classant les ecoles tres demandees

Consequence : les eleves “naıfs” (ceux qui ordonnent leurs vœuxde maniere sincere) sont fortement penalises par cet algorithme

8 / 15

Page 12: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

Une alternative : l’algorithme d’acceptation differee

Un autre algorithme presente de bien meilleures proprietes :l’algorithme d’aceptation differee (Deferred acceptance)

Origine : theorie du “mariage stable” (Gale et Shapley, 1962)

De plus en plus utilise : Boston (depuis 2009), Chicago, NewYork, Seattle, Paris (AFFELNET), Allemagne, Belgique, Suede,Norvege, etc.

Fonctionnement :

– on considere d’abord le 1er vœu des eleves ; les places sonttemporairement attribuees en fonction des criteres de priorite

– on considere ensuite le 2e vœu des eleves refuses sur leur 1er

vœu ; chaque ecole considere les demandes accepteesprecedemment + les nouvelles demandes ; les places sonttemporairement attribuees en fonction des criteres de priorite

– etc. exemple

9 / 15

Page 13: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme d’acceptation differee : proprietes

L’algorithme d’acceptation differee a plusieurs bonnes proprietes :

– Il respecte les priorites (equite) : garantit qu’aucun eleve n’ad’“envie justifiee” (∼ mariage stable)

– il est non-manipulable : etre sincere est la meilleure strategie

– il est efficace sous contrainte : parmi les algorithmes quirespectent les priorites, c’est celui qui donne la satisfaction laplus elevee possible aux eleves

Mais le respect des priorites a un cout en termes d’efficacite :certains eleves pourraient echanger leurs affectations de faconmutuellement avantageuse (au prix d’une violation des priorites)

Il existe un algorithme non-manipulable et efficace : les cyclesd’echanges (Top trading cyles) → peu utilise en pratique cardifficile a expliquer et tolere des violations de priorite

10 / 15

Page 14: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

APB et la regulation desinscriptions dans le superieur

11 / 15

Page 15: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

Admission Post-Bac : vœux et criteres de priorite

APB : procedure centralisee de pre-inscription dans le superieur

– prouesse technique

– donnees tres precieuses pour la recherche

Vœux : 12 maximum par type de formation (licence, CPGE,STS...), dans la limite de 24 vœux au total

Priorites :

– Filieres selectives (CPGE, STS, etc.) : classement opere parles formations

– Filieres non-selectives (licences) : si la demande est superieurea la capacite d’accueil, application de criteres hierarchises

1. candidats de l’academie > hors academie2. rang relatif du vœu (= parmi formations de meme type)3. rang absolu du vœu (= parmi tous les vœux)4. nombre aleatoire (tirage au sort)

11 / 15

Page 16: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

Admission Post-Bac : l’algorithme et ses proprietes

Algorithme : (a priori) une version de l’algorithme d’acceptationdifferee de Gale et Shapley → bonne proprietes

Probleme : prise en compte du rang du vœu (absolu ou relatif)comme critere de priorite pour les licences “en tension” (Droit,PACES, Psycho, STAPS)

Rend l’algorithme manipulable : mettre en haut de sa liste uneformation selective ou une licence en tension fait courir le risque de“perdre sa priorite” sur les licences en tension situees plus loin danssa liste (comme dans l’algorithme de Boston)

Consequence : penalise les candidats qui classent leurs vœux demaniere sincere

12 / 15

Page 17: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

Admission Post-Bac : exemple

Preferences reelles de 3 candidats :

Lea (Toulouse) Theo (Poitiers) Antoine (Bordeaux)

1. L1 Psycho (Bordeaux) 1. CPGE [refuse] 1. L1 Psycho (Bordeaux)

2. L1 Droit (Bordeaux) 2. L1 Droit (Bordeaux)

Capacites d’accueil : 1 place en Psycho, 1 place en Droit

Si Lea classe sincerement ses vœux, elle n’en obtient aucun :

– classee apres Antoine pour Psycho (critere academie)

– classee apres Theo pour Droit (critere rang relatif du vœu)

Lea a interet a etre strategique en classant la L1 Droit en 1er vœu :elle passe alors devant Theo (critere de rang absolu du vœu) etsera admise sur ce vœu

13 / 15

Page 18: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

Admission Post-Bac : revoir les criteres de priorite ?

Faut-il revoir les criteres de priorite utilises dans APB ?

“Avantage” des criteres actuels : incitent les etudiants as’auto-censurer → limite le recours au tirage au sort

Mais inconvenients nombreux :

– Equite : penalise les candidats “naıfs”qui classent leurs vœuxde maniere sincere au profit des etudiants les mieux informes

– Lisibilite : difficile de donner des conseils clairs aux candidats

– Fiabilite des statistique sur la satisfaction des vœux

– Expoitation des donnees d’APB : les voeux fournissent uneinformation biaisee sur preferences reelles des candidats

Symptome des contradictions de l’enseignement superieur enFrance : principe de non-selection mais licences a capacite limitee→ debat necessaire sur les criteres de priorite en licence

14 / 15

8

2ème ETAPE – Confirmation des candidatures

La rubrique « CANDIDATURES » de votre espace personnel APB, vous indique :

L’état de chacune de vos candidatures : à confirmer/confirmée

L’avancement de la saisie de vos fiches pédagogiques par votre établissement, pour les élèves actuellement scolarisés en Terminale ou en classe de Mise à Niveau dans un établissement français ou au CNED en classe complète à inscription réglementée. Ce suivi est accessible en cliquant sur « Accès candidature » à partir du 28 mars. Les fiches seront pleinement consultables à compter du 1er juin.

Au plus tard le 2 avril 2017

Vous devez avoir impérativement confirmé chacune des candidatures qui vous intéressent.

Jusqu’au 31 mai 2017 minuit dernier délai

Vous pouvez modifier le classement de vos demandes de formations sous statut scolaire par ORDRE DE PREFERENCE ET SANS AUTOCENSURE en fonction :

de vos souhaits,

de votre projet de poursuite d’études,

de votre projet professionnel.

Les établissements demandés n’ont à aucun moment connaissance de votre liste ordonnée de vœux.

Vous pouvez modifier l’ordre de classement de votre liste hiérarchisée de vœux jusqu’au 31 mai minuit.

Passé le 31 mai 2017, votre liste devient définitive et ne peut plus être modifiée.

Avant de les confirmer, vérifiez bien que vous n’avez pas fait d’erreurs dans votre sélection, car elles deviennent définitives et sont comptabilisées dans le total des 24 candidatures par liste auxquelles vous avez droit.

Le 2 avril 2017 correspond donc à la date limite de :

modification de votre dossier (saisie ou remontée complète des bulletins, lettre de motivation,…),

confirmation des candidatures.

Votre vœu n°1 est votre vœu prioritaire, celui que vous désirez le plus.

Un vœu non classé ne pourra jamais vous être proposé.

Si vous ne formulez qu’un seul vœu, vous devez tout de même le classer en n°1.

(Source : Guide du candidat APB 2017)

Page 19: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

Admission Post-Bac : revoir les criteres de priorite ?

Faut-il revoir les criteres de priorite utilises dans APB ?

“Avantage” des criteres actuels : incitent les etudiants as’auto-censurer → limite le recours au tirage au sort

Mais inconvenients nombreux :

– Equite : penalise les candidats “naıfs”qui classent leurs vœuxde maniere sincere au profit des etudiants les mieux informes

– Lisibilite : difficile de donner des conseils clairs aux candidats

– Fiabilite des statistique sur la satisfaction des vœux

– Expoitation des donnees d’APB : les voeux fournissent uneinformation biaisee sur preferences reelles des candidats

Symptome des contradictions de l’enseignement superieur enFrance : principe de non-selection mais licences a capacite limitee→ debat necessaire sur les criteres de priorite en licence

14 / 15

Page 20: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

Conclusion

Les algorithmes d’affectation des eleves sont des outils puissantsde regulation des choix scolaire :

– regles de priorite transparentes

– incitations a la revelation sincere des preferences

– mise en œuvre d’objectifs de politique educative

Ne pas se tromper de polemique : les vrais obstacles a la miseen œuvre de procedures d’affectation efficaces et equitables sontplutot

– la complexite souvent inutile des procedures

– le defaut d’information

– l’absence de debat de fond sur les criteres de priorite

15 / 15

Page 21: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

Merci de votre attention

Page 22: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme de Boston : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme de Boston :

16 / 15

Page 23: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme de Boston : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme de Boston :

16 / 15

Page 24: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme de Boston : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme de Boston :

Etape 1 : on considere le 1er vœu de chaque eleve

– i1 candidate a s2 et y est affecte (pas d’autre candidat)

– i2 et i3 candidatent a s1. Puisqu’il n’y a qu’une place et que i3 apriorite sur i2, i3 est affecte a s1

16 / 15

Page 25: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme de Boston : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme de Boston :

Etape 1 : on considere le 1er vœu de chaque eleve

– i1 candidate a s2 et y est affecte (pas d’autre candidat)

– i2 et i3 candidatent a s1. Puisqu’il n’y a qu’une place et que i3 apriorite sur i2, i3 est affecte a s1

16 / 15

Page 26: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme de Boston : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme de Boston :

Etape 1 : on considere le 1er vœu de chaque eleve

– i1 candidate a s2 et y est affecte (pas d’autre candidat)

– i2 et i3 candidatent a s1. Puisqu’il n’y a qu’une place et que i3 apriorite sur i2, i3 est affecte a s1

16 / 15

Page 27: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme de Boston : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme de Boston :

Etape 1 : on considere le 1er vœu de chaque eleve

– i1 candidate a s2 et y est affecte (pas d’autre candidat)

– i2 et i3 candidatent a s1. Puisqu’il n’y a qu’une place et que i3 apriorite sur i2, i3 est affecte a s1

16 / 15

Page 28: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme de Boston : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme de Boston :

Etape 1 : on considere le 1er vœu de chaque eleve

– i1 candidate a s2 et y est affecte (pas d’autre candidat)

– i2 et i3 candidatent a s1. Puisqu’il n’y a qu’une place et que i3 apriorite sur i2, i3 est affecte a s1

16 / 15

X

Page 29: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme de Boston : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme de Boston :

Etape 2 : i2 candidate a s2 mais est refuse (plus de place)

16 / 15

X

Page 30: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme de Boston : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme de Boston :

Etape 2 : i2 candidate a s2 mais est refuse (plus de place)

16 / 15

X X

Page 31: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme de Boston : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme de Boston :

Etape 3 : i2 candidate a s3 et y est affecte

16 / 15

X X

Page 32: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme de Boston : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme de Boston :

Etape 3 : i2 candidate a s3 et y est affecte

16 / 15

X X

Page 33: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme de Boston : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme de Boston :

Affectation finale :

µBM =

(i1 i2 i3s2 s3 s1

)

16 / 15

X X

Page 34: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme de Boston : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme de Boston :

Affectation finale :

µBM =

(i1 i2 i3s2 s3 s1

)L’algorithme de Boston est manipulable : i2 est incite a mentir enclassant s2 en 1er vœu. Il serait alors affecte a s2 (qu’il prefere a s3)

16 / 15

X X

Page 35: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme de Boston : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme de Boston :

Plus generalement, l’algorithme de Boston dissuade les eleves declasser en 1er vœ une ecole ou ils ont peu de chances d’etre admis,car il risquent de perdre leur priorite pour les ecoles classees plus loindans leur liste

Consequence : les eleves “naıfs” (ceux qui ordonnent leurs vœux demaniere sincere) sont fortement penalises par cet algorithme retour

16 / 15

X X

Page 36: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme d’acceptation differee : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme d’acceptation differee :

17 / 15

Page 37: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme d’acceptation differee : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme d’acceptation differee :

Etape 1 : on considere le 1er vœu de chaque eleve

- i1 candidate a s2 et y est temporairement affecte

- i2 et i3 candidatent a s1. Il n’y a qu’une place : i3 esttemporairement affecte a s1 car il a priorite sur i2, qui est rejete

17 / 15

Page 38: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme d’acceptation differee : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme d’acceptation differee :

Etape 1 : on considere le 1er vœu de chaque eleve

- i1 candidate a s2 et y est temporairement affecte

- i2 et i3 candidatent a s1. Il n’y a qu’une place : i3 esttemporairement affecte a s1 car il a priorite sur i2, qui est rejete

17 / 15

Page 39: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme d’acceptation differee : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme d’acceptation differee :

Etape 1 : on considere le 1er vœu de chaque eleve

- i1 candidate a s2 et y est temporairement affecte

- i2 et i3 candidatent a s1. Il n’y a qu’une place : i3 esttemporairement affecte a s1 car il a priorite sur i2, qui est rejete

17 / 15

Page 40: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme d’acceptation differee : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme d’acceptation differee :

Etape 1 : on considere le 1er vœu de chaque eleve

- i1 candidate a s2 et y est temporairement affecte

- i2 et i3 candidatent a s1. Il n’y a qu’une place : i3 esttemporairement affecte a s1 car il a priorite sur i2, qui est rejete

17 / 15

Page 41: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme d’acceptation differee : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme d’acceptation differee :

Etape 1 : on considere le 1er vœu de chaque eleve

- i1 candidate a s2 et y est temporairement affecte

- i2 et i3 candidatent a s1. Il n’y a qu’une place : i3 esttemporairement affecte a s1 car il a priorite sur i2, qui est rejete

17 / 15

X

Page 42: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme d’acceptation differee : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme d’acceptation differee :

Etape 2 : i2 (rejete a l’etape precedente) candidate a s2

- s2 considere conjointement i2 et i1

- Puisque i2 a une priorite plus eleve, il est temporairement affectea s2, et i1 est rejete

17 / 15

X

Page 43: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme d’acceptation differee : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme d’acceptation differee :

Etape 2 : i2 (rejete a l’etape precedente) candidate a s2

- s2 considere conjointement i2 et i1

- Puisque i2 a une priorite plus eleve, il est temporairement affectea s2, et i1 est rejete

17 / 15

X

Page 44: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme d’acceptation differee : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme d’acceptation differee :

Etape 2 : i2 (rejete a l’etape precedente) candidate a s2

- s2 considere conjointement i2 et i1

- Puisque i2 a une priorite plus eleve, il est temporairement affectea s2, et i1 est rejete

17 / 15

X

X

Page 45: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme d’acceptation differee : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme d’acceptation differee :

Etape 3 : i1 (rejete a l’etape precedente) candidate a s1

- s1 considere conjointement i1 et i3

- ii est temporairement affecte a s1, et i3 est rejete

17 / 15

X

X

Page 46: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme d’acceptation differee : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme d’acceptation differee :

Etape 3 : i1 (rejete a l’etape precedente) candidate a s1

- s1 considere conjointement i1 et i3

- ii est temporairement affecte a s1, et i3 est rejete

17 / 15

X

X

Page 47: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme d’acceptation differee : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme d’acceptation differee :

Etape 3 : i1 (rejete a l’etape precedente) candidate a s1

- s1 considere conjointement i1 et i3

- ii est temporairement affecte a s1, et i3 est rejete

17 / 15

X

X

X

Page 48: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme d’acceptation differee : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme d’acceptation differee :

Etape 4 : i3 candidate a s2 et est rejete

17 / 15

X

X

X

Page 49: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme d’acceptation differee : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme d’acceptation differee :

Etape 4 : i3 candidate a s2 et est rejete

17 / 15

X

X

X X

Page 50: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme d’acceptation differee : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme d’acceptation differee :

Etape 5 : i3 candidate a s3 et y est temporairement admis

17 / 15

X

X

X X

Page 51: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme d’acceptation differee : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme d’acceptation differee :

Etape 5 : i3 candidate a s3 et y est temporairement admis

17 / 15

X

X

X X

Page 52: Journée #OpenAPB - intervention de Julien Grenet (Ecole d'Economie de Paris)

L’algorithme d’acceptation differee : exemple

Preferences des eleves Priorites Capacite des ecoles

i1 : (s2, s1, s3) s1 : (i1, i3, i2) q1 = 1

i2 : (s1, s2, s3) s2 : (i2, i1, i3) q2 = 1

i3 : (s1, s2, s3) s3 : (i2, i1, i3) q3 = 1

Algorithme d’acceptation differee :

Affectation finale : Aucune offre n’etant plus rejetee, l’affectation estfinalisee et l’algorithme aboutit a

µDA =

(i1 i2 i3s1 s2 s3

)retour

17 / 15

X

X

X X