We consider a simple model for reputation systems such as the one used by eBay. In our model there are n players, some of which may exhibit arbitrarily malicious (Byzantine) behavior, and there are m objects, some of which are bad. The goal of the honest players is to find a good object. To facilitate collaboration, the system maintains a shared billboard. A basic step of a player consists of consulting the billboard, probing an object to learn its true value, and posting the result on the billboard for the benefit of others. Probing an object incurs a unit cost to the player, and consulting the billboard is free. The dilemma of an honest player is how to balance between the desire to reduce its cost by taking advantage of the reports posted by honest peers, and the fear of being exploited by adopting reports posted by malicious players.

In prior work, we presented an algorithm solving this problem in an asynchronous model, and we analyzed the total cost of the probes made by honest players during the algorithm. In this paper, we focus on the individual cost, and we consider a synchronous model in which each player takes a step in each round. Our prior algorithm has individual cost 0(\frac{1}{\alpha }\log n) in this model, assuming that an \alpha fraction of players are honest. In this paper, we prove that no algorithm can guarantee individual cost of less than \Omega (\frac{1}{\alpha }), which is essentially constant if there are enough honest players. Our main result is a new algorithm that achieves O(1) individual cost when there are many honest players, and achieves individual cost 0(\frac{1}{\alpha }\frac{{\log n}}{{\log \log n}}) even when there are not. We also show that this algorithm generalizes to other interesting scenarios.