Bonjour,
voici la situation :
Il n'y a que deux écoles : Lille et Marseille, avec une place chacune.
Il n'y a que deux candidats : un Lillois et un Marseillais.
Préférences du Lillois : Lille puis Marseille.
Préférences du Marseillais : Marseille puis Lille.
Classement de Lille : 1. Marseillais 2. Lillois.
Classement de Marseille : 1. Lillois 2. Marseillais.
Je ne vois pas comment l'algorithme systématique de SCEI va faire pour proposer Lille au Lillois et Marseille au Marseillais... j'ai loupé quelque chose?
Question d'algorithme SCEI
Re: Question d'algorithme SCEI
(Ceci est abordé dans la FAQ SCEI dans cette section même et dans les messages qui lui sont liés) cette situation a failli arriver en 2008 entre X et ENS.
Sans que nous en ayons eu la preuve absolue, il semblerait que SCEI implémente effectivement un algorithme qui "favorise les écoles" et donc, par défaut, le choix proposé au Marseillais sera Lille et vice-versa . Si l'un des deux répond"non mais", et l'autre "non mais ou "oui mais" , chacun finira dans sa ville . Mais dans la réalité , jouer à ça est très dangereux ( il faut connaître tout le contexte , et les éventuels surbookings).
Sans que nous en ayons eu la preuve absolue, il semblerait que SCEI implémente effectivement un algorithme qui "favorise les écoles" et donc, par défaut, le choix proposé au Marseillais sera Lille et vice-versa . Si l'un des deux répond"non mais", et l'autre "non mais ou "oui mais" , chacun finira dans sa ville . Mais dans la réalité , jouer à ça est très dangereux ( il faut connaître tout le contexte , et les éventuels surbookings).
Re: Question d'algorithme SCEI
Justement, j'ai un gros doute et je n'ai pas pu trouver l'algorithme exact, seulement des explications qui ne sont pas tout à fait précises sur ce genre de cas particulier... donc si quelqu'un a l'algorithme strict, ça m'intéresse.
Re: Question d'algorithme SCEI
Si le responsable de l'algorithme SCEI a l'amabilité de passer par ici et de nous le dire, ce serait sympa 
.
Mais bon , la "rumeur" dit plutôt que c'est le choix favorable aux écoles , et comme c'est bien ce qu'on obtient en remplissant les promos à partir des écoles, ce qui est l'automatisation de ce qui se passait "avant", quand ça se passait par appel un à un sur les listes complémentaires de chaque concours/école, c'est assez logique.
D'où vient ton "gros doute"?
. Mais bon , la "rumeur" dit plutôt que c'est le choix favorable aux écoles , et comme c'est bien ce qu'on obtient en remplissant les promos à partir des écoles, ce qui est l'automatisation de ce qui se passait "avant", quand ça se passait par appel un à un sur les listes complémentaires de chaque concours/école, c'est assez logique.
D'où vient ton "gros doute"?
Dernière modification par mxh le 24 juil. 2011 23:33, modifié 1 fois.
Re: Question d'algorithme SCEI
D'après moi, pour que les candidats aient intérêt à classer les voeux par préférence sans stratégie, cela veut dire que l'algorithme :
- prend les candidats un par un;
- affecte temporairement chaque candidat à son meilleur voeu où il est pris;
- démissionne immédiatement ce candidat des voeux qu'il a placé derrière;
- boucle ainsi plusieurs fois pour que les places libérées soient réaffectées.
Mais apparemment ceci n'empêche pas les situations de blocage ou deux candidats auraient chacun intérêt à démissionner pour avoir un voeu mieux classé... à moins que l'algorithme ne prévoie ensuite de détecter les cycles afin de les résoudre et de faire en sorte que personne n'ait intérêt à échanger sa place avec un autre (intérêt théorique vu que les candidats ne peuvent ni se parler ni échanger les places en pratique).
- prend les candidats un par un;
- affecte temporairement chaque candidat à son meilleur voeu où il est pris;
- démissionne immédiatement ce candidat des voeux qu'il a placé derrière;
- boucle ainsi plusieurs fois pour que les places libérées soient réaffectées.
Mais apparemment ceci n'empêche pas les situations de blocage ou deux candidats auraient chacun intérêt à démissionner pour avoir un voeu mieux classé... à moins que l'algorithme ne prévoie ensuite de détecter les cycles afin de les résoudre et de faire en sorte que personne n'ait intérêt à échanger sa place avec un autre (intérêt théorique vu que les candidats ne peuvent ni se parler ni échanger les places en pratique).
Re: Question d'algorithme SCEI
Je te conseille de lire d'abord les messages sur SCEI et APB, et les mariages stables ( fais un petit coup de recherche éventuellement : le point d'entrée de la FAQ est là : avec d'autres liens à l'intérieur: http://forum.prepas.org/viewtopic.php?f=7&t=26566 ) .
Ce qui appelle une situation de "blocage" n'en est pas une : c'est une situation non optimale pour les candidats , mais "meilleure" pour les écoles ( au sens où elles minimisent le rang de leur dernier entré sur leur concours); et donc il semble bien que SCEI ne cherche pas à résoudre ce problème, qui , en plus doit être d'occurence rare.
Et il est probable que SCEI ne marche pas en bouclant sur les élèves mais sur les écoles.
Ce qui appelle une situation de "blocage" n'en est pas une : c'est une situation non optimale pour les candidats , mais "meilleure" pour les écoles ( au sens où elles minimisent le rang de leur dernier entré sur leur concours); et donc il semble bien que SCEI ne cherche pas à résoudre ce problème, qui , en plus doit être d'occurence rare.
Et il est probable que SCEI ne marche pas en bouclant sur les élèves mais sur les écoles.
Re: Question d'algorithme SCEI
Ce serait très grave, car cela voudrait dire que les conseils du type "mettez l'ordre de vos préférences sans penser à une stratégie", qui est notamment donné par SCEI, conduit à des situations désavantageuses pour certains candidats.mxh a écrit :Ce qui appelle une situation de "blocage" n'en est pas une : c'est une situation non optimale pour les candidats , mais "meilleure" pour les écoles ( au sens où elles minimisent le rang de leur dernier entré sur leur concours); et donc il semble bien que SCEI ne cherche pas à résoudre ce problème, qui , en plus doit être d'occurence rare.
Et il est probable que SCEI ne marche pas en bouclant sur les élèves mais sur les écoles.
Re: Question d'algorithme SCEI
Je comprend pas le problème !! Au final on a la première école de sa liste à laquelle on peut prétendre avec son classement...
Certes on se retrouve dans des cas où quelqu'un de classé disons au pif 1543, rentre dans l'école A alors que c'était son vœu 3 mais le 1544 l'avait mis en 1 et 'y rentre pas parcequ'il n'y a plus de place. Mais c'est comme ça. Le premier n'a pas eu son vœu 1 et 2 non plus.
Certes on se retrouve dans des cas où quelqu'un de classé disons au pif 1543, rentre dans l'école A alors que c'était son vœu 3 mais le 1544 l'avait mis en 1 et 'y rentre pas parcequ'il n'y a plus de place. Mais c'est comme ça. Le premier n'a pas eu son vœu 1 et 2 non plus.
Re: Question d'algorithme SCEI
Pas dans mon exemple : la solution ou chacun a son premier voeu est possible et cohérente avec les classements et optimale pour les candidats mais me semble inaccessible par un algorithme de mariages...
Re: Question d'algorithme SCEI
comme indiqué sur les fils déjà présents et déjà référencés
http://en.wikipedia.org/wiki/Stable_marriage_problem
http://en.wikipedia.org/wiki/Stable_marriage_problem
Optimality of the Solution
While the solution is stable, it is not necessarily optimal from all individuals' points of view. The traditional form of the algorithm is optimal for the initiator of the proposals and the stable, suitor-optimal solution may or may not be optimal for the reviewer of the proposals
The hospitals/residents problem — also known as the college admissions problem — differs from the stable marriage problem in that the "women" can accept "proposals" from more than one "man" (e.g., a hospital can take multiple residents, or a college can take an incoming class of more than one student). Algorithms to solve the hospitals/residents problem can be hospital-oriented (female-optimal) or resident-oriented (male-optimal).