Towards Social Problem-Solving with Human Subjects

1 Introduction

In order to harness the potential of social computing effective mechanisms and tools are needed to cooperation among human agents by means of several forms of knowledge exchange[2; 6]. Furthermore, the wide access to social networks data and the ever growing amount of human knowledge stored in digital format allows a deeper and quantitative analysis of humans' culture influence on human evolution[3; 4]. This raises an important question to Artificial Intelligence research: by which means human and machine agents can cooperate to perform computation and problem-solving in a social network?

Aiming at answering this this question we have implemented and analysed controlled experiments with human subjects solving instances of computational problems in social networks. Our experiments have tow objectives: to identify and infer properties underlying cooperation in human problem-solving, and to find out the mechanisms of knowledge exchange among human and machine agents when solving problems. As a consequence we shall be able to develop efficient algorithms for problem-solving that can impact the understanding of working group performance, coordination, cooperation, and organization of human social networks [2].

2 The Proposed Social NetworkModel

We modeled a Social Network through a generalization of Memetic Networks[1; 5]. In our model, problem-solving agents (either human or artificial) are connected through a network of arbitrary topology [1] where nodes represent agents and the edges allow connected agents to communicate (their solutions). Thus agents are allowed to perform two actions at any time:

1. First, agents can formulate their own solution to the problem's instance (with no communication with network peers) and, after that, agents can submit their formulated solution through the media (social network). This is known as the introspective phase.
2. Second, agents can evaluate neighbors' solutions available in the social network and potentially copy the entire neighbor's current solution. This is in the extroversive phase.

Therefore as agents evaluate solutions and choose between their own solution or their neighbor's, solutions are under selective pressure from the social network's agents.

3 Experiment Setup

In order to perform experiments to validate our model, we have built two web applications where subjects solved problems cooperatively through a web browser. Each submitted or copied solution was tagged with a timestamp and the subjects's identity information, and logged into a database. Subjects (or agents) in the network were groups of first and second year Computer Science undergraduates. The first application was shared with participating universities and experiments used non-industrial SAT problem instances from 1.2 million different instances with varying degrees of difficulty. The second application was published on Facebook's Open Service platform and used Sudoku game problem instances.

4 Experimental Results

The first set of experiments were carried out using a Social SAT solver, where subjects cooperate to solve SAT instances. A few issues have to be reported. First (as expected), we found out that the string size of harder SAT instances did not fit on a browser's window, limiting the set of SAT instances available for experimentation. The remaining SAT instances had a small solution space, thus favouring agents' strategies such as random walks due to high probability of choosing the right solution by chance. Such agents' randomwalks towards solution instances can be seen in Fig. 1.

Given the restrictions imposed by the hardness of the SAT problem, and and the small solution space of most SAT instances, we then chose to experiment with another problem. The second set of experiments was run over the Sudoku game instances. The Sudoku game has a compact description when compared to SAT instances. Also, the popularity of the Sudoku game allows participants from outside the academic community in the social network to generate very large amounts of data. The experiments' runs with the Sudoku game instances generated 300% more data with fewer problem instances (see summary in Table 1).

The experiments with the Sudoku game instances, allowed us to analyse how human subjects behave while cooperating in the extroversive phase. When human agents copy a neighbor's solution they do not evaluate how good a solution is to each problem instance; however, they do search for a neighbor's solution that is close to their own solution on their user interface. Thus, when human agents believe they cannot improve solutions' quality alone and must exchange solutions, they tend to choose solutions of their nearest neighbors, instead searching for the best solution available on the user interface. This result holds for both the SAT and Sudoku problem instances, in networks where agents have 2 to 20 connected neighbours. We also found out that the problem

K: # of neighbors

solving human social network always found the correct solution for all problem instances. The implications of this result and the strategies used by agents in the social networks are currently under further investigation.

5 Current Research Developments

We are currently analyzing the data collected from the experiments in order to model and understand the agents' behavior as represented in Figure 1. For instance, one could think of using Markov processes or other statistical models since there is a probabilistic behaviour associated to agents solving problems in a social network. This can contribute towards understanding how humans achieve complex problem-solving in a number of environments, with possible implications to working groups, social, and human computing.

Acknowledgements: Research partly supported by CNPq.