Parte de la demostración del teorema de Gibbard-Satterthwaite

Question

Actualmente estoy trabajando a través de Nisan's Teoría algorítmica de los juegos , Capítulo 9 (Introducción al diseño de mecanismos). Una parte de la demostración del teorema de Gibbard-Satterthwaite se da como "obvia", pero no consigo entender por qué. Primero daré algunas definiciones:

Dejemos que $A$ sea un conjunto de alternativas ("candidatos") y que haya un conjunto de votantes $1,\dots,n$ . Cada votante $i$ tiene alguna ordenación de preferencia total $\prec_i$ en $A$ . El conjunto de todos los pedidos totales en $A$ se denota por $L$ .

A función de bienestar social $F:L^n\to L$ es una función de las preferencias $(\prec_1,\dots,\prec_n)$ de los votantes a una única opción de preferencia $\prec$ .

Una función de bienestar social $F:L^n\to L$ es dictadura si hay un votante $i$ tal que para todo $\prec_1,\dots,\prec_n\in L$ tenemos $F(\prec_1,\dots,\prec_n)=\prec_i$ .

A función de elección social $f:L^n\to A$ es una función de las preferencias de los votantes a una única alternativa.

Una función de elección social $f:L^n\to A$ es un dictadura si hay un votante $i$ tal que, para todo $\prec_1,\dots,\prec_n\in L$ tenemos $f(\prec_1,\dots,\prec_n)=a$ donde $a$ está en la cima de $\prec_i$ .

Una función de elección social $f:L^n\to A$ es compatible con los incentivos si, para todo $\prec_1,\dots,\prec_n\in L$ y para cualquier $\prec_i'\in L$ tenemos que $$ a=f(\prec_1,\dots,\prec_n)\neq f(\prec_1,\dots,\prec_i',\dots,\prec_n)=a' $$ implica $$ a\prec'_ia'\qquad\text{and}\qquad a'\prec_i a. $$ [Intuitivamente esto significa que el votante $i$ no pueden falsear estratégicamente sus verdaderas preferencias y obtener un mejor resultado].

Dada una preferencia $\prec$ y un subconjunto $B\subset A$ la notación $\prec^B$ denota una nueva preferencia obtenida al mover todo en $B$ a la parte superior de $\prec$ conservando las preferencias relativas de las alternativas en $B$ . Por ejemplo, si $A=\{a,b,c,d,e\}$ y $B=\{b,c\}$ y $a\prec c\prec d\prec b\prec e$ entonces $a\prec^Bd\prec^Be\prec^Bc\prec^Bb$ .

Una función de elección social $f$ en $A$ puede ser ampliado en una función de bienestar social $F$ a través de $$ a\prec b\iff f(\prec_1^{\{a,b\}},\dots,\prec_n^{\{a,b\}})=b, $$ donde $\prec=F(\prec_1,\dots,\prec_n)$ .

Por último, he aquí la afirmación "obvia":

Reclamación. Si $f$ es una función de elección social compatible con los incentivos $f$ en $A$ y $f$ no es una dictadura, entonces la extensión $F$ tampoco es una dictadura.

Lo que ya he hecho: He podido demostrar que la extensión $F$ es una función de bienestar social bien definida (es decir, $F$ es antisimétrico y transitivo). Intento demostrar el contrapositivo de la afirmación. Digamos que $F$ es dictatorial en el votante $i$ para que $F(\prec_1,\dots,\prec_n)=\prec_i$ . Quiero demostrar que $f$ también es dictatorial en cuanto a los votantes $i$ . Digamos que $\prec_i$ rangos $a$ en la parte superior. Por definición de $F$ como una extensión de $f$ Esto significa que $$ b\prec_i a\implies f(\prec_1^{\{a,b\}},\dots,\prec_n^{\{a,b\}})=a. $$ Pero lo que necesito es que $f(\prec_1,\dots,\prec_n)=a$ . Parece que la compatibilidad de los incentivos es la clave aquí - tal vez pueda demostrar de alguna manera que, cambiando secuencialmente cada $\prec_j^{\{a,b\}}$ a $\prec_j$ entonces $f$ no se modifica después de cada paso. Sin embargo, no tengo claro cómo proceder.

Cualquier ayuda se agradece, gracias.

Answer 1

Lo he resuelto; esta es mi solución:

Dejemos que $f:L^n\to A$ sea una función de elección social no dictatorial y compatible con los incentivos y que $F:L^n\to L$ sea su extensión. Para demostrar que $F$ es no dictatorial, entonces para cualquier votante $i\in\{1,\dots,n\}$ necesitamos encontrar $\prec_1,\dots,\prec_n\in L$ tal que $\prec_i\,\neq\,\prec$ , donde $\prec\,=F(\prec_1,\dots,\prec_n)$ . Así que empezamos eligiendo cualquier $i\in\{1,\dots,n\}$ .

Desde $f$ es no dictatorial, dejemos que $\prec_1,\dots,\prec_n\in L$ sea tal que $\prec_i$ clasifica algunos $a\in A$ primero pero $$ f(\prec_1,\dots,\prec_n)=b\neq a. $$ Por suposición $b\prec_ia$ demostraremos que $a\prec b$ . Para cada $j=1,\dots,n$ , cambiar secuencialmente $\prec_j$ a $\prec_j^{\{a,b\}}$ . Afirmamos que después de cada paso, el valor de $f$ no cambia. En efecto, supongamos que antes del $j$ paso todavía tenemos $$ f(\prec^{\{a,b\}}_1,\dots,\prec^{\{a,b\}}_{j-1},\prec_j,\dots,\prec_n)=b. $$ Después de la $j$ paso, digamos que tenemos $$ f(\prec^{\{a,b\}}_1,\dots,\prec^{\{a,b\}}_j,\prec_{j+1},\dots,\prec_n)=c $$ para algunos $c$ . Supongamos que $c\neq b$ . Entonces, por la compatibilidad de los incentivos debe seguirse que $$ c\prec_jb\qquad\text{and}\qquad b\prec_j^{\{a,b\}}c. $$ La preferencia $b\prec_j^{\{a,b\}}c$ sólo es posible si $c=a$ . Pero entonces la preferencia $c\prec_jb$ es realmente $a\prec_jb$ . Es evidente que es imposible que $a\prec_jb$ y $b\prec_j^{\{a,b\}}a$ para que ambos sean verdaderos. Por lo tanto, $c$ debe ser el mismo que $b$ .

De esto podemos concluir que $f(\prec_1^{\{a,b\}},\dots,\prec_n^{\{a,b\}})=b$ para que $a\prec b$ De ahí que $\prec_i$ y $\prec$ no estar de acuerdo con $a$ y $b$ . Con esto concluye la prueba. $\blacksquare$

El libro dice que la afirmación es obvia pero no encuentro una forma más corta de demostrarlo.