Although crowdsourcing has been proven efficient as a mechanism to solve independent tasks for on-line production, it is still unclear how to define and manage workflows in complex tasks that require the participation and coordination of different workers. Despite the existence of different frameworks to define workflows, we still lack a commonly accepted solution that is able to describe the most common workflows in current and future platforms. In this paper, we propose CrowdWON, a new graphical framework to describe and monitor crowd processes, the proposed language is able to represent the workflow of most well-known existing applications, extend previous modelling frameworks, and assist in the future generation of crowdsourcing platforms. Beyond previous proposals, CrowdWON allows for the formal definition of adaptative workflows, that depend on the skills of the crowd workers and/or process deadlines. CrowdWON also allows expressing constraints on workers based on previous individual contributions. Finally, we show how our proposal can be used to describe well known crowdsourcing workflows.

Recent studies have suggested that current agent-based models are not sufficiently sophisticated to reproduce results achieved by human collaborative learning and reasoning. Such studies suggest that humans are diverse and dynamic when solving problems socially. However, despite their relevance to problem-solving, these two behavioral features have not yet been fully investigated. In this paper we analyse a recent social problem-solving model and attempt to address its shortcomings. Specifically, we investigate the effects of separating exploitation from exploration in agent behaviors and explore the concept of diversity in such models. We found out that diverse populations outperform homogeneous ones in both efficient and inefficient networks. Finally, we show that agent diversity is more relevant than the strategic behavioral dynamics. This work contributes towards understanding the role of diverse and dynamic behaviors in social problem-solving as well as the advancement of state-of-art social problem-solving models.

In a basic economic system, each participant receives a (financial) reward according to his own contribution to the system. In this work, we study an alternative approach — Incentive Networks — in which a participant's reward depends not only on his own contribution; but also in part on the contributions made by his social contacts or friends. We show that the key parameter effecting the efficiency of such an Incentive Network-based economic system depends on the participant's degree of directed altruism. Directed altruism is the extent to which someone is willing to work if his work results in a payment to his friend, rather than to himself. Specifically, we characterize the condition under which an Incentive Network-based economy is more efficient than the basic "pay-for-your-contribution" economy. We quantify by how much incentive networks can reduce the total reward that needs to be paid to the participants in order to achieve a certain overall contribution. Finally, we study the impact of the network topology and various exogenous parameters on the efficiency of incentive networks. Our results suggest that in many practical settings, Incentive Network-based reward systems or compensation structures could be more efficient than the ubiquitous 'pay-for-your-contribution' schemes.

Transcribed speech is a critical resource for building statistical speech recognition systems. Recent work has looked towards soliciting transcriptions for large speech corpora from native speakers of the language using crowdsourcing techniques. However, native speakers of the target language may not be readily available for crowdsourcing. We examine the following question: can humans unfamiliar with the target language help transcribe? We follow an information-theoretic approach to this problem: (1) We learn the characteristics of a noisy channel that models the transcribers' systematic perception biases. (2) We use an error-correcting code, specifically a repetition code, to encode the inputs to this channel, in conjunction with a maximum-likelihood decoding rule. To demonstrate the feasibility of this approach, we transcribe isolated Hindi words with the help of Mechanical Turk workers unfamiliar with Hindi. We successfully recover Hindi words with an accuracy of over 85% (and 94% in a 4-best list) using a 15-fold repetition code. We also estimate the conditional entropy of the input to this channel (Hindi words) given the channel output (transcripts from crowdsourced workers) to be less than 2 bits; this serves as a theoretical estimate of the average number of bits of auxiliary information required for errorless recovery.

Motivated by current day crowdsourcing platforms and emergence of online labor markets, this work addresses the problem of task allocation and payment decisions when unreliable and strategic workers arrive over time to work on tasks which must be completed within a deadline. We consider the following scenario: a requester has a set of tasks that must be completed before a deadline; agents (aka crowd workers) arrive over time and it is required to make sequential decisions regarding task allocation and pricing. Agents may have different costs for providing service and these costs are private information of the agents. We assume that agents are not strategic about their arrival times but could be strategic about their costs of service. In addition, agents could be unreliable in the sense of not being able to complete the assigned tasks within the allocated time; these tasks must then be reallocated to other agents to ensure ontime completion of the set of tasks by the deadline. For this setting, we propose two mechanisms: a DPM (DynamicPrice Mechanism) and an ABM (Auction Based Mechanism). Both mechanisms are dominant strategy incentive compatible, budget feasible, and also satisfy ex-post individual rationality for agents who complete the allocated tasks. These mechanisms can be implemented in current day crowdsourcing platforms with minimal changes to the current interaction model.

A* search is a fundamental topic in artificial intelligence. Recently, the general purpose computation on graphics processing units (GPGPU) has been widely used to accelerate numerous computational tasks. In this paper, we propose the first parallel variant of the A* search algorithm such that the search process of an agent can be accelerated by a single GPU processor in a massively parallel fashion. Our experiments have demonstrated that the GPU-accelerated A* search is efficient in solving multiple real-world search tasks, including combinatorial optimization problems, pathfinding and game solving. Compared to the traditional sequential CPU-based A* implementation, our GPU-based A* algorithm can achieve a significant speedup by up to 45x on large-scale search problems.

Temperature Discovery Search (TDS) is a forward search method for computing or approximating the temperature of a combinatorial game. Temperature and mean are important concepts in combinatorial game theory, which can be used to develop efficient algorithms for playing well in a sum of subgames. A new algorithm TDS+ with five enhancements of TDS is developed, which greatly speeds up both exact and approximate versions of TDS. Means and temperatures can be computed faster, and fixed-time approximations which are important for practical play can be computed with higher accuracy than before.

Modern society is critically dependent on the services provided by engineered infrastructure networks. When natural disasters (e.g. Hurricane Sandy) occur, the ability of these networks to provide service is often degraded because of physical damage to network components. One of the most critical of these networks is the electrical distribution grid, with medium voltage circuits often suffering the most severe damage. However, well-placed upgrades to these distribution grids can greatly improve post-event network performance. We formulate an optimal electrical distribution grid design problem as a two-stage, stochastic mixed-integer program with damage scenarios from natural disasters modeled as a set of stochastic events. We develop and investigate the tractability of an exact and several heuristic algorithms based on decompositions that are hybrids of techniques developed by the AI and operations research communities. We provide computational evidence that these algorithms have significant benefits when compared with commercial, mixed-integer programming software.

We present a data mining approach for reducing the search space of local search algorithms in large-scale set partitioning problems (SPPs). We construct a k-nearest neighbor graph by extracting variable associations from the instance to be solved, in order to identify promising pairs of flipping variables in the large neighborhood search. We incorporate the search space reduction technique into a 2-flip neighborhood local search algorithm with an efficient incremental evaluation of solutions and an adaptive control of penalty weights. We also develop a 4-flip neighborhood local search algorithm that flips four variables alternately along 4-paths or 4-cycles in the k-nearest neighbor graph. According to computational comparison with the latest solvers, our algorithm performs effectively for large-scale SPP instances with up to 2.57 million variables.

Stable matching problems have several practical applications. If preference lists are truncated and contain ties, finding a stable matching with maximal size is computationally difficult. We address this problem using a local search technique, based on Adaptive Search and present experimental evidence that this approach is much more efficient than state-of-the-art exact and approximate methods. Moreover, parallel versions (particularly versions with communication) improve performance so much that very large and hard instances can be solved quickly.