On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time

Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski

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

Abstract

We investigate issues related to two hard problems related to voting, the optimal weighted lobbying problem and the winner problem for Dodgson elections. Regarding the former, Christian et al. [CFRS06] showed that optimal lobbying is intractable in the sense of parameterized complexity. We provide an efficient greedy algorithm that achieves a logarithmic approximation ratio for this problem and even for a more general variant--optimal weighted lobbying. We prove that essentially no better approximation ratio than ours can be proven for this greedy algorithm. The problem of determining Dodgson winners is known to be complete for parallel access to NP [HHR97]. Homan and Hemaspaandra [HH06] proposed an efficient greedy heuristic for finding Dodgson winners with a guaranteed frequency of success, and their heuristic is a ``frequently self-knowingly correct algorithm.'' We prove that every distributional problem solvable in polynomial time on the average with respect to the uniform distribution has a frequently self-knowingly correct polynomial-time algorithm. Furthermore, we study some features of probability weight of correctness with respect to Procaccia and Rosenschein's junta distributions [PR07].
BibTeX
@inproceedings{erdelyi2007approximating,
  author = {Gábor Erdélyi and Lane A. Hemaspaandra and Jörg Rothe and Holger Spakowski},
  title = {{On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time}},
  booktitle = {FCT},
  year = {2007},
  doi = {10.1007/978-3-540-74240-1\_26},
}
Figure