Millions of recommendations, opinions and experiences are shared across popular microblogging platforms and services each day. Yet much of this content becomes quickly lost in the stream shortly after being posted. This paper looks at the feasibility of identifying useful content in microblog streams so that it might be archived to facilitate wider access and reference. Towards this goal, we present an experiment with a game-with-a-purpose called Twiage that we designed to determine how well the deluge of content in "raw" microblog streams could be turned into filtered and ranked collections using ratings from players. Experiments with Twiage validate the feasibility of applying human-computation to this problem, finding strong agreement about what constitutes the "most useful" content in our test dataset. Second, we compare the effectiveness of various methods of eliciting such ratings, finding that a "choose-best" interface and Elo rating ranking scheme yield the greatest agreement in the fewest rounds. External validation of resulting top-rated twitter content with a domain expert found that while the top Twiage-ranked "tweets" were among the best of the set, there was a tendency for players to also select what we term "weak spam" - e.g., promotional content disguised as articles or reviews, indicating a need for more stringent content filtering.

We introduce a novel distributed algorithm for multi-agent task allocation problems where the sets of tasks and agents constantly change over time. We build on an existing anytime algorithm (fast-max-sum), and give it significant new capa- bilities: namely, an online pruning procedure that simplifies the problem, and a branch-and-bound technique that reduces the search space. This allows us to scale to problems with hundreds of tasks and agents. We empirically evaluate our algorithm against established benchmarks and find that, even in such large environments, a solution is found up to 31% faster, and with up to 23% more utility, than state-of-the-art approximation algorithms. In addition, our algorithm sends up to 30% fewer messages than current approaches when the set of agents or tasks changes.

We present an on-line decentralised algorithm for coordinating mobile sensors for a broad class of information gathering tasks. These sensors can be deployed in unknown and possibly hostile environments, where uncertainty and dynamism are endemic. Such environments are common in the areas of disaster response and military surveillance. Our coordination approach itself is based on work by Stranders et al. (2009), that uses the max-sum algorithm to coordinate mobile sensors for monitoring spatial phenomena. In particular, we generalise and extend their approach to any domain where measurements can be valued. Also, we introduce a clustering approach that allows sensors to negotiate over paths to the most relevant locations, as opposed to a set of fixed directions, which results in a significantly improved performance. We demonstrate our algorithm by applying it to two challenging and distinct information gathering tasks. In the first–pursuit-evasion (PE)–sensors need to capture a target whose movement might be unknown. In the second–patrolling (P)–sensors need to minimise loss from intrusions that occur within their environment. In doing so, we obtain the first decentralised coordination algorithms for these domains. Finally, in each domain, we empirically evaluate our approach in a simulated environment, and show that it outperforms two state of the art greedy algorithms by 30% (PE) and 44% (P), and an existing approach based on the Travelling Salesman Problem by 52% (PE) and 30% (P).