Abstract:

Systems in which users must make a sequence of decisions guided by information from potentially dishonest peers are ubiquitous in contemporary networked applications. (Examples include reputation and recommendation systems in e-commerce, and resource location systems in peer-to-peer networks.) We will discuss a multi-user learning problem which abstracts the sequential decision problems faced by users of such systems when selecting products or resources. Our model is characterized by three key features: (a) The quality of the products or resources may vary over time; (b) Some of the users in the system may be malicious, Byzantine agents; (c) The honest users are willing to obey a specified protocol when making and reporting their selections. We formulate the problem as a multi-user version of the multi-armed bandit problem from online learning theory. After reviewing the classical multi-armed bandit problem, we will exhibit an algorithm for the multi-user version which guarantees that the average quality of the honest users' decisions converges, in polylogarithmic time, to the average quality of the best fixed decision. Relations with other existing algorithms for reputation management and collaborative filtering will be discussed. This is joint work with Baruch Awerbuch.