בתשובה לטל כהן, 16/07/02 15:23
 |
|
 |
||
|
||||
 |
סוף סוף דיון מתמטי באייל... 1. הפתרון של טל, כמו גם ההכללה של סמילי ל- n שחקנים מספקים חלוקה הוגנת. אבל הדרישה היא למצוא חלוקה ללא-קנאה, וזה הרבה יותר קשה. פתרון העברת הסכין נגוע באותה בעיה בדיוק, ובנוסף הוא דורש רצף של החלטות, הרבה יותר גרוע מהסדרה האינסופית של המאמר. (תארו לעצמכם לחלק עוגה בשיטה זו באי-מייל: "הסעתי את הסכין 1.2 סנטימטרים. יש קונה? הסעתי בעוד סנטימטר. יש קונה? ....") 2. תרגום לעברית של הבעיה: נתונות n מידות f_1,...,f_n רציפות הדדית של עוגה X. צריך למצוא חלוקה X=A_1 U ... U A_n כך ש: * בעיית החלוקה ההוגנת: (f_i(A_i הוא לפחות 1 חלקי n. * בעיית החלוקה ללא-קנאה: (f_i(A_i הוא המקסימלי מבין (f_i(A_1),...,f_i(A_n. 3. ב"בעיה" של חלוקת ארץ-ישראל לשניים אין שום בעיה. אם המחלק הפלשתינאי יציע פרוסה דקה מאד סביב תל-אביב וחיפה, והיא תהיה עדיפה לישראל על-פני הפרוסה השניה, מה לא בסדר כאן? נקודת המוצא שבגללה נראה שמשהו בפתרון שגוי, היא שלישראל כביכול מגיע הרבה יותר מחצי. פויה. 4. דוגמא של חלוקה הוגת ולא נטולת-קנאה: שחקן א' מחשיב תפוז כשווה לשני תפוחים, וכן כשווה לשני-שליש אגוז. שחקן ב' מחשיב אגוז כשווה לשני תפוזים, וכן כשווה לשני-שליש תפוח. שחקן ג' מחשיב תפוח כשווה לשני אגוזים, וכן כשווה לשני-שליש תפוז. הם צריכים לחלק אגוז, תפוח ותפוז; ונקבע שא' יקבל תפוז, ב' אגוז וג' תפוח. כל אחד קיבל שליש מהשלל (לשיטתו), אבל תמיד יש מישהו שקיבל יותר. 5. שעורי בית: א) מצא שיטה לחלוקה הוגנת לשני חלקים, אם מוסכם מראש על הצדדים של-A מגיע 60% ול-B מגיע 40%. כל אחד מהם מעריך דברים שונים בעוגה, וצריך למצוא פתרון שבו כל צד סבור שקיבל לפחות מה שהוסכם ביניהם. ב) הכלל לחלוקה הוגנת של n שחקנים כאשר הפרופורציות מוסכמות מראש. ג) (אם כבר:) הראה שאם נוותר על דרישת הרציפות ההדדית של המידות, אז לא תמיד קיימת חלוקה הוגנת. |
 |
 |
 |
|
|
|
||
|
||||
|
3. הבעיה היא אם המחלק היה ישראל, היא הייתה מקבלת שטחים נוספים לחלק אותו היא קיבלה כבוחרת. אין לזה קשר לפוליטיקה, תחשוב על חלוקת סיפריה 1 בין בני זוג, היא אוהבת ספרי מד"ב הוא אוהב ספרי בישול 2, ובספריה יש סיפרי בישול, מד"ב ומתח (ששניהם מחבבים, אבל לא כמו האהבה). אם היא תחלק, חלק אחד יכלול את ספרי הבישול בלבד, והחלק השני גם את ספרי המד"ב, וגם את ספרי המתח. אם הוא יחלק, ספרי המתח יעברו לחלק של ספרי הבישול. כך שלמרות שחלוקה צודקת תהיה חלוקה של ספרי המתח בין שניהם, בצורת החלוקה הזו, ספרי המתח יעברו תמיד למחלק. --------------------------- 1 וכך האוף טופיק יהיה פחות בוטה. 2 GeG, ככה נותנים דוגמא שוביניסטית. |
|
|
|
|
|
|
||
|
||||
|
הנקודה היא, כמובן, שיש הרבה חלוקות הוגנות: כל חלוקה שבה הוא יקבל את ספרי הבישול והיא את ספרי המד"ב היא הוגנת, כי כל אחד מסכים שקיבל לפחות חצי מהספריה ("אני קיבלתי את הקיבריאדה והוא תקוע עם שלושים רות סירקיס"). ברור שהצד שקובע את החלוקה (ההוגנת) מרוויח, כי הוא יכול לקבל הרבה יותר מחצי (בעוד שהשני יקבל רק חצי או מעט יותר). אתה בעצם מציע להגדיר סוג חדש של חלוקה: "חלוקה צודקת", שבה החלק שלי, לפי הערכתי, שווה לחלק שלך, לפי הערכתך (ובמלים: (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 היא צודקת. השיטות לחלוקת העוגה בעזרת סכין נע מספקות חלוקה הוגנת, שהיא בדרך כלל לא צודקת. יתרה מזו, בשיטת הסכין הנע אף שחקן אינו מגלה את ההעדפות שלו לאחרים. בפועל, כשמחלקים עוגה בין שני שחקנים, השחקן הראשון יעצור את הסכין מיד אחרי שקיבל חצי עוגה, והשני עלול לקבל הרבה יותר (לשיטתו שלו); נראה לי שבמציאות הוא לא ימהר להודות בכך... אני לא רואה כרגע דרך לתרגם את הוכחת הקיום של חלוקה צודקת לתהליך אינטרקטיבי שימצא כזו (אפילו עבור שני שחקנים). שעורי בית (הוכח או הפרך): תמיד קיימת חלוקה צודקת לשלושה שחקנים. |
|
|
|
|
|
|
||
|
||||
|
ההבדל המהותי בין חלוקה הוגנת (או נטולת קנאה, מה שבשני שחקנים הוא אותו הדבר) לבין חלוקה צודקת, הוא שחלוקה הוגנת תלויה עבור כל שחקן בהעדפות שלו, והוא לא צריך להניח שום דבר על האחרים. אפשר להשיג חלוקה צודקת לשני חלקים בעזרת שופט, שמזיז את הסכין ושני הצדדים מדווחים לו באופן שוטף מה החלק שהוקצה עד-כה להערכתם; הוא יעצור את הסכין כשסכום ההערכות יהיה אחד. בלי שופט בלתי תלוי ואמין, זה לא ילך (ההתייחסות היא לדוגמת הספריה, כמובן). לחלוקה הצודקת, אגב, יש יתרון נוסף, והוא שהיא יחידה (ליתר דיוק, יש בדיוק שתי חלוקות צודקות: אחת, שאינה הוגנת, בה כל אחד מקבל פחות מחצי, והשניה, ההוגנת, בה כל אחד קיבל יותר מחצי). (הוכחה: הפונקציה h מן המלבן הקודם היא מונוטונית עולה). אני יכול להראות שתמיד קיימת חלוקה צודקת לשלושה חלקים, אבל לא ברור לי איך להפוך חלוקה כזו להוגנת (יתכן שכולם חושבים שקיבלו רק עשירית). באופן מוזר, המקרה של חלוקה לארבעה חלקים נראה הרבה יותר מסובך. האם תמיד קיימת חלוקה צודקת לארבעה חלקים? |
|
|
|
|
|
|
||
|
||||
|
כדי שלא להשאיר את כל האינטרנט במתח: תמיד קיימת חלוקה צודקת. ההוכחה היא כזו. בונים מערכת של סכינים n-1 התלויות כולן בראשונה, באופן כזה שהפרוסה ה-i שווה (לדעתו של השחקן ה-i) לפרוסה הראשונה (לדעת השחקן הראשון). באופן כזה נוצרת חלוקה צודקת של חלק מהעוגה ל- n-1 שחקנים. הפרוסה הנותרת נופלת בחלקו של השחקן האחרון. בתחילת התהליך השחקן האחרון מקבל את כל העוגה, ובסופו (כאשר הסכין האחרונה מגיעה לסוף העוגה) הוא נשאר בלי כלום. לפי משפט ערך הביניים קיים זמן שבו ערך הפרוסה הנותרת לשחקן האחרון (לשיטתו) שווה לפרוסות שחילקנו, וזוהי חלוקה צודקת. |
|
|
|
|
|
|
||
|
||||
|
אני רק טענתי שלא מדובר בחלוקה ללא קינאה. ז"א הבעל ידע מראש שיקבל את כל רות סירקיס, (הוא מכיר את זוגתו לשעבר מספיק זמן לדעת שאין לה מה לעשות עם ספרי בישול, היא פשוט זוכרת הכל) והאישה ידעה שתקבל את סדרת המוסד במלואה (גם היא מכירה את בן זוגה, ויודעת שזה לא מעניין אותו), ולכן מראש כל ה"עימות" היה על ספר המתח אוסף ספרי בתיה גור (שהם קיבלו כמתנה). ולכן, ברור (?)שהבוחר/ת יקנא במחלק/ת. |
|
|
|
|
|
|
||
|
||||
|
הגדרנו "קנאה" כמקרה שבו צד אחד חושב שהיה עדיף לו להתחלף עם השני, וזה לא יכול לקרות בחלוקה הוגנת של שני שחקנים (כי כל אחד מהם כבר קיבל לפחות חצי). אני מסכים שלא כל חלוקה היא "צודקת" (חלוקה כזו שבה החלק שאני מקבל לשיטתי שווה לחלק שאתה מקבל לשיטתך). כפי שכתבתי לעיל, שיטת המחלק-בוחר *אינה* נותנת חלוקה צודקת, ואני מסכים בזה עם הביקורת שלך עליה. עם זאת, אפשר לגייס שופט שימצא חלוקה צודקת (למשל 12 ספרי מתח לכל אחד). אני רוצה לתקן טעות במה שכתבתי קודם: חלוקה צודקת *אינה* יחידה (היא יחידה בהנחה שקבענו מראש את כיוון הסעת הסכין; אבל כל החלטה כזו תספק חלוקה צודקת (אחת ויחידה) אחרת). |
|
|
|
|
|
|
||
|
||||
|
תודה, חומד (אני אשם שאנשים לוקחים הערות אגב שלי ברצינות, ותגובות שלמות כהערות אגב?). | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |