On the verification complexity of group decision-making tasks

Ofra Amir, Yuval Shahar, Yakov Gal, Litan Ilany

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

A popular use of crowdsourcing is to collect and aggregate individual worker responses to problems to reach a correct answer. This paper studies the relationship between the computation complexity class of problems, and the ability of a group to agree on a correct solution. We hypothesized that for NP-Complete (NPC) problems, groups would be able to reach a majority-based correct solution once it was suggested by a group member and presented to the other members, due to the “easy to verify” (i.e., verification in polynomial time) characteristic of this complexity class. In contrast, when posed with PSPACE-Complete (PSC) “hard to verify” problems (i.e., verification in exponential time), groups will not necessarily be able to choose a correct solution even if such a solution has been presented. Consequently, increasing the size of the group is expected to facilitate the ability of the group to converge on a correct solution when solving NPC problems, but not when solving PSC problems. To test this hypothesis we conducted preliminary experiments in which we evaluated people’s ability to solve an analytical problem and their ability to recognize a correct solution. In our experiments, participants were significantly more likely to recognize correct and incorrect solutions for NPC problems than for PSC problems, even for problems of similar difficulties (as measured by the percentage of participants who solved the problem). This is a first step towards formalizing a relationship between the computationally complexity of a problem and the crowd’s ability to converge to a correct solution to the problem.
Original languageEnglish
Title of host publicationProceedings of the First AAAI Conference on Human Computation and Crowdsourcing
Place of PublicationPalm Springs, California USA
PublisherAAAI Press
Number of pages7
Publication statusPublished - 3 Nov 2013
EventFirst AAAI Conference on Human Computation and Crowdsourcing - Palm Springs, United States
Duration: 6 Nov 20139 Nov 2013


ConferenceFirst AAAI Conference on Human Computation and Crowdsourcing
Abbreviated titleHCOMP 2013
Country/TerritoryUnited States
CityPalm Springs
Internet address


Dive into the research topics of 'On the verification complexity of group decision-making tasks'. Together they form a unique fingerprint.

Cite this