تقطيع الكعكة بشكل عادل

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

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

الإجراء النموذجي لتقسيم الكعكة بشكل عادل هو "التقسيم والاختيار" ، والذي ورد ذكره في سفر التكوين لحل نزاع إبراهيم ولوط . يحل هذا الإجراء مشكلة التقسيم العادل لشخصين. بدأت الدراسات الحديثة لتقسيم الكعكة بشكل عادل خلال الحرب العالمية الثانية ، عندما طلب هوغو شتاينهاوس من تلميذيه ستيفان باناش وبرونيسواف كناستر إيجاد تعميم لـ"التقسيم والاختيار" ليشمل ثلاثة أشخاص أو أكثر. وقد طورا إجراء "المُصغِّر الأخير" . [ ^{1 ] اليوم} ، يُعد تقسيم الكعكة بشكل عادل موضوعًا لبحوث مكثفة في الرياضيات وعلوم الحاسوب والاقتصاد والعلوم السياسية . ^[²^]

الافتراضات

هناك كعكة C ، والتي يفترض عادة أنها إما قطعة محدودة أحادية البعد، أو مضلع ثنائي الأبعاد، أو مجموعة فرعية محدودة من المستوى الإقليدي متعدد الأبعاد R ^d .

يوجد n شخصًا لديهم _دوال قيمة ذاتية على C. لكل شخص i دالة قيمة Vi تُسقط مجموعات جزئية من C على أعداد. يُفترض أن جميع دوال القيمة متصلة اتصالًا مطلقًا بالنسبة للطول أو المساحة أو (بشكل عام) مقياس ليبيغ . ^[³^] هذا يعني أنه لا توجد "ذرات" - أي لا توجد نقاط شاذة يُسند إليها شخص أو أكثر قيمة موجبة، وبالتالي فإن جميع أجزاء الكعكة قابلة للقسمة. في كثير من الحالات، يُفترض أن دوال القيمة جمعية سيجما (قيمة الكل تساوي مجموع قيم أجزائه).

يجب تقسيم المجموعة C إلى n مجموعة جزئية منفصلة، بحيث يحصل كل شخص على مجموعة جزئية منفصلة. تُسمى القطعة المخصصة للشخص i $X_{i}$ ، و $C=X_{1}\cup \cdots \cup X_{n}$ .

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

في الأمثلة التالية، سيتم استخدام الكعكة التالية كمثال توضيحي.

تتكون الكعكة من جزأين: الشوكولاتة والفانيليا.
هناك شخصان: أليس وجورج.
أليس تقدر قيمة الشوكولاتة بـ 9 وقيمة الفانيليا بـ 1.
يُقيّم جورج الشوكولاتة بـ 6 والفانيليا بـ 4.

متطلبات العدالة

التناسب

المعيار الأصلي والأكثر شيوعًا للعدالة هو التناسب . في عملية تقسيم الكعكة بالتناسب ، يحصل كل شخص على قطعة يقدر قيمتها بما لا يقل عن 1/ ن من قيمة الكعكة كاملة. في مثال الكعكة، يمكن تحقيق التقسيم بالتناسب بإعطاء جورج كل الفانيليا و4/9 من الشوكولاتة (بقيمة 6.66)، وأليس 5/9 المتبقية من الشوكولاتة (بقيمة 5). بالرموز:

\forall {i}:\ V_{i}(X_{i})\geq 1/n

بالنسبة لعدد n من الأشخاص ذوي التقييمات الجمعية، يوجد دائمًا تقسيم نسبي. البروتوكولات الأكثر شيوعًا هي:

بروتوكول "المُصغِّر الأخير " يضمن أن تكون القطع n متصلة (أي لا يحصل أي لاعب على مجموعة من قطعتين أو أكثر غير متصلتين). وبالتحديد، إذا كانت الكعكة عبارة عن فاصل زمني أحادي البعد ^، فإن كل لاعب يحصل على فاصل زمني. هذا البروتوكول منفصل ويمكن تطبيقه بالتناوب، ويتطلب O( n² ) من الإجراءات.
إجراء دوبينز-سبانير ذو السكين المتحرك هو نسخة زمنية مستمرة من إجراء Last mininer. ^{[ 4 ]}
بروتوكول فينك (المعروف أيضًا باسم الأزواج المتتالية أو بروتوكول الاختيار الفردي ) هو بروتوكول منفصل يُستخدم للتقسيم الفوري: عند وجود تقسيم نسبي لـ n − 1 شريكًا، يقوم البروتوكول بتعديل التقسيم الحالي عند انضمام شريك جديد، بحيث يبقى لكل من الشريك الجديد والشركاء الحاليين حصة 1/ n . لكن يعيب هذا البروتوكول حصول كل شريك على عدد كبير من القطع غير المتصلة.
يعتمد بروتوكول إيفن-باز ، القائم على تقسيم الكعكة ومجموعة العناصر إلى نصفين بشكل متكرر، على عدد O( n log n ) من الإجراءات فقط. وهو أسرع بروتوكول حتمي ممكن للتقسيم النسبي، وأسرع بروتوكول ممكن للتقسيم النسبي يضمن ترابط القطع.
بروتوكول إدموندز-بروهس هو بروتوكول عشوائي يتطلب فقط O( n ) إجراء، ولكنه يضمن فقط تقسيمًا جزئيًا متناسبًا (يحصل كل شريك على الأقل على 1/ an ، حيث a ثابت ما)، وقد يعطي كل شريك مجموعة من "الفتات" بدلاً من قطعة واحدة متصلة.
يمكن لبروتوكول بيك لتقسيم الأراضي أن ينتج عنه تقسيم نسبي للأراضي المتنازع عليها بين عدة دول متجاورة، بحيث تحصل كل دولة على حصة متصلة ومجاورة لأراضيها التي تسيطر عليها حاليًا.
ينتج عن بروتوكول التقسيم المتناسب الفائق لوودال تقسيمًا يعطي كل شريك أكثر من 1/ ن ، بشرط أن يكون لدى شريكين على الأقل آراء مختلفة حول قيمة قطعة واحدة على الأقل.

انظر قسم تقطيع الكيك النسبي لمزيد من التفاصيل والمراجع الكاملة.

يمكن تعميم معيار التناسب ليشمل الحالات التي لا تتساوى فيها حقوق الأفراد. على سبيل المثال، في توزيع الكعكة بالتناسب مع استحقاقات مختلفة ، تُوزّع الكعكة على المساهمين بحيث يمتلك أحدهم 20% والآخر 80% منها. وهذا ما يُفضي إلى معيار التناسب المرجّح .

\forall i:V_{i}(X_{i})\geq w_{i}

حيث تمثل w _i الأوزان التي مجموعها يساوي 1.

التحرر من الحسد

معيار شائع آخر هو انعدام الحسد . في عملية تقطيع الكعكة الخالية من الحسد ، يحصل كل شخص على قطعة يقدرها على الأقل بقدر تقديره لأي قطعة أخرى. بالرموز:

\forall i,j:\ V_{i}(X_{i})\geq V_{i}(X_{j})

في بعض الحالات، توجد علاقات ضمنية بين التناسب وعدم وجود حسد، كما هو ملخص في الجدول التالي:

الوكلاء	التقييمات	هل يعني EF بالضرورة PR؟	هل يعني PR بالضرورة EF؟
2	مادة مضافة	نعم	نعم
2	عام	لا	لا
3+	مادة مضافة	نعم	لا
3+	عام	لا	لا

يجد بروتوكول التقسيم والاختيار تخصيصًا يكون دائمًا EF. إذا كانت دوال القيمة جمعية، فإن هذا التقسيم يكون أيضًا PR؛ وإلا، فإن التناسب غير مضمون.

يوجد تقسيم EF لعدد n من الأشخاص حتى عندما لا تكون التقييمات قابلة للجمع، طالما يمكن تمثيلها كمجموعات تفضيل متسقة. وقد دُرِسَ تقسيم EF بشكل منفصل في حالة ضرورة اتصال الأجزاء، وفي الحالة الأسهل التي يمكن فيها فصل الأجزاء.

أما بالنسبة للأجزاء المتصلة، فإن النتائج الرئيسية هي:

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

كلا الخوارزميتين لا نهائيتان: الأولى متصلة، والثانية قد تستغرق وقتًا لا نهائيًا للتقارب. في الواقع، لا يمكن إيجاد تقسيمات خالية من الحسد لفترات متصلة إلى 3 أشخاص أو أكثر باستخدام أي بروتوكول محدود.

أما بالنسبة للأجزاء التي قد تكون منفصلة، فإن النتائج الرئيسية هي:

تُنتج عملية سيلفريدج-كونواي المنفصلة تقسيمًا خاليًا من الحسد لثلاثة أشخاص باستخدام خمسة قطع على الأكثر.
تُنتج عملية برامز-تايلور-زويكر باستخدام السكاكين المتحركة تقسيمًا خاليًا من الحسد لأربعة أشخاص باستخدام 11 قطعًا كحد أقصى.
يجد أحد المتغيرات القابلة لإعادة الدخول لبروتوكول Last Diminiher تقريبًا جمعيًا لعملية قسمة خالية من الحسد في وقت محدود. على وجه التحديد، لكل ثابت $\epsilon >0$ ، تُعيد هذه العملية قسمة يكون فيها قيمة كل شريك على الأقل مساوية لأكبر قيمة مطروحًا منها $\epsilon$ مع مرور الوقت $O(n^{2}/\epsilon )$ .
تُنتج ثلاث طرق مختلفة، إحداها لبرامز وتايلور (1995)، والأخرى لروبرتسون وويب (1998)، والثالثة لبيخوركو (2000)، تقسيمًا خاليًا من الحسد لعدد n من الأشخاص. تتطلب كلتا الخوارزميتين عددًا محدودًا من عمليات القطع، ولكنه غير محدود.
وجدت طريقة قام بها عزيز وماكنزي (2016) ^{[ 7 ]} تقسيمًا خاليًا من الحسد لعدد n من الأشخاص في عدد محدود من الاستعلامات.

تكون النتيجة السلبية في الحالة العامة أضعف بكثير منها في الحالة المتصلة. كل ما نعرفه هو أن كل خوارزمية للقسمة الخالية من الحسد يجب أن تستخدم على الأقل Ω( ^n²) استعلامًا. هناك فجوة كبيرة بين هذه النتيجة وتعقيد وقت التشغيل لأفضل إجراء معروف.

راجع قسم تقطيع الكيك الخالي من الحسد لمزيد من التفاصيل والمراجع الكاملة.

معايير أخرى

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

\forall i,j:\ V_{i}(X_{i})=V_{j}(X_{j})

المعيار الرابع هو الدقة . إذا كان حق كل شريك i هو w _i ، فإن التقسيم الدقيق هو التقسيم الذي فيه:

\forall {i,j}:\ V_{i}(X_{j})=w_{j}

إذا كانت الأوزان متساوية (إلى 1/ ن )، فإن القسمة تسمى قسمة تامة و:

\forall i,j:\ V_{i}(X_{j})=1/n

التقسيم العادل الاحتمالي

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

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

p_{i}={\frac {\exp(\beta s_{i})}{\sum _{j}\exp(\beta s_{j})}}

هنا، $p_{i}$ هي الحصة المخصصة للمشارك $i$ ، $s_{i}$ هل هي درجة أو جدارة المشارك $i$ ، و $\beta$ هو معيار يتحكم في التوازن بين المساواة والتوزيع القائم على الجدارة. عندما $\beta =0$ وبالتالي، تُختزل الطريقة إلى قسمة متساوية. $\beta$ مع ازدياد عدد المشاركين، يصبح التوزيع أكثر ترجيحاً نحو المشاركين ذوي الدرجات الأعلى.

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

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

المتطلبات الهندسية

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

القيد الأكثر شيوعًا هو الاتصال . فإذا كانت "الكعكة" عبارة عن فاصل زمني أحادي البعد، فإن هذا يعني أن كل قطعة منها عبارة عن فاصل زمني أيضًا. أما إذا كانت الكعكة عبارة عن دائرة أحادية البعد ("فطيرة")، فإن هذا يعني أن كل قطعة منها عبارة عن قوس؛ انظر إلى تقطيع الفطيرة بشكل عادل .
هناك قيد آخر هو التجاور . ينطبق هذا القيد على حالة كون "الكعكة" منطقة متنازع عليها يجب تقسيمها بين الدول المجاورة. في هذه الحالة، قد يُشترط أن تكون القطعة المخصصة لكل دولة مجاورة لأراضيها الحالية؛ ويتم التعامل مع هذا القيد من خلال مسألة تقسيم الأراضي لهيل .
في تقسيم الأراضي، توجد في كثير من الأحيان قيود هندسية ثنائية الأبعاد، على سبيل المثال، يجب أن تكون كل قطعة مربعة أو (بشكل عام) جسمًا سميكًا . ^{[ 9 ]}

المتطلبات الإجرائية

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

يعني مبدأ الصدق الضعيف أنه إذا كشف الشريك عن قيمته الحقيقية للخوارزمية، فإنه يضمن الحصول على نصيبه العادل (مثلاً، 1/ ن من قيمة الكعكة كاملةً، في حالة التقسيم النسبي)، بغض النظر عما يفعله الشركاء الآخرون. حتى لو تحالف جميع الشركاء الآخرين بقصد الإضرار به فقط، فإنه سيظل يحصل على حصته المضمونة. معظم خوارزميات تقسيم الكعكة صادقة بهذا المعنى. ^{[ 1 ]}
تعني الصراحة التامة أنه لا يمكن لأي شريك أن يستفيد من الكذب. أي أن قول الحقيقة استراتيجية أساسية . معظم بروتوكولات تقسيم الكعكة لا تتسم بالصراحة التامة، ولكن تم تطوير بعض البروتوكولات الصادقة؛ انظر: تقسيم الكعكة الصادق .

ومن الخصائص الأخرى التناظر : إذ لا ينبغي أن يكون هناك فرق بين الأدوار المختلفة في الإجراء. وقد دُرست عدة صيغ لهذه الخاصية:

تتطلب السرية أنه في حال تبديل مواقع العناصر وإعادة تنفيذ الإجراء، فإن كل عنصر يتلقى نفس الجزء تمامًا كما في التنفيذ الأصلي. هذا شرط أساسي؛ ففي الوقت الحالي، لا يُعرف الإجراء المجهول إلا لعنصرين فقط.
تتطلب خاصية التناظر أنه إذا تم تبديل مواقع العناصر وإعادة تنفيذ الإجراء، فإن كل عنصر يحصل على نفس القيمة التي حصل عليها في التنفيذ الأصلي. وهذا أضعف من خاصية إخفاء الهوية؛ حاليًا، يوجد إجراء متناظر ومتناسب معروف لأي عدد من العناصر، ويستغرق O( n³ ) من الاستعلامات. كما يوجد إجراء متناظر وخالٍ من الحسد معروف لأي عدد من العناصر، ولكنه يستغرق وقتًا أطول بكثير - إذ يتطلب n ! من عمليات تنفيذ الإجراء الخالي ^من الحسد الموجود.
يقتضي مبدأ أرسطو أنه إذا كان لدى وكيلين نفس مقياس القيمة، فإنهما يحصلان على نفس القيمة. وهذا المبدأ أضعف من مبدأ التناظر؛ إذ يتحقق بأي إجراء خالٍ من الحسد. علاوة على ذلك، يُعرف إجراء أرسطوي وتناسبي لأي عدد من الوكلاء، ويستغرق O( n³ ⁾ من الاستعلامات.

انظر إلى قسم تقطيع الكعكة المتناظرة للاطلاع على التفاصيل والمراجع.

ثمة فئة ثالثة من المتطلبات الإجرائية وهي الرتابة : فعند إعادة تطبيق إجراء التقسيم مع كعكة أصغر/أكبر ومجموعة أصغر/أكبر من الوكلاء، يجب أن تتغير فائدة جميع الوكلاء في الاتجاه نفسه. انظر رتابة الموارد لمزيد من التفاصيل.

متطلبات الكفاءة

إلى جانب العدالة، من الشائع أيضاً مراعاة الكفاءة الاقتصادية للتقسيم؛ انظر: تقسيم الكعكة بكفاءة . وهناك عدة مستويات من الكفاءة:

المفهوم الأضعف هو كفاءة باريتو . يمكن تحقيقها بسهولة بمجرد إعطاء الكعكة بأكملها لشخص واحد؛ لكن التحدي يكمن في تحقيقها بالتزامن مع العدالة. انظر: التقسيم الكفء الخالي من الحسد .
المفهوم الأقوى هو مفهوم النفعية القصوى - أي تعظيم مجموع المنافع. (UM). عندما تكون دوال القيمة جمعية، توجد تقسيمات UM. وبشكل بديهي، لإنشاء تقسيم UM، ينبغي أن نعطي كل قطعة من الكعكة للشخص الذي يُقدّرها أكثر. في مثال الكعكة ، يُعطي تقسيم UM قطعة الشوكولاتة كاملة لأليس وقطعة الفانيليا كاملة لجورج، محققًا قيمة نفعية قدرها 9 + 4 = 13. يسهل تنفيذ هذه العملية عندما تكون دوال القيمة ثابتة جزئيًا، أي يمكن تقسيم الكعكة إلى قطع بحيث تكون كثافة قيمة كل قطعة ثابتة لجميع الأشخاص. عندما لا تكون دوال القيمة ثابتة جزئيًا، فإن وجود تخصيصات UM يتبع من نظريات القياس الكلاسيكية. انظر: تقطيع الكعكة النفعي .

تقسيم عادل وفعال

بالنسبة لعدد n من الأشخاص الذين لديهم دوال قيمة جمعية، يوجد دائمًا قسمة PEEF. هذه هي نظرية ويلر . ^{[ 10 ]}

إذا كانت الكعكة عبارة عن فترة أحادية البعد ، وكان على كل شخص الحصول على فترة متصلة، فإن النتيجة العامة التالية صحيحة: إذا كانت دوال القيمة رتيبة تمامًا (أي أن كل شخص يفضل قطعة على جميع مجموعاتها الجزئية المناسبة)، فإن كل تقسيم EF هو أيضًا PE. ^{[ 11 ]} وبالتالي، ينتج عن بروتوكول سيمونز تقسيم PEEF في هذه الحالة.

إذا كانت الكعكة عبارة عن دائرة أحادية البعد (أي فترة زمنية محددة نقطتا نهايتها طوبولوجيًا) وكان على كل شخص الحصول على قوس متصل، فإن النتيجة السابقة لا تنطبق: فالتقسيم EF ليس بالضرورة PE. إضافةً إلى ذلك، توجد أزواج من دوال القيمة (غير الجمعية) التي لا يوجد لها تقسيم PEEF. مع ذلك، إذا كان هناك شخصان، وكان لدى أحدهما على الأقل دالة قيمة جمعية، فإن تقسيم PEEF يكون موجودًا. ^{[ 12 ]}

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

إذا كانت دوال القيمة جمعية وثابتة جزئيًا، فهناك خوارزمية لإيجاد قسمة PEEF. ^{[ 13 ]} أما إذا كانت دوال كثافة القيمة جمعية ومستمرة وفقًا لشرط ليبشيتز ، فيمكن تقريبها كدوال ثابتة جزئيًا "بالدقة المطلوبة"، وبالتالي فإن تلك الخوارزمية تُقارب قسمة PEEF "بالدقة المطلوبة". ^{[ 13 ]}

لا يُعدّ تقسيم EF بالضرورة تقسيمًا UM. ^{[ 14 ]}^{[ 15 ]} يتمثل أحد أساليب معالجة هذه الصعوبة في إيجاد التقسيم ذي القيمة النفعية الأعلى من بين جميع تقسيمات EF الممكنة. وقد دُرست هذه المسألة في حالة كعكة تُمثّل فاصلًا أحادي البُعد، حيث يمكن لكل شخص الحصول على قطع منفصلة، وتكون دوال القيمة جمعية. ^{[ 16 ]}

نماذج الحوسبة

يتطلب تحليل تعقيد وقت تشغيل الخوارزميات نموذجًا للحساب . وتوجد عدة نماذج من هذا القبيل شائعة في الأدبيات العلمية:

نموذج استعلام روبرتسون-ويب - حيث يمكن للخوارزمية أن تطلب من كل وكيل استعلامًا من نوعين: "تقييم قطعة معينة من الكعكة" أو "وضع علامة على قطعة من الكعكة بقيمة معينة".
نموذج السكاكين المتحركة - حيث تقوم الخوارزمية بتحريك سكين واحد أو أكثر فوق الكعكة بشكل مستمر حتى يصرخ بعض العملاء "توقف".
نموذج الكشف المباشر – حيث يكشف جميع الفاعلين عن تقييمهم الكامل للآلية. لا يكون لهذا النموذج معنى إلا عندما يمكن تمثيل التقييمات بإيجاز، على سبيل المثال، عندما تكون منتظمة جزئياً، أو ثابتة جزئياً، أو خطية جزئياً .
نموذج التقارير المتزامنة - حيث يرسل الوكلاء في آنٍ واحدٍ تجزئاتٍ لمقاييس قيمهم. التجزئة هي سلسلة من نقاط القطع، وقيم الأجزاء الواقعة بين هذه النقاط (على سبيل المثال: قد يتطلب بروتوكولٌ لوكيلين أن يُبلغ كل وكيل عن سلسلة من ثلاث نقاط قطع (0، x ، 1) حيث تكون قيم (0، x ) و( x ، 1) هي 1/2). ^{[ 17 ]}

تقسيم عدة كعكات

هناك تعميم لمسألة تقطيع الكعكة حيث توجد عدة كعكات، ويحتاج كل عنصر إلى الحصول على قطعة من كل كعكة.

درس كلوتير، ونيمان، وسو ^{[ 18 ]} تقسيم الكعك المتعدد دون وجود حسد بين لاعبين. بالنسبة لكعكتين، أثبتوا أنه قد لا يوجد تخصيص خالٍ من الحسد عندما يكون هناك لاعبان وتُقطع كل كعكة إلى قطعتين. ومع ذلك، يوجد تخصيص خالٍ من الحسد عندما يكون هناك لاعبان وتُقطع إحدى الكعكتين إلى ثلاث قطع (تُستبعد القطعة الأقل رغبة)، أو عندما يكون هناك ثلاثة لاعبين وتُقطع كل كعكة إلى قطعتين (يُتجاهل أحد اللاعبين؛ ويكون التخصيص خاليًا من الحسد للاعبين المتبقيين).
يثبت ليبرت ومونييه وكاربونو ^{[ 19 ]} ، بالنسبة لكعكتين، أن تخصيص EF موجود دائمًا عندما يكون هناك 3 وكلاء ويتم تقطيع كل كعكة إلى 5 قطع (يتم التخلص من القطعتين الأقل رغبة في كل كعكة).
يثبت نيمان وسو وزربيب ^{[ 20 ]} ، بالنسبة لـ k كعكة، أن تخصيص EF موجود دائمًا عندما يكون هناك k ( n- 1)+1 من العملاء ويتم تقطيع كل كعكة إلى n قطعة (التخصيص هو EF لمجموعة معينة من n من العملاء).

هناك مشكلتان مرتبطتان هما:

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

انظر أيضاً

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

مراجع

1 2 شتاينهاوس، هوغو (1949). "مشكلة التقسيم العادل". إيكونومتريكا . 17 : 315-319 . doi : 10.2307/1907319 . JSTOR 1907319 .
↑ أرييل بروكاسيا، "خوارزميات تقطيع الكعكة". الفصل 13 في: براندت، فيليكس؛ كونيتزر، فنسنت؛ إندريس، أولي؛ لانغ، جيروم؛ بروكاسيا، أرييل د. (2016). دليل الاختيار الاجتماعي الحسابي . مطبعة جامعة كامبريدج. ISBN 9781107060432.
↑ هيل، تي بي؛ موريسون، كي إي (2010). "تقطيع الكعك بعناية". مجلة الرياضيات الجامعية . 41 (4): 281. CiteSeerX 10.1.1.185.656 . doi : 10.4169/074683410x510272 . S2CID 3813775 .
↑ دوبينز، ليستر إيلي ؛ سبانير، إدوين هنري (1961). "كيفية تقطيع الكعكة بشكل عادل". المجلة الرياضية الأمريكية الشهرية . 68 (1): 1-17 . doi : 10.2307/2311357 . JSTOR 2311357 .
↑ "حاسبة التقسيم العادل" . مؤرشفة من الأصل بتاريخ 28-02-2010 . تم الاطلاع عليها بتاريخ 10-07-2014 .
↑ إيفارز بيترسون (13 مارس 2000). "صفقة عادلة لزملاء السكن" . ماث تريك . مؤرشف من الأصل في 20 سبتمبر 2012. تم الاطلاع عليه في 10 يوليو 2014 .
↑ عزيز، حارث؛ ماكنزي، سيمون (27-08-2017). "بروتوكول منفصل ومحدود لتقسيم الكعكة خالٍ من الحسد لأي عدد من العملاء". arXiv : 1604.03655 [ cs.DS ].
↑ بارك، جيه-دبليو، كيم، سي يو، غيم، سي، وكيم، بي جيه (2022). تقسيم بولتزمان العادل لتحقيق العدالة التوزيعية. التقارير العلمية، 12، 15494. https://doi.org/10.1038/s41598-022-19792-3
^ سيجال هاليفي، إيريل؛ نيتسان، شموئيل؛ حسيديم، أفيناتان؛ أومان، يوناتان (2017). “عادل ومربع: قطع الكعكة في بعدين”. مجلة الاقتصاد الرياضي . 70 : 1 – 28. أرخايف : 1409.4511 . دوى : 10.1016/j.jmateco.2017.01.007 . S2CID 1278209 .
↑ ويلر، د. (1985). "التقسيم العادل لمساحة قابلة للقياس". مجلة الاقتصاد الرياضي . 14 : 5-17 . doi : 10.1016/0304-4068(85)90023-0 .
↑ بيرليانت، م.؛ طومسون، و.؛ دانز، ك. (1992). "حول التقسيم العادل لسلعة غير متجانسة". مجلة الاقتصاد الرياضي . 21 (3): 201. doi : 10.1016/0304-4068(92)90001-n .
↑ تومسون، و. (2006). "بكاء الأطفال في حفلات أعياد الميلاد. لماذا؟". النظرية الاقتصادية . 31 (3): 501-521 . doi : 10.1007/s00199-006-0109-3 . S2CID 154089829 .
1 2 رينيرس، جيه إتش؛ بوترز، جيه إيه إم (1998). "حول إيجاد تقسيم باريتو الأمثل الخالي من الحسد". البرمجة الرياضية . 83 ( 1-3 ): 291-311 . doi : 10.1007/bf02680564 . S2CID 10219505 .
^ كاراجيانيس، أنا. كاكلامانيس، C .؛ كانيلوبولوس، ب. كيروبولو، م. (2011). “كفاءة القسمة العادلة”. نظرية نظم الحوسبة . 50 (4): 589.سيتيسيركس 10.1.1.475.9976 . دوى : 10.1007/s00224-011-9359-ذ . S2CID 8755258 .
↑ أومان، ي.؛ دومب، ي. (2010). " كفاءة التقسيم العادل مع القطع المتصلة" . اقتصاديات الإنترنت والشبكات . سلسلة محاضرات في علوم الحاسوب. المجلد 6484. ص 26. CiteSeerX 10.1.1.391.9546 . doi : 10.1007/978-3-642-17572-5_3 . ISBN 978-3-642-17571-8.
↑ كوهلر، يوجا جوليان؛ لاي، جون كوانغ؛ باركس، ديفيد سي؛ بروكاسيا، أرييل (2011). تقطيع الكيك الأمثل بدون حسد . AAAI.
↑ بالكانسكي، إريك؛ برانزي، سيمينا؛ كوروكاوا، ديفيد؛ بروكاسيا، أرييل (21-06-2014). "تقطيع الكعكة في وقت واحد" . وقائع مؤتمر AAAI حول الذكاء الاصطناعي . 28 (1). doi : 10.1609/aaai.v28i1.8802 . ISSN 2374-3468 . S2CID 1867115 .
↑ كلوتير، جون؛ نيمان، كاثرين ل.؛ سو، فرانسيس إدوارد (2010-01-01). "تقسيم الكعكات المتعددة الخالي من الحسد بين لاعبين" . العلوم الاجتماعية الرياضية . 59 (1): 26-37 . arXiv : 0909.0301 . doi : 10.1016/j.mathsocsci.2009.09.002 . ISSN 0165-4896 . S2CID 15381541 .
↑ ليبرت، نيكولا؛ مونييه، فريدريك؛ كاربونو، كوينتين (2013-11-01). "تقسيمات الكعكة الثنائية الخالية من الحسد وتقسيمات الكعكة الثنائية الثلاثية" . رسائل بحوث العمليات . 41 (6): 607-610 . doi : 10.1016/j.orl.2013.07.010 . ISSN 0167-6377 . S2CID 7937916 .
↑ نيمان، كاثرين؛ سو، فرانسيس إدوارد؛ زربيب، شيرا (15 سبتمبر 2020). "القسمة العادلة مع قطع متعددة" . الرياضيات التطبيقية المنفصلة . 283 : 115-122 . arXiv : 1710.09477 . doi : 10.1016/j.dam.2019.12.018 . ISSN 0166-218X . S2CID 119602376 .
↑ حسيني، هادي؛ إيغاراشي، أيومي؛ سيرنز، أندرو (2020-04-28). "التقسيم العادل للوقت: تقطيع الكعكة متعددة الطبقات". arXiv : 2004.13397 [ cs.GT ].
↑ سيغال-هاليفي، إيريل (11 مارس 2021). "تقطيع الكعك المتعدد بشكل عادل" . الرياضيات التطبيقية المنفصلة . 291 : 15-35 . doi : 10.1016/j.dam.2020.10.011 . ISSN 0166-218X . S2CID 219792647 .

للمزيد من القراءة

قائمة بالكتب التي تتناول موضوع التقسيم العادل
قائمة بالأبحاث المتعلقة بالتقسيم العادل

[steinhaus48-1] 1 2 شتاينهاوس، هوغو (1949). "مشكلة التقسيم العادل". إيكونومتريكا . 17 : 315-319 . doi : 10.2307/1907319 . JSTOR 1907319 .

[handbook-2] أرييل بروكاسيا، "خوارزميات تقطيع الكعكة". الفصل 13 في: براندت، فيليكس؛ كونيتزر، فنسنت؛ إندريس، أولي؛ لانغ، جيروم؛ بروكاسيا، أرييل د. (2016). دليل الاختيار الاجتماعي الحسابي . مطبعة جامعة كامبريدج. ISBN 9781107060432.

[3] هيل، تي بي؛ موريسون، كي إي (2010). "تقطيع الكعك بعناية". مجلة الرياضيات الجامعية . 41 (4): 281. CiteSeerX 10.1.1.185.656 . doi : 10.4169/074683410x510272 . S2CID 3813775 .

[ds61-4] دوبينز، ليستر إيلي ؛ سبانير، إدوين هنري (1961). "كيفية تقطيع الكعكة بشكل عادل". المجلة الرياضية الأمريكية الشهرية . 68 (1): 1-17 . doi : 10.2307/2311357 . JSTOR 2311357 .

[5] "حاسبة التقسيم العادل" . مؤرشفة من الأصل بتاريخ 28-02-2010 . تم الاطلاع عليها بتاريخ 10-07-2014 .

[6] إيفارز بيترسون (13 مارس 2000). "صفقة عادلة لزملاء السكن" . ماث تريك . مؤرشف من الأصل في 20 سبتمبر 2012. تم الاطلاع عليه في 10 يوليو 2014 .

[7] عزيز، حارث؛ ماكنزي، سيمون (27-08-2017). "بروتوكول منفصل ومحدود لتقسيم الكعكة خالٍ من الحسد لأي عدد من العملاء". arXiv : 1604.03655 [ cs.DS ].

[8] بارك، جيه-دبليو، كيم، سي يو، غيم، سي، وكيم، بي جيه (2022). تقسيم بولتزمان العادل لتحقيق العدالة التوزيعية. التقارير العلمية، 12، 15494. https://doi.org/10.1038/s41598-022-19792-3

[9] سيجال هاليفي، إيريل؛ نيتسان، شموئيل؛ حسيديم، أفيناتان؛ أومان، يوناتان (2017). “عادل ومربع: قطع الكعكة في بعدين”. مجلة الاقتصاد الرياضي . 70 : 1 – 28. أرخايف : 1409.4511 . دوى : 10.1016/j.jmateco.2017.01.007 . S2CID 1278209 .

[w85-10] ويلر، د. (1985). "التقسيم العادل لمساحة قابلة للقياس". مجلة الاقتصاد الرياضي . 14 : 5-17 . doi : 10.1016/0304-4068(85)90023-0 .

[btd92-11] بيرليانت، م.؛ طومسون، و.؛ دانز، ك. (1992). "حول التقسيم العادل لسلعة غير متجانسة". مجلة الاقتصاد الرياضي . 21 (3): 201. doi : 10.1016/0304-4068(92)90001-n .

[t07-12] تومسون، و. (2006). "بكاء الأطفال في حفلات أعياد الميلاد. لماذا؟". النظرية الاقتصادية . 31 (3): 501-521 . doi : 10.1007/s00199-006-0109-3 . S2CID 154089829 .

[rp98-13] 1 2 رينيرس، جيه إتش؛ بوترز، جيه إيه إم (1998). "حول إيجاد تقسيم باريتو الأمثل الخالي من الحسد". البرمجة الرياضية . 83 ( 1-3 ): 291-311 . doi : 10.1007/bf02680564 . S2CID 10219505 .

[14] كاراجيانيس، أنا. كاكلامانيس، C .؛ كانيلوبولوس، ب. كيروبولو، م. (2011). “كفاءة القسمة العادلة”. نظرية نظم الحوسبة . 50 (4): 589.سيتيسيركس 10.1.1.475.9976 . دوى : 10.1007/s00224-011-9359-ذ . S2CID 8755258 .

[15] أومان، ي.؛ دومب، ي. (2010). " كفاءة التقسيم العادل مع القطع المتصلة" . اقتصاديات الإنترنت والشبكات . سلسلة محاضرات في علوم الحاسوب. المجلد 6484. ص 26. CiteSeerX 10.1.1.391.9546 . doi : 10.1007/978-3-642-17572-5_3 . ISBN 978-3-642-17571-8.

[clpp11-16] كوهلر، يوجا جوليان؛ لاي، جون كوانغ؛ باركس، ديفيد سي؛ بروكاسيا، أرييل (2011). تقطيع الكيك الأمثل بدون حسد . AAAI.

[17] بالكانسكي، إريك؛ برانزي، سيمينا؛ كوروكاوا، ديفيد؛ بروكاسيا، أرييل (21-06-2014). "تقطيع الكعكة في وقت واحد" . وقائع مؤتمر AAAI حول الذكاء الاصطناعي . 28 (1). doi : 10.1609/aaai.v28i1.8802 . ISSN 2374-3468 . S2CID 1867115 .

[18] كلوتير، جون؛ نيمان، كاثرين ل.؛ سو، فرانسيس إدوارد (2010-01-01). "تقسيم الكعكات المتعددة الخالي من الحسد بين لاعبين" . العلوم الاجتماعية الرياضية . 59 (1): 26-37 . arXiv : 0909.0301 . doi : 10.1016/j.mathsocsci.2009.09.002 . ISSN 0165-4896 . S2CID 15381541 .

[19] ليبرت، نيكولا؛ مونييه، فريدريك؛ كاربونو، كوينتين (2013-11-01). "تقسيمات الكعكة الثنائية الخالية من الحسد وتقسيمات الكعكة الثنائية الثلاثية" . رسائل بحوث العمليات . 41 (6): 607-610 . doi : 10.1016/j.orl.2013.07.010 . ISSN 0167-6377 . S2CID 7937916 .

[20] نيمان، كاثرين؛ سو، فرانسيس إدوارد؛ زربيب، شيرا (15 سبتمبر 2020). "القسمة العادلة مع قطع متعددة" . الرياضيات التطبيقية المنفصلة . 283 : 115-122 . arXiv : 1710.09477 . doi : 10.1016/j.dam.2019.12.018 . ISSN 0166-218X . S2CID 119602376 .

[21] حسيني، هادي؛ إيغاراشي، أيومي؛ سيرنز، أندرو (2020-04-28). "التقسيم العادل للوقت: تقطيع الكعكة متعددة الطبقات". arXiv : 2004.13397 [ cs.GT ].

[22] سيغال-هاليفي، إيريل (11 مارس 2021). "تقطيع الكعك المتعدد بشكل عادل" . الرياضيات التطبيقية المنفصلة . 291 : 15-35 . doi : 10.1016/j.dam.2020.10.011 . ISSN 0166-218X . S2CID 219792647 .

1 ] اليوم

[

[

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗