Improved bounds for computing Kemeny rankings

Vincent Conitzer · Andrew J. Davenport · Jayant Kalagnanam

148 citations0/0 files stored

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Game Theory and Voting Systems Constraint Satisfaction and Optimization Internet Traffic Analysis and Secure E-voting

Abstract

Voting (or rank aggregation) is a general method for aggre-gating the preferences of multiple agents. One voting rule of particular interest is the Kemeny rule, which minimizes the number of cases where the final ranking disagrees with a vote on the order of two alternatives. Unfortunately, Kemeny rankings are NP-hard to compute. Recent work on computing Kemeny rankings has focused on producing good bounds to use in search-based methods. In this paper, we extend on this work by providing various improved bounding techniques. Some of these are based on cycles in the pairwise majority graph, others are based on linear programs. We completely characterize the relative strength of all of these bounds and provide some experimental results.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 148 citations exist upstream.

References

1973Manipulation of Voting Schemes: A General Result 1975Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions 2014Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix 1989Voting schemes for which it can be difficult to tell who won the election 1995Optimal Voting Rules 1997Exact analysis of Dodgson elections 1991The Clarke tax as a consensus mechanism among automated agents 2005Ranking systems

Cited by

2011Experiments with Kemeny ranking: What works when?2009Preference functions that score rankings and maximum likelihood estimation 2013Better Human Computation Through Principled Voting 2012Consensus ranking under the exponential model 2010Making decisions based on the preferences of multiple agents 2009Fixed-parameter algorithms for Kemeny rankings

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.