Classic result in social choice theory

angiland wrote: Classic result in social choice theory Hi angiland, What is it the Classic problem??

It's called Mc Garvey's theorem

angiland wrote: It's called Mc Garvey's theorem could you explain what exactly is Mc Garvey's theorem?

Anyone willing to solve this one?

muriloogps wrote: Anyone willing to solve this one? There's a solution using induction, which I believe is pretty long. Here's another one without induction: Let $G$ be an arbitrary graph with $1395$ vertices. In each step, we set a few number of votes, so that the arrow from candidate $U$ to $V$ is formed in the graph. Here's what we do: If the arrow is directed from $U$ to $V$, then we form $2\times(1395-2)!$ votes, in $1393!$ votes, $U$ and $V$ are the $1st$ and $2nd$ candidates in order of priority, and in the other $1393$ candidates appear in every $1393!$ possible order of priorities. And the other $1393!$ votes, $U,V$ are the $2$ last candidates and in the other $1393$ candidates appear in every $1393!$ possible order of priorities. In these votes, $U$ is always at a higher level of priority than $V$. and any two candidates other than $U,V$ have the same number of votes (which means if $i$ is at a higher level of priority than $j$ in $k$ votes, then $j$ is also at a higher level of priority than $i$ in exactly $k$ votes) Also, $U,V$ are at a higher level of priority than any other candidates in $1393!$ votes, and at a lower level in the other $1393!$ votes. So the only difference in votes, appears along $U,V$ and the rest of the graph is the same. We can do the same thing for any other arrow in the $G$. So the answer of the problem is Yes.

We prove the following more general problem via induction on $n$. For any graph on $n$ vertices we can give order to $n!$ voters so that the graph is generated. The base case $n=2$ is trivial.Assume that the claim is true for $n$ and we are going to prove it for $n+1$.Every time we delete a vertex and apply the inductive hypopeties to the rest and put that vertex in the end of the priority of each $n!$ voters.We do this for each vertex exactly once.Now we have $(n+1)!$ voters and it is obvious that the graph is generated.So we are done with the inductive step.

Use strong induction : we can have every situations for our graph and on lists there exist someone who is coming first and end in some lists . It's easy to check for $ n=3 $ . suppose that it's true for $ n-1 $ , get an arbitrary graph for $n$ and get one of it's vertexes $ a $ .in the graph on the else get $b$ who is both at first and at end of some lists , Let them ( that lists with special place for $ b $ )$ X_1 , X_2 $ . get $A_1$ set of lists for this graph ( which don't have $ a$ ) Now get $ b$ and look at the else , get $A_2$ set of lists of this graph . if $B \in A_2$ ($B$ is a list ) get the new lists $ (b , B) , (B , b) $ instead of that , if $C \in A_1$ and $ C \neq X_1,X_2 $ , get the new list $ (a , C) , (C , a) $ instead of that , if $b$ is at first in $ X_1$ and at end in $X_2$ , if $(a . to . b)$ get $ (a , b , extra . of . X_1) , (extra . of . X_2 , a , b ) $ and if $(b . to . a)$ get $(b , a , extra . of . X_1) , (extra . of . X_2 , b , a)$ It's easy to check that it's true for $n$ , $\blacksquare$

Is number of voters fixed? Or we can change it?