 Computing Most Equitable Voting RulesLirong Xia Abstract: How to design fair and (computationally) efficient voting rules is a central challenge in Computational Social Choice. In this paper, we aim at designing efficient algorithms for computing most equitable rules for large classes of preferences and decisions, which optimally satisfy two fundamental fairness/equity axioms: anonymity (every voter being treated equally) and neutrality (every alternative being treated equally). By revealing a natural connection to the graph isomorphism problem and leveraging recent breakthroughs by Babai [2019], we design quasipolynomial-time algorithms that compute most equitable rules with verifications, which also compute verifications about whether anonymity and neutrality are satisfied at the input profile. Further extending this approach, we propose the canonical-labeling tie-breaking, which runs in quasipolynomial-time and optimally breaks ties to preserve anonymity and neutrality. As for the complexity lower bound, we prove that even computing verifications for most equitable rules is GI-complete (i.e., as hard as the graph isomorphism problem), and sometimes GA-complete (i.e., as hard as the graph automorphism problem), for many commonly studied combinations of preferences and decisions. To the best of our knowledge, these are the first problems in computational social choice that are known to be complete in the class GI or GA. Date: 2024-10 Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2410.04179 Access Statistics for this paper More papers in Papers from arXiv.org |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.