AAMAS Conference 2012 Conference Paper
Communication Complexity of Approximating Voting Rules
- Travis Service
- Julie Adams
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 $\epsilon \in (0, 1)$, the communication complexity of obtaining a $1 - \epsilon$ approximation to Borda is $O(\log(\frac{1}{\epsilon}) nm)$. A lower bound of $\Omega(nm)$ is provided for small values of $\epsilon$. The communication complexity of computing the true Borda winner is $\Omega(nm\log(m))$. 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 \pm \epsilon$ approximation scheme exists. In particular, it is shown that the communication complexity of computing any constant factor approximation, $\rho$, to Bucklin is $\Omega(\frac{nm}{\rho^2})$. Conitzer and Sandholm show that the communication complexity of computing the true Bucklin winner is $O(nm)$. However, we show that for all $\delta \in (0, 1)$, the communication complexity of computing a $m^{\delta}$ approximate winner in Bucklin elections is $O(nm^{1-\delta}\log(m))$. For $\delta \in (\frac{1}{2}, 1)$ a lower bound of $\Omega( nm^{1-2\delta} )$ is also provided. Similar lower bounds are presented on the communication complexity of computing approximate winners in Copeland elections.