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

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

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

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

הכנה להוכחה

המשפט

תהי A קבוצת האפשרויות לבחירה, ויהי $\ P^{N}$ וקטור בחירות, כאשר $N=\{1,2,\cdots ,n\}$ היא קבוצת הבוחרים. אם $\left|A\right|\geq 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)\neq a$, אז נקבל ש- $G\left(P^{N}\right)\neq a$.

משפט עזר 2

תהי $G$ פונקציית בחירה חברתית המקיימת את עקרונות המונוטונית והפה אחד. יהיו נתונים $P^{N}$,$a,b\in A$ (יש עוד מועמדים). אם $a>_{P_{i}}b$ $\forall i$ $\Leftarrow$ הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle G\left(P^{N}\right)\neq b} .

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

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

הגדרה פונקציית הרווחה החברתית $F$

יהי הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle W^{N}\in \left(P\left(A\right)\right)^{N}} פרופיל העדפות חזקות כלשהו, קבוע לאורך כל ההוכחה. לכל פרופיל העדפות חזקות $P^{N}$ נגדיר יחס בינארי הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle F\left(P^{N}\right)} באופן הבא:

לכל שתי אפשרויות שונות הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle 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\geq _{F\left(P^{N}\right)}a$, הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \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$, מתקיים: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b>_{F\left(P^N\right)}a} או הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a>_{F\left(P^N\right)}b} , כלומר, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F\left(P^N\right)} הוא יחס העדפות שלם על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} . נשים לב גם שאין אדישות ב- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F\left(P^N\right)} , כלומר, או שהחברה מעדיפה ממש את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} , או שהחברה מעדיפה ממש את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} .

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

נניח בשלילה כי היחס אינו טרנזיטיבי, כלומר קיימים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a, b, c \in R} כך ש: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a>_{F\left(P^N\right)}b} , ו- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b>_{F\left(P^N\right)}c} אבל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c>_{F\left(P^N\right)}a} . (האפשרות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c\approx_{F\left(P^N\right)}a} לא תיתכן, משום שלפי הגדרת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F\left(P^N\right)} , שני איברים הם שקולים אם ורק אם הם שווים, ובמקרה זה נקבל שגם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a>_{F\left(P^N\right)}b} וגם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b>_{F\left(P^N\right)}a} מתקיימים ביחד, וזו סתירה להגדרה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F\left(P^N\right)} .)

נשים לב לזהות הבאה: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\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)} . על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{a, b\right\}} יחס הסדר נקבע בשני המקרים על ידי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P^N} , ועל המשלים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{a, b\right\}} יחס הסדר נקבע בשני המקרים על ידי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle W^N} . לכן השוויון הנ"ל מתקיים.

מכך ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a>_{F\left(P^N\right)}b} נובע כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G\left(Z\left(P^N,W^N;\left\{a,b\right\}\right)\right)=a} , ולפי הזהות הקודמת, נקבל ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\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} . בפרט נקבל ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\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) \ne b } , ולפי משפט עזר 1, נסיק כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right)\right) \ne b } .

כלומר, הראינו ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right)\right) \ne b } הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Rightarrow} הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a>_{F\left(P^N\right)}b} .

באופן דומה, מכך ש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b>_{F\left(P^N\right)}c} , נקבל ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right)\right) \ne c } .

כמו כן, מכך ש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c>_{F\left(P^N\right)}a} , נקבל ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right)\right) \ne a } .

סך הכל קיבלנו ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right)\right) \not\in \left\{a, b,c\right\} } .

מצד שני, לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d \in A \ \left\{a, b, c\right\}} , מתקיים: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right)\right) \ne d } . הסבר: לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} כזה מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a>_{G\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right)\right)}d} , ולפי משפט עזר 2 נקבל ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right)\right) \ne d } .

אבל אם כך, מתקבל ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G\left(Z\left(P^N,P^N;\left\{a,b,c\right\}\right)\right) \not\in A } , וזה בסתירה להגדרת הבחירה החברתית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} . מכאן שהנחת השלילה שהיחס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F\left(P^N\right)} אינו טרנזיטיבי אינה נכונה, ולכן היחס כן טרנזיטיבי.

הראינו שהיחס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F\left(P^N\right)} הוא שלם וטרנזיטיבי, לכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} היא פונקציית רווחה חברתית.

נותר להראות ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} מקיימת את עקרון הפה אחד, ואי תלות באפשרויות לא רלוונטיות.

נראה ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} מקיימת את עקרון הפה אחד

יהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P^N} המקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a>_{P_i}b} , הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall i \in N} . צריכים להראות ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a>_{F\left(P^N\right)}b} . לשם כך יש להוכיח ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G\left(Z\left(P^N,W^N;\left\{a,b\right\}\right)\right)=a } . אכן, נשים לב שביחסים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z\left(P^N,W^N;\left\{a,b\right\}\right) } , הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} ממוקם במקום הראשון לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} . כיוון ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} מקיימת את עקרון הפה אחד, אז השוויון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G\left(Z\left(P^N,W^N;\left\{a,b\right\}\right)\right)=a } מתקיים. לכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} מקיימת את עקרון הפה אחד.

נראה ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} מקיימת את עקרון האי תלות באפשרויות לא רלוונטיות

יהיו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P^N} , הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q^N} , הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} , הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} המקיימים: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall i \in N} הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a>_{P_i}b} הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Leftrightarrow} הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a>_{Q_i}b} . יש להוכיח ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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$ כך ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall P^N} מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F\left(P^N\right)=P_i} .

סיום ההוכחה – נראה ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} היא דיקטטורית, עם אותו דיקטטור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i}

יהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P^N} כלשהו, ותהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} האפשרות בעדיפות ראשונה לפי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_i} של בוחר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} . יש להוכיח כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G\left(P^N\right)=a} .

נניח בשלילה ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G\left(P^N\right)=b \ne a} , אז לפי משפט עזר 1 מתקיים ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G\left(Z\left(P^N,W^N;\left\{a,b\right\}\right)\right)=b \ne a } . לכן, לפי הגדרת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} נקבל שהחברה כולה מעדיפה את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} על פני הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} , או באופן שקול: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b>_{F\left(P^N\right)}a} , וזאת בסתירה לכך ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} דיקטטור לפי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} . לכן קיבלנו שגם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} היא דיקטטורית, עם אותו דיקטטור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} .

ראו גם

• משפט ארו

לקריאה נוספת

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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