Social choice theory can serve as an appropriate foundation upon which to build cooperative information agent applications. There is a rich literature on the subject of voting, with important theoretical results, and builders of automated agents can benefit from this work as they engineer systems that reach group consensus.
This talk will review various voting techniques and give an overview of some of the seminal results in social choice theory. We will then consider the application of these techniques (in scenarios such as multiagent planning), and examine nuances in their use. In particular, we'll consider the issue of preference extraction in these systems, with an emphasis on the complexity of manipulating group outcomes. We show that a family of important voting protocols is susceptible to manipulation by coalitions in the average case, when the number of candidates is constant (even though their worst-case manipulations are NP-hard).
This is a joint work with Ariel D. Procaccia.