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

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

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

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

הכנה להוכחה

המשפט

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

רעיון ההוכחה

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

סימוני עזר

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

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

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

דוגמה: נניח שקבוצת האפשרויות היא ${\displaystyle A=\left\{a_{1},a_{2},a_{3},a_{4}\right\}}$, ו- ${\displaystyle R=\left\{a_{1},a_{4}\right\}}$. אם יחסי ההעדפות ${\displaystyle P}$ו- ${\displaystyle Q}$מוגדרים באופן הבא: ${\displaystyle P:a_{1}>a_{2}>a_{3}>a_{4}}$ ${\displaystyle Q:a_{2}>a_{4}>a_{1}>a_{3}}$ אז היחס ${\displaystyle Z\left(P,Q;R\right)}$ יהיה מוגדר כך: ${\displaystyle Z\left(P,Q;R\right):a_{1}>a_{4}>a_{2}>a_{3}}$

משפט עזר 1

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

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

משפט עזר 2

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

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

הוכחת משפט גיבארד–סטרת'ווייט

הגדרה פונקציית הרווחה החברתית ${\displaystyle F}$

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

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

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

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

נראה ש-${\displaystyle F}$ היא פונקציית רווחה חברתית

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

היחס שלם

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

היחס טרנזיטיבי

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

נשים לב לזהות הבאה: ${\displaystyle 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)}$. על ${\displaystyle \left\{a,b\right\}}$ יחס הסדר נקבע בשני המקרים על ידי ${\displaystyle P^{N}}$, ועל המשלים של ${\displaystyle \left\{a,b\right\}}$ יחס הסדר נקבע בשני המקרים על ידי ${\displaystyle W^{N}}$. לכן השוויון הנ"ל מתקיים.

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

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

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

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

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

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

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

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

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

נראה ש- ${\displaystyle F}$ מקיימת את עקרון הפה אחד

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

נראה ש- ${\displaystyle F}$ מקיימת את עקרון האי תלות באפשרויות לא רלוונטיות

יהיו ${\displaystyle P^{N}}$, ${\displaystyle Q^{N}}$, ${\displaystyle a}$, ${\displaystyle b}$ המקיימים: ${\displaystyle \forall i\in N}$ ${\displaystyle a>_{P_{i}}b}$ ${\displaystyle \Leftrightarrow }$ ${\displaystyle a>_{Q_{i}}b}$. יש להוכיח ש- ${\displaystyle a>_{F\left(P^{N}\right)}b}$ ${\displaystyle \Leftrightarrow }$ ${\displaystyle a>_{F\left(Q^{N}\right)}b}$, או באופן שקול: ${\displaystyle 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)}$. ואכן זה מתקיים משום ש- ${\displaystyle Z\left(P^{N},W^{N};\left\{a,b\right\}\right)=Z\left(Q^{N},W^{N};\left\{a,b\right\}\right)}$, ולכן ${\displaystyle F}$ מקיימת את עקרון האי תלות באפשרויות לא רלוונטיות.

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

סיום ההוכחה – נראה ש- ${\displaystyle G}$ היא דיקטטורית, עם אותו דיקטטור ${\displaystyle i}$

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

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

ראו גם

• משפט ארו

לקריאה נוספת

• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, ירושלים: מאגנס, 2008, מסת"ב 9654932946