שיטת שולצה

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

שיטת שולצה היא שיטת הצבעה שפותחה על ידי מרקוס שולצה (Markus Schulze)[1], לשקלול עמדות של מצביעים לגבי כמה מועמדים לכדי סדר עדיפויות משותף. שולצה החל לדון בשיטה בשנת 1997 בפורומים שונים והיא פורסמה בכתב עת מדעי בתחום הבחירה החברתית בשנת 2011[1]. השימוש בה החל ב-2003 בארגונים שונים הקשורים לתנועת התוכנה החופשית.

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

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

אופן ההצבעה[עריכת קוד מקור | עריכה]

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

שקלול הקולות[עריכת קוד מקור | עריכה]

שקלול נאיבי של הקולות יקבע שמועמד A עדיף על מועמד B אם יש יותר מצביעים המעדיפים את A על B. כאמור לעיל, אם השקלול הנאיבי אינו מביא למעגלים, שיטת שולצה תאמץ אותו כתוצאה הסופית.

כדי להדגים את השיטה, נתבונן במקרה שבו יש שלושה מועמדים, B ,A ו-C. נניח שבהצבעה משתתפים 50 מצביעים, ומתברר ש-A עדיף על B ברוב של 15:35, B עדיף על C ברוב של 20:30, ו-C עדיף על A ברוב של 10:40. שיטת שולצה "מנתקת" את המעגל בזוג המועמדים שעבורו מספר המעדיפים את אפשרות הרוב הוא הקטן ביותר: כיוון שהעדפת B על C היא הכי פחות חזקה (עם 10 תומכים בלבד), נותרות רק ההעדפות . כלומר: בדוגמה זו C מנצח, A מגיע למקום השני, ו-B במקום האחרון.

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

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

מסמנים ב- את מספר הבוחרים שהעדיפו את מועמד v על פני מועמד w. בשלב הבא, מסמנים

כעת, בונים גרף מכוון ממושקל, שקודקודיו הם המועמדים ועל החץ ממועמד v למועמד w כתוב הערך .

העוצמה של מסלול בגרף היא הערך הקטן ביותר המופיע על החצים במסלול. אם מסמנים ב-[p[A,B את העוצמה הגדולה ביותר על המסלולים מ-A ל-B, מתברר שהיחס

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

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

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

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

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

נניח 45 מצביעים מדרגים חמישה מועמדים:

  • 5 (כלומר חמישה מצביעים דרגו את העדפתם למועמדים בסדר )
  • 5
  • 8
  • 3
  • 7
  • 2
  • 7
  • 8

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

טבלת העדפת הזוגות
d[*,A] d[*,B] d[*,C] d[*,D] d[*,E]
d[A,*] 20 26 30 22
d[B,*] 25 16 33 18
d[C,*] 19 29 17 24
d[D,*] 15 12 28 14
d[E,*] 23 27 21 31

התאים בעלי רקע ירוק בהיר מייצגים העדפה של X על Y, ואלו בעלי רקע אדום בהיר מייצגים העדפה של Y על פני X. תאים בהם אין מועמד מועדף ללא צבע.

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

הנתיבים המועדפים ביותר
p[*,A] p[*,B] p[*,C] p[*,D] p[*,E]
p[A,*] 28 28 30 24
p[B,*] 25 28 33 24
p[C,*] 25 29 29 24
p[D,*] 25 28 28 24
p[E,*] 25 28 28 31

כעת ניתן למצוא את המועמדים המועדפים. למשל: כאשר משווים את A ל-B, מגלים ש-A עדיף על B מכיוון שמתקיים

.

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

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

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

ויקישיתוף מדיה וקבצים בנושא שיטת שולצה בוויקישיתוף

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

  1. ^ 1.0 1.1 Schulze, Markus (11 ביולי 2010). "A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method". Social Choice and Welfare (Springer Nature) 36 (2): 267–303. ISSN 0176-1714. doi:10.1007/s00355-010-0475-4. 
    קיימת גם גרסת טיוטה של המאמר, הזמינה ללא תשלום או התחברות.
  2. ^ רשימה חלקית של הגופים המשתמשים בשיטה זו