Prosedur Brams–Taylor

Prosedur Brams–Taylor (Templat:Lang-en 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.

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 $X$, dibagi dengan cara tanpa-rasa iri di antara semua mitra.
• Sisa kue, dikatakan $Y$, tetap tidak terbagi, tetapi -
• Satu pasangan, kata Alice, memiliki Keuntungan yang Tidak Dapat Dibatalkan (Irrevocable Advantage (IA)) atas pasangan lain, kata Bob, sehubungan dengan $Y$. Yang berarti, bagaimanapun caranya $Y$ dibagi, bahkan jika kita memberi $Y$ 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 $A,B,C$.
• Bob memotong bagian yang dia anggap terbesar (kata, $A$) untuk membuatnya sama dengan terbesar yang kedua; sebut saja hiasannya adalah $Y$ dan potongan yang dipotongnya ialah $A\setminus Y$.
• Charlie memilih sepotong dari $(A\setminus Y),B,C$; kemudian Bob memilih (dia wajib mengambil $(A\setminus Y)$ jika itu tersedia); dan yang terakhir mengambil ialah Alice.

Setelah tahapan memilih ini selesai, semua kue kecuali $Y$ dibagi dengan cara tanpa-rasa iri. Selain itu, Alice sekarang memiliki IA atas siapa pun yang mengambil $(A\setminus Y)$. Mengapa? karena Alice mengambil keduanya $B$ atau $C$, dan keduanya sama dengan $A$ menurut pendapatnya. Jadi, menurut pendapat Alice, siapa pun yang mengambil $(A\setminus Y)$ bisa juga memiliki $Y$ – 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.