Skip to content
กลับไปยังผลการค้นหา

กลไก VCG (VCG Mechanism)

ผู้เสนอ
William Vickrey, Edward Clarke, Theodore Groves
ปี
1961
ประเภท
algorithm
กลุ่มวิธี
Game-theoretic

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

กลไก Vickrey-Clarke-Groves (VCG) เป็นแนวทางการออกแบบกลไกที่ส่งเสริมความจริงใจ (truthful mechanism design) ซึ่งใช้ในการจัดสรรทรัพยากรและกำหนดการชำระเงินเพื่อจูงใจให้ผู้เข้าร่วมเปิดเผยมูลค่าที่แท้จริงของตน กลไกนี้ต่อยอดมาจากงานวิจัยการประมูลแบบปิดผนึกราคา (sealed-bid auction) ของ William Vickrey ในปี 1961 และได้รับการขยายความโดย Clarke และ Groves กลไก VCG รับประกันว่าการรายงานมูลค่าที่แท้จริงเป็นกลยุทธ์ที่เหนือกว่า (dominant strategy) สำหรับผู้เข้าร่วมทุกคน บรรลุประสิทธิภาพในการจัดสรร (allocative efficiency) พร้อมทั้งเพิ่มผลกำไรสูงสุด (maximizing total surplus)

แนวคิดเบื้องหลังวิธีการ

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

ประวัติศาสตร์

William Vickrey ได้นำเสนอการประมูลแบบเสนอราคาปิดผนึกราคาที่สอง (Vickrey auction) ในปี 1961 และพิสูจน์แล้วว่าสามารถกระตุ้นให้เกิดการเสนอราคาที่แท้จริงได้ Edward Clarke และ Theodore Groves ได้ขยายหลักการนี้ไปยังกลไกการจัดสรรทั่วไปมากขึ้น โดยมีการชำระเงินตามผลกระทบภายนอก การมีส่วนร่วมของพวกเขาได้วางรากฐานทฤษฎีการออกแบบกลไกสมัยใหม่ ซึ่งทำให้ Vickrey ได้รับรางวัลโนเบลสาขาเศรษฐศาสตร์ในปี 1996 (หลังเสียชีวิต) และมีอิทธิพลอย่างลึกซึ้งต่อการออกแบบการประมูลในทางปฏิบัติ โดยเฉพาะอย่างยิ่งการประมูลคลื่นความถี่และตลาดโฆษณาออนไลน์

ควรใช้เมื่อใด

นำกลไก VCG ไปใช้เมื่อออกแบบกลไกสำหรับการจัดสรรทรัพยากร การประมูล หรือการจัดหาสินค้าสาธารณะ ที่การเปิดเผยความพึงพอใจอย่างจริงใจเป็นสิ่งสำคัญ เหมาะอย่างยิ่งสำหรับการประมูลแบบผสม (combinatorial auctions) การจัดสรรคลื่นความถี่ และการจัดซื้อจัดจ้าง ใช้เมื่อการบรรลุทั้งความเข้ากันได้ของแรงจูงใจ (incentive compatibility) และประสิทธิภาพในการจัดสรรเป็นสิ่งสำคัญ แม้ว่าการชำระเงินรวมอาจสูงกว่าการออกแบบทางเลือกอื่น

ข้อจำกัดและข้อควรพิจารณา

  • มีความซับซ้อนในการคำนวณสูงสำหรับรายการหรือผู้เข้าร่วมจำนวนมาก ทำให้การกำหนดผู้ชนะเป็นปัญหา NP-hard
  • มักส่งผลให้เกิดการขาดดุล (การชำระเงินสูงกว่ารายรับ) ซึ่งต้องอาศัยเงินอุดหนุนในการใช้งานบางประเภท
  • มีความอ่อนไหวต่อการสมรู้ร่วมคิดหรือการเข้าร่วม/ถอนตัวของผู้เสนอราคา หากไม่ได้รับการตรวจสอบอย่างรอบคอบ
  • อาจไม่เป็นที่เข้าใจง่ายสำหรับผู้เข้าร่วม ลดการนำไปใช้ในทางปฏิบัติ

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

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

การประยุกต์ใช้

  • การประมูลคลื่นความถี่: การจัดสรรคลื่นความถี่วิทยุให้กับบริษัทโทรคมนาคม พร้อมทั้งส่งเสริมการประเมินมูลค่าที่แท้จริง
  • โฆษณาออนไลน์: การประมูลโฆษณาของ Google ผสมผสานองค์ประกอบของ VCG ในการจัดสรรพื้นที่โฆษณาตามมูลค่าของผู้เสนอราคา
  • การจัดซื้อจัดจ้าง: การจัดซื้อจัดจ้างของรัฐบาลและเอกชนโดยใช้การประมูล VCG แบบย้อนกลับ (reverse VCG auctions) เพื่อให้ได้สินค้าในราคาที่แข่งขันได้
  • โครงการแลกเปลี่ยนไต: การจับคู่ผู้บริจาคและผู้รับ พร้อมทั้งส่งเสริมการเปิดเผยความเข้ากันได้ที่แท้จริง

วิธีการทำงาน

วิธีการทำงาน

1

ขอรับการประมูลแบบปิดผนึกราคาหรือมูลค่าจากผู้เข้าร่วมทั้งหมด โดยไม่เปิดเผยข้อมูลแก่ผู้เข้าร่วมรายอื่น

2

ค้นหาการจัดสรรที่มีประสิทธิภาพโดยการเลือกผลลัพธ์ที่เพิ่มผลกำไรโดยรวมสูงสุด (ผลรวมของมูลค่าของผู้เข้าร่วมทั้งหมด)

3

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

4

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

ข้อผิดพลาดที่พบบ่อย

  • การสมมติฐานเกี่ยวกับความสามารถในการคำนวณสำหรับปัญหาการจัดสรรที่ซับซ้อน การค้นหาการจัดสรรที่มีประสิทธิภาพเป็นปัญหา NP-hard สำหรับการประมูลแบบผสม
  • การสับสนกลไก VCG กับการประมูลแบบราคาแรก (first-price auctions) กลไก VCG ใช้การกำหนดราคาตามผลตอบแทน ไม่ใช่การกำหนดราคาตามการเสนอราคา
  • การมองข้ามว่ากลไก VCG ส่งเสริมความจริงใจในมูลค่า แต่ไม่ส่งเสริมมิติเชิงกลยุทธ์อื่น ๆ (การเข้าร่วม การสมรู้ร่วมคิด)
  • การลืมว่าประสิทธิภาพเป็นภาพรวม ไม่ใช่เฉพาะส่วน การจัดสรรที่ผิดพลาดจะเกิดขึ้นหากการเสนอราคาไม่สะท้อนมูลค่าที่แท้จริง

คำถามที่พบบ่อย

เหตุใดกลไก VCG จึงคิดราคา Vickrey (ราคาที่สอง) ในการประมูลที่มีรายการเดียว?

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

เมื่อใดที่กลไก VCG ไม่ใช่กลไกที่เพิ่มรายได้สูงสุด?

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

กลไก VCG จัดการกับการประมูลแบบผสมที่มีหลายรายการอย่างไร?

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

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Vickrey, W. (1961). Counterspeculation, auctions, and competitive sealed bids. The Journal of Finance, 16(1), 8-37.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Clarke, E. H. (1971). Multipart pricing of public goods. Public Choice, 11(1), 17-33.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว