Seminar by Sayan Bhattacharya
Price of anarchy, auctions and approximations
Sayan Bhattacharya
Max Planck Institute for Informatics, Germany
Date: Tuesday, November 26th, 2013
Time: 11:30 AM
Venue: CS102.Abstract:
In many applications driven by the internet, computation has to be performed in the presence of strategic interactions between multiple autonomous entities. This raises the question: What happens when the input to an algorithm are controlled by rational agents, and each of them, in turn, is affected by the algorithm's output? A systematic study of this question led to the growth of ``algorithmic game theory''. In the talk I will focus on two important topics within this field -- the study of auctions, and price of anarchy.
Motivated by the electronic markets such as eBay and Google adwords, I will first visit the topic of Auction Theory from an algorithmic perspective. In this setting, an auctioneer wants to sell some items to a group of bidders. The bidders' valuations for the items are private knowledge, but they are drawn from publicly known prior distributions. An auction scheme is called ``truthful'' if it gives an incentive to every bidder to report her true value. The goal is to find a truthful auction that maximizes the seller's revenue.
Naturally, to execute the optimal auction we need to know the prior distributions. An intriguing question is to design a truthful auction that does not require the knowledge of these priors, but still manages to get a constant fraction of the optimal revenue. Such auctions are called ``prior-free''. I will conclude the first part of the talk by presenting my recent work on prior-free auctions with asymmetric bidders.
Next, I will consider the game-theoretic variant of a classical scheduling-problem. The setting captures a distributed environment with heterogeneous machines (or data centers) and jobs (or clients) that are situated across different geographical locations. The objective is to minimize the weighted sum of the completion times of the jobs. Each job, however, is a selfish agent and selects a machine that minimizes its own completion time. This defines a game between the jobs. A Nash equilibrium of this game is an outcome where no job wants to switch to another machine. The ``price of anarchy'' is the maximum possible ratio between the objective at a Nash equilibrium and the objective at the globally-optimal outcome. Intuitively, it measures the degradation in overall system-performance due to the presence of selfish jobs.
I will present a generic characterization of the scheduling policies which give a small Price of Anarchy. On the technical side, I will show how to derive this result using a linear program for the underlying optimization problem and dual-fitting.
I will conclude the talk by presenting some interesting open directions for future research.
About the speaker:
Sayan Bhattacharya is a post-doctoral researcher in Max-Planck Institute for Informatics, Saarbrücken, Germany. He did his PhD from Duke University, Durham, USA, and works in Algorithmic Game Theory.