Majority vote of total orders - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T20:33:30Z http://mathoverflow.net/feeds/question/119240 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/119240/majority-vote-of-total-orders Majority vote of total orders aorq 2013-01-18T07:07:03Z 2013-01-26T02:02:11Z <p>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$.</p> <ol> <li><p>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?</p></li> <li><p>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.</p></li> <li><p>What can be said about the computational problem of determining the smallest $k$ that can represent a given tournament or digraph?</p></li> </ol> <p>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.</p> http://mathoverflow.net/questions/119240/majority-vote-of-total-orders/119248#119248 Answer by Ben Barber for Majority vote of total orders Ben Barber 2013-01-18T10:01:43Z 2013-01-18T10:01:43Z <p>Every possible tournament on $n$ vertices is realisable with polynomially many voters. <a href="http://arxiv.org/abs/1211.0515" rel="nofollow">This recent paper</a> cites D. C. McGarvey, <em>A theorem on the construction of voting paradoxes</em>, Econometrica <strong>21</strong> (1953), 608-610.</p> http://mathoverflow.net/questions/119240/majority-vote-of-total-orders/119249#119249 Answer by Zsbán Ambrus for Majority vote of total orders Zsbán Ambrus 2013-01-18T10:02:33Z 2013-01-18T10:02:33Z <p>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).</p> <blockquote> <p>You can get any tournament as the majority vote of some number of linear orders.</p> </blockquote> <p>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. </p> <p>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$.</p> <p>Update: it seems Ben Barber was a bit faster than me to post an answer that proves a bit more than this one. </p> http://mathoverflow.net/questions/119240/majority-vote-of-total-orders/119252#119252 Answer by domotorp for Majority vote of total orders domotorp 2013-01-18T10:55:39Z 2013-01-18T10:55:39Z <p>These tournaments are called majority tournaments and are studied in several papers, e.g.</p> <p><a href="http://www.math.dartmouth.edu/~pw/papers/dice.pdf" rel="nofollow">http://www.math.dartmouth.edu/~pw/papers/dice.pdf</a></p> <p><a href="http://arxiv.org/abs/1109.6172" rel="nofollow">http://arxiv.org/abs/1109.6172</a></p> http://mathoverflow.net/questions/119240/majority-vote-of-total-orders/119903#119903 Answer by Ilhee Kim for Majority vote of total orders Ilhee Kim 2013-01-26T02:02:11Z 2013-01-26T02:02:11Z <p>For $k=3$, the following paper shows an example of a non-3-majority tournament with 8 vertices. </p> <p><a href="http://www2.isye.gatech.edu/~ctovey/publications/papers/voting__19_may_08.pdf" rel="nofollow">http://www2.isye.gatech.edu/~ctovey/publications/papers/voting__19_may_08.pdf</a></p> <p>A few years ago, I checked that every tournament with 7 vertices (even the Paley tournament) is 3-majority by using a computer.</p>