الانتقال إلى المحتوى
العودة إلى نتائج البحث

دورات التداول العليا

قدّمه
Lloyd Shapley, Herbert Scarf
السنة
1974
النوع
algorithm
العائلة
Game-theoretic

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

دورات التداول العليا (TTC) هي خوارزمية لتخصيص السلع غير القابلة للتجزئة للوكلاء بحيث يكون التخصيص فعالًا من حيث باريتو ورشيدًا فرديًا. طوّرها لويد شابلي وهربرت سكارف في عام 1974، وتحدد الخوارزمية دورات التداولات في رسم بياني موجه للتفضيلات، وتنفذ تلك التداولات، وتكرر العملية بشكل متكرر حتى لا تكون هناك تداولات إضافية مفيدة. تُستخدم TTC على نطاق واسع في تبادل الكلى وتخصيص الإسكان نظرًا لكفاءتها وبساطة تنفيذها.

الفكرة الحدسية وراء الطريقة

تخيل مجموعة من الأشخاص يمتلك كل منهم منزلًا واحدًا، ويصنف كل شخص جميع المنازل حسب الأفضلية. تسأل خوارزمية TTC: من هو المفضل لدي؟ أشر إليه. الآن انظر إلى من أشار إليك. إذا كانت دورة (A يشير إلى B، و B يشير إلى C، و C يشير إلى A)، نفّذ تلك التداولات—يحصل A على منزل B، ويحصل B على منزل C، ويحصل C على منزل A. الجميع في الدورة سعداء لأنهم حصلوا على منزل شخص يفضلونه على منزلهم الحالي. أزل الدورة وكرر حتى لا توجد المزيد من الدورات. النتيجة فعالة لأن جميع التداولات المفيدة تتم.

التاريخ

قدم لويد شابلي وهربرت سكارف خوارزمية دورات التداول العليا في عام 1974 كحل لمشكلة سوق الإسكان، وأثبتا أنها تنتج تخصيصات فريدة وفعالة من حيث باريتو. اكتسبت الخوارزمية أهمية عملية من خلال عمل ألفين روث على تبادل الكلى، حيث أصبحت مركزية لمطابقة المتبرعين والمتلقين. أكدت جائزة نوبل لعام 2012 لروث أهمية TTC لتصميم السوق في العالم الحقيقي، لا سيما في زراعة الأعضاء.

متى تُستخدم

طبق TTC عند تخصيص السلع غير القابلة للتجزئة (المنازل، الأعضاء، المقاعد المدرسية) بين الوكلاء ذوي التفضيلات الصارمة على الحزم. استخدمها عندما تكون كفاءة باريتو ضرورية ولا تتوفر أو لا تكون مرغوبة تحويلات نقدية. TTC مثالية للأسواق اللامركزية حيث يمكن للوكلاء تحديد التداولات المفيدة محليًا. تعمل بشكل أفضل عندما يكون لدى الوكلاء معلومات تفضيل كاملة وغير دورية.

الحدود والاعتبارات

  • تتطلب أوامر تفضيل صارمة بدون لامبالاة؛ التوسعات لتفضيلات ضعيفة معقدة
  • ليست مقاومة للتحالفات: يمكن لتحالفات الوكلاء تحريف التفضيلات لتحسين النتيجة الجماعية
  • الحساسية لدورات التفضيل: عدم وجود دورات يمكن أن يترك بعض الوكلاء غير متداولين
  • مقتصرة على المطابقة بدون تحويلات نقدية؛ غير فعالة للتقييمات غير المتجانسة

لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.

نقاط القوة

  • فعالية باريتو: لا توجد تحسينات خالية من التداول؛ يتم تنفيذ جميع المقايضات ذات المنفعة المتبادلة
  • رشيد فرديًا: يفضل كل وكيل بشكل ضعيف التخصيص النهائي على حيازته الأولية
  • مقاومة للتلاعب في بعض الإعدادات: لا يمكن للوكلاء التحسن عن طريق الإبلاغ الكاذب عن التفضيلات
  • فعالة حسابيًا: زمن متعدد الحدود مع تنفيذ بسيط
  • شفافة: يفهم الوكلاء كيف يؤدي اختيارهم المشار إليه إلى التخصيص

التطبيقات

  • تبادل الكلى: مطابقة المتبرعين والمتلقين لزيادة توافق الزرع من خلال المقايضات متعددة الأطراف
  • تخصيص الإسكان: تخصيص غرف السكن الجامعي أو وحدات الإسكان العام بكفاءة
  • اختيار المدارس: تخصيص الطلاب للمدارس مع قيود السعة وتنوع التفضيلات
  • تبادل فصوص الكبد: تسهيل تبادلات التبرع المزدوج لزراعة الكبد من متبرع حي
  • مقايضات الأثاث والسلع: تنظيم تبادلات المقايضة الفعالة في منصات المشاركة المجتمعية

كيف يعمل

كيف يعمل

1

أنشئ رسمًا بيانيًا موجهًا حيث يشير كل وكيل إلى الوكيل المفضل لديه من بين أولئك الذين ما زالوا في السوق.

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
    تم النسخ.