การออกแบบกลไก

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

Definition

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

Scope

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

Core questions

• จะออกแบบกฎเกณฑ์การปฏิสัมพันธ์ได้อย่างไรเพื่อให้ตัวแทนมีแรงจูงใจในการรายงานความชอบที่แท้จริงของตน?
• หลักการเปิดเผยกล่าวถึงอะไรเกี่ยวกับการจำกัดความสนใจเฉพาะกลไกที่ซื่อสัตย์?
• การประมูลจัดสรรสินค้าอย่างมีประสิทธิภาพระหว่างตัวแทนที่มีการประเมินมูลค่าส่วนตัวได้อย่างไร?
• ค่าใช้จ่ายในการคำนวณของการนำกลไกที่พึงประสงค์ไปใช้คืออะไร?

Key concepts

• การเลือกทางสังคมและการรวมความชอบ
• ความเข้ากันได้ของสิ่งจูงใจ (ความซื่อสัตย์)
• การนำไปใช้ตามกลยุทธ์ที่เหนือกว่า
• หลักการเปิดเผย
• การประมูล
• การประมูลแบบราคาที่สองของ Vickrey
• กลไก Vickrey-Clarke-Groves (VCG)
• ประสิทธิภาพและความมีเหตุผลส่วนบุคคล

Key theories

ความเข้ากันได้ของสิ่งจูงใจและการประมูลแบบราคาที่สอง

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

กลไก Vickrey-Clarke-Groves

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

หลักการเปิดเผย

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

Clinical relevance

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

History

การออกแบบกลไกเติบโตมาจากทฤษฎีเศรษฐศาสตร์ โดยมีการวิเคราะห์การประมูลของ Vickrey (1961) และผลงานของ Clarke และ Groves ในภายหลังที่ก่อให้เกิดตระกูล VCG ตั้งแต่ปลายทศวรรษ 1990 วิทยาการคอมพิวเตอร์ได้เพิ่มการศึกษาความสามารถในการคำนวณและการประมาณค่า ซึ่งนำไปสู่การออกแบบกลไกเชิงอัลกอริทึม ดังที่ระบุไว้ในตำราเช่น Algorithmic Game Theory (2007)

Key figures

• William Vickrey
• Edward H. Clarke
• Theodore Groves
• Noam Nisan
• Tim Roughgarden

Seminal works

• vickrey1961
• shoham2009
• nisan2007

Frequently asked questions

เหตุใดการออกแบบกลไกจึงถูกเรียกว่าทฤษฎีเกมผกผัน?

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

เหตุใดการประมูลแบบราคาที่สองจึงส่งเสริมการเสนอราคาอย่างซื่อสัตย์?

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