creatio ex nihilo

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

[Profile ทั้งหมด]

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




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

 
โจรสลัดแบ่งสมบัติ (เกม)









โจรสลัด n คน แต่ละคนมีฐานะไม่เท่าเทียมกัน โจรสลัดหมายเลข 1 คือ กัปตัน หมายเลข 2 ผู้ช่วยกัปตัน หมายเลข 3 เป็นคนที่มีฐานะรองลงมา สุดท้ายหมายเลข n คือโจรสลัดลูกเรือที่กระจอกที่สุด โจรสลัดกลุ่มนี้ปล้นได้เหรียญทองจำนวน m เหรียญ (m>n) ต่อไปเป็นวาระการแบ่งสมบัติกัน

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

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

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


โจทย์ปัญหาข้อนี้เป็นแบบฝึกหัดสำหรับนักเรียนที่เรียนวิชาทฤษฎีเกม วิธีคิดให้เริ่มจากกลุ่ม n ที่น้อยที่สุด เริ่มต้นด้วยการสมมติว่ามี 2 คน คือคนที่ n-1 กับคนที่ n กรณีนี้ชัดเจน 100% ครับ คนที่ n-1 ฮุบเอาไว้ทั้ง m โดยไม่แบ่งให้คนที่ n เพราะตัวเองโหวตให้ตัวเอง ก็มีคะแนนเสียงครึ่งหนึ่งพอดี ข้อเสนอผ่าน คนที่ n ไม่สามารถโต้แย้งได้ เพราะฉะนั้นสูงสุดของคนที่ n คือ 0 เหรียญ ถ้าหากคนที่ n ปล่อยให้เหลือเพียง 2 คน

กรณี 3 คน คือ คนที่ n-2, n-1 กับ n คนที่ n-2 และคนที่ n ต่างรู้ดีว่าหากคนที่ n-2 ถูกกำจัดไป เหรียญทั้งหมดจะตกอยู่กับคนที่ n-1 (ตามเหตุผลกรณีที่เหลือ 2 คน) เหตุการณ์แบบนี้คนที่ n-2 สามารถซื้อตัวคนที่ n ได้ด้วยเหรียญ 1 เหรียญ แล้วตัวเองรับไป m-1 เหรียญ โดยไม่แบ่งให้คนที่ n-1 สักแดงเดียว ซึ่งคนที่ n ก็ต้องยอมรับ 1 เหรียญ ถ้าไม่รับ 1 เหรียญ ตัวเองก็จะไม่ได้อะไรเลย สำหรับคนที่ n-1 แม้ไม่ยอม ก็ไม่อาจทำอะไรได้ เกมดำเนินไปตามกติกา

กรณี 4 คน คือ คนที่ n-3, n-2, n-1 กับ n คนที่ n-3 และคนที่ n-1 ต่างรู้ว่า ถ้าหากกำจัดคนที่ n-3 ไป ทั้งคู่จะไม่ได้อะไรเลย (ตามเหตุผลกรณีมี 3 คน) ดังนั้นคนที่ n-3 จะเสนอเหรียญ 1 เหรียญให้คนที่ n-1 ส่วนตัวเองเก็บไว้ m-1 เหรียญ คนที่ n-2 และคนที่ n ไม่ได้อะไรเลย

ทำนองเดียวกัน คนที่ n-4 ต้องให้เหรียญกับคนที่ n-2 และ n คนละ 1 เหรียญ

ดังนั้น ถ้า n เป็นจำนวนคู่
ให้คนที่ 1 เอาเงินไป m - (n/2) + 1 เหรียญ
คนที่ 2, 4, 6, 8, ..., n เอาเงินไป 0 เหรียญ
คนที่ 3, 5, 7, 9, ..., n-1 เอาเงินไป 1 เหรียญ

ถ้า n เป็นจำนวนคี่
ให้คนที่ 1 เอาเงินไป m - [(n-1)/2] เหรียญ
คนที่ 2, 4, 6, 8, ..., n-1 เอาเงินไป 0 เหรียญ
คนที่ 3, 5, 7, 9, ..., n เอาเงินไป 1 เหรียญ





Create Date : 17 มกราคม 2551
Last Update : 17 มกราคม 2551 14:10:18 น. 2 comments
Counter : 3595 Pageviews.

 
ไม่เคยเรียนวิชาทฤษฎีเกม เคยเรียนแต่ Beer Game ค่ะ


โดย: Michiru วันที่: 17 มกราคม 2551 เวลา:12:51:19 น.  

 
โจทย์ข้อนี้ไม่ได้เห็นมานานเเล้ว

พอเห็นคิดถึงคนสอนครับ...


โดย: มหาสำลี วันที่: 17 มกราคม 2551 เวลา:22:43:33 น.  

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