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

Top Trading Cycles

ผู้เสนอ
Lloyd Shapley, Herbert Scarf
ปี
1974
ประเภท
algorithm
กลุ่มวิธี
Game-theoretic

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

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

ใช้ทำอะไร?

Top Trading Cycles (TTC) เป็นอัลกอริทึมสำหรับการจัดสรรสินค้าที่แบ่งแยกไม่ได้ให้กับตัวแทน โดยมีเป้าหมายเพื่อให้การจัดสรรนั้นมีประสิทธิภาพแบบพาเรโต (Pareto efficient) และมีเหตุผลในระดับบุคคล (individually rational) อัลกอริทึมนี้พัฒนาโดย Lloyd Shapley และ Herbert Scarf ในปี 1974 โดยจะระบุวงจรการแลกเปลี่ยนในกราฟความพึงพอใจ (preference digraph) ดำเนินการแลกเปลี่ยนเหล่านั้น และทำซ้ำเป็นช่วงๆ จนกว่าจะไม่มีการแลกเปลี่ยนใดที่เป็นประโยชน์อีกต่อไป TTC ถูกนำไปใช้อย่างแพร่หลายในการแลกเปลี่ยนไตและการจัดสรรที่อยู่อาศัย เนื่องจากมีประสิทธิภาพและความเรียบง่ายในการนำไปปฏิบัติ

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

ลองนึกภาพกลุ่มคนแต่ละคนเป็นเจ้าของบ้านหนึ่งหลัง และแต่ละคนจัดอันดับบ้านทั้งหมดตามความพึงพอใจ อัลกอริทึม TTC จะถามว่า: ใครคือคนที่ฉันชอบที่สุด? ชี้ไปที่พวกเขา ตอนนี้ดูว่าใครชี้มาที่คุณ หากเป็นวงจร (A ชี้ไปที่ B, B ชี้ไปที่ C, C ชี้ไปที่ A) ให้ดำเนินการแลกเปลี่ยนเหล่านั้น—A ได้บ้านของ B, B ได้บ้านของ C, C ได้บ้านของ A ทุกคนในวงจรจะมีความสุขเพราะพวกเขาได้บ้านของคนที่พวกเขาพึงพอใจมากกว่าบ้านเดิมของตนเอง ลบวงจรนั้นออกแล้วทำซ้ำจนกว่าจะไม่มีวงจรเหลืออยู่ ผลลัพธ์มีประสิทธิภาพเพราะการแลกเปลี่ยนที่เป็นประโยชน์ทั้งหมดได้ถูกดำเนินการแล้ว

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

Lloyd Shapley และ Herbert Scarf ได้นำเสนออัลกอริทึม Top Trading Cycles ในปี 1974 เพื่อแก้ไขปัญหาตลาดที่อยู่อาศัย โดยพิสูจน์ว่าให้ผลลัพธ์การจัดสรรที่มีประสิทธิภาพแบบพาเรโตที่ไม่ซ้ำกัน อัลกอริทึมได้รับความสำคัญในทางปฏิบัติผ่านงานของ Alvin Roth ในการแลกเปลี่ยนไต ซึ่งกลายเป็นหัวใจสำคัญของการจับคู่ผู้บริจาคและผู้รับ รางวัลโนเบลปี 2012 ที่มอบให้กับ Roth ได้รับรองความสำคัญของ TTC สำหรับการออกแบบตลาดในโลกแห่งความเป็นจริง โดยเฉพาะอย่างยิ่งในการปลูกถ่ายอวัยวะ

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

นำ TTC ไปใช้เมื่อจัดสรรสินค้าที่แบ่งแยกไม่ได้ (บ้าน, อวัยวะ, ที่นั่งในโรงเรียน) ให้กับตัวแทนที่มีความพึงพอใจที่แตกต่างกันอย่างชัดเจน (strict preferences) เหนือชุดสินค้า ใช้เมื่อประสิทธิภาพแบบพาเรโตมีความสำคัญ และไม่มีการโอนเงินเข้ามาเกี่ยวข้องหรือเป็นที่ต้องการ TTC เหมาะอย่างยิ่งสำหรับตลาดแบบกระจายศูนย์ที่ตัวแทนสามารถระบุการแลกเปลี่ยนที่เป็นประโยชน์ได้ในระดับท้องถิ่น ทำงานได้ดีที่สุดเมื่อตัวแทนมีข้อมูลความพึงพอใจที่สมบูรณ์และไม่มีวงจร

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

  • ต้องการลำดับความพึงพอใจที่แตกต่างกันอย่างชัดเจนโดยไม่มีความไม่แยแส (indifference); การขยายไปยังความพึงพอใจแบบอ่อน (weak preferences) นั้นซับซ้อน
  • ไม่คุ้มกันต่อการรวมกลุ่ม (Not coalition-proof): กลุ่มของตัวแทนสามารถรายงานความพึงพอใจที่บิดเบือนเพื่อปรับปรุงผลลัพธ์โดยรวม
  • มีความอ่อนไหวต่อวงจรความพึงพอใจ: การไม่มีวงจรอาจทำให้ตัวแทนบางรายไม่ได้รับการจัดสรร
  • จำกัดอยู่เพียงการจับคู่โดยไม่มีการโอนเงิน; ไม่มีประสิทธิภาพสำหรับการประเมินมูลค่าที่แตกต่างกันอย่างมาก

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

จุดแข็ง

  • มีประสิทธิภาพแบบพาเรโต: ไม่มีการปรับปรุงใดๆ ที่ไม่ทำให้ตัวแทนอื่นแย่ลง; การแลกเปลี่ยนที่เป็นประโยชน์ร่วมกันทั้งหมดได้ถูกดำเนินการแล้ว
  • มีเหตุผลในระดับบุคคล: ตัวแทนแต่ละรายพึงพอใจกับการจัดสรรขั้นสุดท้ายมากกว่าสิ่งที่ตนเองครอบครองอยู่เดิมในระดับอ่อน (weakly prefers)
  • มีคุณสมบัติกลยุทธ์ที่พิสูจน์ได้ (Strategy-proof) ในบางบริบท: ตัวแทนไม่สามารถปรับปรุงผลลัพธ์ได้ด้วยการรายงานความพึงพอใจที่บิดเบือน
  • มีประสิทธิภาพในการคำนวณ: ใช้เวลาพหุนาม (polynomial time) พร้อมการนำไปปฏิบัติที่เรียบง่าย
  • โปร่งใส: ตัวแทนเข้าใจว่าการเลือกที่พวกเขาชี้ไปนำไปสู่การจัดสรรได้อย่างไร

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

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

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

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

1

สร้างกราฟมีทิศทาง (directed graph) โดยที่ตัวแทนแต่ละรายชี้ไปยังตัวแทนที่ตนเองพึงพอใจมากที่สุดในบรรดาผู้ที่ยังคงอยู่ในตลาด

2

ค้นหาวงจรทั้งหมดในกราฟมีทิศทาง (ลำดับที่ A ชี้ไปที่ B, B ชี้ไปที่ C, ..., กลับมาที่ A)

3

สำหรับแต่ละวงจรที่ระบุ ให้ดำเนินการแลกเปลี่ยน: ตัวแทนแต่ละรายจะได้รับสิ่งที่ถูกจัดสรรให้กับตัวแทนที่ตนเองชี้ไป

4

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

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

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

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

เหตุใดประสิทธิภาพแบบพาเรโตจึงมีความสำคัญในการจัดสรรทรัพยากร?

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

TTC สามารถสร้างผลลัพธ์การจัดสรรที่แตกต่างกันได้หลายแบบหรือไม่?

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

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

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

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

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

  1. Shapley, L. S., & Scarf, H. (1974). On cores and indivisibility. Journal of Mathematical Economics, 1(1), 23-37.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Roth, A. E., Sönmez, T., & Ünver, M. U. (2008). Efficient kidney exchange: Coincidence of wants in markets with compatibility. American Economic Review, 97(3), 828-851.

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