Allocation Problem

This is a problem of choosing the best position

  • to open a new shop
  • etc

In Game Theory this problem is known as the Median Voter Theorem.


The Median Voter Theorem

2 Candidates

Suppose we have two candidates $s_1$ and $s_2$

  • each candidate thinks "what is the best political position to take so the majority vote for me?"
  • so suppose the candidates put themselves somewhere between 0 and 1 (extreme left vs extreme right)
    median-voter-1.png
  • assumptions:
    • voters are distributed uniformly
    • voters vote for the candidate that is closest to their opinion
    • median-voter-2.png


Utilities

  • with this assumption we use the following utility functions:
    • $u_1(s_1, s_2) = \cfrac{s_1 + s_2}{2}$
    • $u_2(s_1, s_2) = 1 - u_1(s_1, s_2) = 1 - \cfrac{s_1 + s_2}{2}$ - complimentary part of $u_1$


So there can be the following scenarios

  • $s_1 < s_2$
  • both take the same position

Case 1: $s_1 < s_2$

  • not a Nash Equilibrium
  • median-voter-3.png
  • both players want to move: $p_1$ wants to move right and $p_2$ wants to move left
  • so there exists another better strategy:
    • $u_1(s_1 + \epsilon, s_2) > u_1(s_1, s_2)$
    • $p_1$ just moves a little bit to the right and this way gets more votes


Case 2: $s_1 = s_2 < 0.5$

  • this is not a Nash Equilibrium either
  • median-voter-4.png
  • since $s_1 = s_2$ they have the same utilities (the voters choose at random from whom to vote)
    • $u_1(s_1, s_2) = u_2(s_1, s_2)$
  • but this time again there's an incentive to deviate:
    • $u_1(s_1 + \epsilon, s_2) > u_1(s_1, s_2)$
  • median-voter-5.png


Case 3: $s_1 = s_2 = 0.5$

  • this is a Nash Equilibrium!
  • median-voter-6-ne.png
  • no one has an incentive to deviate:
    • if somebody moves, he gets lower payoff
    • $u_1(s_1, s_2) > u_1(s_1 - \epsilon, s_2)$


3 Candidates

But there is no Nash Equilibria for three candidates

Consider this

  • there are 3 candidates $\{a, b, c\}$ who position themselves at the scale [0, 1]
  • the positions of the candidates are $s_a, s_b, s_c$
  • voters vote to the closest candidate to them
  • median-voter3-1.png

We suppose (without loss of generality) that

  • $s_a \leqslant s_b \leqslant s_c$
  • median-voter3-2.png
  • let $u_a, u_b, u_c$ be the utility functions of $a, b, c$ respectively

Utility functions

$s_a < s_b < s_c$ median-voter3-cases-1-alldif.png $\left\{\begin{matrix}

u^{(1)}_a(s_a, s_b, s_c) = \cfrac{s_a + s_b}{2} \\ u^{(1)}_b(s_a, s_b, s_c) = 1 - \cfrac{s_b + s_c}{2} \\ u^{(1)}_c(s_a, s_b, s_c) = \cfrac{s_b + s_c}{2} - \cfrac{s_a + s_b}{2} \\ \end{matrix}\right.$

$a$ may deviate: $u_a(s_a + \epsilon, s_b, s_c) > u_a(s_a, s_b, s_c)$
$s_a < s_b = s_c$ median-voter3-cases-2-beqc.png $\left\{\begin{matrix}

u^{(2)}_a(s_a, s_b, s_c) = \cfrac{s_a + s_b}{2} \\ u^{(2)}_b(s_a, s_b, s_c) = \cfrac{1 - \cfrac{s_a + s_b}{2}}{2} \\ u^{(2)}_c(s_a, s_b, s_c) = u^{(2)}_b(s_a, s_b, s_c) \\ \end{matrix}\right.$

$a$ may deviate: $u_a(s_a + \epsilon, s_b, s_c) > u_a(s_a, s_b, s_c)$
$s_a = s_b < s_c$ median-voter3-cases-3-aeqb.png $\left\{\begin{matrix}

u^{(3)}_a(s_a, s_b, s_c) = \cfrac{s_b + s_c}{2 \cdot 2} \\ u^{(3)}_b(s_a, s_b, s_c) = u^{(3)}_a(s_a, s_b, s_c) \\ u^{(3)}_c(s_a, s_b, s_c) = 1 - \cfrac{s_b + s_c}{2} \\ \end{matrix}\right.$

$c$ may deviate: $u_c(s_a, s_b, s_c - \epsilon) > u_c(s_a, s_b, s_c)$
$s_a = s_b = s_c \ne 0.5$ median-voter3-cases-5-shared-2.png $\left\{\begin{matrix}

u^{(4)}_a(s_a, s_b, s_c) = \cfrac{1}{3} \\ u^{(4)}_b(s_a, s_b, s_c) = \cfrac{1}{3} \\ u^{(4)}_c(s_a, s_b, s_c) = \cfrac{1}{3} \\ \end{matrix}\right.$

$a$ may deviate: $u_a(s_a + \epsilon, s_b, s_c) > u_a(s_a, s_b, s_c)$
$s_a = s_b = s_c = 0.5$ median-voter3-cases-4-shared-1.png $\left\{\begin{matrix}

u^{(4)}_a(s_a, s_b, s_c) = \cfrac{1}{3} \\ u^{(4)}_b(s_a, s_b, s_c) = \cfrac{1}{3} \\ u^{(4)}_c(s_a, s_b, s_c) = \cfrac{1}{3} \\ \end{matrix}\right.$

$a$ may deviate: $u_a(s_a + \epsilon, s_b, s_c) > u_a(s_a, s_b, s_c)$

So in all cases there is somebody who wants to deviate:

  • No Nash Equilibria


Applications

This is the allocation problem:

  • suppose we want to find a location for a new store
  • clients that are closer will go to this store
  • allocation-problem.png
  • so they put it in the center
  • this is the reason why sometimes big grocery stores are located close to each other


Sources