MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

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

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.

-
Are the total orders allowed to occur with multiplicity? Then clearly if a tournament occurs then all subtournaments occur. So there is some list of excluded substructures, and the question is if we can characterize it. But if not then it is not even obvious that this is closed under substructures. – Will Sawin Jan 18 at 8:06
Yes, I'm allowing multiplicity. So I would be interested, for example, in a description of the excluded sub-tournaments for k=3. – aorq Jan 18 at 16:50

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.

-
 I think Gil Kalai proved some generalization of this result, but I'm not sure. – Michael Greinecker Jan 26 at 10:14

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.

-

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

-

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.

-