FairDivision

Dibuat Senin 09 November 2020

Saya memotong, Anda memilih

Metode “ Aku potong, kamu pilih ” untuk membagi sesuatu secara adil antara dua orang sudah terkenal. Diberikan beberapa sumber daya yang dapat dibagi, seperti pizza, dua orang dapat membagi sumber daya menggunakan protokol berikut:

  1. Satu orang dipilih secara acak untuk memotong pizza menjadi dua bagian.
  2. Orang yang tidak memotong mengambil sepotong.
  3. Orang yang memotong mengambil bagian yang tersisa.

Protokol ini mudah diingat dan dijelaskan. Ini juga efisien dalam arti bahwa jumlah potongan minimal – dua – dibuat.

Jika Anda belum pernah melakukannya sebelumnya, saya mendorong Anda untuk meluangkan waktu sejenak untuk mempertimbangkan bagaimana sumber daya dapat dibagi secara adil antara sejumlah orang, bukan hanya dua.

Saya sendiri memikirkan hal ini baru-baru ini ketika saya perlu membagi kue besar antara saya, istri saya, dan putri kami yang berusia 4 tahun. Saya minta diri untuk memikirkan tentang bagaimana melanjutkan. Saat aku kembali, kuenya sudah dimakan! Itu salah satu protokol yang saya tidak rekomendasikan.

Protokol Fink

Kemudian (dan setelah makan kue besar utuh tanpa memberitahu keluarga saya tentang hal itu) saya duduk untuk meneliti masalahnya. Saya berkonsultasi dengan teman saya Micha Niskin dan dia menyarankan teknik berikut yang dia buat, yang saya temukan kemudian dikenal sebagai protokol Fink:

  1. Jika ada dua orang, lakukan “I cut, you choose”.
  2. Jika ada tiga orang, dua dipilih secara acak. Dua orang yang dipilih secara acak melakukan “I cut, you choose”.
  3. Dua orang dengan potongan masing-masing memotong bagian mereka menjadi tiga.
  4. Orang ketiga yang belum memiliki bidak memilih satu bidak dari masing-masing bidak.
  5. Semua orang sekarang memiliki dua bagian masing-masing.
  6. Jika orang keempat bergabung, masing-masing dari ketiganya dengan potongan dipotong menjadi dua bagian.
  7. Orang keempat yang belum memiliki bidak memilih satu dari masing-masing tiga bidak.
  8. Semua orang sekarang memiliki tiga bagian masing-masing.
  9. …dan seterusnya.

Kelemahan terbesar dari protokol Fink adalah setiap orang mendapatkan n-1 buah, di mana n adalah jumlah orang, bukan satu buah ukuran 1 / n. Di sisi lain, seperti “I cut, you choose”, protokol ini mudah diingat, dan hampir semudah menjelaskannya, bahkan kepada anak-anak.

Sebenarnya ada banyak pendekatan terhadap masalah, semuanya dengan berbagai pengorbanan. Saya tidak menemukan satu pun dari mereka yang mudah diingat atau dijelaskan (terutama kepada anak-anak lapar ! ) sebagai Fink, tetapi jika Anda ingin melakukan penelitian sendiri, Pemotongan kue yang adil di Wikipedia adalah tempat saya memulai .

Read More

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments