2012 දී ආර්ථික විද්‍යාව සඳහා වූ නොබෙල් ත්‍යාගය ලොයිඩ් ෂේප්ලි සහ ඇල්වින් රොත් වෙත පිරිනමන ලදී. "ස්ථාවර බෙදාහැරීමේ න්‍යාය සහ වෙළඳපල සංවිධානය කිරීමේ පරිචය සඳහා." 2012 දී Aleksey Savvateev ගණිතඥයින්ගේ කුසලතාවයේ සාරය සරලව හා පැහැදිලිව පැහැදිලි කිරීමට උත්සාහ කළේය. මම ඔබේ අවධානයට සාරාංශයක් ඉදිරිපත් කරමි .
අද න්‍යායාත්මක දේශනයක් පැවැත්වෙනවා. අත්හදා බැලීම් ගැන , විශේෂයෙන් පරිත්‍යාග සමඟ, මම නොකියමි.
ඒ බව ප්‍රකාශ කළ අවස්ථාවේදීය නොබෙල් ත්‍යාගය ලැබුණා, සම්මත ප්‍රශ්නයක් තිබුණා: “කොහොමද!? ඔහු තවමත් ජීවතුන් අතරද!?!?" ඔහුගේ වඩාත් ප්රසිද්ධ ප්රතිඵලය 1953 දී ලබා ගන්නා ලදී.
විධිමත් ලෙස, ප්‍රසාද දීමනාව ලබා දුන්නේ වෙනත් දෙයකට ය. "විවාහ ස්ථායිතා ප්රමේයය" පිළිබඳ ඔහුගේ 1962 පත්‍රිකාව සඳහා: "විද්‍යාල ප්‍රවේශය සහ විවාහයේ ස්ථාවරත්වය."
තිරසාර විවාහයක් ගැන
ගැලපීම (ගැලපීම) - ලිපි හුවමාරුවක් සොයා ගැනීමේ කාර්යය.
එක්තරා හුදකලා ගමක් ඇත. "m" තරුණයන් සහ "w" ගැහැණු ළමයින් ඇත. අපි ඔවුන්ව එකිනෙකාට විවාහ කර දිය යුතුයි. (අවශ්‍යයෙන්ම එකම සංඛ්‍යාව නොවේ, සමහර විට අවසානයේ යමෙකු තනි වනු ඇත.)
ආකෘතියේ කළ යුතු උපකල්පන මොනවාද? අහඹු ලෙස නැවත විවාහ වීම පහසු නොවන බව. නිදහස් තේරීමක් සඳහා නිශ්චිත පියවරක් ගනු ලැබේ. ඔහුගේ මරණයෙන් පසු දික්කසාද වීම ආරම්භ නොවන පරිදි නැවත විවාහ වීමට කැමති නුවණැති අක්සකලාවක් සිටින බව කියමු. (දික්කසාදය යනු ස්වාමිපුරුෂයෙකුට තම භාර්යාවට වඩා තුන්වන පාර්ශ්වයේ කාන්තාවක් තම භාර්යාව වීමට අවශ්ය වූ විට ඇතිවන තත්වයකි.)
මෙම ප්රමේයය නූතන ආර්ථික විද්‍යාවේ ආත්මයයි. ඇය සුවිශේෂී අමානුෂිකයි. ආර්ථිකය සාම්ප්‍රදායිකව අමානුෂිකයි. ආර්ථික විද්‍යාවේදී මිනිසා වෙනුවට ලාභය උපරිම කර ගැනීමට යන්ත්‍රයක් ආදේශ කරයි. මම ඔබට කියන්නම් සදාචාරාත්මක දෘෂ්ටි කෝණයකින් සම්පූර්ණයෙන්ම පිස්සු දේවල්. එය හදවතට ගන්න එපා.
ආර්ථික විද්‍යාඥයන් විවාහය දෙස බලන්නේ මේ ආකාරයටය.
m1, m2,... mk - පිරිමි.
w1, w2,... wL - කාන්තාවන්.
ගැහැනු ළමයින්ට "ඇණවුම්" කරන ආකාරය සමඟ මිනිසෙකු හඳුනාගෙන ඇත. “ශුන්‍ය මට්ටම” ද ඇත, ඊට පහළින් කාන්තාවන්ට වෙනත් අය නොමැති වුවද භාර්යාවන් ලෙස ඉදිරිපත් කළ නොහැක.
සෑම දෙයක්ම දෙපැත්තටම සිදු වේ, ගැහැණු ළමයින්ට සමාන වේ.
ආරම්භක දත්ත අත්තනෝමතික ය. එකම උපකල්පනය/සීමාව නම් අපි අපේ මනාපයන් වෙනස් නොකිරීමයි.
ප්රමේයය: බෙදා හැරීම සහ ශුන්‍ය මට්ටම කුමක් වුවත්, සමහර පිරිමින් සහ සමහර කාන්තාවන් අතර එකින් එක ලිපි හුවමාරුවක් ඇති කර ගැනීමට සෑම විටම ක්‍රමයක් ඇත, එවිට එය සියලු වර්ගවල බෙදීම් වලට (දික්කසාද පමණක් නොව) ශක්තිමත් වේ.
විය හැකි තර්ජන මොනවාද?
විවාහ නොවූ යුවලක් (m,w) ඇත. නමුත් w සඳහා වත්මන් ස්වාමිපුරුෂයා m ට වඩා නරක ය, මට වත්මන් බිරිඳ w ට වඩා නරක ය. මෙය දරාගත නොහැකි තත්ත්වයකි.
"ශුන්‍යයට වඩා අඩු" කෙනෙකු සමඟ යමෙකු විවාහ වූ බවට විකල්පයක් ද ඇත; මෙම තත්වය තුළ, විවාහය ද බිඳ වැටෙනු ඇත.
කාන්තාවක් විවාහක නම්, නමුත් ඇය කැමති අවිවාහක පිරිමියෙකුට, ඇය සඳහා ඇය බිංදුවට වඩා ඉහළින් සිටී.
පුද්ගලයන් දෙදෙනෙකු දෙදෙනාම අවිවාහක නම්, සහ දෙදෙනාම එකිනෙකා සඳහා "ශුන්‍යයට වඩා" නම්.
ඕනෑම මූලික දත්තයක් සඳහා එවැනි විවාහ ක්‍රමයක් පවතින බව තර්ක කරනු ලැබේ, එය සියලු ආකාරයේ තර්ජන වලට ප්‍රතිරෝධී වේ. දෙවනුව, එවැනි සමතුලිතතාවයක් සොයා ගැනීම සඳහා ඇල්ගොරිතම ඉතා සරල ය. අපි M*N සමඟ සංසන්දනය කරමු.
මෙම ආකෘතිය සාමාන්‍යකරණය කර "බහු විවාහ" දක්වා ව්‍යාප්ත කරන ලද අතර බොහෝ ප්‍රදේශවලට අදාළ විය.
Gale-Shapley ක්රියා පටිපාටිය
සියලුම පිරිමින් සහ සියලුම කාන්තාවන් "බෙහෙත් වට්ටෝරු" අනුගමනය කරන්නේ නම්, එහි ප්රතිඵලය වන විවාහ ක්‍රමය තිරසාර වනු ඇත.
බෙහෙත් වට්ටෝරු.
අපි අවශ්ය පරිදි දින කිහිපයක් ගත කරමු. අපි සෑම දිනකම කොටස් දෙකකට බෙදන්නෙමු (උදෑසන සහ සවස).
පළමු දින උදෑසන සෑම පිරිමියෙක්ම තම හොඳම කාන්තාව වෙත ගොස් ජනේලයට තට්ටු කරමින් ඇයව විවාහ කර ගන්නා ලෙස ඉල්ලා සිටියි.
එදිනම සවස් වන විට, හැරීම කාන්තාවන් වෙත හැරේ, කාන්තාවක් සොයා ගත හැක්කේ කුමක්ද? ඇගේ ජනේලය යට සෙනඟක් සිටි බව, එක්කෝ පිරිමින් නැත. අද කිසිවෙක් නැති අය තම වාරය මඟ හැර බලා සිටිති. ඉතිරිය, අඩුම තරමින් එකක්වත් ඇති, ඔවුන් "ශුන්‍ය මට්ටමට වඩා ඉහළින්" සිටින බව බැලීමට පැමිණෙන පිරිමින් පරීක්ෂා කරති. අවම වශයෙන් එකක්වත් තිබීම. ඔබ සම්පූර්ණයෙන්ම අවාසනාවන්ත නම් සහ සෑම දෙයක්ම බිංදුවට වඩා අඩු නම්, එවිට සෑම කෙනෙකුම යැවිය යුතුය. ඒ ආපු අයගෙන් ලොකුම කෙනාව තෝරගන්න ගෑනු කෙනා එයාට ඉන්න කියලා ඉතුරු ටික යවනවා.
දෙවන දිනට පෙර, තත්වය මෙයයි: සමහර කාන්තාවන්ට එක් පිරිමියෙක් ඇත, සමහරුන්ට නැත.
දෙවන දිනයේදී, සියලුම "නිදහස්" (යවන ලද) පිරිමින් දෙවන ප්රමුඛතම කාන්තාව වෙත යාමට අවශ්ය වේ. එවැනි පුද්ගලයෙකු නොමැති නම්, මිනිසා තනිකඩ ලෙස ප්‍රකාශ කරනු ලැබේ. දැනටමත් කාන්තාවන් සමඟ වාඩි වී සිටින පිරිමින් තවමත් කිසිවක් කරන්නේ නැත.
සවස් වන විට කාන්තාවන් තත්වය දෙස බලයි. දැනටමත් වාඩි වී සිටි කෙනෙකුට ඉහළ ප්‍රමුඛතාවයකින් එකතු වූයේ නම්, පහළ ප්‍රමුඛතාවය ඉවතට යවනු ලැබේ. එන අය දැනට තියෙන ප්‍රමාණයට වඩා පහත් නම් හැමෝම යවනවා. කාන්තාවන් සෑම විටම උපරිම මූලද්රව්යය තෝරා ගනී.
අපි නැවත කියනවා.
එහි ප්‍රතිඵලයක් වශයෙන්, සෑම පිරිමියෙක්ම තම කාන්තාවන්ගේ සම්පූර්ණ ලැයිස්තුවට ගොස් තනිව හෝ යම් කාන්තාවක් සමඟ සම්බන්ධ විය. එහෙනම් අපි හැමෝම කසාද බඳිමු.
මෙම සම්පූර්ණ ක්රියාවලිය ක්‍රියාත්මක කළ හැකිද, නමුත් කාන්තාවන්ට පිරිමින් වෙත දිව යා හැකිද? ක්රියා පටිපාටිය සමමිතික වේ, නමුත් විසඳුම වෙනස් විය හැකිය. නමුත් ප්‍රශ්නය නම්, මෙයින් වඩා හොඳ කවුද?
ප්රමේයය. අපි මෙම සමමිතික විසඳුම් දෙක පමණක් නොව, සියලු ස්ථාවර විවාහ පද්ධති කට්ටලය සලකා බලමු. මුල් යෝජිත යාන්ත්‍රණය (පිරිමි දුවන සහ ස්ත්‍රීන් පිළිගන්න/ප්‍රතික්ෂේප කරන) විවාහ ක්‍රමයේ ප්රතිඵලය වන්නේ ඕනෑම පිරිමියෙකුට වෙනත් ඕනෑම පිරිමියෙකුට වඩා හොඳ සහ ඕනෑම කාන්තාවක් සඳහා වෙනත් ඕනෑම දෙයකට වඩා නරක ය.
සමලිංගික විවාහ
"සමලිංගික විවාහ" සමඟ තත්වය සලකා බලන්න. ඒවා නීත්‍යානුකූල කිරීමේ අවශ්‍යතාවය සැක කරන ගණිතමය ප්‍රතිඵලයක් සලකා බලමු. දෘෂ්ටිමය වශයෙන් වැරදි උදාහරණයක්.
a, b, c, d සමලිංගිකයන් හතරක් සලකා බලන්න.
a: bcd සඳහා ප්‍රමුඛතා
b:cad සඳහා ප්‍රමුඛතා
c: abd සඳහා ප්‍රමුඛතා
මන්ද ඔහු ඉතිරි තිදෙනා ශ්‍රේණිගත කරන්නේ කෙසේද යන්න ගැටළුවක් නොවේ.
ප්රකාශය: මෙම ක්‍රමය තුළ තිරසාර විවාහ ක්‍රමයක් නොමැත.
පුද්ගලයන් හතර දෙනෙකු සඳහා පද්ධති කීයක් තිබේද? තුන්. ab cd, ac bd, ad bc. ජෝඩු කඩා වැටෙනු ඇති අතර ක්රියාවලිය චක්ර ලෙස ගමන් කරනු ඇත.
"ත්‍රි-ලිංග" පද්ධති.
සමස්ත ගණිත ක්ෂේත්‍රයක් විවෘත කරන වැදගත්ම ප්‍රශ්නය මෙයයි. මෙය සිදු කළේ මොස්කව්හි මගේ සගයා වන ව්ලැඩිමීර් ඉවානොවිච් ඩැනිලොව් විසිනි. ඔහු "විවාහය" සැලකුවේ වොඩ්කා පානය කිරීමක් ලෙස වන අතර භූමිකාවන් පහත පරිදි විය: "වගා කරන තැනැත්තා", "ටෝස්ට් කතා කරන තැනැත්තා" සහ "සොසේජස් කපන තැනැත්තා". එක් එක් භූමිකාවේ නියෝජිතයින් 4 ක් හෝ වැඩි ගණනක් සිටින තත්වයක් තුළ, තිරිසන් බලයෙන් එය විසඳිය නොහැක. තිරසාර පද්ධතියක් පිළිබඳ ප්‍රශ්නය විවෘත එකකි.
ෂේප්ලි දෛශිකය
ගෘහ ගම්මානයේ ඔවුන් මාර්ගය තාර කිරීමට තීරණය කළහ. ඇතුල් කිරීමට අවශ්යයි. කෙසේද?
ෂේප්ලි 1953 දී මෙම ගැටලුවට විසඳුමක් යෝජනා කළේය. N={1,2...n} පිරිසක් සමඟ ගැටුම්කාරී තත්වයක් උපකල්පනය කරමු. වියදම්/ප්‍රතිලාභ බෙදාගත යුතුය. මිනිස්සු එකතුවෙලා ප්‍රයෝජනවත් දෙයක් කළා කියලා හිතමු, ඒක විකුණලා ලාභය බෙදන්නේ කොහොමද කියලා?
ෂේප්ලි යෝජනා කළේ බෙදීමේදී, මෙම පුද්ගලයින්ගේ ඇතැම් උප කුලකවලට කොපමණ ප්‍රමාණයක් ලැබිය හැකිද යන්න අප මෙහෙයවිය යුතු බවයි. සියලුම 2N හිස් නොවන උප කුලකවලට කොපමණ මුදලක් උපයා ගත හැකිද? මෙම තොරතුරු මත පදනම්ව, ෂේප්ලි විශ්වීය සූත්‍රයක් ලිවීය.
උදාහරණයක්. මොස්කව්හි භූගත මාර්ගයක ඒකල වාදකයෙක්, ගිටාර් වාදකයෙක් සහ බෙර වාදකයෙක් වාදනය කරයි. ඔවුන් තිදෙනා පැයකට රුබල් 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
දී ඇති සමාගමක් බිඳී තනිවම ක්රියා කළහොත් එයින් ලැබෙන ප්‍රතිලාභ මොනවාදැයි දැන ගන්නා තුරු සාධාරණ බෙදීමක් තීරණය කළ නොහැක. සහ අපි සංඛ්යා තීරණය කළ විට (සමූපකාර ක්රීඩාව ලාක්ෂණික ආකාරයෙන් සකසන්න).
Superadditivity යනු ඔවුන් වෙන වෙනම වඩා උපයන විට, එක්සත් වීම වඩා ලාභදායී වන විට, නමුත් ජයග්‍රහණ බෙදන්නේ කෙසේද යන්න පැහැදිලි නැත. මේ ගැන බොහෝ පිටපත් කැඩී ඇත.
ගේමක් තියෙනවා. ව්‍යාපාරිකයන් තිදෙනෙක් එකවර ඩොලර් මිලියනයක් වටිනා තැන්පතුවක් සොයා ගත්හ. තුන්දෙනාම එකග නම් කෝටියක් ඉන්නවා. ඕනෑම යුවළකට මරා දැමිය හැකිය (නඩුවෙන් ඉවත් කරන්න) සහ මුළු මිලියනයම තමන්ටම ලබා ගන්න. ඒ වගේම කාටවත් තනියම කිසිම දෙයක් කරන්න බැහැ. මෙය විසඳුමක් නොමැති භයානක සමුපකාර ක්‍රීඩාවකි. තුන්වැන්න ඉවත් කළ හැකි දෙදෙනෙක් සෑම විටම සිටිනු ඇත ... සමුපකාර ක්‍රීඩා න්‍යාය ආරම්භ වන්නේ විසඳුමක් නොමැති උදාහරණයකිනි.
අපට අවශ්ය වන්නේ පොදු විසඳුම අවහිර කිරීමට කිසිදු සන්ධානයකට අවශ්ය නොවන එවැනි විසඳුමක්. අවහිර කළ නොහැකි සියලුම බෙදීම් කට්ටලය කර්නලය වේ. හරය හිස් බව සිදු වේ. හැබැයි හිස් නොවුනත් බෙදන්නේ කොහොමද?
ෂේප්ලි මේ ආකාරයෙන් බෙදීමට යෝජනා කරයි. n සමඟ කාසියක් විසි කරන්න! දාර. අපි මෙම අනුපිළිවෙලෙහි සියලුම ක්රීඩකයන් ලියන්නෙමු. පළමු බෙර වාදකයා කියමු. එයා ඇවිත් එයාගේ 100 ගන්නවා. එතකොට "දෙවැනියා" එනවා, අපි කියමු ඒකල වාදකයා. (බෙර වාදකයා සමඟ එක්ව ඔවුන්ට 450 ක් උපයා ගත හැකිය, බෙර වාදකයා දැනටමත් 100 ක් ගෙන ඇත) ඒකල වාදකයා 350 ක් ගනී. ගිටාර් වාදකයා ඇතුළු වේ (එකට 1000, -450), 550 ක් ගනී. බොහෝ විට අන්තිමයා ජය ගනී. (Supermodularity)
අපි සියලුම ඇණවුම් සඳහා ලියන්නේ නම්:
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 දෛශිකයකි.
ෂේප්ලි ප්රමේයය (ආසන්න වශයෙන්) ඔප්පු කළේය: ක්‍රීඩා පන්තියක් ඇත (සුපිරි මොඩියුලර්), එහි විශාල කණ්ඩායමකට සම්බන්ධ වන ඊළඟ පුද්ගලයා එයට විශාල ජයග්‍රහණයක් ගෙන එයි. කර්නලය සැමවිටම හිස් නොවන අතර එය ලක්ෂ්‍යවල උත්තල සංයෝජනයකි (අපගේ නඩුවේදී, ලකුණු 6). Shapley දෛශිකය න්‍යෂ්ටියේ මධ්‍යයේ පිහිටා ඇත. එය සෑම විටම විසඳුමක් ලෙස ඉදිරිපත් කළ හැකිය, කිසිවෙකු එයට විරුද්ධ නොවනු ඇත.
1973 දී, කුටිවල ගැටලුව supermodular බව ඔප්පු විය.
සියලුම මිනිසුන් පළමු ගෘහයට යන මාර්ගය බෙදා ගනී. දෙවන දක්වා - n-1 පුද්ගලයින්. ආදිය.
ගුවන් තොටුපළට ධාවන පථයක් ඇත. විවිධ සමාගම්වලට විවිධ දිග අවශ්ය වේ. එකම ගැටළුවක් පැන නගී.
මම හිතන්නේ නොබෙල් ත්‍යාගය ප්‍රදානය කළ අයගේ මනසේ තිබුණේ මේ පින මිස ආන්තිකය පමණක් නොවේ.
ස්තුතියි!
තව පෙන්වන්න
- "ගණිතය - සරල" නාලිකාව:
- "මායිම් නොමැතිව Savvateev" නාලිකාව: edusex.ru, brainsex.ru, studfuck.ru
- පොදු "ගණිතය සරලයි":
- පොදු "ගණිතඥයින් විහිළු":
- වෙබ් අඩවිය, එහි සියලුම දේශන +100 පාඩම් සහ තවත්: savvateev.xyz
මූලාශ්රය: www.habr.com