# Invariance of strategy-proof social choice function when peaks are made close from solution

A question emerging from reading Schummer, J., & Vohra, R. V. (2002). Strategy-proof Location on a Network. Journal of Economic Theory, 104(2), 405–428.

The setting is as follows:

• A finite set of agents $N$ indexed by $i=1,...,n$.
• A network represented by a graph $G$ on which the decision maker must decide the location of a facility, taking individual preferences into account.
• A graph is a closed, connected subset of some euclidean space, $G\subseteq \mathbb{R}^k$, for $k\geq 1$. $G$ is composed of the union of curves of finite length. Curves are called "edges" and each two extremities are called "vertex". In this context, the set of possible locations $G$ is called the set of alternatives.

EDIT : Schummer and Vohra actually impose that graphs be "the union of a finite number of (closed) curves of finite length". This is the point that I missed and rules out the kind of counter examples that I proposed (see below).

• A path between $x,y \in G$ is a minimal connected subset of $G$ containing $x$ and $y$. The distance between $x$ and $y$, $d(x,y)$ is the minimal path joining the two points.
• Each agent $i$ has a complete preferences relation over the set of alternatives represented by the utility function $u_i : G \rightarrow \mathbb{R}$. A preference profile is denoted $U^n=\{u_1,...,u_n\}$. We consider single-peaked preferences represented by the utility function $u_i(x) = -d(p_i,x)$, where $p_i$ is the peak of agent $i$'s preferences. Let $\mathcal{U}^{SP}$ be the domain of single peak preference profiles. We denote a peak profile $P^n=(p_1,...,p_n)$ and $\mathcal{P}$ the domain of peak profiles.
• We look for social choice rule (SCR), that is a function $f : \mathcal{U}^{SP}\rightarrow G$ associating every preference profile with one of the feasible alternatives. Given the characterization of the utility function, for any SCR there exists an equivalent SCR with $\mathcal{P}$ as domain $f : \mathcal{P}\rightarrow X$.
• The SCR are required to be onto (for every alternative $x\in G$ there exists a profile of $P$ such that $f(P)=x$) and to statisfy strategy-proofness:

I have a problem with Lemma 1 in the paper, which states that if $f$ satisfies strategy-proofness and $f(p)=x$ then $f(p_i',p_{-i})=x$ if $p_i'$ is made sufficiently close from $x$.

I am not sure I get how $d(p_i , x) \leq d( p_i , y)$ and $d(p_i,y)\leq d(p_i,x)$ lead to the desired result. This is clear on a line (a very intuitive proof can be found in Border, K., & Jordan, J. (1983). Straightforward elections, unanimity and phantom voters. The Review of Economic Studies, 50(1), 153–170. Retrieved from http://restud.oxfordjournals.org/content/50/1/153.short). But here we are in a multidimensional graph ($G \subseteq \mathbb{R}^k$). Can't we have the following kind of counter-examples:

No matter how small $\epsilon>0$ is made, couldn't we always chose one of the $p_i'\in[p_i,x]$ with $d(p_i',x)<\epsilon$ and have the graph be as in the picture such that strategy-proofness is preserved but $f(p_i',p_{-i})\neq x$?

Does anyone see what I am missing?

• This looks interesting -- I'm too tired now, but I'll look into it tomorrow... – joriki Apr 30 '13 at 0:03

I think you're right that this is a counterexample. $f(p_i',p_{-i})$ could be given by $y^k$ if $p_i'$ is on the $k$-th upward leg or if the $k$-th upward leg is the first one to the right of $p_i'$. You'd need infinitely many upward legs that accumulate at $x$, but nothing in your description of the setting precludes that. Perhaps the "union of curves of finite length" was intended to be restricted to a union of finitely many curves of finite length.
More generally, a social choice rule is strategy-proof if for given $p_{-i}$ there is a set $S$ such that $f(p_i',p_{-i})$ is a point of $S$ closest to $p_i'$. If $S$ accumulates at $x$ in a suitable way, this yields a counterexample. In your case, $S$ comprises $x$ and the $y^k$.