Prosedur Brams–Taylor: Perbedaan antara revisi

Konten dihapus Konten ditambahkan

Sebaris

Revisi terkini sejak 7 Februari 2023 17.11

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]

Sejarah[sunting | sunting sumber]

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 $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[sunting | sunting sumber]

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[sunting | sunting sumber]

^ "Dividing the Spoils". Discover Magazine. 1995-03-01. Diarsipkan dari versi asli tanggal 20 Juli 2021. Diakses tanggal 20 Juli 2021.
^ More Equal than Others: Weighted Voting Diarsipkan 2019-12-05 di Wayback Machine. Sol Garfunkel. For All Practical Purposes. COMAP. 1988
^ 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.
^ 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]}

[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.

[patent5983205-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]}

[1]

[2]

[3]

[4]

@@ Baris 1: / Baris 1: @@
+{{Orphan|date=Februari 2023}}
-Prosedur Brams-Taylor ([[Bahasa Inggris|Inggris]]: ''Brams–Taylor procedure'' disingkat '''BTP''') adalah prosedur 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.<ref>{{cite web |url=http://m.discovermagazine.com/1995/mar/dividingthespoil479 |title=Dividing the Spoils |publisher=Discover Magazine |date=1995-03-01 |accessdate=20 Juli 2021|archive-url=https://web.archive.org/web/20120310190609/http://m.discovermagazine.com/1995/mar/dividingthespoil479 |archive-date=20 Juli 2021|url-status=dead }}</ref>
+'''Prosedur Brams–Taylor''' ({{lang-en|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.<ref>{{cite web |url=http://m.discovermagazine.com/1995/mar/dividingthespoil479 |title=Dividing the Spoils |publisher=Discover Magazine |date=1995-03-01 |accessdate=20 Juli 2021|archive-url=https://web.archive.org/web/20120310190609/http://m.discovermagazine.com/1995/mar/dividingthespoil479 |archive-date=20 Juli 2021|url-status=dead }}</ref>
+== 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.<ref>[http://www.comap.com/product/?idx=746 More Equal than Others: Weighted Voting] {{Webarchive|url=https://web.archive.org/web/20191205002720/http://www.comap.com/product/?idx=746 |date=2019-12-05 }} [[Sol Garfunkel]]. For All Practical Purposes. COMAP. 1988</ref>
+Prosedur BTP kemudian ditemukan oleh [[Steven Brams]] dan [[Alan D. Taylor]]. Prosedur ini pertama kali diterbitkan dalam edisi bulan Januari [[1995]]  [[American Mathematical Monthly]],<ref>{{Cite journal | doi = 10.2307/2974850| jstor = 2974850| title = An Envy-Free Cake Division Protocol| journal = The American Mathematical Monthly| volume = 102| pages = 9| year = 1995| last1 = Brams | first1 = S. J. | last2 = Taylor | first2 = A. D. }}</ref> dan pada tahun 1996 ditulis menjadi buku.
+Brams dan Taylor menjadi pemegang hak [[Hak paten|paten AS]] dari tahun 1999 terkait dengan prosedur BTP.<ref name="patent5983205">{{cite patent|country=US| number=5983205| status=patent| title=Computer-based method for the fair division of ownership of goods| gdate=1999-11-09| fdate=1999-04-05| invent1= Steven J. Brams|invent2=Alan D. Taylor |assign1=New York University |url = http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=%2Fnetahtml%2FPTO%2Fsearch-bool.html&r=1&f=G&l=50&co1=AND&d=PTXT&s1=5983205.PN.&OS=PN/5983205&RS=PN/5983205
+}}{{dead link|date=November 2016 |bot=InternetArchiveBot |fix-attempted=yes }}
+</ref>
+== Deskripsi ==
+Prosedur BTP membagi kue menjadi bagian demi bagian. Perantara khusus dari prosedur BTP ini adalah sebagai berikut:
+* Sebuah bagian dari kue, dikatakan <math>X</math>, dibagi dengan cara tanpa-rasa iri di antara semua mitra.
+* Sisa kue, dikatakan <math>Y</math>, tetap tidak terbagi, tetapi -
+* Satu pasangan, kata Alice, memiliki Keuntungan yang Tidak Dapat Dibatalkan (''Irrevocable Advantage'' (IA)) atas pasangan lain, kata Bob, sehubungan dengan <math>Y</math>. Yang berarti, bagaimanapun caranya <math>Y</math> dibagi, bahkan jika kita memberi <math>Y</math> 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 <math>A,B,C</math>.
+* Bob memotong bagian yang dia anggap terbesar (kata, <math>A</math>) untuk membuatnya sama dengan terbesar yang kedua; sebut saja hiasannya adalah <math>Y</math> dan potongan yang dipotongnya ialah <math>A\setminus Y</math>.
+* Charlie memilih sepotong dari <math>(A\setminus Y),B,C</math>; kemudian Bob memilih (dia wajib mengambil <math>(A\setminus Y)</math> jika itu tersedia); dan yang terakhir mengambil ialah Alice.
+Setelah tahapan memilih ini selesai, semua kue kecuali <math>Y</math> dibagi dengan cara tanpa-rasa iri. Selain itu, Alice sekarang memiliki IA atas siapa pun yang mengambil <math>(A\setminus Y)</math>. Mengapa? karena Alice mengambil keduanya <math>B</math> atau <math>C</math>, dan keduanya sama dengan <math>A</math> menurut pendapatnya. Jadi, menurut pendapat Alice, siapa pun yang mengambil <math>(A\setminus Y)</math> bisa juga memiliki <math>Y</math> – 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 ==