تقطيع الكعكة بشكل متناسب مع استحقاقات مختلفة

في مسألة تقسيم الكعكة بشكل عادل ، غالبًا ما يمتلك الشركاء حقوقًا مختلفة. على سبيل المثال، قد يكون المورد ملكًا لمساهمين اثنين، بحيث تمتلك أليس 8/13 ويمتلك جورج 5/13. وهذا يقودنا إلى معيار التناسب المرجح : حيث توجد عدة أوزان.${\displaystyle w_{i}}$مجموعها يساوي 1، وكل شريك${\displaystyle i}$ينبغي أن يحصل على جزء على الأقل${\displaystyle w_{i}}$من الموارد من خلال تقييمهم الخاص.

في المقابل، في عملية تقطيع الكعكة النسبية الأبسط ، تكون الأوزان متساوية:${\displaystyle w_{i}=1/n}$للجميع${\displaystyle i}$

يمكن استخدام العديد من الخوارزميات لإيجاد قسم WPR.

لنفترض أن جميع الأوزان أعداد نسبية ذات مقام مشترك${\displaystyle D}$إذن، الأوزان هي${\displaystyle p_{1}/D,\dots ,p_{n}/D}$، مع${\displaystyle p_{1}+\cdots +p_{n}=D}$لكل لاعب${\displaystyle i}$، يخلق${\displaystyle p_{i}}$النسخ المستنسخة التي لها نفس مقياس القيمة. إجمالي عدد النسخ المستنسخة هو${\displaystyle D}$أوجد توزيعًا متناسبًا للكعكة بينهم. وأخيرًا، أعطِ كل شريك ما يحتاجه.${\displaystyle i}$أجزاء منه${\displaystyle p_{i}}$المستنسخات.

يُظهر روبرتسون وويب ^{[ 1 ] : 36} إجراءً أبسط لشريكين: تقوم أليس بتقطيع الكعكة إلى${\displaystyle D}$القطع متساوية في نظرها؛ يختار جورج${\displaystyle p_{G}}$أكثر القطع قيمة في نظره، وتأخذ أليس الباقي${\displaystyle p_{A}}$قطع. (هذا تطبيق لإجراء التقسيم والاختيار .)

يتطلب هذا الإجراء البسيط قطع D، لذا${\displaystyle D-1}$قد تكون عمليات التقسيم كثيرة جدًا. على سبيل المثال، إذا كانت أليس تستحق 8/13 وجورج يستحق 5/13، فإن 13-1=12 عملية تقسيم مطلوبة في التقسيم الأولي.

عدد الاستعلامات المطلوبة هو${\displaystyle D\lceil \log _{2}(D)\rceil .}$

لنفترض أن كعكة يجب تقسيمها بين أليس وجورج، حيث يحق لأليس الحصول على 8/13 ويحق لجورج الحصول على 5/13. يمكن تقسيم الكعكة على النحو التالي.

• قامت أليس بتقطيع الكعكة إلى 6 قطع بنسب تقييم 5:3:2:1:1:1 .
• يقوم جورج بتحديد القطع التي لها بالنسبة له على الأقل القيمة التي ذكرتها أليس.

والآن هناك حالتان "جيدتان" - حالتان يمكننا فيهما استخدام هذه الأجزاء لتحقيق تقسيم متناسب مرجح يحترم الاستحقاقات المختلفة:

هناك العديد من التوليفات بين القطع التي تمنح كل قطعة نصيبها المستحق.

الحالة الأولى: يتم الحصول على مجموعة جزئية من القطع مجموعها 5 إذا قام جورج بتحديد القطعة رقم 3 وقطعتين من القطع الثلاث رقم 1. ثم تُعطى هذه المجموعة الجزئية لجورج، ويُعطى الباقي لأليس. الآن، يمتلك جورج 5/13 على الأقل، بينما تمتلك أليس 8/13 تقريبًا.

الحالة الثانية: يتم الحصول على مجموعة جزئية من القطع مجموعها 8 إذا قامت أليس بتحديد القطعة ذات الحجم 5 والقطعة ذات الحجم 3. ثم تُعطى هذه المجموعة الجزئية لأليس، ويُعطى الباقي لجورج. الآن، لدى أليس 8/13 ولدى جورج 5/13 على الأقل.

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

McAvaney و Robertson و Webb ^{[ 1 ] : 36-41 [ 2 ]} يعممون هذه الفكرة باستخدام مفهوم تقسيمات رامزي (سميت على اسم نظرية رامزي ).

رسميًا: إذا${\displaystyle k_{1}}$و${\displaystyle k_{2}}$هي أعداد صحيحة موجبة، وهي تجزئة${\displaystyle P}$ل${\displaystyle k_{1}+k_{2}}$يُطلق عليه اسم تقسيم رامزي للزوج${\displaystyle k_{1},k_{2}}$، إن وجدت قائمة فرعية${\displaystyle L\subseteq P}$إما أن هناك قائمة فرعية من${\displaystyle L}$وهو ما يعادل${\displaystyle k_{1}}$أو توجد قائمة فرعية من${\displaystyle P\setminus L}$وهو ما يعادل${\displaystyle k_{2}}$.

في المثال أعلاه،${\displaystyle k_{1}=8}$و${\displaystyle k_{2}=5}$والتقسيم هو 5:3:2:1:1:1، وهو تقسيم رامزي. علاوة على ذلك، يُعد هذا أقصر تقسيم رامزي في هذه الحالة، مما يسمح لنا باستخدام عدد قليل من عمليات القطع.

توجد تقسيمات رامزي دائمًا. علاوة على ذلك، يوجد دائمًا تقسيم رامزي أقصر فريد. يمكن إيجاده باستخدام صيغة مبسطة من خوارزمية إقليدس . تعتمد الخوارزمية على اللمة التالية: ^{[ 1 ] : 143-144}

لو${\displaystyle p_{1}<a<b}$، و${\displaystyle P=(p_{1},\dots ,p_{n})}$هو تقسيم لـ${\displaystyle b}$، و${\displaystyle P'=(b,p_{1},\dots ,p_{n})}$، ثم${\displaystyle P'}$هو تقسيم لـ${\displaystyle a+b}$. علاوة على ذلك،${\displaystyle P'}$هو تقسيم رامزي الأدنى للزوج${\displaystyle a,b}$إذا وفقط إذا${\displaystyle P}$هو تقسيم رامزي الأدنى للزوج${\displaystyle a,ba}$.

تؤدي هذه اللمة إلى الخوارزمية التكرارية التالية.

${\displaystyle FindMinimalRmsey(a,b)}$:

1. رتب المدخلات بحيث${\displaystyle a<b}$.
2. يدفع${\displaystyle a}$.
3. لو${\displaystyle a=ba=1}$ثم ادفع${\displaystyle 1,1}$وانتهى الأمر.
4. لو${\displaystyle ba\neq 1}$، ثم${\displaystyle FindMinimalRmsey(a,ba)}$.

بمجرد العثور على تقسيم رامزي الأدنى، يمكن استخدامه للعثور على تقسيم WPR الذي يحترم الحقوق.

تحتاج الخوارزمية على الأقل${\displaystyle \log _{\phi }\min(a,b)}$القطع، حيث ${\displaystyle \phi =(1+{\sqrt {5}})/2}$هي النسبة الذهبية . في معظم الحالات، يكون هذا الرقم أفضل من اتخاذ إجراء آخر.${\displaystyle a+b-1}$تخفيضات. ولكن إذا${\displaystyle a=1}$، ثم${\displaystyle b=a+b-1}$هناك حاجة إلى إجراء تخفيضات، لأن قسم رامزي الوحيد للزوج${\displaystyle b,1}$هي سلسلة مع${\displaystyle b+1}$تلك.

لنفترض مرة أخرى أن أليس تستحق 8/13 وجورج يستحق 5/13. يمكن تقسيم الكعكة على النحو التالي.

• قام جورج بتقطيع الكعكة إلى قطعتين بنسبة 7:6.
• تختار أليس قطعة واحدة، تساوي قيمتها بالنسبة لها على الأقل قيمتها المعلنة. لننظر في حالتين:
  • تختار أليس الرقم 7. بعد ذلك، يحق لأليس الحصول على رقم إضافي واحد، ويجب تقسيم القطعة المتبقية بنسبة 5:1.
  • تختار أليس الرقم 6. بعد ذلك، يحق لأليس الحصول على رقمين إضافيين، ويجب تقسيم القطعة المتبقية بنسبة 5:2.
• في كلتا الحالتين، تكون القطعة المتبقية أصغر والنسبة أصغر. في النهاية، تصبح النسبة 1:1 ويمكن تقسيم الكعكة المتبقية باستخدام أداة التقطيع والاختيار .

الفكرة العامة مشابهة لبروتوكول إيفن-باز : ^{[ 1 ] : 42-44}${\displaystyle CutNearHalves(a,b)}$:

1. رتب المدخلات بحيث${\displaystyle a<b}$لنفترض أن أليس يحق لها${\displaystyle b/(a+b)}$ويحق لجورج أن${\displaystyle a/(a+b)}$.
2. اطلب من جورج أن يقطع الكعكة إلى نصفين تقريباً، أي:
   • لو${\displaystyle a+b}$حتى في هذه الحالة، يقطع جورج الكعكة إلى قطعتين متساويتين في نظره؛
   • لو${\displaystyle a+b}$إذا كان الأمر غريبًا، فإن جورج يقطع الكعكة إلى قطعتين، ونسبة تقييمهما هي${\displaystyle (a+b-1)/2:(a+b+1)/2}$في عينيه.
3. قطعة واحدة على الأقل تساوي لأليس على الأقل القيمة التي أعلنها جورج؛ أعطي هذه القطعة لأليس.
4. لنفترض أن القطعة التي أخذتها أليس هي القطعة ذات القيمة${\displaystyle c/(a+b)}$، أين${\displaystyle c\in \{(a+b-1)/2,(a+b)/2,(a+b+1)/2)}$. يتصل${\displaystyle CutNearHalves(b,ac)}$.

تحتاج خوارزمية القطع القريبة من النصفين إلى أكثر من${\displaystyle \log _{2}\min(a,b)}$لذا فهي دائمًا أكثر كفاءة من خوارزمية تقسيم رامزي.

خوارزمية القطع إلى نصفين متقاربين ليست مثالية دائمًا. على سبيل المثال، لنفترض أن النسبة هي 7:3.

• قد تحتاج عملية تقسيم الأشياء إلى نصفين تقريبًا إلى أربع عمليات تقطيع على الأقل: أولًا، يقوم جورج بالتقطيع بنسبة 5:5، وتحصل أليس على 5. ثم، تقوم أليس بالتقطيع بنسبة 3:2؛ لنفترض أن جورج اختار 2. ثم، يقوم جورج بالتقطيع بنسبة 2:1؛ لنفترض أن أليس اختارت 1. أخيرًا، يقومون بالتقطيع والاختيار على الباقي.
• يمكننا تحسين العملية بجعل جورج يقطع بنسبة 6:4. إذا اختارت أليس الرقم 4، تصبح النسبة 3:3، ويمكننا استخدام أسلوب القطع والاختيار مباشرةً. إذا اختارت أليس الرقم 6، تصبح النسبة 3:1. تقطع أليس بنسبة 2:2، ويختار جورج الرقم 2، فنحتاج إلى خطوة إضافية من أسلوب القطع والاختيار. إجمالاً، نحتاج إلى ثلاث عمليات قطع على الأكثر.

يبقى السؤال مفتوحاً حول كيفية إيجاد أفضل نسبة استحقاق أولية لكل نسبة.

يمكن تعميم الخوارزمية لتشمل n من الوكلاء؛ وعدد الاستعلامات المطلوبة هو${\displaystyle n(n-1)\lceil \log _{2}(D)\rceil .}$

قدم تشيه وفلاينر ^{[ 3 ]} خوارزمية لتقسيم كعكة متعددة الأبعاد بين أي عدد من الوكلاء ذوي أي استحقاقات (بما في ذلك الاستحقاقات غير المنطقية)، في عدد محدود من الاستعلامات. تتطلب خوارزميتهم${\displaystyle 2(n-1)\lceil \log _{2}(D)\rceil }$تُعدّ الاستعلامات في نموذج استعلام روبرتسون-ويب أكثر كفاءة من استنساخ الوكلاء وتقسيم النتائج إلى نصفين. وقد أثبتت هذه الدراسات أن تعقيد وقت التشغيل هذا هو الأمثل.

عندما لا تكون الاستحقاقات أعدادًا نسبية، لا يمكن استخدام الطرق القائمة على الاستنساخ لأن المقام يكون لانهائيًا. قدم شيشيدو وزينغ خوارزمية تُسمى " التحديد والقطع والاختيار" ، والتي يمكنها أيضًا التعامل مع الاستحقاقات غير النسبية، ولكن مع عدد غير محدود من عمليات القطع. ^{[ 4 ]}

يمكن أيضًا تكييف خوارزمية Cseh وFleiner للعمل مع الاستحقاقات غير المنطقية في عدد محدود من الاستعلامات. ^{[ 5 ]}

إلى جانب عدد الاستعلامات المطلوبة، من المهم أيضًا تقليل عدد عمليات القطع المطلوبة، حتى لا يكون التقسيم مجزأً للغاية. تُنتج خوارزميات شيشيدو-زينغ تقسيمًا عادلًا بحد أقصى${\displaystyle 2\cdot 3^{n-2}}$تخفيضات، وتقسيم عادل للغاية مع أكثر من ${\displaystyle 4\cdot 3^{n-2}}$^{[ 4 ]}​

في أسوأ الأحوال، على الأقل${\displaystyle 2(n-1)}$قد تكون هناك حاجة إلى إجراء عمليات قطع. يقدم برامز وجونز وكلاملر ^{[ 6 ]} مثالاً لحالة n = 2. يجب تقسيم كعكة مكونة من أربعة مناطق متتالية بين أليس وجورج، وتكون تقييماتهما كما يلي:

لاحظ أن القيمة الإجمالية للكعكة هي 8 لكلا الشريكين. إذا${\displaystyle w_{A}\geq 0.75}$إذا كان جورج، فإن قيمة أليس لا تقل عن 6. ولإعطاء أليس نصيبها المستحق في قطعة متصلة، يجب أن نعطيها إما القطع الثلاث الموجودة في أقصى اليسار أو القطع الثلاث الموجودة في أقصى اليمين. في كلتا الحالتين، يحصل جورج على قطعة بقيمة 1 فقط، وهي أقل من نصيبه المستحق البالغ 2. ولتحقيق تقسيم عادل في هذه الحالة، يجب أن نعطي جورج نصيبه المستحق في منتصف الكعكة، حيث تكون قيمته كبيرة نسبيًا، ولكن حينها ستحصل أليس على قطعتين منفصلتين. ^{[ 7 ]}

يُبين سيغال-هاليفي ^{[ 8 ]} أنه إذا كانت الكعكة دائرية (أي أن طرفيها مُحددان)، فإنه من الممكن دائمًا تقسيمها بطريقة WPR متصلة لشخصين؛ وهذا ما يُستنتج من نظرية سترومكويست-وودال . وبتطبيق هذه النظرية بشكل متكرر لإيجاد تقسيمات دقيقة ، يُمكن الحصول على تقسيم WPR باستخدام عدد لا يتجاوز${\displaystyle 2n\cdot (\log _{2}n-1)+2}$يتم تطبيق القطع عندما يكون n قوة للعدد 2، ورقم مماثل عندما يكون n عامًا.

قام كل من كرو ونارايانان وسبيركل ^{[ 9 ]} بتحسين هذا الحد الأعلى إلى 3 ن -4 باستخدام البروتوكول التالي:

• اطلب من كل وكيل i أن يحدد قيمة x بحيث يكون V _i (0, x )=1/2.
• رتب العملاء حسب ترتيب علاماتهم تصاعدياً، مع كسر التعادلات بشكل تعسفي.
• أضف العناصر بالترتيب المذكور أعلاه إلى المجموعة P. توقف قبل أن يتجاوز الوزن الإجمالي للعناصر في المجموعة P النصف.
• يُطلق على أول عنصر لم تتم إضافته إلى المجموعة P اسم t ، وتُسمى مجموعة العناصر التي تلي t بـ Q. الآن:
  • جميع العوامل في قيمة P (0، x ) لا تقل عن 1/2، ووزنها الإجمالي لا يزيد عن 1/2؛
  • جميع العناصر في Q قيمة ( x,1 ) على الأقل 1/2، ووزنها الإجمالي على الأكثر 1/2؛
  • يقوم العامل t بتقييم كل من (0,x) و ( x,1 ) عند 1/2 بالضبط.
• إذا كانت كل من P و Q غير فارغة، يتم تقسيم العامل t بين P و Q بحيث يكون الوزن الإجمالي في كل مجموعة هو 1/2 بالضبط. يتم قطع الكعكة عند x ، وتستمر العملية بشكل متكرر. يؤدي هذا إلى علاقة التكرار التالية (حيث k هو عدد العوامل في P ، باستثناء نسخة العامل t ):${\displaystyle {\text{Cuts}}(n+1)\leq \max _{1\leq k\leq n-1}(1+{\text{Cuts}}(k+1)+{\text{Cuts}}(n-k+1))}$إضافة الشرط الأولي ${\displaystyle {\text{Cuts}}(2)=2}$ويؤدي إلى الرقم المزعوم ${\displaystyle {\text{Cuts}}(n)\leq 3n-4}$.
• الحالة الأصعب هي أن تكون المجموعة P فارغة (والحالة التي تكون فيها المجموعة Q فارغة مماثلة). هذا يعني أن وزن t لا يقل عن 1/2، وأن جميع الوكلاء يُقيّمون (0, x ) على الأكثر 1/2. في هذه الحالة، نجد قيمة y بحيث يُقيّم الوكيل t (0, y ) تمامًا w _t ، ونحاول تقسيم الوكلاء إلى P و Q كما في السابق. إذا كانت إحدى هاتين المجموعتين فارغة مرة أخرى، فإننا نعلم أن جميع الوكلاء يُقيّمون (0, y ) على الأقل w _t . لذلك، وفقًا لنظرية القيمة المتوسطة ، يجب أن تكون هناك قيمة z في ( x , y ) بحيث يُقيّم أحد الوكلاء، وهو ليس t ، (0, z ) بنفس قيمة t تمامًا . عندئذٍ، يمكننا تقسيم المجموعة عند z وتكرار العملية كما في الحالة الأولى.

لا يزال العدد الدقيق لعمليات القطع المطلوبة غير محدد. أبسط الحالات المفتوحة هي عندما يكون هناك 3 عملاء وتكون الأوزان 1/7، 2/7، 4/7. من غير المعروف ما إذا كان عدد عمليات القطع المطلوبة هو 4 (كما في الحد الأدنى) أو 5 (كما في الحد الأعلى).

قدم زينغ ^{[ 10 ]} خوارزمية لتقسيم الكعكة بشكل تقريبي خالٍ من الحسد مع استحقاقات مختلفة.

Dall'Aglio و MacCheroni ^{[ 11 ] : Thm.3} أثبت وجود تقسيم الكعكة النسبي مع استحقاقات مختلفة حتى عندما يتم وصف تفضيلات الوكلاء بعلاقات تفضيل غير جمعية، طالما أنها تفي ببعض البديهيات.