משפט גיבארד-סתרסוויט

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

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

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

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

הכנה להוכחה[עריכת קוד מקור | עריכה]

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

תהי A קבוצת האפשוריות לבחירה, ויהי \ P^N וקטור בחירות, כאשר N=\{1,2,\cdots,n\} היא קבוצת הבוחרים. אם \left| A \right| \ge 3 , ואם \,G : P^N \rightarrow A היא פונקציית בחירה חברתית המקיימת את עקרונות המונוטוניות ואת עקרון הפה אחד, אז G דיקטטורית.

רעיון ההוכחה[עריכת קוד מקור | עריכה]

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

סימוני עזר[עריכת קוד מקור | עריכה]

יהיו P, Q שני יחסי העדפות חזקים. R\subseteq A תת-קבוצה של אפשרויות. נסמן ב Z\left(P,Q;R\right) את יחס ההעדפות המוגדר באופן הבא:

  • כל האפשרויות ב R מדורגות לפני האפשרויות שאינן ב R.
  • את האפשרויות ב R מדרגים לפי P.
  • את האפשרויות שאינן ב R מדרגים לפי Q.

בנוסף נסמן: P^N= \left(P_i\right)_{i\in N} , Q^N= \left(Q_i\right)_{i\in N} , Z\left(P^N,Q^N;R\right) = \left(Z\left(P_i,Q_i;R\right)\right)_{i\in N}

דוגמה: נניח שקבוצת האפשרויות היא A=\left\{a_1, a_2, a_3, a_4\right\}, ו- R=\left\{a_1,a_4\right\}. אם יחסי ההעדפות Pו- Qמוגדרים באופן הבא: P: a_1> a_2> a_3> a_4 Q: a_2> a_4> a_1> a_3 אז היחס Z\left(P,Q;R\right) יהיה מוגדר כך:  Z\left(P,Q;R\right): a_1> a_4> a_2> a_3

משפט עזר 1[עריכת קוד מקור | עריכה]

תהי G פונקציית בחירה חברתית מונוטונית. יהיו P^N, Q^N נתונים. יהי R\subseteq A. נסמן a=G\left(P^N\right), ונניח a\in R , אז נקבל ש-  G\left(Z\left(P_i,Q_i;R\right)\right)=a. זה נובע מהגדרת המונוטוניות (לא הרענו את מצבו של a ב-  Z\left(P^N,Q^N;R\right) ביחס למצבו ב- P^N ).

מסקנה: אם a\in R וגם  G\left(Z\left(P^N,Q^N;R\right)\right)\ne a, אז נקבל ש- G\left(P^N\right)\ne a.

משפט עזר 2[עריכת קוד מקור | עריכה]

תהי G פונקציית בחירה חברתית המקיימת את עקרונות המונוטונית והפה אחד. יהיו נתונים P^N,a,b\in A (יש עוד מועמדים). אם a>_{P_i}b  \forall i \Leftarrow G\left(P^N\right)\ne b.

הוכחה: נסמן R=\left\{a,b\right\}, ונסתכל על Z\left(P^N,Q^N;R\right). אז בגלל עקרון הפה אחד:  G\left(Z\left(P^N,Q^N;R\right)\right)=a \ne b. מהמסקנה של משפט עזר 1, נסיק ש- G\left(P^N\right)\ne b.

הוכחת משפט Gibbard–Satterthwaite[עריכת קוד מקור | עריכה]

הגדרה פונקציית הרווחה החברתית F[עריכת קוד מקור | עריכה]

יהי W^N\in\left(P\left(A\right)\right)^N פרופיל העדפות חזקות כלשהו, קבוע לאורך כל ההוכחה. לכל פרופיל העדפות חזקות P^N נגדיר יחס בינארי F\left(P^N\right) באופן הבא:

לכל שתי אפשרויות שונות a, b \in R מתקיים:

 G\left(Z\left(P^N,W^N;\left\{a,b\right\}\right)\right)=a \Leftarrow a>_{F\left(P^N\right)}b  G\left(Z\left(P^N,W^N;\left\{a,b\right\}\right)\right)=b \Leftarrow b>_{F\left(P^N\right)}a

כדי שהיחס יהיה רפלקסיבי, נגדיר בנוסף: a\ge_{F\left(P^N\right)}a ,  \forall a \in A.

נראה ש-F היא פונקציית רווחה חברתית[עריכת קוד מקור | עריכה]

על מנת להראות ש F הינה פונקציית רווחה חברתית, יש להראות שהיחס F\left(P^N\right) הוא שלם וטרנזיטיבי.

היחס שלם:[עריכת קוד מקור | עריכה]

כל האפשרויות השונות מ- a ו- b מועדפת פחות מ- a על ידי כל הבוחרים, לכן לפי משפט עזר 2, אף אחת מאפשרויות אלה אינה יכולה להיות  G\left(Z\left(P^N,W^N;\left\{a,b\right\}\right)\right) . לכן  G\left(Z\left(P^N,W^N;\left\{a,b\right\}\right)\right)\in \left\{a,b\right\} . לפי הגדרת היחס הבינארי F\left(P^N\right) נקבל שלכל זוג אפשרויות a ,b שונות זו מזו ב R, מתקיים: b>_{F\left(P^N\right)}a או a>_{F\left(P^N\right)}b, כלומר, F\left(P^N\right) הוא יחס העדפות שלם על R. נשים לב גם שאין אדישות ב- F\left(P^N\right), כלומר, או שהחברה מעדיפה ממש את b על a, או שהחברה מעדיפה ממש עת a על b.

היחס טרנזיטיבי:[עריכת קוד מקור | עריכה]

נניח בשלילה כי היחס אינו טרנזיטיבי, כלומר קיימים a, b, c \in R כך ש: a>_{F\left(P^N\right)}b, ו- b>_{F\left(P^N\right)}c אבל c>_{F\left(P^N\right)}a. (האפשרות c\approx_{F\left(P^N\right)}a לא תיתכן, משום שלפי הגדרת F\left(P^N\right), שני איברים הם שקולים אם ורק אם הם שווים, ובמקרה זה נקבל שגם a>_{F\left(P^N\right)}b וגם b>_{F\left(P^N\right)}a מתקיימים בייחד, וזו סתירה להגדרה F\left(P^N\right).)

נשים לב לזהות הבאה:  Z\left(P^N,W^N;\left\{a,b\right\}\right)=Z\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right),W^N;\left\{a,b\right\}\right). על \left\{a, b\right\} יחס הסדר נקבע בשני המקרים על ידי P^N, ועל המשלים של \left\{a, b\right\} יחס הסדר נקבע בשני המקרים על ידי W^N. לכן השוויון הנ"ל מתקיים.

מכך ש- a>_{F\left(P^N\right)}b נובע כי  G\left(Z\left(P^N,W^N;\left\{a,b\right\}\right)\right)=a, ולפי הזהות הקודמת, נקבל ש-  G\left(Z\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right),W^N;\left\{a,b\right\}\right)\right)=a. בפרט נקבל ש-  G\left(Z\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right),W^N;\left\{a,b\right\}\right)\right) \ne b , ולפי משפט עזר 1, נסיק כי  G\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right)\right) \ne b .

כלומר, הראינו ש-  G\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right)\right) \ne b \Rightarrow a>_{F\left(P^N\right)}b.

באופן דומה, מכך ש b>_{F\left(P^N\right)}c, נקבל ש-  G\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right)\right) \ne c .

כמו כן, מכך ש c>_{F\left(P^N\right)}a, נקבל ש-  G\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right)\right) \ne a .

סך הכל קיבלנו ש-  G\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right)\right) \not\in \left\{a, b,c\right\} .

מצד שני, לכל d \in A \ \left\{a, b, c\right\}, מתקיים:  G\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right)\right) \ne d . הסבר: לכל d כזה מתקיים a>_{G\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right)\right)}d, ולפי משפט עזר 2 נקבל ש-  G\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right)\right) \ne d .

אבל אם כך, מתקבל ש-  G\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right)\right) \not\in A , וזה בסתירה להגדרת הבחירה החברתית G. מכאן שהנחת השלילה שהיחס F\left(P^N\right) אינו טרנזיטיבי אינה נכונה, ולכן היחס כן טרנזיטיבי.

הראינו שהיחס F\left(P^N\right) הוא שלם וטרנזיטיבי, לכן F היא פונקציית רווחה חברתית.

נותר להראות ש- F מקיימת את עקרון הפה אחד, ואי תלות באפשרויות לא רלוונטיות.

נראה ש- F מקיימת את עקרון הפה אחד:[עריכת קוד מקור | עריכה]

יהי P^N המקיים a>_{P_i}b, \forall i \in N. צריכים להראות ש- a>_{F\left(P^N\right)}b. לשם כך יש להוכיח ש-  G\left(Z\left(P^N,W^N;\left\{a,b\right\}\right)\right)=a . אכן, נשים לב שביחסים Z\left(P^N,W^N;\left\{a,b\right\}\right) , a ממוקם במקום הראשון לכל i. כיוון ש-G מקיימת את עקרון הפה אחד, אז השוויון  G\left(Z\left(P^N,W^N;\left\{a,b\right\}\right)\right)=a מתקיים. לכן F מקיימת את עקרון הפה אחד.

נראה ש- F מקיימת את עקרון האי תלות באפשרויות לא רלוונטיות:[עריכת קוד מקור | עריכה]

יהיו P^N, Q^N, a, b המקיימים: \forall i \in N a>_{P_i}b \Leftrightarrow a>_{Q_i}b. יש להוכיח ש- a>_{F\left(P^N\right)}b \Leftrightarrow a>_{F\left(Q^N\right)}b , או באופן שקול:  G\left(Z\left(P^N,W^N;\left\{a,b\right\}\right)\right)= G\left(Z\left(Q^N,W^N;\left\{a,b\right\}\right)\right) . ואכן זה מתקיים משום ש- Z\left(P^N,W^N;\left\{a,b\right\}\right)= Z\left(Q^N,W^N;\left\{a,b\right\}\right) , ולכן F מקיימת את עקרון האי תלות באפשרויות לא רלוונטיות.

ממשפט ארו, נקבל ש- F היא דיקטטורית, כלומר קיים i כך ש- \forall P^N מתקיים F\left(P^N\right)=P_i.

סיום ההוכחה – נראה ש- G היא דיקטטורית, עם אותו דיקטטור i[עריכת קוד מקור | עריכה]

יהי P^N כלשהו, ותהי a האפשרות בעדיפות ראשונה לפי P_i של בוחר i. יש להוכיח כי G\left(P^N\right)=a.

נניח בשלילה ש- G\left(P^N\right)=b \ne a, אז לפי משפט עזר 1 מתקיים ש-  G\left(Z\left(P^N,W^N;\left\{a,b\right\}\right)\right)=b \ne a . לכן, לפי הגדרת F נקבל שהחברה כולה מעדיפה את b על פני a, או באופן שקול: b>_{F\left(P^N\right)}a, וזאת בסתירה לכך ש- i דיקטטור לפי F. לכן קיבלנו שגם G היא דיקטטורית, עם אותו דיקטטור i.

ראו גם[עריכת קוד מקור | עריכה]

לקריאה נוספת[עריכת קוד מקור | עריכה]