Kemeny–Young method: Difference between revisions

Line 46:

So the final ranking is B>C>A, with B winning.

== Approximate methods ==

Some other voting methods have the property that the social order they return has a Kemeny distance at most k times the optimum (the one that Kemeny finds).<ref>{{cite book|

last1 = Claire|

first1 = Mathieu|

last2 = Simon|

first2 = Mauras|

title = How to aggregate Top-lists: Approximation algorithms via scores and average ranks|

journal = Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA)|

chapter = |

pages = 2810-2822|

doi = 10.1137/1.9781611975994.171|

url = https://epubs.siam.org/doi/pdf/10.1137/1.9781611975994.171

}}</ref> They do not necessarily pass the same criteria as Kemeny but can be interesting methods in their own right. Some results are:

* The [[Borda count]] is a 5-approximation.

* The [[footrule method]] is a 2-approximation.

* The "best fit" method, which returns the ranked ballot with the least Kemeny distance, is a 2-approximation.

* The random Kwiksort method <ref name="aggregate">{{cite journal|last1 = Ailon|first1 = Nir|last2 = Charikar|first2 = Moses|last3 = Newman|first3 = Alantha|title = Aggregating Inconsistent Information: Ranking and Clustering|year = 2008|publisher = Association for Computing Machinery|location = New York, NY, USA|volume = 55|number = 5|issn = 0004-5411|url = http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.296.8422&rep=rep1&type=pdf|doi = 10.1145/1411509.1411513}}</ref> and its deterministic version CC-Pivot<ref>{{cite journal | last=Zuylen | first=Anke van | last2=Williamson | first2=David P. | title=Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems | journal=Mathematics of Operations Research | publisher=INFORMS | volume=34 | issue=3 | year=2009 | issn=0364765X |eissn=15265471 | jstor=40538434 | pages=594–620 | url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.2691&rep=rep1&type=pdf | access-date=2022-04-25}}</ref> are both 3-approximations.

* Choosing the best order of best fit and Kwiksort is a 6/5-approximation.<ref name="aggregate"/>

== Notes ==