משפט ארו – הבדלי גרסאות

הוסרו 33 בתים ,  לפני שנתיים
זוטות
(זוטות)
 
חוקה (מנגון שקלול) המקיימת את שלוש הדרישות הבאות תוגדר כ'''חוקה הוגנת''':
* החוקה תכבד [[קונצנזוס]]: אם כל הפרטים מעדיפים את אפשרות A על-פני אפשרות B, מן הדין שגם הדירוג הקיבוצי יעדיף את A על B (לדרישה זו קוראים "[[יעילות פארטו]]").
* [[אי-תלות באפשרויות לא רלוונטיות]]: מקומן היחסי של האפשרויות A ו-B בדירוג הקיבוצי תלוי רק במקומן היחסי בדירוגים הפרטיים (ולא במקומן בהשוואה לאפשרויות אחרות).
* אין '''דיקטטור''': לאף אדם אין כוח לקבוע את הדירוג הקיבוצי לבדו.
 
 
===דוגמה===
נניח כי שלושה חברים: אבי, בני וגלית מעוניינים להזמין [[פיצה]]. באפשרותם לבחור רק אחת מבין שלוש תוספות: [[פטריות]], [[זית|זיתים]]ים או [[תירס]]. כמו כן, יכול להיות שחלק מהתוספות אזלו, ושלא ניתן להזמין אותן. שלושת החברים מעוניינים לגבש סדר העדפות מסוים, שיבטא את העדפותיהם.
 
נסתכל על מספר שיטות לשקלול ההעדפות של החברים:
* '''[[סדר לקסיקוגרפי|סידור אלפביתי]]''': ניתן לקבוע את סדר ההעדפות של הקבוצה לפי סדר הופעת שמות התוספות במילון, כלומר זיתים, אחר-כך פטריות ולבסוף תירס.
 
:שיטה זו אינה מוצלחת, כי היא מתעלמת מרצונותיהם של החברים. בפרט, היא לא עונה על ההגדרה של "שיטה הוגנת", משום שהיא אינה מכבדת קונצנזוס: אפילו אם כל החברים מעדיפים תירס על זיתים, השיטה האלפביתית בחרה עבורם זיתים ולא תירס.
* '''שיטת האפשרות הראשונה''': ניתן לקבוע את סדר ההעדפות של הקבוצה לפי האפשרות הרצויה ביותר בעיני כל פרט. למשל, אם שני חברים בוחרים בתירס כאפשרות המועדפת עליהם, ואחד בחר בפטריות, סדר ההעדפות המשוקלל יהיה: תירס, אחר-כך פטריות, ואחר-כך זיתים.
 
* '''שיטת האפשרות הראשונה''': ניתן לקבוע את סדר ההעדפות של הקבוצה לפי האפשרות הרצויה ביותר בעיני כל פרט. למשל, אם שני חברים בוחרים בתירס כאפשרות המועדפת עליהם, ואחד בחר בפטריות, סדר ההעדפות המשוקלל יהיה: תירס, אחר-כך פטריות, ואחר-כך זיתים.
 
:שיטה זו חשופה למניפולציות, משום שחבר שלטעמו זיתים עדיפים על תירס העדיף על פטריות, הרואה שלזיתים אין סיכוי להיבחר, עשוי להחליף את סדר העדיפויות של תירס וזיתים, על-מנת להבטיח את מקומו של התירס על-פני הפטריות שנואות נפשו. השיטה מתחשבת במקומה של האפשרות השלישית בבואה לדרג שתי אפשרויות אחרות.
: מלבד זה, שיטת האפשרות הראשונה אינה מכריעה בכל המקרים: אם כל חבר מעדיף תוספת אחרת, השיטה תותיר אותם בלי הכרעה.
* '''דיקטטורה (של אבי)''': אבי, שבידיו ה[[טלפון]], יכול לבצע את ההזמנה לפי רצונותיו, בלי להתחשב בחבריו כלל.
 
* '''דיקטטורה (של אבי)''': אבי, שבידיו ה[[טלפון]], יכול לבצע את ההזמנה לפי רצונותיו, בלי להתחשב בחבריו כלל.
 
:שיטה זו איננה הוגנת כלפי בני וגלית שאינם יכולים להשפיע על הזמנת הפיצה.
 
==הוכחת המשפט==
 
נניח כי אנו משתמשים בשיטה לשקלול העדפות שעומדת בשני התנאים הראשונים, ונוכיח כי קיים בה דיקטטור. את המשפט נוכיח באמצעות שני [[למה (מתמטיקה)|משפטי עזר]].
 
'''המשפט:''' אם כל אחד מהפרטים ממקם את אפשרות <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>.
 
'''משפט''':
נניח שישנם לפחות שלושה מועמדים. כל פונקציה המתאימה יחס על תת-קבוצה של אפשרויות לכל וקטור של יחסי העדפות שמקיימת את הדרישות הבאות היא דיקטטורה.
* פה אחד: אם כולם מעדיפים את A במקום ראשון אז A נבחר במקום ראשון (חזק)
* מונוטוניות: אם A נבחר ביחס ההעדפות p ויש יחס ההעדפות שני q שבו מצבו של A אינו נגרע אז מצבו לא נגרע בדירוג של הפונקציה. כלומר אם מתקיים שלכל שחקן ולכל אפשרות B אם שחקן העדיף את A על B ב-p אז גם ב-q, גורר שמצבו לא נגרע בדירוג של הפונקציה.
'''הוכחה'''
עבור <math>\ K = 1</math> זהו [[משפט גיבארד-סתרסוויט]], ואם K הוא מספר המועמדים זהו משפט ארו.
 
נוכיח תחילה את המשפט באינדוקציה על K כאשר הטווח של הפונקציה הוא קבוצת יחסי העדפות חזקים על קבוצות בנות K אפשרויות. בסיס האינדוקציה <math>\ K = 1</math> כבר נתון.
נניח שהמשפט נכון עבור K ונוכיח אותו עבור <math>\ K + 1</math>.
פונקציה f מחזירה דירוג על <math>\ K + 1</math> איברים נגדיר את הפונקציה g להיות הפונקציה שמחזירה את K האיברים הראשונים שנבחרו לפי f (ניתן לבחור אותם כי f מחזירה יחס חזק על המועמדים).
הפונקציה g גם מקיימת את הדרישות מכיוון ש f מקיימת אותם ולכן g דיקטטורה .
 
אז f היא דיקטטורה ב-K האיברים הראשונים של שחקן i נניח בשלילה ש i לא דיקטטור באיבר האחרון
כלומר יש יחס ההעדפות p שבו i מעדיף את A במקום ה <math>\ K + 1</math> אבל B נבחר במקום הזה. כיוון ש i דיקטטור של K
האיברים הראשונים i מעדיף את A על B אחרת B נבחר במקום יותר טוב מ <math>\ K + 1</math>, ובנוסף A לא נבחר.
 
אם i מחליף בסדר ההעדפות שלו בין A לאיבר ה K שלו אז A נבחר במקום ה K,
וB עדיין לא יכול להיבחר במקום טוב מ<math>\ K + 1</math>.
מצב 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 דיקטטור חלש.
==משמעויות נוספות==
בנוסף להשלכותיו של משפט ארו בתחום קבלת ההחלטות בקבוצה, למשפט השלכות גם בתחום קבלת ההחלטות על ידי אדם יחיד, כאשר מתייחסים אל [[קריטריון|קריטריונים]] במקום לפרטים בקבוצה. פרשנות זו של המשפט, עוסקת במקרה שבו אדם רוצה לקבוע סדר העדפות כללי בין מספר אפשרויות, על ידי שקלול סדרי העדפות בין אותן אפשרויות על פי קריטריונים שונים. טבעי שהאדם ירצה שהשקלול יענה על שתי הדרישות הבאות:
 
* '''כלל העליונות המוחלטת''': אם אפשרות א' עדיפה על אפשרות ב' לפי כל קריטריון, אזי אפשרות א' עדיפה על אפשרות ב' גם באופן כללי.
* '''אי-תלות בין אפשרויות לא רלוונטיות''': הדירוג היחסי של אפשרות א' לעומת אפשרות ב' בסדר ההעדפות הכללי יהיה תלוי אך ורק בדירוג היחסי של אפשרות א' לעומת אפשרות ב' לפי כל קריטריון (ולא בדירוגן ביחס לאפשרויות אחרות, למשל).
 
{| class="wikitable" border="1"
! width="20%" | צבע
! width="20%" | בטיחות
! width="20%" | נוחות הנהיגה
! width="20%" | עלות התחזוקה
! width="20%" | מחיר
|-
| 1
| 1