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.