Grant: Discovery Grants Program - Individual

Fundamental problems in computer science revolve around the discovery of efficient algorithms. In the past 5-6 years, computer scientists have witnessed an explosive growth of interest in algorithmic game theory which deals with models where there are no trusted coordinator and the outcome depends on the cooperation or competition by parties of different interests. One aspect of my research will focus on network routing and its generalizations as a non-cooperative game - a line of research in algorithmic game theory. As an example, this work includes a precise analysis of the extension of the classical selfish routing model to the model in which we incorporate the concept of "time" (when all users of a link do not experience the same latency). At the same time, the widespread use of search engines on the Web and its ramifications have raised a variety of important algorithmic issues. In a second aspect of my research, I will consider those issues that concern the sponsored search advertisements. Finding optimum bidding strategies for advertisers, studying the convergence of such strategies (as both the search engine and the advertiser seek for a stable market) and bringing the concept of "externality" (when advertisers care who are the other advertisers on the page) to the existing models are parts of this work. The goods that are being sold in search ads auctions (the search queries) have two interesting characteristics: (i) they should be allocated to the buyers in a fraction of a second or they will perish instantly; and (ii) their total supply is unknown. I will examine the on-line nature of these auctions and in particular, focus on finding optimum "reserve prices" for keywords. Designing fast algorithms or proving that no fast algorithm exists intimately relies, in many cases, on geometrical and graph theoretic characteristics of the problem. I also intend to work on some of the important problems in graph colouring - a traditionally important area of graph theory for computer scientists. Structure of colour-critical graphs, improper colourings and list-colouring of certain classes of planar graphs will be examined.