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

  • $\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$ – Martin Van der Linden May 6 '13 at 21:13

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.