In this talk I will present the concept of bribery and its relation to computer science, multi-agent systems and complexity theory. The idea is that in a multi-agent setting agents often need to arrive at common decisions via, e.g., voting. However, due to their computational power, software agents are capable of systematic strategic behavior (e.g., misrepresenting their votes, or---as in this case---bribery). In this talk we will study the complexity of optimal bribery. In particular, we would like to show that computational complexity can defend us from at least some ways for cheating in elections.
Colloquia Series page.