Communication complexity of approximating voting rules

This paper considers the communication complexity of approximating common voting rules. Both upper and lower bounds are presented. For n voters and m alternatives, it is shown that for all e e (0, 1), the communication complexity of obtaining a 1 - e approximation to Borda is O(log (1/e)nm). A lower bound of Ω(nm) is provided for fixed small values of e. The communication complexity of computing the true Borda winner is Ω(nm log(m)) [5]. Thus, in the case of Borda, one can obtain arbitrarily good approximations with less communication overhead than is required to compute the true Borda winner.For other voting rules, no such 1±e approximation scheme exists. In particular, it is shown that the communication complexity of computing any constant factor approximation, ρ, to Bucklin is Ω(nm/ρ2). Conitzer and Sandholm [5] show that the communication complexity of computing the true Bucklin winner is O(nm). However, we show that for all δ e (0, 1), the communication complexity of computing a mδ approximate winner in Bucklin elections is O(nm1 - δ log(m)). For δ e (1/2, 1), a lower bound of ω(nm1-2δ) is also provided.Similar lower bounds are presented on the communication complexity of computing approximate winners in Copeland elections.