The Strong Maximum Circulation Algorithm: A New Method for Aggregating Preference Rankings

Nathan Atkinson, Scott C. Ganz, Dorit S. Hochbaum and James B. Orlin

Papers from arXiv.org

Abstract: We present a new optimization-based method for aggregating preferences in settings where each voter expresses preferences over pairs of alternatives. Our approach to identifying a consensus partial order is motivated by the observation that collections of votes that form a cycle can be treated as collective ties. Our approach then removes unions of cycles of votes, or circulations, from the vote graph and determines aggregate preferences from the remainder. Specifically, we study the removal of maximal circulations attained by any union of cycles the removal of which leaves an acyclic graph. We introduce the strong maximum circulation, the removal of which guarantees a unique outcome in terms of the induced partial order, called the strong partial order. The strong maximum circulation also satisfies strong complementary slackness conditions, and is shown to be solved efficiently as a network flow problem. We further establish the relationship between the dual of the maximum circulation problem and Kemeny's method, a popular optimization-based approach for preference aggregation. We also show that identifying a minimum maximal circulation -- i.e., a maximal circulation containing the smallest number of votes -- is an NP-hard problem. Further an instance of the minimum maximal circulation may have multiple optimal solutions whose removal results in conflicting partial orders.

Date: 2023-07, Revised 2025-01
New Economics Papers: this item is included in nep-mic
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2307.15702 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2307.15702

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().