Making Consensus Tractable
- Creators
-
Mossel, Elchanan
-
Tamuz, Omer
Abstract
We study a model of consensus decision making in which a finite group of Bayesian agents has to choose between one of two courses of action. Each member of the group has a private and independent signal at his or her disposal, giving some indication as to which action is optimal. To come to a common decision, the participants perform repeated rounds of voting. In each round, each agent casts a vote in favor of one of the two courses of action, reflecting his or her current belief, and observes the votes of the rest. We provide an efficient algorithm for the calculation the agents have to perform and show that consensus is always reached and that the probability of reaching a wrong decision decays exponentially with the number of agents.
Additional Information
© 2013 ACM, Inc. Received May 2012; revised September 2012, January 2013; accepted February 2013. E. Mossel is supported by a Sloan fellowship in Mathematics, by BSF grant 2004105, by an NSF Career Award (DMS 054829), by ONR award N00014-07-1-0506, and by ISF grant 1300/08. O. Tamuz is supported by ISF grant 1300/08 and is a recipient of the Google Europe Fellowship in Social Computing. This research is supported in part by this Google Fellowship.Attached Files
Submitted - 1007.0959.pdf
Files
Name | Size | Download all |
---|---|---|
md5:cbba4025ef313b1e65a135fedace71bd
|
206.9 kB | Preview Download |
Additional details
- Eprint ID
- 71910
- Resolver ID
- CaltechAUTHORS:20161110-081650257
- Binational Science Foundation (USA-Israel)
- 2004105
- NSF
- DMS 054829
- Office of Naval Research (ONR)
- N00014-07-1-0506
- Alfred P. Sloan Foundation
- Israel Science Foundation
- 1300/08
- Alfred P. Sloan Foundation
- Created
-
2016-11-11Created from EPrint's datestamp field
- Updated
-
2021-11-11Created from EPrint's last_modified field