בתשובה לסמילי, 19/07/02 15:06
חלוקה הוגנת וחלוקה צודקת 79583
עוזי ו. • בתשובה לסמילי יום ו', 19/7/2002, 16:38
הנקודה היא, כמובן, שיש הרבה חלוקות הוגנות: כל חלוקה שבה הוא יקבל את ספרי הבישול והיא את ספרי המד"ב היא הוגנת, כי כל אחד מסכים שקיבל לפחות חצי מהספריה ("אני קיבלתי את הקיבריאדה והוא תקוע עם שלושים רות סירקיס").

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

אתה בעצם מציע להגדיר סוג חדש של חלוקה: "חלוקה צודקת", שבה החלק שלי, לפי הערכתי, שווה לחלק שלך, לפי הערכתך (ובמלים: (f_1(A_1)=f_2(A_2). חלוקה כזו עלולה להיות גם: הוא מקבל את המד"ב וחצי מספרי המתח, והיא את ספרי הבישול וחצי מספרי המתח (ושניהם לא יהיו מרוצים, אלא אם מדובר במשפט גירושין קשה במיוחד). אבל אז אפשר להחליף, ותתקבל חלוקה שהיא גם צודקת וגם הוגנת.

משפט. אם f_1,f_2 שתי מידות רציפות של עוגה X וקיימת פונקציה מדידה ורציפה [g:X->[0,1, אז קיימת חלוקה צודקת של X ביחס ל- f_1,f_2.
הוכחה. נגדיר פונקציה (([h(t)=f_1(g^{-1}([0,t]))-f_2(g^{-1}([t,1. קל לבדוק ש- h(0)=-1 ו- h(1)=1. לפי הרציפות של h קיים t כך ש- h(t)=0; החלוקה לפי t היא צודקת.

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

שעורי בית (הוכח או הפרך): תמיד קיימת חלוקה צודקת לשלושה שחקנים.
חלוקה הוגנת, חלוקה צודקת - ושופט 79602
עוזי ו. • בתשובה לעוזי ו. יום ו', 19/7/2002, 17:53
ההבדל המהותי בין חלוקה הוגנת (או נטולת קנאה, מה שבשני שחקנים הוא אותו הדבר) לבין חלוקה צודקת, הוא שחלוקה הוגנת תלויה עבור כל שחקן בהעדפות שלו, והוא לא צריך להניח שום דבר על האחרים.
אפשר להשיג חלוקה צודקת לשני חלקים בעזרת שופט, שמזיז את הסכין ושני הצדדים מדווחים לו באופן שוטף מה החלק שהוקצה עד-כה להערכתם; הוא יעצור את הסכין כשסכום ההערכות יהיה אחד.
בלי שופט בלתי תלוי ואמין, זה לא ילך (ההתייחסות היא לדוגמת הספריה, כמובן).

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

אני יכול להראות שתמיד קיימת חלוקה צודקת לשלושה חלקים, אבל לא ברור לי איך להפוך חלוקה כזו להוגנת (יתכן שכולם חושבים שקיבלו רק עשירית).
באופן מוזר, המקרה של חלוקה לארבעה חלקים נראה הרבה יותר מסובך. האם תמיד קיימת חלוקה צודקת לארבעה חלקים?
חלוקה צודקת 80149
עוזי ו. • בתשובה לעוזי ו. יום ג', 23/7/2002, 7:24
כדי שלא להשאיר את כל האינטרנט במתח: תמיד קיימת חלוקה צודקת.
ההוכחה היא כזו. בונים מערכת של סכינים n-1 התלויות כולן בראשונה, באופן כזה שהפרוסה ה-i שווה (לדעתו של השחקן ה-i) לפרוסה הראשונה (לדעת השחקן הראשון). באופן כזה נוצרת חלוקה צודקת של חלק מהעוגה ל- n-1 שחקנים. הפרוסה הנותרת נופלת בחלקו של השחקן האחרון.
בתחילת התהליך השחקן האחרון מקבל את כל העוגה, ובסופו (כאשר הסכין האחרונה מגיעה לסוף העוגה) הוא נשאר בלי כלום. לפי משפט ערך הביניים קיים זמן שבו ערך הפרוסה הנותרת לשחקן האחרון (לשיטתו) שווה לפרוסות שחילקנו, וזוהי חלוקה צודקת.
אמאלה 79616
סמילי • בתשובה לעוזי ו. יום ו', 19/7/2002, 18:21
אני רק טענתי שלא מדובר בחלוקה ללא קינאה.
ז"א הבעל ידע מראש שיקבל את כל רות סירקיס, (הוא מכיר את זוגתו לשעבר מספיק זמן לדעת שאין לה מה לעשות עם ספרי בישול, היא פשוט זוכרת הכל) והאישה ידעה שתקבל את סדרת המוסד במלואה (גם היא מכירה את בן זוגה, ויודעת שזה לא מעניין אותו), ולכן מראש כל ה"עימות" היה על ספר המתח אוסף ספרי בתיה גור (שהם קיבלו כמתנה). ולכן, ברור (?)שהבוחר/ת יקנא במחלק/ת.
אמאלה 79624
עוזי ו. • בתשובה לסמילי יום ו', 19/7/2002, 18:40
הגדרנו "קנאה" כמקרה שבו צד אחד חושב שהיה עדיף לו להתחלף עם השני, וזה לא יכול לקרות בחלוקה הוגנת של שני שחקנים (כי כל אחד מהם כבר קיבל לפחות חצי).
אני מסכים שלא כל חלוקה היא "צודקת" (חלוקה כזו שבה החלק שאני מקבל לשיטתי שווה לחלק שאתה מקבל לשיטתך). כפי שכתבתי לעיל, שיטת המחלק-בוחר *אינה* נותנת חלוקה צודקת, ואני מסכים בזה עם הביקורת שלך עליה.
עם זאת, אפשר לגייס שופט שימצא חלוקה צודקת (למשל 12 ספרי מתח לכל אחד).

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