A Statistical Decision-Theoretic Framework for Social Choice
In this paper, we take a statistical decision-theoretic viewpoint on social choice, putting a focus on the decision to be made on behalf of a system of agents. In our framework, we are given a statistical ranking model, a decision space, and a loss function defined on (parameter, decision) pairs, and formulate social choice mechanisms as decision rules that minimize expected loss. This suggests a general framework for the design and analysis of new social choice mechanisms. We compare Bayesian estimators, which minimize Bayesian expected loss, for the Mallows model and the Condorcet model respectively, and the Kemeny rule. We consider various normative properties, in addition to computational complexity and asymptotic behavior. In particular, we show that the Bayesian estimator for the Condorcet model satisfies some desired properties such as anonymity, neutrality, and monotonicity, can be computed in polynomial time, and is asymptotically different from the other two rules when the data are generated from the Condorcet model for some ground truth parameter.
The author(s) consider social choice mechanisms from the point of view of statistical decision theory. They use this viewpoint to derive two new voting mechanisms based on the principle of Bayesian risk minimization. The rest of the paper studies the properties of the ranking produced by the new voting mechanisms and also an in-depth study of the computational complexity of realizing these mechanisms. The decision problems arising from finding good winning candidates for one of their schemes turns out to be NP-hard while the other is in P. The paper concludes with an asymptotic comparison of the decisions produced by their mechanisms and the Kemeny voting rule and an experimental evaluation of the asymptotic results.The results are original and the paper is well written (albeit dense with results). Minor comments:* Definition 4, the definition of the loss function L_{0-1}(\theta,c) is not provided this was a bit confusing since it is different from the function in Example 1. It seems that the definition should be L_{0-1}(\theta, c) = 0 if \theta \in \mathcal{L}_c(C) (resp. \mathcal{B}_c(C)) and 1 otherwise.* Lemma 2: I found it slightly confusing that the quantities outside the statement of the lemma (lines 249-251) were used implicitly in the lemma. It would be good to clean this up so that the statement is self-contained.* I'm not sure why this is bothering me so much, but it seems to me that the definition of P_||^NP-hard problem should use truth-table reductions rather than many-one reductions. In any case, feel free to ignore this comment since it does not affect the results of the paper.* Typo on Page 7, line 343: "where d is not ranked" ...->... "where b is not ranked".* Typo on Page 7, line 346: "BETTER DECISION" ...->... "OPTIMAL BAYESIAN DECISION".