Wie man jeden heiratet (ein-, zwei- und dreigeschlechtliche Ehe) aus mathematischer Sicht und warum Männer immer gewinnen

2012 wurde Lloyd Shapley und Alvin Roth mit dem Nobelpreis für Wirtschaftswissenschaften ausgezeichnet. "Für die Theorie der stabilen Distribution und Marktpraxis." Alexey Savvateev versuchte 2012 einfach und klar zu erklären, was die Verdienste der Mathematiker ausmachen. Ich mache Sie auf die Video-Vorlesungsunterlagen aufmerksam .


Heute wird eine theoretische Vorlesung sein. Über die Experimente von Al Roth , insbesondere mit Spenden, werde ich nicht sprechen.

Als bekannt wurde, dass Lloyd Shapley (1923-2016) den Nobelpreis erhalten hat, gab es eine Standardfrage: „Wie !? Lebt er noch!?!? " Sein berühmtestes Ergebnis wurde 1953 erzielt.

Formal wurde der Preis für einen anderen vergeben. Für die Arbeit von 1962 zum „Theorem zur nachhaltigen Ehe“: „Hochschulzulassung und Stabilität der Ehe“.

Über nachhaltige Ehe

Matching ist die Aufgabe, ein Match zu finden.

Es gibt ein bestimmtes abgelegenes Dorf. Es gibt "m" junge Leute und "w" Mädchen. Es ist notwendig, sie miteinander zu heiraten. (Nicht unbedingt die gleiche Menge, vielleicht wird am Ende jemand allein gelassen.)

Welche Voraussetzungen müssen Sie im Modell erfüllen? Welches ist nicht nur randomisieren. Es wird ein Schritt in Richtung freie Wahl unternommen. Angenommen, es gibt einen weisen Aksakal, der heiraten möchte, damit nach seinem Tod keine Scheidungen beginnen. (Eine Scheidung ist eine Situation, in der ein Ehemann möchte, dass eine Frau eines Dritten mehr als eine Frau heiratet.)

Dieser Satz ist im Geiste der modernen Wirtschaft. Sie ist extrem unmenschlich. Die Wirtschaft ist traditionell unmenschlich. In der Wirtschaft wird eine Person durch ein Auto ersetzt, um den Gewinn zu maximieren. Was ich erzählen werde, sind völlig verrückte Dinge in Bezug auf die Moral. Nimm dir nicht zu Herzen.

Ökonomen sehen die Ehe so.
m ₁ , m ₂ , ... m _k sind Männer.
w ₁ , w ₂ , ... w _L - Frauen.

Ein Mann wird damit identifiziert, wie er die Mädchen „befiehlt“. Es gibt auch eine „Nullstufe“, unterhalb derer Frauen überhaupt nicht angeboten werden sollten, zu heiraten, selbst wenn es keine anderen gibt.



Alles passiert in beide Richtungen, die Mädchen haben das Gleiche.

Die Anfangsdaten sind beliebig. Der einzige Vorschlag / die einzige Einschränkung ist, dass wir unsere Präferenzen nicht ändern.

Satz: Unabhängig von der Verteilung und dem Niveau von Null gibt es immer eine Möglichkeit, eine Eins-zu-Eins-Entsprechung zwischen einem Teil von Männern und einem Teil von Frauen herzustellen, so dass sie in Bezug auf jede Art von Spaltungen (nicht nur Scheidungen) stabil ist.

Welche Bedrohungen können sein?

Es gibt ein Paar (m, w), das nicht verheiratet ist. Aber für w ist der aktuelle Ehemann schlechter als m, und für m ist die aktuelle Frau schlechter als w. Dies ist eine instabile Situation.

Es gibt eine andere Möglichkeit, dass jemand jemanden geheiratet hat, der „unter Null“ ist. In dieser Situation wird auch die Ehe aufgelöst.

Wenn eine Frau verheiratet ist, aber eine unverheiratete Frau bevorzugt, für die sie über Null steht.

Wenn zwei Personen, beide unverheiratet, und beide für einander „über Null“ sind.

Es wird argumentiert, dass für alle anfänglichen Daten ein solches Ehe-System existiert, das gegen alle Arten von Bedrohungen resistent ist. Zweitens ist der Algorithmus zum Finden eines solchen Gleichgewichts sehr einfach. Entspricht M * N.

Dieses Modell wurde verallgemeinert und auf „Polygamie“ erweitert und in vielen Bereichen angewendet.

Gale-Shapley-Verfahren

Wenn alle Männer und alle Frauen die „Vorschriften“ einhalten, ist das daraus resultierende Ehe-System stabil.

Rezepte.
Wir nehmen uns nach Bedarf ein paar Tage Zeit. Jeden Tag teilen wir uns in zwei Teile (morgens und abends).

Am ersten Morgen geht jeder Mann zu seiner besten Frau, klopft an das Fenster und lädt sie ein, ihn zu heiraten.

Am Abend desselben Tages geht der Umzug an Frauen. Was kann eine Frau entdecken? Dass sie unter dem Fenster eine Menschenmenge hat, entweder einen oder keinen einzigen Mann. Diejenigen, die heute niemanden hatten, verpassen den Kurs, warten. Der Rest, der mindestens einen hat, überprüft die Männer, die gekommen sind, dass sie "über Null" sind. Mindestens einen haben. Wenn Sie völlig unglücklich sind und alles unter Null liegt, müssen alle gesendet werden. Die Frau wählt das Maximum derer, die kommen, sagt ihm, er solle warten und schickt den Rest.

Vor dem zweiten Tag ist die Situation wie folgt: Einige Frauen haben einen Mann, andere keinen.

Am zweiten Tag müssen alle „freien“ (gesendeten) Männer zur Frau mit der zweiten Priorität gehen. Wenn es keine gibt, wird der Mann für ledig erklärt. Die Männer, die bereits mit Frauen zusammensitzen, tun noch nichts.

Abends schauen sich Frauen die Situation an. Wenn derjenige, der bereits saß, der höheren Priorität beigetreten ist, wird die niedrigere Priorität weggeschickt. Wenn die Besucher niedriger als die vorhandenen sind, werden alle gesendet. Frauen wählen jedes Mal das maximale Element.

Wir wiederholen.

Infolgedessen ging jeder Mann die gesamte Liste seiner Frauen durch und blieb entweder allein oder wurde von einer Frau voreingenommen. Dann werden wir alle heiraten.

Ist es möglich, diesen ganzen Prozess zu vertreiben, aber damit Frauen zu Männern laufen? Das Verfahren ist symmetrisch, aber die Lösung kann unterschiedlich sein. Aber die Frage ist, wer ist besser dran?

Satz Betrachten Sie nicht nur diese beiden symmetrischen Lösungen, sondern auch die Menge aller stabilen Ehe-Systeme. Der ursprünglich vorgeschlagene Mechanismus (Männer laufen und Frauen stimmen zu / lehnen ab) führt zu einem Ehe-System, das für jeden Mann besser ist als jeder andere und für jede Frau schlechter als jeder andere.

Gleichgeschlechtliche Ehen

Betrachten Sie die Situation mit der gleichgeschlechtlichen Ehe. Betrachten Sie ein mathematisches Ergebnis, das Zweifel an der Notwendigkeit aufwirft, sie zu legalisieren. Ein ideologisch falsches Beispiel.

Betrachten Sie die vier Homosexuellen a, b, c, d.

Prioritäten für a: bcd
Prioritäten für b: cad
Prioritäten für c: abd
Für d spielt es keine Rolle, wie die verbleibenden drei eingestuft werden.

Aussage: In diesem System gibt es kein nachhaltiges Ehe-System.

Wie viele Systeme gibt es für vier Personen? Drei. ab cd, ac bd, ad bc. Die Paare fallen auseinander und der Prozess wird wiederholt.

"Drei-geschlechtliche" Systeme.
Dies ist eine entscheidende Frage, die ein ganzes Feld der Mathematik eröffnet. Dies wurde von meinem Kollegen in Moskau, Wladimir Iwanowitsch Danilow, getan. "Ehe" sah er als trinkenden Wodka an und die Rollen waren: "Eingießen", "Toast reden" und "derjenige, der die Wurst schneidet". In einer Situation, in der es 4 oder mehr Vertreter jeder Rolle gibt, ist es unmöglich, mit roher Gewalt zu lösen. Die Frage eines nachhaltigen Systems ist offen.

Shapley Vektor

Im Bauerndorf beschlossen sie, die Straße zu ebnen. Müssen einsteigen. Wie?

Shapley schlug 1953 eine Lösung für dieses Problem vor. Angenommen, eine Konfliktsituation mit einer Personengruppe N = {1,2 ... n}. Müssen die Kosten / Nutzen teilen. Angenommen, die Leute haben gemeinsam etwas Nützliches getan, werden sie verkaufen und wie können sie den Gewinn teilen?

Shapley schlug vor, zu teilen, wenn man sich davon leiten lässt, wie viel die eine oder andere Untergruppe dieser Leute bekommen könnte. Wie viel Geld könnten alle 2 ^N nicht leeren Teilmengen verdienen? Und basierend auf diesen Informationen schrieb Shapley eine universelle Formel.

Ein Beispiel. Solist, Gitarrist und Schlagzeuger spielen in der Unterführung in Moskau. Die drei verdienen 1000 Rubel pro Stunde. Wie teile ich es? Sie können gleichermaßen.
V (1,2,3) = 1000

Nehmen Sie das an
V (1,2) = 600
V (1,3) = 450
V (2,3) = 400
V (1) = 300
V (2) = 200
V (3) = 100

Es ist unmöglich, eine faire Kluft zu bestimmen, bis wir wissen, welche Art von Gewinnen auf dieses oder jenes Unternehmen warten, wenn es sich trennt und unabhängig handelt. Und als wir die Zahlen bestimmten (wir fragten ein kooperatives Spiel in einer charakteristischen Form).

Superradditivität ist, wenn sie zusammen mehr verdienen als einzeln, wenn es rentabler ist, sich zu vereinen, aber es nicht klar ist, wie der Gewinn aufgeteilt werden soll. Viele Kopien wurden darüber gebrochen.

Es gibt ein Spiel. Drei Geschäftsleute fanden gleichzeitig eine Kaution in Höhe von 1 Million US-Dollar. Wenn die drei übereinstimmen, dann eine Million von ihnen. Jedes Paar kann eintauchen (aus dem Geschäft entfernen) und die ganze Million bekommen. Und niemand allein kann etwas tun. Dies ist ein gruseliges kooperatives Spiel, in dem es keine Lösung gibt. Es wird immer zwei geben, die den dritten eliminieren können ... Die kooperative Spieltheorie beginnt mit einem Beispiel, das keine Lösung hat.

Aber wir wollen eine solche Lösung, dass keine Koalition eine gemeinsame Lösung blockieren will. Die Menge aller Freigaben, die nicht blockiert werden können, ist der Kern. Es kommt vor, dass der Kern leer ist. Aber auch wenn es nicht leer ist, wie kann man es teilen?

Shapley schlägt vor, so zu teilen. Wirf eine Münze mit n! Facetten. In dieser Reihenfolge schreiben wir alle Spieler aus. Sagen wir der erste Schlagzeuger. Er tritt ein und nimmt seine 100. Dann kommt der "zweite", sagen wir ein Solist. (Zusammen mit dem Schlagzeuger können sie 450 verdienen, der Schlagzeuger hat bereits 100 genommen.) Der Solist nimmt 350. Der Gitarrist tritt ein (zusammen 1000, -450), nimmt 550. Die letzte Person, die hereinkommt, gewinnt ziemlich oft. (Supermodularität)

Wenn wir für alle Bestellungen schreiben:
GSB - (Sieg C) - (Sieg G) - (Sieg B)
GBS - (Sieg C) - (Sieg G) - (Sieg B)
SBG - (Sieg C) - (Sieg G) - (Sieg B)
BSG - (Sieg C) - (Sieg G) - (Sieg B)
BGS - (Sieg C) - (Sieg G) - (Sieg B)
GBS - (Sieg C) - (Sieg G) - (Sieg B)

Und für jede Spalte addieren und dividieren wir durch 6 - die Mittelung über alle Ordnungen ist ein Shapley-Vektor .

Shapley hat den Satz (ungefähr) bewiesen: Es gibt eine Klasse von Spielen (supermodular), in denen die nächste Person, die sich dem großen Team anschließt, einen größeren Sieg einbrachte. Der Kernel ist immer nicht leer und ist eine konvexe Kombination von Punkten (in unserem Fall 6 Punkte). Der Shapley-Vektor liegt genau in der Mitte des Kerns. Es kann immer als Lösung angeboten werden, niemand wird etwas dagegen haben.

1973 wurde nachgewiesen, dass das Problem mit Hütten supermodular ist.

Die Straße zum ersten Häuschen wird von allen n Personen geteilt. Bis zum zweiten - n-1 Personen. Usw.

Der Flughafen hat eine Landebahn. Unterschiedliche Unternehmen benötigen unterschiedliche Längen. Das gleiche Problem tritt auf.

Ich denke, dass diejenigen, die den Nobelpreis verliehen haben, dieses Verdienst im Auge hatten und nicht nur die Aufgabe der Ehe.

Vielen Dank!