Abstract
Network allocation problems typically seek to assign various resources in the best possible way, perhaps to maximise user welfare or fairness, and which can often be framed as stochastic optimisations. Similar resource allocation problems occur in economic settings, such as online ad-auctions where users bid for slots, and where auctions are often used to allocate the slots. We illustrate the connections between the two areas by considering large-scale Ad-auctions where adverts are assigned over a continuum of search types. For this pay-per-click market, we provide an efficient and highly decomposed mechanism that maximizes social welfare. In particular, we show that the social welfare optimization can be solved in separate optimizations conducted on the time-scales relevant to the advertisement platform and advertisers. This decomposition is implemented in an adversarial setting. Exploiting the information asymmetry between the platform and advertiser, we describe a simple mechanism which incentivizes truthful bidding and has a unique Nash equilibrium that is socially optimal, and thus implements our decomposition. Further, we consider models where advertisers adapt their bids smoothly over time, and prove convergence to the solution that maximizes aggregate utility. In a Cloud setting, the goods allocated may be multidimensional and have associated temporal constraints, adding further layers of complexity. Questions of fairness and allocation remain, and we outline some of this scheduling and pricing issues in this exciting new area.

Bio
Peter Key is a Principal Researcher at Microsoft Research, Cambridge. His current research interests focus on Networks, Economics, and Algorithms, spanning both theory and practice. In the past he has worked on Telecommunication Networks, Computer Networks and Social Networks. He is a Fellow of the ACM, IEEE, IET and IMA. Peter has a PhD and MSC in Statistics from London University and a MA in Mathematics from Oxford.