|
Dodgson's Method
Dodgson's method is an electoral system proposed by the author, mathematician and logician Charles Dodgson, better known as Lewis Carroll. The method is to extend the Condorcet method by swapping candidates until a Condorcet winner is found. The winner is the candidate which requires the minimum number of swaps. Dodgson proposed this voting scheme in his 1876 work "A method of taking votes on more than two issues". Given an integer ''k'' and an election, it is NP-complete to determine whether a candidate can become a Condorcet winner with fewer than ''k'' swaps. Description In Dodgson's method, each voter submits an ordered list of all candidates according to their own preference (from best to worst). The winner is defined to be the candidate for whom we need to perform the minimum number of pairwise swaps in each ballot (added over all candidates) before they become a Condorcet winner. In particular, if there is already a Condorcet winner, they win the election. In short, we must ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Electoral System
An electoral system or voting system is a set of rules that determine how elections and Referendum, referendums are conducted and how their results are determined. Electoral systems are used in politics to elect governments, while non-political elections may take place in business, Nonprofit organization, non-profit organisations and informal organisations. These rules govern all aspects of the voting process: when elections occur, suffrage, who is allowed to vote, who can stand as a candidate, voting method, how ballots are marked and cast, how the ballots are counted, how votes translate into the election outcome, limits on campaign finance, campaign spending, and other factors that can affect the result. Political electoral systems are defined by constitutions and electoral laws, are typically conducted by election commissions, and can use multiple types of elections for different offices. Some electoral systems elect a single winner to a unique position, such as prime ministe ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lewis Carroll
Charles Lutwidge Dodgson (; 27 January 1832 – 14 January 1898), better known by his pen name Lewis Carroll, was an English author, poet and mathematician. His most notable works are ''Alice's Adventures in Wonderland'' (1865) and its sequel ''Through the Looking-Glass'' (1871). He was noted for his facility with word play, logic, and fantasy. His poems ''Jabberwocky'' (1871) and ''The Hunting of the Snark'' (1876) are classified in the genre of literary nonsense. Carroll came from a family of high-church Anglicanism, Anglicans, and developed a long relationship with Christ Church, Oxford, where he lived for most of his life as a scholar and teacher. Alice Liddell, the daughter of Christ Church's dean Henry Liddell, is widely identified as the original inspiration for ''Alice in Wonderland'', though Carroll always denied this. An avid puzzler, Carroll created the word ladder puzzle (which he then called "Doublets"), which he published in his weekly column for ''Vanity Fair ( ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Condorcet Method
A Condorcet method (; ) is an election method that elects the candidate who wins a majority of the vote in every head-to-head election against each of the other candidates, that is, a candidate preferred by more voters than any others, whenever there is such a candidate. A candidate with this property, the ''pairwise champion'' or ''beats-all winner'', is formally called the ''Condorcet winner''. The head-to-head elections need not be done separately; a voter's choice within any given pair can be determined from the ranking. Some elections may not yield a Condorcet winner because voter preferences may be cyclic—that is, it is possible (but rare) that every candidate has an opponent that defeats them in a two-candidate contest.(This is similar to the game rock paper scissors, where each hand shape wins against one opponent and loses to another one). The possibility of such cyclic preferences is known as the Condorcet paradox. However, a smallest group of candidates that beat al ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP-complete
In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions. # the problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified. The name "NP-complete" is short for "nondeterministic polynomial-time complete". In this name, "nondeterministic" refers to nondeterministic Turing machines, a way of mathematically formalizing the idea of a brute-force search algorithm. Polynomial time refers to an amount of time that is considered "quick" for a de ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Condorcet Winner
An electoral system satisfies the Condorcet winner criterion () if it always chooses the Condorcet winner when one exists. The candidate who wins a majority of the vote in every head-to-head election against each of the other candidatesthat is, a candidate preferred by more voters than any othersis the Condorcet winner, although Condorcet winners do not exist in all cases. It is sometimes simply referred to as the "Condorcet criterion", though it is very different from the "Condorcet loser criterion". Any voting method conforming to the Condorcet winner criterion is known as a Condorcet method. The Condorcet winner is the person who would win a two-candidate election against each of the other candidates in a plurality vote. For a set of candidates, the Condorcet winner is always the same regardless of the voting system in question, and can be discovered by using pairwise counting on voters' ranked preferences. A Condorcet winner will not always exist in a given set of votes, which ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kendall Tau Distance
The Kendall tau rank distance is a metric (distance function) that counts the number of pairwise disagreements between two ranking lists. The larger the distance, the more dissimilar the two lists are. Kendall tau distance is also called bubble-sort distance since it is equivalent to the number of swaps that the bubble sort algorithm would take to place one list in the same order as the other list. The Kendall tau distance was created by Maurice Kendall. Definition The Kendall tau ranking distance between two lists \tau_1 and \tau_2 is : K_d(\tau_1, \tau_2) = , \, . where * \tau_1(i) and \tau_2(i) are the rankings of the element i in \tau_1 and \tau_2 respectively. K_d(\tau_1,\tau_2) will be equal to 0 if the two lists are identical and \frac n (n-1) (where n is the list size) if one list is the reverse of the other. Kendall tau distance may also be defined as : K_d(\tau_1,\tau_2) = \sum_ \bar_(\tau_1,\tau_2) where * ''P'' is the set of unordered pairs of distinct element ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP-hardness
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard problem is the subset sum problem. A more precise specification is: a problem ''H'' is NP-hard when every problem ''L'' in NP can be reduced in polynomial time to ''H''; that is, assuming a solution for ''H'' takes 1 unit time, ''H''s solution can be used to solve ''L'' in polynomial time. As a consequence, finding a polynomial time algorithm to solve any NP-hard problem would give polynomial time algorithms for all the problems in NP. As it is suspected that P≠NP, it is unlikely that such an algorithm exists. It is suspected that there are no polynomial-time algorithms for NP-hard problems, but that has not been proven. Moreover, the class P, in which all problems can be solved in polynomial time, is contained in the NP class. Defi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Exact Cover
In the mathematical field of combinatorics, given a collection of subsets of a set , an exact cover is a subcollection of such that each element in is contained in ''exactly one'' subset in . In other words, is a partition of consisting of subsets contained in . One says that each element in is covered by exactly one subset in . An exact cover is a kind of cover. In computer science, the exact cover problem is a decision problem to determine if an exact cover exists. The exact cover problem is NP-complete This book is a classic, developing the theory, then cataloguing ''many'' NP-Complete problems. and is one of Karp's 21 NP-complete problems. It is NP-complete even when each subset in contains exactly three elements; this restricted problem is known as exact cover by 3-sets, often abbreviated X3C. The exact cover problem is a kind of constraint satisfaction problem. An exact cover problem can be represented by an incidence matrix or a bipartite graph. Knuth's Algorith ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Electoral Systems
An electoral system or voting system is a set of rules that determine how elections and referendums are conducted and how their results are determined. Electoral systems are used in politics to elect governments, while non-political elections may take place in business, non-profit organisations and informal organisations. These rules govern all aspects of the voting process: when elections occur, who is allowed to vote, who can stand as a candidate, how ballots are marked and cast, how the ballots are counted, how votes translate into the election outcome, limits on campaign spending, and other factors that can affect the result. Political electoral systems are defined by constitutions and electoral laws, are typically conducted by election commissions, and can use multiple types of elections for different offices. Some electoral systems elect a single winner to a unique position, such as prime minister, president or governor, while others elect multiple winners, such as memb ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
