שיטת שולצה

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

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

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

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

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

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

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

שקלול נאיבי של הקולות יקבע שמועמד A עדיף על B אם יש יותר מצביעים המעדיפים את A על B. כאמור לעיל, אם השקלול הנאיבי אינו מביא למעגלים, שיטת שולצה תאמץ אותו כתוצאה הסופית. כדי להדגים את השיטה, נתבונן במקרה שבו יש שלושה מועמדים, B ,A ו-C, כשהצבעת הרוב מעדיפה את A על B, את B על C, ואת C על A. במקרה כזה, שיטת שולצה "מנתקת" את המעגל בזוג המועמדים שעבורו מספר המעדיפים את אפשרות הרוב הוא הקטן ביותר. לדוגמה, נניח שבהצבעה של -- נאמר -- 50 מצביעים, מתברר ש-A עדיף על B ברוב של 31:12, B עדיף על C ברוב של 27:14, ו-C עדיף על A ברוב של 33:10, אז העדפת B על C היא הפחות חזקה (עם 27 תומכים בלבד), ולכן נותרות רק ההעדפות C>A>B. כלומר, בדוגמה הזו, C מנצח, A היא האפשרות השנייה, ו-B הפחות מועדפת.

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

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

נסמן ב-d[v,w] את מספר הבוחרים שהעדיפו את מועמד V על פני מועמד W. נסמן d'[v,w] = d[v,w] אם d[v,w] > d[w,v], ו-d'[v,w] = 0 אחרת. נבנה גרף מכוון ממושקל, שקודקודיו הם המועמדים ועל החץ ממועמד v למועמד w כתוב הערך d'[v,w].

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

"\ A\geq B אם ורק אם \ p[A,B]\geq p[B,A]"

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

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

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

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

יצוג גראפי של טבלת העדפת הזוגות

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

  • 5 ACBED (כלומר חמישה מצביעים דרגו את העדפתם למועמדים בסדר A > C > B > E > D)
  • 5 ADECB
  • 8 BEDAC
  • 3 CABED
  • 7 CAEBD
  • 2 CBADE
  • 7 DCEBA
  • 8 EBADC

ראשית יש לחשב את העדפת הזוגות. למשל, כאשר משווים את הזוג [A,B] קיימים 5+5+3+7=20 מצביעים אשר מעדיפים את A על B ו- 8+2+7+8=25 מצביעים אשר מעדיפים B על A. כלומר d[A, B] = 20 ו- d[B, A] = 25. התיאור המלא של דירוג ההעדפות נתון בטבלה:

טבלת העדפת הזוגות
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


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

בשלב זה מזהים את הנתיב המועדף ביותר.

הנתיבים המועדפים ביותר
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 מכיוון ש 28 = p[A,B] > p[B,A] = 25. לכן אם ממשיכים בדרך זו להשוות את כל הזוגות מקבלים את סדר ההעדפות הבא: E > A > C > B > D כלומר E מנצח או במילים אחרות p[E,*] ≥ p[*,E] נכון תמיד.

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

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

  1. ^ ‏מרקוס שולצה, שיטה לבחירת מועמד יחיד באופן מונוטוני, סימטרי-הפיך ועקבי עם קריטריון קונדורסה, חלק 1‏‏, יוני 2009
  2. ^ Markus Schulze, A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method, Social Choice and Welfare, volume 36, number 2, page 267–303, 2011.
  3. ^ רשימה חלקית של הגופים המשתמשים בשיטה זו‏