Though deliberation is a critical component of democratic decision-making, existing deliberative processes do not scale to large groups of people. Motivated by this, we propose a model in which large-scale decision-making takes place through a sequence of small group interactions. Our model considers a group of participants, each having an opinion which together form a graph. We show that for median graphs, a class of graphs including grids and trees, it is possible to use a small number of three-person interactions to tightly approximate the wisdom of the crowd, defined here to be the generalized median of participant opinions, even when agents are strategic. Interestingly, we also show that this sharply contrasts with small groups of size two, for which we prove an impossibility result. Specifically, we show that it is impossible to use sequences of two-person interactions satisfying natural axioms to find a tight approximation of the generalized median, even when agents are non-strategic. Our results demonstrate the potential of small group interactions for reaching global decision-making properties.
The problem of scaling up decision-making is a well-studied problem in the context of voting and preference elicitation. In this context, one is typically trying to approximate or calculate the output of a social choice function while only eliciting small amounts of information from voters (e.g. through pairwise comparisons) @cite_9 @cite_23 @cite_14 @cite_30 . Our paper can be viewed as an attempt to create a thread of research mirroring preference elicitation, but for deliberative processes. Thus far, computational social choice has primarily viewed decision-making and preference elicitation from the perspective of efficiency, accuracy, and strategic issues. We propose that deliberation is a valuable new dimension to consider in social choice and provide a small step in this direction. We discuss this direction more in the concluding section.
@cite_30 @cite_9 @cite_14 @cite_23
2121751780 99643971 1948781505
We determine the communication complexity of the common voting rules. The rules (sorted by their communication complexity from low to high) are plurality, plurality with runoff, single transferable vote (STV), Condorcet, approval, Bucklin, cup, maximin, Borda, Copeland, and ranked pairs. For each rule, we first give a deterministic communication protocol and an upper bound on the number of bits communicated in it; then, we give a lower bound on (even the nondeterministic) communication requirements of the voting rule. The bounds match for all voting rules except STV and maximin. While voting schemes provide an effective means for aggregating preferences, methods for the effective elicitation of voter preferences have received little attention. We address this problem by first considering approximate winner determination when incomplete voter preferences are provided. Exploiting natural scoring metrics, we use max regret to measure the quality or robustness of proposed winners, and develop polynomial time algorithms for computing the alternative with minimax regret for several popular voting rules. We then show how minimax regret can be used to effectively drive incremental preference vote elicitation and devise several heuristics for this process. Despite worst-case theoretical results showing that most voting protocols require nearly complete voter preferences to determine winners, we demonstrate the practical effectiveness of regret-based elicitation for determining both approximate and exact winners on several real-world data sets. 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.