2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Nov 1, 2021 at 0:36
  • $\begingroup$ 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. $\endgroup$
    – andrew
    Nov 1, 2021 at 2:19

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.