Dénombrement sur des ordres de préférences

Climont · October 2021

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.

Kolakoski · October 2021

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.

Climont · October 2021

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.

Kolakoski · October 2021

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)

Climont · October 2021

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?

Kolakoski · October 2021

Effectivement, j'ai remplacé par un lien vers GitHub...

Climont · October 2021

Merci beaucoup, je vais essayer d'analyser les résultats.

Kolakoski · October 2021

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$. 128362