Apa yang akan terjadi jika tidak membagi kue dengan adil

Berlaku adil merupakan perkara yang sulit dilakukan, contohnya saja saat kita hendak memotong dan membagikan kue kepada orang lain, bagaimana cara kita membagikan kue dengan adil kepada mereka? sebagian besar mungkin akan membagikan kue tersebut dengan sama rata. Misalnya terdapat 4 orang, maka masing-masing orang mendapatkan 1/4 bagian, dan masing-masing orang mendapatkan jumlah yang sama. Namun pernahkah kita berpikir untuk mempertimbangkan apa yang benar-benar mereka inginkan? semisal orang pertama hanya menginginkan buah cherry yang ada di atas kue tersebut karena sedang dalam program diet. Orang kedua menginginkan 1/8 bagian kuenya saja. Orang ketiga dan keempat juga punya keinginan tersendiri. Bukankah membagikan kue dengan mempertimbangkan keinginan masing-masing orang akan menjadikan pembagian kue lebih adil? karena yang namanya adil itu bukan artinya harus sama rata, namun membagikan sesuatu sesuai kebutuhan masing-masing individu.

Masalah membagikan barang atau lainnya secara adil sudah dipelajari sejak lama, yakni sekitar tahun 1940 yang dilakukan oleh Hugo Steinhaus. Masalah pembagian yang adil ini bahkan sampai berkaitan dengan bidang matematika seperti Kombinatorika, Teori Graf, Teori Permainan, Topologi, dan Algoritma.

Di dalam masalah pembagian kue dengan adil, kita sepakati ada dua cara untuk menafsirkan kalimat ‘pembagian yang adil’. Pertama, pembagian yang proporsional (proportional division), yakni jika terdapat orang, maka setiap orang percaya bahwa masing-masing dari mereka mendapat bagian. Kedua, pembagian sehingga terbebas dari rasa iri (envy-free division), yakni jika tidak ada orang yang menginginkan kue milik orang lain. Terdapat beberapa metode untuk menghasilkan pembagian kue yang proporsional, dan pembagian kue sehingga tidak ada rasa iri pada setiap orang. Berikut saya bahas salah satunya.

Pembagian untuk 2 Orang; Metode Cut-and-Choose

Ada suatu metode namanya Cut-and-Choose Method, yakni metode dimana satu orang memotong kue ke dalam dua bagian (yang menurut dia sama besarnya), dan orang yang satunya lagi memilih kue mana yang ingin dia ambil. Nah ketika menggunakan metode Cut-and-Choose, kita akan menghasilkan pembagian yang proporsional, juga pembagian sehingga terbebas dari rasa iri. Kenapa demikian?

Misalkan dua orang yang akan mendapatkan kue tersebut adalah Udin dan Jessica. Udin bertugas memotong kue menjadi dua bagian yang menurutnya sama besar, dan Jessica memilih potongan kue yang dia inginkan. Ketika Udin memotong kue menjadi dua bagian yang menurutnya sama besar, dia percaya bahwa dirinya akan mendapat jatah kue 1/2 bagian, dan tidak akan menginginkan bagian kue yang telah diambil oleh Jessica. Sedangkan untuk Jessica, dia akan memilih bagian yang dia sukai karena dia orang pertama yang mengambil potongan kuenya, dia juga percaya bahwa dirinya akan mendapatkan 1/2 bagian dan tidak akan menginginkan potongan kue yang lain. Jadi pembagian kue untuk mereka dilakukan dengan adil.

Sekarang jika terdapat tiga orang, katakanlah Udin, Jessica, dan Alejandro, maka bagaimana caranya membagi kue dengan adil untuk mereka bertiga? Pembagian kue untuk tiga orang atau lebih, kita membutuhkan algoritma yang lain. Salah satunya adalah dengan Moving Knife Procedures yang akan saya bahas di dalam postingan selanjutnya. 🙂

Referensi:

Fair Division. Brilliant. Diakses 22 Januari 2018. [https://brilliant.org/wiki/fair-division/]

Saya akan mengatakan di muka bahwa saya tidak dapat memberikan jawaban yang baik untuk pertanyaan Anda (saya pikir Anda mungkin bisa mendapatkan makalah penelitian jika Anda bisa), tetapi saya pikir saya dapat membantu dengan mendefinisikan masalah secara formal dan menyatakan di mana beberapa kesulitan terletak.

Latar Belakang . Biarkan saya dengan jelas menyatakan model untuk memotong kue. Kami ingin membagi interval antara n pemain. Setiap pemain saya memiliki fungsi penilaian v i ( S ) di atas himpunan bagian S kue. Kami akan menganggap bahwa fungsi ini adalah ukuran probabilitas; itu nonnegatif dan aditif (untuk disjoint A , B ⊆ [ 0 , 1 ] , v i ( A ∪ B ) = v i ([0,1][0,1]nniivi(S)vi(S)SSA,B⊆[0,1]A,B⊆[0,1] ) dan v i ( [ 0 , 1 ] ) = 1 . Solusi untuk masalah ini adalahprotokolatau algoritma yang menanyakan pemain dan memberikan porsi interval. Perhatikan bahwa pemain dapat salah melaporkan / berbohong dalam menjawab pertanyaan.vi(A∪B)=vi(A)+vi(B)vi(A∪B)=vi(A)+vi(B)vi([0,1])=1vi([0,1])=1

Beberapa makalah akan memiliki batasan yang lebih spesifik; misal , fungsi penilaian bersifat kontinu, atau linear-demi-satu, atau konstan-demi-satu.

Biarkan potongan yang ditugaskan untuk para pemain menjadi . Kami sering menginginkan properti protokol berikut:{S1,…,Sn}{S1,…,Sn}

• proporsionalitas : Setiap pemain memiliki strategi yang menjamin dia menerima nilai setidaknya ( 1 / n ) v i ( [ 0 , 1 ] ) . (Dari i 's perspektif, s / ia mendapat 1 / n dari total nilai kue.)ii(1/n)vi([0,1])(1/n)vi([0,1])ii1/n1/n
• iri-freeness : Setiap pemain memiliki strategi yang menjamin bahwa untuk setiap pemain lain j . (Setiap pemain lebih memilih bagiannya sendiri daripada bagian pemain lain.)vi(Si)≥vi(Sj)vi(Si)≥vi(Sj)jj

Perhatikan bahwa iri-hati menunjukkan proporsionalitas.

Ada juga properti "operasional" yang mungkin kita inginkan, seperti memotong menjadi beberapa bagian, waktu menjalankan polinomial (atau memang komputabilitas / konstruktivitas sama sekali - kita tidak ingin menggunakan Aksioma Pilihan untuk memilih subset kue! ), dan seterusnya.

Pertanyaan spesifik untuk ditanyakan . Dua catatan. Pertama, setiap jawaban atas pertanyaan Anda akan menyelesaikan masalah umum: Mulailah dengan memberikan seluruh kue ke pemain , lalu biarkan pemain lain tiba online dan menerapkan protokol ini secara berulang. Jadi kita harus mengharapkan masalah ini lebih sulit daripada pengaturan pemotongan kue standar yang kita terapkan.11

Kedua, kami selalu dapat menyelesaikan masalah Anda dengan mengambil seluruh kue kembali dari semua orang dan menggunakan algoritma yang dikenal untuk mendistribusikannya kembali dari awal. Jadi pertanyaannya adalah apakah ada cara yang agak lebih elegan untuk melakukan ini. Saya pikir cara yang baik untuk menghitung ini adalah "kapan redistribusi membutuhkan lebih sedikit waktu atau lebih sedikit pemotongan daripada mulai dari awal; dan / atau kapan pemain bisa mendapatkan porsi signifikan dari irisan mereka saat ini?"

1. Misalkan kita memiliki alokasi kecemburuan bebas untuk pemain. Bagaimana kita mendistribusikan untuk menghasilkan alokasi iri bebas antara n + 1 pemain?nnn+1n+1

Saya kira ini sangat sulit. Alasannya adalah bahwa menemukan alokasi yang bebas iri, efisien, sudah merupakan masalah yang sulit. Sejauh yang saya tahu, protokol yang dikenal bisa membutuhkan jumlah pemotongan yang tidak terbatas pada kue dan sangat kompleks. (Lihat Brams dan Taylor, An Envy-Free Kue Divisi Protocol , 1995.) Jadi mungkin ada yang lebih baik daripada untuk mengambil seluruh kembali kue dari semua orang dan mendistribusikan ke agen menggunakan Brams-Taylor.n+1n+1

1. Misalkan kita memiliki alokasi proporsional untuk ; bagaimana kita mendistribusikan mendapat alokasi proporsional untuk n + 1 ?nnn+1n+1

Saya pikir ini masih sulit (walaupun lebih bisa dilakukan). Pertimbangkan kasus di mana setiap pemain menilai kue secara seragam dan setiap pemain memiliki potongan berukuran . Maka apa pun yang dilakukan pemain baru akan membutuhkan perombakan di antara semua orang. Berikut ini kasus buruk lainnya: Misalkan pemain 1 memiliki penilaian tepat 1 / n untuk slice-nya, tetapi menilai slice pemain 2 di ( n - 1 ) / n . Misalkan pemain 2 menilai irisannya sendiri tepat 1 / n , tetapi menghargai irisan pemain 3 di ( n1/n1/n111/n1/n22(n−1)/n(n−1)/n221/n1/n33 , dan seterusnya, dengan pemain n menilai irisannya sendiri pada 1 / n danirispemain 1 di ( n - 1 ) / n . Sekarang pemain baru tiba. Tidak peduli apa yang diinginkan pemain baru, protokol Anda pada akhirnya harus merombak sesuatu dari pemain 2 ke pemain 1 , dari pemain 3 ke pemain 2 , dll.(n−1)/n(n−1)/nnn1/n1/n11(n−1)/n(n−1)/n22113322

Salah satu referensi mungkin Walsh, Online Cake Cutting , dalam Algorithmic Decision Theory 2011 (pdf link). Tapi saya pikir kertas mengasumsikan kita tahu di muka jumlah agen yang tiba, dan mengasumsikan pemain harus dialokasikan sepotong tepat ketika mereka pergi (yang sebelum akhir protokol), jadi itu benar-benar tidak berlaku untuk masalah Anda.

nnn+1n+1n+1n+1nn