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

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

2007-03-20

arxiv.org/abs/cs/0703097v1

Computer Science

Computer Science and Game Theory

Scientific paper

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].

Affiliated with

Also associated with

No associations

Rating

On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-382184