Fine-Grained Complexity and Algorithms for the Schulze Voting Method

• URL: http://arxiv.org/abs/2103.03959v1
• Date: Fri, 5 Mar 2021 22:27:36 GMT
• Title: Fine-Grained Complexity and Algorithms for the Schulze Voting Method
• Authors: Krzysztof Sornat, Virginia Vassilevska Williams, Yinzhan Xu
• Abstract summary: We study computational aspects of a well-known single-winner voting rule called the Schulze method. Our paper is the first to bring fine-grained complexity into the field of computational social choice.
• Score: 9.399840807973545
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study computational aspects of a well-known single-winner voting rule called the Schulze method [Schulze, 2003] which is used broadly in practice. In this method the voters give (weak) ordinal preference ballots which are used to define the weighted majority graph (WMG) of direct comparisons between pairs of candidates. The choice of the winner comes from indirect comparisons in the graph, and more specifically from considering directed paths instead of direct comparisons between candidates. When the input is the WMG, to our knowledge, the fastest algorithm for computing all possible winners in the Schulze method uses a folklore reduction to the All-Pairs Bottleneck Paths (APBP) problem and runs in $O(m^{2.69})$ time, where $m$ is the number of candidates. It is an interesting open question whether this can be improved. Our first result is a combinatorial algorithm with a nearly quadratic running time for computing all possible winners. If the input to the possible winners problem is not the WMG but the preference profile, then constructing the WMG is a bottleneck that increases the running time significantly; in the special case when there are $O(m)$ voters and candidates, the running time becomes $O(m^{2.69})$, or $O(m^{2.5})$ if there is a nearly-linear time algorithm for multiplying dense square matrices. To address this bottleneck, we prove a formal equivalence between the well-studied Dominance Product problem and the problem of computing the WMG. We prove a similar connection between the so called Dominating Pairs problem and the problem of verifying whether a given candidate is a possible winner. Our paper is the first to bring fine-grained complexity into the field of computational social choice. Using it we can identify voting protocols that are unlikely to be practical for large numbers of candidates and/or voters, as their complexity is likely, say at least cubic.

Related papers

• Improving the Computational Efficiency of Adaptive Audits of IRV Elections [54.427049258408424]
  AWAIRE can audit IRV contests with any number of candidates, but the original implementation incurred memory and computation costs that grew superexponentially with the number of candidates. This paper improves the algorithmic implementation of AWAIRE in three ways that make it practical to audit IRV contests with 55 candidates, compared to the previous 6 candidates.
  arXiv  Detail & Related papers  (2024-07-23T13:28:00Z)
• Computing Voting Rules with Elicited Incomplete Votes [11.550634521005968]
  We study voting rules that are computable by querying voters about $t m$ candidates. For scoring rules that are computable with limited-sized queries, we give parameterized upper and lower bounds on the number of such queries.
  arXiv  Detail & Related papers  (2024-02-16T22:17:01Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
  arXiv  Detail & Related papers  (2024-02-09T19:01:48Z)
• Approximation Algorithms for Preference Aggregation Using CP-Nets [3.337244446073836]
  This paper studies the design and analysis of approximation algorithms for aggregating preferences over Conditional Preference Networks (CP-nets) Its focus is on aggregating preferences over so-called emphswaps, for which optimal solutions in general are already known to be of exponential size.
  arXiv  Detail & Related papers  (2023-12-14T17:31:38Z)
• Computing Star Discrepancies with Numerical Black-Box Optimization Algorithms [56.08144272945755]
  We compare 8 popular numerical black-box optimization algorithms on the $L_infty$ star discrepancy problem. We show that all used solvers perform very badly on a large majority of the instances. We suspect that state-of-the-art numerical black-box optimization techniques fail to capture the global structure of the problem.
  arXiv  Detail & Related papers  (2023-06-29T14:57:56Z)
• Accelerating Voting by Quantum Computation [35.03314687289671]
  We propose a quantum-accelerated voting algorithm that can be applied to any anonymous voting rule. Our algorithm outputs the correct winner with high probability in $Thetaleft(fracntextMOVright)$ time.
  arXiv  Detail & Related papers  (2023-01-08T07:29:38Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  We show that our method computes a solution with cost at most $O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$, where $epsilon$ is the privacy guarantee. Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical.
  arXiv  Detail & Related papers  (2022-06-17T09:24:41Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  We consider the problem of combining and learning over a set of adversarial algorithms with the goal of adaptively tracking the best one on the fly. The CORRAL of Agarwal et al. achieves this goal with a regret overhead of order $widetildeO(sqrtd S T)$ where $M$ is the number of base algorithms and $T$ is the time horizon. Motivated by this issue, we propose a new recipe to corral a larger band of bandit algorithms whose regret overhead has only emphlogarithmic dependence on $M$ as long
  arXiv  Detail & Related papers  (2022-02-12T21:55:44Z)
• When Can Liquid Democracy Unveil the Truth? [12.198420431487731]
  We investigate the so-called ODP-problem that has been formulated by Caragiannis and Micha. Under some hypothesis on either the accuracies of voters or the connectivity of the network, we obtain a-time $1/2$-approximation algorithm. This observation proves formally that the connectivity of the social network is a key feature for the efficiency of the liquid democracy paradigm.
  arXiv  Detail & Related papers  (2021-04-05T09:45:14Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  We study the problem of minimizing the population loss given i.i.d. samples from a distribution over convex loss functions. A recent work of Bassily et al. has established the optimal bound on the excess population loss achievable given $n$ samples. We describe two new techniques for deriving convex optimization algorithms both achieving the optimal bound on excess loss and using $O(minn, n2/d)$ gradient computations.
  arXiv  Detail & Related papers  (2020-05-10T19:52:03Z)
• Resolving the Optimal Metric Distortion Conjecture [27.344649091365067]
  We study the following metric distortion problem. There are two finite sets of points, $V$ and $C$, that lie in the same metric space. We propose algorithms that choose a point in $C$ using only these rankings as input.
  arXiv  Detail & Related papers  (2020-04-16T04:13:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.