# Part of proof of Gibbard-Satterthwaite Theorem

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.

• I might be misunderstanding the extension, but couldn't you let $B = A$ and thus $f$ must be dictatorial? Or is $B$ limited to 2 elements? Commented Nov 1, 2021 at 0:36
• Hi, in the definition of the extension, to know if $x\prec y$ for any two elements $x$ and $y$, you have to see if $f(\prec_1^{\{x,y\}},\dots,\prec_n^{\{x,y\}})=y$. So yes, $B$ is limited to 2 elements. Commented Nov 1, 2021 at 2:19

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$$