การแบ่งเค้กอย่างซื่อสัตย์คือการศึกษาเกี่ยวกับอัลกอริทึมสำหรับการแบ่งเค้กอย่างยุติธรรมซึ่งเป็นกลไกที่ซื่อสัตย์ ด้วย กล่าวคือ กระตุ้นให้ผู้เข้าร่วมเปิดเผยการประเมินมูลค่าที่แท้จริงของตนต่อส่วนต่างๆ ของเค้ก

วิธี การแบ่งและเลือกแบบดั้งเดิมสำหรับการตัดเค้กนั้นไม่ถูกต้องเสมอไป: หากคนตัดรู้ความชอบของผู้เลือก พวกเขาสามารถได้มากกว่าครึ่งหนึ่งโดยการวางแผนอย่างมีกลยุทธ์ ตัวอย่างเช่น สมมติว่าคนตัดให้คุณค่ากับชิ้นเค้กตามขนาด ในขณะที่ผู้เลือกให้คุณค่ากับชิ้นเค้กตามปริมาณช็อกโกแลต ดังนั้นคนตัดสามารถตัดเค้กออกเป็นสองชิ้นที่มีปริมาณช็อกโกแลตเกือบเท่ากัน โดยที่ชิ้นเล็กกว่ามีช็อกโกแลตมากกว่าเล็กน้อย จากนั้นผู้เลือกจะเลือกชิ้นเล็กกว่า และคนตัดจะได้ชิ้นใหญ่กว่า ซึ่งอาจมีมูลค่ามากกว่าครึ่งหนึ่ง (ขึ้นอยู่กับการกระจายตัวของช็อกโกแลต)

มีกลไกการแบ่งเค้ก อย่างยุติธรรมแบบสุ่มและเรียบง่ายอยู่แล้ว คือ เลือกตัวแทนเพียงคนเดียวแบบสุ่มอย่างสม่ำเสมอ และมอบเค้กทั้งหมดให้เขา/เธอ กลไกนี้เรียบง่ายและซื่อสัตย์เพราะไม่ถามคำถามใดๆ ยิ่งไปกว่านั้น มันยังยุติธรรมในแง่ของค่าคาดหวัง กล่าวคือ ค่าคาดหวังของแต่ละคนเท่ากับ 1/ nพอดี อย่างไรก็ตาม การจัดสรรที่ได้นั้นไม่ยุติธรรม ความท้าทายคือการพัฒนากลไกที่ซื่อสัตย์และยุติธรรมในภายหลัง ไม่ใช่แค่ก่อนล่วงหน้าเท่านั้น มีกลไกดังกล่าวหลายกลไกที่ได้รับการพัฒนาขึ้นแล้ว

การแบ่งอย่างแม่นยำ (หรือที่เรียกว่าการแบ่งตามฉันทามติ ) คือการแบ่งเค้กออกเป็นnชิ้น โดยที่ตัวแทนแต่ละคนให้คุณค่าแต่ละชิ้นเท่ากับ 1/ n พอดี การมีอยู่ของการแบ่งเช่นนี้เป็นผลลัพธ์ที่ได้จากทฤษฎีบทความนูนของดูบินส์-สแปเนียร์ยิ่งไปกว่านั้น ยังมีการแบ่งเช่นนี้ที่มีการตัดไม่เกินซึ่งเป็นผลลัพธ์ที่ได้จากทฤษฎีบทสตรอมควิสต์-วูดอลและทฤษฎีบท การแบ่งสร้อยคอ${\displaystyle n(n-1)^{2}}$

โดยทั่วไปแล้ว ไม่สามารถหาการหารที่แน่นอนได้ด้วยอัลกอริทึมแบบจำกัด อย่างไรก็ตาม สามารถพบได้ในบางกรณีพิเศษ เช่น เมื่อตัวแทนทั้งหมดมีการประเมินค่าแบบเชิงเส้นเป็นช่วงๆ สมมติว่าเรามีอัลกอริทึมที่ไม่ซื่อสัตย์ (หรือออราเคิล) สำหรับการหาการหารที่แน่นอน สามารถใช้เพื่อสร้าง กลไก แบบสุ่มที่ซื่อสัตย์ตามความคาดหวังได้^{[ 1 ] [ 2 ]}กลไกแบบสุ่มเป็นกลไกการเปิดเผยโดยตรง - เริ่มต้นด้วยการขอให้ตัวแทนทั้งหมดเปิดเผยการวัดค่าทั้งหมดของตน:

1. ขอให้ตัวแทนรายงานค่าที่วัดได้
2. ใช้อัลกอริทึม/ออราเคิลที่มีอยู่เพื่อสร้างการหารที่แม่นยำ
3. ทำการสุ่มสลับตำแหน่งส่วนแบ่งที่ได้จากการตกลงร่วมกัน และมอบส่วนแบ่งนั้นให้แก่หุ้นส่วนแต่ละฝ่าย

ในที่นี้ ค่าที่คาดหวังของตัวแทนแต่ละคนจะเท่ากับ 1/ n เสมอ โดยไม่ขึ้นอยู่กับฟังก์ชันค่าที่รายงาน ดังนั้น กลไกนี้จึงมีความซื่อสัตย์ – ไม่มีตัวแทนใดได้ประโยชน์จากการโกหก ยิ่งไปกว่านั้น คู่ค้าที่ซื่อสัตย์จะได้รับการรับประกันว่ามีค่าเท่ากับ 1/ n อย่างแน่นอน ด้วยความน่าจะเป็น 1 (ไม่เฉพาะในค่าที่คาดหวังเท่านั้น) ดังนั้น คู่ค้าจึงมีแรงจูงใจที่จะเปิดเผยฟังก์ชันค่าที่แท้จริงของตน

การแบ่งแบบเกินสัดส่วนคือการแบ่งเค้กที่แต่ละคนได้รับมากกว่า 1/ n อย่างชัดเจน ตามการประเมินค่าของตนเอง การแบ่งแบบนี้จะเกิดขึ้นได้ก็ต่อเมื่อมีอย่างน้อยสองคนที่ประเมินค่าของเค้กอย่างน้อยหนึ่งชิ้นแตกต่างกัน กลไก เชิงกำหนด ใดๆ ที่ให้ผลลัพธ์เป็นการแบ่งแบบสัดส่วนเสมอ และให้ผลลัพธ์เป็นการแบ่งแบบเกินสัดส่วนเสมอเมื่อเกิดขึ้น ย่อมไม่สามารถเป็นกลไกที่เที่ยงตรงได้

Mossel และ Tamuz นำเสนอกลไก การสุ่มแบบสัดส่วนเกินที่เป็นจริงตามความคาดหวัง: ^{[ 1 ]}

1. เลือกกลุ่มย่อยหนึ่งกลุ่มจากชุดข้อมูลD ที่กำหนด ไว้
2. ขอให้ตัวแทนแต่ละคนประเมินผลงานของตนเอง
3. ถ้าค่าประเมินทั้งnค่ามากกว่า 1/ nให้ดำเนินการจัดสรรและสิ้นสุดกระบวนการ
4. หรืออีกวิธีหนึ่ง ให้ใช้วิธีการหารที่ตรงกันทุกประการ

ในขั้นตอนที่ 1 ควรเลือก การแจกแจงDในลักษณะที่ว่า ไม่ว่าการประเมินค่าของตัวแทนจะเป็นอย่างไร ก็ยังมีความน่าจะเป็นเป็นบวกที่จะเลือกการแบ่งแบบเกินสัดส่วน หากมีอยู่จริง จากนั้น ในขั้นตอนที่ 2 ควรให้ตัวแทนแต่ละคนรายงานค่าที่แท้จริง การรายงานค่าที่ต่ำกว่าจะไม่มีผลใดๆ หรืออาจทำให้ค่าของตัวแทนลดลงจากเกินสัดส่วนไปเป็นเพียงสัดส่วน (ในขั้นตอนที่ 4) การรายงานค่าที่สูงกว่าจะไม่มีผลใดๆ หรืออาจทำให้ค่าของตัวแทนลดลงจากสัดส่วนไปน้อยกว่า 1/ n (ในขั้นตอนที่ 3)

สมมติว่าแทนที่จะเปิดเผยการประเมินค่าของตนโดยตรง ตัวแทนจะเปิดเผยการประเมินค่าของตนโดยอ้อมผ่านการตอบ คำถามเกี่ยวกับ คะแนนและการประเมิน (เช่นเดียวกับในแบบจำลองของโรเบิร์ตสัน-เว็บ)

Branzei และ Miltersen ^{[ 3 ]}แสดงให้เห็นว่ากลไกการหารที่แม่นยำสามารถ "แยกส่วน" และดำเนินการในแบบจำลองการสอบถามได้ ซึ่งส่งผลให้สำหรับค่าใดๆ ก็ตามโปรโตคอล แบบ สุ่มตามการสอบถามจะถามคำถามไม่เกินหนึ่งครั้งมีความถูกต้องตามความคาดหวัง และจัดสรรค่าให้กับตัวแทนแต่ละรายระหว่างและโดยการประเมินค่าของตัวแทนทั้งหมด ${\displaystyle \epsilon >0}$${\displaystyle O(n^{2}/\epsilon )}$${\displaystyle 1/n-\epsilon }$${\displaystyle 1/n+\epsilon }$

ในทางกลับกัน พวกเขาพิสูจน์ว่า ใน โปรโตคอลการสอบถามความจริงแบบ กำหนดได้ ใดๆ หากตัวแทนทั้งหมดให้คุณค่ากับทุกส่วนของเค้กในเชิงบวก อย่างน้อยที่สุดก็จะมีตัวแทนหนึ่งคนที่ได้รับชิ้นส่วนที่ว่างเปล่า ซึ่งหมายความว่า หากมีตัวแทนเพียงสองคน อย่างน้อยที่สุดก็จะมีตัวแทนหนึ่งคนที่เป็น "เผด็จการ" และได้รับเค้กทั้งหมด เห็นได้ชัดว่ากลไกใดๆ ก็ตามไม่สามารถปราศจากความอิจฉาได้

สมมติว่าตัวแทนทั้งหมดมีการประเมินค่าคงที่แบบเป็นช่วงๆซึ่งหมายความว่าสำหรับตัวแทนแต่ละคน เค้กจะถูกแบ่งออกเป็นเซตย่อยจำนวนจำกัด และความหนาแน่นของค่าของตัวแทนในแต่ละเซตย่อยจะคงที่ สำหรับกรณีนี้Aziz และ Yeนำเสนออัลกอริทึมแบบสุ่มที่มีประสิทธิภาพทางเศรษฐกิจมากกว่า: Constrained Serial Dictatorshipนั้นมีความจริงใจในความคาดหวัง เป็นสัดส่วนที่แข็งแกร่ง และเป็นไปตามคุณสมบัติที่เรียกว่าเอกฉันท์ : หากความยาว 1/ nของเค้กที่ตัวแทนแต่ละคนชื่นชอบมากที่สุดไม่ทับซ้อนกับตัวแทนอื่นๆ ตัวแทนแต่ละคนจะได้รับความยาว 1/ nของเค้กที่ตนชื่นชอบมากที่สุด นี่เป็นรูปแบบประสิทธิภาพที่อ่อนแอซึ่งไม่เป็นไปตามกลไกที่อิงกับการแบ่งที่แน่นอน เมื่อมีตัวแทนเพียงสองคน ก็ยังใช้เวลาพหุนามและปราศจากความอิจฉาที่แข็งแกร่ง^{[ 4 ]}

สำหรับ กลไก เชิงกำหนดผลลัพธ์ส่วนใหญ่จะเป็นลบ แม้ว่าตัวแทนทั้งหมดจะมีค่าประเมินคงที่แบบเป็นช่วงก็ตาม

Kurokawa, Lai และ Procacciaพิสูจน์ว่าไม่มีกลไกที่แน่นอน ถูกต้อง และปราศจากความอิจฉาที่ต้องการการสอบถาม Robertson-Webb จำนวนจำกัด^{[ 5 ]}

Aziz และ Yeพิสูจน์ว่าไม่มีกลไกความจริงเชิงกำหนดที่ตรงตามคุณสมบัติใดคุณสมบัติหนึ่งต่อไปนี้: ^{[ 4 ]}

• เป็นไปตามสัดส่วนและเหมาะสมที่สุดตามหลักพาเรโต
• แข็งแกร่ง สมดุล และไม่สิ้นเปลือง ("ไม่สิ้นเปลือง" หมายความว่าไม่มีชิ้นส่วนใดถูกจัดสรรให้กับตัวแทนที่ไม่ต้องการ ซึ่งอ่อนกว่าหลักการ Pareto-optimality)

เมนอนและลาร์สันนำเสนอแนวคิดเรื่องความจริง εซึ่งหมายความว่าไม่มีตัวแทนใดได้รับผลประโยชน์มากกว่าเศษส่วนεจากการรายงานที่ผิดพลาด โดยที่εเป็นค่าคงที่บวกที่ไม่ขึ้นกับการประเมินค่าของตัวแทน พวกเขาพิสูจน์ว่าไม่มีกลไกเชิงกำหนดใดที่ตรงตามคุณสมบัติข้อใดข้อหนึ่งต่อไปนี้: ^{[ 6 ]}

• ε -เที่ยงตรง สัดส่วนโดยประมาณ และไม่สิ้นเปลือง (สำหรับค่าคงที่โดยประมาณไม่เกิน 1/ n )
• เที่ยงตรง เป็นสัดส่วนโดยประมาณ และเชื่อมโยงกัน (โดยค่าประมาณจะคงที่อย่างมากที่สุด 1/ n )

พวกเขาเสนอการปรับเปลี่ยนเล็กน้อยในโปรโตคอล Even–Pazและพิสูจน์ว่าโปรโตคอลนี้เป็นจริงแบบ ε โดยที่ ε = 1 - 3/(2 n ) เมื่อnเป็นจำนวนคู่ และ ε = 1 - 3/(2 n ) + 1/ n ²เมื่อnเป็นจำนวนคี่

Bei, Chen, Huzhang, Tao และ Wuพิสูจน์ว่าไม่มีกลไกที่แน่นอน ซื่อสัตย์ และปราศจากความอิจฉา แม้แต่ในแบบจำลองการเปิดเผยโดยตรง ที่ตรงตามคุณสมบัติเพิ่มเติมข้อใดข้อหนึ่งต่อไปนี้: ^{[ 7 ]}

• ชิ้นส่วนที่เชื่อมต่อกัน;
• ไม่สิ้นเปลือง;
• โดยไม่คำนึงถึงตำแหน่ง - การจัดสรรส่วนของเค้กนั้นขึ้นอยู่กับการประเมินค่าของส่วนนั้นโดยตัวแทนแต่ละคนเท่านั้น ไม่ใช่ตำแหน่งสัมพัทธ์ของส่วนนั้นบนเค้ก

โปรดทราบว่าผลลัพธ์ที่เป็นไปไม่ได้เหล่านี้ยังคงใช้ได้ไม่ว่าจะมีการกำจัดอย่างอิสระหรือไม่ก็ตาม

ในด้านบวก ในระบบเศรษฐกิจจำลองที่ตัวแทนแต่ละคนถูกจำลองซ้ำkครั้ง จะมีกลไกที่ปราศจากความอิจฉาซึ่งการบอกความจริงเป็นสมดุลแนช : ^{[ 7 ]}

• ในกลไกใดๆ ที่ปราศจากความอิจฉา การบอกความจริงจะลู่เข้าสู่สมดุลแนชเมื่อkเข้าใกล้ค่าอนันต์ โดยต้องมีข้อกำหนดด้านการเชื่อมต่อ
• หากไม่มีข้อกำหนดเรื่องการเชื่อมต่อ ในกลไกที่จัดสรรช่วงย่อยที่เป็นเนื้อเดียวกันแต่ละช่วงอย่างเท่าเทียมกันในหมู่ตัวแทนทั้งหมด การบอกความจริงจะเป็นสมดุลแนชอยู่แล้วเมื่อk ≥ 2

Taoปรับปรุงผลลัพธ์ที่เป็นไปไม่ได้ก่อนหน้านี้โดย Bei, Chen, Huzhang, Tao และ Wu และแสดงให้เห็นว่าไม่มีกลไกที่กำหนดได้ เป็นจริง และได้สัดส่วน แม้แต่ในแบบจำลองการเปิดเผยโดยตรง และแม้ว่าสิ่งต่อไปนี้ทั้งหมดจะเป็นจริงก็ตาม: ^{[ 8 ]}

• มีเจ้าหน้าที่เพียงสองคนเท่านั้น;
• เอเจนต์ต่างหิวโหย: มูลค่าของเอเจนต์แต่ละตัวเป็นค่าบวก (กล่าวคือ ไม่สามารถเป็น 0 ได้)
• กลไกนี้อนุญาตให้เว้นส่วนหนึ่งของเค้กไว้โดยไม่ได้จัดสรร

ยังไม่แน่ชัดว่าผลลัพธ์ที่เป็นไปไม่ได้นี้จะใช้ได้กับตัวแทนสามตัวขึ้นไปหรือไม่

ในด้านบวก Tao นำเสนออัลกอริทึมสองแบบที่บรรลุแนวคิดที่อ่อนกว่าที่เรียกว่า "ความจริงใจที่หลีกเลี่ยงความเสี่ยงตามสัดส่วน" (PRAT) ซึ่งหมายความว่า ในการเบี่ยงเบนที่ได้กำไรสำหรับตัวแทนiจะมีการประเมินค่าของตัวแทนอื่น ๆ ซึ่งiได้รับน้อยกว่าส่วนแบ่งตามสัดส่วนของเขา คุณสมบัตินี้แข็งแกร่งกว่า "ความจริงใจที่หลีกเลี่ยงความเสี่ยง" ซึ่งหมายความว่า ในการเบี่ยงเบนที่ได้กำไรสำหรับ i จะมีการประเมินค่าของตัวแทนอื่น ๆ ซึ่งiได้รับน้อยกว่ามูลค่าของเขาในการรายงานที่เป็นจริง เขานำเสนออัลกอริทึมที่เป็น PRAT และปราศจากความอิจฉา และอัลกอริทึมที่เป็น PRAT ตามสัดส่วน และเชื่อมโยงกัน^{[ 8 ] [ 9 ]}

สมมติว่าตัวแทนทั้งหมดมีการประเมินค่าแบบสม่ำเสมอเป็นช่วงๆหมายความว่า สำหรับตัวแทนแต่ละคน จะมีส่วนย่อยของเค้กที่ ตัวแทนนั้น ต้องการและค่าที่ตัวแทนให้สำหรับแต่ละส่วนนั้นก็คือปริมาณของเค้กที่ต้องการในส่วนนั้นนั่นเอง ตัวอย่างเช่น สมมติว่าบางส่วนของเค้กถูกเคลือบด้วยช็อกโกแลตอย่างสม่ำเสมอ ในขณะที่ส่วนอื่นๆ ไม่ได้ถูกเคลือบ ตัวแทนที่ให้ค่าแต่ละส่วนโดยพิจารณาจากปริมาณของช็อกโกแลตที่อยู่ภายใน จะมีการประเมินค่าแบบสม่ำเสมอเป็นช่วงๆ นี่เป็นกรณีพิเศษของการประเมินค่าแบบคงที่เป็นช่วงๆ มีการพัฒนาอัลกอริทึมที่ถูกต้องหลายตัวสำหรับกรณีพิเศษนี้

Chen, Lai, Parkes และ Procacciaนำเสนอกลไกการเปิดเผยโดยตรงซึ่งเป็นแบบกำหนดได้เป็นสัดส่วนปราศจากความอิจฉาเหมาะสมที่สุดตามหลัก Paretoและใช้เวลาแบบพหุนาม^{[ 2 ]}กลไกนี้ใช้ได้กับตัวแทนจำนวนเท่าใดก็ได้ นี่คือภาพประกอบของกลไก CLPP สำหรับตัวแทนสองตัว (โดยที่เค้กเป็นช่วงเวลา)

1. ขอให้ตัวแทนแต่ละคนรายงานช่วงเวลาที่ตนเองต้องการ
2. ช่วงเวลาย่อยแต่ละช่วงที่ไม่มีผู้ใดต้องการจะถูกตัดทิ้ง
3. แต่ละช่วงเวลาย่อยที่ตัวแทนเพียงรายเดียวต้องการ จะถูกจัดสรรให้กับตัวแทนรายนั้น
4. ช่วงย่อยที่ตัวแทนทั้งสองฝ่ายต้องการจะถูกจัดสรรเพื่อให้ตัวแทนทั้งสองฝ่ายได้รับความยาว รวมเท่า กัน

ทีนี้ ถ้าตัวแทนคนหนึ่งบอกว่าเขาต้องการช่วงเวลาที่เขาไม่ต้องการจริงๆ เขาอาจจะได้เค้กที่ไร้ประโยชน์มากขึ้นในขั้นตอนที่ 3 และเค้กที่มีประโยชน์น้อยลงในขั้นตอนที่ 4 แต่ถ้าเขาบอกว่าเขาไม่ต้องการช่วงเวลาที่เขาต้องการจริงๆ เขาจะได้เค้กที่มีประโยชน์น้อยลงในขั้นตอนที่ 3 และเค้กที่มีประโยชน์มากขึ้นในขั้นตอนที่ 4 อย่างไรก็ตาม จำนวนเค้กที่ให้ในขั้นตอนที่ 4 จะถูกแบ่งกับตัวแทนคนอื่นๆ ดังนั้นโดยรวมแล้ว ตัวแทนที่โกหกจะเป็นฝ่ายเสียเปรียบ กลไกนี้สามารถนำไปปรับใช้กับจำนวนตัวแทนใดๆ ก็ได้

กลไก CLPP อาศัย สมมติฐาน การกำจัดอย่างอิสระกล่าวคือ ความสามารถในการกำจัดชิ้นส่วนที่ไม่เป็นที่ต้องการของตัวแทนใดๆ

หมายเหตุ : Aziz และ Ye ^{[ 4 ]}นำเสนอสองกลไกที่ขยายกลไก CLPP ไปสู่การประเมินค่าคงที่แบบเป็นช่วงๆ ได้แก่ อัลกอริทึมการกินเค้กแบบมีข้อจำกัดและอัลกอริทึมสมดุลตลาด อย่างไรก็ตาม การขยายทั้งสองนี้จะไม่เป็นจริงอีกต่อไปเมื่อการประเมินค่าไม่เป็นแบบสม่ำเสมอเป็นช่วงๆ

มายาและนิซานแสดงให้เห็นว่ากลไก CLPP มีเอกลักษณ์เฉพาะในแง่ต่อไปนี้^{[ 10 ]}พิจารณากรณีพิเศษของ ตัวแทน สองคนที่มีการประเมินค่าแบบสม่ำเสมอเป็นช่วงๆ โดยที่เค้กคือ [0,1] อลิซต้องการเฉพาะช่วงย่อย [0, a ] สำหรับa <1 บางค่า และบ็อบต้องการเฉพาะช่วงย่อย [1− b ,1] สำหรับb <1 บางค่า พิจารณาเฉพาะ กลไก ที่ไม่สิ้นเปลือง - กลไกที่จัดสรรชิ้นส่วนแต่ละชิ้นที่ผู้เล่นอย่างน้อยหนึ่งคนต้องการให้กับผู้เล่นที่ต้องการมัน กลไกแต่ละอย่างดังกล่าวจะต้องให้เซตย่อย [0, c ] แก่อลิซ สำหรับ c <1 บางค่า และให้เซตย่อย [1− d ,1] แก่บ็อบสำหรับ d <1 บางค่า ในแบบจำลองนี้:

• กลไกเชิงกำหนดที่ไม่สิ้นเปลืองนั้นถือว่าเที่ยงตรงก็ต่อเมื่อ สำหรับพารามิเตอร์t บางตัว ในช่วง [0,1] มันจะให้ช่วง [0, min( a , max(1− b , t ))] แก่ Alice และให้ช่วง [1−min( b ,max(1− a ,1− t )),1] แก่ Bob
• กลไกดังกล่าวจะปราศจากความอิจฉาริษยาเมื่อt = 1/2 ในกรณีนี้ กลไกนี้จะเทียบเท่ากับกลไก CLPP

นอกจากนี้ ผลการวิจัยยังแสดงให้เห็นว่า แม้จะมีตัวแทนเพียง 2 คน กลไกที่ซื่อสัตย์ใดๆ ก็ตามจะบรรลุผลประโยชน์ทางสังคมที่เหมาะสมได้มากที่สุดเพียง 0.93 เท่านั้น

Li, Zhang และ Zhangแสดงให้เห็นว่ากลไก CLPP ทำงานได้ดีแม้จะมีผลกระทบภายนอก (เช่น ตัวแทนบางรายได้รับประโยชน์บางอย่างจากมูลค่าที่มอบให้กับผู้อื่น) ตราบใดที่ผลกระทบภายนอกมีขนาดเล็กพอ ในทางกลับกัน หากผลกระทบภายนอก (ไม่ว่าจะเป็นบวกหรือลบ) มีขนาดใหญ่ จะไม่มีกลไกที่แท้จริง ไม่สิ้นเปลือง และไม่ขึ้นกับตำแหน่ง^{[ 11 ]}

Alijani, Farhadi, Ghodsi, Seddighin และ Tajikนำเสนอกลไกหลายประการสำหรับกรณีพิเศษของการประเมินมูลค่าแบบชิ้นเดียว: ^{[ 12 ]}

• กระบวนการขยายนี้จัดการกับการประเมินค่าแบบสม่ำเสมอเป็นช่วงๆ โดยที่ตัวแทนแต่ละตัวมีช่วงเวลาที่ต้องการเพียงช่วงเดียว และยิ่งไปกว่านั้น ช่วงเวลาที่ตัวแทนต้องการนั้นเป็นไปตามคุณสมบัติการเรียงลำดับ กระบวนการนี้ใช้เวลาในการประมวลผลแบบพหุนาม มีความถูกต้อง ปราศจากความอิจฉา และรับประกันว่าชิ้นส่วนต่างๆ เชื่อมต่อกัน
• กระบวนการขยายที่มีการปลดล็อกจะจัดการกับการประเมินค่าแบบสม่ำเสมอเป็นช่วงๆ โดยที่ตัวแทนแต่ละตัวมีช่วงเวลาที่ต้องการเพียงช่วงเดียว แต่ไม่มีข้อกำหนดเรื่องลำดับ กระบวนการนี้ใช้เวลาแบบพหุนาม ซื่อสัตย์ ปราศจากความอิจฉา และไม่จำเป็นต้องเชื่อมต่อกัน แต่จะทำการตัดอย่างมากที่สุด 2 n −2 ครั้ง

Bei, Huzhang และ Suksompongนำเสนอกลไกสำหรับตัวแทนสองตัวที่มีการประเมินค่าแบบสม่ำเสมอเป็นช่วงๆ ซึ่งมีคุณสมบัติเช่นเดียวกับ CLPP (ซื่อสัตย์ กำหนดได้ เป็นสัดส่วน ปราศจากความอิจฉา เหมาะสมที่สุดตาม Pareto และทำงานในเวลาพหุนาม) แต่รับประกันว่า เค้ก ทั้งหมดจะถูกจัดสรร: ^{[ 13 ]}

1. จงหาค่า xที่เล็กที่สุดในช่วง [0,1] ที่ทำให้ความยาวที่อลิซต้องการในช่วง [0, x ] เท่ากับความยาวที่บ็อบต้องการในช่วง [ x ,1]
2. ให้ช่วง [0, x ] ที่อลิซมีค่า และช่วง [ x ,1] ที่บ็อบ ไม่มีค่า แก่อลิซ และให้ส่วนที่เหลือแก่บ็อบ

กลไก BHS ใช้ได้ทั้งสำหรับการตัดเค้กและการแบ่งงานบ้าน (ซึ่งการประเมินค่าของตัวแทนเป็นค่าลบ) โปรดทราบว่า BHS ไม่เป็นไปตามคุณสมบัติที่พึงประสงค์ตามธรรมชาติบางประการ:

• มันไม่ได้รับประกันว่าชิ้นส่วนจะเชื่อมต่อกันเสมอไป ตัวอย่างเช่น เมื่ออลิซต้องการ [0,1] และบ็อบต้องการ [0,0.5] แล้วx = 0.25 อลิซจะได้ [0,0.25] และ [0.5,1] ส่วนบ็อบจะได้ [0.25,0.5]
• ไม่ใช่ การแบ่งแบบไม่ ระบุชื่อ (ดูการแบ่งเค้กแบบยุติธรรมสมมาตร ) : ถ้าอลิซต้องการ [0,1] และบ็อบต้องการ [0,0.5] อลิซจะได้ความยาวที่ต้องการ 0.75 และบ็อบได้ 0.25 แต่ถ้าค่าที่ต้องการสลับกัน (อลิซต้องการ [0,0.5] และบ็อบต้องการ [0,1]) แล้วx = 0.5 และทั้งสองฝ่ายจะได้ความยาวที่ต้องการ 0.5
• ไม่ใช่ว่าไม่คำนึงถึงตำแหน่ง : ถ้าอลิซต้องการ [0,0.5] และบ็อบต้องการ [0,1] ตัวแทนทั้งสองจะได้รับค่า 0.5 แต่ถ้าช่วงเวลาที่อลิซต้องการเปลี่ยนไปเป็น [0.5,1] ค่า xจะเท่ากับ 0.75 และอลิซจะได้รับ 0.25 ส่วนบ็อบจะได้รับ 0.75

นี่ไม่ใช่ปัญหาของกลไกเฉพาะ: เป็นไปไม่ได้ที่จะพิสูจน์ได้ว่ามีกลไกที่เที่ยงตรงและปราศจากความอิจฉาที่จัดสรรเค้กทั้งหมดและรับประกันคุณสมบัติทั้งสามประการนี้ แม้แต่สำหรับตัวแทนสองรายที่มีการประเมินค่าแบบสม่ำเสมอเป็นช่วงๆ^{[ 13 ]}

กลไก BHS ได้รับการขยายให้รองรับตัวแทนจำนวนเท่าใดก็ได้ แต่เฉพาะในกรณีพิเศษของการประเมินค่าแบบสม่ำเสมอเป็นช่วงๆ ซึ่งตัวแทนแต่ละรายต้องการเพียงช่วงเดียวในรูปแบบ [0, x ]

Ianovsky ^{[ 14 ]}พิสูจน์ว่าไม่มีกลไกที่ซื่อสัตย์ใดที่สามารถบรรลุการแบ่งเค้กที่เหมาะสมตามประโยชน์นิยมได้แม้ว่าตัวแทนทั้งหมดจะมีการประเมินค่าแบบสม่ำเสมอเป็นชิ้นๆ ก็ตาม ยิ่งไปกว่านั้น ไม่มีกลไกที่ซื่อสัตย์ใดที่สามารถบรรลุการจัดสรรที่มีสวัสดิภาพตามประโยชน์นิยมอย่างน้อยเท่ากับกลไกอื่นๆ ได้ อย่างไรก็ตาม มีกลไกที่ซื่อสัตย์ง่ายๆ (เรียกว่า Lex Order) ที่ไม่สิ้นเปลือง : มอบชิ้นส่วนทั้งหมดที่ตัวแทน 1 ชอบ จากนั้น มอบชิ้นส่วนทั้งหมดที่ตัวแทน 2 ชอบและยังไม่ได้มอบให้ตัวแทน 1 ให้กับตัวแทน 2 เป็นต้น รูปแบบหนึ่งของกลไกนี้คือ Length Game ซึ่งตัวแทนจะถูกเปลี่ยนชื่อตามความยาวทั้งหมดของช่วงเวลาที่พวกเขาต้องการ โดยที่ตัวแทนที่มีช่วงเวลาที่สั้นที่สุดเรียกว่า 1 ตัวแทนที่มีช่วงเวลาที่สั้นรองลงมาเรียกว่า 2 เป็นต้น อย่างไรก็ตาม นี่ไม่ใช่กลไกที่ซื่อสัตย์:

• หากตัวแทนทุกฝ่ายพูดความจริง การจัดสรรที่ได้จะเป็นไปอย่างเหมาะสมตามหลักอรรถประโยชน์นิยม
• หากตัวแทนมีกลยุทธ์ สมดุลแนชที่ดีทั้งหมดของมันจะมีประสิทธิภาพแบบพาเรโตและปราศจากความอิจฉา และให้ผลตอบแทนเช่นเดียวกับกลไก CLPP

ชื่อ	พิมพ์	เป็นแบบกำหนดได้แน่นอนใช่ไหม?	#เอเจนต์( n )	การประเมินมูลค่า[ 15 ]	งานบ้าน? [ 16 ]	เวลาวิ่ง	ทั้งหมด? [ 17 ]	PO? [ 18 ]	EF? [ 19 ]	นิรนาม? [ 20 ]	คอนน์? [ 21 ]	Pos.Ob.? [ 22 ]	ไม่มีขยะ? [ 23 ]
การหารที่แน่นอน[ 1 ] [ 2 ]	โดยตรง	เลขที่	มากมาย	ทั่วไป	ใช่	ไร้ขอบเขต[ 24 ]	ใช่	เลขที่	ใช่	ใช่	เลขที่	?	?
สัดส่วนเกิน[ 1 ]	โดยตรง	เลขที่	มากมาย	ทั่วไป	ใช่	ไร้ขอบเขต	ใช่	เลขที่	เลขที่	ใช่	เลขที่	?	?
การหารที่แม่นยำแบบไม่ต่อเนื่อง[ 3 ]	คำถาม	เลขที่	มากมาย	ทั่วไป	ใช่	${\displaystyle O(n^{2}/\epsilon )}$	ใช่	เลขที่	${\displaystyle \epsilon }$-เอฟ	ใช่	เลขที่	?	?
การปกครองแบบเผด็จการต่อเนื่องที่ถูกจำกัด[ 4 ]	โดยตรง	เลขที่	มากมาย	พีดับบลิวซี	?	?	เลขที่	เอกฉันท์	ทรัพย์สิน	?	เลขที่	?	?
CLPP [ 2 ]	โดยตรง	ใช่	มากมาย	พีดับบลิวยู	เลขที่	พหุนาม	เลขที่	ใช่	ใช่	ใช่	เลขที่	?	ใช่
บีเอชเอส 1, 2	โดยตรง	ใช่	2	พีดับบลิวยู	ใช่	พหุนาม	ใช่	ใช่	ใช่	เลขที่	เลขที่	เลขที่	ใช่
บีเอชเอส 3, 4	โดยตรง	ใช่	มากมาย	พีดับบลิวยู1	ใช่	พหุนาม	ใช่	ใช่	ใช่	?	?	?	ใช่
การขยาย[ 12 ]	โดยตรง	ใช่	มากมาย	PWU1+สั่งซื้อ	?	พหุนาม	?	?	ใช่	?	ใช่	?	?
การปลดล็อก Expansion+	โดยตรง	ใช่	มากมาย	พีดับบลิวยู1	?	พหุนาม	?	?	ใช่	?	2 n -2 ตัด	?	?
การผสมผสานที่เป็นไปไม่ได้:
[BM] [ 3 ]	คำถาม	ใช่	2+	ใดๆ
[BHS] [ 13 ]	โดยตรง	ใช่	2+	พีดับบลิวยู			ใช่		ใช่	ใช่
[บีเอชเอส]	โดยตรง	ใช่	2+	พีดับบลิวยู			ใช่		ใช่		ใช่
[บีเอชเอส]	โดยตรง	ใช่	2+	พีดับบลิวยู			ใช่		ใช่			ใช่
[T] [ 8 ]	โดยตรง	ใช่	2+	พีดับบลิวซี					ใช่
[BCHTW] [ 7 ]	โดยตรง	ใช่	2+	พีดับบลิวซี			ใช่		ใช่		ใช่
[บีซีทีดับเบิลยู]	โดยตรง	ใช่	2+	พีดับบลิวซี			ใช่		ใช่			ใช่
[บีซีทีดับเบิลยู]	โดยตรง	ใช่	2+	พีดับบลิวซี			ใช่		ใช่				ใช่
[บีซีทีดับเบิลยู]	ลำดับ	ใช่	2+	พีดับบลิวซี			ใช่		ใช่

• การแบ่งงานเชิงกลยุทธ์ที่เป็นธรรม
• การจัดสรรทรัพยากรอย่างเที่ยงธรรม