משפט ארו

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

ניסוח מפורט

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

בלשון מתמטית, כאשר N מצביעים בוחרים בין m אפשרויות, המנגנון הוא פונקציה $\ S_{m}\times \dots \times S_{m}\rightarrow S_{m}$ , כאשר דירוג הוא תמורה של האפשרויות הנתונות.

חוקה (מנגנון שקלול) המקיימת את שלוש הדרישות הבאות תוגדר כחוקה הוגנת:

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

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

משפט ארו התקבל בהפתעה רבה:

משפט ארו: לא קיימת חוקה הוגנת לבחירה בין שלוש אפשרויות או יותר.

דוגמה

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

נסתכל על מספר שיטות לשקלול ההעדפות של החברים:

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

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

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

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

מלבד זה, שיטת האפשרות הראשונה אינה מכריעה בכל המקרים: אם כל חבר מעדיף תוספת אחרת, השיטה תותיר אותם בלי הכרעה.

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

שיטה זו איננה הוגנת כלפי בני וגלית שאינם יכולים להשפיע על הזמנת הפיצה.

הוכחת המשפט

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

משפט העזר הראשון

המשפט: אם כל אחד מהפרטים ממקם את אפשרות $\ b$ בראש או בתחתית סדר ההעדפות שלו, אפשרות $\ b$ תהיה בראש או בתחתית סדר ההעדפות החברתי.

הוכחה: נניח בשלילה כי הטענה איננה נכונה. אזי קיימות שתי אפשרויות $\ a,c$ שעבורן מתקיים בסדר ההעדפות החברתי: $\ a>b>c$ (כאשר משמעות הסימון $\ x>y$ היא: אפשרות $\ x$ רצויה יותר מאפשרות $\ y$ ).

נבנה חתך העדפות דומה לחתך הנתון, שבו אצל כל פרט, $\ c>a$ (ניתן להשיג זאת תוך שימוש רק בהחלפות בין שתי אפשרויות אלה, שלא משפיעות על הדירוג היחסי של כל אחת מהן לעומת $\ b$ , מאחר שאפשרות $\ b$ נמצאת בראש או בתחתית סדר ההעדפות). נשקלל את ההעדפות בחתך ההעדפות החדש באמצעות השיטה ההוגנת שלנו.

הדירוג היחסי של $\ a$ לעומת $\ b$ נשאר זהה אצל כל פרט. לפי דרישת האי-תלות בין אפשרויות לא רלוונטיות, עדיין $\ a>b$ .
הדירוג היחסי של $\ c$ לעומת $\ b$ נשאר זהה אצל כל פרט. לפי דרישת האי-תלות בין אפשרויות לא רלוונטיות, עדיין $\ b>c$ .
לפי דרישת הקונצנזוס, בשקלול ההעדפות בחתך החדש $\ c>a$ .

בכך הגענו לסתירה, ומכאן שהטענה נכונה.

משפט העזר השני

המשפט: קיים פרט $\ n^{*}=n(b)$ שבחתך מסוים יכול לשנות את הצבעתו כך שאפשרות $\ b$ תעלה מתחתית סדר ההעדפות החברתי לראש סדר ההעדפות החברתי.

הוכחה: נבנה חתך העדפות שבו כל פרט מציב את אפשרות $\ b$ בתחתית סדר ההעדפות. נמספר את הפרטים בקבוצה. כעת נבחן את המצבים שמתקבלים כאשר כל אחד מהפרטים מעביר את $\ b$ לראש סדר ההעדפות, לפי הסדר. לפני שהפרט הראשון יעשה זאת, לפי כלל הקונצנזוס, $\ b$ יהיה בתחתית סדר ההעדפות החברתי. לעומת זאת, לאחר שהאחרון יעשה זאת, $\ b$ יהיה בראש סדר ההעדפות החברתי. בכל שלב, $\ b$ יהיה בראש או בתחתית סדר ההעדפות החברתי. לכן קיים פרט $\ n(b)$ שכאשר הוא זה שיבצע את ההעברה, הוא ישנה את מקומו של $\ b$ .

בהמשך ההוכחה, נקרא לחתך ההעדפות שהיה לפני ההעברה של $\ n(b)$ בשם חתך I, ולחתך ההעדפות שנוצר בעקבות ההעברה - חתך II.

השלמת ההוכחה

ראשית, נראה שעבור שתי אפשרויות שונות $\ a,c$ שאף אחת מהן איננה $\ b$ , אם בסדר ההעדפות של $\ n(b)$ מתקיים $\ a>c$ - כך גם בסדר ההעדפות החברתי. לפי כלל האי-תלות, הדירוג היחסי של שתי האפשרויות בסדר ההעדפות החברתי תלוי אך ורק בדירוג היחסי שלהן אצל כל פרט. לכן, דירוג זה לא ישתנה גם אם נניח ש- $\ b$ נמצא בראש סדר ההעדפות של כל פרט לפני $\ n(b)$ , בתחתית סדר ההעדפות של כל פרט אחרי $\ n(b)$ , ואצלו עצמו נמצא בין $\ a$ ל- $\ c$ , כלומר: $\ a>b>c$ .

אם נבחן את הדירוג היחסי של $\ a,b$ , נראה שאצל כל פרט הוא זהה לדירוג היחסי ביניהם בחתך I, ולכן בסדר ההעדפות החברתי $\ a>b$ , כפי שקורה בחתך I.

אם נבחן את הדירוג היחסי של $\ b,c$ , נראה שאצל כל פרט הוא זהה לדירוג היחסי ביניהם בחתך II, ולכן בסדר ההעדפות החברתי $\ b>c$ , כפי שקורה בחתך II.

מכאן, $\ a>c$ .

כעת, נראה שעבור כל אפשרות $\ a$ שאיננה $\ b$ , הדירוג היחסי בינה לבין $\ b$ בסדר ההעדפות החברתי זהה לדירוג היחסי ביניהן בסדר ההעדפות של $\ n(b)$ . על פי משפט העזר השני, נמצא את $\ n(c)$ , עבור $\ c$ כלשהו שאיננו $\ a$ או $\ b$ . הוא קובע לבדו את הדירוג היחסי של כל שתי אפשרויות $\ \alpha ,\beta$ שאף אחת מהן איננה $\ c$ , לרבות האפשרויות $\ a,b$ . אך מכיוון שבהוכחת משפט העזר השני ראינו כיצד בחתך מסוים הדירוג היחסי בין שתי אפשרויות אלה משתנה כאשר רק $\ n(b)$ משנה את העדפותיו, נובע מכך: $\ n^{*}=n(b)=n(c)$ .

מכאן נובע, כי $\ n^{*}$ הוא דיקטטור.

הרחבת המשפט לבחירה חלקית של המועמדים

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

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

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

הוכחה עבור $\ K=1$ זהו משפט גיבארד-סתרסוויט, ואם K הוא מספר המועמדים זהו משפט ארו.

נוכיח תחילה את המשפט באינדוקציה על K כאשר הטווח של הפונקציה הוא קבוצת יחסי העדפות חזקים על קבוצות בנות K אפשרויות. בסיס האינדוקציה $\ K=1$ כבר נתון. נניח שהמשפט נכון עבור K ונוכיח אותו עבור $\ K+1$ . פונקציה f מחזירה דירוג על $\ K+1$ איברים נגדיר את הפונקציה g להיות הפונקציה שמחזירה את K האיברים הראשונים שנבחרו לפי f (ניתן לבחור אותם כי f מחזירה יחס חזק על המועמדים). הפונקציה g גם מקיימת את הדרישות מכיוון ש f מקיימת אותם ולכן g דיקטטורה .

אז f היא דיקטטורה ב-K האיברים הראשונים של שחקן i נניח בשלילה ש i לא דיקטטור באיבר האחרון כלומר יש יחס ההעדפות p שבו i מעדיף את A במקום ה $\ K+1$ אבל B נבחר במקום הזה. כיוון ש i דיקטטור של K האיברים הראשונים i מעדיף את A על B אחרת B נבחר במקום יותר טוב מ $\ K+1$ , ובנוסף A לא נבחר.

אם i מחליף בסדר ההעדפות שלו בין A לאיבר ה K שלו אז A נבחר במקום ה K, וB עדיין לא יכול להיבחר במקום טוב מ $\ K+1$ . מצב B לא נגרע ולכן ממונוטוניות אין איברים חדשים שמנצחים אותו, אבל A מנצח את B בדירוג הפונקציה לכן סתירה ו f דיקטטורה.

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

נניח בשלילה שיש יחס ההעדפות p בו i מעדיף את A על B ושניהם במקומות ה-K ראשונים אבל החברה אדישה בין A ל-B. מכיוון שלא בוחרים את כל המועמדים, כי אז זה משפט ארו והוכחנו, יש אפשרות אחרת C שלא נבחרה ולכן i ממקם אותה במקום גרוע מהמקום ה K, נסתכל על יחס ההעדפות חדש בו i מחליף את מיקום C ,B ושם B לא נבחר כי i דיקטטור חלש. אבל אם נחליף חזרה אז שוב $\ A=B$ כי חזרנו למצב הקודם בסתירה למונוטוניות כי מצב A לא נגרע אצל אף בוחר אבל מצבו נגרע בדירוג של הפונקציה. ולכן גם g דיקטטורה.

משמעויות נוספות

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

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

לפי משפט ארו, השקלול היחיד שמקיים את שתי הדרישות הוא שקלול שלוקח בחשבון קריטריון אחד בלבד.

פרשנות זו של המשפט שקולה לפרשנות שמובאת בתחילת הערך.