Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
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 '13 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 '13 at 16:50
add comment

4 Answers

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.

share|improve this answer
    
I think Gil Kalai proved some generalization of this result, but I'm not sure. –  Michael Greinecker Jan 26 '13 at 10:14
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.