تخصيص العناصر ذات الأولوية بشكل عشوائي

الأولوية العشوائية (RP)، ^{[ 1 ]} وتسمى أيضًا الديكتاتورية التسلسلية العشوائية (RSD)، ^{[ 2 ]} هي إجراء للتخصيص العشوائي العادل - تقسيم العناصر غير القابلة للتجزئة بشكل عادل بين الناس.

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

ملكيات

تُعدّ آلية RSD آليةً صادقةً عندما يكون عدد العناصر مساوياً على الأكثر لعدد العناصر المتاحة. وبالنظر إلى وجود فرصة واحدة فقط لاختيار عنصر، فإنّ الاستراتيجية الأمثل في هذه الحالة هي اختيار أفضل عنصر متاح.

تُؤدي عملية التوزيع العشوائي المُقيد (RSD) دائمًا إلى نتيجة فعّالة وفقًا لمبدأ باريتو (PE) بعد التنفيذ . علاوة على ذلك، في مسألة التخصيص ، يُعد كل تخصيص حتمي وفقًا لمبدأ باريتو (PE) نتيجةً لعملية التوزيع العشوائي المُقيد (SD) لترتيب معين للوكلاء. ^{[ 1 ]}^{: اللمة 1}

مع ذلك، لا يُعدّ التوزيع العشوائي للعناصر (RSD) توزيعًا مثاليًا مسبقًا (EPE) عندما يمتلك الوكلاء منافع فون نيومان-مورغنسترن على التوزيعات العشوائية، أي التوزيعات العشوائية على الأشياء (لاحظ أن انعدام الحسد المسبق أضعف من انعدام الحسد اللاحق، لكن كفاءة باريتو المسبقة أقوى من كفاءة باريتو اللاحقة). على سبيل المثال، لنفترض وجود ثلاثة وكلاء، وثلاثة عناصر، ومنافع فون نيومان-مورغنسترن هي:

	العنصر س	البند ص
أليس	1	0.8
بوب	1	0.2
كارل	1	0.2

يُعطي نموذج التوزيع العشوائي المُقيد (RSD) فرصة 1/3 لكل عنصر لكل فرد (لأن تفضيلاتهم للعناصر المؤكدة تتطابق)، ويُعطي متجه المنفعة المتوقعة (0.6، 0.4، 0.4). لكن تخصيص العنصر y لأليس بشكل مؤكد، وتوزيع العنصرين x وz عشوائيًا بين بوب وكارل، يُعطي متجه المنفعة المتوقعة (0.8، 0.5، 0.5). لذا، فإن متجه المنفعة الأصلي ليس فعالًا وفقًا لمبدأ باريتو .

علاوة على ذلك، عندما يكون للوكلاء تصنيفات ترتيبية، فإن RSD يفشل حتى في خاصية الكفاءة sd الأضعف . ^{[ 1 ]}^{: القسم 2}

عندما يتم اختيار ترتيبات الوكلاء على الأشياء بشكل عشوائي منتظم، فإن احتمال أن يكون التخصيص الذي يقدمه RSD هو PE مسبقًا يقترب من الصفر مع ازدياد عدد الوكلاء. ^{[ 3 ]}

هناك قاعدة بديلة، هي قاعدة الاحتمالية التسلسلية ، تتسم بالكفاءة في تحقيق الانحراف المعياري (مما يعني وجود احتمالية لاحقة) وخالية من الحسد في تحقيق الانحراف المعياري (مما يعني خلوها من الحسد قبل التنفيذ)، لكنها ليست صادقة. من المستحيل الجمع بين مزايا كلتا الآليتين.

مع دوال المنفعة الجمعية الأساسية ، لا توجد آلية متناظرة وصادقة وتوقع مسبق للخطأ. ^{[ 4 ]}
باستخدام دوال المنفعة الترتيبية ، لا توجد آلية تتسم بالكفاءة من حيث الانحراف المعياري، أو مقاومة التلاعب الاستراتيجي، أو تعامل المتساوين على قدم المساواة. ^{[ 1 ]}^{: نظرية 2}

التعميمات

عدد الأشياء أكثر من عدد العناصر

عندما يكون هناك أكثر من $n$ قد يحصل بعض العملاء على أكثر من كائن واحد. وهناك عدة طرق لتوسيع نطاق RSD ليشمل هذه الحالة.

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

صنع القرار العام

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

في هذا السياق العام، إذا كانت لدى جميع الوكلاء تفضيلات صارمة على البدائل، فإنّ RSD يختزل إلى سحب وكيل عشوائي واختيار البديل الذي يُفضّله. يُعرف هذا الإجراء بالديكتاتورية العشوائية (RD)، وهو الإجراء الوحيد الذي يتسم بالكفاءة ومقاومة التلاعب عندما تكون التفضيلات صارمة. ^{[ 5 ]} أما عندما يكون لدى الوكلاء تفضيلات ضعيفة، فلا يوجد إجراء يُوسّع نطاق RD (الذي يشمل RSD) يُحقق الكفاءة ومقاومة التلاعب معًا. ^{[ 6 ]}

انظر أيضاً

تقارن الصفحة الخاصة بالتخصيص العشوائي العادل بين RSD والإجراءات الأخرى لحل نفس المشكلة، مثل قاعدة التسلسل الاحتمالي .
تصف الصفحة المتعلقة بآلية الديكتاتورية أن RSD هي قاعدة عامة للاختيار الاجتماعي - وليس بالضرورة لتخصيص العناصر.

مراجع

1 2 3 4 بوغومولنايا، آنا ؛ مولان، هيرفيه (2001). "حل جديد لمشكلة التخصيص العشوائي". مجلة النظرية الاقتصادية . 100 (2): 295. doi : 10.1006/jeth.2000.2710 .
↑ عبد القادر أوغلو، أتيلا؛ سونميز، تايفون (1998). "الديكتاتورية التسلسلية العشوائية والجوهر من الهبات العشوائية في مشاكل تخصيص المساكن". Econometrica . 66 (3): 689. doi : 10.2307/2998580 . hdl : 10161/1866 . JSTOR 2998580 .
↑ مانيا، ميهاي (2009). "عدم الكفاءة الترتيبية التقاربية للديكتاتورية التسلسلية العشوائية". الاقتصاد النظري . 4 (2): 165-197 . hdl : 10419/150127 .
↑ تشو، لين (1990). "حول تخمين غيل حول مشاكل المطابقة أحادية الجانب". مجلة النظرية الاقتصادية . 52 : 123-135 . doi : 10.1016/0022-0531(90)90070-Z .
↑ جيبارد، آلان (1977). "التلاعب بالمخططات التي تمزج التصويت بالصدفة" (ملف PDF) . مجلة Econometrica . 45 (3): 665-681 . doi : 10.2307/1911681 . JSTOR 1911681 .
↑ براندل، فلوريان؛ براندت، فيليكس؛ سوكسومبونغ، واروت (2016). "استحالة تطبيق الديكتاتورية العشوائية على التفضيلات الضعيفة". رسائل اقتصادية . 141 : 44-47 . arXiv : 1510.07424 . doi : 10.1016/j.econlet.2016.01.028 . S2CID 4917725 .

[bm01-1] 1 2 3 4 بوغومولنايا، آنا ؛ مولان، هيرفيه (2001). "حل جديد لمشكلة التخصيص العشوائي". مجلة النظرية الاقتصادية . 100 (2): 295. doi : 10.1006/jeth.2000.2710 .

[as98-2] عبد القادر أوغلو، أتيلا؛ سونميز، تايفون (1998). "الديكتاتورية التسلسلية العشوائية والجوهر من الهبات العشوائية في مشاكل تخصيص المساكن". Econometrica . 66 (3): 689. doi : 10.2307/2998580 . hdl : 10161/1866 . JSTOR 2998580 .

[m09-3] مانيا، ميهاي (2009). "عدم الكفاءة الترتيبية التقاربية للديكتاتورية التسلسلية العشوائية". الاقتصاد النظري . 4 (2): 165-197 . hdl : 10419/150127 .

[z90-4] تشو، لين (1990). "حول تخمين غيل حول مشاكل المطابقة أحادية الجانب". مجلة النظرية الاقتصادية . 52 : 123-135 . doi : 10.1016/0022-0531(90)90070-Z .

[g77-5] جيبارد، آلان (1977). "التلاعب بالمخططات التي تمزج التصويت بالصدفة" (ملف PDF) . مجلة Econometrica . 45 (3): 665-681 . doi : 10.2307/1911681 . JSTOR 1911681 .

[bbs16-6] براندل، فلوريان؛ براندت، فيليكس؛ سوكسومبونغ، واروت (2016). "استحالة تطبيق الديكتاتورية العشوائية على التفضيلات الضعيفة". رسائل اقتصادية . 141 : 44-47 . arXiv : 1510.07424 . doi : 10.1016/j.econlet.2016.01.028 . S2CID 4917725 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]