TY - JOUR

T1 - Voting paradoxes and diagraphs realizations

AU - Alon, Noga

N1 - Funding Information:
1 Research supported in part by a USA–Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.

PY - 2002/7

Y1 - 2002/7

N2 - A family of permutations ℱ forms a realization of a directed graph T = (V, E) if for every directed edge uv of T, u precedes v in more than half of the permutations. The quality q(ℱ, T) of the realization is the minimum, over all directed edges uv of T, of the ratio (ℱ(u, v) ℱ(v, u))/ℱ, where ℱ(x, y) is the number of permutations in ℱ in which x precedes y. The study of this quantity is motivated by questions about voting schemes in which each individual has a linear ordering of all candidates, and the individual preferences are combined to decide between any pair of possible candidates by applying the majority vote. It is shown that every simple digraph T on n vertices, with no anti-parallel edges, admits a realization ℱ with quality at least c/ n for some absolute positive constant c, and this is tight up to the constant factor c.

AB - A family of permutations ℱ forms a realization of a directed graph T = (V, E) if for every directed edge uv of T, u precedes v in more than half of the permutations. The quality q(ℱ, T) of the realization is the minimum, over all directed edges uv of T, of the ratio (ℱ(u, v) ℱ(v, u))/ℱ, where ℱ(x, y) is the number of permutations in ℱ in which x precedes y. The study of this quantity is motivated by questions about voting schemes in which each individual has a linear ordering of all candidates, and the individual preferences are combined to decide between any pair of possible candidates by applying the majority vote. It is shown that every simple digraph T on n vertices, with no anti-parallel edges, admits a realization ℱ with quality at least c/ n for some absolute positive constant c, and this is tight up to the constant factor c.

UR - http://www.scopus.com/inward/record.url?scp=0036657895&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036657895&partnerID=8YFLogxK

U2 - 10.1016/S0196-8858(02)00007-6

DO - 10.1016/S0196-8858(02)00007-6

M3 - Article

AN - SCOPUS:0036657895

VL - 29

SP - 126

EP - 135

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

SN - 0196-8858

IS - 1

ER -