Το 2012, το Νόμπελ Οικονομικών απονεμήθηκε στους Lloyd Shapley και Alvin Roth. «Για τη θεωρία της σταθερής διανομής και την πρακτική της οργάνωσης των αγορών». Ο Aleksey Savvateev το 2012 προσπάθησε να εξηγήσει απλά και ξεκάθαρα την ουσία των πλεονεκτημάτων των μαθηματικών. Σας παρουσιάζω μια περίληψη .
Σήμερα θα γίνει θεωρητική διάλεξη. Σχετικά με τα πειράματα , ιδίως με τη δωρεά, δεν θα πω.
Όταν ανακοινώθηκε ότι έλαβε το βραβείο Νόμπελ, υπήρχε μια τυπική ερώτηση: «Πώς!; Είναι ακόμα ζωντανός!;!;» Το πιο διάσημο αποτέλεσμα του ελήφθη το 1953.
Τυπικά, το μπόνους δόθηκε για κάτι άλλο. Για την εργασία του το 1962 σχετικά με το «θεώρημα της σταθερότητας του γάμου»: «Είσοδος στο κολέγιο και η σταθερότητα του γάμου».
Σχετικά με τον βιώσιμο γάμο
Αντιστοίχιση (αντιστοιχία) - το έργο της εύρεσης μιας αντιστοιχίας.
Υπάρχει ένα συγκεκριμένο απομονωμένο χωριό. Υπάρχουν «m» νεαροί άνδρες και «w» κορίτσια. Πρέπει να τους παντρέψουμε μεταξύ τους. (Όχι απαραίτητα ο ίδιος αριθμός, ίσως στο τέλος κάποιος να μείνει μόνος.)
Ποιες υποθέσεις πρέπει να γίνουν στο μοντέλο; Ότι δεν είναι εύκολο να ξαναπαντρευτείς τυχαία. Γίνεται ένα συγκεκριμένο βήμα προς την ελεύθερη επιλογή. Ας πούμε ότι υπάρχει ένας σοφός aksakal που θέλει να ξαναπαντρευτεί για να μην αρχίσουν μετά το θάνατό του τα διαζύγια. (Το διαζύγιο είναι μια κατάσταση όταν ένας σύζυγος θέλει μια γυναίκα τρίτου για σύζυγό του περισσότερο από τη σύζυγό του.)
Αυτό το θεώρημα είναι στο πνεύμα της σύγχρονης οικονομίας. Είναι εξαιρετικά απάνθρωπη. Η οικονομία ήταν παραδοσιακά απάνθρωπη. Στην οικονομία, ο άνθρωπος αντικαθίσταται από μια μηχανή για τη μεγιστοποίηση των κερδών. Αυτό που θα σας πω είναι απολύτως τρελά πράγματα από ηθική άποψη. Μην το παίρνετε στην καρδιά.
Οι οικονομολόγοι βλέπουν τον γάμο με αυτόν τον τρόπο.
m1, m2,… mk - άνδρες.
w1, w2,... wL - γυναίκες.
Ένας άντρας ταυτίζεται με το πώς «παραγγέλνει» τα κορίτσια. Υπάρχει επίσης ένα «μηδενικό επίπεδο», κάτω από το οποίο οι γυναίκες δεν μπορούν να προσφερθούν καθόλου ως σύζυγοι, ακόμα κι αν δεν υπάρχουν άλλες.
Όλα συμβαίνουν και προς τις δύο κατευθύνσεις, το ίδιο και για τα κορίτσια.
Τα αρχικά δεδομένα είναι αυθαίρετα. Η μόνη υπόθεση/περιορισμός είναι ότι δεν αλλάζουμε τις προτιμήσεις μας.
Θεώρημα: Ανεξάρτητα από την κατανομή και το επίπεδο μηδέν, υπάρχει πάντα ένας τρόπος να δημιουργηθεί μια αλληλογραφία ένας προς έναν μεταξύ ορισμένων ανδρών και ορισμένων γυναικών, ώστε να είναι ανθεκτική σε όλους τους τύπους χωρισμών (όχι μόνο στα διαζύγια).
Τι απειλές μπορεί να υπάρχουν;
Υπάρχει ένα ζευγάρι (m,w) που δεν είναι παντρεμένο. Αλλά για το w ο σημερινός σύζυγος είναι χειρότερος από τον m, και για τον m η σημερινή σύζυγος είναι χειρότερος από τον w. Αυτή είναι μια μη βιώσιμη κατάσταση.
Υπάρχει επίσης η επιλογή ότι κάποιος ήταν παντρεμένος με κάποιον που είναι «κάτω από το μηδέν»· σε αυτήν την περίπτωση, ο γάμος θα καταρρεύσει επίσης.
Αν μια γυναίκα είναι παντρεμένη, αλλά προτιμά έναν ανύπαντρο, για τον οποίο είναι πάνω από το μηδέν.
Εάν δύο άτομα είναι και τα δύο ανύπαντρα, και τα δύο είναι «πάνω από το μηδέν» το ένα για το άλλο.
Υποστηρίζεται ότι για οποιαδήποτε αρχικά δεδομένα υπάρχει ένα τέτοιο σύστημα γάμου, ανθεκτικό σε κάθε είδους απειλές. Δεύτερον, ο αλγόριθμος για την εύρεση μιας τέτοιας ισορροπίας είναι πολύ απλός. Ας συγκρίνουμε με τον Μ*Ν.
Αυτό το μοντέλο γενικεύτηκε και επεκτάθηκε στην «πολυγαμία» και εφαρμόστηκε σε πολλούς τομείς.
Διαδικασία Gale-Shapley
Εάν όλοι οι άνδρες και όλες οι γυναίκες ακολουθήσουν τις «συνταγές», το προκύπτον σύστημα γάμου θα είναι βιώσιμο.
Συνταγές.
Παίρνουμε λίγες μέρες όπως χρειάζεται. Χωρίζουμε κάθε μέρα σε δύο μέρη (πρωί και βράδυ).
Το πρώτο πρωί κάθε άντρας πηγαίνει στην κουμπάρα του και χτυπάει το παράθυρο ζητώντας της να τον παντρευτεί.
Το βράδυ της ίδιας μέρας η σειρά γυρίζει στις γυναίκες Τι μπορεί να ανακαλύψει μια γυναίκα; Ότι υπήρχε ένα πλήθος κάτω από το παράθυρό της, είτε ένας είτε κανένας άνδρας. Όσοι δεν έχουν κανέναν σήμερα, παραλείπουν τη σειρά τους και περιμένουν. Οι υπόλοιποι, που έχουν τουλάχιστον ένα, ελέγχουν τους άνδρες που έρχονται για να δουν ότι είναι «πάνω από το μηδέν». Να έχει τουλάχιστον ένα. Εάν είστε εντελώς άτυχοι και όλα είναι κάτω από το μηδέν, τότε θα πρέπει να σταλούν όλοι. Η γυναίκα διαλέγει τον μεγαλύτερο από αυτούς που ήρθαν, του λέει να περιμένει και στέλνει τους υπόλοιπους.
Πριν από τη δεύτερη μέρα, η κατάσταση είναι η εξής: κάποιες γυναίκες έχουν έναν άντρα, κάποιες δεν έχουν κανέναν.
Τη δεύτερη μέρα, όλοι οι «ελεύθεροι» (απεσταλμένοι) άνδρες πρέπει να πάνε στη γυναίκα δεύτερης προτεραιότητας. Αν δεν υπάρχει τέτοιο πρόσωπο, τότε ο άνδρας δηλώνεται άγαμος. Όσοι άντρες κάθονται ήδη με γυναίκες δεν κάνουν τίποτα ακόμα.
Το βράδυ, οι γυναίκες κοιτάζουν την κατάσταση. Εάν σε κάποιον που καθόταν ήδη είχε μια υψηλότερη προτεραιότητα, τότε η χαμηλότερη προτεραιότητα απομακρύνεται. Εάν αυτοί που έρχονται είναι χαμηλότεροι από ό,τι είναι ήδη διαθέσιμο, όλοι απομακρύνονται. Οι γυναίκες επιλέγουν το μέγιστο στοιχείο κάθε φορά.
Επαναλαμβάνουμε.
Ως αποτέλεσμα, κάθε άντρας πέρασε από όλη τη λίστα με τις γυναίκες του και είτε έμεινε μόνος είτε αρραβωνιάστηκε με κάποια γυναίκα. Τότε θα παντρευτούμε όλοι.
Είναι δυνατόν να τρέχει όλη αυτή η διαδικασία, αλλά οι γυναίκες να τρέχουν προς τους άνδρες; Η διαδικασία είναι συμμετρική, αλλά η λύση μπορεί να είναι διαφορετική. Αλλά το ερώτημα είναι ποιος είναι καλύτερος από αυτό;
Θεώρημα. Ας εξετάσουμε όχι μόνο αυτές τις δύο συμμετρικές λύσεις, αλλά το σύνολο όλων των σταθερών συστημάτων γάμου. Ο αρχικός προτεινόμενος μηχανισμός (οι άνδρες τρέχουν και οι γυναίκες αποδέχονται/αρνούνται) έχει ως αποτέλεσμα ένα σύστημα γάμου που είναι καλύτερο για κάθε άντρα από οποιονδήποτε άλλο και χειρότερο από οποιοδήποτε άλλο για κάθε γυναίκα.
Γάμος ομοφυλοφίλων
Εξετάστε την κατάσταση με τον «γάμο ομοφύλων». Ας εξετάσουμε ένα μαθηματικό αποτέλεσμα που θέτει υπό αμφισβήτηση την ανάγκη νομιμοποίησής τους. Ένα ιδεολογικά λανθασμένο παράδειγμα.
Σκεφτείτε τέσσερις ομοφυλόφιλους α, β, γ, δ.
προτεραιότητες για ένα: π.χ
προτεραιότητες για b:cad
προτεραιότητες για γ: αβδ
για δ δεν έχει σημασία πώς κατατάσσει τα υπόλοιπα τρία.
Δήλωση: Δεν υπάρχει σύστημα βιώσιμου γάμου σε αυτό το σύστημα.
Πόσα συστήματα υπάρχουν για τέσσερα άτομα; Τρία. ab cd, ac bd, ad bc. Τα ζευγάρια θα χωρίσουν και η διαδικασία θα κάνει κύκλους.
Συστήματα «τριών φύλων».
Αυτό είναι το πιο σημαντικό ερώτημα που ανοίγει ένα ολόκληρο πεδίο των μαθηματικών. Αυτό το έκανε ο συνάδελφός μου στη Μόσχα, Βλαντιμίρ Ιβάνοβιτς Ντανίλοφ. Έβλεπε τον «γάμο» σαν να πίνει βότκα και οι ρόλοι ήταν οι εξής: «αυτός που χύνει», «αυτός που λέει το τοστ» και «αυτός που κόβει το λουκάνικο». Σε μια κατάσταση όπου υπάρχουν 4 ή περισσότεροι εκπρόσωποι για κάθε ρόλο, είναι αδύνατο να λυθεί με ωμή βία. Το ζήτημα ενός βιώσιμου συστήματος είναι ανοιχτό.
διάνυσμα Shapley
Στο εξοχικό χωριό αποφάσισαν να ασφαλτοστρώσουν τον δρόμο. Ανάγκη να μπείτε. Πως?
Ο Shapley πρότεινε μια λύση σε αυτό το πρόβλημα το 1953. Ας υποθέσουμε μια κατάσταση σύγκρουσης με μια ομάδα ατόμων N={1,2…n}. Τα κόστη/τα οφέλη πρέπει να μοιράζονται. Ας υποθέσουμε ότι οι άνθρωποι μαζί έκαναν κάτι χρήσιμο, το πούλησαν και πώς να μοιράσουν το κέρδος;
Ο Shapley πρότεινε ότι κατά τη διαίρεση, θα έπρεπε να καθοδηγούμαστε από το πόσα θα μπορούσαν να λάβουν ορισμένα υποσύνολα αυτών των ανθρώπων. Πόσα χρήματα θα μπορούσαν να κερδίσουν όλα τα 2Ν μη-κενά υποσύνολα; Και με βάση αυτές τις πληροφορίες, ο Shapley έγραψε μια καθολική φόρμουλα.
Παράδειγμα. Ένας σολίστ, κιθαρίστας και ντράμερ παίζουν σε ένα υπόγειο πέρασμα στη Μόσχα. Οι τρεις τους κερδίζουν 1000 ρούβλια την ώρα. Πώς να το χωρίσετε; Ενδεχομένως εξίσου.
V(1,2,3)=1000
Ας προσποιηθούμε ότι
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Ένας δίκαιος διαχωρισμός δεν μπορεί να καθοριστεί έως ότου μάθουμε ποια κέρδη περιμένουν μια δεδομένη εταιρεία εάν αποχωριστεί και ενεργήσει από μόνη της. Και όταν προσδιορίσαμε τους αριθμούς (θέστε το συνεργατικό παιχνίδι σε χαρακτηριστική μορφή).
Η υπερπροσθετικότητα είναι όταν μαζί κερδίζουν περισσότερα από χωριστά, όταν είναι πιο κερδοφόρο να ενωθούν, αλλά δεν είναι ξεκάθαρο πώς να μοιράζονται τα κέρδη. Πολλά αντίγραφα έχουν σπάσει σχετικά με αυτό.
Υπάρχει ένα παιχνίδι. Τρεις επιχειρηματίες βρήκαν ταυτόχρονα μια κατάθεση αξίας 1 εκατομμυρίου δολαρίων. Αν συμφωνούν και οι τρεις τους, τότε υπάρχουν ένα εκατομμύριο. Οποιοδήποτε ζευγάρι μπορεί να σκοτώσει (να αφαιρέσει από την υπόθεση) και να πάρει ολόκληρο το εκατομμύριο για τον εαυτό του. Και κανείς δεν μπορεί να κάνει τίποτα μόνος του. Αυτό είναι ένα τρομακτικό παιχνίδι συνεργασίας χωρίς λύση. Πάντα θα υπάρχουν δύο άνθρωποι που μπορούν να εξαλείψουν το τρίτο... Η θεωρία των συνεργατικών παιγνίων ξεκινά με ένα παράδειγμα που δεν έχει λύση.
Θέλουμε μια τέτοια λύση που κανένας συνασπισμός δεν θα θέλει να εμποδίσει την κοινή λύση. Το σύνολο όλων των τμημάτων που δεν μπορούν να αποκλειστούν είναι ο πυρήνας. Συμβαίνει ότι ο πυρήνας είναι άδειος. Αλλά ακόμα κι αν δεν είναι άδειο, πώς να διαιρέσουμε;
Ο Shapley προτείνει τη διαίρεση με αυτόν τον τρόπο. Πέτα ένα κέρμα με n! άκρα. Γράφουμε όλους τους παίκτες με αυτή τη σειρά. Ας πούμε ο πρώτος ντράμερ. Μπαίνει και παίρνει τα 100 του. Μετά μπαίνει ο «δεύτερος», ας πούμε ο σολίστ. (Μαζί με τον ντράμερ μπορούν να κερδίσουν 450, ο ντράμερ έχει πάρει ήδη 100) Ο σολίστας παίρνει 350. Ο κιθαρίστας μπαίνει (μαζί 1000, -450), παίρνει 550. Ο τελευταίος σε αρκετά συχνά κερδίζει. (Υπεραρθρωτότητα)
Αν γράψουμε για όλες τις παραγγελίες:
GSB - (νίκη C) - (νίκη D) - (νίκη B)
SGB - (νίκη C) - (νίκη D) - (νίκη B)
SBG - (νίκη C) - (νίκη D) - (νίκη B)
BSG - (νίκη C) - (νίκη D) - (νίκη B)
BGS - (κέρδος C) - (κέρδος D) - (κέρδος B)
GBS - (νίκη C) - (νίκη D) - (νίκη B)
Και για κάθε στήλη προσθέτουμε και διαιρούμε με το 6 - κατά μέσο όρο σε όλες τις παραγγελίες - αυτό είναι ένα διάνυσμα Shapley.
Ο Shapley απέδειξε το θεώρημα (κατά προσέγγιση): Υπάρχει μια κατηγορία παιχνιδιών (supermodular), στα οποία το επόμενο άτομο που θα ενταχθεί σε μια μεγάλη ομάδα φέρνει μεγαλύτερη νίκη σε αυτήν. Ο πυρήνας είναι πάντα μη κενός και είναι ένας κυρτός συνδυασμός σημείων (στην περίπτωσή μας, 6 βαθμοί). Το διάνυσμα Shapley βρίσκεται στο κέντρο του πυρήνα. Μπορεί πάντα να προσφερθεί ως λύση, κανείς δεν θα είναι αντίθετος.
Το 1973, αποδείχθηκε ότι το πρόβλημα με τις εξοχικές κατοικίες είναι υπερmodular.
Όλοι οι άνθρωποι μοιράζονται το δρόμο για το πρώτο εξοχικό σπίτι. Μέχρι το δεύτερο - n-1 άτομα. Και τα λοιπά.
Το αεροδρόμιο διαθέτει διάδρομο προσγείωσης. Διαφορετικές εταιρείες χρειάζονται διαφορετικά μήκη. Το ίδιο πρόβλημα προκύπτει.
Νομίζω ότι αυτοί που απένειμαν το βραβείο Νόμπελ είχαν αυτή την αξία στο μυαλό τους και όχι απλώς το καθήκον του περιθωρίου.
Σας ευχαριστούμε!
Ещё
- Κανάλι "Τα μαθηματικά είναι απλά":
- Κανάλι "Savvateev χωρίς σύνορα": edusex.ru, brainsex.ru, studfuck.ru
- Δημόσιο «Τα μαθηματικά είναι απλά»:
- Δημόσιο «Μαθηματικοί αστειεύονται»:
- Ιστοσελίδα, όλες οι διαλέξεις εκεί +100 μαθήματα και άλλα: savvateev.xyz
Πηγή: www.habr.com