UC Berkeley

Over the past few decades, a new field has emerged from the interaction between Computer Science and Game Theory: Algorithmic Mechanism Design. The field has seen tremendous growth and has been extremely successful in tackling a wide variety of problems. Despite all this progress, the vast majority of the literature to date focuses on static, one-time decisions. In many situations of interest, however, this simplification is too far from reality. For example, a search engine must choose how to allocate its advertising inventory in the face of changing search queries and advertiser budgets. In a cloud computing center resources need to be dynamically reallocated in response to the arrival of new computational tasks of varying priority. This thesis explores the interplay of incentives and the dynamic nature of decision-making in the design of efficient mechanisms.

In the first part of this thesis we study Dynamic Auction Design. We introduce a novel class of dynamic auction problems in which a monopolist is selling $m$ items in $m$ consecutive stages to $n$ buyers.

We study these problem from several different perspectives:

{\em Computational Complexity}, i.e. how hard is it to compute the optimal auction, {\em Competition Complexity}, i.e. how much additional competition is necessary for a standard Vickrey (second-price) auction at every stage to extract more revenue than the optimal auction, {\em Power of Adaptivity}, i.e. what is the revenue gap between adaptive and non-adaptive auctions,

{\em Power of Commitment}, i.e. what happens if the seller cannot commit to her future behavior.

In the second part of this thesis we study Dynamic Fair Division. We introduce a novel class of resource allocation problems in which resources are shared between agents dynamically arriving and departing over time.

For a single resource, when $n$ agents are present, there is only one truly ``fair'' allocation: each agent receives $1/n$ of the resource. Implementing this static solution over time is notoriously impractical. There are too many disruptions to existing allocations: for a new agent to get her fair share, all other agents must give up a small piece. What if, at every $c$ arrivals we could only reclaim resources from a fixed number of agents $d$? We provide non-wasteful such algorithms that are almost optimal with respect to fairness, even for multiple, heterogeneous resources.