Voting paradoxes and diagraphs realizations

Research output: Contribution to journalArticle

9 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)126-135
Number of pages10
JournalAdvances in Applied Mathematics
Volume29
Issue number1
DOIs
StatePublished - Jul 1 2002
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Applied Mathematics

Fingerprint Dive into the research topics of 'Voting paradoxes and diagraphs realizations'. Together they form a unique fingerprint.

  • Cite this