שיטת שולצה

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

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

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

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

אופן ההצבעה

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

שקלול הקולות

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

כדי להדגים את השיטה, נתבונן במקרה שבו יש שלושה מועמדים, B ,A ו-C. נניח שבהצבעה משתתפים 7 מצביעים, ומתברר ש-A עדיף על B ברוב של 2:5, B עדיף על C ברוב של 3:4, ו-C עדיף על A ברוב של 1:6. שיטת שולצה "מנתקת" את המעגל בזוג המועמדים שעבורו מספר המעדיפים את אפשרות הרוב הוא הקטן ביותר: כיוון שהעדפת B על C היא הכי פחות חזקה (עם תומך אחד בלבד), נותרות רק ההעדפות . כלומר: בדוגמה זו 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. תאים בהם אין מועמד מועדף ללא צבע. מן המטריצה הזו בונים את , הקובע את הגרף הממושקל המכוון (ראו באיור):

טבלת העדפת הזוגות
d'[*,A] d'[*,B] d'[*,C] d'[*,D] d'[*,E]
d'[A,*] 0 26 30 0
d'[B,*] 25 0 33 0
d'[C,*] 0 29 0 24
d'[D,*] 0 0 28 0
d'[E,*] 23 27 0 31

בשלב האחרון מחשבים את משקלי הנתיבים המועדפים, שאותם מסמנים ב-. לדוגמה, , משום שהמסלול החזק ביותר מ-A ל-B עובר מ-A ל-D (משקל 30), מ-D ל-C (משקל 28), ומ-C ל-B (משקל 29). עוצמת המסלול הזה היא 28 (המינימום של 30,28,29).

הנתיבים המועדפים ביותר
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 (2010-07-11). "A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method". Social Choice and Welfare. Springer Nature. 36 (2): 267–303. doi:10.1007/s00355-010-0475-4. ISSN 0176-1714.
    קיימת גם גרסת טיוטה של המאמר, הזמינה ללא תשלום או התחברות.
  2. ^ רשימה חלקית של הגופים המשתמשים בשיטה זו
Logo hamichlol 3.png
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0