Comment épouser tout le monde (mariage à un, deux et trois sexes) du point de vue des mathématiques et pourquoi les hommes gagnent toujours

En 2012, le prix Nobel d'économie a été décerné à Lloyd Shapley et Alvin Roth. "Pour la théorie de la distribution stable et des pratiques du marché." Alexey Savvateev en 2012 a essayé d'expliquer simplement et clairement quelle est l'essence des mérites des mathématiciens. J'attire votre attention sur les notes de cours vidéo .


Aujourd'hui sera une conférence théorique. Concernant les expériences d' Al Roth , notamment avec le don, je ne parlerai pas.

Quand il a été annoncé que Lloyd Shapley (1923-2016) a reçu le prix Nobel, il y avait une question standard: «Comment!? Est-il toujours en vie!?!? " Son résultat le plus célèbre a été obtenu en 1953.

Officiellement, le prix a été remis pour un autre. Pour les travaux de 1962 pour le «théorème sur le mariage durable»: «Admission au Collège et stabilité du mariage».

À propos du mariage durable

La correspondance est la tâche de trouver une correspondance.

Il y a un certain village isolé. Il y a «m» des jeunes et «w» des filles. Il faut les marier entre eux. (Pas nécessairement le même montant, peut-être qu'à la fin, quelqu'un sera laissé seul.)

Quelles conditions préalables devez-vous remplir dans le modèle? Ce qui n'est pas seulement aléatoire. Un pas est franchi vers le libre choix. Supposons qu'il y ait un sage aksakal qui veuille se marier pour qu'après sa mort, les divorces ne commencent pas. (Le divorce est une situation où un mari veut qu'une femme tierce se marie plus qu'une femme.)

Ce théorème est dans l'esprit de l'économie moderne. Elle est extrêmement inhumaine. L'économie est traditionnellement inhumaine. En économie, une personne est remplacée par une voiture pour maximiser ses profits. Ce que je vais dire, c'est des choses complètement folles en termes de moralité. Ne prenez pas à cœur.

Les économistes voient le mariage comme ça.
m ₁ , m ₂ , ... m _k sont des hommes.
w ₁ , w ₂ , ... w _L - femmes.

Un homme est identifié avec la façon dont il «ordonne» aux filles. Il existe également un «niveau zéro», en dessous duquel aucune femme ne devrait se voir proposer de se marier, même s'il n'y en a pas d'autres.



Tout se passe dans les deux sens, les filles ont la même chose.

Les données initiales sont arbitraires. La seule suggestion / limitation est que nous ne modifions pas nos préférences.

Théorème: Indépendamment de la distribution et du niveau de zéro, il existe toujours un moyen d'établir une correspondance biunivoque entre une partie des hommes et une partie des femmes, afin qu'elle soit stable par rapport à tout type de scissions (pas seulement les divorces).

Quelles menaces peuvent être?

Il y a un couple (m, w) qui n'est pas marié. Mais pour w, le mari actuel est pire que m, et pour m, la femme actuelle est pire que w. Il s'agit d'une situation instable.

Il y a une autre option, que quelqu'un a épousé quelqu'un qui est «en dessous de zéro», dans cette situation, le mariage sera également rompu.

Si une femme est mariée, mais qu'elle préfère une femme non mariée, pour laquelle elle est au-dessus de zéro.

Si deux personnes, toutes deux célibataires, et les deux sont «au-dessus de zéro» l'une pour l'autre.

On fait valoir que pour toutes les données initiales, un tel système de mariage existe et résiste à tous les types de menaces. Deuxièmement, l'algorithme pour trouver un tel équilibre est très simple. À la mesure de M * N.

Ce modèle a été généralisé et étendu à la «polygamie» et appliqué dans de nombreux domaines.

Procédure Gale-Shapley

Si tous les hommes et toutes les femmes respectent les «préceptes», le système de mariage qui en résulte sera stable.

Prescriptions.
Nous prenons quelques jours au besoin. Chaque jour, nous nous divisons en deux parties (matin et soir).

Le premier matin, chaque homme va voir sa meilleure femme et frappe à la fenêtre, l'invitant à l'épouser.

Le soir du même jour, le déménagement revient aux femmes: que peut découvrir une femme? Que sous la fenêtre, elle a une foule, un ou pas un seul homme. Ceux qui n'avaient personne aujourd'hui manquent le cours, attendez. Les autres, qui en ont au moins un, vérifient que les hommes venus sont "au-dessus de zéro". En avoir au moins un. Si vous n'avez pas de chance et que tout est inférieur à zéro, alors tout le monde doit être envoyé. La femme choisit le maximum de ceux qui viennent, lui dit d'attendre et envoie le reste.

Avant le deuxième jour, la situation est la suivante: certaines femmes ont un homme, d'autres n'en ont pas.

Le deuxième jour, tous les hommes «libres» (envoyés) doivent se rendre chez la femme de deuxième priorité. S'il n'y en a pas, alors l'homme est déclaré célibataire. Les hommes qui sont déjà assis avec des femmes ne font encore rien.

Le soir, les femmes regardent la situation. Si celui qui était déjà assis a rejoint la priorité la plus élevée, alors la priorité la plus basse est renvoyée. Si le nombre de visiteurs est inférieur à celui existant, tous sont envoyés. Les femmes choisissent à chaque fois l'élément maximum.

Nous répétons.

En conséquence, chaque homme a parcouru la liste complète de ses femmes et est resté seul ou a été biaisé par une femme. Ensuite, nous épouserons tout le monde.

Est-il possible de chasser tout ce processus, mais pour que les femmes courent aux hommes? La procédure est symétrique, mais la solution peut être différente. Mais la question est de savoir qui s'en tire le mieux?

Théorème Considérez non seulement ces deux solutions symétriques, mais l'ensemble de tous les systèmes de mariage stables. Le mécanisme proposé initialement (les hommes courent et les femmes sont d'accord / refusent) conduit à un système de mariage qui est meilleur pour n'importe quel homme que n'importe quel autre et pire que tout autre pour n'importe quelle femme.

Mariages de même sexe

Considérez la situation du mariage homosexuel. Considérons un résultat mathématique qui jette le doute sur la nécessité de les légaliser. Un exemple idéologiquement incorrect.

Considérez les quatre homosexuels a, b, c, d.

priorités pour a: bcd
priorités pour b: cad
priorités pour c: abd
pour d, peu importe comment il classe les trois autres.

Déclaration: il n'y a pas de système de mariage durable dans ce système.

Combien de systèmes existe-t-il pour quatre personnes? Trois. ab cd, ac bd, ad bc. Les paires se désagrègent et le processus se boucle.

Systèmes "à trois sexes".
C'est une question cruciale qui ouvre tout un champ de mathématiques. Cela a été fait par mon collègue de Moscou, Vladimir Ivanovitch Danilov. «Mariage», il voyait boire de la vodka et les rôles étaient: «verser», «parler de pain grillé» et «celui qui coupe la saucisse». Dans une situation où il y a 4 représentants ou plus de chaque rôle, il est impossible de résoudre par la force brute. La question d'un système durable est ouverte.

Vecteur de Shapley

Dans le village de chalets, ils ont décidé de paver la route. Besoin de participer. Comment?

Shapley en 1953 a proposé une solution à ce problème. Supposons une situation de conflit avec un groupe de personnes N = {1,2 ... n}. Besoin de partager les coûts / avantages. Supposons que les gens aient fait quelque chose d'utile ensemble, vont-ils vendre et comment partager les bénéfices?

Shapley a suggéré de partager une fois guidé par combien un ou un autre sous-ensemble de ces personnes pourrait obtenir. Combien d'argent les 2 ^N sous-ensembles non vides pourraient gagner. Et sur la base de ces informations, Shapley a écrit une formule universelle.

Un exemple. Soliste, guitariste et batteur jouent dans le passage souterrain à Moscou. Les trois gagnent 1000 roubles par heure. Comment le partager? Vous pouvez également.
V (1,2,3) = 1000

Supposons que
V (1,2) = 600
V (1,3) = 450
V (2,3) = 400
V (1) = 300
V (2) = 200
V (3) = 100

Il est impossible de déterminer un juste partage tant que nous ne savons pas quel type de gains attend telle ou telle entreprise si elle se déconnecte et agit de manière indépendante. Et quand nous avons déterminé les nombres (nous avons demandé un jeu coopératif sous une forme caractéristique).

La superradditivité, c'est quand ensemble ils gagnent plus qu'individuellement, quand il est plus rentable de s'unir, mais il n'est pas clair comment diviser le gain. De nombreuses copies ont été cassées à ce sujet.

Il y a un jeu. Trois hommes d'affaires ont trouvé simultanément un dépôt de 1 million de dollars. Si les trois sont d'accord, alors un million d'entre eux. N'importe quel couple peut dunk (retirer de l'entreprise) et obtenir le million entier. Et personne seul ne peut rien faire. Il s'agit d'un jeu coopératif effrayant dans lequel il n'y a pas de solution. Il y en aura toujours deux qui pourront éliminer le troisième ... La théorie du jeu coopératif commence par un exemple qui n'a pas de solution.

Mais nous voulons une telle solution qu'aucune coalition ne veuille bloquer une solution commune. L'ensemble de tous les partages qui ne peuvent pas être bloqués est le noyau. Il arrive que le noyau soit vide. Mais même s'il n'est pas vide, comment partager?

Shapley suggère de partager comme ça. Jetez une pièce avec n! facettes. Dans cet ordre, nous écrivons tous les joueurs. Disons le premier batteur. Il entre et prend ses 100. Vient ensuite le «deuxième», disons, un soliste. (Avec le batteur, ils peuvent gagner 450, le batteur en a déjà pris 100) Le soliste en prend 350. Le guitariste entre (ensemble 1000, -450), en prend 550. La dernière personne qui arrive assez souvent gagne. (Supermodularité)

Si nous écrivons pour toutes les commandes:
GSB - (victoire C) - (victoire G) - (victoire B)
GBS - (victoire C) - (victoire G) - (victoire B)
SBG - (victoire C) - (victoire G) - (victoire B)
BSG - (victoire C) - (victoire G) - (victoire B)
BGS - (victoire C) - (victoire G) - (victoire B)
GBS - (victoire C) - (victoire G) - (victoire B)

Et pour chaque colonne, nous ajoutons et divisons par 6 - la moyenne sur toutes les commandes est un vecteur de Shapley .

Shapley a prouvé le théorème (approximativement): Il y a une classe de jeux (supermodulaire) dans laquelle la prochaine personne à rejoindre la grande équipe - il a apporté une plus grande victoire. Le noyau n'est pas toujours vide et est une combinaison convexe de points (dans notre cas, 6 points). Le vecteur Shapley se situe au centre même du noyau. Cela peut toujours être proposé comme une solution, personne ne s'en souciera.

En 1973, il a été prouvé que le problème des chalets est supermodulaire.

La route vers le premier chalet est partagée par tous les n personnes. Jusqu'à la seconde - n-1 personnes. Et ainsi de suite.

L'aéroport a une piste. Différentes entreprises ont besoin de longueurs différentes. Le même problème se pose.

Je pense que ceux qui ont décerné le prix Nobel avaient à l'esprit ce mérite, et pas seulement la tâche du mariage.

Je vous remercie!