Assistant Professor

助理教授

• 批准号: RGPIN-2015-06127
• 负责人: Cai, Yang
• 金额: $ 2.99万
• 依托单位: McGill University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=646681
• 关键词: Assistant; Professor

Recent years have seen a convergence of ideas and research goals between Computer Science and Economics. Computer Science enabled the development of a new genre of computational platforms that require economic as well as engineering thinking for their proper design and study; primary examples are those systems created and enabled by the Internet. Economics brought to the discussion quantitative models and tools useful to analyze these systems. At the same time, it became clear that the computational nature of these models and tools is crucial for them to be used to study systems with thousands or even millions of interacting individuals. Motivated by this realization, computer scientists have taken in the past decade a fresh, computational look at Game Theory and Economics. One major focus is Algorithmic Mechanism Design, in which we seek for computational efficient systems that are so cleverly designed that users' selfish behavior helps advance the designer's objectives. The goal of this proposal is to enrich Algorithmic Mechanism Design from two directions that - to the PI's opinion - has not been sufficiently explored in the literature. We aim (i) to understand how the complexity of an auction affects its performance, and (ii) to apply Algorithmic Mechanism Design to systems beyond auctions.******Algorithmic Mechanism Design has mainly focused on optimal auction design for various objectives so far. However, the optimal auction is usually complicated and thus hard to implement in practice. The first half of this proposal aims to understand how the complexity of an auction affects its performance, and propose new simple practical auctions with provable performance guarantees. I will employ tools from Theoretical Computer Science and Applied Probability (1) to search for simple and (nearly-) optimal auctions in certain basic and fundamental multi-item multi-bidder settings, (2) to identify settings where the optimal auctions have simple formats, and (3) to study the computational complexity of finding a Bayes-Nash equilibrium in simple non-truthful auction games for the combinatorial auction problem. The second part of this proposal aims to expand the applicability of Algorithmic Mechanism Design to settings beyond auctions. I will import concepts, ideas and techniques from Economics (1) to design mechanisms for data science - incentivizing workers to provide high quality data for statistical estimation with low cost, and (2) to design computational efficient mechanism for fair resource allocation. **

近年来，计算机科学和经济学之间的思想和研究目标有所融合。计算机科学使一种新类型的计算平台的发展成为可能，这种平台需要经济和工程思维来进行适当的设计和研究;主要的例子是由互联网创建和启用的那些系统。经济学带来的讨论定量模型和工具，有助于分析这些系统。与此同时，很明显，这些模型和工具的计算性质对于它们用于研究具有数千甚至数百万交互个体的系统至关重要。在这种认识的推动下，计算机科学家在过去十年中对博弈论和经济学进行了全新的计算研究。一个主要的焦点是计算机机制设计，在其中我们寻求计算效率高的系统，这些系统设计得如此巧妙，以至于用户的自私行为有助于推进设计者的目标。本提案的目标是从两个方向丰富机械机构设计，PI认为这两个方向在文献中尚未得到充分探讨。我们的目标是（i）了解拍卖的复杂性如何影响其性能，以及（ii）将拍卖机制设计应用于拍卖之外的系统。目前，拍卖机制设计主要集中在各种目标下的最优拍卖设计。然而，最优拍卖通常是复杂的，从而难以在实践中实现。该提案的前半部分旨在了解拍卖的复杂性如何影响其性能，并提出新的简单实用的拍卖与可证明的性能保证。我将使用理论计算机科学和应用概率的工具（1）在某些基本和基本的多项目多投标人设置中搜索简单和（接近）最优拍卖，（2）确定最优拍卖具有简单格式的设置，以及（3）研究在简单的非真实拍卖游戏中寻找组合拍卖问题的贝叶斯-纳什均衡的计算复杂性。本提案的第二部分旨在将拍卖机制设计的适用性扩展到拍卖以外的环境。我将从经济学中引入概念，思想和技术（1）设计数据科学的机制-激励工作人员以低成本提供高质量的统计估计数据，以及（2）设计公平资源分配的计算效率机制。**