TL;DR

เรื่องของเรื่อง เริ่มต้นจากที่ /me ได้ฟังปัญหา Cake Cutting Problem จาก Youtube channel Numberphile แล้วรู้สึกประทับใจมาก และเมื่อไม่นานมานี้ Haris Aziz & Simon Mackenzie(2016) สามารถแก้ไขปัญหานี้ได้สำเร็จเป็นที่เรียบร้อยแล้ว

วันอาทิตย์ที่แสนน่าเบื่อกลับมาอีกแล้ว ร่างการต้องการการพักผ่อน แต่มันเบื่อไปซะทุกเรื่อง เฮ้อออออออ~

คิดแล้วคิดอีกว่าจะเขียนบล๊อคนี้ดีไหม แต่ไหนๆมี มก. ทักว่าจะรออ่าน ฮึ๊บ ลุยกันซะหน่อย

เรื่องของเรื่อง เริ่มต้นจากที่ /me ได้ฟังปัญหา Cake Cutting Problem จาก Youtube channel Numberphile แล้วรู้สึกประทับใจมาก มันเป็นอีกหนึ่งปัญหาคลาสสิกของศตวรรษที่ 20 ที่เมื่อไม่นานมานี้ Haris Aziz & Simon Mackenzie(2016) สามารถแก้ไขปัญหานี้ได้สำเร็จเป็นที่เรียบร้อยแล้ว

"one of the most important open problems in 20th century mathematics" -- Garfunkel

The Problem statement

Cake Cutting Problem หรือ ปัญหาการตัดเค้ก พูดถึงปัญหาง่ายๆในการแบ่งเค้กยังไงให้เท่าเทียมกัน

สิ่งที่น่าสนใจ คือ เจ้าปัญหาเป็นที่พูดถึงกันในหลายๆสาขา ไม่ว่าจะเป็น Mathematics, Computer science หรือแม้กระทั้ง Economics

เราสามารถแทนที่ “เค้ก” ด้วย สินค้า, ที่ดิน, มรดก แก้ปัญหาความขัดแย้ง เพื่อให้ทุกฝ่ายได้ทรัพยากรอย่างเท่าเทียม //แต่เอาไปใช้ในการเมืองไม่ได้นะ เพราะมันไม่ใช่ Greedy-freeness

หรือแม้กระทั้งประยุกต์ไปใช้ในการแบ่ง CPU หรือ Disk สำหรับแต่ละ process ในคอมพิวเตอร์, (Fair scheduling, Resource allocation)

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

Allocation of a heterogeneous divisible good among multiple agents with possibly different preferences over different parts of the cake.

เพื่อทำให้คำว่า “เท่าเทียม” สำหรับแต่ละคน มีความหมายตรงกัน สำหรับในบล๊อคนี้ /me จะนิยาม “เท่าเทียม” ด้วย สิ่งที่เรียกว่า “Envy-freeness” หมายความว่า หลังจากแบ่งแล้ว แต่ละคนจะได้เค้กที่ตนเองพอใจ และ(ทุกคน)เชื่อว่าไม่มีใครได้มากกว่าที่ตัวเองได้

Each agent believes that (according to his/her measure) no other agent has received more than he/she has.

กำหนด \(F_u(c)\) เป็น valuation function ของ U โดยเมื่อ c แทนด้วยเค้กชิ้นที่จะทดสอบ โดยผลลัพย์ของ \(F_u(c)\) เป็นคะแนนความพอใจของ U ต่อ c ก้อนนั้น กำหนด \(x_i\) คือ เค้กที่ I ได้รับ

นิยาม Envy-freeness: \(\forall i \forall j : F_i(x_i) \geq F_i(x_j) 2\)

The Solution

จริงๆแล้ว Cake Cutting Problem โดยพูดถึงมาตั้งแต่ปี 1940s และมีคนเสนอวิธีการแบ่งมากมาย แต่ปัญหาสำคัญ คือ วิธีการส่วนใหญ่ต้องการการตัด infinity ครั้ง แปลว่า ถ้าต้องการแบ่งเค้กให้กับคน 100 คน /me อาจจะต้องใช้ทั้งชีวิตเพื่อแบ่งมัน Ummmmmm

แต่สิ่งที่ Haris Aziz และ Simon Mackenzie เสนอ คือ วิธีแบ่งเค้กสำหรับ n คน อย่างเท่าเทียม โดยใช้จำนวนการลงมีดจำกัดแค่จำนวนหนึ่ง ประมาณ n^n^n^n^n^n ครั้งเท่านั้นเอง #บางทีมันก็เยอะไปนะ แต่แปลว่า มันไม่ใช่ตลอดกาล อย่างที่เคยๆมี

เพื่อให้บล๊อคนี้สามารถเขียบจบใน 1 บล๊อค /me จะพูดถึงแค่ในกรณีการแบ่งสำหรับ 2 คนและ 3 คน และจะไม่พูดถึง Aziz/Mackenzie procedure ที่ใช้สำหรับ n คน เพราะอาจจะทำให้บล๊คนี้ซับซ้อน และยาวจนไม่มีใครอ่าน #นี้ไม่ได้แปลว่าปกติจะมีคนอ่านนะ

Case: 2 agents

สำหรับคำตอบในกรณีนี้ ปกติเราจะเรียกว่า Divide and Choose protocol โดยมีวิธีการง่ายๆ คือ ให้คนนึงแบ่ง อีกคนนึงเลือก

กำหนดให้มี 2 คน คือ A, B

• 1 ให้ A แบ่งเค้กเป็น 2 ชิ้นเท่าๆกัน (ตามความคิดของ A)

• 2 ให้ B เลือกชิ้นที่มีค่ากับตัวเองมากกว่า (ตามความคิดของ B)

WHy

ในมุมมองของ A ทั้ง 2 ชิ้นมีค่าเท่าๆกัน (เพราะแบ่งเองกับมือ) ดังนั้น A จึงพอใจกับสิ่งที่ตัวเองได้ ไม่ว่าจะได้ชิ้นไหนก็ตาม

ในมุมมองของ B ที่ได้เลือกชิ้นที่ดีที่สุดในสายตาตัวเอง ดังนั้น B จึงไม่เสียใจที่ A จะได้อีกชิ้นไป

More Math

กำหนด Fa(c) และ Fb(c) เป็น valuation function ของ A, B ตามลำดับ และ ca, cb เป็นเค้กที่ A, B ได้รับ ตามลำดับ

จาก #1 กำหนดให้เค้กโดนแบ่งเป็น c1, c2 ตามลำดับ

ตรวจสอบเงื่อนไข Envy-freeness

• Fa(ca) >= Fa(cb) จริง เพราะว่าจาก #1 จะได้ว่า Fa(c1) = Fa(c2) ไม่ว่า cb จะเป็น c1, c2 ก็ทำให้ประพจน์นี้เป็นจริง

• Fb(cb) >= Fb(ca) จริง เพราะว่าจาก #2 B ได้เลือกก่อน ดังนั้น cb จะต้องเป็นชิ้นที่มี Fb(cb) มากที่สุด

QED

Case: 3 agents

คนแรกที่ได้ชื่อว่าคิดวิธีการนี้เป็นคนแรกๆ คือ John Selfridge และ John Horton Conway (คนเดียวกับที่เสนอ Conway’s Game of Life) จึงเรียกวิธีการนี้ว่า Selfridge–Conway procedure

และเริ่มมีความซับซ้อนขึ้นมากกว่ากรณี 2 คนมาก

กำหนดให้มี 3 คน คือ A, B, C

1. ให้ A แบ่งเค้กเป็น 3 ชิ้นเท่าๆกัน (ตามความคิดของ A)

2. ให้ B เลือก 2 ชิ้นที่มีค่ามากที่สุด (ตามความคิดของ B) แล้วตัด(trim)ชิ้นทั้ง 2 ชิ้นมีค่าเท่าๆกัน (ตามความคิดของ B)

3. ให้ C เลือกชิ้นที่มีค่ามากที่สุด (ตามความคิดของ C) จาก 3 ชิ้น (ไม่นับส่วนที่โดนตัดออกไป)

4. ให้ B เลือก โดย
   • ในกรณีที่ C เลือกชิ้นที่มีโดน B ตัด แปลว่า B จะต้องเลือกอีกชิ้นที่ตัวเองไม่ได้ตัด
   • ในกรณีที่ C ไม่เลือกชิ้นที่มีโดน B ตัด แปลว่า B ต้องถูกบังคับเลือกชิ้นที่ตัวเองตัดไป
5. ยกเค้กชิ้นสุดท้ายให้ A

ถ้าเงื่อนไข คือ สามารถทิ้งเค้กบางส่วนได้ ก็ยอมทิ้ง ส่วนที่โดน trim แล้วก็จบ ทุกคนแฮปปี้

กรณีที่ไม่สามารถทิ้งบางส่วนได้

1. ให้ B/C ที่ไม่ได้เลือกชิ้นที่โดน B ตัดเป็นคนแบ่ง ส่วนที่เหลือออกเป็น 3 ส่วน

2. ถ้า B เป็นคนตัดใน 6 ให้ C เลือกชิ้นที่ตัวเองต้องการ ในทางกลับกันก็จะให้ B เลือก

3. ให้ A เลือก

4. ให้คนที่สุดท้ายเลือก

WHy

ในมุมมองของ A ที่แบ่งเค้กเอง ดังนั้น A จะพอใจกับสิ่งที่ตัวเองได้ ไม่ว่าจะได้ชิ้นไหนก็ตาม (ที่ไม่โดน trim)

ในมุมมองของ B หลังจากเลือก 2 ชิ้น ใหญ่ที่สุดใน #2 แล้วตัดออกให้มันเท่ากัน แปลว่า B พอใจไม่ว่าจะได้ชิ้นไหนก็ตาม 1 ใน 2 ชิ้นนี้ เพราะมันมีค่าพอๆกันในมุมมองของ B และ มีค่ามากกว่าอีกชิ้นที่ตัวเองไม่เลือก

ในมุมมองของ C ได้เลือกเค้กที่ตัวเองต้องการด้วยตัวเอง

และหลังจากแบ่งชิ้นที่เหลือจากการโดนตัดใน #2

ในมุมมองของ A ปกติก็พอใจกับสิ่งที่ตัวเองได้อยู่แล้ว ยิ่งได้เพิ่มก็ยิ่งพอใจมากกว่าเดิม

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

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

More Math

กำหนด Fa(c), Fb(c) และ Fc(c) เป็น valuation function ของ A, B และ C ตามลำดับ และ ca, cb และ cc เป็นเค้กที่ A, B, C ได้รับ ตามลำดับ

จาก #1 กำหนดให้เค้กโดนแบ่งเป็น c1, c2, c3 ตามลำดับ จาก #2 กำหนดให้ชิ้นที่ B เลือก คือ c1, c2 โดย Fb(c1) >= Fb(c2) แล้วตัด c1 เป็น c11 และ c12 โดย Fb(c11) = Fb(c2)

ตรวจสอบเงื่อนไข Envy-freeness ในส่วนแรก (ทิ้งส่วนที่เหลือไป)

• Fa(ca) >= Fa(cb) และ Fa(ca) >= Fa(cc) จริง เพราะว่าจาก #1 จะได้ว่า Fa(c1) = Fa(c2) = Fa(c3) ตราบเท่าที่ ca ไม่โดนบังคับเลือก c11 ประพจน์นี้จะเป็นจริง

• Fb(cb) >= Fb(ca) และ Fb(cb) >= Fb(cc) จริง เพราะว่าจาก #4 ถ้า cc=c11 แล้ว cb=c2 แต่ถ้า cc!=c11 แล้ว cb=c11 และจาก #2 Fb(c11) = Fb(c2) > Fb(c3) ดังนั้นไม่ว่า B จะได้ c11 หรือ c2 ก็ทำให้ประพจน์นี้เป็นจริง

• Fc(cc) >= Fc(ca) และ Fc(cc) >= Fc(cb) จริง เพราะว่าจาก #3 C ได้เลือกชิ้นที่ตัวเองต้องการด้วยตัวเอง ดังนั้น Fc(cc) จึงมีค่ามากกว่าทุกๆชิ้น

ตรวจสอบเงื่อนไข Envy-freeness ในส่วนที่ 2 (เก็บส่วนที่เหลือ)

กำหนด P แทน คนที่เลือกชิ้น c11 และ Q แทน คนที่ไม่ได้ c11 และไม่ใช่ A

จาก #4 A ไม่มีทางได้ c11 ดังนั้น P ไม่มีทางเป็น A และจากนิยาม Q ก็ไม่มีทางเป็น A ดังนั้น P, Q ต้องเป็น B หรือ C เท่านั้น

จากนิยาม P, Q ไม่ใช่คนเดียวกัน ดังนั้นสามารถเปลี่ยน กรุ๊ป A, B, C เป็น A, P, Q ได้

จาก #6 Q แบ่ง c12 เป็น c121, c122, c123 กำหนดให้ xa, xp, xq เป็นชิ้นที่ A, P, Q ได้ตามลำดับ

จะได้ว่า A ได้ ca+xa, P ได้ c11+xp และ Q ได้ cq+xq

• เงื่อนไขของ A

Fa(ca+xa) >= Fa(c11+xp) เพราะว่า

เพราะว่าจาก #6 จะได้ว่า c1 = c11 + c12 = c11 + c121 + c122 + c123 และ Fa(ca) = Fa(c1) > Fa(c11) และ c1 + xa > c11 + c12 ดังนั้น Fa(ca+xa) = Fa(c1+xa) > Fa(c11+c12) > Fa(c11+xp) ไม่ว่า xp จะเป็น c121, c122 หรือ c123

Fa(ca+xa) >= Fa(cq+xq) เพราะว่า

จากเงื่อนไขส่วนแรก Fa(ca) > Fa(cq) และจาก #8 จะได้ว่า A เลือกก่อน Q ดังนั้น Fa(xa) > Fa(xq) และ Fa(ca+xa) >= Fa(cq+xq)

• เงื่อนไขของ P

Fp(c11+xp) >= Fp(ca+xa) และ Fp(c11+xp) >= Fb(cq+xq) จริง เพราะ จากเงื่อนไขส่วนแรก Fp(c11) >= Fp(ca) และ Fp(c11) >= Fp(cq) และ จาก #7 P เป็นคนเลือกส่วนที่เหลือคนแรก ดังนั้น Fp(xp) >= Fp(xa) และ Fp(xp) >= Fp(xq)

• เงื่อนไขของ Q

Fq(cq+xq) >= Fq(ca+xa) และ Fq(cq+xq) >= Fq(c11+xp) จริง เพราะ จากเงื่อนไขส่วนแรก และ จาก #6 Q เป็นคนแบ่งเค้ก ดังนั้น Fq(xp) = Fq(xa) = Fq(xq)

QED

Conclusion

ถึงแม้ว่า Selfridge–Conway procedure จะทำงานได้เป็นอย่างดีสำหรับกรณีแค่ 2-3 คน แต่ก็เป็นพื้นฐานทำให้ Haris Aziz และ Simon Mackenzie แก้ปัญหานี้ได้ในกรณีทั่วไป

แต่อย่างไรก็ตาม ยังคงมีปัญหาอีกหลายๆอย่างรอให้ใครสักคนแก้มัน #

จริงๆแล้วปัญหานี้ ตั้งอยู่บนสมมติฐานหลายๆข้อ เช่น

• ถ้าได้ของมากขึ้น จะต้องพอใจขึ้น \(F_i(x+y) \geq F_i(x)\)
• ถ้า \(x = y + z\) แล้ว \(F_i(x) = F_i(y) + F_i(z)\)
• [เค้ก/ทรัพยากร] สามารถแบ่งได้ไม่จำกัดโดยไม่เสียคุณค่า

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

More Detail

อยากแนะนำให้ดู จุดเริ่มต้นของบล๊อคนี้

และสำหรับคนที่สนใจอ่านวิธีการในกรณี n คน

A Discrete and Bounded Envy-free Cake Cutting Protocol for Any Number of Agents