חלוקה הוגנת
חלוקה הוגנת היא בעיה בתורת המשחקים, הדנה בחלוקת משאב ו/או נכסים מוחשיים בעלי ערך כלכלי, בין קבוצת אנשים בעלי זכויות, באופן ששביעות הרצון של כלל חברי הקבוצה יהיה מרבי, ולא תמצא חלוקה אחרת שתגדיל את שביעות הרצון של לפחות אחד מחברי הקבוצה ולא תפגע בשביעות הרצון של אף אחד משאר חברי הקבוצה. על המשאב להיות ניתן לחלוקה, כלומר שאינו מאבד את ערכו עם החלוקה. חלוקה זו מוגדרת כחלוקה יציבה.
הבעיה קלה יותר כאשר לשחקנים יש העדפות שונות לכל אחד מחלקי המשאב. לדוגמה, בבעיית חלוקת העוגה, אם שחקן A מעדיף את החלק עם קרם השוקולד בעוגה, ושחקן B מעדיף את החלק עם הקרם וונילה בעוגה. בתנאים כאלו, 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
קישורים חיצוניים
עריכה
- ויל היוולי, אמנות חלוקת העוגה, פורסם במקור בגליליאו, 1995
- Short essay about the cake-cutting problem by S. Abbas Raza of 3 Quarks Daily.
- Fair Division from the Discrete Mathematics Project at the University of Colorado at Boulder.
- The Fair Division Calculator (Java applet) at Harvey Mudd College
- Fair Division: Method of Lone Divider
- Fair Division: Method of Markers
- Fair Division: Method of Sealed Bids
- Vincent P. Crawford (1987). "fair division," The New Palgrave: A Dictionary of Economics, v. 2, pp. 274-75.
- Hal Varian (1987). "fairness," The New Palgrave: A Dictionary of Economics, v. 2, pp. 275-76.
- Bryan Skyrms (1996). The Evolution of the Social Contract Cambridge University Press. ISBN 9780521555838