Pada tahun 2012, Hadiah Nobel Ekonomi dianugerahkan kepada Lloyd Shapley dan Alvin Roth. "Untuk teori distribusi yang stabil dan praktik pengorganisasian pasar." Aleksey Savvateev pada tahun 2012 mencoba menjelaskan secara sederhana dan jelas esensi manfaat matematikawan. Saya sampaikan kepada Anda ringkasannya .
Hari ini akan ada kuliah teori. Tentang eksperimen , khususnya dengan donasi, saya tidak akan memberi tahu.
Ketika diumumkan bahwa menerima Hadiah Nobel, ada pertanyaan standar: “Bagaimana!? Apakah dia masih hidup!?!?” Hasil yang paling terkenal diperoleh pada tahun 1953.
Secara formal, bonus diberikan untuk hal lain. Untuk makalahnya tahun 1962 tentang “teorema stabilitas pernikahan”: “Penerimaan Perguruan Tinggi dan Stabilitas Pernikahan.”
Tentang pernikahan berkelanjutan
Sesuai (mencocokkan) - tugas menemukan korespondensi.
Ada sebuah desa terpencil. Ada “m” laki-laki muda dan “w” perempuan. Kita perlu menikahkan mereka satu sama lain. (Belum tentu angkanya sama, mungkin pada akhirnya akan ada yang tertinggal.)
Asumsi apa yang perlu dibuat dalam model? Bahwa tidak mudah untuk menikah lagi secara sembarangan. Sebuah langkah tertentu sedang diambil menuju pilihan bebas. Katakanlah ada seorang aksakal bijak yang ingin menikah lagi agar setelah kematiannya tidak terjadi perceraian. (Perceraian adalah situasi ketika seorang suami lebih menginginkan wanita pihak ketiga sebagai istrinya daripada istrinya.)
Teorema ini sesuai dengan semangat ilmu ekonomi modern. Dia sangat tidak manusiawi. Perekonomian secara tradisional tidak manusiawi. Dalam ilmu ekonomi, manusia digantikan oleh mesin untuk memaksimalkan keuntungan. Apa yang akan saya sampaikan kepada Anda adalah hal-hal yang benar-benar gila dari sudut pandang moral. Jangan dimasukkan ke dalam hati.
Para ekonom memandang pernikahan dengan cara ini.
m1, m2,… mk - laki-laki.
w1, w2,... wL - wanita.
Laki-laki diidentifikasikan dengan cara dia “memerintahkan” perempuan. Ada juga “tingkat nol”, di mana perempuan tidak dapat ditawari menjadi istri sama sekali, meskipun tidak ada orang lain.
Segala sesuatu terjadi dua arah, hal yang sama terjadi pada anak perempuan.
Data awal bersifat arbitrer. Satu-satunya asumsi/batasan adalah kita tidak mengubah preferensi kita.
Dalil: Terlepas dari distribusi dan tingkat nolnya, selalu ada cara untuk membangun korespondensi satu-satu antara beberapa laki-laki dan beberapa perempuan sehingga kuat terhadap semua jenis perpecahan (tidak hanya perceraian).
Ancaman apa saja yang mungkin terjadi?
Ada pasangan (m,w) yang belum menikah. Namun bagi w, suami saat ini lebih buruk dari m, dan bagi m istri saat ini lebih buruk dari w. Ini adalah situasi yang tidak berkelanjutan.
Ada juga pilihan seseorang menikah dengan seseorang yang “di bawah nol”, dalam situasi ini pernikahan juga akan berantakan.
Jika seorang wanita sudah menikah, tetapi dia lebih memilih pria yang belum menikah, yang nilainya di atas nol.
Jika dua orang sama-sama belum menikah, dan keduanya “di atas nol” satu sama lain.
Dikatakan bahwa untuk data awal apa pun ada sistem perkawinan yang tahan terhadap segala jenis ancaman. Kedua, algoritma untuk menemukan keseimbangan seperti itu sangat sederhana. Mari kita bandingkan dengan M*N.
Model ini digeneralisasikan dan diperluas ke “poligami” dan diterapkan di banyak bidang.
Prosedur Gale-Shapley
Jika semua laki-laki dan perempuan mengikuti “resep” tersebut, sistem perkawinan yang dihasilkan akan berkelanjutan.
Resep.
Kami mengambil waktu beberapa hari sesuai kebutuhan. Kami membagi setiap hari menjadi dua bagian (pagi dan sore).
Pada pagi pertama, setiap pria mendatangi wanita terbaiknya dan mengetuk jendela, memintanya untuk menikah dengannya.
Di malam hari yang sama, giliran para wanita. Apa yang bisa ditemukan seorang wanita? Bahwa ada kerumunan orang di bawah jendelanya, baik satu laki-laki atau tidak sama sekali. Mereka yang tidak memiliki siapa pun hari ini melewatkan gilirannya dan menunggu. Sisanya, yang memiliki setidaknya satu, memeriksa orang-orang yang datang untuk melihat bahwa mereka “di atas level nol.” Untuk memiliki setidaknya satu. Jika Anda benar-benar tidak beruntung dan semuanya di bawah nol, maka semua orang harus dikirim. Wanita itu memilih yang terbesar dari mereka yang datang, menyuruhnya menunggu, dan mengirimkan sisanya.
Sebelum hari kedua, situasinya seperti ini: sebagian perempuan mempunyai satu laki-laki, sebagian lagi tidak mempunyai laki-laki.
Pada hari kedua, semua pria “bebas” (dikirim) harus pergi ke wanita prioritas kedua. Jika tidak ada orang tersebut, maka pria tersebut dinyatakan lajang. Laki-laki yang sudah duduk bersama perempuan itu belum berbuat apa-apa.
Di malam hari, para wanita melihat situasi. Jika seseorang yang sudah duduk bergabung dengan prioritas yang lebih tinggi, maka prioritas yang lebih rendah akan diusir. Jika yang datang lebih rendah dari yang sudah tersedia, semua orang diusir. Wanita memilih elemen maksimal setiap saat.
Kami mengulangi.
Akibatnya, setiap pria memeriksa seluruh daftar wanitanya dan ditinggalkan sendirian atau bertunangan dengan wanita tertentu. Lalu kita akan menikahkan semua orang.
Apakah mungkin untuk menjalankan seluruh proses ini, tetapi perempuan harus lari ke laki-laki? Prosedurnya simetris, tetapi solusinya mungkin berbeda. Namun pertanyaannya, siapa yang lebih diuntungkan dari hal ini?
Dalil. Mari kita pertimbangkan tidak hanya dua solusi simetris ini, namun juga himpunan semua sistem perkawinan yang stabil. Mekanisme awal yang diusulkan (laki-laki mencalonkan diri dan perempuan menerima/menolak) menghasilkan sistem perkawinan yang lebih baik bagi laki-laki mana pun dibandingkan sistem apa pun dan lebih buruk daripada sistem apa pun bagi perempuan mana pun.
Pernikahan sesama jenis
Pertimbangkan situasi “pernikahan sesama jenis.” Mari kita perhatikan hasil matematis yang menimbulkan keraguan akan perlunya melegalkannya. Sebuah contoh yang salah secara ideologis.
Perhatikan empat homoseksual a, b, c, d.
prioritas untuk a: bcd
prioritas untuk b:cad
prioritas untuk c: abd
untuk d tidak peduli bagaimana dia memberi peringkat pada tiga sisanya.
Penyataan: Tidak ada sistem perkawinan berkelanjutan dalam sistem ini.
Berapa banyak sistem yang tersedia untuk empat orang? Tiga. ab cd, ac bd, iklan bc. Pasangan akan berantakan dan prosesnya akan berjalan dalam siklus.
Sistem "tiga gender".
Ini adalah pertanyaan paling penting yang membuka seluruh bidang matematika. Ini dilakukan oleh rekan saya di Moskow, Vladimir Ivanovich Danilov. Dia memandang “pernikahan” seperti meminum vodka dan perannya adalah sebagai berikut: “orang yang menuangkan”, “orang yang bersulang”, dan “orang yang memotong sosis”. Dalam situasi di mana terdapat 4 atau lebih perwakilan dari setiap peran, tidak mungkin diselesaikan dengan kekerasan. Pertanyaan mengenai sistem berkelanjutan merupakan pertanyaan terbuka.
vektor Shapley
Di desa pondok mereka memutuskan untuk mengaspal jalan. Perlu ikut serta. Bagaimana?
Shapley mengusulkan solusi untuk masalah ini pada tahun 1953. Misalkan terdapat situasi konflik dengan sekelompok orang N={1,2…n}. Biaya/manfaat perlu dibagi. Misalkan orang bersama-sama melakukan sesuatu yang bermanfaat, menjualnya dan bagaimana membagi keuntungannya?
Shapley menyarankan bahwa ketika membagi, kita harus dipandu oleh seberapa banyak bagian tertentu dari orang-orang ini dapat menerima. Berapa banyak uang yang dapat diperoleh dari 2N himpunan bagian yang tidak kosong? Dan berdasarkan informasi ini, Shapley menulis rumus universal.
Contoh. Seorang solois, gitaris, dan drummer bermain di lorong bawah tanah di Moskow. Ketiganya mendapat 1000 rubel per jam. Bagaimana cara membaginya? Mungkin sama.
V(1,2,3)=1000
Mari kita berpura-pura itu
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Pembagian yang adil tidak dapat ditentukan sampai kita mengetahui keuntungan apa yang menanti suatu perusahaan jika perusahaan tersebut memisahkan diri dan bertindak sendiri. Dan ketika kita menentukan angkanya (mengatur permainan kooperatif dalam bentuk yang khas).
Superadditivitas adalah ketika mereka menghasilkan lebih banyak bersama-sama daripada secara terpisah, ketika lebih menguntungkan untuk bersatu, tetapi tidak jelas bagaimana membagi kemenangan. Banyak salinan telah rusak mengenai hal ini.
Ada permainan. Tiga pengusaha secara bersamaan menemukan deposit senilai $1 juta. Kalau ketiganya setuju, maka jumlahnya sejuta. Pasangan mana pun dapat membunuh (menghapus dari kasus ini) dan mendapatkan satu juta penuh untuk diri mereka sendiri. Dan tidak ada seorang pun yang bisa melakukan apa pun sendirian. Ini adalah permainan co-op yang menakutkan tanpa solusi. Akan selalu ada dua orang yang bisa menghilangkan orang ketiga... Teori permainan kooperatif dimulai dengan sebuah contoh yang tidak memiliki solusi.
Kami menginginkan solusi sedemikian rupa sehingga tidak ada koalisi yang mau menghalangi solusi bersama. Himpunan semua divisi yang tidak dapat diblokir adalah kernel. Kebetulan intinya kosong. Tapi kalaupun tidak kosong, bagaimana cara membaginya?
Shapley menyarankan pembagian dengan cara ini. Melempar koin dengan n! tepian. Kami menulis semua pemain dalam urutan ini. Katakanlah drummer pertama. Dia masuk dan mengambil 100 miliknya. Lalu yang "kedua" masuk, katakanlah solois. (Bersama dengan drummer mereka bisa mendapatkan 450, drummer sudah mengambil 100) Solois mengambil 350. Gitaris masuk (bersama-sama 1000, -450), mengambil 550. Yang terakhir cukup sering menang. (Supermodularitas)
Jika kami menulis untuk semua pesanan:
GSB - (menang C) - (menang D) - (menang B)
SGB - (menang C) - (menang D) - (menang B)
SBG - (menang C) - (menang D) - (menang B)
BSG - (menang C) - (menang D) - (menang B)
BGS - (mendapatkan C) - (mendapatkan D) - (mendapatkan B)
GBS - (menang C) - (menang D) - (menang B)
Dan untuk setiap kolom kami menambahkan dan membagi dengan 6 - rata-rata untuk semua pesanan - ini adalah vektor Shapley.
Shapley membuktikan teorema (kira-kira): Ada kelas permainan (supermodular), di mana orang berikutnya yang bergabung dengan tim besar akan mendapatkan kemenangan yang lebih besar. Kernel selalu tidak kosong dan merupakan kombinasi titik-titik yang cembung (dalam kasus kami, 6 poin). Vektor Shapley terletak di pusat inti atom. Itu selalu bisa ditawarkan sebagai solusi, tidak ada yang menentangnya.
Pada tahun 1973, terbukti bahwa masalah cottage bersifat supermodular.
Semua n orang berbagi jalan menuju pondok pertama. Sampai yang kedua - n-1 orang. Dll.
Bandara ini memiliki landasan pacu. Perusahaan yang berbeda membutuhkan jangka waktu yang berbeda. Masalah yang sama pun muncul.
Saya pikir mereka yang memberikan Hadiah Nobel memikirkan hal ini, dan bukan hanya tugas margin.
Terima kasih!
Namun
- Saluran “Matematika - Sederhana”:
- Saluran “Savvateev tanpa batas”: edusex.ru, brainsex.ru, studfuck.ru
- Publik “Matematika itu sederhana”:
- “Lelucon Matematikawan” publik:
- Situs web, semua kuliah di sana +100 pelajaran dan lebih banyak lagi: savvateev.xyz
Sumber: www.habr.com