Prosedur Brams–Taylor

Prosedur Brams–Taylor ( 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.

 Sejarah 
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.More Equal than Others: Weighted Voting  Sol Garfunkel. For All Practical Purposes. COMAP. 1988

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

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

 Deskripsi 
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 
 Prosedur Brams–Taylor–Zwicker – sebuah prosedur pisau-bergerak untuk 4 mitra, yang menggunakan jumlah pemotongan terbatas.
 Pemotongan-kue tanpa-rasa iri – sebuah prosedur lama dan baru untuk masalah yang sama.

 Referensi 

Kategori:Protokol pembagian yang adil