Collaborate with Strangers to Find Own Preferences

We consider a model with n players and m objects. Each player has a “preference vector” of length m , that models his grades for all objects. The grades are initially unknown to the players. A player can learn his grade for an object by probing that object, but performing a probe incurs cost. The go...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2008, Vol.42 (1), p.27-41
Main Authors: Awerbuch, Baruch, Azar, Yossi, Lotker, Zvi, Patt-Shamir, Boaz, Tuttle, Mark R.
Format: Article
Language:English
Subjects:
Algorithms
Billboards
Collaboration
Computer engineering
Computer Science
Information systems
Mathematical models
Preferences
Recommender systems
Studies
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider a model with n players and m objects. Each player has a “preference vector” of length m , that models his grades for all objects. The grades are initially unknown to the players. A player can learn his grade for an object by probing that object, but performing a probe incurs cost. The goal of a player is to learn his preference vector with minimal cost, by adopting the results of probes performed by other players. To facilitate communication, we assume that players collaborate by posting their grades for objects on a shared billboard: reading from the billboard is free. We consider players whose preference vectors are popular, i.e., players whose preferences are common to many other players. We present a sequential and a parallel algorithm to solve the problem with logarithmic cost overhead.
ISSN:1432-4350
1433-0490
DOI:10.1007/s00224-007-9016-7