שיטת שולצה

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

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

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

אופן ההצבעה

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

שקלול הקולות

שקלול נאיבי של הקולות יקבע שמועמד 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 (ראו להלן), גדולה מן העוצמה הגדולה ביותר בכיוון ההפוך. ניתן להראות כי זהו יחס טרנזיטיבי, ולכן אפשר לקבוע שהמנצח הוא זה שמסלולי הזרימה שלו גברו על כל המועמדים האחרים. השיטה מאפשרת תוצאות תיקו, הבאות לידי ביטוי בקיומם של מסלולי זרימה מקסימליים שווי משקל.

ניסוח טכני

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

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

$$d'[v,w]={\begin{cases}d[v,w],&{\mbox{if }}d[v,w]>d[w,v]\\0,&{\mbox{otherwise }}\end{cases}}$$

כעת, בונים גרף מכוון ממושקל, שקודקודיו הם המועמדים ועל החץ ממועמד v למועמד w כתוב הערך $d'[v,w]$ (צעד זה הכרחי, משום שבלעדיו השיטה אינה מקיימת את תבחין קונדורסה).

העוצמה של מסלול בגרף היא הערך הקטן ביותר המופיע על החצים במסלול. אם מסמנים ב-[p[A,B את העוצמה הגדולה ביותר על המסלולים מ-A ל-B, מתברר שכאשר מובטח ש ${\textstyle p[A,B]\neq p[B,A]}$ לכל A, B, היחס

$$\ A>B\iff p[A,B]>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, ואלו בעלי רקע אדום בהיר מייצגים העדפה של Y על פני X. תאים בהם אין מועמד מועדף ללא צבע. מן המטריצה הזו בונים את $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]$. לדוגמה, $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 מכיוון שמתקיים

$28=p[A,B]>p[B,A]=25$.

אם ממשיכים בדרך זו, ומשווים את תוצאות כל הזוגות, מתקבל סדר ההעדפות הבא: $E>A>C>B>D$ כלומר E מנצח, או במילים אחרות $\ p[E,*]\geq p[*,E]$ נכון תמיד.

ראו גם

• משפט ארו
• תנאי קונדורסה
• הצבעת אישור
• שיטת הקול הנייד

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

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

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

הערות שוליים

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

39944378שיטת שולצה