משפט ארו

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

תוכן עניינים

[עריכה] טענת המשפט המדוייקת

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

[עריכה] הגדרות

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

חתך העדפות הוא פירוט סדר ההעדפות של כל פרט בחברה.

שיטה לשקלול העדפות (או חוקה) היא פונקציה שמתאימה לחתך העדפות של החברה סדר העדפות מסוים, שהוא סדר ההעדפות החברתי.

שיטה הוגנת (או חוקה הוגנת) היא שיטה לשקלול העדפות שעונה על שתי הדרישות הבאות:

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

דיקטטורה היא שיטה לשקלול העדפות שבה סדר ההעדפות החברתי זהה תמיד לסדר ההעדפות של פרט מסוים (דיקטטור).

[עריכה] נוסח המשפט

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

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

[עריכה] דוגמה

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

חתך ההעדפות של השלושה הוא כזה:

אבי בני גליה
פטריות תירס תירס
תירס זיתים פטריות
זיתים פטריות זיתים

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

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

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

לפי משפט ארו, השיטה ה"הוגנת" היחידה היא לפעול תוך התחשבות באחד החברים, תוך התעלמות מרצונותיהם של האחרים.

[עריכה] הוכחת המשפט

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

[עריכה] משפט העזר הראשון

המשפט: אם כל אחד מהפרטים ממקם את אפשרות \ 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^* הוא דיקטטור.

[עריכה] משמעויות נוספות

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

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

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

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

[עריכה] דוגמה

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

צבע בטיחות נוחות הנהיגה עלות התחזוקה מחיר
1 1 4 2 3
2 3 1 3 4
4 2 3 1 1
3 4 2 4 2

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

[עריכה] מגבלות המשפט

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

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

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

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