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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

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

שני שחקנים[עריכת קוד מקור | עריכה]

הפתרון לחלוקה נטולת-קנאה עבור שני שחקנים הוא שיטת 'חלק ובחר'. שני שחקנים מעוניינים לחלק ביניהם עוגה. נסמן את השחקנים ב-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. נניח ש P3 לקח את A (אחרת צריך להחליף להלן בין 3 ל4), השחקנים P2 ו-P4 יחלקו את B לארבעה חלקים על-פי הפרוצדורה של אוסטין. כל אחד מהשחקנים יבחר חלק בסדר הבא: P4, P1, P3 ו-P2.

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

חמישה שחקנים ויותר[עריכת קוד מקור | עריכה]

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

ב-2016 פרסמו האריס עזיז וסיימון מקנזי פרוצדורה עם מספר חלוקות החסום ב-.[1]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ How to Cut Cake Fairly and Finally Eat It Too, באתר quanta magazine, ‏6 באוקטובר 2016