AF: Small: Non-revelation Mechanism Design

机制设计管理着为战略（即自私）代理分配商品问题的协议设计，并在计算机科学和经济学中都有应用。这样的分配问题随处可见：广告商通过在线搜索引擎竞标，在查询回复旁边张贴他们的链接；互联网流量争夺路由器接入；小学生们在精英学校竞争有限的名额。这些过程可以实现不同的目标：搜索引擎希望从广告销售中获得最大的收入；互联网希望将所有用户的总通信延迟最小化；学区希望尊重学校作业的公平性。从历史上看，机制设计的研究几乎完全集中在对主体来说简单的机制上，要求每个主体真实地揭示其偏好符合其最大利益。这种机制被称为启示机制。产生的机制通常都有复杂的规则，并且依赖于对环境的详细假设。本项目发展了非启示机制的设计和分析理论，这可能需要代理进行策略优化，但简单而稳健。这个项目更广泛的影响包括对经济学文献的贡献，工业机制设计理论的发展，以及将在软件开发工作和研究中使用开发技能的本科生和博士生的培训。本项目将解决非启示机制设计中的一些基本问题。首先，简单的非启示机制可能具有需要根据环境进行调整的参数，而该环境可能不是固定的。例如，供给和需求可能都在变化。该项目的目标是了解具有良好性能并且可以直接从机制的历史数据进行调优的机制家族，并确定执行此调优的统计有效过程。其次，设计的一个特别可靠的标准是，该机制在任何环境条件下都表现良好；也就是说，没有任何参数化。该项目将研究稳健的非启示机制的设计，并量化非启示机制的稳健保证可能比启示机制的最佳稳健保证更好的程度。第三，在非启示机制中，真实的启示不是代理人的最佳反应，代理人将需要采取战略行动。代理可能会发现，只有经过一些尝试和错误（例如，通过学习算法）后，才会有战略性的好行为。当所有代理都这样做时，所产生的动作将是相关的。本课题旨在研究机构在这种自然动力学下的性能及其收敛性。

Mechanism Design governs the design of protocols for problems of allocation-of-goods to strategic (i.e., selfish) agents and has applications in both computer science and economics. Such allocation problems are all around: advertisers compete in an auction through online search engines to post their links beside query responses; Internet traffic competes for router access; elementary students compete for a limited number of openings in an elite magnet school. These processes can aim to achieve different objectives: search engines want to maximize revenue from ad sales; the Internet wants to minimize the total communication delays of all users; school districts want to respect fairness in school assignments.Historically, research in mechanism design focuses almost exclusively on mechanisms that are simple for the agents, requiring that it is in each agent's best interest to truthfully reveal its preference. Such mechanisms are known as revelation mechanisms. The mechanisms that result often both have complex rules and are dependent on detailed assumptions about the environment. This project develops the theory for design and analysis of non-revelation mechanisms, which may require strategic optimization by the agents, but are simple and robust. Broader impacts of this project include contribution to the economics literature, development of theory that informs the design of mechanisms in industry, and the training of undergraduates and Ph.D. students who will use the developed skills in software development jobs and research.This project will address a number of foundational questions in non-revelation mechanism design. First, simple non-revelation mechanisms may have parameters that need to be tuned to the environment and this environment may not be stationary. For example, both supply and demand may be evolving. A goal of the project is to understand families of mechanisms that both have good performance and can be tuned directly from historical data from the mechanism, and to identify statistically efficient procedures for performing this tuning.Second, an especially robust criterion for design is that the mechanism perform well under any environmental conditions; i.e., without any parameterization. The project will investigate the design of robust non-revelation mechanisms and quantify the extent to which robust guarantees for non-revelation mechanisms may be better than the best robust guarantees possible for revelation mechanisms. Third, in non-revelation mechanisms, where truthful revelation is not an agent's best response, agents will need to take actions strategically. Agents may find strategically good actions may only come after some trial and error, e.g., via learning algorithms. When all agents are behaving thus, the resulting actions will be correlated. The project aims to study the performance of mechanisms under such natural dynamics and their convergence properties.