Brams–Taylor–Zwicker procedure

The Brams–Taylor–Zwicker procedure is a protocol for envy-free cake-cutting among 4 partners.[1]: 126–128 

The procedure uses a variation of Austin's procedure for two partners and general fractions. That procedure allows two partners to divide an entire cake to pieces, each of which is worth exactly for both of them.

The main procedure works as follows.

A. Use Austin's procedure with and partners #1 and #2. So we have 4 pieces that the first two partners believe to be of exactly identical value of 1/4.

B. Partner #3 trims one piece to create a two-way tie for the largest; the partners now choose pieces in reverse order (#4, #3, #2, #1). Either #4 or #3 must take the trimmed piece. This creates an envy-free division for the entire cake less the trimmings (This is similar to the Selfridge–Conway discrete procedure).

C. Now the trimmings are divided. Assume w.l.o.g. that #3 took the trimmed piece. We use Austin's procedure again with the trimmings and partners #4 and #1, to create 4 pieces each of which equals exactly 1/4 for both of them. Since partners #1 and #2 have an irrevocable advantage over whoever partner that took the trimmed piece, we can let #3 be the first to select a piece from the trimming, then #2, then #4 and #1.

Efficiency

The run-time of the procedure is, technically, infinite, since Austin's procedure involves two knives moving continuously, and this procedure cannot be discretized.

The number of cuts is bounded, though. Austin's procedure requires 2 cuts to divide a cake between 2 people with an exact value of 1/2; each of these pieces should be divided with 2 more cuts to generate the 4 pieces with exact value of 1/4. So in total, 6 cuts are needed for step A. A single cut is done in step B and 6 more cuts in step C, for a total of 13 cuts.

An advanced variant of the Brams–Taylor–Zwicker procedure uses only 11 cuts.[2]

References

  1. ^ Brams, Steven J.; Taylor, Alan D. (1996). Fair division: from cake-cutting to dispute resolution. Cambridge University Press. ISBN 0-521-55644-9.
  2. ^ Brams, Steven J.; Taylor, Alan D.; Zwicker, William S. (1997). "A Moving-Knife Solution to the Four-Person Envy-Free Cake Division". Proceedings of the American Mathematical Society. 125 (2): 547–554. CiteSeerX 10.1.1.104.3390. doi:10.1090/s0002-9939-97-03614-9. S2CID 17233874.

Read other articles:

Jonah Bobo

Jonah BoboBerkas:Jonah Bobo.JPGBobo, 2012LahirJonah BoboPekerjaanaktorTahun aktif2004-sekarang Jonah Bobo (lahir 24 Januari 1997) adalah aktor asal Amerika Serikat. Ia berperan sebagai Danny dalam film Zathura yang dirilis pada tahun 2005. Ia juga bermain dalam film Around the Bend dan 30 Rock. Filmografi Tahun Judul Peran Catatan 2004 The Best Thief in the World Sam Zaidman Around the Bend Zach Lair The Backyardigans Austin Lead voice onlyTelevision series 2005 Zathura Danny Lead role ...

 

CozyCot

CozyCot Pte. Ltd.JenisPerusahaan perseoranganDidirikan2001 (situs),2002 (perusahaan)KantorpusatGemmill Lane (dekat Club Street), Singapura[1]Wilayah operasiAsia Timur dan Asia Tenggara (khususnya Singapura)TokohkunciNicole YeeProdukCozyCot (situs dan surat kabar), berbagai acara langsungPendapatanLebih dari $1 juta[2]Karyawan18[3]Situs webhttp://www.cozycot.com/ CozyCot adalah situs jejaring sosial bagi para wanita dari Asia Timur dan Asia Tenggara (khususnya Singapura...

 

Taiyuan Satellite Launch Center

Launch site in China 38°50′57″N 111°36′29″E / 38.8491°N 111.608°E / 38.8491; 111.608 Taiyuan Satellite Launch CenterLong March 6 on Launch Pad 16LocationKelan, Xinzhou, ShanxiCoordinates38°50′56.71″N 111°36′30.59″E / 38.8490861°N 111.6084972°E / 38.8490861; 111.6084972Short nameTSLCOperatorCASCTotal launches121[a]Launch pad(s)Four (Three active and One Retired)Launch historyStatusActiveLC-7 launch historyStatusRet...

The Calculating Stars

2018 science fiction novel by Mary Robinette Kowal The Calculating Stars First editionAuthorMary Robinette KowalCountryUnited States of AmericaLanguageEnglishSeriesLady Astronaut UniverseGenreScience fictionPublisherTor BooksPublication dateJuly 3, 2018Pages432ISBN978-0-765378385Followed byThe Fated Sky  The Calculating Stars is a science fiction novel by American writer Mary Robinette Kowal. The book was published by Tor Books on July 3, 2018.[1] It is the first book in the...

 

سيادة الشعب

جزء من سلسلة مقالات حولالليبرالية التاريخ تاريخ الفكر الليبرالي مساهمات في النظرية الليبرالية تاريخ الليبرالية الكلاسيكية الأفكار ليبرالية سياسية ليبرالية اقتصادية حرية سياسية ديمقراطية رأسمالية تربية ديمقراطية فردانية اقتصاد عدم التدخل ديمقراطية ليبرالية الحياد ال...

 

COVID-19 pandemic in Africa

Ongoing COVID-19 viral pandemic in Africa COVID-19 pandemic in AfricaDiseaseCOVID-19Virus strainSARS-CoV-2LocationAfricaFirst outbreakWuhan, Hubei, ChinaArrival date14 February 2020(4 years, 1 month, 4 weeks and 1 day ago)Confirmed cases11,984,539 (as of 10 May)[1]Active cases562,295 (as of 10 May)[1]Recovered11,168,212 (as of 10 May)[1]Deaths254,032 (as of 10 May)[1]Territories58[1] Part of a series on theCOVID-19 pandemicScientific...

Ďumbier

Mountain in Slovakia ĎumbierĎumbierHighest pointElevation2,043 m (6,703 ft)Prominence1,143 mCoordinates48°56′11.4″N 19°38′25.3″E / 48.936500°N 19.640361°E / 48.936500; 19.640361GeographyĎumbierLocation in Slovakia LocationSlovakiaParent rangeLow TatraClimbingFirst ascent18th century[1]Easiest routeHike Ďumbier (2,043 m or 6,703 ft) is the highest mountain in the Low Tatra range, in central Slovakia. Despite the remains of med...

 

Basilika Santo Kalistus, Groenlo

Basilika Santo KalistusBasilika Minor Santo KalistusBelanda: Sint-Calixtusbasiliekcode: nl is deprecated Basilika Santo KalistusLokasiGroenloNegara BelandaDenominasiGereja Katolik RomaArsitekturStatusBasilika minorStatus fungsionalAktif Basilika Santo Kalistus (Belanda: Sint-Calixtusbasiliekcode: nl is deprecated ) adalah sebuah gereja basilika minor Katolik yang terletak di Groenlo, Belanda. Basilika ini ditetapkan statusnya pada 2014 dan didedikasikan kepada Santo Kalistus.[1] ...

 

The National (Abu Dhabi)

UAE newspaper The NationalFront page of The National on 27 June 2018TypeDaily newspaperFormatBroadsheetOwner(s)International Media Investments (IMI)Editor-in-chiefMina Al-OraibiDeputy editorDaniel GledhillManaging editorLaura KootStaff writersMore than 120Founded17 April 2008; 15 years ago (2008-04-17)Political alignmentPro-governmentLanguageEnglishHeadquartersAbu DhabiCirculationUnaudited[1]Websitethenationalnews.com The National is a UAE state-owned English-languag...

The Appeal (newspaper)

The AppealJune 13, 1885 front page of Western AppealTypeWeekly newspaperFormatBroadsheetFounder(s)Samuel E. HardyJohn T. BurgettFrederick Douglass ParkerPublisherParker Burgett & Hardy Publishing CompanyEditorFrederick Douglass ParkerJohn Quincy AdamsRoy WilkinsFoundedJune 5, 1885Political alignmentRepublicanLanguageEnglishCeased publication1923HeadquartersSt. Paul, MinnesotaISSN2163-7083OCLC number10153837 The Appeal (originally the Western Appeal) was a weekly newspaper published from 1...

 

Venkaiah Naidu

13th Vice president of India In this Telugu name, the surname is Muppavarapu. M. Venkaiah NaiduOfficial portrait, 201713th Vice President of IndiaIn office11 August 2017 – 11 August 2022[1]President Ram Nath Kovind Droupadi Murmu Prime MinisterNarendra ModiPreceded byMohammad Hamid AnsariSucceeded byJagdeep DhankharUnion Minister of Housing and Urban AffairsIn office6 July 2017 – 17 July 2017Prime MinisterNarendra ModiPreceded byGirija VyasSucceeded byNarendr...

 

Marvel vs. Capcom 3: Fate of Two Worlds

Marvel vs. Capcom 3: Fate of Two WorldsvideogiocoCapitan America contro RyuPiattaformaXbox 360, PlayStation 3 Data di pubblicazione 18 febbraio 2011 15 febbraio 2011 18 febbraio 2011 GenerePicchiaduro a incontri OrigineGiappone SviluppoCapcom, Eighting PubblicazioneCapcom Modalità di giocoGiocatore singolo, multigiocatore SupportoDVD-ROM, Blu-ray Disc Fascia di etàPEGI: 12 SerieMarvel vs. Capcom Preceduto daMarvel vs. Capcom 2: New Age of Heroes Seguito daUltimate Marvel vs. Ca...

Trusono

Trusono Ketua Yayasan Sosial Bhumyamca (Yasbhum)PetahanaMulai menjabat SekarangPendahuluMayor Jenderal TNI (Mar) (Purn.) I Wayan MendraPenggantiPetahanaKomandan Sesko TNIMasa jabatan23 Februari 2017 – 30 Oktober 2018PendahuluLetjen TNI Agus SutomoPenggantiLaksda TNI Deddy Muhibah PribadiKomandan Korps Marinir ke-21Masa jabatan15 Juni 2016 – 23 Februari 2017PendahuluMayjen TNI (Mar) Buyung LalanaPenggantiMayjen TNI (Mar) Bambang SuswantonoKomandan Lantamal III/Jak...

 

هولنشتاين-ستادل

هولنشتاين-ستادلمعلومات عامةالمكان هربرشتينغن[1] — منطقة ألب دانوب[1] البلد  ألمانيا الإحداثيات 48°32′57″N 10°10′21″E / 48.5493°N 10.1724°E / 48.5493; 10.1724 الجيولوجيا Lonetal-Flächenalb (de) تعديل - تعديل مصدري - تعديل ويكي بيانات 48°32′57.57″N 10°10′20.75″E / 48.5493250°N 10.1724306°Eþ...

 

Qanawat

For the Damascus municipality, see Qanawat (Damascus). For the Iranian town, see Qanavat. Canatha redirects here. For the genus of moths, see Canatha (moth). Village in as-Suwayda, SyriaQanawat قَنَوَاتVillageQanawatLocation in SyriaCoordinates: 32°45′20″N 36°37′00″E / 32.75556°N 36.61667°E / 32.75556; 36.61667Grid position301/240Country SyriaGovernorateas-SuwaydaDistrictas-SuwaydaSubdistrictas-SuwaydaElevation1,200 m (3,900 ft)P...

豪栄道豪太郎

豪栄道 豪太郎 場所入りする豪栄道基礎情報四股名 澤井 豪太郎→豪栄道 豪太郎本名 澤井 豪太郎愛称 ゴウタロウ、豪ちゃん、GAD[1][2]生年月日 (1986-04-06) 1986年4月6日（38歳）出身 大阪府寝屋川市身長 183cm体重 160kgBMI 47.26所属部屋 境川部屋得意技 右四つ・出し投げ・切り返し・外掛け・首投げ・右下手投げ成績現在の番付 引退最高位 東大関生涯戦歴 696勝493敗...

 

Eudicotyledoneae

  Eudicotiledóneas o tricolpadas Primaveras (Primula)TaxonomíaReino: PlantaeDivisión: Angiospermae(sin rango): MesangiospermaeClase: EudicotyledoneaeDoyle & Hotton 1991[1]​clados (órdenes) Ranunculales Sabiales Proteales Trochodendrales Buxales Gunneridae o eudicotas nucleares: Gunnerales Pentapetalae Berberidopsidales Dilleniales Caryophyllales Santalales Saxifragales Vitales Rósidas con unos 16 órdenes Astéridas con unos 10 órdenes Sinonimia Tricolpatae (Donoghue &...

 

NGC 2883

NGC 2883   الكوكبة بيت الإبرة[1]  رمز الفهرس NGC 2883 (الفهرس العام الجديد)IRAS 09232-3353 (IRAS)NGC 2883A (الفهرس العام الجديد)PGC 26713 (فهرس المجرات الرئيسية)ESO 372-24 (European Southern Observatory Catalog)MCG-06-21-005 (فهرس المجرات الموروفولوجي)HIPASS J0925-34 (HIPASS)AGC 26451 (Arecibo General Catalog)AM 0923-335 (A catalogue of southern peculiar galaxies and associa...

Oswald Chambers

Scottish baptist and evangelist Oswald ChambersChambers in 1906BornOswald Chambers(1874-07-24)24 July 1874Aberdeen, ScotlandDied15 November 1917(1917-11-15) (aged 43)Cairo, Sultanate of EgyptAlma materRoyal College of ArtUniversity of EdinburghOccupation(s)Christian minister and teacherSpouseGertrude Biddy Hobbs ChambersChildrenKathleen M. Chambers Oswald Chambers (24 July 1874 – 15 November 1917) was an early-twentieth-century Scottish Baptist evangelist and teacher ...

 

Daftar identitas eksponensiasi

Perbedaan grafik fungsi linear dan eksponen, yakni f ( x ) = 50 x {\displaystyle f(x)=50x} , f ( x ) = x 3 {\displaystyle f(x)=x^{3}} dan f ( x ) = 2 x {\displaystyle f(x)=2^{x}} . Masing-masing berwarna merah, biru, dan hijau. Identitas eksponen atau eksponensiasi adalah sifat-sifat metode efisien untuk mengkomputasi berbagai bentuk yang elusif. Mengingat kembali bahwa eksponen adalah perkalian berulang pada basis, atau darab basis dikali sebanyak n {\displaystyle n} [1], maka secara...