I 2012 ble Nobelprisen i økonomi tildelt Lloyd Shapley og Alvin Roth. "For teorien om stabil distribusjon og praksisen med å organisere markeder." Aleksey Savvateev i 2012 prøvde å enkelt og tydelig forklare essensen av matematikernes fordeler. Jeg gir deg en oppsummering .
I dag blir det teoretisk forelesning. Om eksperimenter , spesielt med donasjon, vil jeg ikke fortelle.
Da det ble annonsert at mottok Nobelprisen, var det et standardspørsmål: «Hvordan!? Lever han fortsatt!?!?” Hans mest kjente resultat ble oppnådd i 1953.
Formelt ble bonusen gitt for noe annet. For hans artikkel fra 1962 om "ekteskapsstabilitetsteoremet": "Høgskoleopptak og ekteskapets stabilitet."
Om bærekraftig ekteskap
Matchende (matching) - oppgaven med å finne en korrespondanse.
Det er en viss isolert landsby. Det er "m" unge menn og "w" jenter. Vi må gifte dem med hverandre. (Ikke nødvendigvis samme nummer, kanskje til slutt vil noen bli stående alene.)
Hvilke forutsetninger må gjøres i modellen? At det ikke er lett å gifte seg på nytt tilfeldig. Det tas et visst skritt mot fritt valg. La oss si at det er en klok aksakal som ønsker å gifte seg på nytt slik at skilsmisser ikke starter etter hans død. (Skilsmisse er en situasjon når en mann ønsker en tredjepartskvinne som sin kone mer enn sin kone.)
Dette teoremet er i ånden til moderne økonomi. Hun er usedvanlig umenneskelig. Økonomi har tradisjonelt vært umenneskelig. I økonomi er mennesket erstattet av en maskin for å maksimere profitt. Det jeg vil fortelle deg er helt sprø ting fra et moralsk synspunkt. Ikke ta det til hjertet.
Økonomer ser på ekteskap på denne måten.
m1, m2,... mk - menn.
w1, w2,... wL - kvinner.
En mann identifiseres med hvordan han "beordrer" jenter. Det er også et "nullnivå", under hvilket kvinner ikke kan tilbys som koner i det hele tatt, selv om det ikke er andre.
Alt skjer i begge retninger, det samme for jenter.
De første dataene er vilkårlige. Den eneste antagelsen/begrensningen er at vi ikke endrer våre preferanser.
Teorem: Uavhengig av fordelingen og nivået på null, er det alltid en måte å etablere en-til-en-korrespondanse mellom noen menn og noen kvinner slik at den er robust mot alle typer splittelser (ikke bare skilsmisser).
Hvilke trusler kan det være?
Det er et par (m,w) som ikke er gift. Men for w er den nåværende mannen verre enn m, og for m er den nåværende konen verre enn w. Dette er en uholdbar situasjon.
Det er også mulighet for at noen var gift med en som er "under null"; i denne situasjonen vil ekteskapet også falle fra hverandre.
Hvis en kvinne er gift, men hun foretrekker en ugift mann, for hvem hun er over null.
Hvis to personer begge er ugifte, og begge er "over null" for hverandre.
Det hevdes at for alle innledende data eksisterer et slikt ekteskapssystem som er motstandsdyktig mot alle typer trusler. For det andre er algoritmen for å finne en slik likevekt veldig enkel. La oss sammenligne med M*N.
Denne modellen ble generalisert og utvidet til "polygami" og anvendt på mange områder.
Gale-Shapley prosedyre
Hvis alle menn og alle kvinner følger "reseptene", vil det resulterende ekteskapssystemet være bærekraftig.
Resepter.
Vi bruker noen dager etter behov. Vi deler hver dag i to deler (morgen og kveld).
Den første morgenen går hver mann til sin beste kvinne og banker på vinduet og ber henne om å gifte seg med ham.
Om kvelden samme dag går turen til kvinnene Hva kan en kvinne oppdage? At det var en folkemengde under vinduet hennes, enten en eller ingen menn. De som ikke har noen i dag hopper over tur og venter. Resten, som har minst én, sjekker mennene som kommer for å se at de er «over nivå null». Å ha minst en. Er du helt uheldig og alt er under null, så skal alle sendes. Kvinnen velger den største av de som kom, ber ham vente og sender resten.
Før den andre dagen er situasjonen denne: Noen kvinner har én mann, noen har ingen.
På den andre dagen må alle "frie" (sendte) menn gå til den andre prioriterte kvinnen. Hvis det ikke finnes en slik person, blir mannen erklært singel. De mennene som allerede sitter med kvinner, gjør ikke noe ennå.
Om kvelden ser kvinnene på situasjonen. Hvis noen som allerede satt fikk selskap av en høyere prioritet, så sendes den lavere prioritet bort. Hvis de som kommer er lavere enn det som allerede er tilgjengelig, sendes alle bort. Kvinner velger det maksimale elementet hver gang.
Vi gjentar.
Som et resultat gikk hver mann gjennom hele listen over kvinnene sine og ble enten stående alene eller forlovet med en kvinne. Da skal vi gifte alle.
Er det mulig å kjøre hele denne prosessen, men for kvinner å løpe til menn? Prosedyren er symmetrisk, men løsningen kan være annerledes. Men spørsmålet er, hvem har det bedre med dette?
Teorem. La oss vurdere ikke bare disse to symmetriske løsningene, men settet av alle stabile ekteskapssystemer. Den opprinnelige foreslåtte mekanismen (menn løper og kvinner aksepterer/nekter) resulterer i et ekteskapssystem som er bedre for enhver mann enn noen annen og verre enn noen annen for noen kvinne.
Ekteskap av samme kjønn
Tenk på situasjonen med «ekteskap av samme kjønn». La oss vurdere et matematisk resultat som sår tvil om behovet for å legalisere dem. Et ideologisk feil eksempel.
Tenk på fire homofile a, b, c, d.
prioriteringer for a: bcd
prioriteringer for b:cad
prioriteringer for c: abd
for d spiller det ingen rolle hvordan han rangerer de resterende tre.
Uttalelse: Det er ikke noe bærekraftig ekteskapssystem i dette systemet.
Hvor mange systemer er det for fire personer? Tre. ab cd, ac bd, ad bc. Parene vil falle fra hverandre og prosessen vil gå i sykluser.
"Tre-kjønns"-systemer.
Dette er det viktigste spørsmålet som åpner for et helt felt innen matematikk. Dette ble gjort av min kollega i Moskva, Vladimir Ivanovich Danilov. Han så på «ekteskap» som å drikke vodka, og rollene var som følger: «den som skjenker», «den som snakker toast» og «den som skjærer pølsen». I en situasjon der det er 4 eller flere representanter for hver rolle, er det umulig å løse med rå makt. Spørsmålet om et bærekraftig system er åpent.
Shapley vektor
I hyttebygda bestemte de seg for å asfaltere veien. Må chipe inn. Hvordan?
Shapley foreslo en løsning på dette problemet i 1953. La oss anta en konfliktsituasjon med en gruppe mennesker N={1,2…n}. Kostnader/fordeler må deles. Tenk deg at folk sammen gjorde noe nyttig, selge det og hvordan dele overskuddet?
Shapley foreslo at når vi deler, skulle vi bli veiledet av hvor mye visse undergrupper av disse menneskene kunne motta. Hvor mye penger kan alle 2N ikke-tomme delsett tjene? Og basert på denne informasjonen skrev Shapley en universell formel.
Eksempel. En solist, gitarist og trommeslager spiller i en underjordisk passasje i Moskva. De tre tjener 1000 rubler i timen. Hvordan dele den opp? Muligens like mye.
V(1,2,3)=1000
La oss late som det
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
En rettferdig deling kan ikke fastsettes før vi vet hvilke gevinster som venter et gitt selskap hvis det bryter ut og handler på egenhånd. Og når vi bestemte tallene (sett samarbeidsspillet i karakteristisk form).
Superadditivitet er når de sammen tjener mer enn hver for seg, når det er mer lønnsomt å slå seg sammen, men det er ikke klart hvordan man skal dele gevinsten. Mange kopier har blitt brutt om dette.
Det er et spill. Tre forretningsmenn fant samtidig et innskudd verdt 1 million dollar. Hvis de tre er enige, så er det en million av dem. Ethvert par kan drepe (fjerne fra saken) og få hele millionen for seg selv. Og ingen kan gjøre noe alene. Dette er et skummelt samarbeidsspill uten løsning. Det vil alltid være to personer som kan eliminere den tredje... Samarbeidsspillteori begynner med et eksempel som ikke har noen løsning.
Vi ønsker en slik løsning at ingen koalisjon vil blokkere den felles løsningen. Settet med alle divisjoner som ikke kan blokkeres er kjernen. Det hender at kjernen er tom. Men selv om det ikke er tomt, hvordan dele?
Shapley foreslår å dele på denne måten. Kast en mynt med n! kanter. Vi skriver ut alle spillerne i denne rekkefølgen. La oss si den første trommeslageren. Han kommer inn og tar sine 100. Så kommer «den andre» inn, la oss si solisten. (Sammen med trommeslageren kan de tjene 450, trommeslageren har allerede tatt 100) Solisten tar 350. Gitaristen kommer inn (tilsammen 1000, -450), tar 550. Den siste inn vinner ganske ofte. (Supermodularitet)
Hvis vi skriver ut for alle bestillinger:
GSB - (vinner C) - (vinner D) - (vinner B)
SGB - (seier C) - (seier D) - (seier B)
SBG - (seier C) - (seier D) - (seier B)
BSG - (seier C) - (seier D) - (seier B)
BGS - (gain C) - (gain D) - (gain B)
GBS - (vinner C) - (vinner D) - (vinner B)
Og for hver kolonne legger vi til og deler med 6 - gjennomsnitt over alle bestillinger - dette er en Shapley-vektor.
Shapley beviste teoremet (omtrent): Det er en klasse med spill (supermodulære), der den neste personen som blir med i et stort lag gir det en større gevinst. Kjernen er alltid ikke-tom og er en konveks kombinasjon av punkter (i vårt tilfelle, 6 punkter). Shapley-vektoren ligger i sentrum av kjernen. Det kan alltid tilbys som en løsning, ingen vil være imot det.
I 1973 ble det bevist at problemet med hytter er supermodulært.
Alle n personer deler veien til den første hytta. Opp til den andre - n-1 personer. Etc.
Flyplassen har en rullebane. Ulike selskaper trenger forskjellige lengder. Det samme problemet oppstår.
Jeg tror at de som delte ut Nobelprisen hadde denne fortjenesten i tankene, og ikke bare marginoppgaven.
Takk!
Ещё
- Kanal "Math - Simple":
- Kanal "Savvateev uten grenser": edusex.ru, brainsex.ru, studfuck.ru
- Offentlig "Matematikk er enkel":
- Offentlig "matematiker-vits":
- Nettsted, alle forelesninger der +100 leksjoner og mer: savvateev.xyz
Kilde: www.habr.com