Part of proof of Gibbard-Satterthwaite Theorem

Question

I'm currently working through Nisan's Algorithmic Game Theory, Chapter 9 (Introduction to Mechanism Design). A part of the proof for the Gibbard-Satterthwaite Theorem is given as "obvious," but I can't seem to work out why. I'll provide some definitions first:

Let $A$ be a set of alternatives ('candidates') and let there be a set of voters $1,\dots,n$. Each voter $i$ has some total preference ordering $\prec_i$ on $A$. The set of all total orders on $A$ is denoted by $L$.

A social welfare function $F:L^n\to L$ is a function from the preferences $(\prec_1,\dots,\prec_n)$ of the voters to a single choice preference $\prec$.

A social welfare function $F:L^n\to L$ is dictatorship if there is a voter $i$ such that for all $\prec_1,\dots,\prec_n\in L$ we have $F(\prec_1,\dots,\prec_n)=\prec_i$.

A social choice function $f:L^n\to A$ is a function from the preferences of the voters to a single alternative.

A social choice function $f:L^n\to A$ is a dictatorship if there is a voter $i$ such that, for all $\prec_1,\dots,\prec_n\in L$, we have $f(\prec_1,\dots,\prec_n)=a$ where $a$ is at the top of $\prec_i$.

A social choice function $f:L^n\to A$ is incentive compatible if, for all $\prec_1,\dots,\prec_n\in L$ and for any $\prec_i'\in L$ we have that $$ a=f(\prec_1,\dots,\prec_n)\neq f(\prec_1,\dots,\prec_i',\dots,\prec_n)=a' $$ implies $$ a\prec'_ia'\qquad\text{and}\qquad a'\prec_i a. $$ [Intuitively this means that voter $i$ cannot strategically misrepresent their true preferences and obtain a better outcome.]

Given a preference $\prec$ and a subset $B\subset A$, the notation $\prec^B$ denotes a new preference obtained by moving everything in $B$ to the top of $\prec$, while preserving the relative preferences of alternatives in $B$. For instance, if $A=\{a,b,c,d,e\}$ and $B=\{b,c\}$ and $a\prec c\prec d\prec b\prec e$ then $a\prec^Bd\prec^Be\prec^Bc\prec^Bb$.

A social choice function $f$ onto $A$ can be extended into a social welfare function $F$ via $$ a\prec b\iff f(\prec_1^{\{a,b\}},\dots,\prec_n^{\{a,b\}})=b, $$ where $\prec=F(\prec_1,\dots,\prec_n)$.

Finally, here is the 'obvious' claim:

Claim. If $f$ is an incentive compatible social choice function $f$ onto $A$ and $f$ is not a dictatorship, then the extension $F$ is also not a dictatorship.

What I've done already: I've been able to show that the extension $F$ is a well-defined social welfare function (that is, $F$ is antisymmetric and transitive). I'm trying to show the contrapositive of the claim. Say $F$ is dictatorial in voter $i$, so that $F(\prec_1,\dots,\prec_n)=\prec_i$. I want to show that $f$ is also dictatorial in voter $i$. Let's say $\prec_i$ ranks $a$ at the top. By definition of $F$ as an extension of $f$, this means $$ b\prec_i a\implies f(\prec_1^{\{a,b\}},\dots,\prec_n^{\{a,b\}})=a. $$ But what I need is that $f(\prec_1,\dots,\prec_n)=a$. It seems like incentive compatibility is the key thing here - perhaps I can somehow show that, by sequentially changing each $\prec_j^{\{a,b\}}$ to $\prec_j$, then $f$ is unchanged after each step. However it's unclear to me how to proceed.

Any help would be appreciated, thank you.

Answer 1

I solved it; here's my solution:

Let $f:L^n\to A$ be an incentive compatible, non-dictatorial social choice function and let $F:L^n\to L$ be its extension. To show that $F$ is non-dictatorial, then for any voter $i\in\{1,\dots,n\}$ we need to find $\prec_1,\dots,\prec_n\in L$ such that $\prec_i\,\neq\,\prec$, where $\prec\,=F(\prec_1,\dots,\prec_n)$. So we begin by picking any $i\in\{1,\dots,n\}$.

Since $f$ is non-dictatorial, let $\prec_1,\dots,\prec_n\in L$ be such that $\prec_i$ ranks some $a\in A$ first but $$ f(\prec_1,\dots,\prec_n)=b\neq a. $$ By assumption $b\prec_ia$; we will show that $a\prec b$. For each $j=1,\dots,n$, sequentially change $\prec_j$ to $\prec_j^{\{a,b\}}$. We claim that after each step, the value of $f$ is unchanged. Indeed, assume that before the $j$th step we still have $$ f(\prec^{\{a,b\}}_1,\dots,\prec^{\{a,b\}}_{j-1},\prec_j,\dots,\prec_n)=b. $$ After the $j$th step, say we have $$ f(\prec^{\{a,b\}}_1,\dots,\prec^{\{a,b\}}_j,\prec_{j+1},\dots,\prec_n)=c $$ for some $c$. Suppose $c\neq b$. Then by incentive compatibility it must follow that $$ c\prec_jb\qquad\text{and}\qquad b\prec_j^{\{a,b\}}c. $$ The preference $b\prec_j^{\{a,b\}}c$ is only possible if $c=a$. But then the preference $c\prec_jb$ is really just $a\prec_jb$. Clearly it is impossible for $a\prec_jb$ and $b\prec_j^{\{a,b\}}a$ to be both true. Hence, $c$ must be the same as $b$.

From this we can conclude that $f(\prec_1^{\{a,b\}},\dots,\prec_n^{\{a,b\}})=b$, so that $a\prec b$, whence $\prec_i$ and $\prec$ disagree on $a$ and $b$. This concludes the proof. $\blacksquare$

The book says the claim is obvious but I can't find a shorter way to show this.