Majority vote of total orders Fix an odd natural number $k$.  Suppose we have $k$ total orders on the same (finite) set $X$.  Define a tournament on the vertex set $X$ by putting a directed edge $x\rightarrow y$ if a majority of the total orders compare $x > y$.


*

*What tournaments can be obtained this way?  Of course, if $k = 1$, only linearly ordered tournaments are possible.  I am most interested in the case of small $k$.  For example, is there an excluded-substructure characterization of these tournaments?

*What if we make the problem harder and ask whether a given directed graph $G$ can be extended to a tournament $T$ such that $T$ can be obtained in this way?  Again, if $k = 1$, there are various simple characterizations, such as all digraphs that contain no directed cycles.

*What can be said about the computational problem of determining the smallest $k$ that can represent a given tournament or digraph?
I assume, perhaps naively, that this problem already occurs in the literature, perhaps in the theory of voting/social choice, so I would be happy with references instead of solutions if that's easier.
 A: Every possible tournament on $n$ vertices is realisable with polynomially many voters. This recent paper cites D. C. McGarvey, A theorem on the construction of voting paradoxes, Econometrica 21 (1953), 608-610.
A: You say you are interested in small $ k $.  This makes sense, because allowing an arbitrarily large $ k $ makes the question trivial (provided you allow repetition of a linear order with any multiplicity as well).

You can get any tournament as the majority vote of some number of linear orders.

Indeed, suppose you have $ n $ vertices (where $ 3 \le n $) and a tournament on this you want to obtain.  For every arc $ (u, v) $ in the tournament, take all $ (n - 1)! $ linear orders in which $ v $ is greater than $ u $ and they are adjacent so there is no vertex between them.  In these tournaments, any edge other than $ {u, v} $ occurs the same number of times in the two directions.  Gather these linear orders for all edges in the tournament (that's $ n(n-1)(n-1)!/2 $ linear orders), and add any one linear order to make the total odd.  The majority vote of these shall give your tournament.  
Remark.  I don't claim this construction to be optimal, indeed I think instead of the factorial order here, I think that you might be able to choose $ k $ to grow only polynomially in $ n $.
Update: it seems Ben Barber was a bit faster than me to post an answer that proves a bit more than this one. 
A: These tournaments are called majority tournaments and are studied in several papers, e.g.
http://www.math.dartmouth.edu/~pw/papers/dice.pdf
http://arxiv.org/abs/1109.6172
A: For $k=3$, the following paper shows an example of a non-3-majority tournament with 8 vertices. 
http://www2.isye.gatech.edu/~ctovey/publications/papers/voting__19_may_08.pdf
A few years ago, I checked that every tournament with 7 vertices (even the Paley tournament) is 3-majority by using a computer.
