Incomplete Information and Communication in Voting

Many voting schemes (and other social choice mechanisms) make stringent assumptions about the preference information provided by voters, as well as other aspects of the choice situation. Realizing these assumptions in practice often imposes an undesirable and unnecessary burden on both voters and mechanism designers with respect to the provision of such information. This chapter provides an overview of a variety of topics related to the information and communication requirements of voting. One theme underlying much of the work discussed in this chapter is its focus on determining winners or making decisions with incomplete or stochastic information about voter preferences—or in some
cases, about the alternatives themselves. This includes work on the computational complexity of determining possible/necessary winners and regret-based winner determination; the query or communication complexity of eliciting preferences; practical schemes for preference elicitation; winner determination under alternative uncertainty; the sample complexity of learning voting rules; and compilation complexity.

• Machine intelligence

• Human-computer interaction and visualization