הקצאה (תורת המשחקים) – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
שורה 31:
 
שיטות הקצאה רבות נוצרו בעשורים הראשונים של [[ארצות הברית של אמריקה]], כאשר עלה הצורך לחלק בין המדינות את המושבים ב[[הקונגרס האמריקאי|בית הנבחרים]] בהתאמה למספרים שעלו ב[[מפקד אוכלוסין|מפקד האוכלוסין]] שנערך מדי עשור.
* '''שיטת [[אלכסנדר המילטון|המילטון]]''' (="שיטת השאריות הגדולות ביותר") מחלקת בשלב ראשון <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) אינן מקיימות אותה.
* '''שיטת [[תומאס ג'פרסון|ג'פרסון]]''' (="שיטת המחלקים הגדולים ביותר" = "שיטת d'Hondt") מחלקת את המושבים לפי <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 הוא מספר המושבים העודפים המופיע בשיטת המילטון. שיטה זו נוטה לחלק את המושבים העודפים באופן יחסי לגודל המפלגה, ובכך היא מעדיפה מפלגות גדולות.
* '''שיטת [[ג'ון קווינסי אדמס|אדמס]]''' (="שיטת המחלקים הקטנים ביותר") היא תמונת מראה של שיטת ג'פרסון: השיטה מחלקת את המושבים לפי <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 הוא שלם ועוד חצי. השיטה נחשבת למאוזנת באופן יחסי, ואינה מעדיפה באופן מיוחד מפלגות קטנות או גדולות.
* '''שיטת היל''' (על שם [[ג'וזף היל]], שהיה סטטיסטיקאי ראשי של [[לשכת מפקד האוכלוסין של ארצות הברית]]; נקראת גם "שיטת היחסים השווים" ו"שיטת היל-האנטינגטון") דומה לשיטת ובסטר, פרט לזה שהמספר <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> קטן מן ה[[ממוצע הרמוני|ממוצע ההרמוני]] (במקום ה[[ממוצע אריתמטי|אריתמטי]]) של שני שכניו השלמים. גם שיטה זו מאוזנת באופן יחסי, והיא מעדיפה במעט מפלגות קטנות ביחס לשיטת ובסטר.
 
== לקריאה נוספת ==