Abstract
This research investigates two significant challenges in computational social choice: the optimal weighted lobbying problem and the winner problem for Dodgson elections. We demonstrate that while optimal lobbying is intractable in terms of parameterized complexity, a greedy algorithm can achieve a logarithmic approximation ratio. This bound is shown to be tight for the greedy approach. Furthermore, we explore the relationship between average-case polynomial time (AvgP) and "frequently self-knowingly correct" algorithms, proving that any problem in AvgP under a uniform distribution can be solved by an algorithm that recognizes its own correctness with high frequency. Finally, we critique the current definitions of junta distributions, showing they are insufficient to guarantee average-case hardness.
Introduction
In the field of computational social choice, many voting systems designed to ensure fairness or representativeness are computationally intractable. This paper addresses the gap between theoretical hardness and practical solvability by examining approximation algorithms and the nature of average-case complexity. Specifically, we focus on the Optimal Weighted Lobbying (OWL) problem and the determination of winners in Dodgson elections.
Optimal Weighted Lobbying (OWL)
The Optimal Weighted Lobbying problem involves a lobbyist attempting to influence the outcome of multiple referenda by paying voters to change their votes. Each voter has an associated cost, and the goal is to achieve a specific outcome across all referenda while minimizing the total expenditure.
Previous research by Christian et al. (2006) established that this problem is W[2]-complete, suggesting it is unlikely to be solved efficiently even for small instances. We propose a greedy algorithm that iteratively selects the most cost-effective voter—defined as the voter who provides the highest number of required vote changes per unit of cost.
Approximation and Tightness
Our analysis reveals that this greedy approach achieves an approximation ratio of $1 + \ln(D_0)$, where $D_0$ represents the total number of vote changes required to reach the desired outcome. This result mirrors the classic approximation ratio for the Set Cover problem. To determine if this ratio could be improved, we constructed a specific election matrix (a "tight example") demonstrating that no greedy algorithm can guarantee a better approximation than the logarithmic bound we identified. This establishes the greedy algorithm as a robust, albeit limited, tool for managing lobbying costs.
Dodgson Winners and Average-Case Complexity
Dodgson's voting system identifies a winner who requires the fewest swaps of adjacent candidates in voters' preference lists to become a Condorcet winner. Determining the Dodgson winner is $P^{NP}_{||}$-complete, making it highly resistant to exact computation.
To address this, researchers often turn to heuristics. Homan and Hemaspaandra (2006) introduced the concept of a "frequently self-knowingly correct" (FSKC) algorithm—one that outputs a correct answer most of the time and, crucially, "knows" when it is correct (outputting a special symbol like "?" when it is uncertain).
The Bridge to AvgP
A major contribution of this work is the formal proof that every distributional problem solvable in polynomial time on average (AvgP) with respect to the uniform distribution possesses an FSKC polynomial-time algorithm. This bridges the gap between average-case complexity theory and the practical application of heuristics in voting. It implies that if a voting problem is "easy on average," we can construct an algorithm that is not only fast but also reliable in its self-assessment of correctness.
Critique of Junta Distributions
Procaccia and Rosenschein (2007) proposed "junta distributions" as a way to model hard instances of voting problems. However, our analysis suggests these definitions are currently too weak. We demonstrate that by concentrating probability weight on a small number of instances, one can satisfy the formal requirements of a junta distribution while leaving the problem computationally trivial for heuristics. This finding indicates that the community needs more rigorous criteria for defining what constitutes a truly "hard" distribution in the context of social choice.
Conclusion
This paper provides both practical and theoretical advancements in the study of voting complexity. By providing a tight approximation for weighted lobbying and linking average-case efficiency to self-knowing correctness, we offer a clearer picture of how to handle intractable social choice problems. The critique of junta distributions serves as a necessary caution for future research into the average-case hardness of election manipulation.
Summary updated