القسم العادل

يُعدّ التقسيم العادل مسألةً من مسائل التحسين في نظرية الألعاب ، وتتمثل في تقسيم مجموعة من الموارد بين عدة أطراف لها الحق فيها، بحيث يحصل كل طرف على نصيبه المستحق. ^{[ 1 ]} ويكمن المبدأ الأساسي للتقسيم العادل في أن يقوم اللاعبون أنفسهم بهذا التقسيم، دون الحاجة إلى تحكيم خارجي ، إذ إنهم وحدهم من يعرفون قيمة الموارد حقًا.

تتعدد أنواع مسائل التقسيم العادل، تبعًا لطبيعة السلع المراد تقسيمها، ومعايير العدالة، وطبيعة الأطراف المتنافسة وتفضيلاتها، وغيرها من معايير تقييم جودة التقسيم. وتُعدّ خوارزمية " التقسيم والاختيار" النموذجية للتقسيم العادل . ويمكن اعتبار البحث في مجال التقسيم العادل امتدادًا لهذه الخوارزمية لتشمل بيئات أكثر تعقيدًا.

تظهر هذه المشكلة في العديد من السياقات الواقعية، مثل تقسيم الميراث ، وحلّ الشراكات ، وتسويات الطلاق ، وتخصيص الترددات الإلكترونية ، وإدارة حركة المرور في المطارات ، واستخدام أقمار مراقبة الأرض . وهي مجال بحث نشط في الرياضيات ، والاقتصاد ^{[ 2 ]} (وخاصة نظرية الاختيار الاجتماعي )، وحل النزاعات . ^{[ 3 ]}

توجد أنواع عديدة من مسائل التقسيم العادل، وذلك تبعًا لطبيعة السلع المراد تقسيمها، ومعايير العدالة، وطبيعة اللاعبين وتفضيلاتهم، ومعايير أخرى لتقييم جودة التقسيم. وبشكل رسمي، تُعرَّف مسألة التقسيم العادل بمجموعة من${\displaystyle C}$(والتي تُسمى غالبًا "الكعكة") ومجموعة من${\displaystyle n}$اللاعبون. التقسيم هو تجزئة لـ${\displaystyle C}$داخل${\displaystyle n}$المجموعات الفرعية المنفصلة:${\displaystyle C=X_{1}\sqcup X_{2}\sqcup \cdots \sqcup X_{n}}$مجموعة فرعية واحدة لكل لاعب.

المجموعة${\displaystyle C}$يمكن أن تكون من أنواع مختلفة:

• ${\displaystyle C}$قد تكون مجموعة محدودة من العناصر غير القابلة للتجزئة، على سبيل المثال:${\displaystyle C=\{{\text{بيانو}},{\text{سيارة}},{\text{شقة}}\}}$بحيث يتم إعطاء كل عنصر بالكامل لشخص واحد.
• ${\displaystyle C}$قد تكون مجموعة لانهائية تمثل موردًا قابلًا للقسمة، مثل المال أو الكعكة. رياضيًا، غالبًا ما يُنمذج المورد القابل للقسمة كمجموعة جزئية من فضاء حقيقي، فمثلًا، قد يمثل القسم [0,1] كعكة طويلة وضيقة يجب تقطيعها إلى قطع متوازية. وقد يمثل قرص الوحدة فطيرة تفاح.

بالإضافة إلى ذلك، قد تكون المجموعة المراد تقسيمها كالتالي:

• متجانسة - مثل النقود، حيث لا يهم سوى المبلغ، أو
• غير متجانس - مثل الكعكة التي قد تحتوي على مكونات مختلفة، وتزيينات مختلفة، وما إلى ذلك.

وأخيرًا، من الشائع وضع بعض الافتراضات حول ما إذا كانت العناصر المراد تقسيمها هي:

• السلع - مثل سيارة أو كعكة، أو
• الأمور السيئة – مثل الأعمال المنزلية.

وبناءً على هذه الفروقات، تمت دراسة عدة أنواع عامة من مشاكل التقسيم العادل:

• التخصيص العادل للعناصر - تقسيم مجموعة من السلع غير القابلة للتجزئة وغير المتجانسة .
• التوزيع العادل للموارد – تقسيم مجموعة من السلع القابلة للتقسيم والمتجانسة . وتُعدّ التقسيم العادل لمورد متجانس واحد حالة خاصة .
• تقسيم الكعكة بشكل عادل – تقسيم سلعة غير متجانسة قابلة للتقسيم . وثمة حالة خاصة عندما تكون الكعكة دائرية؛ عندها تُسمى المسألة تقسيم الفطيرة بشكل عادل .
• تقسيم عادل للأعمال المنزلية - تقسيم شيء قابل للتقسيم وغير متجانس.

كما أن التركيبات والحالات الخاصة شائعة أيضاً:

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

معظم ما يُسمى عادةً بالتقسيم العادل لا يُعتبر كذلك في النظرية بسبب اللجوء إلى التحكيم . هذا النوع من المواقف شائعٌ في النظريات الرياضية المُسماة على أسماء مشاكل واقعية. تعكس الأحكام الواردة في التلمود بشأن الاستحقاق عند إفلاس التركة تطور أفكار معقدة حول العدالة. ^{[ 4 ]} مع ذلك، فهي نتاج مناقشات قانونية بين الحاخامات وليست تقسيمات بناءً على تقييمات المطالبين.

وفقًا لنظرية القيمة الذاتية ، لا يمكن وجود مقياس موضوعي لقيمة كل عنصر. لذا، فإن العدالة الموضوعية غير ممكنة، إذ قد يُقيّم كل عنصر بقيم مختلفة من قِبل أشخاص مختلفين. وقد أسفرت التجارب العملية التي تناولت كيفية تعريف الناس لمفهوم العدالة عن نتائج غير حاسمة. ^{[ 5 ]}

لذلك، تركز معظم الأبحاث الحالية حول العدالة على مفاهيم العدالة الذاتية . كل منها${\displaystyle n}$يُفترض أن يكون لدى الأفراد دالة منفعة شخصية أو دالة قيمة ذاتية .${\displaystyle V_{i}}$، والتي تُسند قيمة عددية لكل مجموعة فرعية من${\displaystyle C}$غالباً ما يُفترض أن الدوال مُعَيَّرة، بحيث يُقيِّم كل شخص المجموعة الفارغة على أنها 0 (${\displaystyle V_{i}(\emptyset )=0}$لكل i)، ومجموعة العناصر بأكملها كـ 1 (${\displaystyle V_{i}(C)=1}$لكل (i) إذا كانت العناصر مرغوبة، و-1 إذا كانت العناصر غير مرغوبة. ومن الأمثلة على ذلك:

• لو${\displaystyle C}$إذا كانت المجموعة X هي مجموعة العناصر غير القابلة للتجزئة {بيانو، سيارة، شقة}، فيمكن لأليس أن تُسند قيمة 1/3 لكل عنصر، مما يعني أن كل عنصر مهم بالنسبة لها تمامًا مثل أي عنصر آخر. أما بوب، فيمكنه أن يُسند القيمة 1 للمجموعة {سيارة، شقة}، والقيمة 0 لجميع المجموعات الأخرى باستثناء X؛ وهذا يعني أنه يريد الحصول على السيارة والشقة معًا فقط؛ فالسيارة وحدها أو الشقة وحدها، أو كل منهما مع البيانو، لا قيمة لها بالنسبة له.
• لو${\displaystyle C}$إذا كانت الكعكة طويلة وضيقة (ممثلة بالفترة [0،1])، فيمكن لأليس أن تُسند لكل مجموعة جزئية منها قيمة تتناسب مع طولها، مما يعني أنها تريد أكبر قدر ممكن من الكعكة، بغض النظر عن نوع التزيين. أما بوب، فيمكنه إسناد قيمة فقط لمجموعات جزئية من الفترة [0.4، 0.6]، على سبيل المثال، لأن هذا الجزء من الكعكة يحتوي على الكرز، وبوب لا يهتم إلا بالكرز.

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

• يعني التقسيم النسبي أن يحصل كل لاعب على الأقل على حصته المستحقة وفقًا لقيمته الخاصة . على سبيل المثال، إذا قسم ثلاثة أشخاص كعكة، يحصل كل منهم على الأقل على الثلث وفقًا لتقييمه الخاص، أي أن كل شخص من الأشخاص n يحصل على جزء من${\displaystyle C}$والتي يقدر قيمتها بما لا يقل عن 1/ ن من القيمة الإجمالية:
  • ${\displaystyle V_{i}(X_{i})\geq V_{i}(C)/n}$لكل i.
• التقسيم المتناسب الفائق هو التقسيم الذي يحصل فيه كل لاعب على أكثر من 1/ ن. (لا يوجد مثل هذا التقسيم إلا إذا كان لدى اللاعبين تقييمات مختلفة).
  • ${\displaystyle V_{i}(X_{i})>V_{i}(C)/n}$لكل i .
• يضمن التقسيم الخالي من الحسد ألا يرغب أحد في حصة شخص آخر أكثر من حصته، أي أن كل شخص يقدر حصته على الأقل بقدر تقديره لجميع الحصص الأخرى:
  • ${\displaystyle V_{i}(X_{i})\geq V_{i}(X_{j})}$لكل i و j.
• يضمن التقسيم الخالي من الحسد الجماعي عدم حسد أي مجموعة فرعية من الوكلاء لمجموعة فرعية أخرى من نفس الحجم؛ وهذا شرط أقوى من عدم وجود حسد.
• يعني التقسيم العادل أن يكون تقييم كل لاعب لحصته متساوياً، أي أن كل لاعب يحصل على قيمة متساوية، أو "يختبر سعادة متساوية". وهذا هدف صعب المنال، إذ ليس من الضروري أن يكون اللاعبون صادقين عند سؤالهم عن تقييمهم.
  • ${\displaystyle V_{i}(X_{i})=V_{j}(X_{j})}$لكل i و j.
• التقسيم الدقيق (أو التقسيم بالإجماع) هو التقسيم الذي يتفق فيه جميع اللاعبين على قيمة كل سهم:
  • ${\displaystyle V_{i}(X_{i})=V_{j}(X_{i})}$لكل i و j.

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

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

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

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

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

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

ما يفعله اللاعبون هو:

• اتفقوا على معاييرهم لتقسيم عادل
• اختر إجراءً صالحًا واتبع قواعده

يفترض أن هدف كل لاعب هو زيادة الحد الأدنى من المبلغ الذي قد يحصل عليه، أو بعبارة أخرى، تحقيق الحد الأقصى الأدنى .

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

لا يمكن لأي بروتوكول محدود (حتى لو كان غير محدود) أن يضمن تقسيم كعكة بين ثلاثة لاعبين أو أكثر دون حسد، إذا كان كل لاعب سيحصل على قطعة واحدة متصلة. ^{[ 6 ]} ومع ذلك، تنطبق هذه النتيجة فقط على النموذج المقدم في تلك الدراسة، وليس على الحالات التي، على سبيل المثال، يمتلك فيها الوسيط معلومات كاملة عن دوال تقييم اللاعبين ويقترح تقسيمًا بناءً على هذه المعلومات. ^{[ 7 ]}

يمكن اعتبار البحث في التقسيم العادل بمثابة امتداد لهذا الإجراء إلى العديد من الإعدادات الأكثر تعقيدًا.

في الآونة الأخيرة، تم توسيع نموذج التقسيم العادل من الأفراد إلى عائلات (مجموعات محددة مسبقًا) من الأفراد مع تقسيم عادل بين المجموعات .

وفقًا لسول غارفونكل ، كانت مشكلة تقطيع الكعكة واحدة من أهم المشكلات المفتوحة في الرياضيات في القرن العشرين، ^{[ 8 ]} عندما تم حل أهم متغير للمشكلة أخيرًا باستخدام إجراء برامز-تايلور بواسطة ستيفن برامز وآلان تايلور في عام 1995.

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

لا يعود تاريخ نظرية التقسيم العادل إلا إلى نهاية الحرب العالمية الثانية. وقد وضعها مجموعة من علماء الرياضيات البولنديين ، هم هوغو شتاينهاوس ، وبرونيسواف كناستر ، وستيفان باناش ، الذين كانوا يجتمعون في المقهى الاسكتلندي في لفيف (التي كانت آنذاك جزءًا من بولندا). وفي عام 1944، طُوِّر تقسيم نسبي (تقسيم عادل) لأي عدد من اللاعبين، يُعرف باسم "التقسيم الأخير المُخفِّض". وقد نسب شتاينهاوس هذا التقسيم إلى باناش وكناستر عندما طرحه للعلن لأول مرة في اجتماع الجمعية الاقتصادية القياسية في واشنطن العاصمة، في 17 سبتمبر 1947. وفي ذلك الاجتماع، طرح أيضًا مسألة إيجاد أقل عدد من القطع اللازمة لمثل هذه التقسيمات.

• تتضمن أحجية الميراث المكونة من 17 حيوانًا تقسيم 17 جملًا (أو فيلًا، أو حصانًا) بشكل عادل إلى النسب 1/2 و1/3 و1/9. وهي أحجية رياضية شائعة ، يُزعم غالبًا أن لها أصلًا قديمًا، ولكن أول نشر موثق لها كان في إيران في القرن الثامن عشر. ^{[ 9 ]}
• في الحلقة "ساعة واحدة" من الموسم الثالث من مسلسل Numb3rs ، يتحدث تشارلي عن مشكلة تقطيع الكعكة وتطبيقها على المبلغ الذي كان يطلبه الخاطف.
• كتب هوغو شتاينهاوس عن عدد من أشكال القسمة العادلة في كتابه "لقطات رياضية" . ويذكر في كتابه أن نسخة خاصة من القسمة العادلة لثلاثة أشخاص ابتكرها جي. كروشمايني في بيرديشوف عام 1944، ونسخة أخرى ابتكرتها السيدة إل. كوت. ^{[ 10 ]}
• نشر كلٌّ من مارتن غاردنر وإيان ستيوارت كتبًا تتضمن أقسامًا حول هذه المسألة. ^{[ 11 ] [ 12 ]} وقدّم مارتن غاردنر صيغة تقسيم المهام المنزلية للمسألة. أما إيان ستيوارت فقد ساهم في نشر مسألة التقسيم العادل من خلال مقالاته في مجلتي ساينتفك أمريكان ونيو ساينتست .
• تستند إحدى حلقات سلسلة قصص ديناصور كوميكس إلى مشكلة تقطيع الكعكة. ^{[ 13 ]}
• في الفيلم الإسرائيلي "القديسة كلارا" ، يسأل مهاجر روسي مُدرّس رياضيات إسرائيليًا: كيف يُمكن تقسيم كعكة دائرية بالتساوي بين سبعة أشخاص؟ فيُجيبه المعلم بعمل ثلاثة شقوق مستقيمة في منتصفها، ما يُنتج ثماني قطع متساوية. وبما أن عددهم سبعة فقط، يجب التخلص من قطعة واحدة، على غرار مبادئ الشيوعية.

• تجارب التقسيم العادل
• قائمة بالمسائل غير المحلولة في التقسيم العادل
• قسم المعارض عبر الإنترنت
• تقسيم المعرض الاستراتيجي
• التوزيع وحسابات التوزيع
• الإنصاف (الاقتصاد)
• التجارة الدولية
• العدالة (الاقتصاد)
• مشكلة حقيبة الظهر
• لعبة مساومة ناش
• نظرية البيتزا
• ثمن العدالة

• يونغ، بيتون هـ. (1995). الإنصاف: في النظرية والتطبيق . مطبعة جامعة برينستون.
• برامز، ستيفن جيه؛ تايلور، آلان دي. (1996). التقسيم العادل: من تقطيع الكعكة إلى حل النزاعات . مطبعة جامعة كامبريدج. ISBN 0-521-55644-9.
• روبرتسون، جاك؛ ويب، ويليام (1998). خوارزميات تقطيع الكعكة: كن عادلاً إن استطعت . ناتيك، ماساتشوستس: إيه كيه بيترز. ISBN 978-1-56881-076-8. إل سي سي إن 97041258 . OL 2730675W .  
• هيرفيه مولان (2004). التقسيم العادل والرفاه الجماعي . كامبريدج، ماساتشوستس: مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 9780262134231.
• باربانيل، يوليوس ب. (2005). هندسة التقسيم العادل الفعال . مقدمة بقلم آلان د. تايلور. كامبريدج: مطبعة جامعة كامبريدج. doi : 10.1017/CBO9780511546679 . ISBN 0-521-84248-4MR 2132232​​ يتوفر ملخص موجز على الرابط التالي: باربانيل، ج. (2010). "مقاربة هندسية للقسمة العادلة". مجلة الرياضيات الجامعية . 41 (4): 268. doi : 10.4169/074683410x510263 .
• ستيفن ج. برامز (2008). الرياضيات والديمقراطية: تصميم إجراءات تصويت أفضل وتقسيم عادل . برينستون، نيوجيرسي: مطبعة جامعة برينستون. ISBN 9780691133218.

• فينسنت ب. كروفورد (1987). "التقسيم العادل"، قاموس نيو بالغراف: قاموس الاقتصاد ، المجلد 2، الصفحات  274-275.
• هال فاريان (1987). "الإنصاف"، قاموس بالغراف الجديد: قاموس الاقتصاد ، المجلد 2، الصفحات  275-276.
• برايان سكيرمز (1996). تطور العقد الاجتماعي. مطبعة جامعة كامبريدج. رقم ISBN 978-0-521-55583-8
• هيل، تي بي (2000). "أدوات رياضية للحصول على حصة عادلة". مجلة ساينتست الأمريكية . 88 (4): 325-331 . رمز Bibcode : 2000AmSci..88..325H . doi : 10.1511/2000.4.325 . S2CID 221539202 . 
• براندت، فيليكس؛ كونيتزر، فنسنت؛ إندريس، أولي؛ لانغ، جيروم؛ بروكاسيا، أرييل د. (2016). دليل الاختيار الاجتماعي الحاسوبي . مطبعة جامعة كامبريدج. ISBN 9781107060432.، الفصول من 11 إلى 13.
• القسمة العادلة بقلم كريستيان كلاملر - في كتيب اتخاذ القرارات الجماعية والتفاوض، الصفحات 183-202.
• تقطيع الكعكة: التقسيم العادل للسلع القابلة للتقسيم بقلم كلوديا ليندنر ويورغ روث - في الاقتصاد والحوسبة، الصفحات 395-491.
• القسمة العادلة للسلع غير القابلة للتجزئة بقلم جيروم لانج ويورغ روث - في الاقتصاد والحوسبة، الصفحات 493-550.

• القسمة العادلة من مشروع الرياضيات المتقطعة في جامعة كولورادو في بولدر.
• تقسيم المعرض: طريقة العلامات
• القسم العادل: طريقة العطاءات المختومة