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: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$. Lemma 1 and its proof

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:

A conter-example?

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?

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

1 Answer 1


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

  • $\begingroup$ (this comment replace a former one that was mistaken). Thanks for you answer Joriki. You are right in suggesting that the graph is meant to be the union of a FINITE number of curves. That was my mistake. I did not read the paper carefully enough : they consider "A (finite) graph is a closed, connected subset of Euclidean space,that is composed of the union of a FINITE number of (closed) curves of finite length. $\endgroup$ May 6, 2013 at 21:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .