Archive for the ‘cooperation’ Category

Mobile Social Shopping

Wednesday, July 4th, 2007

The Utiforo project that some of us here are involved in (see previous posts) is sub-titled “pervasive computing support for market trading;” the broad goal of the project is to bridge the gap between online and offline commerce by researching the applicability of trust to this scenario. One of the sub-goals of our partners at Sussex is to develop a navigation kiosk application, to capture user policies as they roam shopping centres.

However, I’ve read a couple recent articles that show that commercial applications are most likely one step ahead: Wishpot, for example, allows users to upload and share items of interest (via mobile phone text messages or photographs) to their online profile. They can then use their profile, along with various social-network features, to research prices, view user-ratings, and receive recommendations. Other commercial applications include Kaboodle, Stylehive, Zlio, and MyPickList. One site even quoted that these services will bring about the end of impulse buying (by allowing users quick access to price comparisons and product quality assessments)!

Participatory Sensing starts from Web 2.0

Friday, June 8th, 2007

A first step towards participatory sensing (pdf). Commissioned by the Cabinet Office, a report, called The Power of Information, aimed to find out more about Web 2.0 tools and communities to see how the government can get involved to help Britons make the most of this “new pattern of information creation and use”. (bbc news)

Private Collaborative Filtering

Thursday, June 7th, 2007

Recently, I submitted my first paper to RecSys 07, “Private Distributed Collaborative Filtering using Estimated Concordance Measures.” Even though it is not particularly about mobile-stuff, here’s a quick run through the main ideas:

Collaborative filtering is a means of using a community’s behavior, within a certain domain (movies, music), to support reducing the amount of information that each individual needs to looks through to find their items of interest. It is the dominant method behind recommender systems (such as Amazon, etc), and is based on a simple idea: people with previous shared interests will, most likely, share common likes and dislikes in the future. So, to predict how much I will like a certain item, the system first compares my rating history to all the other users to produce similarity measures, and then uses these similarity measures to compute a weighted average of how much they enjoyed the item in question.

The problem is that this method allows for no privacy. Particularly in a distributed environment, where I do not know how much to trust unknown neighbors, I do not want to have to share my entire rating history (i.e. my profile) with them, to find a similarity measure- thus discouraging cooperation, which is harmful to collaborative filtering. The actual similarity measures (the most famous being the Pearson correlation coefficient), simply cannot be found without full profile disclosure.

Therefore, in the paper we proposed a new similarity measure, based on concordance. You and I rate a movie concordantly if we both rate it above or below our mean rating (in other words, we agree about whether to give it thumbs up/thumbs down). If you hated the movie (and rated it below your mean), and I loved it (rating it above my mean), then we disagree- the ratings are discordant. If one of us has no opinion about the movie, we just say it is tied. The new similarity measure is derived from the number of concordant (C), discordant (D), tied (T) pairs between our rating sets, and the size of the set N, and this similarity measure works just as effectively (in terms of generating recommendations) as the Pearson correlation coefficient.

So how can this be used to include privacy in collaborative filtering? If you and I share a common randomly-generated set, and report to each other the number of C, D, and T pairs we have with the random set to each other, these values can be used to place bounds on the actual values of C, D, and T pairs we have with each other: we can estimate our similarity without ever sharing any profile-specific information, only sharing abstracted profile information derived from a comparison with a random set. Privacy is not breached, and, along with an incremental learning technique (future work) about how to evolve the similarity measure between recommenders, we can start collaborating with each other!

If you’re interested in the details (and the evaluation), I’ll post the paper on my web site soon (when I hear back from RecSys!)

Trust and reputation at AAMAS

Monday, January 15th, 2007

The program of AAMAS is out. Some of us may be interested in:

An Incentive Mechanism for Message Relaying in Unstructured Peer-to-Peer Systems
Information Searching and Sharing in Large-Scale Dynamic Networks
A Multi-Agent System for Building Dynamic Ontologies
Incentive Compatible Ranking Systems
On the Benefits of Cheating by Self-Interested Agents in Vehicular Networks
An Agent-Based Approach for Privacy-Preserving Recommender Systems
Effective Tag Mechanisms for Evolving Coordination
Distributed Task Allocation in Social Networks
Selecting Trust Evidences: an intuitive approach based on presumptive reasoning and domain analysis
Dynamically Learning Sources of Trust Information: Experience vs. Reputation
Rumours and Reputation: Evaluating Multi-Dimensional Trust within a Decentralised Reputation System

BitTyrant: a selfish BitTorrent client that improves performance

Friday, January 5th, 2007

BitTyrant is a BitTorrent client with a novel unchoking algorithm.

Suppose your upload capacity is 50 KBps. If you’ve unchoked 5 peers, existing clients will send each peer 10 KBps, independent of the rate each is sending to you. In contrast, BitTyrant will rank all peers by their receive / sent ratios, preferentially unchoking those peers with high ratios.

During evaluation testing on more than 100 real BitTorrent swarms, BitTyrant provided an average 70% download performance increase when compared to the existing Azureus 2.5 implementation, with some downloads finishing more than three times as quickly.

I wonder how well it performs in swarms of other BitTyrant clients?

The USENIX paper is here.

Update: it seems to be using the same faster than the bear algorithm I came up with last year. Damn it, I should have tried it out. :-)

From Competition to Cooperation

Friday, December 15th, 2006

Understanding the evolution of cooperation–whether between genes or cells or within animal and human societies–remains one of the fundamental challenges of biology (see the Perspective by Boyd). Nowak (p. 1560) reviews the five main mechanisms of cooperation: kin selection, direct reciprocity, indirect reciprocity, network reciprocity, and group selection. Bowles (p. 1569) contends that the ecological challenges facing humans during the late Pleistocene resulted in intense competition for resources, frequent group extinctions, and intergroup violence. Genetic, climatic, archaeological, ethnographic, and experimental data were used to look at human cooperation in an economics-based, cost-benefit model. Members of a group bearing genes for altruistic behavior pay a tax by limiting their reproductive opportunities in order to benefit from sharing food and information, thereby increasing the average fitness of the group, as well as their interrelatedness. Bands of altruistic humans would then act in concert to gain resources from other groups at a time when humans faced daily challenges to survival.


Friday, November 10th, 2006

The program of ACM MobiShare (International Workshop on Decentralized Resource Sharing in Mobile Computing and Networking) – in conjunction with Mobicom.

“Game” Digg

Thursday, November 9th, 2006

Digg continues to grow, claiming 20 million visitors per month and an increasing amount of mainstream attention. But as traffic to Digg has grown, the incentive to “game” the site to get stories to the home page has also increased.