שיטת שולצה

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

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

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

אופן ההצבעה

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

שקלול הקולות

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

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

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

ניסוח טכני

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

מסמנים ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d[v,w]} את מספר הבוחרים שהעדיפו את מועמד v על פני מועמד w. בשלב הבא, מסמנים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d'[v,w]= \begin{cases} d[v,w], &\mbox{if } d[v,w] > d[w,v] \\ 0, & \mbox{otherwise } \end{cases} }

כעת, בונים גרף מכוון ממושקל, שקודקודיו הם המועמדים ועל החץ ממועמד v למועמד w כתוב הערך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d'[v,w]} (צעד זה הכרחי, משום שבלעדיו השיטה אינה מקיימת את תבחין קונדורסה).

העוצמה של מסלול בגרף היא הערך הקטן ביותר המופיע על החצים במסלול. אם מסמנים ב-[p[A,B את העוצמה הגדולה ביותר על המסלולים מ-A ל-B, מתברר שכאשר מובטח ש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\textstyle p[A,B]\neq p[B.A]} לכל A, B, היחס

\ A>B\iff p[A,B]>p[B,A]

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

מימוש

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

דוגמה

שגיאה ביצירת תמונה ממוזערת:

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

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

5 הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle ACBED} (כלומר חמישה מצביעים דרגו את העדפתם למועמדים בסדר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A > C > B > E > D} )
5 הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle ADECB}
8 הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle BEDAC}
3 $CABED$
7 הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle CAEBD}
2 הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle CBADE}
7 הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle DCEBA}
8 הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle EBADC}

ראשית יש לחשב את העדפת הזוגות. למשל, כאשר משווים את הזוג הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle [A,B]} קיימים $5+5+3+7=20$ מצביעים אשר מעדיפים את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} ו- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 8+2+7+8=25} מצביעים אשר מעדיפים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} על $A$ . כלומר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d[A, B] = 15} ו- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

התאים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d[X, Y]} בעלי רקע ירוק בהיר מייצגים העדפה של X על Y, ואלו בעלי רקע אדום בהיר מייצגים העדפה של Y על פני X. תאים בהם אין מועמד מועדף ללא צבע. מן המטריצה הזו בונים את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d'[X, Y]} , הקובע את הגרף הממושקל המכוון (ראו באיור):

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

בשלב האחרון מחשבים את משקלי הנתיבים המועדפים, שאותם מסמנים ב- $p[X,Y]$ . לדוגמה, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p[A,B]=28} , משום שהמסלול החזק ביותר מ-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 מכיוון שמתקיים

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 28 = p[A,B] > p[B,A] = 25} .

אם ממשיכים בדרך זו, ומשווים את תוצאות כל הזוגות, מתקבל סדר ההעדפות הבא: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E > A > C > B > D} כלומר E מנצח, או במילים אחרות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p[E,*] \ge p[*,E]} נכון תמיד.

ראו גם

קישורים חיצוניים

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

אתר האינטרנט הרשמי של שיטת שולצה
מאמר שיצא בדצמבר 2018 ומאגד את כל הנושא עם הסברים ודוגמאות רבות The Schulze Method of Voting מאת מרקוס שולצה
מחשבון שולצה

הערות שוליים

^ ^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.
קיימת גם גרסת טיוטה של המאמר, הזמינה ללא תשלום או התחברות.
^ רשימה חלקית של הגופים המשתמשים בשיטה זו

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

37630448שיטת שולצה

[schulze2011-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] רשימה חלקית של הגופים המשתמשים בשיטה זו

[1]

[2]

בחירות
שיטות בחירה	בחירות ישירות • בחירות יחסיות • טופס כללי • בחירות אזוריות • בחירות ארציות • בחירות רובניות • הצבעה בשני סיבובים • הצבעת אישור • שיטת בורדה • שיטת ג'פרסון • שיטת הבונוס להשגת רוב קואליציוני • שיטת שולצה • שיטת הקול הנייד • חבר האלקטורים
הצבעה	אחוז הצבעה • הצבעה בדואר • הצבעה במעטפות כפולות • הצבעה חשאית • הצבעה מוקדמת • הצבעה ממוחשבת • הצבעה מרחוק • הצבעה באינטרנט • זכות בחירה • חובת הצבעה
אמצעי הצבעה	קלפי • מכונת הצבעה • פתק הצבעה • קלרוטריון
מונחים	כלכלת בחירות • דממת בחירות • רשימה • שריון • הסכם עודפים • עימות בחירות • בחירות מקדימות • חוג בית • בחירות ביניים • בחירות בזק
נוספים	פיקוח על בחירות • אחוז החסימה