We present an incentive-based architecture for providing recommendations in a social network. We maintain a distinct reputation system for each individual and we rely on users to identify appropriate correlations and rate the items using asystem-providedrecommendationlanguage.Thekeyidea is to design an incentive structure and a ranking system such that any inaccuracy in the recommendations implies the existence of a profitable arbitrage opportunity, hence making the system resistant to malicious spam and presentation bias. We also show that, under mild assumptions, our architecture provides users with incentive to minimize the Kullback-Leibler divergence between the ratings and the actual item qualities, quickly driving the system to an equilibrium state with accurate recommendations.

We study the stability of the commonly used packet forwarding protocol, FIFO (first in first out), in the adversarial queueing model. We prove that FIFO can become unstable, i.e., lead to unbounded buffer-occupancies and queueing delays, at arbitrarily low injection rates. In order to demonstrate instability at rate r, we use a network of size $\tilde{O}(1/r)$.

We study the stability of the commonly used packet forwarding protocol, FIFO (First In First Out), in the adversarial queuing model. We prove that FIFO can become unstable, i.e., lead to unbounded buffer-occupancies and queuing delays, at arbitrarily low injection rates. In order to demonstrate instability at rate r, we use a network of size polynomial in 1/r.