Cara menikahi semua orang (pernikahan satu, dua, dan tiga jenis kelamin) dari sudut pandang matematika dan mengapa pria selalu menang

Pada 2012, Hadiah Nobel Ekonomi diberikan kepada Lloyd Shapley dan Alvin Roth. "Untuk teori distribusi stabil dan praktik pasar." Alexey Savvateev pada tahun 2012 mencoba menjelaskan secara sederhana dan jelas apa esensi dari manfaat matematika. Saya membawa perhatian Anda pada catatan video ceramah .


Hari ini akan menjadi kuliah teori. Tentang eksperimen Al Roth , khususnya dengan donasi, saya tidak akan berbicara.

Ketika diumumkan bahwa Lloyd Shapley (1923-2016) menerima Hadiah Nobel, ada pertanyaan standar: "Bagaimana!? Apa dia masih hidup!?!? ” Hasil yang paling terkenal diperoleh pada tahun 1953.

Secara formal, hadiah diberikan untuk yang lain. Untuk pekerjaan tahun 1962 untuk "teorema tentang pernikahan berkelanjutan": "Pendaftaran Perguruan Tinggi dan Stabilitas Perkawinan".

Tentang Pernikahan Berkelanjutan

Pencocokan adalah tugas menemukan kecocokan.

Ada desa terpencil tertentu. Ada anak-anak muda dan perempuan. Perlu untuk menikahi mereka satu sama lain. (Tidak harus jumlah yang sama, mungkin pada akhirnya seseorang akan dibiarkan sendiri.)

Prasyarat apa yang perlu Anda buat dalam model? Yang bukan hanya mengacak. Sebuah langkah sedang diambil menuju pilihan bebas. Misalkan ada aksakal yang bijak yang ingin menikah sehingga setelah kematiannya, perceraian tidak dimulai. (Perceraian adalah situasi di mana seorang suami menginginkan seorang wanita pihak ketiga untuk menikah lebih dari seorang istri.)

Teorema ini ada dalam semangat ekonomi modern. Dia sangat tidak manusiawi. Ekonomi secara tradisional tidak manusiawi. Dalam bidang ekonomi, seseorang digantikan oleh mobil untuk memaksimalkan keuntungan. Apa yang akan saya sampaikan adalah hal yang benar-benar gila dalam hal moralitas. Jangan mengambil hati.

Ekonom memandang pernikahan seperti itu.
m ₁ , m ₂ , ... m _k adalah laki-laki.
w ₁ , w ₂ , ... w _L - wanita.

Seorang pria diidentifikasi dengan bagaimana dia “memerintahkan” para gadis. Ada juga "level nol", di bawah ini wanita tidak boleh ditawari untuk menikah sama sekali, bahkan jika tidak ada yang lain.



Semuanya terjadi di kedua arah, para gadis memiliki hal yang sama.

Data awal bersifat arbitrer. Satu-satunya saran / batasan adalah bahwa kita tidak mengubah preferensi kita.

Teorema: Terlepas dari distribusi dan tingkat nol, selalu ada cara untuk membangun korespondensi satu-ke-satu antara bagian pria dan bagian wanita, sehingga akan stabil dalam kaitannya dengan segala jenis perpecahan (tidak hanya perceraian).

Ancaman apa yang bisa terjadi?

Ada pasangan (m, w) yang belum menikah. Tetapi untuk w, suami saat ini lebih buruk daripada m, dan untuk m, istri saat ini lebih buruk daripada w. Ini adalah situasi yang tidak stabil.

Ada pilihan lain, bahwa seseorang menikahi seseorang yang "di bawah nol", dalam situasi ini pernikahan juga akan putus.

Jika seorang wanita menikah, tetapi dia lebih suka wanita yang belum menikah, untuk siapa dia di atas nol.

Jika dua orang, keduanya belum menikah, dan keduanya "di atas nol" untuk satu sama lain.

Dikatakan bahwa untuk setiap data awal, sistem perkawinan semacam itu ada yang tahan terhadap semua jenis ancaman. Kedua, algoritma untuk menemukan keseimbangan seperti itu sangat sederhana. Sepadan dengan M * N.

Model ini digeneralisasikan dan diperluas ke “poligami” dan diterapkan di banyak daerah.

Prosedur Gale-Shapley

Jika semua pria dan wanita mematuhi "sila", maka sistem pernikahan yang dihasilkan akan stabil.

Resep.
Kami membutuhkan beberapa hari sesuai kebutuhan. Setiap hari kami membelah menjadi dua bagian (pagi dan sore).

Pada pagi pertama, setiap pria pergi ke wanita terbaiknya dan mengetuk jendela, mengundangnya untuk menikah dengannya.

Di malam hari di hari yang sama, pindah ke wanita Apa yang bisa wanita temukan? Bahwa di bawah jendela dia memiliki kerumunan, baik satu atau tidak satu pria. Mereka yang tidak memiliki siapa pun hari ini ketinggalan kursus, tunggu. Sisanya, yang memiliki setidaknya satu, periksa pria yang datang bahwa mereka "di atas nol." Untuk memiliki setidaknya satu. Jika Anda benar-benar sial dan semuanya di bawah nol, maka semua orang perlu dikirim. Wanita itu memilih maksimum dari mereka yang datang, menyuruhnya menunggu, dan mengirimkan sisanya.

Sebelum hari kedua, situasinya adalah ini: beberapa wanita memiliki satu pria, beberapa tidak memiliki satu pria.

Pada hari kedua, semua pria "bebas" (dikirim) harus pergi ke wanita prioritas kedua. Jika tidak ada, maka pria itu dinyatakan lajang. Pria-pria yang sudah duduk dengan wanita belum melakukan apa-apa.

Di malam hari, wanita melihat situasi. Jika orang yang sudah duduk bergabung dengan prioritas yang lebih tinggi, maka prioritas yang lebih rendah akan dikirim. Jika pengunjung lebih rendah dari yang ada, semua dikirim. Wanita setiap kali memilih elemen maksimal.

Kami ulangi

Akibatnya, masing-masing lelaki memeriksa seluruh daftar wanitanya dan tetap sendirian atau dibiaskan oleh beberapa wanita. Lalu kita akan menikahi semua orang.

Apakah mungkin untuk mengusir seluruh proses ini, tetapi agar wanita lari ke pria? Prosedurnya simetris, tetapi solusinya mungkin berbeda. Tetapi pertanyaannya adalah, siapa yang lebih baik dari ini?

Teorema Pertimbangkan bukan hanya dua solusi simetris ini, tetapi himpunan semua sistem pernikahan yang stabil. Mekanisme awal yang diusulkan (pria menjalankan dan wanita setuju / menolak) mengarah ke sistem perkawinan yang lebih baik untuk pria mana pun daripada yang lain dan lebih buruk daripada yang lain untuk wanita mana pun.

Perkawinan sesama jenis

Pertimbangkan situasi dengan pernikahan sesama jenis. Pertimbangkan hasil matematika yang menimbulkan keraguan akan perlunya melegalkannya. Contoh ideologis yang salah.

Pertimbangkan keempat homoseksual a, b, c, d.

prioritas untuk: bcd
prioritas untuk b: cad
prioritas untuk c: abd
untuk d, tidak masalah bagaimana peringkat tiga sisanya.

Pernyataan: tidak ada sistem pernikahan yang berkelanjutan dalam sistem ini.

Ada berapa sistem untuk empat orang? Tiga ab cd, ac bd, ad bc. Pasangan akan berantakan dan proses akan berulang.

Sistem "tiga jenis kelamin".
Ini adalah pertanyaan penting yang membuka seluruh bidang matematika. Ini dilakukan oleh rekan saya di Moskow, Vladimir Ivanovich Danilov. "Pernikahan" yang dilihatnya sebagai minum vodka dan perannya adalah: "menuangkan", "berbicara bersulang" dan "orang yang memotong sosis". Dalam situasi di mana ada 4 atau lebih perwakilan dari masing-masing peran, tidak mungkin untuk diselesaikan dengan kekerasan. Masalah sistem berkelanjutan terbuka.

Vektor Shapley

Di desa pondok, mereka memutuskan untuk membuka jalan. Perlu di-chip. Bagaimana?

Shapley pada tahun 1953 mengusulkan solusi untuk masalah ini. Misalkan situasi konflik dengan sekelompok orang N = {1,2 ... n}. Perlu berbagi biaya / manfaat. Misalkan orang telah melakukan sesuatu yang bermanfaat bersama, akankah mereka menjual dan bagaimana membagi keuntungan?

Shapley menyarankan berbagi ketika dibimbing oleh berapa banyak satu atau beberapa bagian dari orang-orang ini bisa dapatkan. Berapa banyak uang yang dapat dihasilkan oleh 2 subset nonempty. Dan berdasarkan informasi ini, Shapley menulis formula universal.

Sebuah contoh Solois, gitaris dan drummer bermain di underpass di Moskow. Ketiganya menghasilkan 1.000 rubel per jam. Bagaimana cara membagikannya? Anda bisa sama.
V (1,2,3) = 1000

Asumsikan itu
V (1,2) = 600
V (1.3) = 450
V (2,3) = 400
V (1) = 300
V (2) = 200
V (3) = 100

Tidak mungkin untuk menentukan pembagian yang adil sampai kita tahu kemenangan seperti apa yang menunggu perusahaan ini atau itu jika itu memutuskan dan bertindak secara independen. Dan ketika kami menentukan angka (kami meminta permainan kooperatif dalam bentuk karakteristik).

Superradditivity adalah ketika bersama-sama mereka menghasilkan lebih dari secara individual, ketika lebih menguntungkan untuk dipersatukan, tetapi tidak jelas bagaimana cara membagi keuntungan. Banyak salinan telah rusak tentang ini.

Ada sebuah game. Tiga pengusaha secara bersamaan menemukan deposit $ 1 juta. Jika mereka bertiga setuju, maka sejuta dari mereka. Pasangan mana pun dapat dunk (menghapus dari bisnis) dan mendapatkan seluruh juta. Dan tidak ada seorang pun yang bisa melakukan apa pun. Ini adalah permainan kooperatif yang menakutkan di mana tidak ada solusi. Akan selalu ada dua yang dapat menghilangkan yang ketiga ... Teori permainan kooperatif dimulai dengan contoh yang tidak memiliki solusi.

Tetapi kami menginginkan solusi seperti itu sehingga tidak ada koalisi yang ingin memblokir solusi bersama. Himpunan semua saham yang tidak dapat diblokir adalah intinya. Kebetulan intinya kosong. Tetapi bahkan jika itu tidak kosong, bagaimana cara berbagi?

Shapley menyarankan berbagi seperti itu. Lempar koin dengan n! segi. Dalam urutan ini, kami menulis semua pemain. Katakanlah drummer pertama. Dia masuk dan mengambil 100-nya. Kemudian datang "kedua", katakanlah, seorang solois. (Bersama dengan drummer, mereka dapat memperoleh 450, drummer telah mengambil 100). Sang solois mengambil 350. Gitaris masuk (bersama 1000, -450), membutuhkan 550. Orang terakhir yang masuk cukup sering mendapat kemenangan. (Supermodularitas)

Jika kami menulis untuk semua pesanan:
GSB - (win C) - (win G) - (win B)
GBS - (win C) - (win G) - (win B)
SBG - (win C) - (win G) - (win B)
BSG - (win C) - (win G) - (win B)
BGS - (win C) - (win G) - (win B)
GBS - (win C) - (win G) - (win B)

Dan untuk setiap kolom kita tambahkan dan bagi dengan 6 - rata-rata semua pesanan adalah vektor Shapley .

Shapley membuktikan teorema (kurang-lebih): Ada kelas permainan (supermodular) di mana orang berikutnya bergabung dengan tim besar - ia membawa kemenangan yang lebih besar. Kernel selalu tidak kosong dan merupakan kombinasi titik-titik cembung (dalam kasus kami, 6 poin). Vektor Shapley terletak di tengah-tengah inti. Itu selalu bisa ditawarkan sebagai solusi, tidak ada yang keberatan.

Pada tahun 1973, terbukti bahwa masalah dengan cottage bersifat supermodular.

Jalan menuju pondok pertama dibagikan oleh semua orang. Hingga yang kedua - n-1 orang. Dan sebagainya.

Bandara memiliki landasan pacu. Perusahaan yang berbeda membutuhkan panjang yang berbeda pula. Masalah yang sama muncul.

Saya pikir mereka yang mengeluarkan Hadiah Nobel ada dalam benaknya, dan bukan hanya tugas pernikahan.

Terima kasih