💻 computer science

A General Theory of Proportionality with Additive Utilities

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

المؤلفون الأصليون: Piotr Skowron

نُشر 2026-02-10

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Piotr Skowron

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

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

الهدف هو اختيار مجموعة من الأنشطة التي تشعر الجميع بأنها عادلة. إذا كانت مجموعة من الجيران تمثل 20% من الحشد وجميعهم يحبون نوعاً معيناً من الموسيقى، فيجب أن يحصلوا تقريباً على 20% من "وقت الموسيقى" في المهرجان.

تتناول هذه الورقة نسخة معقدة للغاية من هذه المشكلة: ماذا لو لم يكتفِ الناس بالقول "أنا أحب هذا" أو "لا أحبه"؟ ماذا لو قالوا: "أنا أحب حفل الروك هذا قليلاً، لكني أعشق فرقة الجاز تلك أكثر بك كثيراً"؟

إليك تفصيل لأفكار الورقة باستخدام تشبيهات بسيطة.

1. المشكلة: الفجوة بين "الاستحسان" و"المنفعة"

افترضت معظم القواعد السابقة للاختيار العادل أن الناخبين لديهم فقط زر "نعم/لا" (الاستحسان - Approval).

الاستحسان (Approval): "أنا أحب حفل الروك." (القيمة = 1)
المنفعة (Utility - التحدي الجديد): "أنا أحب حفل الروك قليلاً، لكن فرقة الجاز هي المفضلة لدي تماماً." (الروك = 0.2، الجاز = 1.0).

تجادل الورقة بأن الحياة الواقعية مليئة بهذه التفضيلات القائمة على "المنفعة". فحتى لو أدليت بصوت "نعم" لمشروع ما، فقد تهتم به أكثر إذا كلف 100 دولار مما لو كلف 10 دولارات. أراد المؤلفون بناء قواعد تتعامل مع هذه المشاعر الدقيقة، وليس فقط أصوات "نعم/لا" البسيطة.

2. الفكرة الجوهرية: شراء المرشحين بـ "أموال افتراضية"

يقترح المؤلفون نظاماً يكسب فيه الناخبون أموالاً افتراضية بمرور الوقت، مثل صنبور يقطر العملات في جيوبهم.

الطريقة القديمة (قاعدة فريجمان - Phragmén's Rule): بمجرد أن تمتلك مجموعة من الناس ما يكفي من العملات لشراء مرشح يحبونه، يشترونه فوراً. إنه نهج "جشع".
الطريقة الجديدة (PropRank و Equal Shares): أدرك المؤلفون أن شراء مرشح الآن قد يكون فكرة سيئة. ربما إذا انتظرت 5 دقائق، سيكون لديك ما يكفي من المال لشراء مرشح أفضل تحبه أكثر.

التشبيه: تخيل أنك في بوفيه مفتوح، لكنك تدفع مقابل كل دقيقة تقضيها هناك.

الجشع: ترى برجر يعجبك، فتأخذه فوراً.
الذكاء (طريقة الورقة): ترى البرجر، لكنك تعلم أن هناك شريحة لحم (ستيك) ستخرج بعد دقيقتين. فتنتظر. تحسب: "إذا أنفقت مالي الآن على البرجر، فقد أفوت الشريحة. ولكن إذا انتظرت، يمكنني الحصول على الشريحة، والتي ستمنحني 'سعادة' أكبر مقابل كل دولار".

تقدم الورقة آلية "استشراف" رياضية. فهي تحاكي المستقبل لتقرر: هل يستحق الأمر الانتظار للحصول على صفقة أفضل، أم يجب أن أشتري هذا الآن؟

3. القاعدتان الرئيسيتان

أ. PropRank (المُحدد "المسافر عبر الزمن")

صُممت هذه القاعدة لإنشاء تصنيف (قائمة من المركز الأول إلى الأخير) بدلاً من مجرد قائمة نهائية.

كيف تعمل: يكسب الناخبون المال. تقوم الخوارزمية بفحص كل مرشح وتسأل: "من هو المستعد للدفع مقابل هذا، وبأي تكلفة؟"
اللمسة المميزة: هي لا تشتري أرخص شيء فحسب. بل تحسب "السعر لكل وحدة من السعادة". إذا كان المرشح مكلفاً ولكنه يمنح مجموعة من الناخبين سعادة هائلة، فقد يكون "أرخص" من حيث السعادة مقارنة بمرشح رخيص وممل.
النتيجة: تنتج قائمة عادلة حيث يكون كل جزء علوي من القائمة (البادئة - prefix) عبارة عن لجنة عادلة بحد ذاتها.

ب. طريقة الحصص المتساوية (Method of Equal Shares - "موزع الميزانية")

هذه نسخة أكثر جرأة. بدلاً من تقطير المال ببطء، تعطي هذه الطريقة الجميع مبلغاً كبيراً من المال الافتراضي مقدماً وتتركهم ينفقونه.

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

4. "الخوارزاء" (Heuristics - الاختصارات الذكية)

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

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

5. ماذا وجدوا؟ (النتائج)

اختبر المؤلفون قواعدهم على بيانات من العالم الحقيقي من الميزانية التشاركية (حيث تسمح المدن الحقيقية للمواطنين بالتصويت على كيفية إنفاق الأموال العامة).

عامل "الانتظار": وجدوا أن ضبط معلمة "الانتظار" (المسماة $\kappa$ ) على 1 (بمعنى أن الناخبين مستعدون جداً للانتظار للحصول على صفقات أفضل) كان هو الأفضل للعدالة.
العدالة مقابل السعادة: كانت قواعدهم الجديدة عادلة للغاية. نادراً ما انتهكت قواعد "العدالة" (المسماة التمثيل المبرر الممتد - Extended Justified Representation).
المقارنة:
- الطريقة الجشعة (Greedy): (مجرد اختيار الأشياء الأكثر شعبية) كانت فعالة ولكنها غير عادلة للمجموعات الصغيرة.
- القواعد الجديدة (PropRank و Equal Shares): كانت أكثر عدلاً بك كثيراً للمجموعات المتنوعة من الناخبين، مما يضمن تمثيل تفضيلات الأقليات فعلياً، وليس فقط تفضيلات الأغلبية.
- نسخ الخوارزاء (Heuristic versions): (التي تحتوي على ميزات "إعادة الضبط" و"التراجع") قدمت أداءً شبه مثالي، حيث حققت نتائج تكاد تخلو من انتهاكات العدالة.

ملخص

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

لقد أثبتوا رياضياً أن هذه القواعد عادلة، واختبروها على بيانات حقيقية لإظهار أنها تعمل بشكل أفضل من الطرق القديمة.

ملخص تقني: نظرية عامة للتناسب مع المنفعة الجمعية

1. بيان المشكلة

تتناول الورقة مشكلة اختيار مجموعة فرعية قابلة للتنفيذ من المرشحين من مجموعة $C$ بناءً على تفضيلات الناخبين، مع مراعاة قيود الجدوى العامة المحددة بواسطة عائلة من المجموعات الفرعية $\mathcal{F} \subseteq 2^C$ . هذا الإطار يعمم عدة نماذج راسخة في نظرية الاختيار الاجتماعي، بما في ذلك:

انتخابات اللجان: اختيار عدد محدد من المرشحين.
الموازنة التشاركية (PB): اختيار مشاريع ضمن ميزانية إجمالية.
صنع القرار العام وتجميع الأحكام: اتخاذ القرارات بشأن قضايا متعددة مستقلة.
قيود التنوع: ضمان خصائص هيكلية معينة (مثل التوازن بين الجنسين) في المجموعة المختارة.

بينما تم تعريف بديهيات التناسب (مثل التمثيل المبرر) لهذا النموذج العام، فإن القواعد الموجودة مصممة أساساً لـ بالونات الموافقة (حيث يخصص الناخبون منفعة 0 أو 1). تركز الورقة على الإطار الأكثر تعقيداً لـ المنفعة الجمعية، حيث يخصص كل ناخب $i$ منفعة عددية $u_i(c) \geq 0$ لكل مرشح $c$ . الهدف هو تصميم قواعد تضمن التمثيل العادل للمجموعات المتماسكة من الناخبين تحت هذه القيود العامة والمنفعة العددية.

2. المنهجية

يقترح المؤلفون نهجين خوارزميين أساسيين مستوحيين من مفهوم "شراء" الناخبين للمرشحين باستخدام عملة افتراضية.

2.1 قاعدة PropRank

إن PropRank هي قاعدة تسلسلية مستوحاة من قاعدة Phragmén التسلسلية ولكنها مكيفة للمنافع الجمعية.

الآلية: يكسب الناخبون مالاً افتراضياً بمعدل ثابت بمرور الوقت. تحاكي القاعدة عملية شراء حيث يقرر الناخبون مقدار ما سينفقونه على المرشحين.
آلية الاستشراف: على عكس النهج الجشع القياسي، يتوقع الناخبون في PropRank الفرص المستقبلية. يقومون بحساب "عامل قياس" $\lambda_i$ بناءً على أفضل نسبة ممكنة بين الدفع إلى المنفعة التي يمكنهم تحقيقها إذا انتظروا مرشحاً أكثر رغبة ليصبح متاحاً مادياً.
دالة الإنفاق: يوافق الناخب $i$ على إنفاق ما لا يزيد عن $x_i(c, r)$ على المرشح $c$ في الجولة $r$ ، وذلك عبر صيغة تتضمن ميزانية الناخب، ومنفعة المرشح، وعامل القياس. يضمن هذا أن نسبة الدفع إلى المنفعة لا تتجاوز أفضل عملية شراء كسرية متاحة.
الترتيب: تبني الخوارزمية ترتيباً كاملاً للمرشحين بناءً على طوابع زمن الشراء. وبما أن المرشحين غير القابلين للتنفيذ لا يتم استبعادهم أثناء عملية الترتيب (بل يتم ذلك فقط في نهاية بناء الترتيب لأحجام لجان محددة)، فإن كل بادئة (prefix) للترتيب تحقق التناسب.

2.2 الطريقة المعممة للحصص المتساوية (MES)

يوسع المؤلفون طريقة "الحصص المتساوية" (المخصصة أصلاً للموازنة التشاركية PB) لتشمل القيود العامة.

الهيكل: تعمل الخوارزمية في جولات. في كل جولة، تحدد الحد الأقصى للمبلغ الذي يمكن تخصيصه للناخبين بحيث يمكن لروتين "الحصص المتساوية" الفرعي شراء مجموعة من المرشحين دون انتهاك قيود الجدوى.
الاستشراف في MES: على غرار PropRank، تتضمن MES المعممة آلية استشراف. فهي تحسب الحدود العليا للإنفاق ($capi$) لمنع الناخبين من الإنفاق المبكر على مرشحين قد يكونون أقل كفاءة من أولئك المتاحين في الدورات المستقبلية.
الاستدراك (Backtracking) التجريبي: تقدم الورقة متغيرات تجريبية (PropRankRem، PropRankBacktrack) تقوم بإعادة تشغيل الإجراء أو التراجع عند استبعاد المرشحين، بهدف تقليل الميزانيات غير المنفقة أو تحسين الأداء العملي، رغم أنها تفتقر إلى نفس الضمانات النظرية للقواعد الأساسية.
الإنفاق الزائد المحدود (BOS): تم اقتراح تكييف لطريقة BOS لهذا النموذج من القيود العامة، حيث تحدد الخوارزمية أكبر طابع زمني صالح للشراء قبل انتهاك الجدوى.

3. المساهمات الرئيسية

3.1 الإطار النظري

بديهيات التناسب للمنافع الجمعية: تعمم الورقة بديهيات مثل التمثيل المبرر الممتد (EJR) والتمثيل المبرر التناسبي (PJR) إلى إعداد المنفعة الجمعية مع القيود العامة.
درجة التناسب: يعرف المؤلفون ويحللون "درجة التناسب"، وهي كمية تقيس متوسط رضا المجموعة المتماسكة. ويؤسسون العلاقة بين EJR ودرجة التناسب، موضحين أنه بالنسبة للقيود العامة، يعتمد الضمان على حجم المجموعة المتماسكة ( $\gamma = |S|/n$ ).

3.2 الضمانات النظرية

ضمانات PropRank:
- بالنسبة لـ قيود الموازنة التشاركية، تحقق PropRank درجة تناسب قدرها $d(\alpha) = (\alpha - u_{max})/2$ .
- بالنسبة لـ القيود العامة، تحقق درجة قدرها $d(\alpha) \geq \alpha \cdot \frac{1-\gamma}{2} - \frac{u_{max}}{2}$ .
- بالنسبة لـ قيود الماترويد (Matroid)، تحقق درجة تناسب ضعيفة قدرها $(\alpha - u_{max})/2$ .
ضمانات PJR: تحقق القواعد ضمانات درجة PJR قدرها $d(\alpha) = (\alpha - u_{max})/(\kappa + 1)$ ، حيث $\kappa$ هو معامل يتحكم في مرونة الإنفاق.

3.3 التوسعات الخوارزمية

تقدم الورقة أول تعميم لطريقة الحصص المتساوية للقيود التعسفية مع المنافع الجمعية.
تقدم متغيرات تجريبية (PropRankRem، PropRankBacktrack) لمعالجة مسألة الميزانيات غير المنفقة في السيناريوهات العملية.

4. النتائج التجريبية

قيم المؤلفون قواعدهم على أكثر من 1,300 حالة واقعية من حالات الموازنة التشاركية من مجموعة بيانات Pabulib.

المقاييس: تم التقييم بناءً على انتهاكات EJR+ (التناسب)، ونسبة الاستبعاد (نسبة الناخبين الذين لديهم منفعة صفرية)، ومتوسط التكلفة-الرضا (الكفاءة النفعية).
النتائج:
- معامل $\kappa$ : تشير التجارب إلى أن PropRank مع $\kappa = 1$ (الذي يسمح بإنفاق أكثر مرونة) يؤدي بشكل أفضل بكثير من حيث التناسب (انتهاكات أقل لـ EJR+) مقارنة بـ $\kappa = 0$ .
- النماذج التجريبية: أظهرت المتغيرات التجريبية (PropRankRem، PropRankBacktrack) مع $\kappa = 0$ عددًا قليلاً جدًا من انتهاكات EJR+ ونسب استبعاد مواتية، متفوقة غالبًا على PropRank الأساسي في المقاييس العملية رغم افتقارها للبراهين الرسمية لهذه المتغيرات تحديدًا.
- تكييف BOS: حققت طريقة الحصة المتساوية المكيفة مع الإنفاق الزائد المحدود أداءً ممتازًا، حيث تفوقت على BOS-PB الأصلي في انتهاكات EJR+ وكانت تضاهيه في نسبة الاستبعاد والمنفعة. كما لوحظ أنها الأكثر كفاءة حسابيًا من بين التقنيات المقترحة.
- المقارنة: حققت القواعد المقترحة عمومًا تكلفة-رضا مماثلة أو أفضل من القواعد المخصصة للموازنة التشاركية (MES-PB، BOS-PB) مع التعامل مع القيود العامة.

5. الأهمية والادعاءات

تدعي الورقة تقديم نظرية عامة للتناسب تجسر الفجوة بين النماذج المحددة (مثل انتخابات اللجان وPB) والمشهد الأوسع لمشكلات الاختيار المقيدة.

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

باختصار، يؤسس هذا العمل لقاعدة نظرية متينة للتمثيل التناسبي تحت قيود عامة ومع منافع جمعية، مقدمًا خوارزميات ذات ضمانات مثبتة وهياكل تجريبية تؤدي بشكل جيد في البيانات الواقعية.