0

City has $1, ..., n$ citizens. Citizen $c_{i}$ has $v_{i}$ number of votes and each citizen's vote can be bought for certain price $p_{i}$. Election can be won by getting at least half of the votes. Given $F$ funds and knowing that each not bribed person will vote against, can election be won?

I have to show this problem is NP-Complete.

My idea is to just get maximum ammount of votes by using knapsack algorithm and checking if result (value of packed items) $R \gt \frac{1}{2}\sum_{v\in{V}}^{} v$, but i don't know if this is the right thinking, and what's more I have no idea how to show it formally and properly.

helloFromTheOtherSide
  • 3
  • You have to go in the other direction. If you had an algorithm for the "election fraud problem," how would you use it to solve the knapsack problem? – Fabio Somenzi Jun 03 '17 at 17:51
  • Does it even sound like I should use knapsack problem? Because I have to give an answer yes or no. – helloFromTheOtherSide Jun 03 '17 at 18:41
  • It's useful to think concretely: You have a program for the election problem. Someone is willing to pay you if you solve a knapsack problem. Can you (easily) translate the knapsack problem instance into an instance of your election problem so that the yes/no answer to the latter is the same you'd get if you solved the knapsack problem directly? In this context, "formally proving" amounts to specifying the translation and showing that it is cheap (polynomial). – Fabio Somenzi Jun 03 '17 at 19:07
  • I think the problem for me is that I can't see that translation without wich I think I can't safely say I understand how this works. – helloFromTheOtherSide Jun 03 '17 at 20:45
  • I can't see how I can get answer yes or no from knapsack problem since it gives set or value. – helloFromTheOtherSide Jun 03 '17 at 21:36
  • Given an optimization problem and a threshold, you can define the decision problem, "is there a solution with cost below the threshold (or value above the threshold)." It's the decision version of the knapsack problem that is proved NP-complete and that you want to reduce to your problem. – Fabio Somenzi Jun 04 '17 at 03:26
  • Ok I think I understand now, but I don't think I can transform decision knapsack problem to mine since I can not think of the way it can be translated, because I am getting data to knapsack problem I have to translate it to mine, solve mine problem and get answer to mine and knapsack problems both yes or no, but it cannot be done by this reduction because I have strict limit to my problem which is half of the votes, and variable limit to decision knapsack problem. – helloFromTheOtherSide Jun 04 '17 at 22:36
  • So if anyone could please tell me from which problem I could reduce mine I would be really grateful. – helloFromTheOtherSide Jun 05 '17 at 01:17
  • Sorry for being brief, but I'm traveling. The problem you map from has a certain maximum value. You check whether there's a solution with half that maximum. Check Wikipedia for that form of knapsack. – Fabio Somenzi Jun 05 '17 at 09:20

1 Answers1

0

The decision version of the Knapsack problem is:

Knapsack: Given $n$ items with
$\quad$ sizes $\quad\;\;s_1, s_2, ..., s_n$
$\quad$ values $\quad v_1, v_2, ..., v_n$
$\quad$ capacity $\;B$
$\quad$ value $\quad\; V$
is there a subset $S \subseteq \{ 1, 2,..., n \}$ such that $\sum_{i \in S} s_i \leq B$ and $\sum_{i \in S} v_i \geq V?$

Election: Given $n$ citizens with
$\quad$ sizes (prices)$\quad\quad\quad\quad\quad\; p_1, p_2, ..., p_n$
$\quad$ values (number of votes) $\;v_1, v_2, ..., v_n$
$\quad$ capacity (funds) $\quad\quad\quad \; F$
$\quad$ value (half the votes) $\quad\;V=\frac{1}{2} \sum_{i = 1}^{n} v_i$
is there a subset $S \subseteq \{ 1, 2,..., n \}$ such that $\sum_{i \in S} p_i \leq F$ and $\sum_{i \in S} v_i \geq V?$

Can you see the correspondence between the 2 decision problems now?

user137481
  • 2,605
  • Correspondence I could see from the beginning, but not how to do a reduction, and to be honest I think I didn't understand hole problem. All you need to do during reduction is to add new citizen to fraud problem if required limit in backpack differs from half of the votes fto fill the gap. – helloFromTheOtherSide Jun 07 '17 at 21:12
  • I have only provided an informal explanation of how to do the reduction. Are you able to do the formal proof now or do you still need help with the formal proof? – user137481 Jun 08 '17 at 21:02