Robust Dynamic Mechanisms

Citation

Mostagir, Mohamed (2012) Robust Dynamic Mechanisms. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/9PWJ-QM61. https://resolver.caltech.edu/CaltechTHESIS:03262012-183213517

Abstract

This thesis presents and solves two dynamic problems. The first problem comes from online display advertising. In display advertising, a publisher displays an ad for an advertiser when a targeted user visits a webpage related to the advertiser's products or services. However, the publisher cannot control the supply of display opportunities, and hence the actual supply of ads that it can sell is stochastic. I consider the problem of optimal ad delivery, where the advertiser demands a certain number of impressions to be displayed over a certain time horizon. Time is divided into periods, and in the beginning of each period the publisher chooses a fraction of the still unrealized supply to allocate towards fulfilling the publisher's demand. The goal is to be able to fulfill the demand at the end of the horizon with minimal costs incurred from penalties associated with shortage or overdelivery of impressions. For a special case of this problem I describe an optimal policy that is very easy to implement. The general version of the problem is more computationally demanding, but I describe policies that are both implementable and arbitrarily close to the optimal solution.

In the second part of the thesis, I develop a framework in which a principal can exploit myopic social learning in a population of agents in order to implement social or selfish outcomes that would not be possible under the traditional fully-rational agent model. Learning in this framework takes a simple form of imitation, or replicator dynamics, a class of learning dynamics that often leads the population to converge to a Nash equilibrium of the underlying game. To illustrate the approach, I give a wide class of games for which the principal can obtain strictly better outcomes than the corresponding Nash solution and show how such outcomes can be implemented. The framework is general enough to accommodate many scenarios, and powerful enough to generate predictions that agree with empirically-observed behavior. The last part of the thesis considers two more learning models, best response and fictitious play, and derives the principal's optimal policies theoretically and computationally for the same class of games considered in the social learning model.

Thesis Files