Majority vote of total orders

Question

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

1. 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?

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

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

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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.