In 2012 werd de Nobelprijs voor de Economie toegekend aan Lloyd Shapley en Alvin Roth. "Voor de theorie van stabiele distributie en de praktijk van het organiseren van markten." Aleksey Savvateev probeerde in 2012 de essentie van de verdiensten van wiskundigen eenvoudig en duidelijk uit te leggen. Ik presenteer een samenvatting onder uw aandacht .
Vandaag is er een theoretische lezing. Over experimenten , vooral met donatie, zal ik het niet vertellen.
Toen dat bekend werd gemaakt de Nobelprijs ontving, was er een standaardvraag: “Hoe!? Leeft hij nog!?!?" Zijn bekendste resultaat behaalde hij in 1953.
Formeel werd de bonus voor iets anders gegeven. Voor zijn artikel uit 1962 over de ‘huwelijksstabiliteitsstelling’: ‘College Admission and the Stability of Marriage.’
Over duurzaam trouwen
Bijpassende (matching) - de taak om een correspondentie te vinden.
Er is een bepaald geïsoleerd dorp. Er zijn ‘m’ jonge mannen en ‘w’ meisjes. We moeten ze met elkaar uithuwelijken. (Niet noodzakelijkerwijs hetzelfde aantal, misschien wordt er uiteindelijk iemand met rust gelaten.)
Welke aannames moeten in het model worden gedaan? Dat het niet gemakkelijk is om willekeurig te hertrouwen. Er wordt een zekere stap gezet in de richting van vrije keuze. Laten we zeggen dat er een wijze Aksakal is die wil hertrouwen, zodat er na zijn dood geen echtscheidingen beginnen. (Echtscheiding is een situatie waarin een man meer een vrouw van een derde partij als zijn vrouw wil dan zijn vrouw.)
Deze stelling is in de geest van de moderne economie. Ze is uitzonderlijk onmenselijk. De economie is van oudsher inhumaan. In de economie wordt de mens vervangen door een machine om de winst te maximaliseren. Wat ik je ga vertellen zijn absoluut gekke dingen vanuit moreel oogpunt. Neem het niet ter harte.
Economen kijken op deze manier naar het huwelijk.
m1, m2,… mk - mannen.
w1, w2,... wL - vrouwen.
Een man wordt geïdentificeerd met de manier waarop hij meisjes ‘beveelt’. Er is ook een ‘nulniveau’, waaronder vrouwen helemaal niet als echtgenote kunnen worden aangeboden, zelfs als er geen anderen zijn.
Alles gebeurt in beide richtingen, hetzelfde voor meisjes.
De initiële gegevens zijn willekeurig. De enige veronderstelling/beperking is dat we onze voorkeuren niet veranderen.
Stelling: Ongeacht de verdeling en het nulniveau is er altijd een manier om een één-op-één-correspondentie tot stand te brengen tussen sommige mannen en sommige vrouwen, zodat deze bestand is tegen alle soorten splitsingen (niet alleen echtscheidingen).
Welke bedreigingen kunnen er zijn?
Er is een echtpaar (m,v) dat niet getrouwd is. Maar voor w is de huidige echtgenoot slechter dan m, en voor m is de huidige vrouw slechter dan w. Dit is een onhoudbare situatie.
Ook bestaat de mogelijkheid dat iemand getrouwd is geweest met iemand die ‘onder nul’ is; in deze situatie valt het huwelijk ook uiteen.
Als een vrouw getrouwd is, maar ze de voorkeur geeft aan een ongehuwde man, voor wie ze boven de nul staat.
Als twee mensen allebei ongehuwd zijn, en beiden ‘boven nul’ voor elkaar staan.
Er wordt betoogd dat op basis van alle initiële gegevens zo’n huwelijkssysteem bestaat, dat bestand is tegen alle soorten bedreigingen. Ten tweede is het algoritme voor het vinden van een dergelijk evenwicht heel eenvoudig. Laten we eens vergelijken met M*N.
Dit model werd gegeneraliseerd en uitgebreid tot "polygamie" en op veel gebieden toegepast.
Gale-Shapley-procedure
Als alle mannen en alle vrouwen de ‘voorschriften’ volgen, zal het resulterende huwelijkssysteem duurzaam zijn.
Recepten.
Indien nodig nemen we een paar dagen de tijd. We verdelen elke dag in twee delen (ochtend en avond).
Op de eerste ochtend gaat elke man naar zijn beste vrouw en klopt op het raam om haar ten huwelijk te vragen.
Op de avond van dezelfde dag is het de beurt aan de vrouwen: wat kan een vrouw ontdekken? Dat er een menigte onder haar raam stond, één of geen mannen. Degenen die vandaag niemand hebben, slaan hun beurt over en wachten. De rest, die er minstens één heeft, controleert de mannen die komen kijken of ze ‘boven niveau nul’ zitten. Om er tenminste één te hebben. Als je helemaal pech hebt en alles onder nul is, dan moet iedereen gestuurd worden. De vrouw kiest de grootste van degenen die kwamen, zegt hem te wachten en stuurt de rest.
Vóór de tweede dag is de situatie als volgt: sommige vrouwen hebben één man, andere geen.
Op de tweede dag moeten alle “vrije” (gezonden) mannen naar de vrouw met de tweede prioriteit gaan. Is er geen sprake van een dergelijke persoon, dan wordt de man alleenstaand verklaard. Die mannen die al bij vrouwen zitten, doen nog niets.
'S Avonds bekijken de vrouwen de situatie. Als iemand die al zat, gezelschap krijgt van een hogere prioriteit, dan wordt de lagere prioriteit weggestuurd. Als degenen die komen lager zijn dan wat al beschikbaar is, wordt iedereen weggestuurd. Vrouwen kiezen elke keer voor het maximale element.
We herhalen.
Als gevolg hiervan doorliep elke man de hele lijst van zijn vrouwen en werd hij met rust gelaten of verloofd met een vrouw. Dan laten we iedereen trouwen.
Is het mogelijk om dit hele proces te runnen, maar dat vrouwen naar mannen toe rennen? De procedure is symmetrisch, maar de oplossing kan anders zijn. Maar de vraag is: wie is hier beter af?
Stelling. Laten we niet alleen deze twee symmetrische oplossingen bekijken, maar ook de verzameling van alle stabiele huwelijkssystemen. Het oorspronkelijk voorgestelde mechanisme (mannen rennen en vrouwen accepteren/weigeren) resulteert in een huwelijkssysteem dat beter is voor iedere man dan welke andere dan ook en slechter dan welk ander systeem dan ook voor welke vrouw dan ook.
Homohuwelijk
Neem de situatie met het ‘homohuwelijk’. Laten we eens een wiskundig resultaat bekijken dat twijfel doet rijzen over de noodzaak om ze te legaliseren. Een ideologisch onjuist voorbeeld.
Beschouw vier homoseksuelen a, b, c, d.
prioriteiten voor a: bcd
prioriteiten voor b:cad
prioriteiten voor c: abd
voor d maakt het niet uit hoe hij de overige drie rangschikt.
Uitspraak: Er bestaat in dit systeem geen duurzaam huwelijkssysteem.
Hoeveel systemen zijn er voor vier personen? Drie. ab cd, ac bd, ad bc. De paren zullen uit elkaar vallen en het proces zal in cycli verlopen.
"Drie-gender"-systemen.
Dit is de belangrijkste vraag die een heel gebied van de wiskunde opent. Dit werd gedaan door mijn collega in Moskou, Vladimir Ivanovitsj Danilov. Hij beschouwde ‘het huwelijk’ als het drinken van wodka en de rollen waren als volgt: ‘degene die schenkt’, ‘degene die de toast uitspreekt’ en ‘degene die de worst snijdt’. In een situatie waarin er vier of meer vertegenwoordigers van elke rol zijn, is het onmogelijk om deze met brute kracht op te lossen. De vraag naar een duurzaam systeem is een open vraag.
Shapley-vector
In het huisjesdorp besloten ze de weg te asfalteren. Moet inhaken. Hoe?
Shapley stelde in 1953 een oplossing voor dit probleem voor. Laten we een conflictsituatie aannemen met een groep mensen N={1,2…n}. Kosten/baten moeten gedeeld worden. Stel dat mensen samen iets nuttigs doen, het verkopen en hoe de winst verdelen?
Shapley suggereerde dat we ons bij het verdelen moeten laten leiden door hoeveel bepaalde subgroepen van deze mensen zouden kunnen ontvangen. Hoeveel geld kunnen alle 2N niet-lege subsets verdienen? En op basis van deze informatie schreef Shapley een universele formule.
Voorbeeld. Een solist, gitarist en drummer spelen in een ondergrondse passage in Moskou. Ze verdienen alle drie 1000 roebel per uur. Hoe het te verdelen? Mogelijk evenveel.
V(1,2,3)=1000
Laten we doen alsof
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Er kan pas een eerlijke verdeling worden gemaakt als we weten welke winst een bepaald bedrijf te wachten staat als het zich losmaakt en op eigen kracht handelt. En toen we de cijfers bepaalden (het coöperatieve spel in karakteristieke vorm zetten).
Superadditiviteit is wanneer ze samen meer verdienen dan afzonderlijk, wanneer het winstgevender is om zich te verenigen, maar het is niet duidelijk hoe de winsten moeten worden verdeeld. Hierover zijn veel exemplaren kapot gegaan.
Er is een spel. Drie zakenlieden vonden tegelijkertijd een aanbetaling ter waarde van $ 1 miljoen. Als ze het alle drie eens zijn, zijn het er een miljoen. Elk stel kan doden (uit de zaak verwijderen) en het hele miljoen voor zichzelf krijgen. En niemand kan iets alleen. Dit is een eng coöpspel zonder oplossing. Er zullen altijd twee mensen zijn die de derde kunnen elimineren... Coöperatieve speltheorie begint met een voorbeeld dat geen oplossing kent.
Wij willen een zodanige oplossing dat geen enkele coalitie de gemeenschappelijke oplossing wil blokkeren. De verzameling van alle divisies die niet kunnen worden geblokkeerd, is de kernel. Het komt voor dat de kern leeg is. Maar zelfs als het niet leeg is, hoe te verdelen?
Shapley stelt voor om op deze manier te verdelen. Gooi een munt met n! randen. We schrijven alle spelers in deze volgorde op. Laten we zeggen de eerste drummer. Hij komt binnen en neemt zijn 100. Dan komt de ‘tweede’ binnen, laten we zeggen de solist. (Samen met de drummer kunnen ze 450 verdienen, de drummer heeft er al 100 verdiend) De solist neemt 350. De gitarist komt binnen (samen 1000, -450), neemt 550. De laatste die vrij vaak wint. (Supermodulariteit)
Als we voor alle bestellingen schrijven:
GSB - (winst C) - (winst D) - (winst B)
SGB - (winst C) - (winst D) - (winst B)
SBG - (winst C) - (winst D) - (winst B)
BSG - (winst C) - (winst D) - (winst B)
BGS - (winst C) - (winst D) - (winst B)
GBS - (winst C) - (winst D) - (winst B)
En voor elke kolom tellen we op en delen we door 6 - het gemiddelde over alle bestellingen - dit is een Shapley-vector.
Shapley bewees de stelling (ongeveer): Er is een klasse van spellen (supermodulair), waarin de volgende persoon die zich bij een groot team voegt een grotere overwinning oplevert. De kernel is altijd niet leeg en is een convexe combinatie van punten (in ons geval 6 punten). De Shapley-vector ligt precies in het centrum van de kern. Het kan altijd als oplossing worden aangeboden, niemand zal er tegen zijn.
In 1973 werd bewezen dat het probleem met huisjes supermodulair is.
Alle n mensen delen de weg naar het eerste huisje. Tot de tweede - n-1 personen. Enz.
De luchthaven heeft een landingsbaan. Verschillende bedrijven hebben verschillende lengtes nodig. Hetzelfde probleem doet zich voor.
Ik denk dat degenen die de Nobelprijs uitreikten deze verdienste in gedachten hadden, en niet alleen de taak van marge.
Dank je wel!
Ещё
- Kanaal “Wiskunde - Eenvoudig”:
- Kanaal “Savvateev zonder grenzen”: edusex.ru, brainsex.ru, studfuck.ru
- Publiek “Wiskunde is eenvoudig”:
- Publieke “Wiskundigen maken grapjes”:
- Website, alle lezingen daar +100 lessen en meer: savvateev.xyz
Bron: www.habr.com