CSAIL Research Abstracts - 2005 link to http://publications.csail.mit.edu/abstracts/abstracts05/index.html link to http://www.csail.mit.edu
bullet Introduction bullet Architecture, Systems
& Networks
bullet Language, Learning,
Vision & Graphics
bullet Physical, Biological
& Social Systems
bullet Theory bullet

horizontal line

Graphical Models and Collective Choice

Whitman Richards

The Problem

If group decisions are (i) based on rational models of choice relationships, and (ii) consensus is reached using a procedure akin to voting, then how easily can consensus be disrupted? Given a graphical model for the similarity relations between choices, there are three obvious (non-strategic) ways to affect consensus: (1) "rogue" voters who intentionally try to disrupt the process by casting votes arbitrarily, (2) voters whose viewpoints violate the shared model for the domain held by all other voters, and (3) unintentional "noise" distributed among all the voters introduced simply by uncertainty.


Decision-making by nations, states, parties, blocks of constituents, or more generally "agents" are not arbitrary, but are based on models for the domain. When uncertainty or "noise" is present about how choices are related, then outcomes may differ even if their choices are based on the same set of "facts" [3]. More perversely, outcomes can be changed by rogue agents who intentionally try to disrupt the decision-making process.

Previous Work

Over the past few years, we have shown how individual models for the relations among choices can lead to consensus, even when these models are not identical. The insight was to cast the similarity relations between the full set of alternatives as a graph, and to constrain an individual's model to be a sub-graph consistent with this global graphical model [1,2]. This is plausible for rational behaviors that have real-world constraints. The graphical form plays a dominant role in whether or not consensus will be reached, specifically how likely any alternative in the choice set will be selected.


Group decision-making is a process where individual members weigh alternative choices, and then vote for that alternative most preferred. The Borda count is one of the optimal voting procedures because it incorporates information about the choice domain, by including second preference choices in the voting tally. In a pair-wise contest, however, the Borda winner may at times be overturned. We measure the fragility of any Borda winner by the likelihood that it can be overturned with all other variables constant (e.g. voting strengths, graphical model…) If a Borda winner does not pass the test of beating all other alternatives in a pair-wise contest, then we have no consensus or "no-winner."


The figure shows the likelihood of no-winner when some fraction of all the votes are cast haphazardly, completely ignoring the graphical domain model. The labels for each of the solid curves indicate the size of the choice set. Decisions made using large choice sets are more easily disrupted than when there are only a few choices. The dashed curves show the effects when only a small group of rogue agents votes haphazardly all the time (or one-half the time for the 1/2 rogue curve.) Note that now the size of the domain model (i.e. the choice set) interacts with the number of rogue agents. Additional studies using less aggressive rogue agents are underway. Unlike the results below, when haphazard votes are cast only for an agent's third or fourth choice, then the graphical form, not the size of the graph, becomes the important variable.

How noise affects outcomes
Research Support:

AFOSR under contract #F49620-03-1-0213


[1] W. Richards, B. McKay, and D. Richards. The Probability of Collective Choice with shared Knowledge Structures. Jrl. Math. Psych. 46, 338-351, 2002.

[2] D. Richards, B. McKay and W. Richards. Collective Choice and Mutual Knowledge Structures. Adv. in Complex Systems 1, 221-236, 1998. Reprinted 2002 Chapt. 17 in Modeling Complexity in Economic & Social Systems. F. Schweitzer (Ed.)

[3] W. Richards and S. Seung, Neural Voting Machines. AI Memo 2004-029, 2004. See also: Ann. Proc. Cog. Sci. Soc. (2003)

horizontal line

MIT logo Computer Science and Artificial Intelligence Laboratory (CSAIL)
The Stata Center, Building 32 - 32 Vassar Street - Cambridge, MA 02139 - USA
tel:+1-617-253-0073 - publications@csail.mit.edu
(Note: On July 1, 2003, the AI Lab and LCS merged to form CSAIL.)