Abstract. 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.

Citation: Ofra Amir, Yuval Shahar, Ya’akov Gal and Litan Ilany. On the Verification Complexity of Group Decision-Making Tasks. Conference on Human Computation and Crowdsourcing, Palm Springs, CA, November 2013.

Download: http://bit.ly/1MBhsqn

Social computing broadly refers to computing-supported approaches that facilitate interactions among people and organizations. Social computing has emerged as an exciting multidisciplinary area of research, driven by the wealth of easily available information and the success of online social networks and social media. Social computing applications are characterized by high interactivity among users, user-generated content, and in cases such as Wikipedia, more open governance structures. Much of the recent excitement in social computing is driven by data analytics and business models. What is still lacking, however, is a deeper conceptual understanding of social computing — e.g., relating to its conceptual bases, information and abstractions, design principles, and platforms. This event invites papers that take an explicitly multiagent perspective in addressing these gaps and do so in thought-provoking ways.

The First International Workshop on Multiagent Foundations of Social Computing is Co-located with AAMAS 2014

Important Dates

• Submission: January 22, 2014
• Notification: February 19, 2014
• Camera-ready due: March 5, 2014

Collective Intelligence 2014 is an interdisciplinary conference seeking to bring together researchers from a variety of fields relevant to understanding and designing collective intelligence of many types.

The conference will take place at MIT and consist of:

• Invited talks from prominent researchers in different areas related to collective intelligence such as engineering, psychology, management, political science, information science, and sociology
• Oral presentations
• Poster/Demo sessions
• “Ignite” sessions in which practitioners (e.g. policy makers) connect with researchers around collective-intelligence-based solutions to real-world problems

IMPORTANT DATES

• Extended abstract submission deadline:  January 15, 2014
• Notification of acceptance / rejection:  February 15, 2014
• Conference dates:  June 10-12, 2014

Also see Collective Intelligence 2012.