הקצאה (תורת המשחקים)

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

בעיית ההקצאה

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

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

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

פרדוקסים

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

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

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