In theoretical computer science, algorithms are usually evaluated with respect to their worst-case performance, whereas in other areas, average-case analysis is often used. Both of these approaches have drawbacks: worst-case analysis is overly pessimistic and average-case analysis often rests on unrealistic assumptions. To address these issues, a number of other analysis frameworks have been proposed including self-improving algorithms, smoothed analysis, instance-optimality, and algorithmic design based on a variety of data models. The objective of the project is to continue this line of research and develop techniques that go beyond worst-case analysis in the areas of approximation algorithms, algorithmic mechanism design and online algorithms. In the area of approximation algorithms for NP-hard problems, the project focuses on the development of approximation algorithms that achieve a kind of instance optimality. In the area of algorithmic mechanism design, the PI will continue to study the design and analysis of profit maximizing auctions in single-parameter environments and beyond. In the area of online algorithms, the PI will work to develop effective online algorithms for a fundamental and practical self-organizing data structure problem.
Through the development of more effective and practical algorithms and a deeper understanding of the performance of these algorithms in practice, this research has the potential to impact a variety of subfields of computer science including artificial intelligence, systems and networking, data mining, and electronic commerce.
In the age of the Internet, the systems and mechanisms we design must take into account the fact that participants are self-interested, and that high quality probabilitistic information about these participants and their private information is available or can be learned. Examples where these two principles apply include the following settings: scheduling tasks in the cloud, routing traffic in a network, buying and selling goods in electronic marketplaces, assigning ad-slots to sellers on search engines and on and on. Indeed, nowadays, with global markets in which large-scale resource sharing and electronic commerce is taking place among parties with diverse and selfish interests, the question of how to design algorithms or protocols with good performance in the presence of self-interested participants is increasingly important. To have maximum impact in practice, it is important that these algorithms be designed without overly pessimistic or worst-case assumptions. The most important outcomes from this grant concern the design of such mechanisms for electronic commerce and especially for pricing and auction design. Some of the auction design settings considered are the following: 1) when the bidders' values for the items are correlated or common, as in auctions for the right to drill for oil in a certain location was studied. 2) auction design with new utility models, for example, when bidders not only care about their own profit, but also care about making sure other bidders don't do well. 3) settings where consumers do not know precisely how much they value goods, but rather learn it over time, or else can pay money to learn more about it. 4) multiple item, multiple bidder settings, where the auctioneer does not know the distribution of agents values. In all of the above settings, among others, the PI and coauthors have shown how to design auctions with strong theoretical profit guarantees, taking into account both the incentives of the bidders, and the probabilistic information available.
