  We study the concept of bribery in the situation where voters are willing to
change their votes as we ask them, but where their prices depend on the nature
of the change we request. Our model is an extension of the one of Faliszewski
et al. [FHH06], where each voter has a single price for any change we may ask
for. We show polynomial-time algorithms for our version of bribery for a broad
range of voting protocols, including plurality, veto, approval, and utility
based voting. In addition to our polynomial-time algorithms we provide
NP-completeness results for a couple of our nonuniform bribery problems for
weighted voters, and a couple of approximation algorithms for NP-complete
bribery problems defined in [FHH06] (in particular, an FPTAS for
plurality-weighted-$bribery problem).

Computer Science and Game Theory;Computational Complexity;Multiagent Systems