Dodgson's method: Difference between revisions

← Older edit

Dodgson's method (view source)

Revision as of 14:06, 25 August 2020

1,077 bytes added , 3 years ago

m

Fishburn's variant can be computed in polytime

VisualWikitext

Kristomun

1,206

edits

Revision as of 11:56, 25 August 2020 (view source) Kristomun (talk \| contribs) (Provide some information about Dodgson's method) Tag: Visual edit: Switched ← Older edit		Latest revision as of 14:06, 25 August 2020 (view source) Kristomun (talk \| contribs) m (Fishburn's variant can be computed in polytime) Tag: Visual edit: Switched
(3 intermediate revisions by the same user not shown)
Line 1: Dodgson's method is a Condorcet method that ranks a candidate X according to the number of times adjacent candidates have to be swapped on ~~some~~a ~~provided~~ballot (not necessarily the same ballot each time) to make X the Condorcet winner. The candidate with the least number of necessary swaps wins. If X is the Condorcet winner, the number of swaps is zero, so the method passes Condorcet. However, determining the winner in the general case is complete for parallel access to NP,<ref>{{Cite journal\|last=Hemaspaandra\|first=Edith\|last2=Hemaspaandra\|first2=Lane A.\|last3=Rothe\|first3=Jörg\|date=1997\|editor-last=Degano\|editor-first=Pierpaolo\|editor2-last=Gorrieri\|editor2-first=Roberto\|editor3-last=Marchetti-Spaccamela\|editor3-first=Alberto\|title=Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP\|url=https://arxiv.org/abs/cs/9907036\|journal=Automata, Languages and Programming\|series=Lecture Notes in Computer Science\|language=en\|location=Berlin, Heidelberg\|publisher=Springer\|volume=\|pages=214–224\|doi=10.1007/3-540-63165-8_179\|isbn=978-3-540-69194-5\|via=}}</ref> and thus NP-hard. Dodgson's method furthermore fails the [[homogeneity criterion]]:<ref>{{Cite journal\|last=Fishburn\|first=Peter C.\|date=1977-11-01\|title=Condorcet Social Choice Functions\|url=https://epubs.siam.org/doi/abs/10.1137/0133030\|journal=SIAM Journal on Applied Mathematics\|volume=33\|issue=3\|pages=477\|doi=10.1137/0133030\|issn=0036-1399\|via=}}</ref> an election with 100 voters may return a different result to an election with 10 voters, even if the relative size of the different factions is the same. For more information, see [[w:Dodgson's method\|Dodgson's method on Wikipedia]]. ==Criterion compliances== Dodgson's method passes the Condorcet criterion. It fails the [[independence of clones criterion]],<ref>{{Cite journal\|last=Brandt\|first=Felix\|date=2009\|title=Some Remarks on Dodgson's Voting Rule\|url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.149.5624&rep=rep1&type=pdf\|journal=Mathematical Logic Quarterly\|volume=55\|issue=4\|pages=460–463\|doi=10.1002/malq.200810017\|issn=1521-3870\|via=}}</ref> the [[Smith criterion]], the [[monotonicity criterion]], and also fails the [[homogeneity criterion]]:<ref name="PCFishburn">{{Cite journal\|last=Fishburn\|first=Peter C.\|date=1977-11-01\|title=Condorcet Social Choice Functions\|url=https://epubs.siam.org/doi/abs/10.1137/0133030\|journal=SIAM Journal on Applied Mathematics\|volume=33\|issue=3\|pages=477-479\|doi=10.1137/0133030\|issn=0036-1399\|via=}}</ref> an election with 100 voters may return a different result to an election with 10 voters, even if the relative size of the factions is the same. P. C. Fishburn proposed a variant that passes homogeneity<ref name="PCFishburn" /> and where the winner can be found in polynomial time,<ref>{{Cite journal\|last=Rothe\|first=Jörg\|last2=Spakowski\|first2=Holger\|last3=Vogel\|first3=Jörg\|date=2003-08-01\|title=Exact Complexity of the Winner Problem for Young Elections\|url=https://arxiv.org/pdf/cs/0112021\|journal=Theory of Computing Systems\|language=en\|volume=36\|issue=4\|pages=375–386\|doi=10.1007/s00224-002-1093-z\|issn=1433-0490\|via=}}</ref> but the variant fails the other three criteria mentioned above. ==References== <references /> [[Category:Condorcet methods]]