Devez-vous quitter votre femme pour celle du voisin ?

Présentation :

Voici mon premier article, où j'essaye de faire découvrir les travaux des prix Nobel d'économie de 2012 qui sont souvent méconnus mais qui ont pourtant des tas d'applications pratiques dans la vie de tous les jours.

Merci pour vos retours

Devez vous quitter votre femme pour celle du voisin ?

Je ne sais pas si vous vous êtes déjà posé cette question (je ne veux pas savoir ) mais c'est une question qui intéresse beaucoup les économistes. Oui ce sont des gens un peu bizarres.

L'idée derrière cette question est de s'intéresser au marché de la rencontre. Supposons que vous ayez 100 hommes et 100 femmes qui veulent se marier, comment organiser des couples de façon efficace pour que chacun soit satisfait de la situation ? Si cela peut vous faire sourire, sachez que les mécanismes qui sont en jeu derrière cela sont fondamentaux en économie et ont plein d'applications pratiques dans la vie de tous les jours ! Bienvenue dans le monde du market design, ou l'art de concevoir un marché qui fonctionne.

Un marché de la rencontre efficace.

Revenons à nos 100 hommes et femmes qui veulent se marier de façon optimale. On cherche à réaliser ce qu'on appelle une allocation des ressources (ici les hommes et les femmes), c'est à dire à les distribuer. Et on veut que cette distribution des couples soit satisfaisante pour un maximum de personnes (si l'année suivante 95 de nos couples ont divorcé c'est que notre allocation n'était peut être pas super…). Pour pouvoir réfléchir à un mécanisme d'allocation efficace de notre marché de la rencontre, il faut définir ce qu'est une allocation efficace. Heureusement pour nous, les économistes ont trouvé une réponse simple et satisfaisante à cette question depuis longtemps:

Dans notre cas, une allocation optimale du marché est une situation où tous les couples sont stables, c'est à dire qu'aucun participant ne peut trouver une autre personne qui veut bien de lui et qui est préférable à son partenaire actuel.

Comment organiser un processus qui conduise à un tel résultat ?

On pourrait imaginer organiser un bal populaire, où la règle serait qu'il est interdit de repartir seul à la fin de la soirée. Cela fonctionnerait, mais il n'est pas sûr que cette technique soit vraiment optimale.

Heureusement pour nous, en 1962 deux économistes, Llyod Shapley et David Gale proposent un algorithme qui permet de résoudre ce problème, dans un article intitulé : College Admissions and the Stability of Marriage. Cet article est considéré comme l'un des articles fondateurs du market design.

L'algorithme de Gale-Shapley :

L'algorithme de Gale-Shapley fonctionne de la façon suivante :

• étape 1 : les hommes font un classement des femmes et se proposent à celle qu'ils préfèrent.
• étape 2 : les femmes acceptent ou refusent les offres qu'elles reçoivent.
• étape 3 : les hommes qui sont célibataires après ce premier tour reformulent une offre mais cette fois à la femme qui est juste après sur leur liste de préférences.
• étape 4 : les femmes acceptent ou refusent ces nouvelles offres. Notons qu'une femme qui était en couple à l'étape précédente peut ainsi quitter son conjoint si un homme qu'elle lui estime supérieur lui fait une proposition. Son partenaire rejoindra alors le rang des célibataires à l'étape suivante.

On recommence à partir de l'étape 3 jusqu'à ce que tous les couples soient stables et formés. Après un certain nombre d'itérations, l'allocation des couples est optimale : aucune personne ne peut trouver mieux ailleurs et tout le monde est marié.

Vous allez me dire "oui, c'est rigolo¹ comme truc mais en pratique à quoi ça sert, personne ne trouve son conjoint en procédant de cette façon!". Vous avez raison, il est peu probable que Shapley et Gale vous aident à trouver l'âme sœur… mais cet algorithme est à la base de pleins de choses qui sont utilisées tous les jours.

Quand l'économie théorique est utile dans la vie courante.

Roth est un économiste qui s'intéresse à ce qu'on appelle en économie les marchés répugnants (repugnant markets) et qui va prolonger les travaux de Shapley et Gale tout en les popularisant. Les marchés répugnants sont des marchés où il serait possible en théorie d'avoir une régulation par les prix mais où celle-ci est impossible en pratique pour des raisons culturelles, éthiques ou religieuses. Un exemple classique est le don d'organe. On sait qu'il existe une pénurie de donneurs et qu'autoriser la vente d'organes serait une façon efficace de lutter contre ce problème. Mais les sociétés se refusent à l'autoriser.

Au lieu de s'énerver comme certains de ses collègues sur le fait que les gens sont trop conservateurs, Roth décide d'accepter ces limites posées par la société et réfléchit à une façon de rendre ces marchés plus efficaces, sans passer par un mécanisme de prix.

Il va alors avoir l'idée de reprendre les travaux de Shapley et Gale et d'utiliser leur façon de procéder pour arranger les mariages afin de résoudre des problèmes bien plus concrets. Il va perfectionner l’algorithme pour le rendre plus efficace et pour l'adapter aux situations de pénuries, par exemple si on devait organiser des mariages avec 100 hommes et 90 femmes. Voici quelques illustrations qui montrent comment ces travaux ont été appliqués :

• L'affectation des médecins dans les hôpitaux : chaque médecin préférerait travailler dans certains hôpitaux plutôt que dans d'autres. Un hôpital lui aimerait avoir les meilleurs médecins possible. Et bien un processus à la Gale-Shapley permet de réaliser une allocation "médecins-hôpitaux" qui satisfait le maximum de monde. Ainsi en 1995 le système de répartition des médecins dans les hôpitaux américains, le National Resident Matching Program (NRMP) fait appel à Roth pour améliorer son système de répartition.

• La répartition des étudiants dans les universités : si vous avez connu le site Admission Post Bac, (APB) sachez qu'il fonctionne exactement sur le principe de l'algorithme de Gale-Shapley. Il suffit à chaque étudiant de classer ses différents vœux et le système va répartir les étudiants entre les universités en fonctions des places disponibles et du niveau des étudiants de la façon la plus performante possible. Si vous n'avez pas eu de place dans la classe préparatoire de votre rêve à cause d'APB, vous savez qui est le responsable maintenant

- Le don d'organe, en particulier le don de rein. Le don de rein est particulier car souvent on accepte de donner à un proche, mais on refuserait de vendre son rein ou de le donner à une autre personne. Malheureusement un donneur et son proche sont souvent incompatibles entre eux pour des raisons génétiques. Le donneur n'est pas prêt à donner son rein à une autre personne, sauf s'il a l'assurance de voir son proche bénéficier lui aussi d'un don d'une autre personne. Alvin Roth a alors l'idée d'organiser un don croisé : A n'est pas compatible avec B. A donne alors son rein à C qui lui a un proche prêt à donner, qui donne à D, qui a un proche qui est compatible avec B. La boucle est bouclée, tout le monde finit par trouver un rein ! Et quoi de mieux que l'algorithme de Gate-Shapeley pour organiser ces chaînes de dons de façon optimale à grande échelle? Ce système sera testé dans un premier temps en nouvelle-Angleterre et sera par la suite étendu partout aux états-unis où il sauvera de nombreuses vies chaque années et en sauve toujours.

Comme vous le voyez, de nombreuses situations réelles peuvent être améliorées par un système de ce genre. On pourrait aussi citer des sites de rencontres qui utilisent en général des algorithmes plus ou moins proches pour proposer des partenaires aux gens.

Conclusion :

À travers ce petit exemple de l’arrangement des mariages, vous avez pu découvrir un mécanisme fondamental de la recherche en économie moderne et ces applications. Le market design, qui consiste à imaginer des solutions pour allouer des ressources entre différents acteurs en l’absence de prix est une discipline qui a encore de beaux jours devant elle. Par exemple certains économistes suggèrent de s'en inspirer pour résoudre les problème migratoires en Europe, en particulier le souci de la répartition des migrants³ entre les différents pays d'accueil…

Alors, pour les fautes : J'en ai corrigé pas mal, en ai laissé d'autres pour que tu comprennes ce que j'ai voulu montrer, et tout est dans l'ordre du texte. Have fun.

• Je ne sais pas si vous vous êtes déjà posé cette question (je ne veux pas savoir ) mais c'est une question qui intéresse beaucoup les économistes. Oui ce sont des gens un peu bizarres.
• On cherche à réaliser ce qu'on appelle une allocation des ressources (ici les hommes et les femmes)
• Une allocation est dite optimale si il est impossible de trouver au moins deux personnes qui peuvent faire un échange mutuellement avantageux.

  Je ne trouve pas cette définition claire et simple

• où la règle serait qu'il serait interdit de repartir seul à la fin de la soirée.

  Correction proposée : où la règle serait la suivante : il est interdit aux participants de repartir célibataires à la fin de la soirée.

• Cela fonctionnerait, mais il n'est pas sûr que cette technique soit vraiment optimale.
• Heureusement pour nous en 1962, deux économistes, Llyod Shapley et David Gale, proposent un algorithme qui permet de résoudre ce problème dans un article intitulé ; College Admissions and the Stability of Marriage. Cet article est considéré comme un des articles fondateurs du market design.
• Un algorithme est simplement une procédure dont il suffit de suivre les étapes pour obtenir le résultat qu'on souhaite (si l'algorithme est correctement conçu pour cela).

  Une bulle d’info ici, au lieu du texte en dur ?

• étape 1 : les hommes font un classement des femmes et se proposent à celle qu'ils préfèrent.
• étape 3 : les hommes qui sont célibataires après ce premier tour reformulent une offre mais cette fois à la femme qui est juste après sur leur liste de préférences.
• Une des particularité de cet algorithme est qu'il est est conçu de façon à ne pas pouvoir être manipulé par les participants qui pourraient essayer par exemple de se dire « Je vais mettre la femme que je préfère en second sur la liste car si je la mets en première je n'ai aucune chance de l'avoir ». Le système fait que les hommes ont intérêt à faire une liste qui reflète leurs préférences réelles car c'est ce qui sera le plus efficace. C'est ce qu'on appelle un mécanisme de « Truth Telling ».
• Roth est un économiste qui s'intéresse à ce qu'on appelle en économie les marchés répugnants (repugnant markets) et qui va prolonger les travaux de Shapley et Gates tout en les popularisant.
• Au lieu de s'énerver certains de ses collègues

  Il ne manquerait pas un mot par hasard ?

• Il va alors avoir l'idée de reprendre les travaux de Shapley et Gale et d'utiliser leur façon de procéder pour arranger les mariages afin de résoudre
• par exemple si on devait organiser des mariages avec 100 hommes et 90 femmes. Voici quelques illustrations qui montrent comment ses travaux ont été appliqués :

  Je ne suis pas sûr pour celui là.

• L'affectation des médecins dans les hôpitaux : chaque médecin préférerait travailler dans certains hôpitaux plutôt que dans d'autres. Un hôpital, lui, aimerait avoir les meilleurs médecins possible. Et bien un processus à la (de ?) Gate-Shapley permet de réaliser une allocation « médecins-hôpitaux » qui satisfait le maximum de monde. Ainsi en 1995, le système de répartition des médecins dans les hôpitaux américains, le National Resident Matching Program (NRMP) fait appel à Roth pour améliorer son système de répartition.

  D'ailleurs pour ce passage pense à mettre en valeur l'entête de ta puce liste (L'affectation des médecins dans les hôpitaux pourrait être en gras par exemple)

• La répartition des étudiants dans les universités. Si vous avez connu le site Admission Post Bac, (APB) sachez qu'il fonctionne exactement sur le principe de l'algorithme de Gate-Shapley.
• la classe préparatoire de votre rêve à cause d’APB
• don de reins. Le don de reins

  Je ne mettrais pas de s personnellement.

• on accepte de donner à un proche, et on refuserait de vendre son rein

  Problème de concordance des temps là, non ?

• pour des raisons génétiques
• sauf si il a l'assurance
• Alvin Roth a alors l'idée
• qui lui a un proche prêt à
• D qui possède un proche qui est
• Ce système sera testé dans un premier temps en nouvelle-Angleterre et sera par la suite étendu partout aux états-unis où il sauve de nombreuses vies chaque années.
• États-Unis

  Encore la concordance des temps.

• peuvent être améliorées
• Shapley et Roth ont reçu en 2012
• des mécanisme de prix
• À travers
• vous avez pu avoir découvrir

  Un mot de trop ?

• ses applications
• qui a encore de beaux jours devant elle
• certains économistes suggèrent
• le souci (ou les soucis) de répartition

Pour le fond, je ne m'y connais pas assez pour critiquer réellement, mais je pense que tu pourrais rajouter les sources dans des notes en bas de page, avec des liens si tu en as (si tu n'as que des livres, tant pis, mais là tu m'as donné envie d'approfondir le sujet et c'est difficile de savoir par où commencer ).

Je viens de le lire, et je trouve ça intéressant, même si je n'ai pas les connaissances pour en dire plus. Je confirme que mettre des liens, même si c''est lourd, serait un plus.

Je voudrai juste dire, à propos de la répartition par Admission PostBac qu'une partie de la sélection (université en manque de place) se fait par tirage au sort, très loin du système décrit dans le reste de l'article, donc.

Whaaa merci Poliorcetics pour ce super retour, ça m’impressionnera toujours et ça me fait un peu honte ne de pas avoir fait mieux niveau orthographe… EDIT : c'est corrigé EDIT 2 : même moi sur la fin j'avais mal aux yeux tellement j'ai pu faire des fautes énormes, mes excuses pour l'agression visuelle que j'ai pu te causer et merci encore mille fois pour ce travail de relecture.

Concernant les liens c'est prévu d'en mettre, simplement pour l'instant je voulais simplement avoir une idée de comment était reçu l'article et si ça plaisait. Aussi les notes de bas de pages sont super pénibles à ajouter et ne me souvient jamais du code

Je voudrais juste dire, à propos de la répartition par Admission PostBac qu'une partie de la sélection (université en manque de place) se fait par tirage au sort, très loin du système décrit dans le reste de l'article, donc.

Bha en fait post bac ne concerne pas l'université car tu y as accès de droit. Post bac concerne uniquement l'université quand tu demandes une fac autre que celle de ton académie (typiquement Paris) et dans ce cas là tu n'es pas concerné par le tirage au sort (qui ne concerne que les "résidants" d'une académie quand il y a plus de demandes que de places). De plus je décris juste le mécanisme fondateur d'APB, mais je penses qu'ils ont leurs propre version de l'algorithme… Donc c'est pour ça que je ne parle pas de ce mécanisme de tirage au sort qui est propre à certaines universités et ne concerne pas vraiment mon propos ni le mécanisme fondamental du système. Mais tu as raison de rappeler que ça existe !

Pour les liens et notes de bas de pages j'en rajouterai demain, je penses que ça sera surtout en anglais mais je regarderais si je trouve des ressources complémentaires et utiles en français

Je n'ai pas vraiment de remarque à te soumettre, mais je voulais juste te dire que j'ai lu ton article et que je l'ai trouvé super ! Le sujet est intéressant et traité avec légèreté ce qui le rend amusant et facile à comprendre.

Bel article !

Merci pour ces retours, j'avoue que ça fait plaisir, je ne m'attendait pas à un accueil si positif je dois dire !

J'ai ajouté quelques notes de bas de pages pour aller un peu plus loin et en savoir plus. Je regarderais si je peux trouver encore d'autres ressources de qualité, mais c'est difficile de trouver des trucs accessibles sans tomber dans l'article académique qui n'as pas beaucoup de sens…

j'ai trouvé un truc en français qui développe l'aspect mathématique de la chose et explore des solutions un peu différentes, par exemples si les hommes sont amnésiques et oublient à qui ils ont fait des demandes… le seul problème est que je trouve que la qualité du scan rend la lecture difficile. Vous pensez que c'est trop problématique ou pas pour l'ajouter aux sources/notes de bas de page?

http://www-cs-faculty.stanford.edu/~uno/mariages-stables.pdf

Sur APB, le probleme resolu n'est pas celui d'une affectation stable mais d'une affectation optimale. Pas le meme probleme, pas les meme algorithmes. Il y a fort a parier qu'on a une variante d'algorithme de Khun pour hypergraphe pour APB.

Pareil pour les hopitaux. Le probleme n'est pas celui resolu par l'algorithme de Gale-Shapley, et est bien plus complexe (polynomial dans un cas, NP complet dans l'autre).

Höd, je t'ai déja demander d'arreter de troll mes sujets par ce tu t'étais fais volé ton gouter par un économiste à la récré quand tu étais petite

Pour répondre quand même :

1) Une allocation optimale au sens de Pareto est par définition stable donc c'est la même chose. De toute façon je parle de couples stable mais jamais d'allocation stable donc pourquoi tu fais cette remarque ?

2) l'académie Nobel indique elle même les contributions de Shapley et Roth et les applications dans les hôpitaux et l'affection des étudiants. Si tu n'es pas d'accord je te laisse leurs expliquer en quoi ils se trompent.

3) APB indique sur son site que c'est du Gale-Shapelay. http://www.admission-postbac.info/fr/fr/mecanisme-apb.html

Maintenant évite de venir troll mes sujets en racontant n'importe quoi et en sortant un nom d'algorithme qui n’a rien à voir. Tu pourrais au moins te renseigner un minimum, car là tes critiques sont aussi ridicules sur la forme que sur le fond…

PS : Toi tu fais tous pour que les économistes n'aiment pas les matheux non ? Enfin bon cela dit je doute qu'un vrai matheux ai ce genre d'attitude enfantine qui consiste à aller sur tous les sujets d'économie en sortant quelques trucs de maths pour montrer que ta discipline est la meilleure… (au passage le fait que ce problème soit np complet ou pas n'as pas la moindre importance et si les mariages et les hopitaux c'est strictement la même chose. En fait c'est pour avoir montrer ça mathématiquement que Roth à eu le Nobel. Donc je te laisse aller lire son article et en discuter avec lui si t'es pas de cet avis. Il y à le lien de son blog dans mon article, c'est facile. Mais arrête de venir troll ici stp.

Car au sens de Paretto c'est exactement la même chose…

C'est Pareto.
Esuite non, pas vraiment.

Le probleme d'affectation stable consiste a trouver un couplage parfait tel que chaque element de chaque couple prefere rester dans son couple.
Le probleme d'affectation optimale consiste a trouver un couplage parfait de poids minimal. Pas besoin de stabilite.

Cependant, dans certains contextes, le couplage optimal est egalement stable. Par ailleurs, on connait une methode polynomiale, donc efficace pour resoudre le second a peu pres 10 ans avant le premier. Les travaux de Roth-Shapley sur le marriage stables sont donc interessants pour les cas ou le couplage optimal n'est pas stable. Or, ce n'est pas le cas pour le protocole d'APB (et il y a d'autres considerations qui rentrent en ligne de compte) et donc je te dis de source sure que ce n'est pas Roth-Shapley qui est mit en place.

Les proprietes de stabilite et d'optimalite, bien que reliees voire superposees dans de nombreux cas (en particulier partiques), sont differentes. Sans compter evidemment qu'elles varient en fonction du contexte.

Après tu peux écrire au comité Nobel pour leurs expliquer en long en large que Gale-Shapley ça n'a rien à voir avec tout ça, mais évite de venir ici raconter des bêtises, c'est pénible de t'avoir sur le dos à dire n'importe quoi à longueur de temps. Fait ton contre-article si tu veux, mais stop.

C'est chiant de voire des etudiants en economie parler de choses de maniere superficielles parce qu'elles reposent sur des concepts et des notions qu'ils n'ont pas etudies (contrairement a Roth, et lui sait tres bien la difference entre un probleme d'affectation stable et un probleme d'affectation optimale mais je parie que tu n'as jamais lu une seule de ses publications mathematiques, n'est pas ?). Par exemple, sais-tu personnellement prouver l'optimalite de l'algorithme ? Sa complexite ? Que l'algorithme n'est pas manipulable ? Parce qu'avant de m'attaquer sur le terrain de la combinatoire, il va falloir me prouver que tu ne fais pas que reciter un vulgaire cours de brocante du dimanche qui consiste a aligner des faits a gober comme si c'etait la Bible.

Je t'invite a ouvrir ne serait-ce qu'un cours de mathematique, particulierement en theorie des graphes, en optimisation combinatoire, et complexite. Les choses que tu abordes dans ton articles ont surtout des fondements mathematiques. Les deux livres de Michel Sakarovitch sur l'optimisation combinatoire sont de bonnes references et normalement, de souvenir, assez accessibles.

Sauf qu'on est économie pas en maths, et en économie stabilité = optimalité par ce que c'est comme ça que fonctionne le critère de Pareto. Là si tu n'es pas d'accord j'avoue que je ne peux pas grand chose pour toi…

Si APB ne fonctionne pas comme ça je t'invite à sourcer ta "source sur" par ce que même leur site indique clairement que c'est un algorithme type Gale-Shapley. Et la procédure correspond exactement. Et aussi écrit à l'académie Nobel pour qu'ils modifient leurs biographies ils seront content de corriger toutes ces erreurs.

Sinon j'ai rarement vu plus pénible que toi dans le genre "je suis un mathématicien frustré trop mauvais pour réussir en maths alors je vais en économie où je peux étaler ma science et raconter n'importe quoi en prenant les gens de haut". Voilà c'est dit. Tu veux pas plutôt aller embêter les sociologues où les biologistes qui font de la théorie des jeux bizarres ? Ça me fera des vacances

PS: Si la modération pouvais lui faire passer le message que ses interventions inutiles ne sont pas les bienvenus, ça serait mieux pour tout le monde je crois.

Il serait appréciable de ne pas perdre de vue que le but est d'améliorer l'article (par ailleurs, on évite les titres "Conclusion" dans les articles, ce n'est pas un devoir ou un mémoire). Il en serait d'autant plus d'indiquer des références pour vos propos (Hod et tout autre membre ont le droit de faire des remarques sur le fond comme la forme, en respectant l'interlocuteur).

Voilà pour les remarques générales.

Maintenant, je vais passer à la partie un peu moins sympa. Peu importe si tu estimes qu'il se trompe ou non, Hod est intervenu sans jugement sur ta personne ni petites provoc' sous un ton "humoristique" ou sarcastique. Ce qui n'est pas vraiment ton cas :

Höd, je t'ai déja demander d'arreter de troll mes sujets par ce tu t'étais fais volé ton gouter par un économiste à la récré quand tu étais petite

et

PS : Toi tu fais tous pour que les économistes n'aiment pas les matheux non ? Enfin bon cela dit je doute qu'un vrai matheux ai ce genre d'attitude enfantine qui consiste à aller sur tous les sujets d'économie en sortant quelques trucs de maths pour montrer que ta discipline est la meilleure…

et

Sinon j'ai rarement vu plus pénible que toi dans le genre "je suis un mathématicien frustré trop mauvais pour réussir en maths alors je vais en économie où je peux étaler ma science et raconter n'importe quoi en prenant les gens de haut".

C'est clairement le genre de choses dont on peut se passer parce que ça peut vite faire partir un sujet en vrille.

Maintenant, et je ne le dirais qu'une seule fois, le prochain qui poste un message contenant des petites piques provocantes sur un autre intervenant de ce sujet (y compris déguisées sous un ton pseudo-humoristique/sarcastique) se verra offrir plusieurs jours de congé. J'apprécie moyennement devoir intervenir sur ce genre d'enfantillage. Vous êtes assez grands pour discuter calmement, en donnant des sources à vos propos.

Je suis désolé, mais j'en ai juste marre de voir Höd intervenir comme ça pour troll tous les sujets d'économie. Sur les autres articles/tutos il est bien moins prolifique et ne réclame pas tant d'explications.

C'est lui qui vient balancer sa vérité qui est en contradiction avec mes sources ou hors de propos sans donner la moindre justification.

• Le site du Nobel indique clairement les applications de ces travaux dans la répartition des étudiants et médecins et c'est quelque chose que je n'ai jamais vu contester nul part. Et Höd arrive avec ses gros sabots et sa "source sur" pour expliquer que ça n'a rien à voir… C'est assez énervant je trouve.

• Höd fait exprès de chercher la petite bête avec sa différence entre allocation stable et allocation optimale. Hors je ne parle jamais d'allocation stable mais tjrs d'allocation optimale (je parle de mariages stables), et surtout c'est strictement la même chose en économie. Et il le sait très bien vu que le crtère de Pareto est un des premiers trucs qu'on apprends. Pour que les deux soient différents il faudrait se placer dans un context de dictature bienveillante qui maximise une fonction d'utilité sociale ce qui revient à se placer dans un contexte utilitariste (de là encore Höd viendrait débattre des caractéristiques de la fonction d'utilité ou de sa convexité…). Donc soit il vient parler d'un truc qu'il ne connait pas comme si il avait la science infuse, soit il sait que ces critiques sont à coté de la plaque. Dans les deux ça m'énerve aussi de perdre du temps là dessus.

• Concernant APB leurs site indique eux même que c'est une procédure à la Gale-Shapley et même si il est clair que l'algorithme utilisé en pratique doit être différent et amélioré (pour tenir compte des places en universités qui sont limités mais non sélectives par exemple) mais mon article n'est pas une description ni une démonstration de l'algo de APB que je sache (algo que personne ne connait en détail il me semble…). Donc sa critique est vraiment hors de propos.

Je suis là encore désolé si je lui réponds sèchement mais j'en ai plus qu'assez de perdre du temps à chaque fois avec Höd qui fait tout le temps des remarques du même genre en invoquant des idées et notions mathématiques qui n'ont pas lieu d'être. Et ce sans donner la moindre source et en contredisant les miennes.

Pour être honnête si sa continue comme ça je ne proposerai plus d'articles d'économie ici, ça ne servira à rien et ça me fera juste perdre mon temps de discuter avec ce genre de troll (c'en est un pour moi désolé). Le but est de faire découvrir aux gens certains grands principes d'économie et de voir comment ils peuvent être mis en application dans la vie courante. Pas de savoir si le temps de calcul de l'algo de Gale-Shapley et polynomiale ou non et encore moins de le démontrer…

Comme je l'ai déja demandé, j'aimerai que Höd évite d'intervenir sur mes sujets quand ça parle d'économie. Il va juste m'énerver dans 99% des cas et je le dis clairement je ne tiendrait pas compte de ses remarques (sauf si il en fait une que je juge utile). Je l'invite à me faire ses remarques par mp et si je fais une modification qui en tient compte je le mentionnerais comme ça chacun saura qu'il en est à l'origine. Ainsi il pourra toujours contribuer de façon constructive sans que ça fasse dégénérer le topic car j'en ai vraiment marre de ses interventions. Tout le monde sera content.

Voici une explication assez détaillée de leurs travaux qui devrait convenir à Höd : http://www.nobelprize.org/nobel_prizes/economic-sciences/laureates/2012/advanced-economicsciences2012.pdf

J'hésite à l'ajouter aux notes en bas de page car c'est une ressource disponible sur la page du prix nobel 2012 que j'indique déja en source… Du coup je vais laisser la page principale en source, après aux gens qui veulent en savoir plus de cliquer sur les différents liens et pdf proposés selon leurs niveaux et les infos qu'ils recherchent.

Si vous avez des questions ou que vous voulez une source sur un point précis n'hésitez pas à demandez, même si je penses que ce que fournit le site du Nobel est vraiment complet et bien fait… (uniquement en anglais malheureusement).

Sinon je voulais illustrer différents mécanismes possible pour former des courses par un exemple que j'avais lu quelque part mais impossible d'en trouver une trace sur internet. L'idée était en gros que dans les campagnes un jour des célibataires était organisé. Les femmes devaient partir se cacher dans la montagne et les hommes devaient les retrouver. Il était interdit de rentrer seul au village (homme comme femme). C'est une anecdote sympa je trouve et le mécanisme n'est pas bête, il permet par exemple aux hommes les plus rapides et les plus ingénieux de trouver les meilleurs femmes, et aux femmes les plus malines de ne se faire découvrir que par les hommes les plus rusés. Si vous avez déjà entendu parler de cette histoire et avez une source à m'indiquer je suis preneur !

A part ça et sauf remarque particulière je ne penses pas particulièrement modifier l'article…

J'en ai entendu parler, sauf que le mécanisme est un peu différent. Les hommes devaient bien aller chercher les femmes cachées dans le village à la suite d'un bal, mais ils étaient obligés de se marier avec la première femme qu'ils trouvaient y compris dans le cas où ils soient tombés sur un laideron sans intelligence qui ne leur convenait pas. Et ceux qui étaient surpris en train de chercher une seconde chance plus heureuse ou qui refusaient la première femme à leur tomber sous la main se faisaient tabasser par les anciens du village.

En clair, ce mécanisme est juste une affectation au hasard pour des gens qui ne voulaient pas organiser une loterie. Sans compter que je doute qu'il soit évident que savoir se cacher ou trouver rapidement quelqu'un dans des fourrés est clairement signe qu'on est un bon mari ou une bonne épouse…

Ce serait possible d'en dire plus à ce sujet ? Là l'article nous laisse un peu sur notre faim.

@Mewtow : C'est exactement ça que je cherche comme exemple Après j'imagine que selon les versions les modalités de mise en couple doivent variées^^ Mais j'arrive pas à taper les bons mots clefs dans google pour trouver ça et une source…

@Looping : Je vais essayer de développer un peu là dessus !

C'est moi ou l'idée des reins croisé est mal formulé ? Je ferais un schéma personnellement

Très bonne article d'ailleurs si tu souhaites des dessins, contact moi

Le message qui suit n'a pas grand chose a voir avec l'article. C'est plus pour repondre a Demandered.

L'algorithme de Gale-Shapley n'est pas utilise par APB pour un tas de raisons. Citons principalement le fait que l'algorithme est manipulable par le genre qui se voit proposer. Ensuite, d'autres criteres independants (ministeriels notamment) interviennent qui font que la modelisation naturelle du probleme n'est pas celle d'un marriage stable. Derniere raison que je peux evoquer, le fait que les universites n'ont pas de preference a exprimer et que les profils de preferences ne sont pas complets (meme si il y aurait moyen de faire sans profil complet probablement).

• 1) Une allocation optimale au sens de Pareto est par définition stable donc c'est la même chose. De toute façon je parle de couples stable mais jamais d'allocation stable donc pourquoi tu fais cette remarque ?

Je serais curieux de savoir quelle difference tu fais entre allocation stable et couples stables.

• 2) l'académie Nobel indique elle même les contributions de Shapley et Roth et les applications dans les hôpitaux et l'affection des étudiants. Si tu n'es pas d'accord je te laisse leurs expliquer en quoi ils se trompent.

Les prix Nobels recompensent a posteriori des decouvertes interessantes ou fondatrices dans un certain nombre de domaines. Il s'est ecoule plus de 50 ans entre l'algorithme que tu decris et le Nobel qui recompense celui-ci (plus les travaux par la suite comme la preuve de cas d'inexistence en cas de choix reciproque). Autant dire une eternite pour la recherche en mathematiques. Entre temps les problemes se sont complexifies, les connaissances accrues de manieres exponentielles. Croire qu'en 2015 pour des situtations reelles et complexes, sous contraintes multiples, comme celui d'une affectation de medecins dans des hopitaux, ne fait apparaitre des problemes bien plus complexes qu'un simple marriage stable et donc qu'un algorithme de Gale-Shapley est suffisant, ce n'est pas tres raisonnable (mais dans un sens tu as raison, je suis trop optimiste de considerer que le monde reel n'a pas en general un retard de 40 a 50 ans sur l'etat de l'art). Les exemples sont tellement nombreux qu'il serait impossible d'en faire une liste.

3) APB indique sur son site que c'est du Gale-Shapeley. http://www.admission-postbac.info/fr/fr/mecanisme-apb.html

Non, il indique que c'est un mecanisme de Truth Telling, pas qu'il s'agit de Gale-Shapeley. Et comme je te l'ai dit, je sais que derriere ce n'est pas Gale-Shapeley principalement.

(au passage le fait que ce problème soit np complet ou pas n'as pas la moindre importance et si les mariages et les hopitaux c'est strictement la même chose.

Ce n'est la meme chose que si tu decides que c'est la meme chose. L'algorithme de Roth-Shapley resout le probleme de marriage stable, qui a une signification mathematique tres precise. Si la situation reelle que tu essayes de modeliser correspond entierement ou de maniere acceptable a ce probleme, alors effectivement, un algorithme efficace pour ce probleme mathematique est a adopter pour resoudre ton probleme reel.
Affecter des medecins dans des hopitaux peut certainement grossierement s'approximer par un marriage stable, mais on ne s'est pas contente de cela, et tant mieux. Que se passe-t-il si l'on doit tenir compte de contraintes spatiales, de departements de specialites au sein de tel ou tel hopital, de preferences complexes ou floues, ou simplement que le resultat ne soit pas manipulable par le profil de preference des hopitaux, etc. ? La reponse est que le probleme change, se complique a mesure qu'il se complexifie, et que les methodes de resolution changent egalement. Et si en pratique on peut integrer ces raffinements car on a la capacite de calcul ou de nouveaux algorithmes efficaces, alors on aurait tord de s'en priver… et on ne s'en prive pas.
Un exemple serait le probleme d'arbre couvrant de poids minimal. Ce probleme peut etre resolu polynomialement par un algorithme de Kruskal ou de Prim et modelise grossierement le cablage optimal pour un reseau. Dans les annees 50, on etait deja tres heureux de pouvoir resoudre cela, sur machine qui plus est. Sauf que dans la realite, les commutateurs reseaux ont un nombre limites de connectiques, et donc il faut limiter le degres des noeuds de l'arbre couvrant a un nombre fixe $k$. Rien que par cette toute petite modification l'algorithme de Kruskal ou Prim n'est plus applicable et le probleme devient NP-Complet. Ne parlons pas du cas non-homogene, et autre raffinement pour modeliser au mieux la realite.

Sauf qu'on est économie pas en maths, et en économie stabilité = optimalité par ce que c'est comme ça que fonctionne le critère de Pareto. Là si tu n'es pas d'accord j'avoue que je ne peux pas grand chose pour toi…

En economie comme ailleurs, la stabilite a le sens de n'importe quel dictionnaire (puis une definition precise selon le contexte et domaine): qui reste stable, dans son etat. La stabilite n'est pas lie au concept d'optimalite lui meme mais a une solution particuliere. Il peut arriver que les deux concordent, par le plus grand des hasards, mais rien ne le dit a priori.
Je pense que tu fais un melange semantique entre les deux du fait que n'ait pas une culture mathematique assez grande. Si tu ne manipules que des problemes ou tu definis l'optimalite comme des solutions stables, en un sens a definir, ca se comprends. Mais ce n'est pas un probleme de l'economie versus mathematiques. Un probleme economique tres simple pourrait consiste a affecter $n$ travailleurs a $n$ differents postes, sachant que chacun d'eux realise la tache du poste $i$ en un temps $t_i$. Il s'agit de minimiser le temps necessaire a la realisation des $n$ taches. A priori tu peux toujours qualifier le probleme de probleme economique, puisqu'il s'agit de gerer l'affectation de ressources. Pourtant la notion d'optimalite de ce probleme ne fait pas reference a une quelconque stabilite. Dans d'autres contextes encore, les solutions de Pareto ne sont pas atteignables sans conditions, voire non stable (il suffit de prendre un systeme dynamique en deux dimensions, sans contrainte, dont l'origine est repulsive), etc.

Si APB ne fonctionne pas comme ça je t'invite à sourcer ta "source sur" par ce que même leur site indique clairement que c'est un algorithme type Gale-Shapley.

Il n'est nul part ecrit que l'algorithme principal d'APB est un algorithme de Gale-Shapley. Et pour cause…

Le site du Nobel indique clairement les applications de ces travaux dans la répartition des étudiants et médecins et c'est quelque chose que je n'ai jamais vu contester nul part.

Personne ne conteste qu'ils ont travailles la dessus et ont eu un Nobel pour leurs travaux des annees 60. Saisis-tu la difference entre dire que les auteurs ont travailles sur la repartitions des etudiants et medecins (plus comme toy-model pour Shapley par ailleurs), et dire que ce cas particulier cite en exemple n'est pas pertinent parce que ce n'est pas ce qui est utilise ?

Höd fait exprès de chercher la petite bête avec sa différence entre allocation stable et allocation optimale.

C'est marrant de ne pas oublier de mettre de tremats a mon pseudo mais ne pas s'embeter a distinguer des termes fondamentalements differents. Si je cherchais la petite bete je dirais que tu le fais expres.

Pour être honnête si sa continue comme ça je ne proposerai plus d'articles d'économie ici, ça ne servira à rien et ça me fera juste perdre mon temps de discuter avec ce genre de troll (c'en est un pour moi désolé).

Dans un autre sujet, sur l'enseignement, quelqu'un avait propose comme regle de ne pas essayer d'enseigner quelque chose avant d'avoir 5 a 10 ans de recul et d'experience sur le domaine. Tu pourrais commencer a l'appliquer, cela nous epargnerait au moins ta mauvaise humeur et susceptibilite mal placee.

Et le pire dans tout cela, c'est que tout cela part d'un constat sur la pertinence des deux exemples que tu cites. Ce qui fait tiquer c'est que l'algorithme utilise par National Resident Matching Program est fondamentalement different de celui que tu presentes plus haut puisque le probleme pose est fondamentalement different (NP-Complet, cas d'inexistence de solution optimale, etc). Preciser que ce que ce qui a ete fait en 95 est bien plus evolue – 50 ans se sont ecoules – me semble bienvenue. Idem pour APB ou c'est encore pire ! Par contre, l'algorithme utilise pour la premiere annee de medecine qui effectivement utilise une version un peu modifiee de Roth-Shapley. Cela ferait un exemple parfait, car bien sourcee dans la presse francaise notamment.

Sinon, a la base j'avais rien a dire d'autre que cela, mais quitte a ecrire un pave:

Au lieu de s'énerver comme certains de ses collègues sur le fait que les gens sont trop conservateurs,

Je ne crois pas que fait de refuser d'autoriser la vente d'organes soit un acte conservateur en soit. C'est tres mal formule.

Je penses que on n'est pas sur la même longueur d'onde : mon article vise à présenter les travaux des deux Nobels de 2012, Gale et Roth, et de montrer en quoi leurs travaux sont utiles aux quotidiens et comment ils ont pu être utilisés.

Je n'ai jamais dis que en pratique on utilisait réellement cette version là de l'algorithme. Il est évident que pour quelque chose comme post bac les différentes contraintes obligent à modifier l'algorithme. Idem pour les hôpitaux.

Je pense que tu fais un melange semantique entre les deux du fait que n'ait pas une culture mathematique assez grande. Si tu ne manipules que des problemes ou tu definis l'optimalite comme des solutions stables, en un sens a definir, ca se comprends.

Je fais la différence entre les deux ne t'en fais pas

Le truc que tu sembles oublier c'est qu'on parle de market design, c'est à dire d'imaginer une façon d'organiser le marché qui conduise à une allocation des ressources optimale (au sens de Pareto). Donc la stabilité est identique à l'optimalité.

Je penses que du fais de ta formation mathématique tu ne vois que la subtilité qui fait toute la différence : il n'existe pas de fonction à optimiser pour résoudre ces problèmes mathématiquement. Pour que cela soit possible il faudrait avoir une fonction d’agrégation sociale ce qui est un prérequis douteux (sauf en URSS). Si tu ignore totalement le poids des arrêtes du graphe tu peux utiliser les meilleurs algos du monde, tu n'iras pas bien loin…

Prenons le cas des médecins et des hôpitaux : on peut supposer raisonnablement qu'il existe un ensemble de solutions stables. La question de l'optimalité revient à se demander "quelle solution parmi celle-ci est la meilleure ?". Hors quels critères peut-tu utiliser pour juger si une situation A est meilleure qu'une situation B ? Je dirai qu'il n'en existe pas. Donc exit les fonctions d'optimisation car il n'y à rien à optimiser. La seule chose que l'on peut faire c'est regarder en faveur de quels groupes le résultat penche. Par exemple dans un algorithme de Gale-Shaplay le résultat est en faveur des femmes (quand les hommes proposent). C'est pour ça que dans APB le mécanisme est fait de façon à favoriser les universités (qui ont les meilleurs étudiants) et non les étudiants. Mais ça c'est une question de choix social et c'est aux personnes qui se penchent sur le problème de savoir si oui ou non ils veulent avantager telle ou telle partie…

C'est pas pour rien qu'on parle de market design et non simplement d'optimisation, car c'est deux choses différentes et j'ai l'impression que tu ne fais pas la différence.

Si je cherchais la petite bete je dirais que tu le fais expres.

Je suis mauvais en orthographe mais j'essaye quand même ne pas écorcher les noms ou pseudo des gens, c'est tout. Et je ne fais pas différence dans le cas présent car comme j'essaie de t'expliquer c'est exactement la même chose… Mais je fais très bien cette différence, ne t'en fais pas^^

. Un probleme economique tres simple pourrait consiste a affecter n travailleurs a n differents postes, sachant que chacun d'eux realise la tache du poste i en un temps ti. Il s'agit de minimiser le temps necessaire a la realisation des n taches.

Là c'est un problème d'optimisation, pas de market design. Là oui tu peux utiliser tous tes algos et ce genre de cas n'intéresse pas vraiment les économistes^^ Cet exemple m'invite vraiment à penser que tu mélanges le problème du market design avec un problème d'optimisation, ce qui est assez différent…

dire que ce cas particulier cite en exemple n'est pas pertinent parce que ce n'est pas ce qui est utilise ?

J'ai dis que Roth avait travaillé en 95 pour améliorer le système américain. je n'ai jamais dis qu'il avait utilisé un algo de Gale-Shapley si ? Ne me reproche pas ce que je n'ai pas dis

Je ne crois pas que fait de refuser d'autoriser la vente d'organes soit un acte conservateur en soit.

Pour un économiste c'est considéré comme tel ! Je penses qu'on comprends ce que je veux dire, tu trouves que la formulation pourrait introduire un biais du genre "Il est normal de considérer le refus de la vente d'organe conserveur" ? Je dis bien que ce sont les économistes qui pensent ça et ce n'est pas très très loin de la réalité…

Très bon article !

Un titre qui donne envie de cliquer/lire. Une introduction intéressante et rigolote, des exemples concrètes et d'actualité.

Donc merci, et continu !