Lompat ke isi

Prosedur Brams–Taylor

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas


Prosedur Brams–Taylor (bahasa Inggris: Brams–Taylor procedure disingkat BTP) adalah prosedur matematika untuk Pemotongan-kue tanpa-rasa iri (Envy-free cake-cutting). Ini menjelaskan prosedur terbatas pertama untuk menghasilkan pembagian kue yang bebas iri di antara sejumlah bilangan bulat positif.[1]

Pada tahun 1988, sebelum ditemukannya prosedur BTP, Sol Garfunkel berpendapat bahwa masalah yang diselesaikan dengan teorema, yaitu pemotongan kue bebas iri n-person, adalah salah satu masalah terpenting dalam dunia matematika abad ke-20.[2]

Prosedur BTP kemudian ditemukan oleh Steven Brams dan Alan D. Taylor. Prosedur ini pertama kali diterbitkan dalam edisi bulan Januari 1995 American Mathematical Monthly,[3] dan pada tahun 1996 ditulis menjadi buku.

Brams dan Taylor menjadi pemegang hak paten AS dari tahun 1999 terkait dengan prosedur BTP.[4]

Deskripsi

[sunting | sunting sumber]

Prosedur BTP membagi kue menjadi bagian demi bagian. Perantara khusus dari prosedur BTP ini adalah sebagai berikut:

  • Sebuah bagian dari kue, dikatakan , dibagi dengan cara tanpa-rasa iri di antara semua mitra.
  • Sisa kue, dikatakan , tetap tidak terbagi, tetapi -
  • Satu pasangan, kata Alice, memiliki Keuntungan yang Tidak Dapat Dibatalkan (Irrevocable Advantage (IA)) atas pasangan lain, kata Bob, sehubungan dengan . Yang berarti, bagaimanapun caranya dibagi, bahkan jika kita memberi sepenuhnya untuk Bob, Alice masih tidak iri pada Bob.

Sebagai contoh bagaimana IA dapat dihasilkan, dengan mempertimbangkan tahapan pertama prosedur diskrit Selfridge–Conway (Selfridge–Conway discrete procedure), yakni:

  • Alice membagi kue menjadi 3 bagian yang dianggapnya sama; sebut saja bagian-bagiannya yakni .
  • Bob memotong bagian yang dia anggap terbesar (kata, ) untuk membuatnya sama dengan terbesar yang kedua; sebut saja hiasannya adalah dan potongan yang dipotongnya ialah .
  • Charlie memilih sepotong dari ; kemudian Bob memilih (dia wajib mengambil jika itu tersedia); dan yang terakhir mengambil ialah Alice.

Setelah tahapan memilih ini selesai, semua kue kecuali dibagi dengan cara tanpa-rasa iri. Selain itu, Alice sekarang memiliki IA atas siapa pun yang mengambil . Mengapa? karena Alice mengambil keduanya atau , dan keduanya sama dengan menurut pendapatnya. Jadi, menurut pendapat Alice, siapa pun yang mengambil bisa juga memiliki – hal ini tidak akan membuatnya iri.

Untuk memastikan apakah Alice mendapatkan IA dari pemain atau mitra tertentu (misalnya Bob), maka diperlukan prosedur yang jauh lebih rumit. Ini secara berurutan membagi kue menjadi potongan-potongan yang lebih kecil dan lebih kecil lagi, selalu memberi Alice sepotong yang dia hargai lebih dari milik Bob, sehingga IA dipertahankan. Ini mungkin membutuhkan waktu yang tidak terbatas – tergantung pada penilaian yang tepat menurut Alice dan juga Bob.

Lihat juga

[sunting | sunting sumber]

Referensi

[sunting | sunting sumber]
  1. ^ "Dividing the Spoils". Discover Magazine. 1995-03-01. Diarsipkan dari versi asli tanggal 20 Juli 2021. Diakses tanggal 20 Juli 2021. 
  2. ^ More Equal than Others: Weighted Voting Diarsipkan 2019-12-05 di Wayback Machine. Sol Garfunkel. For All Practical Purposes. COMAP. 1988
  3. ^ Brams, S. J.; Taylor, A. D. (1995). "An Envy-Free Cake Division Protocol". The American Mathematical Monthly. 102: 9. doi:10.2307/2974850. JSTOR 2974850. 
  4. ^ US patent 5983205, Steven J. Brams & Alan D. Taylor, "Computer-based method for the fair division of ownership of goods", dikeluarkan tanggal 1999-11-09, diberikan kepada New York University [pranala nonaktif permanen]