ค่าแชปลีย์

ค่าแชปลีย์ เป็นแนวคิดในการแก้ปัญหาในทฤษฎีเกมแบบร่วมมือ โดยได้รับการตั้งชื่อตาม ลอยด์ แชปลีย์ เพื่อเป็นเกียรติให้แก่เขาซึ่งได้แนะนำแนวคิดนี้ในปี 1951 และได้รับรางวัลโนเบลสาขาเศรษฐศาสตร์ในปี ค.ศ. 2012 สำหรับผลงานนี้

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

 นิยามอย่างเป็นทางการ 
เกมการรวมกลุ่ม (coalitional game) ถูกนิยามอย่างเป็นทางการดังนี้:
มีเซต N (ของผู้เล่น n คน) และฟังก์ชัน  ที่ส่งเซตย่อยของผู้เล่นไปยังจำนวนจริง:  โดยที่  ซึ่ง  หมายถึงเซตว่าง ฟังก์ชัน  นี้เรียกว่า ฟังก์ชันลักษณะเฉพาะ (characteristic function)

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

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




โดยที่ n คือจำนวนผู้เล่นทั้งหมดและผลรวมจะครอบคลุมทุกเซตย่อย S ของ N ที่ไม่รวมผู้เล่น i (รวมถึงเซตว่างด้วย) โปรดทราบว่า  คือตัวประกอบทวินาม (binomial coefficient) สูตรนี้สามารถตีความได้ดังนี้: ลองนึกภาพกลุ่มพันธมิตรกำลังก่อตัวขึ้นทีละผู้เล่น โดยที่แต่ละผู้เล่นเรียกร้องส่วนแบ่งที่ยุติธรรมตามที่พวกเขามีส่วนร่วม  และจากนั้นจะใช้ค่าเฉลี่ยของการมีส่วนร่วมนี้สำหรับแต่ละผู้เล่นในลำดับการรวมกลุ่มพันธมิตร

สูตรทางเลือกสำหรับค่าแชปลีย์ คือ:



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



 ในแง่ของการทำงานร่วมกัน 
จาก ฟังก์ชันลักษณะเฉพาะ  สามารถคำนวณ การทำงานร่วมกัน ที่ผู้เล่นแต่ละกลุ่มมีให้ได้ Synergy คือฟังก์ชันที่ไม่ซ้ำ  ที่ทำให้



สำหรับทุกเซตย่อย  กล่าวอีกนัยหนึ่งคือ 'ค่ารวม' ของกลุ่มพันธมิตร  มาจากการรวม synergies ของเซตย่อยทุกเซตของ 

ฟังก์ชันการทำงานร่วมกัน (synergy)  ถูกคำนวณโดยใช้



ตามหลักการของการรวม-แยก (Inclusion-exclusion principle) กล่าวอีกนัยหนึ่งการทำงานร่วมกันของกลุ่มพันธมิตร  คือค่า  ที่ไม่ถูกนับจากเซตย่อย

ค่าแชปลีย์ สามารถนิยามในแง่ของฟังก์ชันการทำงานร่วมกันได้โดย



ซึ่งผลรวมนี้จะครอบคลุมเซตย่อย  ทั้งหมดของ  ที่รวมผู้เล่น 

สิ่งนี้สามารถตีความได้ว่า



กล่าวอีกนัยหนึ่งการทำงานร่วมกันของแต่ละกลุ่มพันธมิตรจะแบ่งเท่า ๆ กันระหว่างสมาชิกทั้งหมด

 ตัวอย่าง 

 ตัวอย่างทางธุรกิจ 
พิจารณาคำอธิบายที่เรียบง่ายของธุรกิจ เจ้าของ o ให้ทุนที่สำคัญในแง่ที่ว่า ถ้าไม่มีเขาหรือเธอจะไม่มีผลกำไรสามารถเกิดขึ้นได้ มีคนงาน m คน w1, ..., wm แต่ละคนมีส่วนร่วมจำนวน p ต่อกำไรรวม



ฟังก์ชันค่า (value function) สำหรับเกมการรวมกลุ่มนี้คือ

การคำนวณค่าแชปลีย์ สำหรับเกมกลุ่มนี้ทำให้ได้ค่า  สำหรับเจ้าของและ  สำหรับแต่ละคนใน m คนงาน

ซึ่งสามารถเข้าใจได้จากมุมมองของการทำงานร่วมกัน ฟังก์ชันการทำงานร่วมกัน  คือ

ดังนั้นกลุ่มพันธมิตรที่สร้างการทำงานร่วมกันได้ มีเพียงการจับคู่หนึ่งต่อหนึ่งระหว่างเจ้าของและคนงานแต่ละคน

การใช้สูตรค่าแชปลีย์ข้างต้นตาม  เราคำนวณได้ว่า



และ


ผลลัพธ์นี้ยังสามารถเข้าใจได้จากมุมมองของการเฉลี่ยในลำดับทั้งหมด คนงานแต่ละคนเข้าร่วมกลุ่มหลังจากเจ้าของ (และดังนั้นจึงมีส่วนร่วม p) ในครึ่งหนึ่งของลำดับ ดังนั้นค่าเฉลี่ยการมีส่วนร่วมของเขาคือ  เมื่อลงมาในกลุ่ม เจ้าของจะเข้ามาโดยเฉลี่ยเมื่อคนงานครึ่งหนึ่งได้เข้าร่วมแล้ว ดังนั้นค่าเฉลี่ยการมีส่วนร่วมของเจ้าของเมื่อลงมาในกลุ่มคือ 

 เกมถุงมือ 
เกมถุงมือ (Glove game) เป็นเกมการรวมกลุ่มที่ผู้เล่นมีถุงมือซ้ายและขวา และเป้าหมายคือการจับคู่ถุงมือขวาและซ้ายมาอยู่ด้วยกัน

ให้

โดยที่ผู้เล่น 1 และ 2 มีถุงมือขวา และผู้เล่น 3 มีถุงมือซ้าย

ฟังก์ชันค่า (value function) สำหรับเกมการรวมกลุ่มนี้คือ

สูตรในการคำนวณค่าแชปลีย์คือ



โดยที่  เป็นการจัดลำดับของผู้เล่นและ  คือเซตของผู้เล่นใน  ที่มาก่อน  ในลำดับ 

ตารางด้านล่างแสดงการมีส่วนร่วมของ Player 1



สังเกตว่า



โดยการใช้ข้อโต้แย้งด้านความสมมาตร (symmetry argument) สามารถแสดงได้ว่า



ตามหลักการของประสิทธิภาพ (efficiency axiom) ผลรวมของค่าแชปลีย์ ทั้งหมดจะเท่ากับ 1 ซึ่งหมายความว่า



 คุณสมบัติ 
ค่าแชปลีย์มีคุณสมบัติที่น่าพอใจหลายประการ โดยเฉพาะอย่างยิ่งเป็นกฎการจ่ายเงินเพียงอย่างเดียวที่เป็นไปตามคุณสมบัติทั้งสี่ของ ประสิทธิภาพ (Efficiency), ความสมมาตร (Symmetry), ความเป็นเส้นตรง (Linearity) และผู้เล่นที่ไม่มีผล (Null player)
ดูเพิ่มเติม สำหรับการจำแนกค่าแชปลีย์

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


การพิสูจน์: 

เนื่องจาก  เป็นการรวมแบบเทเลสโคป (telescoping sum) และมีการจัดลำดับ |N|! ลำดับต่าง ๆ

 ความสมมาตร (Symmetry) 
หาก  และ  เป็นตัวแทนสองคนที่เทียบเท่ากันในแง่ที่ว่า


สำหรับทุกชุด  ของ  ที่ไม่รวม  หรือ  ก็จะมี 

คุณสมบัตินี้ยังเรียกว่า การปฏิบัติต่อเท่าเทียมกัน (equal treatment of equals) 

 ความเป็นเส้นตรง (Linearity) 
หากเกมกลุ่มสองเกมที่อธิบายด้วยฟังก์ชันผลกำไร  และ  ถูกผสมกัน ผลกำไรที่แจกจ่ายควรตรงกับผลกำไรที่ได้จาก  และผลกำไรที่ได้จาก :


สำหรับทุก  ใน  นอกจากนี้ สำหรับจำนวนจริง ,

สำหรับทุก  ใน 

 ผู้เล่นที่ไม่มีผล (Null player) 
ค่าแชปลีย์  ของผู้เล่นที่ไม่มีผล  ในเกม  เท่ากับศูนย์ ผู้เล่น  ถือเป็น ผู้เล่นที่ไม่มีผล ใน  หาก  สำหรับกลุ่มพันธมิตร  ทั้งหมดที่ไม่รวม 

 การทดสอบแบบอิสระ (Stand-alone test) 
หาก  เป็นฟังก์ชันเซ็ตที่ไม่เพิ่มค่า (subadditive set function), เช่น , แล้วสำหรับแต่ละตัวแทน : 

ในทำนองเดียวกัน, หาก  เป็นฟังก์ชันเซ็ตที่เพิ่มค่า (superadditive set function), เช่น , แล้วสำหรับแต่ละตัวแทน : 

ดังนั้น, หากความร่วมมือมีผลลัพธ์ภายนอกที่เป็นบวก ตัวแทนทั้งหมดจะได้รับ (อย่างน้อย) การเพิ่มขึ้น และหากมีผลลัพธ์ภายนอกที่เป็นลบ ตัวแทนทั้งหมดจะได้รับ (อย่างน้อย) การลดลง

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

 ความมาร์จินัล (Marginalism) 
ค่าแชปลีย์ สามารถกำหนดเป็นฟังก์ชันที่ใช้เฉพาะการมีส่วนร่วมของมาร์จินัลของผู้เล่น  เป็นอาร์กิวเมนต์

 ค่าออน์–แชปลีย์ (Aumann–Shapley) 
ในหนังสือปี 1974 ของลอยด์ แชปลีย์ และโรเบิร์ต ออมันน์ ได้ขยายแนวคิดของค่าแชปลีย์ไปยังเกมที่ไม่มีที่สิ้นสุด (ซึ่งกำหนดตามเมเชอร์ (measure) ที่ ไม่ใช่อะตอม) โดยสร้างสูตรแนวทแยง (diagonal formula) ซึ่งต่อมาขยายโดยฌอง-ฟรองซัวส์ แมร์เต็นส์ และอับราฮัม เนย์มาน

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

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



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

โดยสมมติว่าฟังก์ชันการมีคุณค่าเป็นไปตามระเบียบบางประการเช่น สมมติว่า  สามารถแสดงเป็นฟังก์ชันที่มีการแยกต่างหากของเมเชอร์ที่ไม่เป็นอะตอมบน , ,  โดยที่ฟังก์ชันความหนาแน่น , โดยที่  ( คือฟังก์ชันลักษณะของ ) ภายใต้เงื่อนไขเหล่านี้

 ,

ตามที่สามารถแสดงได้โดยการประมาณความหนาแน่นโดยฟังก์ชันขั้นตอนและรักษาสัดส่วน  สำหรับแต่ละระดับของฟังก์ชันความหนาแน่น และ



สูตรแนวทแยงมีรูปแบบที่พัฒนาโดย ออมันน์ และ แชปลีย์ (1974)



ที่กล่าวถึง  สามารถเป็นค่าดัชนี (vector valued) (ตราบใดที่ฟังก์ชันถูกกำหนดและสามารถแยกได้ในช่วงของ , สูตรข้างต้นมีความหมาย)

ในอาร์กิวเมนต์ข้างต้น หากเมเชอร์มีอะตอม  จะไม่เป็นจริงอีกต่อไป—นี่คือเหตุผลที่สูตรแนวทแยงมักใช้กับเกมที่ไม่มีอะตอม

มีสองวิธีที่ใช้ขยายสูตรแนวทแยงนี้เมื่อฟังก์ชัน  ไม่สามารถแยกได้ เมอร์เทนส์ (Mertens) กลับไปที่สูตรดั้งเดิมและทำการแยกหลังจากการรวม ซึ่งจะได้รับผลจากการปรับเรียบอย่างมีประสิทธิภาพ เนย์แมน (Neyman) ใช้แนวทางที่แตกต่างออกไปโดยกลับไปที่การใช้ แนวทางของเมอร์เทนส์ (Mertens's approach) จาก เมอร์เทนส์ (1980) :



สิ่งนี้ใช้ได้กับเกมส่วนใหญ่—ในขณะที่สูตรแนวทแยงดั้งเดิมไม่สามารถใช้ได้โดยตรง เมอร์เทนส์ ขยายเพิ่มเติมโดยการระบุความสมมาตรที่ค่าแชปลีย์ควรเป็นอิสระ และเฉลี่ยตามความสมมาตรเหล่านี้เพื่อสร้างผลการปรับเรียบเพิ่มเติมที่สลับการเฉลี่ยกับการดำเนินการแยกอย่างที่กล่าวไว้ข้างต้น การสำรวจค่าไม่ใช่อะตอม (non-atomic) พบในงานของเนย์แมน (Neyman, 2002)

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



ในแง่ของฟังก์ชันการทำงานร่วมกัน  ข้างต้น สามารถเขียนได้เป็น



โดยที่การรวมไปยังทุกชุด  ของ  ที่มี 

สูตรนี้แนะนำว่าค่าแชปลีย์ของกลุ่ม สามารถคิดได้ว่าเป็นค่าแชปลีย์มาตรฐานของผู้เล่นคนเดียว หากกลุ่ม  ถูกปฏิบัติเหมือนเป็นผู้เล่นคนเดียว

 มูลค่าของผู้เล่นต่อผู้เล่นอื่น 
ค่าแชปลีย์ ถูกแยกออกเป็น ในรูปของเมทริกซ์ค่า



แต่ละค่า  แสดงถึงมูลค่าของผู้เล่น  ต่อผู้เล่น  เมทริกซ์นี้ทำให้เห็นว่า



กล่าวคือ มูลค่าของผู้เล่น  ต่อเกมทั้งหมดเป็นผลรวมของมูลค่าที่ผู้เล่น  มีต่อผู้เล่นแต่ละคน

ในแง่ของความร่วมมือ  ที่กำหนดไว้ข้างต้น สามารถเขียนได้ว่า



โดยที่การรวมไปยังทุกชุด  ของ  ที่มี  และ 

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

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

 การถดถอยค่าแชปลีย์ 
การถดถอยค่าแชปลีย์ เป็นวิธีทางสถิติที่ใช้เพื่อวัดการมีส่วนร่วมของตัวแปรแต่ละตัวในแบบจำลองการถดถอย ในบริบทนี้ "ผู้เล่น" คือ ตัวแปรหรือพรีดิคเตอร์แต่ละตัวในแบบจำลอง และ "กำไร" คือ ความแปรปรวนที่อธิบายทั้งหมดหรือพลังการคาดการณ์ของแบบจำลอง วิธีนี้รับประกันการกระจายกำไรทั้งหมดอย่างเป็นธรรมระหว่างตัวพรีดิคเตอร์ โดยการมอบค่าที่แทนการมีส่วนร่วมของแต่ละตัวพรีดิคเตอร์ในประสิทธิภาพของแบบจำลอง ลิโปเวตสกี (Lipovetsky, 2006) ได้อภิปรายการใช้ค่าแชปลีย์ ในการวิเคราะห์การถดถอย โดยให้ภาพรวมที่ครอบคลุมเกี่ยวกับพื้นฐานทฤษฎีและการใช้งานจริง

การมีส่วนร่วมของค่าแชปลีย์ ได้รับการยอมรับในเรื่องความสมดุลของเสถียรภาพและพลังในการแยกแยะ ซึ่งทำให้เหมาะสมในการวัดความสำคัญของคุณลักษณะการบริการในการวิจัยตลาดอย่างแม่นยำ การศึกษาหลายชิ้นได้นำการถดถอยค่าแชปลีย์ ไปใช้ในการวิเคราะห์ปัจจัยหลักในการวิจัยการตลาด โปครีเชฟสกายา และอันตีปอฟ (Pokryshevskaya และ Antipov, 2012) ใช้วิธีนี้ในการวิเคราะห์เจตนาการซื้อซ้ำของลูกค้าออนไลน์ แสดงให้เห็นถึงประสิทธิภาพในการเข้าใจพฤติกรรมของผู้บริโภค เช่นเดียวกัน อันตีปอฟ และโปครีเชฟสกายา (Antipov และ Pokryshevskaya, 2014) ได้นำการถดถอยค่าแชปลีย์ ไปใช้ในการอธิบายความแตกต่างในอัตราการแนะนำโรงแรมในไซปรัสใต้ โดยเน้นประโยชน์ในอุตสาหกรรมการบริการ การตรวจสอบเพิ่มเติมเกี่ยวกับประโยชน์ของค่าแชปลีย์ในการวิเคราะห์ปัจจัยหลักได้แก่ Vriens, Vidden และ Bosch (2021) ที่เน้นข้อดีในการวิเคราะห์การตลาดที่ใช้จริง

 ในการเรียนรู้ของเครื่อง 
ค่าแชปลีย์ให้วิธีการที่มีหลักการในการอธิบายการคาดการณ์ของแบบจำลองที่ไม่เป็นเชิงเส้นซึ่งเป็นที่นิยมในสาขาการเรียนรู้ของเครื่อง โดยการตีความแบบจำลองที่ฝึกฝนด้วยชุดของคุณลักษณะเป็นฟังก์ชันค่าในกลุ่มผู้เล่น ค่าแชปลีย์จะช่วยให้คำนวณได้ว่าคุณลักษณะใดมีส่วนช่วยในการคาดการณ์ หรือมีส่วนช่วยในความไม่แน่นอนของการคาดการณ์ วิธีนี้รวมหลายวิธีอื่น ๆ เช่น Locally Interpretable Model-Agnostic Explanations (LIME) DeepLIFT และ Layer-Wise Relevance Propagation

 อ่านหนังสือเพิ่ม 


 ดูเพิ่ม 
 ปัญหาสนามบิน
 ดัชนีพลังของบานซาฟ
 ดัชนีพลังของแชปลีย์–ชูบิก

 อ้างอิง 

 แหล่งข้อมูลอื่น 

 เครื่องคำนวณค่าแชปลีย์
 การคำนวณค่าโดยสารแท็กซี่โดยใช้ค่าแชปลีย์

หมวดหมู่:เกมร่วมมือ
หมวดหมู่:การแบ่งที่ยุติธรรม
หมวดหมู่:ลอยด์ แชปลีย์