<p>I solved it; here's my solution:</p>
<p>Let <span class="math-container">$f:L^n\to A$</span> be an incentive compatible, non-dictatorial social choice function and let <span class="math-container">$F:L^n\to L$</span> be its extension. To show that <span class="math-container">$F$</span> is non-dictatorial, then for any voter <span class="math-container">$i\in\{1,\dots,n\}$</span> we need to find <span class="math-container">$\prec_1,\dots,\prec_n\in L$</span> such that <span class="math-container">$\prec_i\,\neq\,\prec$</span>, where <span class="math-container">$\prec\,=F(\prec_1,\dots,\prec_n)$</span>. So we begin by picking any <span class="math-container">$i\in\{1,\dots,n\}$</span>.</p>
<p>Since <span class="math-container">$f$</span> is non-dictatorial, let <span class="math-container">$\prec_1,\dots,\prec_n\in L$</span> be such that <span class="math-container">$\prec_i$</span> ranks some <span class="math-container">$a\in A$</span> first but
<span class="math-container">$$
f(\prec_1,\dots,\prec_n)=b\neq a.
$$</span>
By assumption <span class="math-container">$b\prec_ia$</span>; we will show that <span class="math-container">$a\prec b$</span>. For each <span class="math-container">$j=1,\dots,n$</span>, sequentially change <span class="math-container">$\prec_j$</span> to <span class="math-container">$\prec_j^{\{a,b\}}$</span>. We claim that after each step, the value of <span class="math-container">$f$</span> is unchanged. Indeed, assume that before the <span class="math-container">$j$</span>th step we still have
<span class="math-container">$$
f(\prec^{\{a,b\}}_1,\dots,\prec^{\{a,b\}}_{j-1},\prec_j,\dots,\prec_n)=b.
$$</span>
After the <span class="math-container">$j$</span>th step, say we have
<span class="math-container">$$
f(\prec^{\{a,b\}}_1,\dots,\prec^{\{a,b\}}_j,\prec_{j+1},\dots,\prec_n)=c
$$</span>
for some <span class="math-container">$c$</span>. Suppose <span class="math-container">$c\neq b$</span>. Then by incentive compatibility it must follow that
<span class="math-container">$$
c\prec_jb\qquad\text{and}\qquad b\prec_j^{\{a,b\}}c.
$$</span>
The preference <span class="math-container">$b\prec_j^{\{a,b\}}c$</span> is only possible if <span class="math-container">$c=a$</span>. But then the preference <span class="math-container">$c\prec_jb$</span> is really just <span class="math-container">$a\prec_jb$</span>. Clearly it is impossible for <span class="math-container">$a\prec_jb$</span> and <span class="math-container">$b\prec_j^{\{a,b\}}a$</span> to be both true. Hence, <span class="math-container">$c$</span> must be the same as <span class="math-container">$b$</span>.</p>
<p>From this we can conclude that <span class="math-container">$f(\prec_1^{\{a,b\}},\dots,\prec_n^{\{a,b\}})=b$</span>, so that <span class="math-container">$a\prec b$</span>, whence <span class="math-container">$\prec_i$</span> and <span class="math-container">$\prec$</span> disagree on <span class="math-container">$a$</span> and <span class="math-container">$b$</span>. This concludes the proof. <span class="math-container">$\blacksquare$</span></p>
<p>The book says the claim is obvious but I can't find a shorter way to show this.</p>

CC BY-SA 4.0
2021-11-01T11:56:40.073Z
2021-11-01T11:56:40.073Z
andrew
<p>I'm currently working through Nisan's <em>Algorithmic Game Theory</em>, Chapter 9 (Introduction to Mechanism Design). A part of the proof for the Gibbard-Satterthwaite Theorem is given as &quot;obvious,&quot; but I can't seem to work out why. I'll provide some definitions first:</p>
<p>Let <span class="math-container">$A$</span> be a set of alternatives ('candidates') and let there be a set of voters <span class="math-container">$1,\dots,n$</span>. Each voter <span class="math-container">$i$</span> has some total preference ordering <span class="math-container">$\prec_i$</span> on <span class="math-container">$A$</span>. The set of all total orders on <span class="math-container">$A$</span> is denoted by <span class="math-container">$L$</span>.</p>
<p>A <strong>social welfare function</strong> <span class="math-container">$F:L^n\to L$</span> is a function from the preferences <span class="math-container">$(\prec_1,\dots,\prec_n)$</span> of the voters to a single choice preference <span class="math-container">$\prec$</span>.</p>
<p>A social welfare function <span class="math-container">$F:L^n\to L$</span> is <strong>dictatorship</strong> if there is a voter <span class="math-container">$i$</span> such that for all <span class="math-container">$\prec_1,\dots,\prec_n\in L$</span> we have <span class="math-container">$F(\prec_1,\dots,\prec_n)=\prec_i$</span>.</p>
<p>A <strong>social choice function</strong> <span class="math-container">$f:L^n\to A$</span> is a function from the preferences of the voters to a single alternative.</p>
<p>A social choice function <span class="math-container">$f:L^n\to A$</span> is a <strong>dictatorship</strong> if there is a voter <span class="math-container">$i$</span> such that, for all <span class="math-container">$\prec_1,\dots,\prec_n\in L$</span>, we have <span class="math-container">$f(\prec_1,\dots,\prec_n)=a$</span> where <span class="math-container">$a$</span> is at the top of <span class="math-container">$\prec_i$</span>.</p>
<p>A social choice function <span class="math-container">$f:L^n\to A$</span> is <strong>incentive compatible</strong> if, for all <span class="math-container">$\prec_1,\dots,\prec_n\in L$</span> and for any <span class="math-container">$\prec_i'\in L$</span> we have that
<span class="math-container">$$
a=f(\prec_1,\dots,\prec_n)\neq f(\prec_1,\dots,\prec_i',\dots,\prec_n)=a'
$$</span>
implies
<span class="math-container">$$
a\prec'_ia'\qquad\text{and}\qquad a'\prec_i a.
$$</span>
[Intuitively this means that voter <span class="math-container">$i$</span> cannot strategically misrepresent their true preferences and obtain a better outcome.]</p>
<p>Given a preference <span class="math-container">$\prec$</span> and a subset <span class="math-container">$B\subset A$</span>, the notation <span class="math-container">$\prec^B$</span> denotes a new preference obtained by moving everything in <span class="math-container">$B$</span> to the top of <span class="math-container">$\prec$</span>, while preserving the relative preferences of alternatives in <span class="math-container">$B$</span>. For instance, if <span class="math-container">$A=\{a,b,c,d,e\}$</span> and <span class="math-container">$B=\{b,c\}$</span> and <span class="math-container">$a\prec c\prec d\prec b\prec e$</span> then <span class="math-container">$a\prec^Bd\prec^Be\prec^Bc\prec^Bb$</span>.</p>
<p>A social choice function <span class="math-container">$f$</span> onto <span class="math-container">$A$</span> can be <strong>extended</strong> into a social welfare function <span class="math-container">$F$</span> via
<span class="math-container">$$
a\prec b\iff f(\prec_1^{\{a,b\}},\dots,\prec_n^{\{a,b\}})=b,
$$</span>
where <span class="math-container">$\prec=F(\prec_1,\dots,\prec_n)$</span>.</p>
<p>Finally, here is the 'obvious' claim:</p>
<p><strong>Claim.</strong> If <span class="math-container">$f$</span> is an incentive compatible social choice function <span class="math-container">$f$</span> onto <span class="math-container">$A$</span> and <span class="math-container">$f$</span> is not a dictatorship, then the extension <span class="math-container">$F$</span> is also not a dictatorship.</p>
<p>What I've done already: I've been able to show that the extension <span class="math-container">$F$</span> is a well-defined social welfare function (that is, <span class="math-container">$F$</span> is antisymmetric and transitive). I'm trying to show the contrapositive of the claim. Say <span class="math-container">$F$</span> is dictatorial in voter <span class="math-container">$i$</span>, so that <span class="math-container">$F(\prec_1,\dots,\prec_n)=\prec_i$</span>. I want to show that <span class="math-container">$f$</span> is also dictatorial in voter <span class="math-container">$i$</span>. Let's say <span class="math-container">$\prec_i$</span> ranks <span class="math-container">$a$</span> at the top. By definition of <span class="math-container">$F$</span> as an extension of <span class="math-container">$f$</span>, this means
<span class="math-container">$$
b\prec_i a\implies f(\prec_1^{\{a,b\}},\dots,\prec_n^{\{a,b\}})=a.
$$</span>
But what I need is that <span class="math-container">$f(\prec_1,\dots,\prec_n)=a$</span>. It seems like incentive compatibility is the key thing here - perhaps I can somehow show that, by sequentially changing each <span class="math-container">$\prec_j^{\{a,b\}}$</span> to <span class="math-container">$\prec_j$</span>, then <span class="math-container">$f$</span> is unchanged after each step. However it's unclear to me how to proceed.</p>
<p>Any help would be appreciated, thank you.</p>

CC BY-SA 4.0
2021-11-01T00:36:33.373Z
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?
Walrasian Auctioneer
CC BY-SA 4.0
2021-11-01T02:19:28.903Z
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.
andrew
<microeconomics><preferences><choice-theory><social-choice><voting>
Part of proof of Gibbard-Satterthwaite Theorem
andrew
# Part of proof of Gibbard-Satterthwaite Theorem

(Asked by: username_0 on 2021-10-31)

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.

**Tags:** microeconomics, preferences, choice-theory, social-choice, voting
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_0 on 2021-11-01. Score: 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.


---

