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.
A similar high-level triadic decision-making process was proposed in a prior paper by the authors @cite_41 and analyzed for the restricted case (described in Figure ) of opinions on a line. In this paper, we consider richer small group decision dynamics such as majority rule. We also consider spaces more complex than the line and provide a general framework for analyzing deliberative decision-making that enables us to prove an impossibility result for dyads.
@cite_41
1971118040 1949110650 1982839492 2241340194
A voter sits on each vertex of an infinite tree of degree @math , and has to decide between two alternative opinions. At each time step, each voter switches to the opinion of the majority of her neighbors. We analyze this majority process when opinions are initialized to independent and identically distributed random variables. In particular, we bound the threshold value of the initial bias such that the process converges to consensus. In order to prove an upper bound, we characterize the process of a single node in the large @math -limit. This approach is inspired by the theory of mean field spin-glass and can potentially be generalized to a wider class of models. We also derive a lower bound that is nontrivial for small, odd values of @math . We consider the following distributed consensus problem: Each node in a complete communication network of size n initially holds an opinion, which is chosen arbitrarily from a finite set Σ. The system must converge toward a consensus state in which all, or almost all nodes, hold the same opinion. Moreover, this opinion should be valid, i.e., it should be one among those initially present in the system. This condition should be met even in the presence of a malicious adversary who can modify the opinions of a bounded subset of nodes, adaptively chosen in every round. We consider the 3-majority dynamics: At every round, every node pulls the opinion from three random neighbors and sets his new opinion to the majority one (ties are broken arbitrarily). Let k be the number of valid opinions. We show that, if k ≤ nα, where α is a suitable positive constant, the 3-majority dynamics converges in time polynomial in k and log n with high probability even in the presence of an adversary who can affect up to o([EQUATION]) nodes at each round. Previously, the convergence of the 3-majority protocol was known for |Σ| = 2 only, with an argument that is robust to adversarial errors. On the other hand, no anonymous, uniform-gossip protocol that is robust to adversarial errors was known for |Σ| > 2. A simple Ising spin model which can describe a mechanism of making a decision in a closed community is proposed. It is shown via standard Monte Carlo simulations that very simple rules lead to rather complicated dynamics and to a power law in the decision time distribution. It is found that a closed community has to evolve either to a dictatorship or a stalemate state (inability to take any common decision). A common decision can be taken in a "democratic way" only by an open community. We introduce a two-state opinion dynamics model where agents evolve by majority rule. In each update, a group of agents is specified whose members then all adopt the local majority state. In the mean-field limit, where a group consists of randomly selected agents, consensus is reached in a time that scales @math , where @math is the number of agents. On finite-dimensional lattices, where a group is a contiguous cluster, the consensus time fluctuates strongly between realizations and grows as a dimension-dependent power of @math . The upper critical dimension appears to be larger than 4. The final opinion always equals that of the initial majority except in one dimension.