משתמש:עוזי ו./שולצה

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

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

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

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

אופן ההכרעה. לכל מסלול בגרף יש עוצמה, שהיא הערך המינימלי של קשתות במסלול. הגרף הממושקל מגדיר יחס בינארי על האפשרויות: a>b (כלומר "a עדיף על b") אם יש מסלול מ-a ל-b, שעוצמתו גדולה מזו של כל מסלול מ-b ל-a. מתברר שזהו יחס סדר חלקי. יתרה מזו, כמעט תמיד יש בו מנצח יחיד ומפסיד יחיד ("כמעט תמיד" - פרט למקרי תיקו). יחס הסדר הזה הוא היחס שמציעה שיטת שולצה. (כיצד מחשבים בפועל? ע"ע שיטת שולצה או אלגוריתם פלויד-וורשאל). חשוב להבחין שבשיטת שולצה יתכן שאפשרות a תנצח את b, גם כאשר רוב המצביעים מעדיף את b על פני a (אם יש מסלול בעל עוצמה גדולה יותר מ-a ל-b; למשל, אם היתרון של a על b הוא 55:45, ואילו היתרון של a על c הוא 70:30 וגם היתרון של c על b הוא 70:30).

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

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

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