როგორ შეიძლება ყველამ დაქორწინდეს (ერთ, ორ და სამსქესიან ქორწინება) მათემატიკური თვალსაზრისით და რატომ იმარჯვებენ კაცები ყოველთვის

2012 წელს ნობელის პრემია ეკონომიკაში მიენიჭათ ლოიდ შეპლის და ელვინ როტს. „სტაბილური განაწილების თეორიისა და ბაზრების ორგანიზების პრაქტიკისთვის“. ალექსეი სავვატეევი 2012 წელს ცდილობდა მარტივად და ნათლად აეხსნა მათემატიკოსთა დამსახურების არსი. თქვენს ყურადღებას წარმოგიდგენთ რეზიუმეს ვიდეო ლექციები.

დღეს ჩატარდება თეორიული ლექცია. ექსპერიმენტების შესახებ ელა როტა, კერძოდ შემოწირულობით, არ გეტყვით.

როცა გამოცხადდა რომ ლოიდ შეპლი (1923-2016) მიიღო ნობელის პრემია, იყო სტანდარტული კითხვა: „როგორ!? ის ჯერ კიდევ ცოცხალია?!?” მისი ყველაზე ცნობილი შედეგი 1953 წელს იქნა მიღებული.

ფორმალურად, პრემია სხვა რამეზე იყო მოცემული. მისი 1962 წლის ნაშრომისთვის "ქორწინების სტაბილურობის თეორემა": "კოლეჯში მიღება და ქორწინების სტაბილურობა".

მდგრადი ქორწინების შესახებ

შესაბამისი (შემთხვევა) - მიმოწერის პოვნის ამოცანა.

არის გარკვეული იზოლირებული სოფელი. არიან „მ“ ახალგაზრდები და „ვ“ გოგონები. ჩვენ უნდა გავთხოვოთ ისინი ერთმანეთზე. (აუცილებლად ერთი და იგივე რიცხვი არ არის, შესაძლოა ბოლოს ვინმე მარტო დარჩეს.)

რა დაშვებები უნდა გაკეთდეს მოდელში? რომ შემთხვევითი ხელახლა დაქორწინება ადვილი არ არის. გარკვეული ნაბიჯი გადაიდგმება თავისუფალი არჩევანისკენ. ვთქვათ, არის ბრძენი აქსაკალი, რომელსაც სურს ხელახლა გათხოვება, რათა მისი სიკვდილის შემდეგ განქორწინება არ დაიწყოს. (განქორწინება არის სიტუაცია, როდესაც ქმარს სურს მესამე მხარის ქალი, როგორც მისი ცოლი, ვიდრე მისი ცოლი.)

ეს თეორემა თანამედროვე ეკონომიკის სულისკვეთებაა. ის განსაკუთრებულად არაადამიანურია. ეკონომიკა ტრადიციულად არაადამიანური იყო. ეკონომიკაში ადამიანს ანაცვლებს მანქანა, რომ მაქსიმალურად გაზარდოს მოგება. რასაც გეტყვით, მორალური თვალსაზრისით აბსოლუტურად სიგიჟეა. გულთან არ მიიტანო.

ეკონომისტები ქორწინებას ასე უყურებენ.
m1, m2,… mk - კაცები.
w1, w2,... wL - ქალები.

მამაკაცი იდენტიფიცირებულია იმით, თუ როგორ "უბრძანებს" გოგოებს. ასევე არსებობს „ნულოვანი დონე“, რომლის ქვემოთაც ქალებს საერთოდ არ შეუძლიათ ცოლებად შეთავაზება, თუნდაც სხვები არ იყვნენ.

ყველაფერი ორივე მიმართულებით ხდება, გოგოებში იგივე.

საწყისი მონაცემები თვითნებურია. ერთადერთი დაშვება/შეზღუდვა არის ის, რომ ჩვენ არ ვცვლით ჩვენს პრეფერენციებს.

თეორემა: მიუხედავად განაწილებისა და ნულის დონისა, ყოველთვის არსებობს გზა, რომ დაამყაროს ერთი-ერთზე კორესპონდენცია ზოგიერთ მამაკაცსა და ზოგიერთ ქალს შორის, რათა ის მდგრადი იყოს ყველა სახის გაყოფისთვის (არა მხოლოდ განქორწინებისთვის).

რა საფრთხეები შეიძლება იყოს?

არის წყვილი (m,w), რომელიც არ არის დაქორწინებული. მაგრამ w-სთვის ამჟამინდელი ქმარი m-ზე უარესია, ხოლო m-ისთვის ამჟამინდელი ცოლი w-ზე უარესია. ეს არამდგრადი მდგომარეობაა.

ასევე არსებობს ვარიანტი, რომ ვინმე დაქორწინდა ვინმეზე, ვინც "ნულზე ქვემოთ" არის; ამ სიტუაციაში, ქორწინებაც დაიშლება.

თუ ქალი გათხოვილია, მაგრამ უპირატესობას ანიჭებს გაუთხოვარ მამაკაცს, რომლისთვისაც ის ნულზე მაღლა დგას.

თუ ორი ადამიანი ორივე გაუთხოვარია და ორივე ერთმანეთისთვის "ნულზე ზემოთ".

ამტკიცებენ, რომ ნებისმიერი საწყისი მონაცემებისთვის არსებობს ასეთი ქორწინების სისტემა, რომელიც მდგრადია ყველა სახის საფრთხის მიმართ. მეორეც, ასეთი წონასწორობის პოვნის ალგორითმი ძალიან მარტივია. შევადაროთ M*N-ს.

ეს მოდელი განზოგადდა და გაფართოვდა „პოლიგამიამდე“ და გამოიყენებოდა მრავალ სფეროში.

გეილ-შეპლის პროცედურა

თუ ყველა მამაკაცი და ყველა ქალი დაიცავს „რეცეპტებს“, შედეგად მიღებული ქორწინების სისტემა მდგრადი იქნება.

რეცეპტები.
საჭიროებისამებრ ვატარებთ რამდენიმე დღეს. ყოველ დღე ვყოფთ ორ ნაწილად (დილა და საღამო).

პირველ დილით ყველა მამაკაცი მიდის თავის მეჯვარე ქალთან და ფანჯარაზე აკაკუნებს და ცოლობას სთხოვს.

იმავე დღეს საღამოს მორიგეობა ქალებს უხვევს.რას აღმოაჩენს ქალმა? რომ მის ფანჯრის ქვეშ ხალხმრავლობა იყო, ერთი ან არცერთი კაცი. ვისაც დღეს არავინ ჰყავს, თავის რიგს გამოტოვებს და ელოდება. დანარჩენები, რომლებსაც ერთი მაინც ჰყავთ, ამოწმებენ იმ მამაკაცებს, რომლებიც მოდიან, რომ ნახონ, რომ ისინი "ნულზე ზემოთ არიან". ერთი მაინც რომ ჰქონდეს. თუ სრულიად უიღბლო ხარ და ყველაფერი ნულის ქვემოთაა, მაშინ ყველა უნდა გაიგზავნოს. ქალი მოსულთაგან ყველაზე დიდს ირჩევს, ეუბნება, დაელოდე და დანარჩენებს აგზავნის.

მეორე დღის წინ სიტუაცია ასეთია: ზოგ ქალს ერთი კაცი ჰყავს, ზოგს - არა.

მეორე დღეს ყველა „თავისუფალი“ (გაგზავნილი) მამაკაცი უნდა წავიდეს მეორე პრიორიტეტულ ქალთან. თუ ასეთი ადამიანი არ არის, მაშინ მამაკაცი გამოცხადებულია მარტოხელა. ის კაცები, რომლებიც უკვე ქალებთან სხედან, ჯერ არაფერს აკეთებენ.

საღამოს ქალები სიტუაციას უყურებენ. თუ ვინმეს, რომელიც უკვე იჯდა, შეუერთდა უფრო მაღალი პრიორიტეტი, მაშინ ქვედა პრიორიტეტი იგზავნება. თუ ისინი, ვინც მოდიან, უკვე ხელმისაწვდომზე დაბალია, ყველას აცილებენ. ქალები ყოველ ჯერზე ირჩევენ მაქსიმალურ ელემენტს.

ვიმეორებთ.

შედეგად, თითოეულმა კაცმა გაიარა თავისი ქალების მთელი სია და დარჩა ან მარტო ან რომელიმე ქალთან დაინიშნა. მერე ყველა დავქორწინდებით.

შესაძლებელია თუ არა მთელი ამ პროცესის გაშვება, მაგრამ ქალებმა კაცებთან გაიქცნენ? პროცედურა სიმეტრიულია, მაგრამ გამოსავალი შეიძლება განსხვავებული იყოს. მაგრამ საკითხავია, ვინ არის უკეთესი ამისგან?

თეორემა. განვიხილოთ არა მხოლოდ ეს ორი სიმეტრიული გადაწყვეტა, არამედ ყველა სტაბილური ქორწინების სისტემის ნაკრები. თავდაპირველი შემოთავაზებული მექანიზმი (მამაკაცები გარბიან და ქალები იღებენ/უარს) იძლევა ქორწინების სისტემას, რომელიც უკეთესია ნებისმიერი კაცისთვის, ვიდრე ნებისმიერი სხვა და უარესი, ვიდრე ნებისმიერი სხვა ნებისმიერი ქალისთვის.

ერთსქესიანთა ქორწინება

განვიხილოთ სიტუაცია „ერთსქესიანთა ქორწინებასთან“. განვიხილოთ მათემატიკური შედეგი, რომელიც ეჭვქვეშ აყენებს მათი ლეგალიზაციის აუცილებლობას. იდეოლოგიურად არასწორი მაგალითი.

განვიხილოთ ოთხი ჰომოსექსუალი a, b, c, d.

პრიორიტეტები a: bcd
პრიორიტეტები b:cad
პრიორიტეტები გ: აბდ
დ არ აქვს მნიშვნელობა როგორ ანაწილებს დარჩენილ სამს.

დამტკიცება: ამ სისტემაში არ არსებობს მდგრადი ქორწინების სისტემა.

რამდენი სისტემაა ოთხი ადამიანისთვის? სამი. 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

სამართლიანი დაყოფა არ შეიძლება განისაზღვროს მანამ, სანამ არ გვეცოდინება, რა მოგება ელის მოცემულ კომპანიას, თუ ის დაშორდება და იმოქმედებს დამოუკიდებლად. და როცა დავადგინეთ რიცხვები (დავაყენეთ კოოპერატიული თამაში დამახასიათებელი ფორმით).

სუპერდამატება არის მაშინ, როცა ერთად ისინი უფრო მეტს შოულობენ, ვიდრე ცალკე, როცა უფრო მომგებიანია გაერთიანება, მაგრამ გაუგებარია როგორ გაიყოს მოგება. ამის შესახებ ბევრი ასლი გატეხილია.

არის თამაში. სამმა ბიზნესმენმა ერთდროულად იპოვა 1 მილიონი დოლარის ანაბარი. თუ სამივე თანახმაა, მაშინ მილიონია. ნებისმიერ წყვილს შეუძლია მოკლას (მოხსნას საქმიდან) და მიიღოს მთელი მილიონი თავისთვის. და მარტო ვერავინ ვერაფერს გააკეთებს. ეს არის საშინელი კოოპერატიული თამაში გამოსავლის გარეშე. ყოველთვის იქნება ორი ადამიანი, ვისაც შეუძლია მესამეს აღმოფხვრა... კოოპერატიული თამაშების თეორია იწყება მაგალითით, რომელსაც გამოსავალი არ აქვს.

ჩვენ გვსურს ისეთი გამოსავალი, რომ არცერთ კოალიციას არ მოუნდეს საერთო გადაწყვეტის დაბლოკვა. ყველა განყოფილების ნაკრები, რომლის დაბლოკვა შეუძლებელია, არის ბირთვი. ეს ხდება, რომ ბირთვი ცარიელია. მაგრამ თუნდაც ცარიელი არ იყოს, როგორ გავყოთ?

შეპლი გვთავაზობს ამ გზით დაყოფას. ჩააგდე მონეტა 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-ზე - საშუალოდ ყველა შეკვეთაზე - ეს არის შაპლის ვექტორი.

შეპლიმ დაამტკიცა თეორემა (დაახლოებით): არის თამაშების კლასი (სუპერმოდულური), რომელშიც შემდეგი ადამიანი, რომელიც შეუერთდება დიდ გუნდს, მას უფრო დიდი გამარჯვება მოაქვს. ბირთვი ყოველთვის არ არის ცარიელი და არის წერტილების ამოზნექილი კომბინაცია (ჩვენს შემთხვევაში, 6 ქულა). შეპლის ვექტორი დევს ბირთვის ცენტრში. ის ყოველთვის შეიძლება შემოგთავაზოთ, როგორც გამოსავალი, წინააღმდეგი არავინ იქნება.

1973 წელს დადასტურდა, რომ კოტეჯების პრობლემა სუპერმოდულურია.

ყველა n ადამიანი იზიარებს გზას პირველი კოტეჯისკენ. მეორემდე - n-1 ადამიანი. და ა.შ.

აეროპორტს აქვს ასაფრენი ბილიკი. სხვადასხვა კომპანიას სჭირდება სხვადასხვა სიგრძე. იგივე პრობლემა ჩნდება.

მე ვფიქრობ, რომ მათ, ვინც ნობელის პრემიას მიანიჭეს, ეს დამსახურება ჰქონდათ მხედველობაში და არა მხოლოდ ზღვრული დავალება.

დიდი მადლობა!

Ещё

• არხი "მათემატიკა - მარტივი": youtube.com/punkmathematics
• არხი "Savvateev საზღვრების გარეშე": eduex.ru, brainsex.ru, studfuck.ru
• საჯარო "მათემატიკა მარტივია": vk.com/alexei_savvateev
• საჯარო "მათემატიკოსების ხუმრობა": vk.com/bsu_mmf_jokes
• საიტი, ყველა ლექცია იქ +100 გაკვეთილი და მეტი: savvateev.xyz

წყარო: www.habr.com