Dénombrement sur des ordres de préférences
Bonjour,
On considère 2 hommes m1, m2 et 2 femmes f1, f2 et chacune de ces 4 personnes a un ordre de préférence aléatoire pour le sexe opposé, par exemple:
- m1 préfère f1 à f2
- m2 préfère f1 à f2
- f1 préfère m1 à m2
- f2 préfère m2 à m1
On cherche à marier chaque femme à un homme en respectant les préférences des femmes en priorité (c'est l'algorithme de Gale-Shapley), et on souhaite calculer l'espérance du nombre de personnes satisfaites.
La réponse est 2,75 (en traitant les 16 cas à la main), mais je n'arrive pas à le faire sous forme de dénombrements, pourriez-vous m'aider svp?
Merci.
On considère 2 hommes m1, m2 et 2 femmes f1, f2 et chacune de ces 4 personnes a un ordre de préférence aléatoire pour le sexe opposé, par exemple:
- m1 préfère f1 à f2
- m2 préfère f1 à f2
- f1 préfère m1 à m2
- f2 préfère m2 à m1
On cherche à marier chaque femme à un homme en respectant les préférences des femmes en priorité (c'est l'algorithme de Gale-Shapley), et on souhaite calculer l'espérance du nombre de personnes satisfaites.
La réponse est 2,75 (en traitant les 16 cas à la main), mais je n'arrive pas à le faire sous forme de dénombrements, pourriez-vous m'aider svp?
Merci.
Réponses
-
Je fais un peu de programmation pour voir ce qui se passe quand il y a plus de célibataires (pour peut-être donner une intuition sur la réponse à chercher). Pour être bien sûr : vous entendez par "satisfaite" une personne (homme ou femme) qui se retrouve, à la fin du processus, en couple avec son premier choix ?
Je vous dis dès que j'en sais plus. -
Dans un premier temps oui, on considère qu'une personne est satisfaite exclusivement si elle a son premier choix. Merci d'avance.
Je précise d'ailleurs que j'ai finalement réussi le cas avec 2 hommes et 2 femmes, mais le cas n = 3 semble bien plus complexe. -
Pour expérimenter un petit peu (mon code mériterait des commentaires, et il n'est sûrement pas très efficace, je me suis basé sur le pseudo-code proposé par wikipédia) : le programme Python suivant simule $k$ fois l'expérience, avec $n$ hommes et $n$ femmes. On se fixe un critère "maxi" qui est l'indice correspondant au nombre de personnes avec lesquelles chaque individu se dirait "satisfait" ($1$ correspond à n'être satisfait qu'avec son premier choix). Le programme renvoie la moyenne du nombre de personnes satisfaites sur ces expériences (On retrouve bien votre résultat pour $n=2$ et maxi$=1$).
https://github.com/Wkolakoski/mariages_stables/blob/main/prog
(il semblerait qu'il y ait un problème avec la mise en page de mon code, je le mets, pour l'instant, sur GitHub) -
Merci pour le programme que vous avez rédigé. Malheureusement, je crois qu'il y a une erreur lors de copier-coller car le code ne s'exécute pas. Pourriez-vous revérifier svp?
-
Effectivement, j'ai remplacé par un lien vers GitHub...
-
Merci beaucoup, je vais essayer d'analyser les résultats.
-
J'ai regardé un peu ce qu'il se passait pour maxi$\in\{1,2,3\}$. J'ai fait $k=5000$ fois l'expérience, pour $n\in \{2,...,29\}$. J'ai tracé les courbes (des fractions des $2n$ personnes qui se disent satisfaites, en fonction de $n$, une courbe par paramètre "maxi"). En bleu, maxi$=1$, en rouge maxi$=2$ et en noir maxi$=3$.
-
Merci beaucoup pour ces simulations, il semblerait que cette fraction admet une loi stationnaire. Je vais me pencher sur cela.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 69 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres