Mechanisms to manage incentives in online systems

In large scale online systems, such as electronic marketplaces and peer-to-peer systems, users often act in their self interest without considering whether their actions lead to efficient outcomes for the system. This thesis studies two important classes of mechanisms that can be used to incentivize users to act in a way that promotes efficiency. Aggregation mechanisms provide aggregate information on the past behavior of a user to other users in the system. When there is such a mechanism in place, a user should expect that bad behavior now affects his future interactions within the system, and may be incentivized to act in a way that is beneficial for the system. Market mechanisms can be used to incentivize contribution to the system by using prices to identify value, and associating a budget with each user the budget increases when the user contributes to the system and decreases when he uses system resources. By requiring that users have non-negative budgets, users can only use the system in return for valuable contributions.In Chapter 2 we address a basic question: how do we design an aggregation mechanism to encourage trustworthy behavior? Electronic marketplaces, such as eBay, are a natural setting to study this question, since they usually rely on mechanisms that collect ratings of sellers from past transactions, and provide aggregate information to potential buyers. First, we show that weighting all past ratings equally gives sellers an incentive to falsely advertise. We then study aggregation mechanisms that weight recent ratings more heavily, and show that under increasing returns to reputation the optimal strategy of a sufficiently patient and sufficiently high quality seller is to always advertise honestly. We suggest approaches for designing an aggregation mechanism that maximizes the range of parameters for which it is optimal for the seller to be truthful. We show that mechanisms that use information from a larger number of past transactions tend to provide incentives for patient sellers to be more truthful, but for higher quality sellers to be less truthful.In Chapter 3 we study the use of market mechanisms for peer-assisted content distribution. We formulate a peer-to-peer filesharing system as an exchange economy: a price is associated with each file, and users exchange files only when they can afford it. The exchange economy approach allows peers to exchange files multilaterally. This formulation solves the free-riding problem, since uploading files is a necessary condition for being able to download. We discuss existence, uniqueness, and dynamic stability of the competitive equilibrium, which is always guaranteed to be Pareto efficient. In addition, a novel aspect of our approach is an allocation mechanism for clearing the market out of equilibrium. We analyze this mechanism when users can anticipate how their actions affect the allocation mechanism (price anticipating behavior). For this regime we characterize the Nash equilibria that will occur, and show that as the number of users increases, the Nash equilibrium rates become approximately Pareto efficient. Finally, we consider a system with a general network structure and show that maintaining a single price per peer (even across multiple files) suffices to achieve the benefits of multilateral exchange.Most prevalent peer-to-peer systems incentivize users to contribute their upload capacity in a bilateral manner: downloading is possible in return for uploading to the same user. In Chapter 4 we provide a formal comparison of peer-to-peer system designs based on bilateral exchange with those that enable multilateral exchange via a price-based market mechanism to match supply and demand. First, we compare the two types of exchange in terms of the equilibria that arise. A competitive equilibrium allocation is Pareto efficient, while we demonstrate that bilateral equilibrium allocations are not Pareto efficient in general. We show that Pareto efficiency represents the "gap" between bilateral and competitive equilibria: a bilateral equilibrium allocation corresponds to a competitive equilibrium allocation if and only if it is Pareto efficient. Second, we compare the two types of exchange through the expected percentage of users that can trade in a large system, assuming a fixed file popularity distribution. Our theoretical results as well as analysis of a BitTorrent dataset provide quantitative insight into regimes where bilateral exchange may perform quite well even though it does not always give rise to Pareto efficient equilibrium allocations.