Incentives Design in the Presence of Externalities

Abstract

The design of incentives becomes challenging when faced with externalities. In this thesis I resolve this difficulty in two settings: position auctions and software economies. The first part of the thesis studies value externalities in position auctions. I develop a constraint-based model that allows an advertiser to submit, along with its bid, additional constraints to state how its value for clicks depends on the positions of the other ads with which it is allocated. I establish complexity results for winner determination and prove the existence of Nash and envy-free equilibria under certain conditions.

A significant contribution of this thesis is that it proposes a foundation for software economies. I first study a setting in the private software economy consisting of a single task, a worker, and a manager. This is a combination of a repeated principal-agent problem and a prediction problem. I characterize a scoring system that elicits truthful information, leading to accurate predictions from both agents and best effort from the worker.

In the public software economy, I consider the problem of how to incentivize deep fixes to bugs from both computational as well as theoretical perspectives. In the computational work, I introduce a dynamic model of the software ecosystem and propose subsumption mechanisms as a solution. Next, I adapt an approximation methodology that is well-suited to large market settings, known as mean field equilibrium, to the model. I conduct an experimental study to characterize the system in equilibrium and derive lessons for market design.

I perform theoretical analysis of a simple mean field model of deep fixes and prove the existence of a mean field equilibrium. Further, I define a new type of dynamic market equilibrium, called correctness equilibrium, and prove its existence. Finally I consider the relationship between mean field equilibrium and correctness equilibrium, showing that mean field equilibrium need not satisfy a notion of efficiency whereas correctness equilibrium does.