CAREER: Algorithms for Environments with Incomplete Information

Cornell University, Ithaca NY

Investigators

Abstract

An increasing number of information systems, especially in networking and electronic commerce, require algorithms to make decisions without full knowledge of the optimization problem they are trying to solve. Challenges of this sort underlie decision problems in electronic commerce (where relevant information is hidden by parties who may have an incentive to misreport it), online resource allocation (where the quality of decisions in the present depends on information revealed only in the future), and decentralized networking (where system components try to optimize global objectives armed with only a local view of the network state). This research focuses on algorithms which meet provable guarantees in the face of such uncertainty. Recent developments in online learning theory and algorithmic mechanism design have opened up the exciting prospect of designing efficient algorithms with meet provable worst-case guarantees while still performing nearly as well as existing algorithms in the common case. The intellectual merit of such algorithms lies in providing an appealing bridge between worst-case and average-case analysis. The PI will pursue this prospect in several application domains, including multi-agent learning systems (studying algorithmic notions of trust and reputation based on extending online learning techniques to situations in which multiple learners share information) and auctiondesign (exploring the roles of optimal stopping theory, learning theory, and randomization over outcomes in the design of approximately profit-maximizing auctions). This research holds the potential to have a broad impact on technology and society. For example, improved algorithms for multi-agent online learning could lead to safer and better systems for e-commerce, spam filtering, and sharing information and content on the Internet. The PI's education plan further contributes to the project's impact, by developing a new undergraduate course which will make randomness a central notion in the undergraduate computer science curriculum and by encouraging the participation of graduate students and talented undergraduates in the PI's research.