הצגת המקור של הדף "הקצאה (תורת המשחקים)"

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

== בעיית ההקצאה ==

בעיית ההקצאה דורשת חלוקת משאבים במספר שלם, כאשר הזכאות להם נתונה במספרים ממשיים. נניח ש-k מפלגות מועמדות לבחירה, וכל מפלגה <math>i </math> זכתה בחלק השווה ל-<math>\ p_i</math> מן הקולות הכשרים; החלקים הם חיוביים וסכומם 1. בכנסת יש מספר שלם של מושבים (למשל n=120). המספרים <math>\ p_in</math>, המייצגים כמה מושבים "מגיעים" לכל מפלגה מלכתחילה, נקראים בהקשר זה '''מנות סטנדרטיות''' (standard quota). המנות הסטנדרטיות אינן שלמות בדרך כלל, ובעיית ההקצאה דורשת למצוא מספרים טבעיים <math>\ n_1,\dots,n_k</math> שסכומם n, כך שהחלוקה השלמה <math>\ (n_1,\dots,n_k)</math> קרובה, במובן זה או אחר, לחלוקה הצודקת <math>\ (p_1n,\dots,p_kn)</math> (שאינה אפשרית משום שאינה שלמה).

לדוגמה, בבחירות לוועד הבית שבו 5 מושבים השתתפו שתי מפלגות. אחת זכתה ב-72% מהקולות, והשנייה ב-18%. לכאורה, "מגיעים" למפלגה הגדולה 3.6 מושבים, ולקטנה 1.4. האם נכון יותר לחלק את המושבים ביחס 4:1 או אולי ביחס של 3:2? כאן השאלה היא כיצד לעגל את מספר המושבים של אחת משתי המפלגות. בהקצאה בין מפלגות רבות מתעוררות דילמות נוספות.

== קריטריונים לשיטות הקצאה ==

הצורך במעבר מנתוני הצבעה כלליים למספרים שלמים דווקא מחייב [[עיגול (אריתמטיקה)|עיגול]] מסוגים שונים. בהקשר זה נזכיר כי <math>\ \lfloor x\rfloor, \lceil x\rceil</math> הן [[פונקציית הערך השלם|פונקציית הרצפה]] ו[[פונקציית התקרה]], בהתאמה. תמיד מתקיים <math>\ \lfloor x \rfloor \leq x \leq \lceil x \rceil</math> ו-
<math>\ \lceil x \rceil - \lfloor x \rfloor \leq 1</math>, עם שוויון אלא אם x שלם. את [[הערך השברי]] מסמנים <math>\ (x) = x - \lfloor x \rfloor</math>.

'''תנאי המנות''' (quota condition) דורש שבחלוקה הסופית המרחק בין מספר המושבים של מפלגה למספר המושבים המגיע לה מלכתחילה לא יעלה על 1. כלומר, <math>\ \lfloor p_in \rfloor \leq n_i \leq \lceil p_i n \rceil</math>. בשיטה כזו מחלקים את המושבים לפי החלק השלם של המנה הבסיסית, ומקצים את המושבים הנותרים, בדרך כלשהי, אחד לכל היותר לכל מפלגה.

שיטה היא '''סימטרית''' אם היא אדישה לזהות המפלגות. שיטת הקצאה מקיימת את '''תנאי המודד''' (Divisor Criterion) עבור פונקציה ממשית d המוגדרת על המספרים הטבעיים, אם לכל שתי מפלגות i,j מתקיים <math>\ p_i/d(a_i-1) \geq p_j/d(a_j-1)</math> (כאשר p הוא יחס המצביעים למפלגה, ו-a מספר המושבים שלה). לדוגמה, שיטת ג'פרסון מקיימת את תנאי המודד עבור <math>\ d(a)=a+1</math>, ושיטת ובסטר מקיימת את תנאי המודד עבור <math>\ d(a)=a+\frac{1}{2}</math>. שיטה היא '''יציבה''' (stable) אם איחוד של שתי מפלגות אינו משנה את מספר המושבים המגיע להן יחד ביותר מ-1. כל שיטה המקיימת את תנאי המודד d כאשר <math>\ d(a+a')\leq d(a)+d(a')\leq d(a+a'+1)</math> היא יציבה.

שיטת הקצאה היא '''מונוטונית''' אם הוספת מושב לחלוקה אינה מורידה את מספר המושבים של אף מפלגה. שיטת המילטון, למרות שהיא יציבה, אינה מונוטונית. כל שיטה המקיימת את תנאי המודד היא מונוטונית. שיטה היא '''עקבית''' אם לכל שתי מפלגות i,j, הבחירה לאיזו מהן תעניק הגדלת בית הנבחרים מושב נוסף, תלויה רק בערכים <math>\ (p_i,a_i)</math> ו-<math>\ (p_j,a_j)</math>. <!--עמ' 11 ב[http://pure.iiasa.ac.at/id/eprint/525/1/RR-76-020.pdf] --> כל שיטה עקבית היא סימטרית.

שיטת הקצאה היא '''מאוזנת''' אם שתי מפלגות שיש להן אותו יחס מצביעים (p_i=p_j) אינן יכולות להתרחק ביותר ממושב אחד. כל שיטה המקיימת את תנאי המודד היא מאוזנת. גם שיטת המילטון מאוזנת. 

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

=== פרדוקסים ===

שיטת ההקצאה נגועה ב'''פרדוקס אלבמה''' אם תוספת של מושב בבית הנבחרים עשויה לגרום לאחת המפלגות לאבד מושב (היינו, השיטה אינה מונוטונית). (הפרדוקס נקרא כך משום שעל פי נתוני המפקד של 1882 ובחלוקה לפי שיטת המילטון, לו היה בית הנבחרים בן 299 מושבים, הוספת מושב אחד הייתה גורמת ל[[אלבמה|מדינת אלבמה]] אובדן מושב; אכן, במהלך המאה ה-19 גודלו של בית הנבחרים האמריקאי נקבע כך ששיטות הקצאה שונות תגענה לאותה תוצאה, כך שהיה על הנציגים לשקול בין השאר בתי נבחרים בני 299 ו-300 מושבים).

שיטת הקצאה נגועה ב'''פרדוקס האוכלוסייה''' אם בהשוואת יחסי ההצבעות <math>(p_i)</math> ו-<math>(p_i')</math>, שלהם מגיעים <math>(n_i)</math> ו-<math>(n_i')</math> מושבים בהתאמה, עלול לקרות ש-<math> n_i' < n_i</math> ו-<math> n_j' > n_j</math>, על אף ש-<math>p_i'/p_i < p_j'/p_j</math>. במילים אחרות, שינוי דמוגרפי שהיטיב עם מפלגה i יותר מאשר עם מפלגה j עשוי לגרום דווקא לראשונה לאבד מושב.

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

שלושת הפרדוקסים האלה עלולים להתרחש תחת שיטות המודד המתוארות בהמשך (בפרט תחת השיטות של ג'פרסון, אדמס וובסטר). לפי [[משפט בלינסקי-יאנג]]{{הערה|
Balinski, M; Young HP (1982). Fair Representation: Meeting the Ideal of One Man, One Vote. Yale Univ Pr. {{ISBN|0-300-02724-9}}.
}}
, אין שיטת הקצאה המקיימת את תנאי המנות וחופשית מפרדוקס האוכלוסייה.

=== הקצאה אופטימלית ===

בבעיית ההקצאה יש לבחור וקטור שלם <math>\ (n_1,\dots,n_k)</math> שיהיה קרוב לווקטור המנות הסטנדרטיות <math>\ (p_1n,\dots,p_kn)</math>. בחירה של [[מטריקה]] על מרחב הווקטורים האפשריים מובילה לדרישה הטבעית שווקטור ההקצאה יהיה הווקטור הקרוב ביותר לווקטור המנות הסטנדרטיות. לדוגמה, שיטת המילטון (ראו להלן) היא זו הממזערת את נורמת הסכומים (<math>\ \ell_1</math>), כלומר זו שעבורה <math>\ \sum |np_i - n_i|</math> הוא הקטן ביותר האפשרי (אכן, הקצאה היא אופטימלית ביחס לנורמת הסכומים אם ורק אם היא מקיימת את תנאי המנות ובנוסף מרוכזים כל ההפרשים <math>\ np_i-n_i</math> בקטע שאורכו אינו עולה על 1; ותנאי זה מתאר את שיטת המילטון).

== שיטות הקצאה מקובלות ==

שיטות הקצאה רבות נוצרו בעשורים הראשונים לקיומה של [[ארצות הברית של אמריקה]], כאשר עלה הצורך לחלק בין המדינות את המושבים ב[[הקונגרס האמריקאי|בית הנבחרים]] בהתאמה למספרי המתפקדים ב[[מפקד אוכלוסין|מפקד האוכלוסין]] שנערך מדי עשור. אודות מעלותיהן וחסרונותיהן של השיטות השונות ניטשו ויכוחים עזים. ה[[וטו|ווטו]] הנשיאותי הראשון בתולדות ארצות הברית  הוטל על ידי [[ג'ורג' וושינגטון]] ב-1792 כדי לפסול שיטת הקצאה שהוצעה ונתמכה על ידי שר האוצר [[אלכסנדר המילטון]], בעצתו של [[מזכיר המדינה]] [[תומאס ג'פרסון]] שתמך בשיטה אחרת (ראו להלן).
* '''שיטת [[אלכסנדר המילטון|המילטון]]'''  (="שיטת השאריות הגדולות ביותר") מחלקת בשלב ראשון <math>\ \lfloor p_i n \rfloor</math> למפלגה ה-i. בשלב זה נותרו <math>\ d = n - \sum_i \lfloor p_i n \rfloor</math> מושבים בלתי מאוישים. מעניקים את d המושבים שנותרו למפלגות שה'''שארית''' שלהן <math>\ (p_i n)</math> היא הגדולה ביותר.
שיטת המילטון מקיימת את תנאי המנות, ואילו כל שאר השיטות המוצגות כאן, הנקראות '''שיטות מודד''' (divisor methods) אינן מקיימות אותה. השיטה הייתה נהוגה בארצות הברית להקצאת מספר חברי בית הנבחרים למדינות בין השנית 1850 ל-1900
* '''[[שיטת ג'פרסון]]''' (= '''שיטת המחלקים הגדולים ביותר''' = '''שיטת ד'הונד'''") מחלקת את המושבים לפי <math>\ n_i = \lfloor p_i x \rfloor</math>, כאשר x הוא מספר, לאו דווקא שלם, שעבורו מתקבל <math>\ \sum n_i = n</math>. מגדילים באופן זמני, כביכול, את מספר המושבים בבית הנבחרים ל-x, כך שהחלקים השלמים של מספרי המושבים המגיעים לכל מפלגה יצטברו ל-n המבוקש. אפשר להראות שאפשר לבחור את x הזה בצורה <math>\ x = \frac{\lfloor n p_i\rfloor + t}{p_i}</math> כאשר <math>\ t = 1,2,\dots</math> הוא שלם, בדרך כלל קטן. למעשה יש לסדר את כל המספרים <math> \frac{\lfloor n p_i\rfloor+1}{p_i}, \frac{\lfloor n p_i\rfloor+2}{p_i}, \dots </math>, ולקחת את x כמספר ה-<math>\ d = n - \sum_i \lfloor p_i n \rfloor</math> בגודלו, כאשר d הוא מספר המושבים העודפים המופיע בשיטת המילטון. שיטה זו נוטה לחלק את המושבים העודפים באופן יחסי לגודל המפלגה, ובכך היא מעדיפה מפלגות גדולות. זו השיטה בה נעשה שימוש בחלוקת המושבים בכנסת לאחר הבחירות בישראל ([[חוק בדר-עופר]]). השיטה הייתה נהוגה בארצות הברית להקצאת מספר חברי בית הנבחרים למדינות בין השנים 1790 ל-1840. נטען נגדה שהיא נוטה להעדיף מדינות גדולות. שיטת ג'פרסון היא השיטה היחידה שהיא עקבית, מונוטונית ומאוזנת, ומעודדת קואליציות.

* '''שיטת [[ג'ון קווינסי אדמס|אדמס]]''' (="שיטת המחלקים הקטנים ביותר") היא תמונת מראה של שיטת ג'פרסון: השיטה מחלקת את המושבים לפי <math>\ n_i = \lceil p_i y \rceil</math>, כאשר y הוא מספר, לאו דווקא שלם, שעבורו מספרים אלה מסתכמים ל-n. בדומה לשיטה הקודמת, יש לסדר את כל המספרים <math> \frac{\lceil n p_i\rceil-1}{p_i}, \frac{\lceil n p_i\rceil-2}{p_i}, \dots </math>, ולקחת את y כמספר ה-<math>\ d' = \sum_i \lceil p_i n \rceil - n</math> בגודלו. שיטה זו נוטה להעניק להן את המושבים העודפים באופן יחסי הפוך לגודל המפלגה, ובכך היא מעדיפה מפלגות קטנות. אכן, זוהי השיטה היחידה שהיא עקבית, מונוטונית ומאוזנת, ומעודדת פיצולים.

* '''שיטת [[דניאל ובסטר|ובסטר]]''' (="שיטת השברים הגדולים ביותר" = שיטת ובסטר-וילקוקס") דומה לקודמותיה, ושונה רק באופן העיגול: היא מחלקת את המושבים לפי <math>\ n_i = \lfloor p_i z + \frac{1}{2}\rfloor</math>, כאשר z הוא מספר, לאו דווקא שלם, שעבורו המספרים האלה מסתכמים ל-n. פונקציית העיגול שנבחרה כאן היא סימטרית, שהרי <math>\ \lfloor x + \frac{1}{2} \rfloor = \lceil x - \frac{1}{2} \rceil</math> אלא אם x הוא שלם ועוד חצי. השיטה נחשבת למאוזנת באופן יחסי, ואינה מעדיפה באופן מיוחד מפלגות קטנות או גדולות. בשיטה זו נעשה שימוש בהקצאת מספר חברי בית הנבחרים של ארצות הברית למדינות השונות בהקצאה אחת, לאחר המפקד של 1840   ושוב לאחר מפקד 1900.
* '''שיטת היל-האנטינגטון''' (על שם [[ג'וזף היל]], שהיה סטטיסטיקאי ראשי של [[לשכת מפקד האוכלוסין של ארצות הברית]] והמתמטיקאי אדוארד האנטינגטון, שהיה נשיא האגודה המתמטית האמריקאית (MAA); נקראת גם "שיטת היחסים השווים" ו"שיטת היל") דומה לשיטת ובסטר, פרט לזה שהמספר <math>\ m+\delta</math> (כאשר m שלם ו-<math>\ 0 < \delta < 1</math>) מעוגל כלפי מטה אם <math>\ \delta < \sqrt{m(m+1)}-m \approx \frac{1}{2}-\frac{1}{8m}</math> (במקום אם <math>\ \delta < \frac{1}{2}</math> כמקובל). נוסחה זו מתקבלת מכך שמעגלים כלפי מטה אם <math>\ m+\delta</math> קטן מן ה[[ממוצע הרמוני|ממוצע ההרמוני]] (במקום ה[[ממוצע אריתמטי|אריתמטי]]) של שני שכניו השלמים. גם שיטה זו מאוזנת באופן יחסי, והיא מעדיפה במעט מפלגות קטנות ביחס לשיטת ובסטר. זו השיטה הנוכחית בה משתמשים להקצאת  מספר חברי בית הנבחרים של ארצות הברית למדינות השונות והיא נהוגה החל מ-1941.

== לקריאה נוספת ==
* The mathematics of voting and elections: a hands-on approach, J.K. Hodge and R.E.Klima, AMS "Mathematical World" series Vol 22, 2005, Chapter 10.
* Criteria for proportional representation, Balinski and Young, 1976, [http://pure.iiasa.ac.at/id/eprint/525/1/RR-76-020.pdf].

==הערות שוליים==
{{הערות שוליים}}

[[קטגוריה:תורת המשחקים]]
[[קטגוריה:בחירות]]