חלוקה הוגנת

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

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

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

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

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

  • לשחקנים השונים יש העדפות שונות לחלקים מהרכוש.
  • ערך הרכוש עבור שחקן כלשהו שווה לסכום ערכי כל חלקי הרכוש.
  • רכוש יכול להיות מחולק לחלקים בעלי ערך שרירותי נמוך.

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

  • מסכימים על הקריטריונים הקובעים חלוקה הוגנת.
  • בוחרים פרוצדורה חוקית ופועלים לפיה.

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

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

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

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

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

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

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

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

סוגי חלוקה[עריכת קוד מקור | עריכה]

חלוקת ברלין על ידי ועידת פוטסדאם

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

ראו גם[עריכת קוד מקור | עריכה]

לקריאה נוספת[עריכת קוד מקור | עריכה]

  • Steven J. Brams and Alan D. Taylor (1996). Fair Division - From cake-cutting to dispute resolution Cambridge University Press. ISBN 0-521-55390-3
  • Jack Robertson and William Webb (1998). Cake-Cutting Algorithms: Be Fair If You Can, AK Peters Ltd, . ISBN 1-56881-076-8.

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