การแบ่งแบบฉันทามติหรือที่เรียกว่าการแบ่งแบบแม่นยำ^{[ 1 ]} : ¹²⁷ คือการแบ่งทรัพยากรต่อเนื่อง (" เค้ก ") ออกเป็นkชิ้น โดยที่คนnคน ที่มีรสนิยมแตกต่างกันเห็นพ้องต้องกันในคุณค่าของแต่ละชิ้น ตัวอย่างเช่น พิจารณาเค้กที่มีช็อกโกแลตครึ่งหนึ่งและวานิลลาครึ่งหนึ่ง อลิซให้คุณค่าเฉพาะช็อกโกแลต และจอร์จให้คุณค่าเฉพาะวานิลลา เค้กถูกแบ่งออกเป็นสามชิ้น ชิ้นแรกมีช็อกโกแลต 20% และวานิลลา 20% ชิ้นที่สองมีช็อกโกแลต 50% และวานิลลา 50% และชิ้นที่สามมีส่วนที่เหลือของเค้ก นี่คือการแบ่งแบบแม่นยำ (โดยที่k  = 3 และn  = 2) เนื่องจากทั้งอลิซและจอร์จให้คุณค่ากับทั้งสามชิ้นเป็น 20%, 50% และ 30% ตามลำดับ มีรูปแบบทั่วไปและกรณีพิเศษหลายกรณีที่รู้จักกันในชื่อต่างๆ:

• การแบ่งครึ่งตามฉันทามติ – เค้กควรถูกแบ่งออกเป็นสองชิ้น ( k  = 2) และตัวแทนทั้งหมดเห็นพ้องต้องกันว่าชิ้นส่วนมีมูลค่าเท่ากัน^{[ 2 ]}
• การแบ่งแบบ ฉันทามติ 1/ kสำหรับค่าคงที่k  > 1 ใดๆ – เค้กควรถูกแบ่งออกเป็นkชิ้น และตัวแทนทั้งหมดเห็นพ้องต้องกันว่าชิ้นส่วนเหล่านั้นมีมูลค่าเท่ากัน^{[ 2 ]}อีกคำหนึ่งคือ การแบ่ง แบบฉันทามติ^{[ 3 ]}
• การแบ่งที่สมบูรณ์แบบ – จำนวนชิ้นเท่ากับจำนวนตัวแทน: เค้กควรถูกแบ่งออกเป็นnชิ้น และตัวแทนทุกคนเห็นพ้องต้องกันว่าทุกชิ้นมีมูลค่าเท่ากัน
• ${\displaystyle \varepsilon }$-การหารแบบเกือบแม่นยำสำหรับค่าคงที่ใดๆตัวแทนอาจไม่เห็นด้วยกับค่าของชิ้นส่วน แต่ความแตกต่างระหว่างค่าควรมีค่าไม่เกิน ในทำนองเดียวกัน รูปแบบโดยประมาณของปัญหาที่กล่าวถึงข้างต้นเรียกว่า - การแบ่งครึ่งตามฉันทามติ -การ หาร แบบฉันทามติ 1/ k - การแบ่ง แบบฉันทามติ หรือ-การแยกแบบฉันทามติและ-การหารแบบสมบูรณ์${\displaystyle \varepsilon >0}$${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$
• ปัญหาของแม่น้ำไนล์ – มีผู้เกี่ยวข้องมากมายนับไม่ถ้วน
• การแบ่งสร้อยคอ – ทรัพยากรที่จะแบ่งนั้นประกอบด้วยวัตถุที่ไม่สามารถแบ่งย่อยได้จำนวนจำกัด ("ลูกปัด")

เมื่อทั้งnและkมีจำนวนจำกัด การแบ่งแบบฉันทามติจะมีอยู่เสมอ อย่างไรก็ตาม ไม่สามารถค้นหาการแบ่งเหล่านั้นได้ด้วยโปรโตคอลแบบไม่ต่อเนื่อง (ที่มีจำนวนการสอบถามจำกัด) ในบางกรณี สามารถค้นหาการแบ่งที่แน่นอนได้ด้วยโปรโตคอลแบบมีดเคลื่อนที่ ส่วนการแบ่งที่ใกล้เคียงแน่นอนสามารถค้นหาได้ด้วยโปรโตคอลแบบไม่ต่อเนื่อง

ให้kเป็นน้ำหนักที่มีผลรวมเท่ากับ 1 สมมติว่ามี ตัวแทน nคน ซึ่งทุกคนให้คุณค่าเค้กCเท่ากับ 1 การวัดคุณค่าของตัวแทนiจะใช้สัญลักษณ์ โดยถือว่าเป็นการวัดแบบไม่เป็นอะตอมบนCการหารที่แน่นอนในอัตราส่วนคือการแบ่งเค้กออกเป็นkชิ้น: โดยที่สำหรับตัวแทนi ทุกคน และชิ้นส่วนj ทุกชิ้น : ${\displaystyle w_{1},w_{2},\ldots ,w_{k}}$${\displaystyle V_{i}}$${\displaystyle w_{1},w_{2},\ldots ,w_{k}}$${\displaystyle C=X_{1}\sqcup \cdots \sqcup X_{k}}$

${\displaystyle V_{i}(X_{j})=w_{j}}$

เรียกอีกอย่างว่าการแบ่งตามฉันทามติเนื่องจากมีฉันทามติในหมู่ตัวแทนทั้งหมดว่ามูลค่าของชิ้นส่วนjเท่ากับ^{[ 1 ]} : ¹²⁷ กรณีพิเศษบางกรณีได้แก่: ${\displaystyle w_{j}}$

• การหารแบบฉันทามติ 1/ k – กรณีพิเศษที่.${\displaystyle w_{1}=\cdots =w_{n}=1/k}$
• การแบ่งครึ่งตามฉันทามติ – กรณีพิเศษที่และ.${\displaystyle k=2}$${\displaystyle w_{1}=w_{2}=1/2}$
• การหารที่สมบูรณ์แบบ – กรณีพิเศษที่และ${\displaystyle k=n}$${\displaystyle w_{1}=\cdots =w_{n}=1/n}$

สำหรับทุกค่า การหาร ที่เกือบสมบูรณ์แบบในอัตราส่วนคือการหารที่: ${\displaystyle \varepsilon >0}$${\displaystyle \varepsilon }$${\displaystyle w_{1},w_{2},\ldots ,w_{k}}$

${\displaystyle |V_{i}(X_{j})-w_{j}|<\varepsilon }$

นั่นคือ มีฉันทามติในหมู่หุ้นส่วนทั้งหมดว่ามูลค่าของชิ้นส่วนj เกือบ จะเท่ากับ โดยที่ความแตกต่างน้อยกว่า[ ^{1 ] : 127} กรณีพิเศษบางกรณีได้แก่: ${\displaystyle w_{j}}$${\displaystyle \varepsilon }$

• ${\displaystyle \varepsilon }$-ฉันทามติ 1/ kการแบ่งส่วน – กรณีพิเศษที่.${\displaystyle w_{1}=\cdots =w_{n}=1/k}$
• ${\displaystyle \varepsilon }$-การแบ่งครึ่งตามฉันทามติ – กรณีพิเศษที่และ.${\displaystyle k=2}$${\displaystyle w_{1}=w_{2}=1/2}$
• ${\displaystyle \varepsilon }$-การหารสมบูรณ์ – กรณีพิเศษที่และ.${\displaystyle k=n}$${\displaystyle w_{1}=\cdots =w_{n}=1/n}$

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

• แบ่งแต่ละภูมิภาคออกเป็นkภูมิภาคย่อย โดยที่ภูมิภาคย่อยjประกอบด้วยภูมิภาคทั้งหมด จำนวนหนึ่ง${\displaystyle w_{j}}$
• ให้ส่วนที่jเป็นผลรวมของส่วนย่อยที่j ในทุก ภูมิภาคR

จำนวนการตัดที่จำเป็นคือโดยที่Rคือจำนวนภูมิภาค อัลกอริทึมนี้สามารถขยายไปสู่ การประเมินค่า เชิงเส้นแบบแบ่งส่วนได้^{[ 4 ]}${\displaystyle k\cdot R}$

การแบ่งที่แน่นอนมีอยู่ในการตั้งค่าทั่วไปมากขึ้นซึ่งตัวแทนมีการวัดที่ไม่ใช่เชิงกายวิภาคแบบนับได้ นี่เป็นผลสืบเนื่องมาจากทฤษฎีความนูนของ Dubins–Spanier (การมีอยู่ของการแบ่ง 1/ k ที่ เป็นเอกฉันท์ได้รับการกล่าวถึงก่อนหน้านี้โดยJerzy Neyman ^{[ 5 ]} ) อย่างไรก็ตาม ทฤษฎีบทนี้ไม่ได้กล่าวถึงจำนวนการตัดที่จำเป็น

Woodall ^{[ 6 ]}แสดงให้เห็นว่าสามารถสร้างการแบ่งที่แน่นอนของเค้กช่วงเวลาได้โดยใช้ การรวมกันของช่วงเวลา ที่นับได้แนวคิด: พิจารณาขั้นตอนการแบ่งสำหรับเค้กที่เป็นเนื้อเดียวกันเป็นชิ้นๆ ที่อธิบายไว้ข้างต้น โดยทั่วไป เค้กจะไม่เป็นเนื้อเดียวกันเป็นชิ้นๆ อย่างไรก็ตาม เนื่องจากมาตรวัดค่ามีความต่อเนื่อง จึงสามารถแบ่งเค้กออกเป็นบริเวณที่เล็กลงเรื่อยๆ จนกระทั่งบริเวณเหล่านั้นมีความเป็นเนื้อเดียวกันมากขึ้นเรื่อยๆ เมื่อกระบวนการนี้จะลู่เข้าสู่การแบ่งที่เป็นเอกฉันท์ อย่างไรก็ตาม จำนวนการตัดที่จำเป็นในขีดจำกัดนั้นเป็นอนันต์ ต่อมา Fremlin แสดงให้เห็นว่าสามารถสร้างการแบ่งดังกล่าวได้โดยใช้การรวมกันของช่วงเวลา แบบจำกัด${\displaystyle R\to \infty }$

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

พิจารณา กรณี การแบ่งครึ่งตามฉันทามติ ก่อน : และน้ำหนักเท่ากัน ขอบเขตล่างของจำนวนการตัดคือ อันที่จริง การแบ่งครึ่งตามฉันทามติที่มี การตัดไม่เกินn ครั้งนั้นมีอยู่เสมอ ^{[ 7 ]}นี่เป็นผลลัพธ์โดยตรงจากทฤษฎีบท Hobby–Riceนอกจากนี้ยังสามารถพิสูจน์ได้โดยใช้ทฤษฎีบท Borsuk-Ulam : ^{[ 8 ]}${\displaystyle k=2}$${\displaystyle n\cdot (k-1)=n}$

• การแบ่งช่วงแต่ละช่วงโดยใช้การตัด สามารถแสดงได้ด้วยเวกเตอร์ที่มีความยาวโดยที่องค์ประกอบของเวกเตอร์ คือความยาวของช่วงย่อยต่างๆ${\displaystyle n}$${\displaystyle n+1}$
• แต่ละองค์ประกอบของเวกเตอร์สามารถเป็นได้ทั้งค่าบวก (ถ้าเป็นของชิ้นส่วนที่ 1) หรือค่าลบ (ถ้าเป็นของชิ้นส่วนที่ 2)
• เซตของพาร์ทิชันทั้งหมดมีลักษณะสมมาตรกับทรงกลม${\displaystyle S^{n}}$
• กำหนดฟังก์ชันในลักษณะต่อไปนี้: สำหรับทุกพาร์ติชันxฟังก์ชันจะเป็นเวกเตอร์ที่มี องค์ประกอบที่ iเป็นค่าของชิ้นส่วนที่ 1 ในพาร์ติชันนั้นตามคู่ที่iลบด้วย 1/2${\displaystyle V:S^{n}\to \mathbb {R} ^{n}}$${\displaystyle V(x)}$
• ฟังก์ชันVมีความต่อเนื่อง ยิ่งไปกว่านั้น สำหรับทุกx , .${\displaystyle V(x)+V(-x)=0}$
• ดังนั้น ตามทฤษฎีบทบอร์ซุก-อูแลมจึงมีค่าx อยู่ ค่าหนึ่งที่ทำให้ในการแบ่งส่วนนั้น หุ้นส่วนทุกคนให้คุณค่าชิ้นส่วนที่ 1 (และชิ้นส่วนที่ 2) เท่ากับ 1/2 พอดี${\displaystyle V(x)=0}$

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

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

พิจารณากรณีk = 2 และ น้ำหนัก ใดๆ Stromquist และ Woodall ^{[ 9 ]}พิสูจน์แล้วว่ามีการแบ่งพาย(เค้กทรงกลม) ที่แน่นอนซึ่งแต่ละชิ้นมีช่วงไม่เกินn - 1 ช่วง ดังนั้นจึงต้องใช้การตัด ไม่เกิน 2 n - 2 ครั้ง ดู ทฤษฎีบท Stromquist–Woodallจำนวนการตัดนั้นเหมาะสมที่สุดสำหรับน้ำหนักทั่วไป ทฤษฎีบทนี้สามารถนำไปใช้แบบเรียกซ้ำเพื่อให้ได้การแบ่งที่แน่นอนสำหรับk > 1 ใดๆ และน้ำหนักใดๆ โดยใช้การตัด O( nk ) ครั้ง

ทฤษฎีบท สโตน-ทูคีย์กล่าวว่า เมื่อมี "วัตถุ" ที่วัดได้n ชิ้น ในปริภูมิnมิติก็สามารถแบ่งวัตถุทั้งหมดนั้นออกเป็นครึ่ง (โดยพิจารณาจากขนาดเช่น ปริมาตร) ด้วยระนาบไฮเปอร์มิติเพียงระนาบเดียวที่ มีมิติ( n − 1)

กล่าวอีกนัยหนึ่งคือ ถ้าเค้กคือปริภูมิและค่าการวัดของหุ้นส่วนแต่ละคนมีค่าจำกัดและเป็นศูนย์บนระนาบมิติใดๆ แล้วจะมีครึ่งปริภูมิที่มีค่าเท่ากับ 1/2 พอดีสำหรับหุ้นส่วนแต่ละคน ดังนั้นจึงมีการแบ่งอย่างฉันทามติโดยใช้การตัด เพียงครั้งเดียว${\displaystyle \mathbb {R} ^{n}}$${\displaystyle n-1}$

ทฤษฎีบทฉบับดั้งเดิมนี้ใช้ได้เฉพาะในกรณีที่จำนวนมิติของเค้กเท่ากับจำนวนคู่หูเท่านั้น ตัวอย่างเช่น ไม่สามารถใช้ทฤษฎีบทนี้ในการแบ่งแซนด์วิชสามมิติให้กับคู่หู 4 คนขึ้นไปได้

อย่างไรก็ตาม มีการสรุปทั่วไปที่ทำให้สามารถแบ่งได้เช่นนั้น พวกเขาไม่ได้ใช้มีดไฮเปอร์เพลน แต่ใช้พื้นผิวพหุนามที่ซับซ้อนกว่าแทน^{[ 10 ]}

นอกจากนี้ยังมีการปรับเปลี่ยนแบบแยกส่วนของผลลัพธ์หลายมิติเหล่านี้ด้วย^{[ 11 ]}

เป็นไปไม่ได้ที่จะคำนวณการหารที่แน่นอนด้วยจำนวนคำถามที่จำกัด แม้ว่าจะมีตัวแทนเพียงn = 2 และ ชิ้นส่วน k = 2 ชิ้น น้ำหนักจะเท่ากับ 1/2 ก็ตาม^{[ 1 ] : 103–104} ซึ่งหมายความว่าสิ่งที่ดีที่สุดที่เราสามารถทำได้โดยใช้อัลกอริทึมแบบไม่ต่อเนื่องคือการหารที่ใกล้เคียงกับจำนวนที่แน่นอน

บทพิสูจน์ : เมื่อโปรโตคอลอยู่ที่ขั้นตอนkจะมีชิ้นส่วนอยู่ไม่เกินkชิ้น เพื่อให้เกิดการหารที่ลงตัว โปรโตคอลจะต้องหาสับเซตที่ลงตัว – สับเซตของชิ้นส่วนที่ทั้งสองฝ่ายให้ค่าเท่ากับ 1/2 พอดี เราจะพิสูจน์ว่า สำหรับทุกค่าkจะมีสถานการณ์ที่ในขั้นตอนkไม่มีสับเซตที่ลงตัว และด้วยเหตุนี้ โปรโตคอลอาจต้องดำเนินต่อไปอย่างไม่มีที่สิ้นสุด

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

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

จำนวนเซตย่อยที่แตกต่างกันทั้งหมดในขณะนี้คือ 2k ^และตามสมมติฐานการอุปมาน ไม่มีเซตย่อยใดที่แน่นอน ในขั้นตอนที่kโปรโตคอลสามารถขอให้ Alice หรือ George ตัดชิ้นส่วนหนึ่งออกเป็นสองชิ้น สมมติว่าผู้ตัดคือ George และเขาตัดชิ้นส่วน X ออกเป็นสองชิ้นส่วนย่อย: X1 และ X2 ตอนนี้ จำนวนเซตย่อยทั้งหมดคือ 2k ^{+ 1} : ครึ่งหนึ่งของเซตย่อยเหล่านี้มีอยู่แล้ว และตามสมมติฐาน เซตย่อยเหล่านี้ไม่แน่นอน ดังนั้นโอกาสเดียวที่โปรโตคอลจะพบเซตย่อยที่แน่นอนคือการพิจารณาเซตย่อยใหม่ เซตย่อยใหม่แต่ละเซตสร้างขึ้นจากเซตย่อยเก่า โดยที่ชิ้นส่วน X ถูกแทนที่ด้วย X1 หรือ X2 เนื่องจาก George เป็นผู้ตัด เขาจึงสามารถตัดในลักษณะที่ทำให้เซตย่อยใดเซตหนึ่งเป็นเซตย่อยที่แน่นอนสำหรับเขา (เช่น ถ้าเซตย่อยหนึ่งที่มีชิ้นส่วน X มีค่าเป็น 3/4 George สามารถตัด X ได้เพื่อให้ X1 มีค่าเป็น 1/4 ในความคิดของเขา ดังนั้นเซตย่อยใหม่จึงมีค่าเป็น 1/2 พอดี) แต่จอร์จไม่ทราบค่าที่อลิซประเมินไว้ และไม่สามารถนำมาพิจารณาเมื่อทำการตัดได้ ดังนั้นจึงมีค่าที่แตกต่างกันเป็นอนันต์นับไม่ถ้วนที่ชิ้นส่วน X1 และ X2 สามารถมีได้สำหรับอลิซ เนื่องจากจำนวนของเซตย่อยใหม่มีจำกัด จึงมีกรณีเป็นอนันต์ที่ไม่มีเซตย่อยใหม่ใดมีค่าเท่ากับ 1/2 สำหรับอลิซ ดังนั้นจึงไม่มีเซตย่อยใหม่ใดที่เป็นเซตที่แน่นอน

ตัวแทนสองคนสามารถบรรลุข้อตกลงร่วมกันในการแบ่งทรัพย์สินโดยใช้ขั้นตอนการแบ่งแบบมีดเคลื่อนที่ของออสติน

กรณีที่ง่ายที่สุดคือเมื่อน้ำหนักของมีดทั้งสองเล่มเท่ากับ 1/2 กล่าวคือ พวกเขาต้องการตัดเค้กชิ้นหนึ่งที่ทั้งสองฝ่ายเห็นพ้องต้องกันว่ามีมูลค่าครึ่งหนึ่งของเค้กทั้งหมด วิธีการทำมีดังนี้ ตัวแทนคนหนึ่งจะเลื่อนมีดสองเล่มไปบนเค้กจากซ้ายไปขวา โดยรักษาน้ำหนักระหว่างมีดทั้งสองเล่มให้เท่ากับ 1/2 เสมอ สามารถพิสูจน์ได้ (โดยทฤษฎีบทค่ากลาง ) ว่า ณ จุดใดจุดหนึ่ง มูลค่าของชิ้นเค้กระหว่างมีดทั้งสองเล่มสำหรับอีกฝ่ายหนึ่งจะมีค่าเท่ากับ 1/2 เช่นกัน ตัวแทนอีกคนจะตะโกนว่า "หยุด!" ณ จุดนั้น และชิ้นเค้กก็จะถูกตัดออก

สามารถใช้วิธีการเดียวกันนี้ในการแบ่งส่วนทรัพย์สินที่ทั้งสองฝ่ายเห็นพ้องต้องกันว่ามีค่าเท่ากับโดยการรวมส่วนต่างๆ ดังกล่าวหลายๆ ส่วนเข้าด้วยกัน ก็สามารถบรรลุการหารที่ตกลงร่วมกันได้ โดยใช้สัดส่วนใดๆ ก็ได้ที่เป็นจำนวนตรรกยะ แต่การทำเช่นนี้อาจต้องใช้การแบ่งส่วนจำนวนมาก ${\displaystyle 1/n}$

วิธีที่ดีกว่าในการบรรลุการแบ่งที่เป็นเอกฉันท์คือการระบุจุดปลายทั้งสองของเค้กและถือว่ามันเป็นวงกลม กล่าวคือ เมื่อมีดด้านขวาไปถึงด้านขวา มันจะไปทางด้านซ้ายทันที และชิ้นส่วนระหว่างมีดนั้นก็คือการรวมกันของชิ้นส่วนทางด้านขวาของมีดด้านขวาและชิ้นส่วนทางด้านซ้ายของมีดด้านซ้าย ด้วยวิธีนี้ จึงเป็นไปได้ที่จะหาการแบ่งที่เป็นเอกฉันท์สำหรับทุกๆตัวแทนหนึ่งจะเคลื่อนมีดไปรอบๆ เค้กเป็นวงจร โดยรักษามูลค่าระหว่างมีดไว้ที่p เสมอ เป็นไปได้ที่จะพิสูจน์ได้ว่า ณ จุดใดจุดหนึ่ง มูลค่าของชิ้นส่วนระหว่างมีดสำหรับคู่ค้าอีกฝ่ายหนึ่งก็จะเป็นp เช่นกัน [ ^{12 ] ตัวแทนอีกฝ่ายหนึ่งจะตะโกน ว่า} "หยุด!" ณ จุดนั้น และชิ้นส่วนจะถูกตัด ซึ่งต้องใช้การตัดเพียงสองครั้ง ${\displaystyle p\in [0,1]}$

โดยการใช้ขั้นตอนข้างต้นซ้ำๆ จะสามารถบรรลุการแบ่งส่วนโดยฉันทามติระหว่าง คู่ค้า n = 2 ราย และ กลุ่มย่อย k > 1 กลุ่มใดๆ จำนวนการตัดคือ. ${\displaystyle 2(k-1)}$

ณ ปี 2015 ยังไม่มีการสรุปทั่วไปของขั้นตอนการใช้มีดเคลื่อนที่นี้สำหรับ ตัวแทน n > 2 ตัว^{[ 13 ]}

สำหรับค่าที่กำหนดใดๆเราสามารถมอบชิ้นส่วนให้กับคู่ค้าแต่ละรายโดยที่คู่ค้าทุกรายเชื่อว่าค่าที่พวกเขามีแตกต่างกันน้อยกว่านั่นคือ สำหรับทุกiและทุกj : ^{[ 1 ] : 127} ${\displaystyle \varepsilon >0}$${\displaystyle \varepsilon }$

${\displaystyle |V_{i}(X_{j})-w_{j}|<\varepsilon }$

ขั้นตอนการแบ่งที่เกือบสมบูรณ์แบบนี้มีสองขั้นตอน ได้แก่การบดละเอียดและการบรรจุ

ขั้นตอนการหั่นเค้กเป็นชิ้นเล็กๆ: เป้าหมายคือการหั่นเค้กให้เป็นชิ้นเล็กๆ ("เศษเค้ก") โดยที่แต่ละคนจะกำหนดค่าให้กับเศษเค้กแต่ละชิ้นให้มีค่าไม่มากนัก วิธีการทำมีดังนี้ สมมติให้kเป็นค่าคงที่ ขอให้คู่หูคนที่ 1 หั่นเค้กเป็นkชิ้น โดยแต่ละชิ้นมีค่าเท่ากับ 1/ kขอให้คู่หูคนที่ 2 หั่นชิ้นเค้กเพิ่มเติมตามความจำเป็น (โดยใช้จำนวนครั้งไม่เกินk -1 ครั้ง) โดยที่แต่ละชิ้นมีค่าไม่เกิน 1/ kแน่นอนว่าชิ้นเค้กใหม่เหล่านี้ยังมีค่าไม่เกิน 1/ kสำหรับคู่หูคนที่ 1 ทำเช่นนี้ต่อไปกับคู่หูคนที่ 3, 4, ..., nสุดท้าย คู่หูทั้งn คนจะต้องกำหนดค่าให้ กับ เศษเค้กแต่ละชิ้นไม่เกิน 1/ k

ขั้นตอนการบรรจุ : เป้าหมายในที่นี้คือการแบ่งเศษขนมปังออกเป็นnเซตย่อย โดยที่ผลรวมของค่าในแต่ละเซตย่อยjจะใกล้เคียงกับw _jต่อไปนี้เป็นคำอธิบายเชิงลึกของขั้นตอนการบรรจุสำหรับคู่หูสองคน (อลิซและจอร์จ) เมื่อน้ำหนักเป็น 1/2 ^{[ 1 ] : 68–71}

1. เตรียมชามเปล่ามาหนึ่งใบ
2. ใส่เศษขนมปังชิ้นหนึ่งลงในชาม
3. ถ้ามูลค่าของเศษขนมในชามมีมากกว่าครึ่งหนึ่งของฝ่ายใดฝ่ายหนึ่ง ให้ส่งชามนั้นให้ฝ่ายที่ชนะ และให้เศษขนมที่เหลือแก่ฝ่ายอีกคน
4. มิฉะนั้น (มูลค่าในชามน้อยกว่า 1/2 สำหรับทั้งสองฝ่าย) หากมูลค่าในชามของอลิซมากกว่าของจอร์จ ให้หาเศษขนมปังที่มูลค่าสำหรับจอร์จมากกว่ามูลค่าสำหรับอลิซ (เศษขนมปังดังกล่าวต้องมีอยู่จริง เพราะผลรวมของมูลค่าของเศษขนมปังทั้งหมดเท่ากับ 1 ทั้งสำหรับอลิซและจอร์จ) เพิ่มเศษขนมปังนี้ลงในชาม แล้วกลับไปที่ขั้นตอนที่ 2

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

ในทางรูปแบบ แต่ละชิ้นส่วนสามารถแสดงเป็นเวกเตอร์ของค่าได้ หนึ่งค่าต่อคู่หู ความยาวของแต่ละเวกเตอร์มีขอบเขต กล่าวคือ สำหรับแต่ละเวกเตอร์v ดังกล่าว : . เป้าหมายของเราคือการสร้างเวกเตอร์ สำหรับคู่หู j แต่ละคู่ ซึ่งองค์ประกอบทั้งหมดอยู่ใกล้ w _jในการทำเช่นนี้ เราต้องแบ่งเวกเตอร์ออกเป็นเซตย่อย โดยที่ผลรวมของเวกเตอร์ในแต่ละเซตย่อยjจะใกล้เคียงกับเวกเตอร์ทั้งหมดซึ่งองค์ประกอบทั้งหมดคือw _j มาก พอ สิ่งนี้เป็นไปได้ด้วยทฤษฎีบทของ V.Bergström ^{[ 14 ] [ 1 ] : 126–128} ${\displaystyle ||v||\leq {\sqrt {n}}/k}$

ขั้นตอน Crumb-and-Pack เป็นขั้นตอนย่อยในโปรโตคอล Robertson-Webb โปรโตคอลหลังนี้สร้างการแบ่งเค้กที่ แม่นยำ เกือบสมบูรณ์แบบและปราศจากความอิจฉา

Brams และ Taylor ได้ให้คำอธิบายที่แตกต่างกันเกี่ยวกับขั้นตอนการบดและบรรจุ^{[ 15 ]}

ผลลัพธ์ส่วนใหญ่สำหรับกรณีที่มีข้อจำกัดเรื่องจำนวนการตัด มักมุ่งเน้นไปที่กรณีที่น้ำหนักเท่ากัน

การ ลดฉันทามติลงครึ่งหนึ่งโดยประมาณ εสามารถคำนวณได้ด้วยอัลกอริทึมที่อิงตามทฤษฎีบทของ Tuckerซึ่งเป็นเวอร์ชันแบบไม่ต่อเนื่องของทฤษฎีบทBorsuk-Ulam ^{[ 2 ]}การปรับอัลกอริทึมนี้แสดงให้เห็นว่าปัญหาอยู่ในระดับความซับซ้อนPPA ^{[ 16 ]} ซึ่งยังคงใช้ได้แม้กับการประเมินค่าแบบจำกัดและไม่เป็นอะตอม อย่างไรก็ตาม เวลาในการทำงานของอัลกอริทึมนี้อาจเป็นแบบเลขชี้กำลังตามพารามิเตอร์ ของปัญหา ในความเป็นจริง การลดฉันทามติลงครึ่งหนึ่งนั้นยากต่อการคำนวณในหลายแง่มุม

ขั้นแรก สมมติว่าεอนุญาตให้เป็นฟังก์ชันผกผันเลขชี้กำลังของn (นั่นคือ 1/ εเป็นฟังก์ชันเลขชี้กำลังของn ) จากนั้น การหาการลดฉันทามติโดยประมาณε ถือเป็น ปัญหา PPA-hardความยากนี้ยังคงมีอยู่แม้จะมีเงื่อนไขเพิ่มเติมดังต่อไปนี้: ^{[ 16 ]}

• ตัวแทนแต่ละตัวมีค่าประเมินคงที่แบบเป็นช่วงๆข้อมูลนำเข้าของปัญหาประกอบด้วยจุดปลายและค่าประเมินคงที่แบบเป็นช่วงๆ ของตัวแทนแต่ละตัว และตัวเลขทั้งหมด (รวมถึงความแม่นยำในการประมาณค่าε ) จะแสดงในรูปแบบเลขฐานสอง
• จำนวนชิ้นส่วนในการประเมินค่าคงที่แบบเป็นช่วงๆ นั้นเป็นพหุนามในn (ส่วนค่าเหล่านั้นอาจเป็นเลขชี้กำลังในn )
• อนุญาตให้ปัจจัยการประมาณค่าε เป็นพหุนามผกผันใน nได้^{[ 17 ]}
• การประเมินค่าของตัวแทนมีความสม่ำเสมอเป็นช่วงๆโดยมีเพียงสองบล็อก (อย่างไรก็ตาม เมื่อตัวแทนมีการประเมินค่าที่สม่ำเสมอเป็นช่วงๆ โดยมีเพียงบล็อกเดียว ปัญหาจะสามารถแก้ไขได้ในเวลาพหุนามแบบพาราเมตริกสำหรับ การตัด n ครั้งและในเวลาพหุนามสำหรับการตัด 2n - d ครั้ง สำหรับค่าคงที่ dใดๆ) ^{[ 18 ]}
• จำนวนตัวแทนเป็นค่าคงที่และอย่างน้อย 3 (อย่างไรก็ตาม แม้จะมีตัวแทน 2 ตัว ก็สามารถแก้ปัญหาได้ในเวลาพหุนาม) ^{[ 19 ]}

ต่อไป สมมติว่าεเป็นค่าคงที่ (ไม่ขึ้นอยู่กับn ) การหาการลดฉันทามติโดยประมาณε นั้นเป็น ปัญหา PPAD-hardซึ่งในทางทฤษฎีแล้วอ่อนกว่าปัญหา PPA-hard การพิสูจน์ทำได้โดยการลดรูปจากปัญหา Generalised Circuitโดยประมาณεความยากนี้ยังคงมีอยู่แม้ในเงื่อนไขต่อไปนี้:

• ค่าการประเมินเป็นค่าคงที่แบบเป็นช่วงๆ
• อนุญาตให้ใช้การตัดเพิ่มเติมจำนวนคงที่ (นั่นคือ เราค้นหาการแบ่งครึ่งฉันทามติสำหรับตัวแทนn รายโดยใช้การตัด n + dสำหรับค่าคงที่d บางค่า ) ^{[ 20 ]}
• เมื่อεเป็นค่าคงที่ ยังไม่แน่ชัดว่า การลดจำนวนลงครึ่งหนึ่งโดยประมาณตามฉันทามติ ε นั้นยากต่อ PPA หรือไม่ (ซึ่งยากกว่า PPAD) ^{[ 16 ]}
• นอกจากนี้ การตัดสินใจว่ามีการแบ่งครึ่งฉันทามติโดยประมาณε ที่มีการตัด n -1 หรือไม่นั้นเป็นปัญหา NP-hard แม้ว่าεจะเป็นค่าคงที่ก็ตาม การพิสูจน์ทำได้โดยการลดจาก3SAT ^{[ 20 ]}

เมื่อεเป็นค่าคงที่ สามารถคำนวณการประมาณค่าได้สองประเภทในเวลาพหุนาม อัลกอริทึมทำงานสำหรับการประเมินค่าแบบบวกทั่วไป (ไม่จำเป็นต้องเป็นค่าคงที่แบบเป็นช่วง) การประเมินค่าจะเข้าถึงได้โดยใช้การสอบถามในแบบจำลองการสอบถามของ Robertson–Webbรวมถึง การสอบถาม เครื่องหมายไปยังผลรวมของการประเมินค่า ทั้ง n รายการ ^{[ 3 ]}สามารถบรรลุการประมาณค่าต่อไปนี้ได้:

• การหาพาร์ทิชันที่ทำให้ตัวแทนแต่ละคนให้คุณค่ากับแต่ละส่วนอย่างน้อย 1/ 2nโดยใช้การตัดแบ่ง${\displaystyle n}$
• การหาพาร์ทิชันที่ทำให้ตัวแทนแต่ละคนให้คุณค่าแต่ละส่วนเท่ากับ 1/2 ± εโดยใช้การตัดในอัลกอริธึมออนไลน์หรือใช้การตัดในอัลกอริธึมออฟไลน์ ${\displaystyle O((n\log {n})/(\varepsilon ^{2}))}$${\displaystyle n\cdot \lceil 2+\log _{2}(1/\epsilon )\rceil }$
  • โปรดทราบว่ามีช่องว่างระหว่างความยากของ PPAD สำหรับ การตัด n + dครั้งสำหรับค่าคงที่d ใดๆ และอัลกอริทึมเวลาพหุนามสำหรับ 2 n +O(log( ε))
• เมื่อεเป็นค่าคงที่หรือพหุนามผกผันในn การแบ่งฉันทามติโดยประมาณε จะเทียบเท่ากับการคำนวณของปัญหา การแบ่งสร้อยคอ – แต่ละปัญหาสามารถลดรูปเป็นอีกปัญหาหนึ่งได้ในเวลาพหุนาม (ซึ่งหมายความว่าการแบ่งสร้อยคอเป็นปัญหา PPAD ที่ยาก) ^{[ 16 ]}
• หากเราสนใจที่จะค้นหา วิธีแก้ปัญหา ที่แน่นอนการแบ่งครึ่งฉันทามติจะยากขึ้นมาก การหาวิธีแก้ปัญหาด้วย การตัด nครั้งนั้นยากระดับ FIXP และการตัดสินใจว่ามีวิธีแก้ปัญหาด้วย การตัด n -1 ครั้งหรือไม่นั้นเป็นปัญหาระดับ ETR ที่สมบูรณ์^{[ 21 ]}
• เมื่อการประเมินค่าของตัวแทนแสดงด้วยวงจรพีชคณิต การลดฉันทามติโดย ประมาณεจะเทียบเท่ากับการคำนวณค่าประมาณของคำตอบที่แน่นอนของปัญหาการค้นหา Borsuk-Ulam ในเวลาพหุนาม ซึ่งหมายความว่ามันสมบูรณ์สำหรับคลาสความซับซ้อน BU ซึ่งเป็นคลาสใหญ่ของFIXPที่เกี่ยวข้องกับคำตอบของปัญหาที่มีการรับประกันการมีอยู่โดยทฤษฎีบท Borsuk-Ulam ^{[ 22 ]}

เมื่อทรัพยากรที่จะแบ่งไม่ใช่เค้ก แต่เป็นชุดของทรัพยากรที่แบ่งได้ ปัญหาจะง่ายขึ้น: ^{[ 23 ]}

• สำหรับตัวแทนที่มีอรรถประโยชน์แบบบวกจะมีอัลกอริทึมแบบเวลาพหุนามสำหรับการคำนวณการแบ่งครึ่งฉันทามติโดยมีการตัดไม่เกินnครั้ง และสำหรับการคำนวณ การแบ่ง k ฉันทามติโดยมี การตัดไม่เกิน ( k -1) n ครั้ง
• การคำนวณการลดจำนวนสมาชิกครึ่งหนึ่งโดยใช้จำนวนการตัดที่เหมาะสมที่สุดสำหรับกรณีที่กำหนดนั้นเป็นปัญหา NP-hard ยิ่งไปกว่านั้น การคำนวณการลดจำนวนสมาชิกครึ่งหนึ่งโดยใช้จำนวนการตัดไม่เกิน OPT + n - 1 ครั้ง โดยที่ OPT คือจำนวนการตัดที่เหมาะสมที่สุดสำหรับกรณีนั้น ก็ เป็นปัญหา NP-hard เช่นกัน
• การตัดจำนวนn ครั้งนั้น แทบจะแน่นอนว่า เป็น สิ่งจำเป็นสำหรับการแบ่งครึ่งตามฉันทามติ เมื่ออรรถประโยชน์ของตัวแทนถูกสุ่มมาจาก1การแจกแจงความน่าจะเป็น
• สำหรับเอเจนต์ที่มีฟังก์ชันอรรถประโยชน์แบบโมโนโทนที่ไม่สามารถบวกได้ การลดจำนวนเอเจนต์ลงครึ่งหนึ่งเพื่อสร้างฉันทามติยังคงยากในระดับ PPAD แต่มีอัลกอริธึมที่ใช้เวลาในการคำนวณแบบพหุนามสำหรับจำนวนเอเจนต์ที่กำหนดไว้

จากมุมมองด้านการคำนวณ ยังไม่มีข้อมูลมากนักเกี่ยวกับการคำนวณการหารลงตัวด้วยตัวแบ่งย่อยสำหรับโปรดทราบว่าปัญหาไม่จำเป็นต้องยากกว่าสำหรับเนื่องจากเราสามารถใช้ตัวแบ่งย่อยจำนวนมากขึ้นได้ สิ่งที่เรารู้ในปัจจุบันคือ: ${\displaystyle (k-1)n}$${\displaystyle k\geq 3}$${\displaystyle k\geq 2}$

• ปัญหาอยู่ที่ PPA- kสำหรับk ใด ๆ^{[ 24 ]}
• ปัญหาดังกล่าวเป็นปัญหา PPA-hard สำหรับk = 3 เมื่อ 1/ εอาจเป็นฟังก์ชันเลขชี้กำลังของn ^{[ 18 ]}

สามารถคำนวณการประมาณค่าสองประเภทโดยใช้จำนวนพหุนามของคำถาม Robertson-Webb ได้ : ^{[ 3 ]}

• การหาพาร์ทิชันที่ทำให้ตัวแทนแต่ละคนให้คุณค่ากับแต่ละส่วนอย่างน้อย 1/ knโดยใช้การตัด ใน อัลกอริทึม แบบ ออนไลน์${\displaystyle (k-1)n}$
  • ยังไม่มีข้อสรุปว่า 1/ knสามารถปรับปรุงให้ดีขึ้นได้หรือไม่ โดยเฉพาะอย่างยิ่ง ยังไม่มีข้อสรุปว่ามีอัลกอริทึมที่มีประสิทธิภาพ (แบบออนไลน์หรือออฟไลน์) ที่ทำให้ตัวแทนแต่ละตัวประเมินค่าแต่ละส่วนอย่างน้อย 1/ c ( k ) โดยที่ c(k) เป็นฟังก์ชันบางอย่างของk (ไม่ขึ้นอยู่กับn ) โดยใช้การตัดหรือไม่${\displaystyle (k-1)n}$
• การค้นหาพาร์ติชันที่ตัวแทนแต่ละคนให้คุณค่าแต่ละส่วนที่ 1/ k ± εโดยใช้การตัดในอัลกอริทึมออนไลน์หรือใช้การตัด^{[ 3 ] : มาตรา 6} ${\displaystyle O({\frac {kn\log {(kn)}}{\varepsilon ^{2}}})}$${\displaystyle n\cdot (k-1)\cdot \lceil 2+\log _{2}(3k/\epsilon )\rceil }$
  • ยังไม่แน่ชัดว่าจะสามารถปรับปรุงจำนวนการตัดได้หรือไม่ สำหรับอัลกอริธึมออนไลน์ ค่าต่ำสุดของจำนวนการตัดสำหรับk = 2 คือดังนั้นจึงมีช่องว่างแบบลอการิทึม${\displaystyle O({\frac {n}{\varepsilon ^{2}}})}$

ผลลัพธ์จากการคำนวณสำหรับการลดฉันทามติลงครึ่งหนึ่งโดยประมาณε สำหรับ เอเจนต์ n ตัว

#ชิ้นk	# ตัวแทนn	ความแม่นยำ 1/ ε	# การตัด	การประเมินมูลค่า	สถานะ
2	${\displaystyle n}$	${\displaystyle O({\text{poly}}(n))}$	${\displaystyle n}$	ต่อเนื่องใดๆ	ใน PPA [ 2 ] [ 20 ]
2	${\displaystyle n}$	${\displaystyle \Omega (1)}$	${\displaystyle n+d}$,${\displaystyle d\geq 0}$	ค่าคงที่แบบเป็นช่วง	PPAD-hard; [ 20 ] ตรวจสอบว่า PPA-hard หรือไม่
2	${\displaystyle n}$	${\displaystyle \Omega ({\text{poly}}(n))}$	${\displaystyle n+n^{1-d}}$,${\displaystyle d>0}$	แบบสม่ำเสมอเป็นช่วงๆ โดยมี 2 บล็อก	PPA-hard [ 18 ] (PPAD-hard; [ 20 ] PPA-hard สำหรับ; [ 16 ]${\displaystyle \varepsilon \in \Omega (2^{n})}$ PPA-hard สำหรับการประเมินค่าคงที่แบบเป็นช่วงๆ[ 17 ] )
2	${\displaystyle n}$	${\displaystyle O({\text{poly}}(n))}$	${\displaystyle n}$	แบบสม่ำเสมอเป็นช่วงๆ ด้วยบล็อก 1 บล็อก	พหุนามพาราเมตริก[ 18 ]
2	${\displaystyle n}$	${\displaystyle O({\text{poly}}(n))}$	${\displaystyle 2n-d}$,${\displaystyle d\geq 0}$	แบบสม่ำเสมอเป็นช่วงๆ ด้วยบล็อก 1 บล็อก	พหุนาม[ 18 ]
2	${\displaystyle n}$	${\displaystyle \Omega (1)}$	${\displaystyle n-1}$	ค่าคงที่แบบเป็นช่วง	NP-hard ตัดสินการมีอยู่[ 20 ]
2	${\displaystyle n}$	${\displaystyle \Omega (1)}$	${\displaystyle 2n}$	ค่าคงที่แบบเป็นช่วง	เปิด. [ 20 ]
2	${\displaystyle n}$	?	${\displaystyle n}$	วงจรพีชคณิต	การประมาณค่าที่แข็งแกร่งคือ BU a -สมบูรณ์[ 22 ]
2	${\displaystyle n}$	∞ [แน่นอน]	${\displaystyle n}$	วงจรพีชคณิต	FIXP-hard. [ 21 ]
2	${\displaystyle n}$	∞ [แน่นอน]	${\displaystyle n-1}$	วงจรพีชคณิต	ETR-สมบูรณ์เพื่อตัดสินการมีอยู่[ 21 ]
nคงที่:
2	2	${\displaystyle O({\text{poly}}(n))}$	${\displaystyle n}$	โมโนโทน	พหุนาม; พหุนาม #คำถาม[ 19 ]
2	3	${\displaystyle O({\text{poly}}(n))}$	${\displaystyle n}$	โมโนโทน	PPA-hard; จำนวนการสอบถามอย่างน้อยแบบเลขชี้กำลัง[ 19 ]
2	2	${\displaystyle O({\text{poly}}(n))}$	${\displaystyle n}$	ทั่วไป	PPA-hard; จำนวนการสอบถามอย่างน้อยแบบเลขชี้กำลัง[ 19 ]
k >2:
3	${\displaystyle n}$	${\displaystyle O({\text{poly}}(n))}$	${\displaystyle 2n}$	ค่าคงที่แบบเป็นช่วง	PPAD-hard. [ 18 ]
กำลังหลัก	${\displaystyle n}$	${\displaystyle O({\text{poly}}(n))}$	${\displaystyle (k-1)n}$	ค่าคงที่แบบเป็นช่วง	ใน PPA - k [ 24 ]

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

การแบ่งอย่างเท่าเทียมโดยมีน้ำหนักต่างกันนั้น ไม่ได้หมายความว่าจะยุติธรรมเสมอไป ย้อนกลับไปที่ตัวอย่างแรก หากชิ้นส่วน 20% มอบให้แก่อลิซ และอีกสองชิ้นส่วน (50% และ 30%) มอบให้แก่จอร์จ เห็นได้ชัดว่าไม่ยุติธรรมต่ออลิซ แต่การแบ่งแบบนี้สามารถนำมาใช้เป็นขั้นตอนย่อยสำหรับการตัดเค้กอย่างยุติธรรมได้

ในปัญหาการแบ่งเค้กระหว่างครอบครัว[ ^{25 ]}มี ตัวแทน nรายที่รวมกลุ่มกันเป็นkครอบครัว เป้าหมายคือการแบ่งเค้กออกเป็นkชิ้นและจัดสรรให้ครอบครัวละหนึ่งชิ้น เกณฑ์ความยุติธรรมตามธรรมชาติในบริบทนี้คือ^{สัดส่วน}ที่เป็นเอกฉันท์ซึ่งหมายความว่าสมาชิกทุกคนในทุกครอบครัวให้คุณค่าส่วนแบ่งของครอบครัวตนเองอย่างน้อย 1/ k (สำหรับเกณฑ์อื่นๆ และปัญหาที่เกี่ยวข้อง โปรดดูการแบ่งอย่างยุติธรรมระหว่างกลุ่ม ) ปัญหานี้เทียบเท่ากับการแบ่งที่แน่นอนในความหมายต่อไปนี้:

• สำหรับทุกค่าnและkวิธีแก้ปัญหาการแบ่งส่วนอย่างเป็นเอกฉันท์ตามสัดส่วนระหว่าง ตัวแทน n ( k -1)+1 คนที่จัดกลุ่มเป็นkครอบครัว บ่งชี้ถึงวิธีแก้ปัญหาการแบ่งส่วนที่แน่นอนระหว่าง ตัวแทน nคนด้วย ชิ้นส่วน kชิ้น (และน้ำหนักเท่ากัน) โดยเฉพาะอย่างยิ่ง หมายความว่าการแบ่งส่วนอย่างเป็นเอกฉันท์ตามสัดส่วนต้องใช้การแบ่งอย่างน้อยn -1 ครั้ง และการหาการแบ่งส่วนอย่างเป็นเอกฉันท์ตามสัดส่วนโดยประมาณนั้นเป็นปัญหา PPA-hard
• สำหรับnและk ทุก ค่า วิธีแก้ปัญหาการแบ่งที่แน่นอนระหว่าง ตัวแทน nตัวและ ชิ้นส่วน kชิ้น หมายถึงวิธีแก้ปัญหาการแบ่งตามสัดส่วนที่เป็นเอกฉันท์ระหว่างตัวแทน n+1 ตัวที่จัดกลุ่มเป็นkครอบครัว โดยเฉพาะอย่างยิ่ง หมายถึงการแบ่งตามสัดส่วนที่เป็นเอกฉันท์ที่แน่นอนสามารถทำได้ด้วยการตัด ( n -1)( k -1) ครั้ง และการหาการแบ่งตามสัดส่วนที่เป็นเอกฉันท์โดยประมาณอยู่ใน PPA จำนวนการตัดนั้นกระชับสำหรับk = 2 ครอบครัว แต่ไม่กระชับสำหรับk > 2 ^{[ 25 ]}

อัลกอริทึมใดๆ สำหรับการแบ่งฉันทามติขึ้นอยู่กับการวัดค่าที่รายงานโดยพันธมิตร หากพันธมิตรรู้ว่าอัลกอริทึมทำงานอย่างไร พวกเขาอาจมีแรงจูงใจที่จะโกหกเกี่ยวกับการวัดค่าของตนเพื่อให้ได้รับมากกว่าน้ำหนักของตน เพื่อป้องกันสิ่งนี้ควรใช้กลไกที่ซื่อสัตย์^{[ 4 ] [ 26 ]}

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

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

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

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

ชื่อ	พิมพ์	เค้ก	การประเมินมูลค่า[ 27 ]	#พันธมิตร ( n )	#เซตย่อย ( k )	#ตัดผม	น้ำหนัก
ออสติน	ขั้นตอนการใช้มีดเคลื่อนที่	ช่วงเวลา	คอน	2	มากมาย	${\displaystyle 2(k-1)}$(เหมาะสมที่สุด)	ใดๆ
เอกพันธุ์แบบแบ่งส่วน	ขั้นตอนแยก	เอกพันธุ์แบบแบ่งส่วน	คอน+แอด+พัล	มากมาย	มากมาย	จำนวนเขต	ใดๆ
ดูบินส์-สแปเนียร์	หลักฐานการมีอยู่	ใดๆ	คอน+แอด	มากมาย	มากมาย	ไร้ขอบเขต	ใดๆ
การลดลงครึ่งหนึ่งของฉันทามติ	กระบวนการอนันต์	ช่วงเวลา	คอน	มากมาย	2	n (เหมาะสมที่สุด)	เท่ากัน
การแยกสร้อยคอ	หลักฐานการมีอยู่	ช่วงเวลา	Con(+Add?)	มากมาย	มากมาย	${\displaystyle n(k-1)}$(เหมาะสมที่สุด)	เท่ากัน
สตรอมควิสต์-วูดอลล์	หลักฐานการมีอยู่	วงกลม	คอน+แอด	มากมาย	2	${\displaystyle 2n-2}$(เหมาะสมที่สุดสำหรับน้ำหนักบางระดับ)	ใดๆ
สโตน-ทูคีย์	หลักฐานการมีอยู่	nมิติ	Con(+Add?)	n	2	1 ครึ่งระนาบ	เท่ากัน
บดและบรรจุ	ขั้นตอนที่เกือบเหมือนเป๊ะ	ใดๆ	คอน+แอด	มากมาย	มากมาย	ไร้ขอบเขต	ใดๆ

• ปัญหาของแม่น้ำไนล์