creatio ex nihilo

ศล
Location :
กรุงเทพ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 85 คน [?]




Group Blog
 
All Blogs
 
Friends' blogs
[Add ศล's blog to your web]
Links
 

 
cut-and-choose



คำถามคลาสสิกเวลาเห็นเค้กคือเกมแบ่งเค้ก ถ้ามีคนสองคน เราจะแบ่งเค้กออกเป็นสองก้อนยังไงให้ยุติธรรม ผมเดาว่าใครก็ตามที่กำลังอ่านตอนนี้รู้คำตอบอยู่แล้วล่ะ กลยุทธ์ cut-and-choose ให้คนแรกเป็นคนแบ่งเค้ก แล้วคนที่สองเป็นคนเลือกก่อนว่าจะเอาเค้กก้อนไหน (ทำไมมันถึงยุติธรรม? คุณตอบได้) แล้วถ้ามี 3 คนล่ะ บางคนอาจนึกถึงวิธีคลาสสิกของ Steinhaus

1. คนแรกแบ่งเค้กเป็น 3 ก้อนที่เขาคิดว่าเท่า ๆ กัน
2. คนที่สอง ถ้าเห็นว่ามีเค้กอย่างน้อย 2 ก้อนที่ขนาดไม่ต่ำกว่า 1/3 ของเค้กก้อนก่อนแบ่ง ก็จะไม่ทำอะไร แต่ถ้าเห็นว่ามีเค้ก 2 ก้อนที่น้อยอย่างน่าเกลียด เขาก็จะบอกว่า 2 ก้อนไหนที่น่าเกลียด
3. ถ้าเป็นกรณีที่คนที่สองไม่ทำอะไรในข้อ 2. เราก็ให้คนที่สามเป็นคนเลือกคนแรก คนที่สองเป็นคนเลือกอีกสองก้อนที่เหลือ (ซึ่งเขาจะได้หนึ่งก้อนที่เขาคิดว่าไม่ต่ำกว่า 1/3 แน่ ๆ) และเค้กก้อนที่เหลือก้อนสุดท้ายเป็นของคนแรก (นั่นคือทั้ง 3 คนจะได้เค้กที่มีขนาดไม่ต่ำกว่า 1/3 จากการวัดของตัวเอง)
4. ถ้าเป็นกรณีที่คนที่สองบอกว่าเค้ก 2 ก้อนไหนที่น้อยอย่างน่าเกลียด เราก็จะถามคนที่สามแบบเดียวกับถามคนที่สองในข้อ 2. โดยที่เราบอกคนที่สามว่าไม่ต้องสนใจว่าคนที่สองบอกว่าเค้ก 2 ก้อนไหนน่าเกลียด
5. ถ้าคนที่สามไม่ทำอะไรจากข้อ 4. เราก็ให้คนที่สองเลือกเค้กเป็นคนแรก แล้วคนที่สามเลือกเค้กเป็นคนที่สอง และเค้กก้อนสุดท้ายเป็นของคนแรก
6. แต่ถ้าคนที่สามเห็นว่ามีเค้ก 2 ก้อนที่น้อยจากข้อ 4. เขาก็จะบอกว่า 2 ก้อนไหนที่น้อย ซึ่งแน่นอนว่า จะต้องมีเค้กอย่างน้อยหนึ่งก้อนที่เลือกตรงกับคนที่สองจากข้อ 2. เราให้เค้กที่ทั้งคู่เห็นตรงกันว่าเป็นเค้กก้อนเล็กแก่คนแรก (ในสายตาของคนแรกย่อมไม่เป็นเช่นนั้น เพราะเขาแบ่งเท่า ๆ กันทั้งสามก้อน)
7. เอาเค้ก 2 ก้อนที่เหลือมารวมกัน แล้วให้คนที่สองกับคนที่สามแบ่งกันด้วยเทคนิค cut-and-choose

เกือบยี่สิบปีต่อมา Selfridge กับ Conway เสนอ envy-free protocol สำหรับกรณี 3 คน ดังนี้ (การแบ่งเค้กจะถือว่าเป็น envy-free ก็ต่อเมื่อทุกคนมีวิธีที่จะทำให้ได้เค้กที่ตัวเองคิดว่ามีขนาดเท่ากับเค้กชิ้นใหญ่ที่สุด, กรณี cut-and-choose ในแง่หนึ่งเราพูดว่ายุติธรรม ยุติธรรมในแง่ที่ทุกคนพอใจ ถึงจะไม่พอใจก็ไม่มีข้ออ้างว่าไม่ยุติธรรม เพราะคนแรกตัดเองนี่ คนที่สองก็ได้เลือกก่อนแล้วนี่ แต่มันไม่ได้รับประกันว่าคุณจะได้เค้กที่มีขนาดเท่ากับเค้กก้อนใหญ่ที่สุด)

1. คนแรกแบ่งเค้กเป็น 3 ก้อนที่เขาถือว่าเท่ากัน
2. ถ้าคนที่สองเห็นว่า มีเค้กอย่างน้อย 2 ก้อนมีขนาดเท่ากันและเป็น 2 ก้อนที่มีขนาดใหญ่ที่สุด เขาก็จะไม่ทำอะไร แต่ถ้าคนที่ 2 เห็นว่ามีเค้กก้อนใหญ่ที่สุดเพียงก้อนเดียว เขาจะใช้มีดตัดเค้กก้อนนั้นให้มีขนาดเท่ากับเค้กที่ใหญ่เป็นอันดับสอง เค้กส่วนที่ถูกเขาตัดออกเราจะเรียกว่า L
3. เราให้คนที่สาม สอง หนึ่ง เลือกเค้กตามลำดับ โดยที่ ถ้าคนที่สามไม่เลือกเค้กก้อนที่โดนคนที่สองตัด คนที่สองต้องถูกบังคับให้เลือกชิ้นนั้น ซึ่งคนที่สองก็ต้องเต็มใจรับ เพราะเขาเป็นคนทำให้เกิดเค้กที่ใหญ่ที่สุด 2 ก้อนที่มีขนาดเท่ากันด้วยตัวเขาเอง ตอนนี้เค้กทั้ง 3 ถูกแบ่งให้ 3 คนโดยที่ทั้งสามคนเห็นว่าส่วนของตัวเองเท่ากับส่วนที่ใหญ่ที่สุด ต่อมา เราจะต้องหาทางแบ่ง L
4. กรณีที่คนที่สองไม่ได้ทำอะไรในข้อ 2. ก็จบเกม เพราะไม่มี L แต่ถ้าเป็นกรณีที่มี L นั่นหมายความว่า ไม่คนที่สามก็คนที่สองที่จะได้เค้กก้อนที่โดนคนที่สองตัด ในสองคนนี้ เราจะให้คนที่ได้เค้กก้อนที่ไม่โดนคนที่สองตัดเป็นคนแบ่ง L ออกเป็น 3 ชิ้นเท่า ๆ กัน และเราจะเรียกคนที่แบ่ง L ว่า A, เรียกอีกคนหนึ่งว่า B
5. เค้ก 3 ชิ้นที่ A แบ่ง L ถูกเลือกโดย B, คนแรก และ A ตามลำดับ (B เป็นคนเลือกคนแรกจึงไม่มีเหตุผลที่จะต้องอิจฉาใคร และคนแรกไม่อิจฉา B เพราะ เขาคิดว่า L บวกกับเค้กส่วนที่ B ได้ในรอบแรกนั้นเท่ากับเค้กก้อนของเขา แต่นี่เขายังได้บางส่วนของ L มาอีก เขาย่อมได้เปรียบ B)

:))

ผมกินเค้กหมดก่อนเขียนจบย่อหน้าที่สามเสียอีก


Create Date : 08 ธันวาคม 2556
Last Update : 8 ธันวาคม 2556 7:37:45 น. 0 comments
Counter : 924 Pageviews.

ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
  *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.