Crowdsourcing systems aggregate decisions of many people to help users quickly identify high-quality options, such as the best answers to questions or interesting news stories. A long-standing issue in crowdsourcing is how option quality and human judgement heuristics interact to affect collective outcomes, such as the perceived popularity of options. We address this limitation by conducting a controlled experiment where subjects choose between two ranked options whose quality can be independently varied. We use this data to construct a model that quantifies how judgement heuristics and option quality combine when deciding between two options. The model reveals popularity-ranking can be unstable: unless the quality difference between the two options is sufficiently high, the higher quality option is not guaranteed to be eventually ranked on top. To rectify this instability, we create an algorithm that accounts for judgement heuristics to infer the best option and rank it first. This algorithm is guaranteed to be optimal if data matches the model. When the data does not match the model, however, simulations show that in practice this algorithm performs better or at least as well as popularity-based and recency-based ranking for any two-choice question. Our work suggests that algorithms relying on inference of mathematical models of user behavior can substantially improve outcomes in crowdsourcing systems.

Unpredictability is often portrayed as an undesirable outcome of social influence in cultural markets. Unpredictability stems from the "rich get richer" effect, whereby small fluctuations in the market share or popularity of products are amplified over time by social influence. In this paper, we report results of an experimental study that shows that unpredictability is not an inherent property of social influence. We investigate strategies for creating markets in which the popularity of products is better-and more predictably-aligned with their underlying quality. For our study, we created a cultural market of science stories and conducted randomized experiments on different policies for presenting the stories to study participants. Specifically, we varied how the stories were ranked, and whether or not participants were shown the ratings these stories received from others. We present a policy that leverages social influence and product positioning to help distinguish the product's market share (popularity) from underlying quality. Highlighting products with the highest estimated quality reduces the "rich get richer" effect highlighting popular products. We show that this policy allows us to more robustly and predictably identify high quality products and promote blockbusters. The policy can be used to create more efficient online cultural markets with a better allocation of resources to products.

Users of peer production web sites differ greatly in their activity levels.A small minority are engaged contributors, while the vast majority are only casual surfers. The casual users devote little effort to evaluating the site's content and many of them visit the site only once. This churn poses a challenge for sites attempting to gauge user interest in their content. The challenge is especially severe for sites focusing on content with subjective quality, including movies, music, restaurants and items in other cultural markets. A key question is whether content evaluation should use opinions of all users or only the minority who devote significant effort to reviewing content? Using Amazon Mechanical Turk, we experimentally address this question by comparing outcomes for these two approaches. We find that the larger numbers of less informed users more than offset their noisy signals on content quality to provide rapid evaluation. However, such users are systematically biased, and the speed of their assessments comes at the expense of limited collective accuracy.

The popularity of content in social media is unequally distributed, with some items receiving a disproportionate share of attention from users. Predicting which newly-submitted items will become popular is critically important for both the hosts of social media content and its consumers. Accurate and timely prediction would enable hosts to maximize revenue through differential pricing for access to content or ad placement. Prediction would also give consumers an important tool for filtering the content. Predicting the popularity of content in social media is challenging due to the complex interactions between content quality and how the social media site highlights its content. Moreover, most social media sites selectively present content that has been highly rated by similar users, whose similarity is indicated implicitly by their behavior or explicitly by links in a social network. While these factors make it difficult to predict popularity a priori , stochastic models of user behavior on these sites can allow predicting popularity based on early user reactions to new content. By incorporating the various mechanisms through which web sites display content, such models improve on predictions that are based on simply extrapolating from the early votes. Specifically, for one such site, the news aggregator Digg, we show how a stochastic model distinguishes the effect of the increased visibility due to the network from how interested users are in the content. We find a wide range of interest, distinguishing stories primarily of interest to users in the network (“niche interests”) from those of more general interest to the user community. This distinction is useful for predicting a story’s eventual popularity from users’ early reactions to the story.

Popularity of content in social media is unequally distributed, with some items receiving a disproportionate share of attention from users. Predicting which newly-submitted items will become popular is critically important for both companies that host social media sites and their users. Accurate and timely prediction would enable the companies to maximize revenue through differential pricing for access to content or ad placement. Prediction would also give consumers an important tool for filtering the ever-growing amount of content. Predicting popularity of content in social media, however, is challenging due to the complex interactions among content quality, how the social media site chooses to highlight content, and influence among users. While these factors make it difficult to predict popularity a priori, we show that stochastic models of user behavior on these sites allows predicting popularity based on early user reactions to new content. By incorporating aspects of the web site design, such models improve on predictions based on simply extrapolating from the early votes. We validate this claim on the social news portal Digg using a previously-developed model of social voting based on the Digg user interface.

Increasingly, large organizations are experimenting with internal social media (e.g., blogs, forums) as a platform for widespread distributed collaboration. Contributions to their counterparts outside the organization’s firewall are driven by attention from strangers, in addition to sharing among friends. However, employees in a workplace under time pressures may be reluctant to participate–and the audience for their contributions is comparatively smaller. Participation rates also vary widely from group to group. So what influences people to contribute in this environment? In this paper, we present the results of a year-long empirical study of internal social media participation at a large technology company, and analyze the impact attention, feedback, and managers’ and coworkers ’ participation have on employees ’ behavior. We find feedback in the form of posted comments is highly correlated with a user’s subsequent participation. Recent manager and coworker activity relate to users initiating or resuming participation in social media. These findings extend, to an aggregate level, the results from prior interviews about blogging at the company and offer design and policy implications for organizations seeking to encourage social media adoption.

Traditional online social network sites use a single monolithic "friends" relationship to link users. However, users may have more in common with strangers, suggesting the use of a "similarity network" to recommend content. This paper examines the usefulness of this distinction in propagating new content. Using both macroscopic and microscopic social dynamics, we present an analysis of Essembly, an ideological social network that semantically distinguishes between friends and ideological allies and nemeses. Although users have greater similarity with their allies than their friends and nemeses, surprisingly, the allies network does not affect voting behavior, despite being as large as the friends network. In contrast, users are influenced differently by their friends and nemeses, indicating that people use these networks for distinct purposes. We suggest resulting design implications for social content aggregation services and recommender systems.

This paper proposes a dynamic model of DNA microarray hybridization properties in moving fluid. Prior experimental studies indicate hybridization efficiency is closely related to fluid dynamics, temperature, DNA probe density and microarray surface properties. Simulation results using the model proposed here agree well with practical observations. The model may be used to improve and manipulate performance of DNA microarray hybridization, and implement as a control model for hybridization automation to improve reliability and robustness of microarray hybridization process.

This work presents chemical communication techniques for nanorobots foraging in fluid environments relevant for medical applications. Unlike larger robots, viscous forces and rapid diffusion dominate their behaviors. Examples range from modified microorganisms to nanorobots using ongoing developments in molecular computation, sensors and motors. The nanorobots use an innovative methodology to achieve decentralized control for a distributed collective action in the combat of cancer. A communication approach is described in the context of recognize a single tumor cell in a small venule as a target for medical treatment. Thus, a higher gradient of signal intensity of E-cadherin is used as chemical parameter identification in guiding nanorobots to identify malignant tissues. A nanorobot can effectively use chemical communication to improve intervention time to identify tumor cells

The biologically-inspired swarm paradigm is being used to design self-organizing systems of locally interacting artificial agents. A major difficulty in designing swarms with desired characteristics is understanding the causal relation between individual agent and collective behaviors. Mathematical analysis of swarm dynamics can address this difficulty to gain insight into system design. This paper proposes a framework for mathematical modeling of swarms of microscopic robots that may one day be useful in medical applications. While such devices do not yet exist, the modeling approach can be helpful in identifying various design trade-offs for the robots and be a useful guide for their eventual fabrication. Specifically, we examine microscopic robots that reside in a fluid, for example, a bloodstream, and are able to detect and respond to different chemicals. We present the general mathematical model of a scenario in which robots locate a chemical source. We solve the scenario in one-dimension and show how results can be used to evaluate certain design decisions.

We experimentally compare low-information, high-information and self-reporting reputation mechanisms. The results indicate players strategically reacted to the reputation mechanisms, with higher information mechanisms increasing market efficiency.

No abstract available.

We demonstrate how simple local rules, inspired by social insects, produce complex dynamic behaviors required for locomotion and navigation in modular self-reconfigurable robots. We show how systems made up of many modules respond dynamically to their environment, such as obstacles during navigation. We present control algorithms tested on simulation experiments of TeleCube, a new modular robot developed at Xerox PARC.

We propose using the information revealed through auctions, including in particular the unsuccessful bids, to identify latent demand. Applied to combinatorial auctions for bundles of goods, this information can identify new bundles with particularly high valuations, expressed by their high complementarity. We present a simple algorithm for identifying these bundles, suitable for use with agent-based ecommerce systems.

We demonstrate how simple local sensing and control rules achieve useful emergent behaviors in modular self-reconfigurable (metamorphic) robots. Our biologically inspired approach grows structures with the desired functionality even though the final shapes have some unspecified random variation. By contrast, other self-reconfiguration algorithms require an a-priori exact description of a target shape for the given task, which may be difficult when a robot operates in uncertain environments. We present and evaluate several control algorithms through simulation experiments of Proteo, a metamorphic robot system.

A bstra& A major impediment to using recommendation systems and collective knowledge for electronic commerce is the reluctance of individuals to reveal preferences in order to find groups of people that share them.An equally important barrier to fluid electronic commerce is the lack of agreed upon trusted third parties.We propose new non-third party mechanisms to overcome these barriers.Our solutions facilitate finding shared preferences, discovering communities with shared values, removing disincentives posed by liabilities, and negotiating on behalf of a group.We adapt known techniques from the cryptographic literature to enable these new capabilities.

A previously developed quantum search algorithm for solving 1-SAT problems in a single step is generalized to apply to a range of highly constrained k-SAT problems. We identify a bound on the number of clauses in satisfiability problems for which the generalized algorithm can find a solution in a constant number of steps as the number of variables increases. This performance contrasts with the linear growth in the number of steps required by the best classical algorithms, and the exponential number required by classical and quantum methods that ignore the problem structure. In some cases, the algorithm can also guarantee that insoluble problems in fact have no solutions, unlike previously proposed quantum search algorithms.

Autonomous agents in distributed computational systems make decisions based on imperfect and delayed information. These systems are analogous to immune systems, ecologies, market economies and large human organizations. The nonlinear interactions among agents lead to a wide range of system-level dynamical behaviors, including chaos which can reduce overall performance. This paper uses a general dynamical model of autonomous agents to illustrate the stabilizing effect of a simple reward mechanism. The implications of these theoretical results are described for two examples: interacting agents on the World Wide Web and distributed controls for smart matter, i.e., materials with embedded sensors, actuators and controllers.

The easy-hard-easy pattern in the difficulty of combinatorial search problems as constraints are added has been explained as due to a competition between the decrease in number of solutions and increased pruning. We test the generality of this explanation by examining one of its predictions: if the number of solutions is held fixed by the choice of problems, then increased pruning should lead to a monotonic decrease in search cost. Instead, we find the easy-hard-easy pattern in median search cost even when the number of solutions is held constant, for some search methods. This generalizes previous observations of this pattern and shows that the existing theory does not explain the full range of the peak in search cost. In these cases the pattern appears to be due to changes in the size of the minimal unsolvable subproblems, rather than changing numbers of solutions.

We introduce an algorithm for combinatorial search on quantum computers that is capable of significantly concentrating amplitude into solutions for some NP search problems, on average. This is done by exploiting the same aspects of problem structure as used by classical backtrack methods to avoid unproductive search choices. This quantum algorithm is much more likely to find solutions than the simple direct use of quantum parallelism. Furthermore, empirical evaluation on small problems shows this quantum algorithm displays the same phase transition behavior, and at the same location, as seen in many previously studied classical search methods. Specifically, difficult problem instances are concentrated near the abrupt change from underconstrained to overconstrained problems.

Search is fundamental to artificial intelligence (AI) and numerous sophisticated search methods have been developed. We present a general, simple model of search processes and use it to analytically determine some typical behavior when applied to large problems. In particular, this identifies abrupt changes in overall search cost as small improvements are made in the underlying method. We also examine the robustness of this model's predictions in a range of more realistic cases. More generally, we introduce a criterion for determining when average case results reflect typical behavior which allows the method developed here to be used for investigating other large‐scale behaviors of complex AI systems.

The authors have designed and implemented an open, market-based computational system called Spawn. The Spawn system utilizes idle computational resources in a distributed network of heterogeneous computer workstations. It supports both coarse-grain concurrent applications and the remote execution of many independent tasks. Using concurrent Monte Carlo simulations as prototypical applications, the authors explore issues of fairness in resource distribution, currency as a form of priority, price equilibria, the dynamics of transients, and scaling to large systems. In addition to serving the practical goal of harnessing idle processor time in a computer network, Spawn has proven to be a valuable experimental workbench for studying computational markets and their dynamics.>

A simple and robust procedure for freezing out chaotic behavior in systems composed of interacting agents making decisions based on imperfect and delayed information is described. It is based on a reward mechanism whereby the relative number of computational agents following effective strategies is increased at the expense of the others. This procedure, which generates a diverse population out of an essentially homogeneous one, is able to control chaos through a series of dynamical bifurcations into a stable fixed point. Stability boundaries are computed and the minimal amount of diversity required in the system is established.>

The performance of fault-stealing algorithms for very large, multipipeline systolic arrays is considered. Extensions of an existing algorithm are proposed, and with these extensions the algorithm is shown to work for large array sizes. Using the modified algorithms as a testbed, a scaling theory that predicts, on the basis of performance for a single small array, the performance of the algorithm for arbitrary array size, defect rate, and number of spares is introduced. The theory differs from current approaches in that it has both analytical and empirical components, and in that it accurately predicts system performance, rather than providing bounds on it.>