CAREER: Algorithms for Environments with Incomplete Information

越来越多的信息系统，特别是在网络和电子商务中，要求算法在不完全了解它们试图解决的优化问题的情况下做出决策。这类挑战是电子商务(相关信息被可能有误报动机的当事方隐瞒)、在线资源分配(目前决策的质量取决于仅在未来披露的信息)和分散联网(系统组成部分试图优化全球目标，仅凭对网络状态的本地看法)方面的决策问题的根源。在线学习理论和算法机制设计的最新发展为设计满足可证明最坏情况保证的高效算法开辟了令人兴奋的前景，而在一般情况下仍能获得与现有算法相近的性能。这类算法的智力优势在于在最坏情况分析和平均情况分析之间提供了一座吸引人的桥梁。PI将在几个应用领域探索这一前景，包括多智能体学习系统(基于将在线学习技术扩展到多个学习者共享信息的情况来研究信任和声誉的算法概念)和拍卖设计(探索最优停止理论、学习理论和结果随机化在设计近似利润最大化拍卖中的作用)。这项研究具有对技术和社会产生广泛影响的潜力。例如，改进的多代理在线学习算法可以为电子商务、垃圾邮件过滤以及在互联网上共享信息和内容带来更安全、更好的系统。PI的教育计划进一步促进了该项目的影响，开发了一门新的本科课程，使随机性成为本科计算机科学课程的核心概念，并鼓励研究生和有才华的本科生参与PI的研究。

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 networkstate). 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 excitingprospect 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.