IFIP WG 7.3 Performance 2013

31st International Symposium on Computer Performance, Modeling, Measurements and Evaluation 2013

September 24-26, Vienna, Austria


Keynote speakers:

Peter Key: "Ad-auctions: where game theory meets machine learning and computer science"

Abstract: Each time a user types a query into a search engine, an auction is run to decide which ads (if any) to show in response, and where to place them on the results page. When a user clicks on an ad, the publisher is paid by the advertiser. This happens in real time, thousands of times every second, and generates billions of dollars in revenue. Current auctions run by Google or Bing use a ranking algorithm which is a variant of a Generalised Second Price Auction. This e-commerce example is a rich area for research which lies at the intersection of mathematics, economics and computer science. For example, advertisers need to determine how to bid in the face of uncertainty, a machine learning problem, while the auction designer wants to design a robust mechanism that balances the competing demands of users, advertisers and publisher.

We describe such ad-auctions, and illustrate how current systems have adapted insights taken from auction theory and optimisation to design mechanisms that can be used at scale. We show how the allocation problem facing the publisher is similar to certain resource allocation problems in networks.

Yet despite their ubiquity, such repeated auctions are not fully understood: the simplifications typically needed for analysis of single-shot auctions rarely hold in practice, new methodology is required, while new forms of advertising stretch the existing models. We give examples of some recent research, and example from live auctions.

  Bio: Peter Key is a Principal Researcher at MSR Cambridge. He leads a newly created Networks, Economics, and Algorithms team, which operates at the intersection of Computer Science, Economics and Game Theory. He is excited about the possibilities of applying research in this area to ad-auctions, markets and networks in Microsoft. Current projects include the Pricing of Media Service Provision, and Budget Smoothing in Sponsored Search Auctions. His previous work at Microsoft has involved the design and performance of networks, covering congestion control in the Internet, home networks, multipath routing, and wireless

Douglas Leith: "Decentralised Constraint Satisfaction"

Abstract: Several important resource allocation problems in wireless networks fit within the common framework of Constraint Satisfaction Problems (CSPs). These include channel allocation, power control, transmission scheduling and network coding. Inspired by the requirements of these applications, where variables are located at distinct network devices that may not be able to communicate but may interfere, we define natural criteria that a CSP solver must possess in order to be practical. We introduce a stochastic decentralized CSP solver, sketching how it provably finds a solution should one exist and illustrating its other desirable features. Using an implementation on a wireless testbed we demonstrate the decentralized solver's practical utility for one of the fundamental challenges in wireless networks, namely interference management by appropriate channel allocation.

  Bio: Douglas Leith is a Research Professor at the National University of Ireland Maynooth and Director of the Hamilton Institute. His research interests include resource allocation and measurement in wireless networks, congestion control and privacy.