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

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

תהי A קבוצת האפשוריות לבחירה, ויהי <math>\ P^N </math> וקטור בחירות, כאשר <math>N=\{1,2,\cdots,n\}</math> היא קבוצת הבוחרים. <br>

יהיו <math>P</math>, <math>Q</math> שני יחסי העדפות חזקים. <br>

<math>R\subseteq A</math> תת-קבוצה של אפשרויות. <br>

נסמן ב <math>Z\left(P,Q;R\right)</math> את יחס ההעדפות במוגדר באופן הבא: <br>

* כל האפשרויות ב <math>R</math> מדורגות '''לפני''' האפשרויות שאינן ב <math>R</math>. <br>

* את האפשרויות ב <math>R</math> מדרגים לפי <math>P</math>. <br>

* את האפשרויות שאינן ב <math>R</math> מדרגים לפי <math>Q</math>. <br>

'''דוגמה:''' נניח שקבוצת האפשרויות היא <math>A=\left\{a_1, a_2, a_3, a_4\right\}</math>, ו- <math>R=\left\{a_1,a_4\right\}</math>. <br>

אם יחסי ההעדפות <math>P</math>ו- <math>Q</math>מוגדרים באופן הבא: <br>

<math>P: a_1> a_2> a_3> a_4</math><br>

<math>Q: a_2> a_4> a_1> a_3</math><br>

אז היחס <math>Z\left(P,Q;R\right)</math> יהיה מוגדר כך: <br>

תהי <math>G</math> פונקציית בחירה חברתית מונוטונית. <br>

יהיו <math>P^N</math>, <math>Q^N</math> נתונים. יהי <math>R\subseteq A</math>. נסמן <math>a=G\left(P^N\right)</math>, ונניח <math>a\in R</math> , אז נקבל ש- <math> G\left(Z\left(P_i,Q_i;R\right)\right)=a</math>.<br>

תהי <math>G</math> פונקציית בחירה חברתית המקיימת את עקרונות המונוטונית והפה אחד. <br>

אז בגלל עקרון הפה אחד: <math> G\left(Z\left(P^N,Q^N;R\right)\right)=a \ne b</math>. <br>

מהמסקנה של משפט עזר 1, נסיק ש- <math>G\left(P^N\right)\ne b</math>. <br><br>

יהי <math>W^N\in\left(P\left(A\right)\right)^N</math> פרופיל העדפות חזקות כלשהו, קבוע לאורך כל ההוכחה. <br>

<math>a G\ge_{Fleft(Z\left(P^N,W^N;\left\{a,b\right)\}a\right)\right)=b</math> , <math> \forall a \in ALeftarrow</math>. <brmath>b>_{F\left(P^N\right)}a</math>

כל האפשרויות השונות מ- <math>a</math> ו- <math>b</math> מועדפת פחות מ- <math>a</math> על ידי כל הבוחרים, לכן לפי '''משפט עזר 2''', אף אחת מאפשרויות אלה אינה יכולה להיות <math> G\left(Z\left(P^N,W^N;\left\{a,b\right\}\right)\right) </math> . לכן <math> G\left(Z\left(P^N,W^N;\left\{a,b\right\}\right)\right)\in \left\{a,b\right\} </math> . <br>

לפי הגדרת היחס הבינארי <math>F\left(P^N\right)</math> נקבל שלכל זוג אפשרויות <math>a</math> ,<math>b</math> שונות זו מזו ב <math>R</math>, מתקיים: <math>b>_{F\left(P^N\right)}a</math> או <math>a>_{F\left(P^N\right)}b</math>, כלומר, <math>F\left(P^N\right)</math> הוא יחס העדפות שלם על <math>R</math>.<br>

<math>a>_{F\left(P^N\right)}b</math>, ו- <math>b>_{F\left(P^N\right)}c</math> '''אבל''' <math>c>_{F\left(P^N\right)}a</math>. <br>

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

'''נשים לב לזהות הבאה:''' <math> 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)</math>.<br>

על <math>\left\{a, b\right\}</math> יחס הסדר נקבע בשני המקרים על ידי <math>P^N</math>, ועל המשלים של <math>\left\{a, b\right\}</math> יחס הסדר נקבע בשני המקרים על ידי <math>W^N</math>. לכן השוויון הנ"ל מתקיים. <br><br>

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

בפרט נקבל ש- <math> 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 </math>, ולפי '''משפט עזר 1''', נסיק כי <math> G\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right)\right) \ne b </math>. <br>

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

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

כמו'''סך כן, מכך ש <math>c>_{F\left(P^N\right)}a</math>,הכל נקבלקיבלנו ש- <math> G\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right)\right) \nenot\in \left\{a, b,c\right\} </math>.''' <br>

'''סךמצד הכלשני, קיבלנולכל <math>d \in A \ \left\{a, b, c\right\}</math>, ש-מתקיים: <math> G\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right)\right) \not\inne \left\{a, b,c\right\}d </math>.''' <br>

יהי <math>P^N</math> המקיים <math>a>_{P_i}b</math>, <math>\forall i \in N</math>. צריכים להראות ש- <math>a>_{F\left(P^N\right)}b</math>.<br>

לשם כך יש להוכיח ש- <math> G\left(Z\left(P^N,W^N;\left\{a,b\right\}\right)\right)=a </math>.<br>

אכן, נשים לב שביחסים <math>Z\left(P^N,W^N;\left\{a,b\right\}\right) </math>, <math>a</math> ממוקם במקום הראשון לכל <math>i</math>. כיוון ש-<math>G</math> מקיימת את עקרון הפה אחד, אז השוויון <math> G\left(Z\left(P^N,W^N;\left\{a,b\right\}\right)\right)=a </math> מתקיים. <br>

'''לכן <math>F</math> מקיימת את עקרון הפה אחד.'''<br><br>

<math>\forall i \in N</math> <math>a>_{P_i}b</math> <math>\Leftrightarrow</math> <math>a>_{Q_i}b</math>. <br>

יש להוכיח ש- <math>a>_{F\left(P^N\right)}b</math> <math>\Leftrightarrow</math> <math>a>_{F\left(Q^N\right)}b</math> , או באופן שקול: <math> 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) </math>.<br>

ואכן זה מתקיים משום ש- <math>Z\left(P^N,W^N;\left\{a,b\right\}\right)= Z\left(Q^N,W^N;\left\{a,b\right\}\right) </math>, '''ולכן <math>F</math> מקיימת את עקרון האי תלות באפשרויות לא רלוונטיות.'''<br><br>

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

יהי <math>P^N</math> כלשהו, ותהי <math>a</math> האפשרות בעדיפות ראשונה לפי <math>P_i</math> של בוחר <math>i</math>.<br>

יש להוכיח כי <math>G\left(P^N\right)=a</math>.<br><br>