משפט ארו – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
אין תקציר עריכה |
||
שורה 1:
'''משפט האי-אפשרות של ארו''' (או '''[[פרדוקס]] ארו''') הוא [[משפט (מתמטיקה)|משפט מתמטי]] בתחום הבחירה החברתית (שמהווה חלק מ[[תורת המשחקים]]) שהוכח על ידי הכלכלן [[קנת' ג'יי. ארו]] במסגרת עבודת ה[[דוקטורט]] שלו. לפי המשפט, לא קיימת שיטה הוגנת לשקלול בחירתם של מספר מצביעים בין כמה אפשרויות, שאיננה [[דיקטטורה|שלטון יחיד]].
==ניסוח מפורט==
המערכת שבה דן משפט ארו כוללת [[פרלמנט]] בן מספר מצביעים, המבקשים לבחור אחת מבין כמה אפשרויות. כל מצביע מדרג את האפשרויות מן הטובה ביותר לגרועה ביותר. '''חוקה''' היא מנגנון המשקלל את הדירוגים הפרטיים, בדרך כלשהי, ומחזיר דירוג משלו. דירוג זה הוא הדירוג הקיבוצי, על-פי החוקה.
בלשון מתמטית, כאשר N מצביעים בוחרים בין m אפשרויות, המנגנון הוא [[פונקציה]] <math>\ S_m\times \dots\times S_m \rightarrow S_m</math>, כאשר דירוג הוא [[תמורה (מתמטיקה)|תמורה]] של האפשרויות הנתונות.
חוקה (מנגון שקלול) המקיימת את שתי הדרישות הבאות תוגדר כ'''חוקה הוגנת''':
* החוקה תכבד [[קונצנזוס]]: אם כל הפרטים מעדיפים את אפשרות A על-פני אפשרות B, מן הדין שגם הדירוג הקיבוצי יעדיף את A על B (לדרישה זו קוראים "[[יעילות פארטו]]").
* החוקה צריכה למנוע [[מניפולציות]]: מקומן היחסי של האפשרויות A ו-B בדירוג הקיבוצי תלוי רק במקומן היחסי בדירוגים הפרטיים (ולא במקומן בהשוואה לאפשרויות אחרות).
אין דרישה מהחוקה שתעניק לכל המצביעים מעמד שווה, כדי שתקרא '''הוגנת'''; קרי, מותר לחוקה לאפשר התחשבות בגורמים כמו [[ותק]], או מבנה מדורג של ועדות.
מבחינת שני הקריטריונים נובע כי חוקה שמכתירה '''דיקטטור''' – אדם מסוים שהדירוג האישי שלו נקבע להיות הדירוג הקיבוצי – היא '''חוקה הוגנת'''. מעשית, אפשר לשער שחוקה כזו לא תחשב למוצלחת במיוחד, וטבעי להאמין שקיימות דרכים אחרות לשקלול הצבעות כך שיעמדו בקריטריונים הנ"ל ל'''חוקה הוגנת'''. משום כך, התקבל משפט ארו בהפתעה רבה:
:'''משפט ארו''': לא קיימת חוקה הוגנת לבחירה בין שלוש אפשרויות או יותר, שאיננה בחירה בדיקטטור.
===דוגמה===
נניח כי שלושה חברים: אבי, בני וגלית מעוניינים להזמין [[פיצה]]. באפשרותם לבחור רק אחת מבין שלוש תוספות: [[פטריות]], [[זית|זיתים]] או [[תירס]]. כמו כן, יכול להיות שחלק מהתוספות אזלו, ושלא ניתן להזמין אותם. שלושת החברים מעוניינים לגבש סדר העדפות מסוים, שיבטא את העדפותיהם.
חתך ההעדפות של השלושה הוא כזה:
<div style="text-align: center;">
{| class="wikitable" border="1"
! אבי
! בני
! גליה
|-
| פטריות
| תירס
| תירס
|-
| תירס
| זיתים
| פטריות
|-
| זיתים
| פטריות
| זיתים
|}
</div>
כל עמודה בטבלה משקפת את סדר ההעדפות האישי של אחד החברים.
נסתכל על מספר שיטות לשקלול ההעדפות של החברים:
* '''[[סדר לקסיקוגרפי|סידור אלפביתי]]''': ניתן לקבוע את סדר ההעדפות של הקבוצה לפי סדר הופעת שמות התוספות במילון, כלומר:
<div style="text-align: center;">
{| class="wikitable" border="1"
! שקלול
|-
| זיתים
|-
| פטריות
|-
| תירס
|}
</div>
:שיטה זו אינה מוצלחת, כי היא מתעלמת מרצונותיהם של החברים. בפרט, היא לא עונה על ההגדרה של "שיטה הוגנת", כי היא לא משקפת את הקונצנזוס שבין החברים, לפיו תירס עדיף על זיתים.
* '''שיטת הבחירה היחידה''': ניתן לקבוע את סדר ההעדפות של הקבוצה לפי האפשרות הרצויה ביותר בעיני כל פרט. כך, מאחר ששני חברים בחרו בתירס כאפשרות המועדפת עליהם, ואחד בחר בפטריות, סדר ההעדפות המשוקלל יהיה:
<div style="text-align: center;">
{| class="wikitable" border="1"
! שקלול
|-
| תירס
|-
| פטריות
|-
| זיתים
|}
</div>
:שיטה זו אמנם נתפסת לרוב כהוגנת במשמעות הטבעית של המילה, אך היא לא עונה על ההגדרה של "שיטה הוגנת", כיוון שאנו מתחשבים רק באפשרות המועדפת '''מבין השלוש''' על כל פרט, ולא בדירוג היחסי של כל שתיים, בניגוד לדרישת האי-תלות של אפשרויות לא רלוונטיות.
* '''דיקטטורה (של אבי)''': אבי, שבידיו ה[[טלפון]], יכול לבצע את ההזמנה לפי רצונותיו, בלי להתחשב בחבריו כלל:
<div style="text-align: center;">
{| class="wikitable" border="1"
! שקלול
|-
| פטריות
|-
| תירס
|-
| זיתים
|}
</div>
:שיטה זו נתפסת לרוב כשיטה לא הוגנת במשמעות הטבעית של המילה, אך היא עונה על ההגדרה של "שיטה הוגנת".
לפי משפט ארו, השיטה ה"הוגנת" '''היחידה''' היא לפעול תוך התחשבות באחד החברים, תוך התעלמות מרצונותיהם של האחרים.
==הוכחת המשפט==
נניח כי אנו משתמשים בשיטה הוגנת לשקלול העדפות, ונוכיח כי קיים בה דיקטטור. את המשפט נוכיח באמצעות שני [[למה (מתמטיקה)|משפטי עזר]].
===משפט העזר הראשון===
'''המשפט:''' אם כל אחד מהפרטים ממקם את אפשרות <math>\ b</math> בראש או בתחתית סדר ההעדפות שלו, אפשרות <math>\ b</math> תהיה בראש או בתחתית סדר ההעדפות החברתי.
'''הוכחה:''' נניח בשלילה כי הטענה איננה נכונה. אזי קיימות שתי אפשרויות <math>\ a,c</math> שעבורן מתקיים בסדר ההעדפות החברתי: <math>\ a>b>c</math> (כאשר משמעות הסימון <math>\ x>y</math> היא: אפשרות <math>\ x</math> רצויה יותר מאפשרות <math>\ y</math>).
נבנה חתך העדפות דומה לחתך הנתון, שבו אצל כל פרט, <math>\ c>a</math> (ניתן להשיג זאת תוך שימוש רק בהחלפות בין שתי אפשרויות אלה, שלא משפיעות על הדירוג היחסי של כל אחת מהן לעומת <math>\ b</math>, מאחר שאפשרות <math>\ b</math> נמצאת בראש או בתחתית סדר ההעדפות). נשקלל את ההעדפות בחתך ההעדפות החדש באמצעות השיטה ההוגנת שלנו.
* הדירוג היחסי של <math>\ a</math> לעומת <math>\ b</math> נשאר זהה אצל כל פרט. לפי דרישת האי-תלות בין אפשרויות לא רלוונטיות, עדיין <math>\ a>b</math>.
* הדירוג היחסי של <math>\ c</math> לעומת <math>\ b</math> נשאר זהה אצל כל פרט. לפי דרישת האי-תלות בין אפשרויות לא רלוונטיות, עדיין <math>\ b>c</math>.
* לפי דרישת הקונצנזוס, בשקלול ההעדפות בחתך החדש <math>\ c>a</math>.
בכך הגענו לסתירה, ומכאן שהטענה נכונה.
===משפט העזר השני===
'''המשפט:''' קיים פרט <math>\ n^*=n(b)</math> שבחתך מסוים יכול לשנות את הצבעתו כך שאפשרות <math>\ b</math> תעלה מתחתית סדר ההעדפות החברתי לראש סדר ההעדפות החברתי.
'''הוכחה:''' נבנה חתך העדפות שבו כל פרט מציב את אפשרות <math>\ b</math> בתחתית סדר ההעדפות. [[מספור|נמספר]] את הפרטים בקבוצה. כעת נבחן את המצבים שמתקבלים כאשר כל אחד מהפרטים מעביר את <math>\ b</math> לראש סדר ההעדפות, לפי הסדר. לפני שהפרט הראשון יעשה זאת, לפי כלל הקונצנזוס, <math>\ b</math> יהיה בתחתית סדר ההעדפות החברתי. לעומת זאת, לאחר שהאחרון יעשה זאת, <math>\ b</math> יהיה בראש סדר ההעדפות החברתי. בכל שלב, <math>\ b</math> יהיה בראש או בתחתית סדר ההעדפות החברתי. לכן קיים פרט <math>\ n(b)</math> שכאשר הוא זה שיבצע את ההעברה, הוא ישנה את מקומו של <math>\ b</math>.
בהמשך ההוכחה, נקרא לחתך ההעדפות שהיה לפני ההעברה של <math>\ n(b)</math> בשם '''חתך I''', ולחתך ההעדפות שנוצר בעקבות ההעברה - '''חתך II'''.
===סיום ההוכחה===
ראשית, נראה שעבור שתי אפשרויות שונות <math>\ a,c</math> שאף אחת מהן איננה <math>\ b</math>, אם בסדר ההעדפות של <math>\ n(b)</math> מתקיים <math>\ a>c</math> - כך גם בסדר ההעדפות החברתי. לפי כלל האי-תלות, הדירוג היחסי של שתי האפשרויות בסדר ההעדפות החברתי תלוי אך ורק בדירוג היחסי שלהן אצל כל פרט. לכן, דירוג זה לא ישתנה גם אם נניח ש-<math>\ b</math> נמצא בראש סדר ההעדפות של כל פרט לפני <math>\ n(b)</math>, בתחתית סדר ההעדפות של כל פרט אחרי <math>\ n(b)</math>, ואצלו עצמו נמצא בין <math>\ a</math> ל-<math>\ c</math>, כלומר: <math>\ a>b>c</math>.
אם נבחן את הדירוג היחסי של <math>\ a,b</math>, נראה שאצל כל פרט הוא זהה לדירוג היחסי ביניהם בחתך I, ולכן בסדר ההעדפות החברתי <math>\ a>b</math>, כפי שקורה בחתך I.
אם נבחן את הדירוג היחסי של <math>\ b,c</math>, נראה שאצל כל פרט הוא זהה לדירוג היחסי ביניהם בחתך II, ולכן בסדר ההעדפות החברתי <math>\ b>c</math>, כפי שקורה בחתך II.
מכאן, <math>\ a>c</math>.
כעת, נראה שעבור כל אפשרות <math>\ a</math> שאיננה <math>\ b</math>, הדירוג היחסי בינה לבין <math>\ b</math> בסדר ההעדפות החברתי זהה לדירוג היחסי ביניהן בסדר ההעדפות של <math>\ n(b)</math>. על פי משפט העזר השני, נמצא את <math>\ n(c)</math>, עבור <math>\ c</math> כלשהו שאיננו <math>\ a</math> או <math>\ b</math>. הוא קובע לבדו את הדירוג היחסי של כל שתי אפשרויות <math>\ \alpha,\beta</math> שאף אחת מהן איננה <math>\ c</math>, לרבות האפשרויות <math>\ a,b</math>. אך מכיוון שבהוכחת משפט העזר השני ראינו כיצד בחתך מסוים הדירוג היחסי בין שתי אפשרויות אלה משתנה כאשר רק <math>\ n(b)</math> משנה את העדפותיו, נובע מכך: <math>\ n^*=n(b)=n(c)</math>.
מכאן נובע, כי <math>\ n^*</math> הוא דיקטטור.
==הרחבת המשפט לבחירה חלקית של המועמדים==
נרחיב את המשפט לפונקציות שבוחרות רק K מהמועמדים כלומר מחזירות דירוג על קבוצה בגודל קבוע מהמועמדים.
שורה 33 ⟵ 161:
אבל אם נחליף חזרה אז שוב <math>\ A = B</math> כי חזרנו למצב הקודם בסתירה למונוטוניות כי מצב A לא נגרע אצל אף בוחר
אבל מצבו נגרע בדירוג של הפונקציה. ולכן גם g דיקטטורה.
==משמעויות נוספות==
בנוסף להשלכותיו של משפט ארו בתחום קבלת ההחלטות בקבוצה, למשפט השלכות גם בתחום קבלת ההחלטות על ידי אדם יחיד, כאשר מתייחסים אל [[קריטריון|קריטריונים]] במקום לפרטים בקבוצה. פרשנות זו של המשפט, עוסקת במקרה שבו אדם רוצה לקבוע סדר העדפות כללי בין מספר אפשרויות, על ידי שקלול סדרי העדפות בין אותן אפשרויות על פי קריטריונים שונים. טבעי שהאדם ירצה שהשקלול יענה על שתי הדרישות הבאות:
* '''כלל העליונות המוחלטת''': אם אפשרות א' עדיפה על אפשרות ב' לפי כל קריטריון, אזי אפשרות א' עדיפה על אפשרות ב' גם באופן כללי.
* '''אי-תלות בין אפשרויות לא רלוונטיות''': הדירוג היחסי של אפשרות א' לעומת אפשרות ב' בסדר ההעדפות הכללי יהיה תלוי אך ורק בדירוג היחסי של אפשרות א' לעומת אפשרות ב' לפי כל קריטריון (ולא בדירוגן ביחס לאפשרויות אחרות, למשל).
לפי משפט ארו, השקלול היחיד שמקיים את שתי הדרישות הוא שקלול שלוקח בחשבון קריטריון אחד בלבד.
פרשנות זו של המשפט שקולה לפרשנות שמובאת בתחילת הערך.
===דוגמה===
אם משה רוצה לקנות מכונית, והוא מתלבט בין מכוניות שמספריהן בין 1 ל-4, חתך ההעדפות שלו יכול להיראות כך:
<div style="text-align: center;">
{| class="wikitable" border="1"
! width="20%" | צבע
! width="20%" | בטיחות
! width="20%" | נוחות הנהיגה
! width="20%" | עלות התחזוקה
! width="20%" | מחיר
|-
| 1
| 1
| 4
| 2
| 3
|-
| 2
| 3
| 1
| 3
| 4
|-
| 4
| 2
| 3
| 1
| 1
|-
| 3
| 4
| 2
| 4
| 2
|}
</div>
בטבלה זו, כל עמודה מייצגת את סדר ההעדפות על פי קריטריון מסוים. טבלה זו בנויה באותו אופן כמו חתך ההעדפות של שלושת החברים לגבי התוספת לפיצה, לעיל.
==מגבלות המשפט==
על אף ניסוחו הקיצוני של המשפט, יש לשים לב למגבלותיו. המגבלה העיקרית של המשפט היא שההגדרה הפורמלית ל"הוגנות" שבה משתמש המשפט, לא מתלכדת עם מה שמקובל להגדיר כ"הוגן" בשפה הטבעית. הסיבה העיקרית לכך היא ההגדרה של "שיטה לשקלול העדפות". על פי הגדרה זו, שיטה משקללת את סדר ההעדפות החברתי אך ורק על סמך '''סדר''' ההעדפות של כל פרט, ומתעלמת מפרמטרים נוספים. אחד הפרמטרים האלה, למשל, הוא '''מידת ההעדפה'''.
אם על שני חברים לבחור אם לקנות לארוחה [[גבינה]] או [[סלט]], כאשר אחד מהם מעדיף לקנות גבינה בגלל טעמה (אך מוכן לאכול גם סלט), ואילו האחר [[אלרגיה|אלרגי]] ל[[חלב]] ולא יכול לאכול גבינה כלל, רובנו היינו מגדירים התחשבות יתרה בחבר האלרגי כהוגנת. עם זאת, שיטה שמתחשבת ב'''מידה''' שבה הוא מעדיף סלט על גבינה לא עונה על ההגדרה הפורמלית של "שיטה הוגנת", ולמעשה איננה נחשבת כלל לשיטה לשקלול העדפות.
באופן דומה, שיטה לשקלול העדפות של פרט עשויה להתחשב בסדר העדפותיו לפי כל קריטריון, אך לא במידת ההעדפה. בדוגמה שהוצגה לעיל - קניית מכונית - השיטה יכולה להתחשב בכך שמכונית אחת יקרה יותר מחברתה, אך לא ב[[הפרש]] בין המחירים. מאחר שכל שיטה מעשית לשקלול הנתונים כן תתחשב במחירים עצמם ובהפרש ביניהם, למשפט אין בהקשר זה השלכות מעשיות.
שיטות שקלול שמתבססות על מתן נקודות לאפשרויות ייחשבו לרוב כשיטות הוגנות, אף על פי שאינן עונות להגדרה של "שיטה הוגנת". על כן, משפט ארו לא חל לגביהן.
== ראו גם ==
* [[פונקציית רווחה חברתית]]
==קישורים חיצוניים==
* {{לא מדויק|173|בחר לך דיקטטור}}
[[קטגוריה: משפטים מתמטיים|ארו]]
[[קטגוריה: תורת המשחקים]]
[[קטגוריה:בחירות]]
[[en:Arrow's impossibility theorem]]
[[de:Arrow-Theorem]]
[[es:Paradoja de Arrow]]
[[fi:Arrow'n paradoksi]]
[[fr:Théorème d'impossibilité d'Arrow]]
[[it:Teorema dell'impossibilità di Arrow]]
[[ja:アローの不可能性定理]]
[[pl:Twierdzenie Arrowa]]
[[pt:Teorema da impossibilidade de Arrow]]
[[ru:Теорема Эрроу]]
[[tr:Arrow'un İmkânsızlık Kuramı]]
[[zh:阿罗悖论]]
| |||