חלוקה נטולת-קנאה

חלוקה נטולת קנאה היא אפיון לחלוקה בה הסחורה ניתנת לחלוקה, כלומר אינה מאבדת את ערכה אם מחלקים אותה, וכן לחלוקה בה לשחקנים שונים יכולים להיות העדפות שונות לחלקים מהסחורה. חלוקה הוגנת היא נטולת-קנאה אם כל אחד מהשחקנים מאמין שאף אחד מהשחקנים האחרים לא קיבל חלק טוב יותר משלו. כלומר, שהוא ירצה את החלק שלו יותר מכל חלק של שחקן אחר. אפיון זה חזק יותר מחלוקה יחסית. חלוקה נטולת-קנאה מתאימה למשימת חלוקת מטלות, במצב זה החלוקה היא נטולת-קנאה אם כל אחד מהשחקנים מאמין שקיבל מטלה קטנה משל אחרים ואינו מוכן להתחלף במטלה שלו עם אף אחד אחר.

שני שחקנים

הפתרון לחלוקה נטולת-קנאה עבור שני שחקנים הוא שיטת 'חלק ובחר'. שני שחקנים מעוניינים לחלק ביניהם את הפרוסה האחרונה של עוגה. נסמן את השחקנים ב-P1 ו- P2. השיטה קצרה, פשוטה ופועלת באופן הבא:

• P1 מחלק את העוגה איך שהוא רוצה ו-P2 בוחר ראשון את החלק שהוא רוצה.

ל-P1 יש אינטרס לחלק את העוגה באופן שווה, שכן אחרת P2 ייבחר את הפרוסה הגדולה יותר ואז P1 ייצא מופסד. מהות החלוקה יכולה להיות לא רק מי מקבל את הפרוסה הגדולה ביותר אלא מי מקבל את החלק עם הדובדבן, כמו כן ייתכן כי אחד השחקנים מעוניין בחלק השוקולד של העוגה והשני בחלק הווניל, שהרי ייתכנו העדפות שונות לחלקים שונים בין השחקנים. עבור שני שחקנים חלוקה נטולת-קנאה זהה לחלוקה יחסית.

שלושה שחקנים

פרוצדורה דיסקרטית

חלוקת העוגה על-פי סלפרידג'-קונווי

פרוצדורה דיסקרטית היא פרוצדורה שמתירה שאלות דיסקרטיות בלבד לשחקנים. סלפרידג'-קונווי פרסמו פרוצדורה דיסקרטית המהווה פתרון לחלוקה נטולת-קנאה עבור שלושה שחקנים. הפרוצדורה פועלת באופן הבא: שלושה שחקנים מתחלקים בפרוסה האחרונה של עוגה. נסמן את שלושת השחקנים ב-P2, P1 ו-P3.

• P1 מחלק את העוגה לשלושה חלקים הנראים לו שווים. נסמן ב-A את החלק הגדול ביותר על פי P2.
• P2 מקטין את A כדי להשוות אותו לחלק הגדול יותר שקטן ממנו. כעת A הוא שני חלקים: A החדש, הקטן יותר שנסמנו A1 והפיסה ש-P2 חתך מ-A, נסמנה A2.
  • אם P2 חושב ששני החלקים הגדולים יותר זהים בגודלם אזי כל אחד מהשחקנים יבחרו חלק בסדר הבא: P2, P3 ולבסוף P1.
• P3 יבחר חלק מבין A1 ושני החלקים האחרים.
• P2 יבחר חלק, אך אם P3 לא בחר את A1, אז P2 יהיה חייב לבחור אותו.
• P1 יבחר את החלק האחרון, כעת נותר רק A2.

עד כה, כל העוגה חולקה בחלוקה נטולת-קנאה למעט החלק היחיד שנותר והוא A2.

• A1 נבחר על ידי P2 או P3, נסמן ב-PA את השחקן מביניהם שבחר את A1, ונסמן ב-PB את השחקן השני.
• PB יחתוך את A2 לשלושה חלקים זהים בגודלם.
• PA יבחר חלק מ-A2, אחריו P1 יבחר חלק מ-A2.
• PB יבחר את החלק האחרון שנותר מ-A2.
• נסמן ב-B את החלק שקיבל PB ונסמן ב-C את החלק שקיבל P1.

נעבור על כמה קיבל כל אחד מהשחקנים וככה נראה שהחלוקה אכן חלוקה נטולת-קנאה.

• PA קיבל את A1 ואת החתיכה הגדולה ביותר של A2. על פי ההערכות של PA מתקיים A1 ≥ B וגם A1 ≥ C. לכן, PA קיבל יותר מכל אחד אחר.
• PB קיבל את B ובנוסף חתיכה מ-A2. על-פי ההערכות של B מתקיים B ≥ A1 וגם B ≥ C. בנוסף, PB הוא זה שחילק את A2 ל-3 חלקים, לכן עבורו הם זהים בגודלם.
• P1 קיבל את C ובנוסף חתיכה מ-A2. על-פי ההערכות של C ≥ A1 וגם C = B.
  • P1 חושב ש-PB לא קיבל יותר ממנו משום ש-P1 בחר את חלק מ-A2 לפני PB.
  • P1 חושב ש-PA לא קיבל יותר ממנו משום שעל-פי ההערכות של P1 מתקיים C = A וגם A = A1 + A2. לכן, C גדול מ-A1 ועוד החלק של A2 ש-PA קיבל.

בסופה של הפרוצדורה, כל אחד מהשחקנים מאמין שהחלק שלו טוב יותר משל כל אחד אחר ואינו מוכן להתחלף עם אחד מהשחקנים.

פרוצדורת הסכין הזז

פרוצדורת הסכין הזז לחלוקת עוגה

בשנת 1980 סטרומקיסט פרסם את פרוצדורת הסכין הזז שהייתה הפתרון הראשון לחלוקה נטולת-קנאה של שלושה שחקנים. הפרוצדורה פועלת באופן הבא: השופט מתחיל עם הסכין מעל הצד השמאלי של העוגה ומזיז אותה לאורך העוגה, משמאל לימין. כל אחד משלושת השחקנים מחזיק סכין, במקביל לסכין של השופט ומימין לו, במקום שהוא חושב לחצות את העוגה מהסכין של שופט. כלומר, בזמן שהשופט מזיז את סכינו, שאר השחקנים יזיזו את סכינהם במקביל. בכל שלב, כל אחד מהשחקנים יכול לקרוא 'חתוך'. השחקן שקורא 'חתוך' ראשון מקבל את החלק מהעוגה שנמצא לשמאלו של השופט. לאחר ששחקן אחד יצא מהמשחק, נותרו השופט ושני שחקנים. החלוקה הבאה נעשית על ידי השחקן שסכינו קרוב יותר לשופט והוא מקבל את החלק שבין הסכין של השופט לסכינו. השחקן האחרון מקבל את החלק הימני ביותר. השחקנים מבטיחים שהם מקבלים את החלק הטוב ביותר כי הם קובעים מתי תעשה הפריסה. כאשר שחקן מזהה מצב של שוויון, עליו לקרוא לפריסה וכך יתקבלו שלושה חלקים זהים. אחרת, הסכין תמשיך לזוז ונקבל חלק גדול יותר שימנע חלוקה נטולת-קנאה.

ארבעה שחקנים

ברהמס, טיילור וזוויקר פרסמו פרוצדורה ב-1997 המבטיחה חלוקה נטולת-קנאה בין ארבעה שחקנים. הפרוצדורה מסתמכת על פרוצדורה שפרסם אוסטין ב-1982, המבטיחה חלוקה נטולת-קנאה לשני שחקנים. הפרוצדורה פועלת באופן הבא:

• השופט מזיז את הסכין משמאל לימין לאורך העוגה, נסמן ב-P1 את השחקן שקורא 'עצור' כשהוא חושב שהשופט הגיע לאמצע העוגה.
• אחרי שהשופט עצר, P1 יניח סכין נוסף בצד השמאלי הקיצוני של העוגה ויזיז את שני הסכינים משמאל לימין כך שהחלק שנמצא בין שני הסכינים הוא בגודל 1/2 על-פי P1.
• על-פי P2 החלק שבין הסכינים גדל מפחות מ-1/2 ליותר מ-1/2, ברגע שהוא חושב שהחלק בגודל בדיוק 1/2 הוא קורא 'חתוך'.

זו היא הפרוצדורה מאת אוסטין. P1 ו-P2 יבצעו את אותה פרוצדורה, בשנית, על כל אחד מחצאי העוגה ונקבל 4 חלקים שכל אחד מהשחקנים מאמין שהוא בגודל 1/4.

• P3 יחתוך פיסה מהחלק שנראה לו הגדול ביותר, נסמנו A ואת הפיסה נסמן B, כדי ליצור שני חלקים זהים.
• כל אחד מהשחקנים יבחר חלק, לא כולל B, בסדר הבא: P2, P3, P4 ו-P1. אם P4 לא לקח את A, אזי P3 חייב לבחור אותו.

P1 ו-P2 אינם מקנאים באף אחד, כי הם קיבלו חלקים מקוריים והנחנו כי החלקים המקוריים זהים.

• נותר לחלק את B. השחקנים P1 ו-P3 יחלקו את B לארבעה חלקים על-פי הפרוצדורה של אוסטין. כל אחד מהשחקנים יבחר חלק בסדר הבא: P4, P1, P3 ו-P2.

P3 לא מקנא באף אחד משום שהוא בוחר ראשון. P1 לא מקנא ב-P4 וב-P2 משום שהוא בוחר לפניהם, וגם לא ב-P3 משום שהיה לו יתרון על פניו בחלוקה הקודמת, שכן הוא קיבל חלק מקורי. לבסוף, P2 ו-P4 לא מקנאים באף אחד אחר כי ההנחה היא שכל החלקים המתקבלים מ-B זהים. לכן החלוקה היא נטולת-קנאה.

חמישה שחקנים ויותר

ב-1995 ברהמס וטיילור פרסמו פרוצדורה דיסקרטית עם מספר חלוקות לא חסום לחלוקה נטולת-קנאה.

ב-2016 פרסמו האריס עזיז וסיימון מקנזי פרוצדורה עם מספר חלוקות החסום ב-$n^{n^{n^{n^{n^{n}}}}}$.