Démission Ulm

[mxh]

hello,

quelq'u'un a t il trouvé une spécification précise de l'alogorithme utilisé par SCEI ? Est - il capable de sortir la meilleur proposition d'affectation possible ? C'est à dire telle qu'on ne puisse pas avoir une meilleure proposition d'affectation pour au moins un candidat, (et sans moins bonne pour tous les autres ) ?

Par exemple , sait-il éviter la configuration suivante :
- l'élève A proposé à Ulm , et premier sur la Liste d'Attente de l'X , qui est son premier choix,
- l'élève B proposé à l'X , et premier sur la Liste d'Attente d'Ulm , qui est son premier choix.
En effet proposer Ulm à B et l'X à A est un meilleur choix pour les deux .
Il me semble qu'un algorithme simple qui affecte d'abord les admis en premier choix, libère les places qu'ils laissent dans les autres écoles, itère ainsi jusqu'à ce que ça ne bouge plus, puis passe au deuxième choix, etc. peut arriver à cette configuration .
Dans notre cas si A et B se connaissent , ils peuvent s'en sortir , l'un au moins répond "non mais" , il libère ainsi une place , l'autre répond "oui mais" ou "non mais" et au deuxième appel chacun a son meilleur choix ; mais en pratique , c'est impossible à faire sans se connaître et sans une confiance absolue !
EDIT du 26 juillet 2009: en cas de surbooking faite par une école, qui anticipe les "non" ou "non mais" , la liste d'attente n'avancera pas et la technique décrite ci-dessus ne marche pas , il faut appeler les écoles pour vérifier, mais entre X et Ulm pas de surbooking !

Dans le cas des CCP , on doit pouvoir trouver ainsi des configurations beaucoup plus complexes, avec des choix relatifs bien plus souvent différents entre candidats .

MXH

[lhommekipasse]

Mets "oui mais" (pour ne rien regretter), mais prépare-toi à aller à l'X, parce que c'est ce qui va arriver avec 99% de chances...

Mais c'est pas grave, l'X c'est bien aussi !

[Julian]

Pour celui qui se demande comment marche scei : il calcule tout pour que chacun ait le truc le plus haut dans sa liste. En fait si tout le monde mettait "oui mais" ou alors "oui definitif" PERSONNE de liste d'attente serait EFFECTIVEMENT ADMIS ! les variations de liste d'attente sont essentiellement dues aux "oui definitif" des gens classés avant soi sur cette meme liste d'attente. Il y a aussi des ecoles qui sont pas dans SCEI... donc toujours un petit espoir. Enfin quelqu'un premier sur liste d'attente à ULM doit esperer que 3 personnes preferent faire 5/2 alors qu'elles sont prises à ulm, ou bien que les 2 devant lui acceptent definitivement l'ecole proposée et qu'une seule personne fasse 5/2. Sachant que c'est le plus dur à avoir il y a pas beaucoup de chances malheureusement.

[mxh]

Mets "oui mais" (pour ne rien regretter), mais prépare-toi à aller à l'X, parce que c'est ce qui va arriver avec 99% de chances...

Je suis plutôt de la génération du modérateur de ce forum ; et c'est d'abord un intérêt paternel qui m'a amené sur ce forum ; ensuite lisant les questions des uns et des autres , et ayant fait de l'"info fondamentale" , comme on dit aujourd'hui , parcourant ce post , je me suis demandé si l'algorithme SCEI maximisait ou non les choix des candidats et j'ai donné un exemple où cela pourrait ne pas être le cas.
Il n'est pas garanti que SCEI cherche à maximiser le choix des candidats , il peut aussi chercher à minimiser le rang du dernier entré à l'école ( et compatible avec l'ordre de veux de chacun et le classement) ; dans le cas de mon exemple , il laissera donc A à Ulm et B à l'X. Seulement avec ce que je propose , si les élèves se connaissent ils peuvent résoudre ce cas . Maintenant si on prend les écoles CCP, on doit avoir des configurations beaucoup plus compliquées , et réellement impossibles à résoudre entre élèves. Il est tout à fait possible que l'algorithme propose quelque chose de compatible avec ces deux ordres ( ordre de voeux et classement des écoles ) sans , en plus , maximiser les voeux possibles, ni le rang du dernier entré ...

Pour celui qui se demande comment marche scei : il calcule tout pour que chacun ait le truc le plus haut dans sa liste..

C'est bien la question que je pose : le fait-il effectivement ? S'il suit l'algorithme que je décris brièvement , ce ne sera pas le cas . D'ailleurs , je ne suis même pas sûr qu'il existe une seule configuration maximale .

En fait si tout le monde mettait "oui mais" ou alors "oui definitif" PERSONNE de liste d'attente serait EFFECTIVEMENT ADMIS !

Tout à fait , seuls les "non" ( démission ou "non mais" ) peuvent contribuer à faire bouger les propositions au deuxième tour ; c'est bien ce que j'utilise dans mn exemple.

MXH

[Julian]

En réalité presque tout le monde met les ecoles dans le meme ordre, en tout cas pour ce qui est des grandes grandes ecoles, et donc dans ce cas l'ecole proposée est bien la plus haute possible non?

[KaiM]

En réalité presque tout le monde met les ecoles dans le meme ordre, en tout cas pour ce qui est des grandes grandes ecoles, et donc dans ce cas l'ecole proposée est bien la plus haute possible non?

Compte tenu du nombre de places dans les "grandes grandes écoles" et du nombre total de taupins, je ne pense pas que "presque tout le monde" fasse sa liste de voeux dans le même ordre...


Par ailleurs, même pour les écoles les plus prestigieuses, c'est faux : on peut très bien avoir des admis à Ulm sur liste d'attente à l'X, et qui veulent l'X, et des admis à l'X qui veulent Ulm, où ils sont sur liste d'attente. La question est : l'algorithme de SCEI est-il capable de gérer au mieux ce genre de situation?

[chewie]

Le problème est leur place sur liste d'attente.
La solution "à l'amiable" proposé par mxh ne fonctionne pas nécessairement : s'il est trop loin sur liste d'attente, l'élève qui répond "non mais" se retrouve sans rien.

De plus, pourquoi un tel élève aurait ULM, d'autres l'ayant plus mérité ?

EDIT : Effectivement, j'avais oublié de lire le "premier"
Bon, cette configuration doit quand même être relativement rare ^^

[mxh]

Pour Julian: oui le cas que je cite est certainement rare mais peut exister et a certainement existé : pour qu'il se produise il faut des réussites diférentes avec donc des classements différents, et une inversion entre réussite et choix de l'élève : ceci peut exister entre X et Ulm , Ponts et Supélec, une Centrale et l'Ensimag ( pour un informaticien ) , mais pas entre deux écoles des CCP , qui ont le même classement .

Pour chewie , pour te taquiner , je dirai que si tu rentres en MP , il te faudra mieux lire les énoncés de concours que les posts de ce forum :
- dans l'exemple que j'ai pris les deux élèves sont premiers sur la liste d'attente de leur école préférée où l'autre a une proposition d'intégration : ma solution à l'amiable marche, et celui qui a le plus "mérité" Ulm préfère l'X et serait donc très content de laisser sa place à Ulm pour pouvoir aller à l'X.

MXH

EDIT après l'édition de chewie : oui configuration rare , mais pas très rare ; en effet , comme il est assez fréquent que l'ordre de choix des candidats soient "1 Ulm, 2 X " ou "1 X, 2 Ulm" et vu le nombre de places de chacun des concours, le premier sur liste d'attente de Ulm doit être assez souvent admis à l'X , et le premier sur liste d'attente de l'X peut l'être ( mais sans doute moins souvent ) , en n'oubliant pas que pour être sur liste d'attente, il faut ne pas avoir eu son premier choix.

[PierreR]

C'est effectivement un problème bien plus délicat qu'il n'y parait au premier abord.

Rappel : SCEI est financé par les écoles. Il est donc normal qu'ils cherchent à obtenir la configuration la meilleure du point de vue des écoles (elles prennent les candidats qu'elles ont le mieux classés par leur concour) et non les élèves (en tout cas c'est ce que nous a affirmé un TDman qui avait été assez motivé pour les harceler jusqu'à obtenir la réponse). Là j'ai un peu la flemme de ressortir le TD en question (ben oui, c'est les vacances tout de même) mais si ça interesse quelqu'un, demandez.

[mxh]

Oui ça m'intéresse bien d'avoir les infos de ton TDman, mais je ne pense pas qu'il y ait d'urgence, car , effectivement , c'est sans doute un algorithme qui minimise le rang d'entrée ( modulo les démissions ou "non mais" , incontrôlables par les écoles) qui doit être en place , et peut-être pas uniquement car ce serait l'intérêt des écoles, mais aussi car c'est sans doute plus simple ; et , donc , pas moyen pour les admis de l'année de "réclamer" .
En revanche s'il tombe dans un cas proche de ce que j'ai proposé , l'auteur du post initial ( s'il s'agissait bien de lui ) peut toujours essayer de voir s'il y a moyen de s'arranger, mais c'est aussi assez peu probable que le premier sur liste d'attente de l'X soit justement admis à Ulm.

Bonsoir,
MXH